计算机图形学_ 光栅图形学算法(一)_24 多边形扫描转换X扫描线算法_

图形学（4）多边形的扫描转换（上）由于计算机屏幕的光栅显示，需要发展一套相应的光栅图形学算法配合它。

前面介绍了直线段如何才能显示在计算机屏幕上，接下来要介绍一下多边形如何在计算机屏幕上显示，内部颜色又如何填充。

多边形的扫描转换多边形的扫描转换和区域填充的实质是思考如何在离散的像素集上表示连续的二维图形，目前主要用两种方法表示一个多边形：定点表示和点阵表示定点表示和点阵表示定点表示：用多边形的定点序列来表示多边形，这种方法直观，几何意义强，占内存少，且易于进行几何转换。

但是由于其并未说明具体哪些像素点在多边形内部，故着色时仍需特定算法点阵表示：用多边形内的像素表示多边形，这种方法丢掉了很多多边形的几何属性，不易于几何转换，但却是光栅显示中所需要的表示形式。

定点表示与点阵表示之间的相互转换成了光栅显示中需要研究的重要问题。

其中，定点表示转换为点阵表示称为多边形的扫描转换，而点阵表示转换为定点表示不属于计算机图形学的研究范畴，需要图像识别的知识去实现它。

多边形的扫描转换多边形也有分类：凸多边形（任意两顶点连线均在多边形内），凹多边形（不符合凸多边形的定义），含内环多边形（多边形内包含多边形）现在，要讨论的问题就转化为了已知边界，找到多边形内部的点并填色问题。

X-扫描线算法X-扫描线算法核心思想是按一定顺序，用扫描线去与多边形相交，计算其相交区间并对相交区间填色。

区间的端点通过扫描线与多边形边界线交点获得如图，按y正方向递增的扫描线算法可以按如下步骤求得：确定多边形所需扫描线的最大、最小y值，也即多边形定点的最值。

按y值递增循环，每次循环时循环体中要进行的工作有：a)?扫描线与多边形各边求交b)?所有交点按照递增顺序排序c)?交点配对，确定多边形在该条扫描线处的内、外d)?对“内”区间进行颜色填充但是，这看似没毛病的算法其实是有隐患的，其一就是交点的配对问题。

比如，万一我的扫描线撞上多边形定点，然后多边形与扫描线交点是奇数个怎么办？（也就是上图中过点P3时的情况）X-扫描线算法潜在问题1：交点配对对于交点个数问题，我们只要制定一套严谨的交点个数计数方案，规定好什么时候计算交点，什么时候不计算就行了。

描述多边形扫描转换的扫描线算法的基本步骤多边形扫描转换是计算机图形学中一种常用的算法，用于将输入的多边形进行转换和填充。

其基本步骤包括初始化，活性边表的生成，活性边表的更新和扫描线的处理。

1.初始化首先，需要根据输入的多边形构造一个扫描线填充的边表。

这包括对多边形顶点的排序、计算多边形中的水平线交点，并将边表中的数据初始化为初始值。

2.活性边表的生成活性边表是用来存储和管理与扫描线相交的边的数据结构。

生成活性边表的过程包括两个步骤：-遍历多边形的每一条边，将边与当前扫描线的位置进行比较，如果两者相交，则将这条边添加到活性边表中。

-对活性边表中的边按照交点的水平位置进行排序。

这里可以使用插入排序等算法。

3.活性边表的更新活性边表需要在每次扫描线移动时进行更新。

这包括对活性边表中的边进行更新，以反映新的交点或边的状态的变化。

-对于与当前扫描线相交的边，需要计算其交点，并更新到活性边表中。

-对于已经处理完的边或超出当前扫描线范围的边，从活性边表中移除。

4.扫描线的处理在每次扫描线移动时，需要对当前的活性边表进行处理。

这包括两个子步骤：-将活性边表中的边按照两两成对的方式遍历，找到当前扫描线和这两条边所定义的三角形的上顶点和下顶点。

-将这个三角形的内部填充，并进行显示或存储等处理。

5.继续扫描线的移动在处理完一条扫描线后，需要将扫描线的位置向上移动一个单位，并继续执行第3步和第4步，直到所有的扫描线都被处理完毕。

总结：多边形扫描转换的基本步骤包括初始化、活性边表的生成、活性边表的更新和扫描线的处理。

