图形学chap2-4.pptVIP

2.5 裁剪 裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。 2.5.1 直线段裁剪 2.5.2 多边形裁剪 2.5.1 直线段裁剪 直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。 2.5.1.1 Cohen-Sutherland算法 2.5.1.2 中点分割算法 2.5.1.3 梁友栋－Barskey算法 2.5.1.1 Cohen-Sutherland裁剪 基本思想：对于每条线段P1P2分为三种情况处理: （1）若P1P2在窗口内，则显示该线段P1P2，简称“取”之。 （2）若P1P2在窗口外，则丢弃该线段P1P2 ，简称“弃”之。 （3）若线段不满足“取”或 “弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，弃之。然后对另一段重复上述处理。 为快速判断，采用如下编码方法： 每个区域赋予4位编码CtCbCrCl 这一编码的特点是：窗口某一条边的外侧的三个区域的编码有一位全为1。对于要被裁剪的线段，确定其两个端点的编码code1和code2： 若P1P2完全在窗口内code1 = 0，且code2 = 0，则“取” 若P1P2完全在窗口外code1 code2 ≠ 0，则“弃” 在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 2.5.1.2 中点分割裁剪算法 基本思想：与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况: 全在、完全不在和线段和窗口有交。对前两种情况，进行一样的处理。 对于第三种情况，用中点分割的方法求出线段与窗口的交点。即从P0点出发找出距P0最近的可见点A和从P1点出发找出距P1最近的可见点B，两个可见点之间的连线即为线段P0P1的可见部分。 求线段与窗口的交点 从P0出发找最近可见点采用中点分割方法 先求出P0P1的中点Pm 若P0Pm不是完全不可见的，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1 否则取PmP1代替P0P1 再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点 从P1出发找最近可见点采用与上面类似方法。 2.5.1.3 梁友栋－Barskey算法 梁友栋和Barskey提出了更快的参数化裁剪算法。过线段P1P2的直线的参数方程为： 参数化形式写出裁剪条件： 当pk = 0且qk 0，则线段完全在边界外，qk ≥ 0，则该线段平行于裁剪边界并且在内部 当pk0, 线段从裁剪边界延长线的外部延伸到内部。 当pk 0, 线段从裁剪边界延长线的内部延伸到外部。 For each k, calculate rk=qk/pk u1=max(0, rk) for all k where pk0 [outside to inside] u2=min(1, rk) for all k where pk 0 [inside to outside] If (pk=0) and (qk=0) reject line If u1 u2 then discard line, else use u1 and u2 to calculate end points of the line △x = 13-3 = 10 △y = 8-1 = 7 Left (k =1) p1=-△x =-10 q1=x1-XL =3-4=-1 r1=-1/-10=1/10 u1=max(0,1/10)=1/10 Right (k =2) p2=△x=10 q2=XR-x1=11-3=8 r2=8/10 u2=min(1,8/10)=8/10=0.8 Bottom(k =3) p3= -△y=-7 q3=y1- YB=1-2=-1 r3=-1/-7=1/7 u1=max(1/10,1/7) = 1/7 Top(k =4) p4= △y=7 q4=XT-y1=7-1=6 r4=6/7=0.85 u2=min(0.8,0.85) = 0.8 u1=1/7 u2 = 0.8 = 3+(1/7)*10=3+1.42=4.42 = 1+(1/7)* 7 = 2 = 3+(8/10)*10=3+8=11 = 1+(8/10)* 7 = 1+5.6=6.6 void LB_LineClip(float x1, float y1