1. 项目背景与核心需求拆解1.1 为什么直线裁剪是图形学里绕不开的一课做计算机图形学实验做到第六个基本上已经把直线生成、圆生成、多边形填充这些基础 rasterization 算法摸了一遍。到了直线裁剪这个环节很多人第一反应是“不就是把屏幕外的线去掉吗”但真动手写起来才发现事情没那么简单。Cohen-Sutherland 裁剪算法之所以成为图形学课程里的经典必做实验核心原因在于它用一个非常优雅的编码思路把“线段与矩形窗口求交”这个看似需要大量几何计算的问题转化成了几次位运算和简单的参数方程求解。这个实验的典型场景是这样的你在 MFC 的单文档或者对话框程序里画了一条从 (-100, -50) 到 (500, 400) 的直线但你的绘图窗口客户区只有 800x600如果不做裁剪直接调用MoveTo/LineTo在 GDI 层面虽然也能画但一旦你要做更复杂的填充、消隐或者拾取操作超出窗口的像素会带来大量无效计算和逻辑错误。Cohen-Sutherland 算法解决的就是这个问题给定一个矩形裁剪窗口和一条线段快速判断线段是完全可见、完全不可见还是部分可见并对部分可见的线段求出精确的裁剪交点。适合谁来参考这篇内容如果你正在做图形学实验、需要交 MFC 版本的 Cohen-Sutherland 实现或者你虽然写过但对其中的编码逻辑、交点计算顺序、边界情况处理还不太清楚那这篇东西就是给你准备的。我会从设计思路、编码细节、MFC 集成、调试排查几个层面把它讲透代码可以直接抄作业但更重要的是理解每一步为什么这么写。1.2 实验的核心需求与常见坑点从输入标题来看这个实验有几个明确的关键词计算机图形学、实验6、直线裁剪、Cohen Sutherland裁剪算法、MFC。拆开来看核心需求无非是这几条在 MFC 环境下建立一个可交互的绘图程序能够绘制直线和裁剪窗口实现 Cohen-Sutherland 算法的完整逻辑包括区域编码、可见性判断、交点计算和线段替换能够直观地展示裁剪前后的效果对比最好能动态调整裁剪窗口或线段位置处理各种边界情况线段完全在窗口内、完全在窗口外、与一条边相交、与两条边相交、经过顶点、平行于边界等。我见过不少同学做这个实验时踩的坑集中在这几个地方第一区域编码的位顺序搞反了导致判断逻辑全错第二交点计算时没有区分线段与哪条边界相交用错了参数 t 的计算公式第三MFC 的坐标系统和算法用的坐标系不一致裁剪结果偏移第四循环退出条件写错导致死循环或者漏裁。这些坑我在后面会逐一展开先把这个算法的设计思路讲清楚。2. Cohen-Sutherland 算法的设计思路与编码原理2.1 区域编码用四位二进制描述点的位置Cohen-Sutherland 算法最核心的设计就是区域编码region code。它把整个二维平面按照裁剪窗口的边界分成九个区域每个区域用一个四位二进制码来表示。具体规则是这样的第 0 位最低位点在窗口左侧编码为 1记为 LEFT第 1 位点在窗口右侧编码为 1记为 RIGHT第 2 位点在窗口下方编码为 1记为 BOTTOM第 3 位最高位点在窗口上方编码为 1记为 TOP。一个点的编码就是把这四个条件分别判断后组合起来。比如一个点在窗口左上方那它的编码就是 LEFT | TOP 0001 | 1000 1001。如果点在窗口内部四位全是 0编码为 0000。这里有一个非常关键的细节编码的位顺序并不影响算法正确性但必须与后续的判断逻辑保持一致。我建议按照 LEFT1、RIGHT2、BOTTOM4、TOP8 来定义这样用位或运算组合起来很自然判断时用位与运算也很清晰。很多教材上把 TOP 放在最低位BOTTOM 放在最高位如果你照着抄但判断时又用了另一套顺序那结果肯定不对。用生活化的类比来说这就像给每个点发一张“身份证”四位分别代表“是否在左边界外”“是否在右边界外”“是否在下边界外”“是否在上边界外”。有了这张身份证判断一条线段的可见性就变成了对两个端点身份证的简单运算。2.2 可见性快速判断全零与位与运算有了端点的区域编码之后判断线段可见性就变得非常高效。设线段两个端点分别为 P1 和 P2编码分别为 code1 和 code2判断逻辑如下完全可见code1 0 且 code2 0。两个端点都在窗口内线段必然完全可见直接保留。完全不可见code1 code2 ! 0。两个端点在同一侧窗口外比如都在左侧那这条线段必然完全在窗口外直接丢弃。部分可见以上两个条件都不满足说明线段与窗口边界有交点需要进一步计算。这里重点解释一下为什么code1 code2 ! 0就能判断完全不可见。位与运算的性质是只要两个编码在同一个位上都是 1结果就不为 0。比如 code1 1001左上code2 1000上它们在第 3 位都是 1说明两个点都在窗口上方线段自然完全在上方窗口外。这个判断的巧妙之处在于它不需要做任何除法或浮点运算一次位与就能排除大量显然不可见的线段。注意code1 code2 ! 0是判断完全不可见的充分条件但不是必要条件。也就是说有些线段虽然 code1 code2 0但仍然可能完全不可见比如线段从窗口左上方穿过到右下方但中间完全避开了窗口。这种情况需要靠后续的交点计算和迭代来排除。2.3 交点计算从窗口外端点向边界逼近当线段被判定为部分可见时就需要计算它与窗口边界的交点。Cohen-Sutherland 的策略是每次取一个在窗口外的端点根据它的编码确定它相对于哪条边界越界然后计算线段与该边界的交点用交点替换该端点并重新编码。这个过程循环进行直到线段被完全接受或完全拒绝。具体来说假设当前处理的端点是 P它的编码是 code。我们按顺序检查如果 code 的 LEFT 位为 1说明 P 在窗口左侧计算线段与左边界 x xmin 的交点否则如果 code 的 RIGHT 位为 1计算与右边界 x xmax 的交点否则如果 code 的 BOTTOM 位为 1计算与下边界 y ymin 的交点否则如果 code 的 TOP 位为 1计算与上边界 y ymax 的交点。交点的计算公式根据边界类型不同而不同。以左边界为例已知线段参数方程x x1 t * (x2 - x1) y y1 t * (y2 - y1)当 x xmin 时可以解出 t (xmin - x1) / (x2 - x1)然后 y y1 t * (y2 - y1)。这里有一个必须注意的点如果 x2 - x1 0即线段垂直于 x 轴那么与左右边界要么平行要么重合不会产生交点此时应该跳过左右边界的判断。同理与上下边界求交时如果 y2 - y1 0也要跳过。这个计算过程用代码实现时建议把“计算与某条边界的交点”封装成一个函数传入边界类型和线段端点返回交点坐标。这样主循环的逻辑会非常清晰。2.4 算法主循环迭代直到收敛把上面的步骤串起来Cohen-Sutherland 的主循环逻辑是这样的while (true) { 计算 code1, code2; if (code1 0 code2 0) { 完全可见保留; break; } if (code1 code2 ! 0) { 完全不可见丢弃; break; } 选择一个在窗口外的端点 P; 根据 P 的编码确定越界边界; 计算线段与该边界的交点; 用交点替换 P; }这个循环最多执行四次因为每次替换至少会把一个端点移到窗口边界上使其在某个方向上的编码位变为 0。最坏情况下线段从窗口的一个角穿到另一个角需要四次裁剪。这个性质保证了算法的终止性不会出现死循环。实操心得在写循环时我建议用一个计数器限制最大迭代次数为 4 或 5虽然理论上不会超过 4 次但万一编码逻辑有 bug这个计数器可以防止程序卡死方便调试。3. MFC 环境下的完整实现与关键代码3.1 MFC 项目搭建与坐标系统一在 MFC 里做这个实验第一步不是写算法而是把坐标系统一好。MFC 的默认坐标系统是客户区左上角为原点x 向右递增y 向下递增。而图形学教材里的 Cohen-Sutherland 算法通常假设左下角为原点y 向上递增。如果你直接把教材上的坐标代入 MFC 的绘图函数裁剪结果会上下颠倒。解决这个问题有两种常见方案。第一种是在算法内部统一使用 MFC 坐标即 y 轴向下裁剪窗口的 ymin 对应客户区上边界ymax 对应下边界。第二种是保持算法使用数学坐标系在最终绘图时做一次 y 轴翻转。我推荐第一种方案因为少一次坐标变换就少一个出错的机会而且 MFC 的CRect类本身就是左上角为 (left, top)、右下角为 (right, bottom)直接用它的成员变量作为裁剪窗口边界很自然。具体来说假设你的绘图窗口客户区矩形是CRect rectClient你想在中间定义一个裁剪窗口可以这样写CRect rectClip; rectClip.left 200; rectClip.top 150; rectClip.right 600; rectClip.bottom 450;那么在算法中xmin rectClip.leftxmax rectClip.rightymin rectClip.topymax rectClip.bottom。注意这里的 ymin 在数值上小于 ymax但对应的是屏幕上方这与数学坐标系相反但只要编码逻辑一致算法本身不受影响。3.2 区域编码函数的实现细节区域编码函数是整个算法的基石我把它写成这样const int LEFT 1; // 0001 const int RIGHT 2; // 0010 const int BOTTOM 4; // 0100 const int TOP 8; // 1000 int EncodePoint(double x, double y, const CRect clip) { int code 0; if (x clip.left) code | LEFT; else if (x clip.right) code | RIGHT; if (y clip.top) code | TOP; // 注意MFC 中 y 小的是上方 else if (y clip.bottom) code | BOTTOM; return code; }这里有一个容易搞混的地方在 MFC 坐标下y 值越小越靠上所以y clip.top表示点在窗口上方应该编码为 TOP。很多同学按照数学坐标的习惯写成y clip.top编码为 BOTTOM结果裁剪出来的线段位置完全不对。这个细节我在第一次做实验时就踩过调了半天才发现是编码方向反了。另外判断条件用还是也有讲究。如果点正好在边界上编码应该为 0表示它在窗口内。所以用严格的小于和大于边界上的点不编码。这样处理可以避免边界点被反复裁剪。3.3 交点计算函数的封装交点计算我封装成一个函数根据传入的边界类型返回交点坐标bool ComputeIntersection(int edge, double x1, double y1, double x2, double y2, const CRect clip, double ix, double iy) { double dx x2 - x1; double dy y2 - y1; if (edge LEFT) { if (dx 0) return false; double t (clip.left - x1) / dx; ix clip.left; iy y1 t * dy; } else if (edge RIGHT) { if (dx 0) return false; double t (clip.right - x1) / dx; ix clip.right; iy y1 t * dy; } else if (edge TOP) { if (dy 0) return false; double t (clip.top - y1) / dy; iy clip.top; ix x1 t * dx; } else if (edge BOTTOM) { if (dy 0) return false; double t (clip.bottom - y1) / dy; iy clip.bottom; ix x1 t * dx; } return true; }这个函数里我加了dx 0和dy 0的保护防止除零。虽然理论上主循环在选择边界时已经避免了平行情况但加上这层保护更稳妥。返回false表示无法计算交点主循环里遇到这种情况可以直接判定线段不可见。3.4 主裁剪函数的完整实现把编码和交点计算组合起来主裁剪函数如下bool CohenSutherlandClip(double x1, double y1, double x2, double y2, const CRect clip) { int code1 EncodePoint(x1, y1, clip); int code2 EncodePoint(x2, y2, clip); int guard 0; while (guard 5) { if ((code1 | code2) 0) { return true; // 完全可见 } if ((code1 code2) ! 0) { return false; // 完全不可见 } int codeOut code1 ? code1 : code2; double ix, iy; int edge 0; if (codeOut LEFT) edge LEFT; else if (codeOut RIGHT) edge RIGHT; else if (codeOut TOP) edge TOP; else if (codeOut BOTTOM) edge BOTTOM; if (!ComputeIntersection(edge, x1, y1, x2, y2, clip, ix, iy)) { return false; } if (codeOut code1) { x1 ix; y1 iy; code1 EncodePoint(x1, y1, clip); } else { x2 ix; y2 iy; code2 EncodePoint(x2, y2, clip); } } return false; }这个函数直接修改传入的端点坐标返回true表示线段可见裁剪后的坐标在 x1,y1,x2,y2 中返回false表示完全不可见。guard计数器是我加的保险正常情况不会用到。注意codeOut code1 ? code1 : code2这行代码的意思是优先选择 code1 不为 0 的端点。如果 code1 为 0说明它在窗口内那就选 code2。这个选择顺序不影响正确性但保持固定顺序有助于调试。3.5 在 MFC 中绘制裁剪窗口与线段算法写好了接下来要在 MFC 的OnDraw或OnPaint里把它用起来。我的做法是void CGraphicsView::OnDraw(CDC* pDC) { CRect rectClip(200, 150, 600, 450); // 绘制裁剪窗口 CPen penClip(PS_SOLID, 2, RGB(0, 0, 255)); CPen* pOldPen pDC-SelectObject(penClip); pDC-Rectangle(rectClip); // 绘制原始线段虚线 CPen penOriginal(PS_DOT, 1, RGB(128, 128, 128)); pDC-SelectObject(penOriginal); pDC-MoveTo(m_ptStart); pDC-LineTo(m_ptEnd); // 裁剪并绘制结果 double x1 m_ptStart.x, y1 m_ptStart.y; double x2 m_ptEnd.x, y2 m_ptEnd.y; if (CohenSutherlandClip(x1, y1, x2, y2, rectClip)) { CPen penClipped(PS_SOLID, 2, RGB(255, 0, 0)); pDC-SelectObject(penClipped); pDC-MoveTo((int)round(x1), (int)round(y1)); pDC-LineTo((int)round(x2), (int)round(y2)); } pDC-SelectObject(pOldPen); }这里用灰色虚线画原始线段红色实线画裁剪后的线段蓝色矩形画裁剪窗口视觉效果很直观。注意MoveTo和LineTo接收的是整数坐标所以要把 double 四舍五入。4. 常见问题排查与调试技巧实录4.1 裁剪结果偏移或颠倒这是最常见的问题九成以上是坐标系统一没做好。如果你发现裁剪后的线段上下颠倒检查一下编码函数里 TOP 和 BOTTOM 的判断条件。在 MFC 坐标下y clip.top是上方应该编码为 TOP如果你写成了 BOTTOM那所有上方的点都会被当成下方处理裁剪结果自然就反了。另一个可能的原因是裁剪窗口的 top 和 bottom 传反了。CRect的构造函数是CRect(left, top, right, bottom)其中 top 通常小于 bottom。如果你手动传入了CRect(200, 450, 600, 150)那 top 大于 bottom算法里的比较逻辑就会全部失效。建议在算法开始前加一句断言ASSERT(clip.top clip.bottom clip.left clip.right);。4.2 线段与边界平行时程序崩溃或结果错误这个问题通常出现在交点计算函数里没有做除零保护。当线段垂直于 x 轴时dx 0计算与左右边界的交点时会出现除以零。虽然主循环在选择边界时如果端点在左右两侧理论上 dx 不会为 0因为端点在窗口外另一个端点在窗口内或另一侧x 坐标必然不同但边界情况比如线段两个端点都在窗口左侧但 y 坐标不同此时 code1 code2 ! 0会直接判定不可见不会进入交点计算。真正会出问题的是线段一个端点在窗口内、另一个端点在窗口外且垂直于边界的情况此时 dx 可能为 0。加上if (dx 0) return false;这层保护就能避免崩溃。4.3 线段经过窗口顶点时的处理当线段恰好经过裁剪窗口的顶点时比如从左上角外部穿过顶点进入窗口内部编码和交点计算可能会出现边界情况。具体表现为交点计算出来的坐标正好等于顶点坐标重新编码后该点编码为 0算法继续处理另一个端点。这种情况算法本身是能正确处理的但如果你在绘制时用了整数坐标可能会因为四舍五入导致 1 像素的偏差。我的建议是算法内部全程用 double只在最终绘制时取整。4.4 常见问题速查表问题现象可能原因排查方法解决方案裁剪结果上下颠倒TOP/BOTTOM 编码反了打印端点的区域编码检查 y 比较方向MFC 中 y 小为上线段完全不可见但实际可见code1 code2 判断有误手动计算两个端点的编码确认位与运算的位顺序一致程序卡死或死循环循环退出条件缺失加断点看端点是否在变化加 guard 计数器限制迭代次数交点坐标偏差大参数 t 计算用错边界检查 ComputeIntersection 的边界类型确认传入的 edge 与端点编码匹配裁剪后线段超出窗口交点计算后未重新编码在替换端点后打印新编码确保每次替换后都调用 EncodePoint垂直线段崩溃除零错误检查 dx 或 dy 是否为 0在交点计算中加除零保护4.5 调试技巧可视化区域编码调试这个算法最有效的方法是把每个端点的区域编码打印出来。你可以在EncodePoint函数里加一句TRACE输出TRACE(Point (%.1f, %.1f) code %d%d%d%d\n, x, y, (code TOP) ? 1 : 0, (code BOTTOM) ? 1 : 0, (code RIGHT) ? 1 : 0, (code LEFT) ? 1 : 0);这样在 Visual Studio 的输出窗口里就能看到每个点的编码对照算法逻辑一步步检查很快就能定位问题。我当年做这个实验时就是靠这个方法发现自己的 TOP 和 BOTTOM 写反了。实操心得建议在实验报告中附上几组典型测试用例包括完全可见、完全不可见、与一条边相交、与两条边相交、经过顶点、平行于边界这六种情况每组都打印出裁剪前后的坐标和编码变化。这样不仅实验报告更充实也能帮你彻底理解算法的每一步。5. 算法扩展与性能优化思路5.1 从 Cohen-Sutherland 到 Liang-BarskyCohen-Sutherland 算法虽然经典但它的交点计算是基于边界逐次逼近的每次只裁剪一条边界最坏情况下需要四次迭代。后来出现的 Liang-Barsky 算法用参数化方法一次性求出线段与窗口的四个交点参数效率更高。如果你做完这个实验还有余力可以尝试实现 Liang-Barsky 作为对比在实验报告里分析两种算法在不同线段分布下的性能差异。Liang-Barsky 的核心思想是把线段写成参数方程然后对四条边界分别求出参数 t 的取值范围最后取交集。如果交集为空线段不可见否则用交集的上下界作为裁剪后的参数。这个算法不需要迭代一次计算就能得到结果在大量线段裁剪的场景下优势明显。5.2 批量线段裁剪与窗口划分在实际应用中往往需要对成百上千条线段做裁剪。这时候可以考虑两个优化方向一是用包围盒快速排除大量完全不可见的线段二是把裁剪窗口划分成多个子区域用空间索引加速查询。不过对于实验级别的程序来说这些优化不是必须的理解算法本身才是重点。5.3 在 MFC 中加入交互功能为了让实验演示效果更好可以在 MFC 程序里加入鼠标交互按下鼠标左键确定线段起点拖动确定终点松开后自动裁剪并绘制。还可以加入滑块控件调整裁剪窗口的大小和位置实时观察裁剪结果的变化。这些交互功能虽然不涉及算法核心但能显著提升实验的展示效果也是实验报告中加分的地方。实现鼠标交互的关键是处理OnLButtonDown、OnMouseMove和OnLButtonUp三个消息。在OnMouseMove里用Invalidate触发重绘在OnDraw里根据当前鼠标位置动态绘制预览线段。注意要用双缓冲避免闪烁这个在 MFC 里可以通过CMemDC或者手动创建兼容 DC 来实现。5.4 浮点精度问题的处理Cohen-Sutherland 算法涉及浮点除法和比较在极端情况下可能会出现精度问题。比如线段端点恰好落在边界上由于浮点误差编码可能不为 0导致算法多做一次无用的裁剪。解决方法是引入一个很小的 epsilon在比较时允许一定误差const double EPS 1e-6; if (x clip.left - EPS) code | LEFT; else if (x clip.right EPS) code | RIGHT;这样边界附近的点会被视为在窗口内避免不必要的裁剪。不过 epsilon 的选择要谨慎太大可能导致真正需要裁剪的线段被误判为可见太小则起不到作用。1e-6 对于屏幕坐标来说通常足够了。6. 实验报告撰写与评分要点6.1 实验报告的结构建议如果你需要提交实验报告建议按照这个结构来组织算法原理简述、核心数据结构与编码定义、关键代码片段与注释、测试用例与结果截图、问题与解决过程、心得体会。其中测试用例部分要覆盖前面提到的六种典型情况每种都附上裁剪前后的坐标和截图对比。问题与解决过程部分把你踩过的坑写进去这往往是老师最看重的部分因为它体现了你的实际动手能力。6.2 代码规范与注释MFC 项目的代码要注意命名规范区域编码的常量用全大写函数名用驼峰或下划线分隔保持一致。关键逻辑处加注释特别是编码判断和交点计算的部分注释要说明“为什么这么写”而不是“这行代码做了什么”。比如code1 code2 ! 0这行注释应该写“两个端点在同一侧窗口外线段完全不可见”而不是“位与运算”。6.3 演示与答辩准备如果实验需要答辩演示提前准备好几组典型线段包括一条完全可见的、一条完全不可见的、一条穿过窗口的、一条经过顶点的。演示时先展示原始线段和裁剪窗口再展示裁剪结果最后打开 TRACE 输出展示编码变化过程。老师如果问“为什么最多循环四次”你可以回答“每次裁剪至少把一个端点移到边界上使其在一个方向上的编码位变为 0四个方向最多四次”。我个人在实际操作中的体会是Cohen-Sutherland 算法看起来简单但真正自己从头写一遍并且处理各种边界情况对理解图形学里的裁剪、编码、参数化求交这些概念非常有帮助。做完这个实验之后再去看 Liang-Barsky 或者更复杂的裁剪算法会发现思路是相通的。最后再分享一个小技巧如果你在 MFC 里调试时发现绘图闪烁严重可以在OnDraw里先用CreateCompatibleDC创建一个内存 DC把所有绘制操作先在内存 DC 上完成最后一次性BitBlt到屏幕 DC这样界面会流畅很多。