资源描述：
《计算机图形学讲义2(裁减)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、中点分割裁剪算法1、基本思想：从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。（见上图）与Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。A、B分别为距P0、P1最近的可见点，Pm为P0P1中点。2、中点分割算法-求线段与窗口的交点1）、从P0出发找距离P0最近可见点采用中点分割方法先求出P0P1的中点Pm,若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部
2、分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；否则取PmP1代替P0P1。再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点。2）、从P1出发找距离P1最近可见点采用上面类似方法。3、·s对分辩率为2N*2N的显示器，上述二分过程至多进行N次。·主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。·对分辩率为2N*2N的显示器，上述二分过程至多进行N次。····主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大
3、大加快了速度。梁友栋-Barsky算法设要裁剪的线段是P0P1。P0P1和窗口边界交于A,B,C,D四点，见图。算法的基本思想是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。线段的参数表示x=x0+t△xy=y0+t△y0<=t<=1△x=x1-x0△y=y1-y0窗口边界的四条边分为两类：始边和终边。n求出P0P1与两条始边的交点参数t0,t1,令tl=max(t0,t1,0)，则tL即为三者中离p1最近的点的参数n求出p0p1与两条终边的交点参数t
4、2,t3,令tu=min(t2,t3,1)，则tU即为三者中离p0最近的点的参数n若tu>tl,则可见线段区间[tl,tu]t0t1t2t301始边和终边的确定及交点计算：令QL=-△xDL=x0-xLQR=△xDR=xR-x0QB=-△yDB=y0-yBQT=△yDT=yT-y0交点为ti=Di/Qii=L,R,B,TQi<0ti为与始边交点参数Qi>0ti为与终边交点参数Qi=0Di<0时,线段不可见Di>0时,分析另一D,当Qi=0时若Di<0时,线段不可见（如图中AB，有QR=0，DR<0）若Di>0时,分析另一D,（如图中的EF就是这种情况，它使QL
5、=0，DL>0和QR=0，DR>0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。）EFAB参数化算法(Cyrus-Beck)ARNP1·考虑凸多边形区域R和直线段P1P2P(t)=(P2-P1)*t+P1·设A是区域R的边界上一点，N是区域边界在A点的内法线向量·则对于线段P1P2上任一点P(t)·N·(P(t)-A)<0->外侧·N·(P(t)-A)>0->内侧·N·(P(t)-A)=0->边界或其延长线上·凸多边形的性质：点P(t)在凸多边形内的充要条件是，对于
6、凸多边形边界上任意一点A和该点处内法向N，都有N·(P(t)-A)>0·k条边的多边形，可见线段参数区间的解:·Ni·(p(t)-Ai)>=0,i=0,…,k,0≤t≤1.·即：Ni·(P1-Ai)+Ni·(P2-P1)t>=0(1)式·可得：··令ti=Ni·(P1-Ai)/[Ni·(P2-P1)]·Ni·(P2-P1)=0->平行于对应边。·此时判断Ni·(P1-Ai)·若Ni·(P1-Ai)<0->P1P2在多边形外侧->不可见，·若Ni·(P1-Ai)>0->P1P2在多边形内侧->继续其它边的判断·对于t值的选择：首先，要符合0≤t≤1；其次，对于凸
7、窗口来说，每一个线段与其至多有两个交点，即有两个相应的t值。所以我们可以把计算出的t值分成两组：一组为下限组，是分布在线段起点一侧的；一组为上限组，是分布在线段终点一侧的。这样，只要找出下限组中的最大值及上限组中的最小值，就可确定线段了。·分组的依据是：·如果Ni·(P2-P1)＜0，则计算出的值属于上限组·如果Ni·(P2-P1)＞0，则计算出的值属于下限组·因此，线段可见的交点参数：·tl=max{0,max{ti:Ni·(P2-P1)>0}}·tu=min{1,min{ti:Ni·(P2-P1)<0}}·若tl<=tu,[tl，tu]是可见线段的交点参数
8、区间，否则，线段不可见。当凸多边形是矩
