计算机图形学(裁剪III).ppt

《计算机图形学(裁剪III).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第4章变换和裁剪直线P0P1的参数方程对于直线上一点(x,y),若它在窗口内则有梁友栋-Barsky算法BLP0P1RTxLxRyByTxy22009-2010-2:CG:SCUEC令则有由梁友栋-Barsky算法32009-2010-2:CG:SCUEC梁友栋-Barsky算法由42009-2010-2:CG:SCUEC设P0P1和两条始边的交点参数为t0’，t0”，令t0=max(t0’，t0”，0)，则t0就是P0P1和两条始边的交点与P0三点中最靠近P1的点的参数。设P0P1和两条终边的交点参数为t1’，t

2、1”，令t1=min(t1’，t1”，1)，则t1就是P0P1和两条终边的交点与P1三点中最靠近P0的点的参数。当t1>t0时，参数t[t0,t1]的线段就是P0P1的可见部分当t10时，参数t用于更新t1。如果更新了t0或t1后，使

3、t0>t1，则舍弃该线段。否则画出以t0和t1为参数的线段梁友栋-Barsky算法的基本步骤62009-2010-2:CG:SCUEC梁友栋-Barsky算法doublet0=0,t1=1;doublexL,xR,yB,yT;boolvisible;voidLiang_Barsky(doublex[2],doubley[2]){doubledx,dy;visible=false;dx=x[1]-x[0];dy=y[1]-y[0];if(clipt(-dx,x[0]-xL))if(clipt(dx,xR-x[0]))

4、if(clipt(-dy,y[0]-yB))if(clipt(dy,yT-y[0]))visible=true;if(visible)drawline(P0+(P1-P0)t0,P0+(P1-P0)t1);}Booclipt(doubleq,doubled){doublet;if(q<0)//属于起始边参数{t=q/d;if(t>t1)returnfalse;elseif(t>t0)t0=t;}elseif(q>0)//属于终点边参数{t=q/d;if(t

5、=t;}elseif(d<0)returnfalse;returntrue;}梁-Barsky算法演示例子72009-2010-2:CG:SCUECCyrus-Beck裁剪算法（参数化裁剪算法）考虑如图所示一个凸多边形区域R和一条线段P1P2，要求计算线段落在区域R中的部分。假定A是区域R边界L上一点。N是区域边界在A点的内法向量。线段P1P2用参数方程表示：P(t)=(P2-P1)t+P10t1P1P2ANR图示称直线上某点在某边界的内侧，如果该点和多边形区域内任一点都在该边界的同一侧。Ref:M.Cyrus

6、andJ.Beck,Generalizedtwo-andthree-dimensionclipping,ComputersandGraphics,3(1),23-28,1978.82009-2010-2:CG:SCUEC线段上的点和多边形的关系P(t)=(P2-P1)t+P10t1对于线段上任意一点P(t)，P(t)和多边形边界L的关系有三种可能（此处t为一定值）：1)N(P(t)-A)>0，则P(t)在L内侧。2)N(P(t)-A)=0，则P(t)在L或其延长线上。3)N(P(t)-A)<0，则P(t)

7、在L外侧。凸多边形裁剪区域性质1性质1表明，P(t)在凸多边形内的充要条件是，对于凸多边形边界上任意一点A和该处内法向量N，都有N(P(t)-A)0。92009-2010-2:CG:SCUEC现假设多边形有k条边，在每条边界Li上取1个点Ai，该点处的内法向量Ni（i=1,2,…,k），则可见线段的参数区间为下列不等式组的解i=1,2,…,k解的最小值ts和最大值te分别对应于可见线段的端点。把式P(t)=(P2-P1)t+P1代入上式，整理得当Ni(P2-P1)0，由上式可求得tti，当Ni(P2-

8、P1)>0tti，当Ni(P2-P1)<0i=1,2,…,k而是线段与第i条边界（或延长线）的交点参数。Cyrus-Beck算法102009-2010-2:CG:SCUEC解的几何意义：Ni(P2-P1)把ti分为两组：起点组和终点组。解的几何意义终点组起点组P2P1终点组以Ni(P2-P1)<0为特征，表示在该处沿P1P2方向前进进入多边形外侧。起