这个算法通常用于实现对多边形的填充。

在每次扫描线移动时，活性边表需要进行更新，以反映新的交点或变化的边的状态。

扫描线的处理包括遍历活性边表中的边，并根据扫描线和这两条边所定义的三角形的顶点来进行填充。

最后，重复执行扫描线的移动和对活性边表的更新和处理，直到所有的扫描线都被处理完毕。

光栅化算法一、概述光栅化算法是计算机图形学中的一种基础算法，用于将连续的矢量图形数据转换为离散的像素点。

在图形渲染中，光栅化算法起到了至关重要的作用，它能够高效地将矢量图形转化为像素点，从而实现图形的显示。

二、光栅化的原理光栅化算法的基本原理是将矢量图形分解为像素点的集合。

它通过扫描线或者逐点的方式，将矢量图形上的点映射到屏幕上的像素点。

光栅化算法可以分为线段光栅化和多边形光栅化两种。

2.1 线段光栅化算法线段光栅化算法是将一条线段转换为像素点的集合。

常用的线段光栅化算法有DDA算法和Bresenham算法。

2.1.1 DDA算法DDA算法（Digital Differential Analyzer）是一种简单直观的线段光栅化算法。

它通过沿着线段的方向逐个像素点进行采样，从而得到线段上的像素点。

DDA算法的基本思想是根据线段的斜率，计算每个像素点的坐标，并进行取整操作。

DDA算法的优点是简单易懂，但由于需要进行浮点数计算和取整操作，效率较低。

在处理大量线段时，可能会出现像素点丢失或者重复的情况。

2.1.2 Bresenham算法Bresenham算法是一种高效的线段光栅化算法。

它通过利用整数运算和递增误差的方式，减少了浮点数计算和取整操作，从而提高了算法的效率。

Bresenham算法的基本思想是根据线段的斜率和误差项，选择最接近线段路径的像素点。

通过递增误差项的方式，确定下一个像素点的位置，并更新误差项。

这样就能够准确地绘制出线段上的像素点，避免了像素点丢失或者重复的情况。

2.2 多边形光栅化算法多边形光栅化算法是将一个闭合的多边形转换为像素点的集合。

常用的多边形光栅化算法有扫描线填充算法和边缘标记算法。

2.2.1 扫描线填充算法扫描线填充算法是一种基于扫描线的多边形光栅化算法。

它通过从多边形上的最低点开始，逐行扫描，将扫描线与多边形的交点作为像素点。

扫描线填充算法的基本步骤如下： 1. 找到多边形的最低点作为起始点。

多边形扫描转换算法多边形扫描转换算法是一种计算机图形学中常用的算法，用于将一个多边形转换为一组水平线段，以便进行填充或渲染。

该算法的基本思想是将多边形沿着水平方向进行扫描，找出多边形与水平线段的交点，并将这些交点按照从左到右的顺序进行排序，最终得到一组水平线段。

多边形扫描转换算法的实现过程可以分为以下几个步骤：1. 找出多边形的顶点首先需要找出多边形的顶点，这些顶点可以通过遍历多边形的边来得到。

在遍历边的过程中，需要注意将相邻的边进行合并，以便得到多边形的完整轮廓。

2. 找出多边形与水平线段的交点在进行扫描转换时，需要将多边形沿着水平方向进行扫描，找出多边形与水平线段的交点。

这些交点可以通过遍历多边形的边来得到，对于每条边，需要判断其是否与当前扫描线相交，如果相交，则计算出交点的坐标。

3. 对交点进行排序得到多边形与水平线段的交点后，需要将这些交点按照从左到右的顺序进行排序。

这可以通过对交点的x 坐标进行排序来实现。

如果有多个交点具有相同的 x 坐标，则需要按照其 y 坐标进行排序。

4. 将交点组成线段将交点按照从左到右的顺序进行排序后，就可以将它们组成一组水平线段。

对于相邻的两个交点，可以将它们之间的部分作为一条水平线段。

如果两个交点之间没有其他交点，则可以将它们之间的部分作为一条水平线段。

5. 进行填充或渲染得到一组水平线段后，就可以进行填充或渲染。

对于填充操作，可以使用扫描线算法来实现。

对于渲染操作，可以将每条水平线段转换为一组像素点，并将这些像素点进行绘制。

