计算机图形学基础课件chap5

计算机图形学基础课件

第五章 基本图形生成算法 如何在指定的输出设备上根据坐标描述构造基 本二维几何图形(点、直线、圆、椭圆、多边 形域、字符串及其相关属性等)。

计算机图形学基础课件

第五章 基本图形生成算法 图形生成的概念 直线段的扫描转换 圆的扫描转换 多边形的扫描转换与区域填充 属性处理

反走样技术 在OpenGL中绘制图形2

计算机图形学基础课件

图形生成的概念 图形的生成：是在指定的

输出设备上，根据坐标描述构造二维几何图形。

图形的扫描转换：在光栅显示器等数字设备上确定图5.1 用象素点集逼近直线

一个最佳逼近于图形的象素集的过程。3

计算机图形学基础课件

5.1 直线的扫描转换 直线的绘制要求(1)直线要直； (2)直线的端点要准确，无定向性无断裂； (3)直线的亮度、色泽要均匀； (4)画线的速度要快； (5)具有不同的色泽、亮度、线型等。

计算机图形学基础课件

直线的扫描转换 解 决 的 问 题 ： 给 定 直 线 两 端 点 P0(x0,y0) 和P1(x1,y1),画出该直线。

数值微分法 中点Bresenhan算法

改进的Bresenhan算法

计算机图形学基础课件

数值微分法(DDA法)直线的微分方程：

dy Δy y1 y 0 k dx Δx x1 x 0

y

yi+1 ε△y yi xi ε△x xi+1 x

xi 1 xi x yi 1 yi yε=1/max(|△x|,|△y|)

图5.2 DDA算法原理

计算机图形学基础课件

max(|△x|,|△y|)=|△x|,即|k|≤1的情况：1 xi 1 xi x xi x xi 1 x 1 yi 1 yi y yi y y i k x

max(|△x|,|△y|)=|△y|,此时|k|≥1:1 1 xi 1 xi x xi x xi y k 1 yi 1 yi y yi y y i 1 y

计算机图形学基础课件

数值微分法(DDA法)——特点 增量算法 直观、易实现 不利于用硬件实现

计算机图形学基础课件

中点Bresenham算法 直线的方程

y y1 y0 F ( x, y ) y kx b 0 , 其中k x x1 x0y F(x,y)=0 F(x,y)>0 x F(x,y)<0 F(x,y)=0 F(x,y)>0 y

F(x,y)<0

x

图5.3 直线将平面分为三个区域9

计算机图形学基础课件

中点Bresenham算法 算法原理：根据直线的斜率确定或选择变量在 x或y方向上每次递增一个单位，而另一方向的 增量为1或0,它取决于实际直线与相邻象素

点的距离，这一距离称为误差项。

计算机图形学基础课件

假定0≤k≤1, 即0≤ Δy/Δ x ≤1,x是最大位移方向

Pu(xi+1,yi+1) Q M(xi+1,yi+1/2) P(xi,yi) Pd(xi+1,yi)

图5.4 Brensemham算法生成直线的原理

计算机图形学基础课件

判别式：

d F ( xM , yM ) F ( xi 1, yi 0.5) yi 0.5 k ( xi 1) b则有：

xi 1 xi 1 yi 1 yi 1 y i

(d 0) (d 0)P(xi,yi)

Pu(xi+1,yi+1) Q M(xi+1,yi+1/2) Pd(xi+1,yi)

图5.5 Brensemham算法生成直线的原理

计算机图形学基础课件

d的意义：

d F ( xM , yM ) F ( xi 1, yi

0.5) yi 0.5 k ( xi 1) b

d F ( xM , yM ) F ( xQ , yQ ) yM kxM b ( yQ kxQ b) yM yQ

d 0 d 0 d 0

yM yQ yM yQ yM yQP(xi,yi)

Pu(xi+1,yi+1) Q M(xi+1,yi+1/2) Pd(xi+1,yi)

图5.6 Brensemham算法生成直线的原理

计算机图形学基础课件

误差项的递推(d<0)

d1 F ( xi 1, yi 0.5) yi 0.5 k ( xi 1) bd 2 F ( xi 2, yi 1.5) yi 1.5 k ( xi 2) b

(x i+2,yi+1.5) (xi+1,yi+0.5) (xi,yi) d<0图5.7 误差项递推

d 2 yi 0.5 k ( xi 1) b 1 k d1 1 k

计算机图形学基础课件

误差项的递推(d≥0)

d1 F ( xi 1, yi 0.5)

(x i+2,yi+0.5) yi 0.5 k ( xi 1) b (xi+1,yi+0.5) (xi,yi) d>=0图5.8 误差项递推

d 2 F ( xi 2, yi 0.5) yi 0.5 k ( xi 2) b d1 k d 2 yi 0.5 k ( xi 1) b k

计算机图形学基础课件

中点Bresenham算法初始值d的计算

d 0 F ( x0 1, y0 0.5) y0 0.5 k ( x0 1) b y0 k x0 b k 0.5 0 .5 k(x0+1,y0+0.5) (x0,y0)图5.9 计算初值