1. 数学分析
为什么我们要画2D直线，要做2D的直线-矩形裁剪？原因很简单，无论游戏世界是2D的还是3D的，最终都要投影到玩家的屏幕上，3D的东西最终要是要投影到视平面上。所以3D游戏仍然有很多东西要在2D视平面上做。对于3D游戏的裁剪就有两种方法：一是在3D空间做裁剪，利用视域体的各个面与三角形中直线的关系来做，这叫做立方体空间裁剪；另一种是，把3D物体先投影在2D视平面上，然后在视平面上对2D直线做矩形裁剪，叫作图像空间裁剪。三角形都是由直线组成的，屏幕是矩形的，所以用矩形裁剪一条直线是非常重要的，而且也不是想当然的简单的，也有很多因素要考虑。
1) 直线被矩形裁剪的四种情况
直线被矩形裁剪只有以下4种情况，如图：
2) 裁剪的核心问题？
我们来看看，裁剪的核心问题是什么：
如上图，两个端点分别为p0,p1的直线线段，被某一矩形裁剪。裁剪的过程是给定输入值x0,y0,x1,y1和矩形RECT，输出被裁剪后的直线两端点p0',p1'的坐标x0',y0',x1',y1'。
通过观察上图，我们可以知道，我们其实就在求两条直线的交点，一条是红线，一条是矩形的某个边。这让我们想起了几何学时的几种直线表示形式，然后求交点就是解一个方程组的过程。这没有错，但是我们可以走捷径，因为矩形的某个边不是水平线，就是垂直线，所以这第二条直线的表示非常简单。垂直线是x = c，水平线是y = c。
我们来表示一下这条红线。比如我们用点斜式：
斜率m = (y2 - y1) / (x2 - x1)
点斜式： y - y1 = m * (x - x1)
整理后，用y表示x：
x = (y - y1) / m + x1
也可以用x表示y：
y = m * (x - x1) + y1
所以与某个矩形的边的交点，可以把那个边线的表示形式直接代入，即可求得。
3) Cohen-Sutherland
上面我们解决了核心问题，那就是如何求交点。而Cohen-Sutherland算法为我们解决了另一个文章开头所说的问题，就是如何处理直线与矩形之间的4种关系。
该算法虽然简单，但极其精妙，后面会讲如何精妙！它把空间分成了各个部分，并赋予了相应的位代码，所以只使用少量的if语句，并且还是位运算，根据直线的两端点，即可判断出是上面哪种关系，如图：
如果你想感动一下，那一定要非常仔细的研究这个图了。
首先，我们看红色代码的部分，请不要看那个黑色的十进制code，中间裁剪矩形的代码是0000。正左方、正右方、正下方、正上方分别是：
0001
0010
0100
1000
即，他们每个是其中的一个位标记，所以可以通过两两做或操作(|)，来得到斜着的4个角的代码(绿色)。
首先，根据这些特性，我们可以做一些工作了，我们定义p1code、p2code分别表示直线的两个端点在这张图的位置编码，我们以p1code为例，p2code相同，就不贴代码了，下面一组简单的判断，就能求得恰当的p1code：
int p1code = 0; if (y1 < rect.top) p1code |= 8; else if (y1 > rect.bottom) p1code |= 4; if (x1 < rect.left) p1code |= 1; else if (x1 > rect.right) p1code |= 2;
也许你觉得这没有什么，但神奇的是，通过现在的p1code和p2code的位编码的组合，我们已经可以使用仅仅一个位运算操作来判断线段是否完全被删除，即求p1code & p2code的值。你可以尝试一下，当点p1和点p2在同一侧时，比如都在上方，无论是在左上、正上还是右上，这个表达式的结果都是1；而只要有一个点不在这一侧，则这个表达式必然是0。所以可以只用一个位运算来过滤掉大量的裁剪操作。
还有一个表达式则很容易理解了：p1code == 0 && p2code == 0，当这个表达式为true时，则直线完全被保留。
这时可能读者会问了，还有一种完全删除的情况并没有被排除，那就是虽然两个点在不同侧，但是直线仍都在矩形的外面，应该也被全删除。对于这种情况，没有办法，我们无法在现有的条件下来判断了，在上面这两个表达式过滤完大部分情况后，这种特殊情况只能在我们马上要做的具体求点的过程里面来判断了。下面我们来做这件事。
对于直线的起始端点p0来说，在正方向和斜方向处理的复杂度不同，请看下图：
请注意，我只画了从p0发射的必然与相邻的矩形边缘有交点的情况，而所有没画其他情况，其实那些其他情况，大部分已经被上面所说的那两个表达式排除了。还有一种情况是，比如p0在N这个位置，但是他与矩形上边缘直线的交点在矩形的外面，对于这种情况，我们先把交点算出来，在计算完两个端点分别的新值后再来判断，这个后面会讲。
对于在正方向(W、E、S、N)，已经可以直接求出p0与矩形边缘线的交点坐标了，以N为例：
switch(p1code)
{
case 0: // C
break;
case 8: // N
{
ny1 = rect.top;
nx1 = x1 + (rect.top - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
} break;
}
上面的代码求得了p1点的裁剪后的新点np1的坐标(nx1, ny1)。这个就是利用上文的点斜式推得的公式计算的。可能你会发现有点地方不一样，在求nx1的时候我们加了个0.5，这是因为出现了除法，我们要把最后一步除法变成浮点数除法，然后通过+0.5，再舍弃小数位来达到四舍五入的目的。
然后就是斜方向的问题了。这个问题我们采取好理解的方式来处理，如图p0nw。我们首先假定那根红色的线是和矩形上方相交，我们使用正方向求解交点的方法，可以先把这个交点给求出来，求出来之后，判断这个nx1，是不是在矩形上边的范围之内，如果在，那么这个点就是对的，如果不在，那么说明直线与左边线相交，我们就需要再求直线与矩形左边线的交点，而这个交点就是真正的np1了。读者可以边看着上图中最左边的那条红线，边看这段文字，非常好理解，以nw为例，代码如下：
switch(p1code)
{
case 0: // C
break;
case 8: // N
{
ny1 = rect.top;
nx1 = x1 + (rect.top - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
} break;
case 9: // NW
{
// 先和求N的一样
ny1 = rect.top;
nx1 = x1 + (rect.top - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
// 然后判断结果
if (nx1 < rect.left || nx1 > rect.right) // 上面的假设错误，需要算与左边线的交点
{
nx1 = rect.left;
ny1 = y1 + (rect.left - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
}
} break;
}
聪明的读者不难发现，其实对p2code的处理和对p1code的是一模一样的。哈哈，因为本来就和是哪个点没关系，只和他们所在的区域可能与相邻的哪些矩形边有关系。
于是我们只剩下最后一个问题了，就是上文提到过的，可能直线的两个点在不同侧，但是与矩形没交点的情况，我们只要把上面的结果做一下边界检查就可以找出这种情况了，代码如下：
if (nx1 < rect.left || nx1 > rect.right ||
ny1 < rect.top || ny1 > rect.bottom ||
nx2 < rect.left || nx2 > rect.right ||
ny2 < rect.top || ny2 > rect.bottom)
{
return 0;
}
至此，大功告成，下面是完整的函数实现。
2. 代码实现
// 返回1则有交点，返回0则无交点，无需画了
int _CPPYIN_3DLib::ClipLineByRect(int x1, int y1, int x2, int y2, RECT rect, int &nx1, int &ny1, int &nx2, int &ny2)
{
// 创建并设置起点p1和终点p2的位置代码p1code和p2code
int p1code = 0;
int p2code = 0;
if (y1 < rect.top)
p1code |= 8;
else if (y1 > rect.bottom)
p1code |= 4;
if (x1 < rect.left)
p1code |= 1;
else if (x1 > rect.right)
p1code |= 2;
if (y2 < rect.top)
p2code |= 8;
else if (y2 > rect.bottom)
p2code |= 4;
if (x2 < rect.left)
p2code |= 1;
else if (x2 > rect.right)
p2code |= 2;
// 过滤同侧情况
if ((p1code & p2code))
return 0;
// 完全保留
if (p1code == 0 && p2code == 0)
{
nx1 = x1;
ny1 = y1;
nx2 = x2;
ny2 = y2;
return 1;
}
// 计算np1的坐标nx1, ny1
switch(p1code)
{
case 0: // C
{
nx1 = x1;
ny1 = y1;
} break;
case 8: // N
{
ny1 = rect.top;
nx1 = x1 + (rect.top - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
} break;
case 4: // S
{
ny1 = rect.bottom;
nx1 = x1 + (rect.bottom - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
} break;
case 1: // W
{
nx1 = rect.left;
ny1 = y1 + (rect.left - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
} break;
case 2: // E
{
nx1 = rect.right;
ny1 = y1 + (rect.right - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
} break;
case 9: // NW
{
// 先和求N的一样
ny1 = rect.top;
nx1 = x1 + (rect.top - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
// 然后判断结果
if (nx1 < rect.left || nx1 > rect.right) // 上面的假设错误，需要算与左边线的交点
{
nx1 = rect.left;
ny1 = y1 + (rect.left - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
}
} break;
case 10: // NE
{
ny1 = rect.top;
nx1 = x1 + (rect.top - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
if (nx1 < rect.left || nx1 > rect.right)
{
nx1 = rect.right;
ny1 = y1 + (rect.right - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
}
} break;
case 6: // SE
{
ny1 = rect.bottom;
nx1 = x1 + (rect.bottom - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
if (nx1 < rect.left || nx1 > rect.right)
{
nx1 = rect.right;
ny1 = y1 + (rect.right - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
}
} break;
case 5: // SW
{
ny1 = rect.bottom;
nx1 = x1 + (rect.bottom - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
if (nx1 < rect.left || nx1 > rect.right)
{
nx1 = rect.left;
ny1 = y1 + (rect.left - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
}
} break;
}
// 计算np2的坐标nx2, ny2
switch(p2code)
{
case 0: // C
{
nx2 = x2;
ny2 = y2;
} break;
case 8: // N
{
ny2 = rect.top;
nx2 = x1 + (rect.top - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
} break;
case 4: // S
{
ny2 = rect.bottom;
nx2 = x1 + (rect.bottom - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
} break;
case 1: // W
{
nx2 = rect.left;
ny2 = y1 + (rect.left - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
} break;
case 2: // E
{
nx2 = rect.right;
ny2 = y1 + (rect.right - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
} break;
case 9: // NW
{
// 先和求N的一样
ny2 = rect.top;
nx2 = x1 + (rect.top - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
// 然后判断结果
if (nx2 < rect.left || nx2 > rect.right) // 上面的假设错误，需要算与左边线的交点
{
nx2 = rect.left;
ny2 = y1 + (rect.left - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
}
} break;
case 10: // NE
{
ny2 = rect.top;
nx2 = x1 + (rect.top - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
if (nx2 < rect.left || nx2 > rect.right)
{
nx2 = rect.right;
ny2 = y1 + (rect.right - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
}
} break;
case 6: // SE
{
ny2 = rect.bottom;
nx2 = x1 + (rect.bottom - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
if (nx2 < rect.left || nx2 > rect.right)
{
nx2 = rect.right;
ny2 = y1 + (rect.right - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
}
} break;
case 5: // SW
{
ny2 = rect.bottom;
nx2 = x1 + (rect.bottom - y1) * (x2 - x1) / (double)(y2 - y1) + 0.5;
if (nx2 < rect.left || nx2 > rect.right)
{
nx2 = rect.left;
ny2 = y1 + (rect.left - x1) * (y2 - y1) / (double)(x2 - x1) + 0.5;
}
} break;
}
// 过滤一种直线与矩形不相交的特殊情况
if (nx1 < rect.left || nx1 > rect.right ||
ny1 < rect.top || ny1 > rect.bottom ||
nx2 < rect.left || nx2 > rect.right ||
ny2 < rect.top || ny2 > rect.bottom)
{
return 0;
}
return 1;
}
3. 项目下载
这次的示例，是随机生成直线，起点和端点的范围是正负两个屏幕的最大坐标之间，裁剪区域是屏幕里的一个矩形。每秒将500个这种直线通过矩形裁剪，如果与矩形有交点，则在矩形内画出相应的线段。截图如下：
项目完整代码下载：>>点击进入下载页<<
4. 补充内容
如果有时间，我会更新上Cyrus-Beck裁剪算法，如果您已实现，请留言分享，谢谢。
转自:http://blog.csdn.net/cppyin/archive/2011/02/04/6172457.aspx