射线法扫描线算法.ppt

第4章二维填充图元的生成1本章目标掌握如何绘制填充图元(矩形、多边形等)扫面转换算法(扫描线算法)(Filling)图元矩形(Rectangle)多边形(Polygon)扇形(EllipseArc)步骤确定那些像素位于填充图元的内部用指定颜色绘制这些像素两类方法扫描转换(ScanConverting):参数->点阵填充(Filling):点阵->(xmin,ymin)右上角坐标(xmax,ymax)voidFillRectangle(Rectangle*rect,intcolor){intx,y;for(y=rect->ymin;y<=rect->ymax;y++)for(x=rect->xmin;x<=rect->xmax;x++)SetPixel(x,y,color);}/*endofFillRectangle()*/(xmin,ymin)(xmax,ymax),那么为什么要单独处理矩形?与一般多边形相比可简化计算应用非常多,如窗口系统共享边界如何处理? 原则:左闭右开,下闭上开属于谁?…Pn点阵表示扫描转换多边形:将多边形顶点表示形式转换成点阵表示形式三种方法:逐点判断法;扫描线算法;边缘填充法多边形分类(只考虑:简单多边形,即多边形边不自相交)凸多边形(convex):内角小于180度凹多边形(concave)::多边形边的延长线是否划分顶点在两侧方法2:向量的叉积每条边建立一个向量,测试相邻边的叉积z坐标的正负(1)如果叉积同号,那么是凸多边形(2)如果叉积不同号,那么是凹多边形(E1×E2)z>0(E2×E3)z>0(E3×E4)z<0(E4×E5)z>0(E5×E6)z>0(E6×E1)z>(CrossProductofTwoVector)当a与b为二维向量时,a×b矢量中x,,若是,则用指定颜色绘制该像素问题如何判断点在多边形的内外关系?射线法累计角度法*编码法*P1P2(xmin,ymin)(xmax,ymax)10