中点分割算法-求线段与窗口的交点 从Po出发找距离P最近可见点采用中点分割方法 先求出PoP1的中点Pm, n若PoPm不是显然不可见的,并且PoP1在窗口中有可见 部分,则距Po最近的可见点一定落在PoPm上,所以用 PoPm代替PoP1; 否则取PmP代替PoP1。 ■再对新的PoP求中点Pm。重复上述过程,直到PnP长 度小于给定的控制常数为止,此时Pm收敛于交点。 从P1出发找距离P1最近可见点采用上面类似方法。 Pm B 2021/1/21 P1 形学
2021/1/21 浙江大学计算机图形学 16 中点分割算法-求线段与窗口的交点 ◼ 从P0出发找距离P0最近可见点采用中点分割方法 ◼ 先求出P0P1的中点Pm, ◼ 若P0Pm不是显然不可见的，并且P0P1在窗口中有可见 部分，则距P0最近的可见点一定落在P0Pm上，所以用 P0Pm代替P0P1； ◼ 否则取PmP1代替P0P1。 ◼ 再对新的P0P1求中点Pm。重复上述过程，直到PmP1长 度小于给定的控制常数为止，此时Pm收敛于交点。 ◼ 从P1出发找距离P1最近可见点采用上面类似方法。 P0 P1 Pm A B
中点分割裁剪算法 5可见Y P=p exit B B1显然不可见八Y不可见 exit F烈=(+F)2 Y d(2烈,)<E exit Y B2显然不可见> B1= 2021/1/21 浙江大学计算机图形学 17
2021/1/21 浙江大学计算机图形学 17 中点分割裁剪算法
中点分割裁剪算法 ■对分辩率为2N*2N的显示器,上述二分过 程至多进行N次。 ■主要过程只用到加法和除法运算,适合 硬件实现,它可以用左右移位来代替乘 除法,这样就大大加快了速度。 2021/1/21 浙江大学计算机图形学 18
2021/1/21 浙江大学计算机图形学 18 ◼ 对分辩率为2 N*2N的显示器，上述二分过 程至多进行N次。 ◼ 主要过程只用到加法和除法运算，适合 硬件实现，它可以用左右移位来代替乘 除法，这样就大大加快了速度。 中点分割裁剪算法
梁友栋- Barsky算法 设要裁剪的线段是PoP1。PP1和 窗口边界交于A,B,C,D四点,见图 算法的基本思想是从A,B和P0三点 中找出最靠近P1的点,图中要找的 B 点是Po从C,D和P1中找出最靠近P 的点。图中要找的点是C点。那么 xPQC就是PP线段上的可见部分。 2021/1/21 浙江大学计算机图形学 19
2021/1/21 浙江大学计算机图形学 19 梁友栋-Barsky算法 ◼ 设要裁剪的线段是P0P1。 P0P1和 窗口边界交于A,B,C,D四点，见图。 算法的基本思想是从A,B和P0三点 中找出最靠近P1的点，图中要找的 点是P0。从C,D和P1中找出最靠近P0 的点。图中要找的点是C点。那么 P0C就是P0P1线段上的可见部分
v梁友栋= -Barsky算法 线段的参数表示 X=×0+tX y=yo+tAy 0<=t<=1 △X=X1X0y=y1yc 窗口边界的四条边分为两类:始边和终边。 若Ax≥0→x=x为始边,x=x为终边。 若Ax<0→x=x1为终边,x=x为始边 若Ay≥0→y=y为始边,y=y为终边。 1若Ay<0→y=y为终边,y=y为始边。 2021/1/21 浙江大学计算机图形学 20
2021/1/21 浙江大学计算机图形学 20 梁友栋-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