计算机图形学讲义(裁减).doc

中点分割裁剪算法 1、基本思想： 从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。（见上图） 与Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。A、B分别为距P0 、 P1最近的可见点，Pm为P0P1中点。 2、中点分割算法-求线段与窗口的交点 1）、从P0出发找距离P0最近可见点采用中点分割方法 先求出P0P1的中点Pm, 若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1； 否则取PmP1代替P0P1。 再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点。 2）、从P1出发找距离P1最近可见点采用上面类似方法。 3、 s对分辩率为2N*2N的显示器，上述二分过程至多进行N次。 主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。 对分辩率为2N*2N的显示器，上述二分过程至多进行N次。 主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。 梁友栋-Barsky算法 设要裁剪的线段是P0P1。 P0P1和窗口边界交于A,B,C,D四点，见图。算法的基本思想是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。 线段的参数表示 x=x0+t△x y=y0+t△y 0=t=1 △x=x1-x0 △y=y1-y0 窗口边界的四条边分为两类：始边和终边。 求出P0P1与两条始边的交点参数t0, t1 , 令tl=max(t0 ,t1,0)，则tL即为三者中离p1最近的 点的参数 求出p0p1与两条终边的交点参数t2, t3, 令tu=min(t2,t3,1) ，则tU即为三者中离p0最近的 点的参数 若tu tl,则可见线段区间 [tl , tu] 始边和终边的确定及交点计算： 令 QL= - △x DL= x0-xL QR= △x DR= xR-x0 QB= - △y DB= y0-yB QT= △y DT= yT-y0 交点为 ti= Di / Qi i=L,R,B,T Qi 0 ti为与始边交点参数 Qi 0 ti为与终边交点参数 Qi =0 Di 0 时,线段不可见 Di 0 时, 分析另一D, 当Qi =0时 若Di 0 时,线段不可见 （如图中AB，有QR=0，DR0） 若Di 0 时, 分析另一D, （如图中的EF就是这种情况，它使QL=0，DL0和QR=0，DR0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。） 参数化算法(Cyrus-Beck) 考虑凸多边形区域R和直线段P1P2 P(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)在凸多边形内的充要条件是，对于凸多边形边界上任意一点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-P1 P2在多边形外侧-不可见， 若Ni· (P1-Ai) 0-P1 P2在多边形内侧-继续其它边的判断 对于t值的选择：首先，要符合0≤t≤1；其次，对于凸窗口来说，每一个线段与其至多有两个交点，即有两个相应的t值