计算机图形学3多边形gai.ppt

计算机图形学 讲授： 郝旺身 E_Mail：haows@126.com学时：48 第一章 绪论 1 第二章 直线与直线的图形 3 第三章 多边形 6 第四章 二次曲线 4 第五章 裁剪 6 第六章 曲线曲面 4 第七章 图形变换 2 考试 2 第三章 多边形 1 多边形的概念 2 多边形的填充 3 polygon fill-area algorithm 4 反走样基础 3.1 多边形的概念 一 多边形的分类 多边形：由一些首尾连接的线段构成的图形，线段为多边形的边线段的端点成为多边形的顶点。 多边形分为凸多边形和凹多边形。 多边形的特征： Vertex: P1,P2, ….Pn Edge: PiPi+1 二 多边形的描述 如果要用来描述多边形则应该描述多边形的特征，比如边和顶点。 多边形的顶点序列为：P1,P2, ….Pn，P1。 则用一个二维数组来表示。 3.2 多边形的填充 3.3 polygon fill-area algorithm 一多边形扫描转换的扫描线算法 1，思想： 1）取最上端的一条扫描线与多边形的各边相交，(x1 ，x2 ), (x3 ，x4 ) ……, (xl-1 ，xl )，在第一条扫描线时，x1 ＝x2 ，x3 ＝x4。 2）排序 3）填色 4）下一条扫描线 5）区域变化：在边的下端点变化 I)换新边，ii）一起退出 1）insert the edge (边插入)。 6）update the edge (边更新)。 2）sort (排序)。 3）filling (填色)。 4）next scan line (下一条扫描线)。 5）delete the edge (边删除)。 remark： 1）充分利用连贯性 2）避免求交点运算，计算量少，速度快 3）数据结构复杂 4）程序复杂 注：如果四连通区域内的任意点出发只经过上下左右四个方向的运动可以到达区域的任何一点，即为漫延。 种子填充法：有一点出发逐步影响周围的点。 逐点漫延，用堆栈实现。 注： 1）点进出系统堆栈达4次 2）程序简单明了 3）算法采用递归（尽量不用） 4）费时费内存。 2 种子填充的扫描线算法 Algorithm: step1：给定种子点（x，y）在种子点所在扫描线上找出包含种子点所在区域内的最长的区间（xl，xr） 三 边填充算法 基本思想：对于每一条扫描线与多边形的交点 （x，y），将交点右方的所有象素取补。 栅栏填充算法： 栅栏：指的是一条与扫描线垂直得直线，一般栅栏的位置取过多边形顶点且把多边形分成左右两半。 对于每一条与多边形相交的扫描线： 1）如果交点位于栅栏之左，将所有位于扫描线与边交点之右和栅栏之左的象素取补； 2）如果交点位于栅栏之右，将所有位于扫描线与边交点之左和栅栏之右的象素取补； 第四节 反走样基础 走样：由离散量来表示连续量时引起的失真。 反走样：用于减少或克服走样的技术。 * * 2，要求的序列 1）交点序列：动态，可调。 I）x值可修改（Δxik ） II）区域发生变化时，老边退出，新边加入。 2）y下：判别带状区域是否发生变化。 3）y上 3，数据结构 回顾： 1）建立边结构：new（element），alloc（） 2）判断是否到尾：next＝＝Null 3）插入一元素（element） 二 区域的种子填充算法 1）点邻域：四邻域，八邻域 四邻域：四个点为A点的邻域，对于上下左右四个 方向运动而言，上下左右四点构成一点的四邻域。 八邻域同样可得。 2）路径：四连通路径，八连通路径 四连通路径：点集中相邻两点均在对方的四邻域中 3）区域：四连通区域，八连通区域 四连通区域：如果一点集内任意两点都存在一条完全有 该点集中的内点组成的四连通路径相连接则称该点集为 四连通区域。