第6章 2维裁剪.ppt

之间的连线AB即为原线段PoP1的可见部分。假设有一质点从P0出发向P1方向运动，则该点从A点进入窗口区域，从B点离开窗口区域。 从P0(P1)出发找最近可见点的办法是采用中点分割方法。先求出P0P1的中点Pm,若PoPm不是显然不可见的,并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；否则 取PmP1代替P0P1，再对新的P0Pl求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数s为止。这时候，Pm即为所求的距P0最近的可见点。图6．9为从P0出发找距P0最近可见点P的框图。求距P1最近的可见点的过程是一样的，只要把P0和P1交换即可。可取为一个像素的宽度。 分辨率为2NX2N的显示器来说，上面的二分过程至多进行N次。由于主要计算过程只用到加法和除2运算，所以特别适合用硬件来实现，同时该算法也适合于并行计算。 6.1.6 梁友栋—Barsky算法 在梁友栋－Barsky算法中，将待裁剪线段P0 P1及矩形窗口均看作点集，那么裁剪结果即为两点集的交集。窗口是一个二维对象而线段是一个一维对象，两个对象的维数不同不便于比较。可按如下方式产生一维窗口：设P0Pl所在直线为L，记L与窗口的两交点为Q0，Q1，称Q0Q1为诱导窗口(见图6．10)，它是一维的。P0P1关于矩形窗口的裁剪结果与P0Pl关于诱导窗口的裁剪结果是一致的。这样就将二维裁剪问题化简成了一维裁剪问题。 现在首先讨论一维裁剪问题。在一维数轴上，P0P1和Q0Ql的关系如图6．11所示，分别记为情况I，Ⅱ，Ⅲ，Ⅳ。我们不妨将P0,P1,Q0,Q1的坐标写成参数形式。 假设P0为数轴的原点，P1对应的参数为1，即在表达式中，P0，Pl对应的参数为0，1，再记Q0，Q1对应的参数为 。 不妨假设 ≤ ：，则P0，P1，Q0，Q1坐标间的关系如下表。 由上面的关系表可以得出一维裁剪问题的解：P0Pl至少部分可见的充分必要条件是 且可见部分的参数区间为[max(0，)，min(1，)]。 一维裁剪问题的解得出之后，为了解决二维裁剪问题，只要生成诱导窗口就可以了。假定P0P1所在的直线L与窗口左、右、上、下四边所在直线的交点分别为L，R，T，B，Q0Ql为诱导窗口(见图6．12)，再记窗口左、右边所在直线夹成的带形区域为△1，上、下边所在直线夹成的带形区域为△2，窗口区域为口，则诱导窗口Q0Q1计算如下： P0P1的可见部分记为VW，则 这就是二维裁剪问题的解。 为实现方便，仍然将各点化到参数域上进行，P0P1的参数方程为： 其中△x=x1-x0, △y=y1-y0。现根据窗口四条边与有向线段P0P1的相交的顺序将它们分成两类，一类称为始边，一类称为终边。对于左、右两条边，当△x≥0时，x＝xmin称为始边，x=xmax称为终边。当△x0时，x=xmax称为始边，x=xmin称为终边。对上、下两条边，当△y≥0时，y＝ymin称为始边，y=ymax称为终边，当△y0时，y=ymax称为始边，y=ymin称为 终边。如图6．13中，对P0P1来说x=xmin，y＝ymin为始边，而对P2P3，来说，x=xmin,y=ymax为始边。 假定P0P1与竖直方向的始边、终边(左、右边)的交点参数为t0’，t1’，p0p1和水平方向的始边、终边(上、下边)的交点参数为t0’’，t1”，则式(6．7)中LR，TB所对应的参数区间分别为[t0’,t1’],[t0’’,t1’’] .根据式(6．7)得出诱导窗口Q0Ql对应的参数区间为： 再由式(6．8)和一维裁剪的结论得出，VW的参数区间为: 其中 于是得出结论：当tl≥t0时，P0P1有可见部分且其对应的参数区间为[t0,t1];否则，P0Pl 完全不可见。如图6．13中的P4P5就属于这种情况 。 为了确定始边和终边，并求出P0P1与它们的交点，令 由相似三角形的比例关系，易知交点的参数ti=Di／Qi, i=L, R，B，T，这里，tL是P0P1与x=xmin的交点参数，其它有相类似的意义。 当Qi0时，对应的ti必是p0p1和始边交点的参数，当Qi0时，对应的ti是p0p1 和终边交点的参数。 而当Qi＝0时，若Di0，则p0p1完全不可见，如图6．14中的AB(QR=0，DR0)；若Di≥0时，如图6．14中的CD(