计算机图形学(多边形的扫描转换)ppt.ppt

第三章基本光栅图形算法 本章内容 2 2014 2015 1 CG SCUEC 多边形的扫描转换 什么是多边形的扫描转换 把多边形的顶点表示转化为点阵表示 也就是从多边形的给定边界出发 求出位于其内部的各个像素 并给帧缓冲器内各个对应元素设置相应的灰度和颜色多边形的扫描转换过程 实际上是给多边形包围的区域着色的过程 多边形的表示方法顶点表示 用多边形的顶点序列来刻划多边形该表示方法几何意义强 占内存少不能明确指出哪些像素在多边形内 不能直接用于面着色点阵表示 用位于多边形内的象素的集合来刻划多边形该方法便于利用帧缓冲器表示图形 是面着色所需要的图形表示形式失去了许多重要的几何信息 3 2014 2015 1 CG SCUEC 为什么研究图形的扫描转换与区域填充 与单纯由线条所构成的线画图形相比 采用面着色绘制的光栅图形显得更为生动 直观 真实感更强 面着色可以使使光栅图形的画面明暗自然 色彩丰富 形象逼真 具有真实感 4 2014 2015 1 CG SCUEC 逐点判断法 逐点判断是实现多边形扫描转换最简单的方法逐个像素判别 确定它们是否在多边形内 从而给出位于多边形内的点 像素 的集合 defineMAX100typedefstruct intVertexNum 多边形顶点个数PointVertices MAX 多边形顶点数组 Polygon 多边形 5 2014 2015 1 CG SCUEC voidFillPolygonPbyP PolygonP intx y for x xmin x xmax x for y xmin y ymax y if IsInside P x y FrameBuffer x y POLYGON COLOR elseFrameBuffer x y BACKGROUND COLOR endofFillPolygonPbyP IsInside P x y 验证点 x y 是否在多边形P内的布尔函数 当从 x y 到 y 的射线与P的交点个数是奇数时 函数取值true 否则取值False FrameBuffer x y 在帧缓存中对应位置存放屏幕上像素 x y 的颜色值 POLYGON COLOR 多边形P的颜色值 BACKGROUND COLOR 屏幕的背景色 逐点判断法 6 2014 2015 1 CG SCUEC 扫描线算法 扫描线算法按扫描线的顺序计算出扫描线与多边形的相交区间 然后用要求的颜色填充这些区间内的像素 该算法利用了相邻像素间的连续性 避免对像素的逐点判断和反复求交运算 减少了计算量 提高了算法速度 先求出扫描线与多边形边的交点 利用扫描线的连续性求出多边形与扫描线相交的连续区域 然后利用多边形边的连续性 求出下一条扫描线与多边形的交点 对所有扫描线由上到下依次处理 区域的连续性 扫描线的连续性 边的连续性 7 2014 2015 1 CG SCUEC 区域的连续性 2 1 设多边形P的顶点为Pi xi yi i 0 1 2 n 又设是各顶点Pi的纵坐标yi的递减数列 当 屏幕上位于于y 和y 两条扫描线之间的长方形区域 被多边形P的边分割成若干梯形 三角形看作其中一底边长为0的梯形 8 2014 2015 1 CG SCUEC 区域的连续性 2 2 如果知道长方形区域内任一梯形内一点关于多边形P的内外关系后 即可确定区域内所有梯形关于P的内外关系 此性质称为区域的连续性 这些梯形有如下的三个性质 梯形的两底边分别在y 和y 两条扫描线上 腰在多边形P的边上或在显示屏幕的边界上 梯形可分为两类 一类位于多边形P的内部 另一类在多边形P的外部 两类梯形在长方形区域 内相间的排列 即相邻的两梯形必有一个在多边形P内 另一个在P外 9 2014 2015 1 CG SCUEC 设多边形P的顶点 将各顶点的纵坐标按递减顺序排列 即设当前扫描线 与多边形P的边的交点记为 设为与P的边界各交点横坐标的递增序列 该序列称为交点序列 扫描线的连续性 2 1 10 2014 2015 1 CG SCUEC 1 交点个数l是偶数 2 扫描线上的区间l 1位于多边形P内 下图中的红线段部分 其余区间都在P外 下图中的虚线段部分 两类区间沿扫描线相间排列 这些性质就称为扫描线的连续性 扫描线的连续性 2 2 交点序列具有以下性质 11 2014 2015 1 CG SCUEC 边的连续性 两交点序列元素的个数相等 即l h 当前扫描线e与多边形的某些边是相交的 设是该扫描线与这些边各交点横坐标的递增序列 设下一条扫描线为d e 1 如果y k e d y k 1 那么扫描线d与上述边也是相交的 交点横坐标递增序列记为 对同一条边 前一条扫描线e与该边的交点为xeir 而后一条扫描线d e 1与该边的交点则为xdir xeir 1 m 如右图所示 以上性质称为边的连续性 12 2014 2015 1 CG SCUEC 存在的问题 上述三种形式的连续性都基于一个几何事实 每一条扫描线与多边形P的边界的交点个数都是偶数 包括零 但是当扫描线与多边形P的边界的交点恰好是P的顶点时 如果把每一奇点简单地计为一个交点 则交点个数可能出现奇数 如下图中的扫描线7的情况 若将每一奇点都简单地计为两个交点 同样会导致反常的结果 如下图中扫描线2的情况 13 2014 2015 1 CG SCUEC 多边形顶点的分类 设多边形P的顶点为这些顶点可分为两类 极值点和非极值点 如果 则称顶点为极值点 如下图中的 否则称为非极值点 如下图中的 14 2014 2015 1 CG SCUEC 2020 3 18 15 可编辑 奇点的处理 为了使交点个数保持为偶数 规定当奇点是P的极值点时 该点按两个交点计算 否则按一个交点计算 预处理 若Pi是非极值点 则将两边中位于扫描线y yi上方的那条边在Pi点处截去一单位长 非极值点的处理 16 2014 2015 1 CG SCUEC 算法的实现步骤 对于每一条扫描线 多边形的扫描转换可分为以下4步 求交点 计算扫描线与多边形各边的交点 设交点个数为n 交点排序 把所有的交点按x值递增的顺序进行排列 交点配对 将排序后的第1个与第2个交点 第3个与第4个交点 第n 1个与第n个交点配对 每对交点就代表扫描线与多边形的一个相交区间 区间填色 把相交区间内的像素置成多边形的颜色 相交区间外的像素置成背景色 17 2014 2015 1 CG SCUEC 算法的数据结构 与当前扫描线相交的边称为活性边 把活性边与扫描线的交点按x坐标递增的顺序放在一个链表中 该链表就称为活性边表 ActiveEdgeList AEL 设多边形某一条边的方程为 当前扫描线与该边的交点坐标为 则下一条扫描线与该边的交点不需要重新计算 只要加一个增量即可 因为此时有 其中为常数 并规定时 18 2014 2015 1 CG SCUEC 算法的数据结构 19 2014 2015 1 CG SCUEC 为方便活性边表的建立与更新 还要为每一条扫描线建立一个新边表 NewEdgeList NEL 存放在该扫描线上第一次出现的边 也就是说 如果某边的较低端点为 则该边就放在扫描线的新边表中 注意 水平边不放到任何扫描线的NEL中 即水平边不参加分类 NEL中的节点结构与AEL相同 只是x在这里不再表示边与扫描线的交点 而是表示该边较低端点的x坐标值 算法的数据结构 20 2014 2015 1 CG SCUEC 算法描述 根据给出的多边形顶点坐标 建立新边表NEL AEL初始化 将边的活性边表AEL设置为空 y初始化 取扫描线纵坐标y的初始值为NEL中非空元素的最小序号 21 2014 2015 1 CG SCUEC 如新边表NEL中的第y类元素非空 则将属于该类的所有边从NEL中取出并插入边的活性边表AEL中 AEL中的各边按照x值 当x的值相等时 按 x值 递增方向排序若相对于当前扫描线 边的活性边表AEL非空 则将AEL中的边两两依次配对 即第1 2边为一对 第3 4边为一对 依此类推 每一对边与当前扫描线的交点所构成的区段位于多边形内 依次对这些区段上的点 象素 按多边形属性着色将活性边表AEL中满足y ymax的边删去将活性边表AEL剩下的每一条边的x域累加 x 即x x x将当前的扫描线的纵坐标值y累加 即y y 1 4 按从下到上的顺序对纵坐标值为y的扫描线 当前扫描线 执行下列步骤 直到新边表NEL和活性边表AEL都为空 算法描述 22 2014 2015 1 CG SCUEC P0 2 5 P1 2 10 P2 9 6 P3 16 11 P4 16 4 P5 12 2 P6 7 2 具体例子 23 2014 2015 1 CG SCUEC 边缘填充算法 假设某像素的颜色是 对该像素做偶数次求补运算后 其颜色还是 做奇数次求补运算后 其颜色变为 在光栅图形中 如某区域已着上值为M的某种颜色 则上述求补运算的结果是 对区域作偶数次求补运算后 该区域的颜色不变 作奇数次求补运算后 该区域的颜色则变成值为的颜色 24 2014 2015 1 CG SCUEC 以扫描线为中心的边缘填充算法 设x0 x2 xm是扫描线y e与多边形P的边界交点x坐标序列 不要求递增排列 则该扫描线上位于多边形P内的像素可按如下步骤求得 步骤1 将位于扫描线y e上的所有像素都着上值为M的颜色forx xmintoxmaxdosetpixel framebuffer x e M 步骤2 将位于扫描线y e上所有坐标大于xi i 1 2 m 的像素向右求反fori 1tomdoforx xitoxmaxdocomplement framebuffer x e 25 2014 2015 1 CG SCUEC 1 将绘图窗口的背景色置为 以边为中心的边缘填充算法 2 对多边形的每