《计算机图形学》基本图形生成算法.pptVIP

（三）梁友栋-Brian裁剪算法 梁友栋是浙江大学CAD国家重点实验室教授，他提出的裁剪算法在国内外也得到广泛的承认。梁友栋-Brian裁剪算法的基本思想是将二维裁剪归结为一维裁剪，把多边形的裁剪变成解一元不等式组的问题。 设一维直线上有“窗口”Q1Q2，坐标q1≤q2，考察该直线上线段AB，其坐标a≤b，则窗口内可见部分VW=AB∩Q1Q2。AB与Q1Q2的关系如表5.3.1所示。 由上表可归结为下述结论：AB在Q1Q2上可视线段存在的充要条件为： max(min(a,b),min(q1,q2)) ≤ min(max(a,b),max(q1,q2)) （公式5-1） 可视部分为： max(min(a,b),min(q1,q2)) ≤x≤ min(max(a,b),max(q1,q2)) （公式5-2） 例如，图5.4.4为一窗口和线段AB，若AB不平行于窗口边，则AB所在直线及其延长线与窗口四边有交点L，R，T，U。窗口部分Q1Q2=LR∩TU，线段AB在窗口的部分为： VW=AB∩Q1Q2=AB∩LR∩TU。（xl,yb）（xr,yt）ABQ1Q2ULTR图5.4.4 梁友栋-Brian裁剪算法示例 设窗口左下端点为（xl,yb），右上端点坐标为（xr,yt）,该算法分以下几种情况： （1）若AB平行于上下窗口边，即Ay=By,且在窗口其间，则可视部分VW=AB∩LR; (3) 当Ax≠Bx，且Ay≠By,VW存在的充要条件为： max(xl,min(Ax,Bx),min(Tx,Ux))≤min(xr,max(Ax,Bx),max(Tx,Ux)) （公式5-3） 可视线段VW的x区间为： max(xl,min(Ax,Bx),min(Tx,Ux))≤x≤min(xr,max(Ax,Bx),max(Tx,Ux)) 同理，可视线段VW的y区间为： max(yb,min(Ay,By),min(Ly,Ry))≤y≤min(yt,max(Ay,By),max(Ly,Ry)) (4)当Ax=Bx时，VW存在的充要条件为： max(yb,min(Ay,By)) ≤min(yt,max(Ay,By)) 当Ay=By时，VW存在的充要条件为： max(xl,min(Ax,Bx)) ≤min(xr,max(Ax,Bx)) 可视部分： V=( max(xl,min(Ax,Bx)), max(yb,min(Ay,By))) W=( min(xr,max(Ax,Bx)), min(yt,max(Ay,By))) 根据以上描述，算法描述: double xl,xr,yt,yb; Void L_Barsky(double x0,y0,x2,y2) { double t0,t1,deltax,delaty; t0=0.0;t1=1.0; deltax=x2-x0; if(!cansee(-deltax,x0-xl,t0,t1)) return; if(!cansee(-deltax,xr-x0,t0,t1)) return; deltay=y2-y0; if(!cansee(-deltay,y0-yb,t0,t1)) return; if(!cansee(-deltay,yt-y0,t0,t1)) return; x2=x0+t1*deltax; y2=x0+t1*deltay; x0=x0+t0*deltax; y0=x0+t0*deltay; showline(x0,y0,x2,y2);} Bool cansee(double q,d,t0,t1) { double r; if(q0) { r=d/q; if (rt1) {cansee=false;return;} else if (rt0) t0=r; } else if(q0) { r=d/q; if(rt0){cansee=false;return;} else if (rt1) t1=r; } else if (d0){cansee=false;return;} cansee=true; } max(xl,min(Ax,Bx)) ≤min(xr,max(Ax,Bx)) 可视部分： V=( max(xl,min(Ax,Bx)), max(yb,min(Ay,By))) W=( min(xr,max(Ax,Bx)), min(yt,max(Ay,By))) 根据以上描述，算法