中点分割算法-求线段与窗口的交点 从Po出发找距离Po最近可见点采用中点分割方法 先求出PoP的中点Pm, 若PPm不是显然不可见的,并且PoP1在窗口中有可见 部分,则距Po最近的可见点一定落在PoPm上,所以用 PoPm代替PoP1; 否则取PnP1代替PoP1 再对新的PP1求中点Pm。重复上述过程,直到PmP1长 度小于给定的控制常数为止,此时Pm收敛于交点 从P1出发找距离P1最近可见点采用上面类似方法。 PO Pm B 十算机图形学 PI
浙江大学信息学院 计算机图形学 中点分割算法-求线段与窗口的交点 • 从P0出发找距离P0最近可见点采用中点分割方法 –先求出P0P1的中点Pm, –若P0Pm不是显然不可见的，并且P0P1在窗口中有可见 部分，则距P0最近的可见点一定落在P0Pm上，所以用 P0Pm代替P0P1； –否则取PmP1代替P0P1。 –再对新的P0P1求中点Pm。重复上述过程，直到PmP1长 度小于给定的控制常数为止，此时Pm收敛于交点。 • 从P1出发找距离P1最近可见点采用上面类似方法。 P0 P1 Pm A B
中点分割裁剪算法 可见?F P=P exit B 弓显然不可见 Y,不可见 exit 园=(6+)/2 d(2,B)<E? ￥[P=P P=Pm It 2显然不可见 F1=2烈 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 中点分割裁剪算法
中点分割裁剪算法 对分辩率为2N*2N的显示器,上述二分过 程至多进行N次 主要过程只用到加法和除法运算,适合 硬件实现,它可以用左右移位来代替乘 除法,这样就大大加快了速度 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 • 对分辩率为2 N*2N的显示器，上述二分过 程至多进行N次。 • 主要过程只用到加法和除法运算，适合 硬件实现，它可以用左右移位来代替乘 除法，这样就大大加快了速度。 中点分割裁剪算法
梁友栋- Barsky算法 设要裁剪的线段是PP1。PoP1和 窗口边界交于A,B,C,D四点,见图。 C 算法的基本思想是从A,B和Po三点中 找出最靠近的P1点,图中要找的点 B 是Po。从C,D和P1中找出最靠近P0的 a X1 点。图中要找的点是C点。那么PC x就是PP1线段上的可见部分 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 设要裁剪的线段是P0P1。 P0P1和 窗口边界交于A,B,C,D四点，见图。 算法的基本思想是从A,B和P0三点中 找出最靠近的P1点，图中要找的点 是P0。从C,D和P1中找出最靠近P0的 点。图中要找的点是C点。那么P0C 就是P0P1线段上的可见部分。 梁友栋-Barsky算法
Y梁友栋 Barsky 算法 线段的参数表示 X=X+t△X y=yo+t△y 0<=t<=1 △X-x1-×0△y-y 窗口边界的四条边分为两类:始边和终边。 若Ax≥0→x=x1为始边,x=x为终边。 若△x<0→x=x为终边,x=x为始边 若y≥0→y=y为始边,y=y7为终边 若△y<0→y=y2为终边,y=y为始边
浙江大学信息学院 计算机图形学 梁友栋-Barsky算法 线段的参数表示 x=x0+t△x y=y0+t△y 0<=t<=1 △x=x1 -x0 △y=y1 -y0 窗口边界的四条边分为两类：始边和终边。 = = = = = = = = 若 为终边， 为始边。 若 为始边， 为终边。 若 为终边， 为始边。 若 为始边， 为终边。 B T B T L R L R y y y y y y y y y y x x x x x x x x x x 0 0 0 0