gjl_chp04二维填充图元的生成.ppt

浙江大学计算机图形学 扫描转换矩形 问题： 矩形是简单的多边形，那么为什么要单独处理矩形？ 比一般多边形可简化计算。 应用非常多，窗口系统。 共享边界如何处理？ 原则：左闭右开，下闭上开 扫描转换矩形 方法： 扫描转换多边形 多边形分为凸多边形、凹多边形、含内环的多边形。 扫描转换多边形 多边形的表示方法 顶点表示 点阵表示 顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。 点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。 多边形的扫描转换 多边形的扫描转换：把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。 几种方法：逐点判断法；扫描线算法；边缘填充法；栅栏填充法；边界标志法。 逐点判断法 逐个判断绘图窗口内的像素： 如何判断点在多边形的内外关系？ 1）射线法： 2）累计角度法 3）编码法； 逐点判断法 1）射线法 步骤： 从待判别点v发出射线 求交点个数k K的奇偶性决定了点与多边形的内外关系 逐点判断法 2）累计角度法 步骤 从v点向多边形P顶点发出射线，形成有向角 计算有相交的和，得出结论 逐点判断法 逐点判断的算法虽然程序简单，但不可取。原因是速度太慢，主要是由于该算法割断了各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。 扫描线算法 扫描线算法 目标：利用相邻像素之间的连贯性，提高算法效率 处理对象：非自交多边形 （边与边之间除了顶点外无其它交点） 扫描线算法 交点的取整规则 要求：使生成的像素全部位于多边形之内 假定非水平边与扫描线y=e 相交，交点的横坐标为x, 规则如下 扫描线算法 ●规则1： X为小数，即交点落于扫描线上两个相邻像素之间 (a)交点位于左边之上，向右取整 (b)交点位于右边之上，向左取整 扫描线算法 ●规则2： 边界上象素的取舍问题，避免填充扩大化。 ●解决方法： 边界象素：规定落在右上边界的象素不予填充。 具体实现时，只要对扫描线与多边形的相交区间左闭右开 扫描线算法 ●规则3： 扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。 ●解决方法： 检查两相邻边在扫描线的哪一侧。 只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。 扫描线算法 区域的连贯性 1）梯形的两底边分别在y=yik和y=yik+1两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。 2）这些梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部。 3）两类梯形在长方形区域{yik,yik+1}内相间的排列，即相邻的两梯形必有一个在多边形P内，另一个在P外。 区域的连贯性 根据这些性质，实际上只需知道该长方形区域内任一梯形内一点关于多边形P的内外关系后，即可确定区域内所有梯形关于P的内外关系。 扫描线的连贯性 1）l是偶数。 2）在该扫描线上，只有区段xeik,xeik+1）,k=1,3,5,…,l-1位于多边形P内，其余区段都在P外。 以上性质称为扫描线的连贯性，它是多边形区域连贯性在一条扫描线上的反映。 边的连贯性 可利用d的交点序列计算e的交点序列：先运用递推关系式(1)求得与扫描线y=e和y=d都相交的所有多边形上的交点xer；再求得与扫描线y=d不相交但与扫描线y=e相交的所有边PqPq+1上的交点xeq。然后把这两部分按递增的顺序排列，即可得e的交点序列。 边的连贯性 特别是当存在某一个整数k,0≤k≤n-1,使得 yike, dyik+1 成立时，则由区域的连贯性可知d的交点序列和e的交点序列之间有以下关系： 1）两序列元素的个数相等，如上图所示。 2）点(xeir,e)与(xdjr,d)位于多边形P的同一边上，于是 xeir= xdjr + 1/kjr (2) 这样，运用递推关系式(2)可直接由d的交点序列和e的获得e的交点序列。 以上性质称为边的连贯性，它是区域的连贯性在相邻两扫描线上的反映。 奇点的处理 若奇点做一个交点处理，则情况A，交点个数不是偶数。 若奇点做两个交点处理，则情况B，交点个数不是偶数。 奇点的处理 多边形P的顶点可分为两类：极值奇点和非极值奇点。如果(yi-1 - yi)(yi+1 - yi)≥0，则称顶点Pi