计算机图形学(裁剪III)

计算机图形学第4章变换和裁剪直线P0P1的参数方程00xxxtyyyt01t对于直线上一点(x,y),若它在窗口内则有L0RB0Txxxtxyyyty梁友栋-Barsky算法BLP0P1RTxLxRyByTxy22009-2010-2:CG:SCUEC0000LLLRRRBBBTTTQxDxxQxDxxQyDyyQyDyy令则有,,,iitQDiLRBT0R00T0LBxtxxxtxxytyyytyyL0RB0Txxxtxyyyty由梁友栋-Barsky算法32009-2010-2:CG:SCUEC(0)(0),{,}(0)(0),{,}01jiijijjiijijDDQtQijLRijQQDDQtQijBTijQQt梁友栋-Barsky算法由,,,iitQDiLRBT42009-2010-2:CG:SCUEC设P0P1和两条始边的交点参数为t0’，t0”，令t0=max(t0’，t0”，0)，则t0就是P0P1和两条始边的交点与P0三点中最靠近P1的点的参数。设P0P1和两条终边的交点参数为t1’，t1”，令t1=min(t1’，t1”，1)，则t1就是P0P1和两条终边的交点与P1三点中最靠近P0的点的参数。当t1t0时，参数t[t0,t1]的线段就是P0P1的可见部分当t1t0时，整个线段为不可见。为什么？梁友栋-Barsky算法52009-2010-2:CG:SCUEC1.初始化线段在边界内的端点参数为t0=0、t1=1。2.计算出各个裁剪边界的q、d值。3.当q=0且d0时，舍弃该线段；否则计算线段与边界的交点参数t。4.当q0时，参数t用于更新t0；5.当q0时，参数t用于更新t1。6.如果更新了t0或t1后，使t0t1，则舍弃该线段。否则画出以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]))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(q0)//属于起始边参数{t=q/d;if(tt1)returnfalse;elseif(tt0)t0=t;}elseif(q0)//属于终点边参数{t=q/d;if(tt0)returnfalse;elseif(tt1)t1=t;}elseif(d0)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.CyrusandJ.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)在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代入上式，整理得10,0))((tAtPiiN10,0)()(121ttPPNAPiiiN当Ni(P2-P1)0，由上式可求得tti，当Ni(P2-P1)0tti，当Ni(P2-P1)0i=1,2,…,k)()(121PPAPtiiiiNN而是线段与第i条边界（或延长线）的交点参数。Cyrus-Beck算法102009-2010-2:CG:SCUEC解的几何意义：Ni(P2-P1)把ti分为两组：起点组和终点组。解的几何意义终点组起点组P2P1终点组以Ni(P2-P1)0为特征，表示在该处沿P1P2方向前进进入多边形外侧。起点组以Ni(P2-P1)0为特征，表示在该处沿P1P2方向前进进入多边形内侧。tti，当Ni(P2-P1)0tti，当Ni(P2-P1)0i=1,2,…,k设起点组中最大的t为ts，终点组中最小的t为te，则ts=max{0,max{ti|Ni(P2-P1)0|}}te=min{1,min{ti|Ni(P2-P1)0|}}若tste，则ts和te是可见线段的端点参数，否则，整条线段在区域外部。Cyrus-Beck算法112009-2010-2:CG:SCUEC若对于某个i，有Ni(P2-P1)=0，这时，NiP2-P1，P1P2与对应边平行，如图所示。这时有两种情况：线段在区域外侧或内侧。前一种情况对应于Ni(P1-Ai)0线段与裁剪边平行的情况可直接判断线段在多边形之外后一种情况对应于Ni(P1-Ai)0则不予考虑（因为没有交点），继续处理其他边界。线段与多边形边平行122009-2010-2:CG:SCUECCyrus-Beck算法doublets=0,te=1;intCyrus_Beck(doubleA[][2],doubleN[][2],intk,doublex[2],doubley[2]){inti,j;doublet,dn,nw,Rs[2],Re[2];for(i=0;ik;i++){dn=N[i][0]*(x[1]-x[0])+N[i][1]*(y[1]-y[0]);//计算Ni·(P2-P1)nw=N[i][0]*(x[0]-A[i][0])+N[i][1]*(y[0]-A[i][1]);//计算Ni·(P1-Ai)if(fabs(dn)1.0e-6)//与边界平行if(nw0)return0;//且在边界之外，丢弃else//与边界不平行，即与边界有交点{t=-nw/dn;//求出交点参数if(dn0)//属于起点组参数{if(tts)ts=t;}//求最大值elseif(tte)te=t;//属于终点组，求最小值}}if(ts=te)//起点组的最大值小于等于终点组的最小值{Rs[0]=(x[1]-x[0])*ts+x[0];Rs[1]=(y[1]-y[0])*ts+y[0];//计算起点坐标Re[0]=(x[1]-x[0])*te+x[0];Re[1]=(y[1]-y[0])*te+y[0];//计算终点坐标LineFunction(doubleRs[],doubleRe[]);return1;}return0;//起点组的最大值大于终点组的最小值}132009-2010-2:CG:SCUEC当凸多边形是矩形窗口，且矩形的边平行于坐标轴时，上述算法可简化为梁友栋-Barsky算法。由于每条边上法向量只有一个非零分量,所以任意一个向量与法向量求内积的运算很简单。Cyrus-Beck算法特例——Liang-Barsky算法边内法向量N边上一点AP1-A左边x=XL（1，0）（XL，y）（x1-XL，y1-y）右边x=XR（-1，0）（XR，y）（x1-XR，y1-y）下边y=YB（0，1）（x，YB）（x1-x，y1-YB）上边y=YT（0，-1）（x，YT）（x1-x，y1-YT）)()(121PPAPtNN)()(121xxXLx121)(xxXRx)()(121yyYBy121)(yyYTyA1A2A3A4P1P2142009-2010-2:CG:SCUEC多边形是由一组线段围成的封闭区域，线段裁剪是多边形裁剪的基础。下图（b）是多边形的线段被裁剪后的结果，但已不再是封闭的区域。正确的剪裁结果应是一个有边界的区域，即裁剪后的结果仍是一个（或多个）多边形，这就要求在裁剪过程中应当保留多边形的区域性质。（a）裁剪前（c）对多边形区域做裁剪（b）仅对多边形的线段做裁剪多边形裁剪多边形裁剪-凸多边形的二维裁剪152009-2010-2:CG:SCUECSutherland-Hodgman算法Sutherland-Hodgman算法对多边形裁剪的Sutherland–Hodgman算法是一种十分简便的方法，只要对多边形用窗口的四条边依次裁剪四次(见下图）便可得到裁剪后的多边形。算法的输入是以顶点序列表示的多边形，输出也是一个顶点序列，构成一个或多个多边形。考虑以窗口的一条边及其延长线构成的裁剪线，该线把平面分成两部分：一部分包含窗口，称为可见侧；另一部分称为不可见侧。162009-2010-2:CG:SCUEC线段端点S、P与裁剪线的位置关系对多边形的每一条边，假设它的两个端点分别为S和P。则它与裁剪直线的位置关系只有4种情况。S、P与裁剪线的四种位置关系（b）（c）（d）S可见侧可见侧可见侧可见侧SPSPSPP（a）II根据上述4种情况，线段SP经裁剪后可输出0至2个顶点。情况1：S、P都在可见一侧，则输出P。情况2：S、P都在不可见一侧，则不输出顶点。情况3：S在可见一侧，P在不可见一侧，则输出SP与裁剪线的交点点I。情况4：S在不可见一侧，P在可见一侧，则输出SP与裁剪线的交点点I和P。172009-2010-2:CG:SCUECSutherland-Hodgman算法框图Sutherland-Hodgman算法流程图（1）主框图开始第一个顶点→S,F顶点输入完毕输入顶点P处理线段SPP→SF→P处理线段SP结束NY（2）处理线段SP子过程SP与裁剪线相交求SP与裁剪线的交点I输出IP位于可见侧输出PNNYY左算法框图仅描述用一条裁剪边对多边形裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。对于每条裁剪边，算法的框图是一样的，只是判断点在裁剪边哪一侧以及求线段SP与裁剪边的交点算法应做相应的改变。182009-2010-2:CG:SCUEC1．从主函数得到待裁剪多边形的顶点序列P[][2]、顶点序列数n、窗口一条边界参数xl(假如为矩形窗口的左边界)；2．赋初值：将顶点序列中的最后一个顶点赋给前一顶点S；设置初始标志flag：if(S在边界内侧)flag=0;elseflag=1；设新的顶点序列数j=0；考虑多边形相对于一条边界及其延长线进行裁剪的算法：Suthe