计算机图形学第二讲 光栅图形学

山东科技大学信息学院
区域的连贯性
根据这些性质，实际上只需知道该长方形 区域内任一梯形内一点关于多边形P的内 外关系后，即可确定区域内所有梯形关 于P的内外关系。
山东科技大学信息学院
扫描线的连贯性
设e为一整数，yi0≥e≥yin。若扫描线y=e与多边形P的 Pi-1Pi相交，则记其交点的横坐标为xei。 现设xei1,xei2,xei3,…,xeil 是该扫描线与P的边界各交点 横坐标的递增序列，称此序列为交点序列。由区域的连贯 性可知，此交点序列具有以下性质：
山东科技大学信息学院
三、多边形的扫描转换
山东科技大学信息学院
1 逐点判断法
• 逐个判断绘图窗口内的像素： • 如何判断点在多边形的内外关系？
1）射线法： 2）累计角度法 3）编码法；
山东科技大学信息学院
逐点判断法
1）射线法
• 步骤： 1. 从待判别点v发出射线 2. 求交点个数k 3. K的奇偶性决定了点与多边形的内外关系
山东科技大学信息学院
3 扫描线种子填充算法
• 扫描线种子填充算法
–目标：减少递归层次 –适用于边界表示的4连通区域 算法思想：在任意不间断区间中只取一个种子 像素（不间断区间指在一条扫描线上一组相 邻元素），填充当前扫描线上的该段区间； 然后确定与这一区段相邻的上下两条扫描线 上位于区域内的区段，并依次把它们保存起 来，反复进行这个过程，直到所保存的个区 段都填充完毕。
逐点判断法程序简单， 速度太慢，效率低。
P1
v P2
山东科技大学信息学院
逐点判断法
• 逐点判断的算法虽然程序简单，但不可取。原 因是速度太慢，主要是由于该算法割断了各象 素之间的联系，孤立地考察各象素与多边形的 内外关系，使得几十万甚至几百万个象素都要 一一判别，每次判别又要多次求交点，需要做 大量的乘除运算，花费很多时间。

直线的斜率为 k＝△y／△x
当 △x＞△y 时，让 x 从 x1 到 x2 变化，每
步递增 1，
那么，x 的变化可以表示为 xi+1＝xi＋1
y 的变化可以表示为 yi+1＝yi＋k
2.1.1 直线DDA算法 (Digital Differential Analyser)
用上式可求得图中直线 P1P2 和 y 向网格线的交点， 但显示时要用舍入, 找到 最靠近交点处的象素点耒 表示。 当 △x<△y 时，让 y 递 增 1，x作相应变化。
2.1.1 直线的扫描转换——中点画线算法
在d≥0时，取正右方像素点P1，则下一个中点M 坐标：M1(xp+2,yp+0.5)，则下一个像素点的判 别式 d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a 故d的增量为a。
而若d<0，则取右上方像素点P2,则下一个中点M 坐标：M2(xp+2,yp+1.5)，则下一个像素点的判 别式
2.1.2 直线Bresenham算法( 续）
求误差的初值P1，可将x1、y1和b代入式(2.4)中的xi、 yi而得到 P1 = 2dydx 综述上面的推导，第1a象限内的直线Bresenham算法 思想如下： ⒈ 画点(x1, y1)，dx=x2x1，dy=y2y1，计算误差初值 P1=2dy dx，i=1； ⒉ 求直线的下一点位置 xi+1 = xi + 1 如果Pi>0，则yi+1=yi+1，否则yi+1=yi； ⒊ 画点(xi+1, yi+1)； ⒋ 求下一个误差Pi+1，如果Pi>0，则Pi+1=Pi+2dy2dx， 否则 Pi+1=Pi+2dy； ⒌ i=i+1；如果i<dx+1则转步骤2；否则结束操作。

x
d、区间填色：把这些相交区间内的 像素置成不同于背景色的填充色
当扫描线与多边形顶点相交时，交点的取舍问题（交点的个数 应保证为偶数个）
y 12 11 10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 101112 x
解决方案：
y
（1）若共享顶点的两条边分别落
12 11
x
算法的核心是按X递增顺序
排列交点的X坐标序列。由 y P7
此，可得到X-扫描线算法步
12 11
骤如下：
10 9
P6
P5
8
（3）对一条扫描线填充的过
7 6
P1
P3
5
程可分为四个步骤：
4 3
2
a、求交：计算扫描线与多边
1
1 2P23 4 5 6 7 8P4 9 101112 x
形各边的交点
b、排序：把所有交点按递增 顺序进行排序
任意两顶点间的连线均在多边形内
（2）凹多边形 任意两顶点间的连线有不在在多边形内
（3）含内环的多边形 多边形内包含多边形
现在的问题是，知道多边形的边界，如何找到多边形内部 的点，即把多边形内部填上颜色
P2
P3
P4
P1 P6
P5
顶点表示
点阵表示
1、X-扫描线算法
X-扫描线算法填充多边形的基本思想是按扫描线顺序，计算 扫描线与多边形的相交区间，再用要求的颜色显示这些区间 的像素，即完成填充工作
区间的端点可以通过计算扫 描线与多边形边界线的交点 获得
扫描线
交点 交点
交点
交点
如扫描线y=3与多边形的边界相 y
交于4点：
11

由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。
中点画线法
void Midpoint Line (int x0,int y0,int x1, int y1,int color) { int a, b, d1, d2, d, x, y;
a=y0-y1, b=x1-x0, d=2*a+b; d1=2*a, d2=2* (a+b); x=x0, y=y0; drawpixel(x, y, color); while (x<x1) { if (d<0) {x++; y++; d+=d2; } else {x++; d+=d1;} drawpixel (x, y, color); } /* while */ } /* mid PointLine */
= kxi+b+kx = yi+kx 当x =1; yi+1 = yi+k
• 即：当x每递增1，y递增k(即直线斜率)； • 注意上述分析的算法仅适用于k ≤1的情形。
在这种情况下，x每增加1,y最多增加1。 • 当 k 1时，必须把x，y地位互换
数值微分(DDA)法
• 增量算法：在一个迭代算法中，如果每一 步的x、y值是用前一步的值加上一个增量 来获得，则称为增量算法。
部分重要概念
光栅化（扫描转化）
确定最佳逼近图形的像素集合，并用指定属性 写像素的过程称为图形的扫描转化或光栅化。
区域充填
确定二维图形内部区域对应的像素集，并用 指定的属性或图案进行显示的过程。
部分重要概念
裁剪
确定一个图形的哪些部分在窗口内，必须显示；哪 些部分落在窗口之外，不该显示的过程称为裁剪。