gjlchp二维填充图元的生成PPT教案.pptx

gjlchp二维填充图元的生成
3
扫描转换多边形
多边形分为凸多边形、凹多边形、含内环的多边形。
第2页/共62页
4
扫描转换多边形
多边形的表示方法
顶点表示
点阵表示
顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。
点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。
第3页/共62页
5
多边形的扫描转换
多边形的扫描转换：把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。
几种方法：逐点判断法；扫描线算法；边缘填充法；栅栏填充法；边界标志法。
第4页/共62页
6
void FillPolygonPbyP(Polygon *P,int polygonColor)
{ int x,y;

for(y = ymin;y <= ymax;y++)
for(x = xmin;x <= xmax;x++)
if(IsInside(P,x,y))
PutPixel(x,y,polygonColor);
else
PutPixel(x,y,backgroundColor);
}/*end of FillPolygonPbyP() */
#define MAX 100
Typedef struct { int PolygonNum; // 多边形顶点个数
Point vertexces[MAX] //多边形顶点数组
} Polygon // 多边形结构
逐点判断法
第5页/共62页
7
逐点判断法
逐个判断绘图窗口内的像素：
如何判断点在多边形的内外关系？
1）射线法：
2）累计角度法
3）编码法；
第6页/共62页
8
逐点判断法
1）射线法
步骤：
从待判别点v发出射线
求交点个数k
K的奇偶性决定了点与多边形的内外关系
第7页/共62页
9
逐点判断法
2）累计角度法
步骤
从v点向多边形P顶点发出射线，形成有向角
计算有相交的和，得出结论
第8页/共62页
10
逐点判断法
逐点判断的算法虽然程序简单，但不可取。原因是速度太慢，主要是由于该算法割断了各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。
第9页/共62页