第3章基本光栅图形生成技术..doc

第3章 基本光栅图形生成技术 显示器由离散的发光点组成，称为像素（光栅）。图形是由方程表示的连续图像，在输出图形前，需要进行光栅化，计算逼近图形的像素。这是将连续量转化为离散量的过程，图形转化为图像的过程（即渲染）。 内容： 直线光栅化：DDA算法；Bresenham算法 园光栅化：中点画园法 多边形光栅化：区域填充算法 裁剪算法 要求掌握这些算法的目的、思路、过程，能够进行手工计算、进行编程 3.1 线的生成算法 3.1.1 直线的生成算法 1 数值微分(DDA)法 已知：线段(x0,y0), (x1,y1)，斜率|k|1,x,y为整数 求：与线段接近的像素 直线方程 y=kx+b 画线过程从x的左端点x0开始，向x右端点步进，步长=1(个像素)，计算相应的y坐标。 计算 yi+1= kxi+1+b = k(xi+1)+b = kxi+k +b = yi+k yi+1 = yi+k 此时y不是整数，用四舍五入取整，int(yi+1+0.5) 例：模拟线段(0,0),(5,2)的计算过程 k = 2/5 = 0.4 x y int(y+0.5) ----------------------------------------------------------------- 0 0 0 1 0.4 0 2 0.8 1 3 1.2 1 4 1.6 2 5 2 2 练习：模拟线段(-2,0),(5,6)的计算过程 DDA算法每一步要进行四舍五入后取整，不利于硬件实现，效率不够高。 斜率问题：当斜率不满足|k|1时，上面的计算不充分。 方法1：根据斜率情况使用不同公式 当Δx0, |Δx||Δy|, xi+1 = xi +1; yi+1 = yi + k 当Δy0, |Δx||Δy|, yi+1 = yi +1; xi+1 = xi + 1/k 当Δx0, |Δx||Δy|, xi+1 = xi - 1; yi+1 = yi – k 当Δy0, |Δx||Δy|, yi+1 = yi - 1; xi+1 = xi - 1/k 方法2：调节x的步长，自动适应，读31页代码 2 Bresenham算法 Bresenham算法增加了一个判别参数，实现了全整数计算，每步计算只包括一个正负判别和一个整数加法，适合硬件实现。 已知：线段(x0,y0), (x1,y1)，斜率0k1, x,y为整数 y = kx+b Δx = x1-x0 Δy = y1-y0 k = Δy/Δx 思路：x从x0开始，每次给予增量1，计算对应的y。 事实上，y只有2个选择，即yi或yi+1，可以寻找一个判断方法，而不按方程进行计算。 （1）误差计算 可以作为选择y的判别量，但式子还复杂。 乘Δx，并代入kΔx=Δy 则ei的计算仅包括整数运算，其符号与(d1-d2)的符号相同。 当ei0时，直线上理想位置与像素(xi＋1，yi)更接近，应取yi； 当ei0时，像素(xi＋1，yi＋1)与直线上理想位置更接近，应取yi+1； 当ei=0时，两个像素与直线上理想位置一样接近，可约定取(xi＋1，yi＋1)。 特别地，代入xi=x0，yi=y0，b=y0-Δy/Δx*x0，则e0 =2Δy-Δx e0= 2Δy*x0 - 2Δx*y0 + [2Δy+Δx*(2b-1)] = 2Δy*x0 - 2Δx*y0 + 2Δy+Δx*(2 y0-Δy/Δx*x0-1) = 2Δy*x0 - 2Δx*y0 + 2Δy+2Δx*y0-2Δy *x0 –Δx ei的几何意义：ei是使用xi点信息计算的量，用于判断xi+1点上y的选取。 （2）ei的递推 代入x的增量为1，则 如果选择右上方像素，即：，则： 如果选择右方像素，即：，则： （3）计算过程 1 计算Δx、Δy等常数 计算e0 绘制点(x0,y0) 2 设xi点的计算、绘制已经完成，xi、yi、ei为已知，对i+1点 若ei =0 ， 若ei 0 ， 3 循环2 线段(0,0),(5,2) Δy=2，Δx=5，2Δy-2Δx= -6，2Δy=4 , e0 = 2Δy-Δx = -1 x y e ------------------