多边形的扫描转换PPT学习教案.pptx

会计学
1
多边形的扫描转换
多边形分为凸多边形、凹多边形、含内环的多边形。

第1页/共57页

多边形的表示方法
顶点表示
点阵表示
顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。
点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。
第2页/共57页

多边形的扫描转换：把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。
两种方法：扫描线算法；边界标志法。
第3页/共57页
扫描线算法
扫描线算法
目标：利用相邻像素之间的连贯性，提高算法效率
处理对象：非自交多边形 （边与边之间除了顶点外无其它交点）
第4页/共57页
扫描线算法
交点的取整规则
要求：使生成的像素全部位于多边形之内
用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用
假定非水平边与扫描线y=e
相交，交点的横坐标为x,
规则如下
第5页/共57页
扫描线算法
●规则1：
X为小数，即交点落于扫描线上两个相邻像素之间
(a)交点位于左边之上，向右取整
(b)交点位于右边之上，向左取整
第6页/共57页
●规则2：
边界上象素的取舍问题，避免填充扩大化。
●解决方法：
边界象素：规定落在右上边界的象素不予填充。
具体实现时，只要对扫描线与多边形的相交区间左闭右开
扫描线算法
第7页/共57页
●规则3：
扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。
●解决方法：
检查两相邻边在扫描线的哪一侧。
只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。
扫描线算法
第8页/共57页
扫描线算法是多边形扫描转换的常用算法。与逐点判断算法相比，扫描线算法充分利用了相邻象素之间的连贯性，避免了对象素的逐点判断和反复求交的运算，达到了减少了计算量和提高速度的目的。
开发和利用相邻象素之间的连贯性是光栅图形算法研究的重要内容。扫描转换算法综合利用了区域的连贯性、扫描线连贯性和边的连贯性等三种形式的连贯性。
扫描线算法
第9页/共57页