计算机图形学图形填充初步.ppt

填充图元生成原理 多边形扫描转换 区域填充 图形分类 线段图形 直线、圆以及自由曲线等，用于表现物体的几何轮廓 实面积图形 封闭图形，在其封闭的区域内具有相同的颜色。既表现了物体的几何轮廓，也反映了物体表面的色彩。 在计算机屏幕上表现为：处于封闭图形内部区域的屏幕象素具有相同的亮度和色彩。 实面积图形的表示 顶点表示法 以封闭多边形的顶点坐标数据（或者 ，闭合曲线的特征数据）来描述实面积图形；其内部以用户指定的颜色填充；基本填充方法：多边形填充。 点阵表示法 以点阵数组的方式描述实面积图形；图形的内部以用户指定的颜色包围或者组成，易于面着色；基本填充方法：种子填充。 多边形分为凸多边形、凹多边形、含内环的多边形。 注意：凹、凸点的判断 实区域填充算法 确定待填充的象素，即检查光栅的每一像素是否位于多边形区域内 多边形的填充原理 多边形填充的任务:把多边形的顶点表示转换为点阵表示。即，找出所有位于多边形内部的像素点，以所要求的像素值画这些像素点。 可能的做法： 遍历屏幕上的像素点，判断是否在多边形内部，然后填充。 问题：逐点判断，速度太慢；不是所有对多边形都容易作内部判断。 关键：寻找一种快速而通用的内部判断方法。 扫描线:点阵图形在屏幕上的像素点，可以认为是由位于一条条水平直线上的像素点构成的. 对每一条切割多边形的扫描线，决定扫描线上哪些像素点是在多边形内部，并对这些相应的像素点赋以合适的值表示某种颜色或灰度，就能对整个多边形进行扫描转换。 一条扫描线与一个多边形的关系: 相交或不相交.若相交,则直线被多边形分割成不同的直线段,其中一些在多边形内,另外一些在多边形外.并且这些多边形内外的直线段大多数情况下相互交替出现. 扫描线连贯性(scan line coherence)：当像素点位于多边形内(外)的直线段上时,它就位于多边形内(外). 也就是说，与多边形相交的一条扫描线上总会有一组相互相连的像素点都位于多边形之内。 每一个像素点—?像素点所在的直线段 分析 从扫描线的一端出发, 当前在多边形外, 当沿扫描线前进到达与多边形的第一个交点时, 就进入多边形内；由于扫描线的另一端是在多边形外, 继续沿扫描线前进一定会走出多边形内部,于是一定会遇到第二个交点。这时可以看到,第一和第二个交点之间的直线段就位于多边形内； 如果没有更多的交点,则该扫描线上只有一段直线段位于多边形内。否则,继续沿扫描线前进, 此时位于多边形外,直到遇到第三个交点后,重新进入多边形内。类似前面的分析,一定有第四个交点。于是第三,第四个交点给出的直线段就位于多边形内； 如果还有更多的交点,就重复这样的过程,直到没有新的交点为止。因为交点个数是有限的, 这一过程是一定可以结束的。 射线交点计数的方法： 从多边形外一点，引水平射线（即扫描线）穿过多边形，记录扫描线与多边形边的交点个数情况，当交点数为奇数时，扫描线处在多边形内部，当交点数为偶数时，扫描线处在多边形外部。多边形与同一扫描线的交点按x方向大小顺序排列，并两两配对，则可得扫描线在多边形内的直线段，从而可实现多边形填充。 奇点问题 奇点：当扫描线与多边形的交点是顶点。 如果奇点存在,上述判别过程就不能正确地进行 多边形顶点的潜在问题 这个问题与交点的求解方法有关. 所有交点通过扫描线所在直线依次与多边形各边所在直线段求解出。如果某个交点恰恰是其中一个边的端点：重复计算。 水平边问题 水平边重合于某一条扫描线：无数多交点，不予处理 可能情况图示： 奇点的处理 多边形的顶点可分为两类：极值奇点和非极值奇点。如果(yi-1 - yi)(yi+1 - yi)≥0，则称顶点Pi为极值点；否则称Pi为非极值点。 规定：奇点是极值点时，该点按两个交点计算，否则按一个交点计算。 奇点的计数问题 总结：简单地数交点不能解决所有的问题，需要补充规则完善此射线交点计数法： （1）忽略多边形的水平边； （2）与多边形的极值点端点相交时，该点算做两个； （3）其余的非极值点端点，仅计算一次。 实际操作任务： （1）判断水平边； （2）判断奇点； 在求交点过程中，因为是依次计算扫描线与各条边的交点，因此奇点也自然被计算两次。但造成另一个问题是非极值点的顶点也被计算了两次。 对此问题的一种处理办法是，计算前，先将每条斜边的低端点在y方向上缩小一个屏幕坐标单位，这将忽略极小值 此法的缺点是，填充的图形可能会出现残缺 这样处理后，极值点仍计算两次，而非极值点的斜边交点只计算一次。 经上述约定及处理后，可保证同一扫描线与多边形的交点成对出 现，因此只要算出交