多边形扫描转换算法的优点是可以处理任意形状的多边形，并且可以得到一组水平线段，方便进行填充或渲染。

但是该算法的缺点是需要进行大量的计算，特别是在多边形较复杂时，计算量会非常大，导致性能下降。

为了提高多边形扫描转换算法的性能，可以采用一些优化技术。

例如，可以使用空间分割技术来减少计算量，将多边形分割成多个小块进行处理。

另外，可以使用并行计算技术来加速计算过程，将多个处理器或计算机同时进行计算。

计算机图形学——多边形的扫描转换（基本光栅图形算法）⼀、多边形扫描转换在光栅图形中，区域是由【相连的】像素组成的集合，这些像素具有【相同的】属性值或者它们位于某边界线的内部1、光栅图形的⼀个基本问题是把多边形的顶点表⽰转换为点阵表⽰。

这种转换成为多边形的扫描转换。

2、多边形的扫描转换与区域填充问题是怎样在离散的像素集上表⽰⼀个连续的⼆维图形。

3、多边形有两种重要的表⽰⽅法：（1）顶点表⽰：⽤多边形的定点序列来表⽰多边形优点：直观、⼏何意义强、占内存少、易于进⾏⼏何变换缺点：没有明确指出那些象素在多边形内，故不能直接⽤于上⾊（2）点阵表⽰：是⽤位于多边形内的象素集合来刻画多边形缺点：丢失了许多⼏何信息（eg:边界、顶点等）但是【点阵表⽰是光栅显⽰系统显⽰时所需的表现形式。

】多边形的扫描转换就是把多边形的顶点表⽰转换为点阵表⽰，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜⾊。

实际上就是多边形内的区域的着⾊过程。

4、多边形分类⼆、X扫描线算法X扫描线算法填充多边形的基本思想是按扫描线顺序，计算扫描线与多边形的相交区间，再⽤要求的颜⾊显⽰这些区间的象素，即完成填充⼯作。

区间的端点可以通过计算扫描线与多边形边界线的交点获得。

如扫描线y=3与多边形的边界相交于4点（2,3）、（4,3）、（7,3）、（9,3）这四个点定义了扫描线从x=2到x=4，从x=7到x=9两个落在多边形内的区间，该区间内像素应取填充⾊。

算法的核⼼是按x递增顺序排列交点的x坐标序列。

由此可得到扫描线算法步骤如下：算法步骤：1.确定多边形所占有的最⼤扫描线数，得到多边形定点的最⼩最⼤值（y min和y max）；2.从y min到ymax每次⽤⼀条扫描线进⾏填充；3.对⼀条扫描线填充的过程分为四个步骤：a)求交点；b)把所有交点按递增顺序排序；c)交点配对（第⼀个和第⼆个，第三个和第四个）；d)区间填⾊。

贵州大学计算机图形学实验报告学院：计算机科学与信息学院专业：软件工程班级：反映）根据扫描线的连贯性可知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。

所以，对所有的扫描线填充入点到出点之间的点就可填充多边形。

如何具体实现（如何找到入点、出点）？根据区域的连贯性，分为3个步骤：(1)求出扫描线与多边形所有边的交点；(2)把这些交点按x坐标值以升序排列；(3)对排序后的交点进行奇偶配对，对每一对交点间的区域进行填充。

步骤(3)如上图：对y＝8的扫描线，对交点序列按x坐标升序排序得到的交点序列是(2,4,9,13)，然后对交点2与4之间、9与13之间的所有象素点进行填充。

