目录：

多边形的扫描转换与区域填充

多边形有两种重要的表示方法：顶点表示和点阵表示

多边形的扫描转换：把多边形的顶点表示转换为点阵表示

为什么研究图形的扫描转换和区域填充？

  1. 与单纯由线条所构成的线画图形相比，采用面着色绘制的光栅图形显得更为生动、直观，真实感更强
  2. 面着色可以是光栅图形的画面明暗自然，色彩丰富，形象逼真，且有真实感

多边形的扫描转换

扫描线算法

对于一条扫描线填充过程可以分为四个步骤：（1）求交（2）排序（3）配对（4）填色

5-3-1-1.png

5-3-1-2.png

边界标志算法

  1. 帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。
  2. 然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。
  3. 使用一个布尔量inside来指示当前点是否在多边形内的状态。

二者比较

  • 用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同
  • 但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。

区域填充算法

  • 区域指已经表示成点阵形式的填充图形，它是象素的集合。
  • 区域可采用内点表示和边界表示两种表示形式。
  • 区域可分为4向连通区域和8向连通区域。
  • 区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。
  • 区域填充算法要求区域是连通的。

顶点表示：也称为几何表示，是用区域的顶点序列来表示区域。

点阵表示：也称为像素表示，是用位于多边形内的像素集合来刻画多边形。

内点表示：区域内的所有像素着同一颜色，而区域外的所有像素具有另一种颜色；

边界表示：区域边界上的所有像素点具有特定的颜色（可以是填充色），在区域内的所有像素均不能具有这一特定色，而且边界外的像素不能 具有与边界相同的颜色。

算法基本思想：

给定区域G一种子点（x, y）,首先判断该点是否是区域内的一点，如果是，则将该点填充为新的颜色，然后将该点周围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理，通过这种扩散完成对整个区域的填充。

多边形的扫描转换与区域填充算法小结

  1. 多边形扫描转换是指将多边形的顶点表示转化为点阵表示
  2. 区域填充改变填充颜色
  3. 在区域填充算法中，要求给定区域内的一点作为种子点，然后从这一点根据连通性将新的颜色扩展到整个区域。
  4. 扫描转换多边形是从多边形的边界（顶点）信息出发，利用多种形式的连贯性进行填充的。
  5. 扫描转换区域填充的核心是知道多边形的边界。
  6. 区域填充条件更强一些，不但要知道边界，而且要知道区域内的一点，可以利用四连通或八连通区域不断向外扩展。

剪裁

裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以 便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。

直线段裁剪

直线段裁剪算法是复杂图元裁剪的基础。
复杂的曲线可以通过折线段来近似，裁剪问题可以化为直线段的裁剪问题。

  • Cohen-Sutherland
  • 中点分割算法
  • 梁友栋－barskey算法

Cohen-Sutherland裁剪

基本思想：
对于每条线段P1P2分为三种情况处理分为三种情况处理:
 若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。
 若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。
若线段不满足“取”或“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。

中点分割算法

与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况:

  • 全在、完全不在和线段和窗口有交。对前两种情况，进行一样的处理。
  • 对于第三种情况，用中点分割的方法求出线段与窗口的交点。

梁友栋－Barskey算法

--见笔记--

Cohen-Sutherland与Liang-Barsky算法的比较

  1. Cohen-Sutherland算法的核心思想是编码
  2. 如果被裁剪的图形大部分线段要么在窗口内或者要么完全在窗口外，很少有贯穿窗口的。Cohen-Sutherland算法 效果非常好
  3. 在一般情况下，Liang-Barsky裁剪算法的效率则优于Cohen-Sutherland算法
  4. Cohen-Sutherland和Liang-Barsky只能应用于矩形窗口

多边形裁剪

基本思想是一次用窗口的一条边裁剪多边形。

考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧
多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种

5-3-2-1.png

  • 对于情况（1）仅输出顶点P；情况（2）输出0个顶点；
  • 情况（3）输出线段SP与裁剪线的交点I；
  • 情况（4）输出线段SP与裁剪线的交点I和终点P

