第五章 多边形的扫描转换及区域填充.ppt

内容 基本概念 扫描转换矩形 扫描转换多边形 区域填充 光栅图形的反走样 基本概念 多边形有两种重要的表示方法 顶点表示 用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些象素在多边形内，故不能直接用于面着色 点阵表示 用位于多边形内的象素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。 基本概念 多边形的扫描转换 把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应象素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。 区域填充（演示） 是指先将在点阵表示的多边形区域内的一点（称为种子点）赋予指定的颜色和灰度，然后将这种颜色和灰度扩展到整个区域内的过程。 扫描转换矩形 问题： 矩形是简单的多边形，那么为什么要单独处理矩形？ 应用非常多，特别是窗口系统 比一般多边形可简化计算 共享边界如何处理？ 左闭右开 下闭上开 扫描转换矩形 方法 扫描转换多边形 凸多边形 任意两顶点间的连线均在多边形内 凹多边形 任意两顶点间的连线有不在多边形内的部分 含内环的多边形 多边形内再套有多边形，多边形内的多边形也叫内环，内环之间不能相交 扫描转换多边形 几种方法 逐点判断算法 逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。 扫描线算法（要求重点掌握） 利用相邻像素之间的连贯性，避免逐点判断和反复求交运算。 边缘填充算法 利用求余运算，来达到填充的目的。 逐点判断算法 逐点判断算法 逐个判断绘图窗口内的像素 如何判断点在多边形的内外关系？ 射线法 弧长法 点关于多边形内外关系的判断 射线法（演示） 如果从一点发出的射线与多边形边界的交点个数为奇数，则该点位于多边形之内，否则位于多边形之外。 点关于多边形内外关系的判断 弧长法（累计角度法) 步骤 从v点向多边形P各顶点发出射线，形成有向角 计算有向角的和，得出结论 逐点判断算法-小结 逐点判断的算法虽然程序简单，但不可取。原因是速度太慢，效率低。 主要是由于该算法割断了各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。 扫描线算法 处理对象 非自交多边形 （边与边之间除了顶点外无其它交点） 扫描线算法 扫描线算法是多边形扫描转换的常用算法。 与逐点判断算法相比，扫描线算法充分利用了相邻象素之间的连贯性，避免了对象素的逐点判断和反复求交的运算，达到了减少计算量和提高速度的目的。 开发和利用相邻象素之间的连贯性是光栅图形算法研究的重要内容。扫描转换算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。 扫描线算法 基本思想 对于一个给定的多边形，用一组水平或垂直的扫描线进行扫描，分别求出每条扫描线与多边形的交点，这些交点将扫描线分割为相间排列的落在多边形内和多边形外的线段，将落在多边形内的所有线段上的每个像素点赋以给定的多边形填充色。 利用相邻象素之间的连贯性填充每一条扫描线位于多边形内部的区段。 区域的连贯性 设多边形P的顶点Pi=(xi,yi),i=0,1, …,n，又设yi0,yi1,…yin是各顶点Pi的坐标yi的递减数列，即yik≥yik+1,0≤k≤n-1。 屏幕上位于y=yik和y=yik+1两条扫描线之间的长方形区域被多边形P的边分割成若干梯形（三角形可看作其中一底边长为零的梯形），它们具有下列性质： 区域的连贯性 梯形的两底边分别在y=yik和y=yik+1（ yik≥yik+1)两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。 这些梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部。 两类梯形在长方形区域{yik,yik+1}内相间的排列，即相邻的两梯形必有一个在多边形P内，另一个在P外。 区域的连贯性 结论： 根据这些性质，实际上只需知道该长方形区域内任一梯形内一点关于多边形P的内外关系后，即可确定区域内所有梯形关于P的内外关系。 扫描线的连贯性 设e为一整数，yi0≥e≥yin。若扫描线y=e与多边形P的Pi-1Pi相交，则记其交点的横坐标为xei。 以上交点的横坐标递增排序得到的序列称为交点序列。交点序列具有如下性质： 扫描线的连贯性 （1）交点个数为偶数。 （2）交点之间的区段按交替的顺序依次出现在多边形内部和外部。 以上性质称为扫描线的连贯性，它是多边形区域连贯性在一条扫描线上的反映。 边的连贯性 由扫描线y=e和多边形的所有交点递推出扫描线y=d=e+1与多边形