割算法思路:通过对线段的分割,找出可见线段,在运算过程中仅使用加法和移位运算算法:(1)对线段端点编码以判别可见性(2)在线段P1P2上分别求出离P1最远的可见点和离P2最远的可见点,此两点?间即为可见线段算法的实现:软件实现:两遍对数查找硬件实现:可并行处理通过对对分得到子线段端点的判别,抛弃不可见线段当对分段很短时,(达到允许精度),处理结束P1P2P2P1三、Cyrus-Beck算法特点:可对任意凸多边形窗口实现二维和三维裁剪考虑一个凸多边形R和一个线段P1P2,P1P2与R最多只有两个交点设A是R边界上一点,N是该区域边界在A点的内法向量将P1P2用参数方程表示:P(t)=(P2-P1)t+P1则线段上任一点P(t),与N的点积有三种可能(1)P(t)在多边形外侧:N。(P(t)-A)<0(2)P(t)在多边形的边及其延长线上:N。(P(t)-A)=0(3)P(t)在多边形内侧:N。(P(t)-A)>0因此,P(t)在凸多边形内的充要条件是:对凸多边形边界上任意一点A和该处内法向量N,都有:N•(P(t)-A)>0P(t)NAP1P2R上述问题是一个线性规划问题,可求得满足条件的一系列t值,在实际操作中我们只关心其最大和最小值,它们对应可见线段区间的端点设多边形有M条边,可以在每条边上取一个点Ai和该点的法向量Ni,则可见线段的参数区间为下列不等式的解(i=1,2,……M)为具体求解t,将线段方程代入上述判别式得:化简得:讨论:(1)当Ni•(P2-P1)=0时,Ni垂直于(P2-P1),第i条边与P1P2平行,无交点(2)当Ni•(P2-P1)>0时,P1在该边外侧,可求出交点ti,并将其归入下限组(3)当Ni•(P2-P1)<0时,P2在该边外侧,可求出交点ti,并将其归入上限组(P2-P1)NNi(P2-P1)>0情况(P2-P1)NNi(P2-P1)<0情况
全文预览