上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。
对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。

字符裁剪

  • 串精度: 将包围字串的外接矩形对窗口作裁剪 (字符串的所有字符都在窗口内则保留，否则舍弃)
  • 字符精度: 将包围字的外接矩形对窗口作裁剪 (对窗口有重叠或者落在外面的裁掉)
  • 以及笔画\象素精度: 将笔划分解成直线段对窗口作裁剪 (像素、比划裁剪)
  • 5-5-3-1.png

反走样

用离散量表示连续量引起的失真现象称之为走样(aliasing)

用于减少或消除这种效果的技术称为反走样(antialiasing)

提高分辨率

把分辨率提高一倍

  • 直线经过两倍的象素，锯齿也增加一倍，
  • 但同时每个阶梯的宽度也减小了一倍，
  • 所以显示出的直线段看起来就平直光滑了一些。

增加分辨率虽然简单，但是不经济的方法——会引起扫描转换时间、帧缓存容量等一系列问题。

而且它也只能减轻而不能消除锯齿问题

区域采样

走样原因：由于在实际中，像素是由实际面积大小不为0，同时直线段的宽度是至少为1个像素。而我们假设是像素面积为0，亮度由覆盖该点的亮度决定，同时线段宽度为0。二者的矛盾是导致走样原因。

基本思想：

每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该象素的亮度值。

过程

  1. 首先将屏幕象素均分成n个子象素
  2. 然后计算中心点落在直线段内的子象素的个数k。
  3. 将屏幕该象素的亮度置为相交区域面积的近似值可k/n。

非加权区域采样方法有两个缺点：

  1. 象素的亮度与相交区域的面积成正比，而与相交区域落在象素内的位置无关，这仍然会导致锯齿效应。
  2. 直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差。

加权区域取样

消隐

投影变换失去了深度信息，往往导致图形的二义性

要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线和隐藏面，简称为消隐。

经过消隐得到的投影图称为物体的真实图形。

消隐的对象是三维实体模型。三维实体模型的表示主要有边界表示法和实体构造法(CSG)等。

消隐的分类

  • 按消隐对象分类
    1. 线消隐(线框图)：消隐对象是物体上的边，消除的是物体上不可见的边。
    2. 面消隐(填色图)：消隐对象是物体上的面，消除的是物体上不可见的面。

Southerland按消隐空间分类

  1. 物体空间的消隐算法: 将场景中每一个面与其他每个面比较，求出所有点、边、面遮挡关系。

    • 光线投射
    • Roberts

  2. 图像空间的消隐算法: 对屏幕上每个象素进行判断，决定哪个多边形在该象素可见。

    • Z－buffer
    • 扫描线
    • Warnock

  3. 物体空间和图像空间的消隐算法: 在物体空间中预先计算面的可见性优先级，再在图像空间中生成消隐图。

    • 画家算法

画家算法（列表优先算法）

  1. 先把屏幕置成背景色

  2. 再把物体的各个面按其离视点的远近进行排序，排序结果存在一张深度优先级表中。

  3. 然后按照从远到近的顺序逐个绘制各个面。

Z缓冲区算法

帧缓存来存放每个象素的颜色值: 初值取成对应背景颜色的值

深度缓存来存放每个象素的深度值: 初值可放z的极小值

算法过程：

  1. 在把显示对象的每个面上每一点的属性（颜色或灰度）值填入帧缓冲器相应单元前，要把这点的z坐标值和z缓冲器中相应单元的值进行比较。只有前者大于后者时才改变帧缓冲器的那一单元的值，同时z缓冲器中相应单元的值也要改成这点的z坐标值。

  2. 如果这点的z坐标值小于z缓冲器中的值，则说明对应象素已经显示了对象上一个点的属性，该点要比考虑的点更接近观察点。

  3. 对显示对象的每个面上的每个点都做了上述处理后，便可得到消除了隐藏面的图