LH计算机图形学作业：共九道题
具体计算时要把P0P1写成参数方程
?x?x0??x?t ??y?y0??y?t其中?x?xy?。y把窗口边界的四条边分成两类，一类称1?x0,?y?10为始边，另一类称为终边。
参数化形式写出裁剪条件:
XL?x1?u??x?XRYB?y1?u??y?YT可以统一表示为形式：upk?qk
p1???xp3???yq1?x1?XLq1?y1?YBp2??xp4??yq2?XR?x1q4?YT?y1
当pk?0且qk?0，则线段完全在边界外，qk?0，则该线段平行于裁剪边界并且在窗口内；
当pk?0的情况下：当pk?0,线段从裁剪边界延长线的外部延伸到内部；当pk?0,线段从裁剪边界延长线的内部延伸到外部。
对于每条直线，可以计算出参数u1和u2，它们定义了在裁剪矩形内的线段部分，u1的值由线段从外到内遇到的矩形边界所决定?p?0?。对这些边界计算rk?qk/pk。u1取0和各个rk值之中的最大值。u2的值由线段从内到外遇到的矩形边界所决定?p?0?。对这些边界计算rk?qk/pk。u2取1和各个rk值之中的最小值。如果u1?u2，则线段完全落在裁剪窗口之外，被舍弃。否则裁剪线段由参数u的两个值u1，u2计算出来。 3.3.2 算法程序（或伪程序）描述
具体程序见附录8。 3.3.3 算法流程图
（略） 3.4 快速算法
在实际绘图时，常出现大部分线段是可见的，或大部分线段为显然不可见。因而用最少的操作去判断被裁剪的线段是否属于这两种情况则可以提高裁剪的效率。此外，尽量减少比较和四则运算，也是提高效率的重要措施。这样会使程序长一点，但由于效率高，在软件包中值得采用。用这样的算法确定一根显然不可见线段平均只要做3.6次比较，确
15
LH计算机图形学作业：共九道题
定一根完全可见线段要用8次比较，而用Sutherland-Cohen算法做同样工作则分别要做11次和10次比较。快速算法在最快的情况下要和四条边求交点，这要用10次加减法、5次乘除法和13次比较。采用Sutherland-Cohen算法要做16次加减法、8次乘除法和35次比较。此外后者还要多次调用过程合作集合运算，这些都使它比快速算法效率低。
3.5 其余一些改进的直线裁剪算法
除过前面所讲到的4种基本直线裁剪算法外，还有一些其它的裁剪方法，由于过多，这里仅列举几种如下：
（1）具有最少算术运算量的二维线裁剪算法。见文献：王骏，梁友栋，彭群生，具有最少算术运算量的二维线裁剪，《计算机学报》，1991年第7期。
（2）一个有效的多边形窗口的线裁剪算法。见文献：刘勇奎等，一个有效的多边形窗口的线裁剪，《计算机学报》，1999年第11期。
（3）一种基于几何变换的高效的线裁剪新算法。见文献：汪乱，吴锐迅，蔡士杰。一种基于几何变换的高效的线裁剪新算法。《软件学报》，1998，9(10): 728一733。
（4）任意多边形窗口的线裁剪算法。见文献：孙岩，唐棣:任意多边形窗口的线裁剪，《2000年图形学会议专刊))。 3.6 各种直线裁剪算法的优缺点对比分析
Sutherland-Cohen直线裁剪算法要计算直线段与窗口边界的交点，这不可避免地要进行大量的乘除运算，必会降低程序的执行效率。而中点分割裁剪算法却只需用到加法和除2运算，而除2运算在计算机中可以简单地用右移一位来实现，从而提高算法的效率。所以特别适合硬件实现，同时也适合于并行计算。 3.7 直线裁剪算法的发展趋势
（略）
4 图形求交技术
4.1 求交点算法
求交点可以分两种情况：求线与线的交点以及求线与面的交点。
16
LH计算机图形学作业：共九道题
4.1.1 线与线的交点的求法
1、直线段与直线段的交点
假设二条直线的端点分别为P1则，P，2Q，1，Q2它们可以用向量形式表示为：
P?t?=A+Bt Q?s?=C+Ds (0?t?1)(0?s?1)
其中，A?P1，B?P2?P1，C?Q1，D?Q2?Q1。 构造方程
A+Bt=C+Ds (4.1.1)
对三维空间中的直线段来说，上述方程实际上是一个二元一次方程组，由三个方程式组成。可以从其中两个解出s,t，再用第三个验证解的有效性：若第三个方程成立则说明找到了解，否则说明两条直线不相交。当所得的解（ti, si）是有效解时，可用二个线段方程之一计算交点坐标，例如P?ti?=A+Bti。
我们还可以根据向量的基本性质，直接计算s与t：对（4.1.1）两边构造点积得
?A+Bt）=（C X D）（?C+Ds）?C X D?（由于CXD同时垂直于C和D，等式右边为零。故有
t??(C?D)?A
(C?D)?B类似地有
s??(A?B)?C
(A?B)?D完整的算法还应判断无解与无穷多解（共线）的情形，以及考虑数值计算误差造成的影响。
2、直线段与二次曲线的交点
不失一般性，考虑平面上一条直线与同平面的一条二次曲线的交。 假设曲线方程为 f?x?,y， =0直线段方程为 则在交点处有
?x, y?=?x1+tdx, y1+tdy?,
f?x1+tdx, y1+tdy?=0。
at2?bt?c?0
当曲线为二次曲线时，上述方程可写为
17
LH计算机图形学作业：共九道题
用二次方程求根公式即可解出t值。 3、圆锥曲线与圆锥曲线的交点
圆锥曲线有代数法表示、几何法表示与参数法表示。在进行一对圆锥曲线的求交时，把其中一条圆锥曲线用代数/几何法表示为隐函数形式，另一条表示为参数形式（如二次NURBS曲线）。将参数形式代入隐函数形式可得关于参数的四次方程，可以使用四次方程的求根公式解出交点参数。得到交点后可再验证交点是否在有效的圆锥曲线段上。 4.2.2 线与面的交点的求法
1、直线段与平面的交点（如图4.1）
图4.1 线段与平面求交
考虑直线段与无界平面的求交问题。把平面上的点表示为
P?u,w?=A+uB+wC，直线段上的点表示为Q?t?=D+tE，二者的交点记为
R。假设线段不平行于平面，则它们交于R=P?u,w?=Q?t?，即
A+uB+wC=D+tE
C等式两边点乘（B X ），得
（B X C）（?A+uB+wC）（=B X C）（?D+tE）
C垂直于B，又垂直于C，故有 由于B X 既
（B X C）?A=（B X C）（?D+tE）
可解出
t?
(B?C)?A?(B?C)?D
(B?C)?E类似求得
18
LH计算机图形学作业：共九道题
u?(C?E)?D?(C?E)?A
(C?E)?B(B?E)?D?(B?E)?A
(B?E)?C??如果是直线与平面区域求交点，则要进一步判断点是否在平面上的有效区域中，其算法可参见4.2节。
2、圆锥曲线与平面的交点
圆锥曲线与平面求交时，可以把圆锥曲线表示为参数形式，并把圆锥曲线的参数形式代入平面方程，即可得到参数的二次方程进行求解。
3、圆锥曲线与二次曲面的交点
圆锥曲线与二次曲面求交时，可把圆锥曲线的参数形式代入二次曲
面的隐式方程，得到参数的四次方程，用求根公式求解。 4.2 求交线算法
求交线显然是指求面与面的交线，下面讨论几种常见的情况。 1、平面与平面的交线
在CAD中一般使用平面上有界区域。先考虑最简单的情形。两个平面区域分别由P?u,w定如果它们不共面而且不分 Q?s,t, u?, ?w, ?s, 义t 。0, 1?,?离，则必交于一直线段。这条直线必落在P?u,w?-Q?s,t?=0所定义的无限直线上。注意这是个含有四个未知数，三个方程式的方程组，只要分别与八条边界线方程：u=0, u=1, w=0, w=1, s=0, s=1, t=0, t=1联立，即可求出线段的两个端点的参数。在上述方程组中，只要找到两组解，就可以不再对剩余其它方程组求解。找到的两组解就是所求的交线段端点参数。
当两个一般的多边形（即既可能是凸的，也可能是凹的，甚至可能带有内孔）相交时，可能有多段交线。我们可以把两个多边形分别记为A和B，用如下的算法求出它们的交线：
（1）把A的所有边与B求交，求出所有有效交点； （2）把B的所有边与A求交，求出所有有效交点； （3）把所有交点先按y，再按x的大小进行排序；
（4）把每对交点的中点与A和B进行包含性检测，若该中点即在A中又在B中，则该对交点定义了一条交线段。
2、平面与二次曲面的交线
求平面与二次曲面的交线有两种方法：代数法和几何法。
19