基本图形生成算法.pptVIP

梁友栋-Barsky算法计算机图形学始边和终边的确定及交点计算：令QL=-△xDL=x0-xLQR=△xDR=xR-x0QB=-△yDB=y0-yBQT=△yDT=yT-y0交点为ti=Di/Qii=L,R,B,TQi0ti为与始边交点参数Qi0ti为与终边交点参数Qi=0Di0时,线段不可见Di0时,分析另一D,EFAB梁友栋-Barsky算法计算机图形学当Qi=0时若Di0时,线段不可见（如图中AB，有QR=0，DR0）若Di0时,分析另一D,（如图中的EF就是这种情况，它使QL=0，DL0和QR=0，DR0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。）EFAB参数化算法(Cyrus-Beck)计算机图形学AP2RNP1P(t)=(P2-P1)*t+P1设A是区域R的边界上考虑凸多边形区域R和直线段P1P2A点的内法线向量一点，N是区域边界在参数化算法(Cyrus-Beck)计算机图形学则对于线段P1P2上任一点P(t)N·(P(t)-A)0-外侧N·(P(t)-A)0-内侧N·(P(t)-A)=0-边界或其延长线上AP2RNP1参数化算法(Cyrus-Beck)计算机图形学凸多边形的性质：点P(t)在凸多边形内的充要条件是，对于凸多边形边界上任意一点A和该点处内法向N，都有N·(P(t)-A)0参数化算法(Cyrus-Beck)计算机图形学k条边的多边形，可见线段参数区间的解:Ni·(p(t)-Ai)=0,i=0,…,k,0≤t≤1.即：Ni·(P1-Ai)+Ni·(P2-P1)t=0(1)式可得：令ti=Ni·(P1-Ai)/[Ni·(P2-P1)]参数化算法(Cyrus-Beck)计算机图形学Ni·(P2-P1)=0-平行于对应边。01此时判断Ni·(P1-Ai)02若Ni·(P1-Ai)0-P1P2在多边形外侧-不可见，03若Ni·(P1-Ai)0-P1P2在多边形内侧-继续其它边的判断04参数化算法(Cyrus-Beck)计算机图形学对于t值的选择：首先，要符合0≤t≤1；其次，对于凸窗口来说，每一个线段与其至多有两个交点，即有两个相应的t值。所以我们可以把计算出的t值分成两组：一组为下限组，是分布在线段起点一侧的；一组为上限组，是分布在线段终点一侧的。这样，只要找出下限组中的最大值及上限组中的最小值，就可确定线段了。分组的依据是：如果Ni·(P2-P1)＜0，则计算出的值属于上限组如果Ni·(P2-P1)＞0，则计算出的值属于下限组参数化算法(Cyrus-Beck)计算机图形学因此，线段可见的交点参数：01tl=max{0,max{ti:Ni·(P2-P1)0}}02tu=min{1,min{ti:Ni·(P2-P1)0}}03若tl=tu,[tl，tu]是可见线段的交点参数区间，否则，线段不可见。04设该边的直线方程为：ax+by+c=0；若y＝yi，x=xi；则当y=yi+1时，其中为常数假定当前扫描线与多边形某一条边的交点的x坐标为x，则下一条扫描线与该边的交点不要重计算，只要加一个增量△x。交点问题计算机图形学扫描线与多边形的顶点或边界相交时，必须正确的交点的取舍。只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定。算法过程计算机图形学voidpolyfill(polygon,color)1intcolor;多边形polygon;2{for(各条扫描线i)3{初始化新边表头指针NET[i]；4把ymin=i的边放进边表NET[i];5}6y=最低扫描线号；7初始化活性边表AET为空；8for(各条扫描线i)9{10把新边表NET[i]中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列；遍历AET表，把配对交点区间(左闭右开)