求交点、排序、配对、填色利用链表：与当前扫描线相交的边称为活性边(Active Edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活性边表AEL (AEL， Active Edge List)。

它记录了多边形边沿扫描线的交点序列。

AEL中每个对象需要存放的信息：ymax：边所交的最高扫描线；x：当前扫描线与边的交点；Δx：从当前扫描线到下一条扫描线之间的x增量next：指向下一对象的指针。

伪码：建立ET，置y为ET中非空桶的最小序号；置AEL表为空，且把y桶中ET表的边加入AEL表中；while AEL表中非空do begin对AEL表中的x、Δx按升序排列；按照AEL表中交点前后次序，在每对奇偶交点间的x段予以填充；计算下一条扫描线：y=y+1；if 扫描线y=ymax then 从AEL表中删除这些边；对在AEL表中的其他边，计算与下一条扫描线的交点：x=x +Δx 按照扫描线y值把ET表中相应桶中的边加入AEL表中；endend of algorithm二、区域填充算法：区域可采用两种表示形式:内点表示枚举区域内部的所有像素；内部的所有像素着同一个颜色；边界像素着不同的颜色。

边界表示：枚举出边界上所有的像素；边界上的所有像素着同一颜色；内部像素着不同的颜色。

计算机图形学（三种画线算法）第⼆章：光栅图形学算法1、光栅显⽰器：光栅扫描式图形显⽰器简称光栅显⽰器，是画点设备，可看作是⼀个点阵单元发⽣器，并可控制每个点阵单元的亮度2、由来：随着光栅显⽰器的出现，为了在计算机上处理、显⽰图形，需要发展⼀套与之相适应的算法。

3、研究内容：1>直线段的扫描转换算法2>多边形的扫描转换与区域填充算法3>裁剪算法4>反⾛样算法5>消隐算法⼀、直线段的扫描转换算法1.为了显⽰⼀条直线，就在光栅显⽰器上⽤离散的像素点逼近直线，所以我们就要知道这些像素点的坐标已知P0和P1，利⽤斜截式⽅程，y=kx+b,求出k=（y1-y0）/(x1-x0),b为截距现在k,b已知，x,y未知，现在假设⼀个像素距离为y，即可求出y的值。

因为像素的坐标是整数，所以y值还要进⾏取整处理2.在计算机中加法的运算更快，乘法较慢，故可以把上述⽅法优化来提⾼效率1>数值微分法（DDA）2>中点划线法3>Bresenham算法数值微分法（DDA）-----增量算法（只有⼀个加法）这个式⼦的含义是：当前步的y值等于前⼀步的y值加上斜率k（增量）例⼦：思考：x递增1，y递增k，是否适合任意的k？可改进的点：1>⼀般情况下，k都是⼩数，且每⼀步均要对y四舍五⼊，唯⼀改进的途径是把浮点运算变为整数加法！2>⽅程还有两点式，⼀般式当|k|<=1时，伪代码如下：voidDDALine(int x0,int y0,int x1,int y1,int color){Int x;Float dx,dy,y,k;dx=x1-x0;dy=y1-y0;K=dy/dx;y=y0;For(x=x0,x<=x1;x++){Drawpixel(x,int(y+0.5),color);//drawpixel(x, y, color)在(x, y)像素点绘制颜⾊为color的点Y=y+k;}}中点画线法采⽤直线的⼀般式⽅程：Ax+By+C=0 F(x,y)=0，其中a = y0 - y1， b = x1 - x0，c = x0y1 - x1y0令F(x, y)=0则得出直线⽅程，代⼊ (x0, y0)和(x1, y1)，便可得到三个⽅程，可求出a,b,c的值⼀条直线把平⾯分成了三个部分，直线上⽅，直线上，直线下⽅x⽅向上+1，y⽅向上加不加1需判断如何判断Q在M的上⽅还是下⽅？把M点的坐标带⼊⽅程,其中a = y0 - y1， b = x1 - x0分析计算量？两个乘法，四个加法，推导出d的增量公式d的初始值包含⼩数，因此可以⽤2d来代替d实现整数加法，所以d=2a+b伪代码如下：Void MidPointLine(int x0,int y0,int x1,int y1,int color){Int a,b,delta1,delta2,d,x,y;a=y0-y1;b=x1-x0;d=2*a+b;Delta1 = 2*a;Delta2 =2*(a+b);X = x0;Y=y0;//在对应的x,y像素点着⾊putpixel(x,y,GREEN);while(x<x1){if(d<0){x++;y++;d+=delta2;}else{x++;d+=delta1;}//在对应的x,y像素点着⾊putpixel(x,y,GREEN);}Bresenham算法每步的进化：DDA把算法效率提⾼到每步只做⼀个加法中点算法进⼀步把效率提⾼到每步只做⼀个整数加法Bresenham算法提供了⼀个更⼀般的算法，该算法不仅有好的效率，⽽且有更⼴泛的适⽤范围如何把算法的效率也提⾼到整数加法？改进⼀：令e=d-0.5因为d的初值为0，所以e的初值为-0.5，e=e+k,如果e>0,e=e-1改进⼆：在计算e值的情况下还是关于浮点数的计算，所以把浮点数化为整数。