计算机图形学-生成直线和圆弧

计算机图形学

计算机图形学

第2章 生成直线和圆弧的算法坐标系统 画线算法 帧缓存值的装载 圆生成算法

计算机图形学

坐标系统视频显示器上的位置使用与帧缓存中的像素位置相 对应的整数屏幕坐标进行描述。7 6 5 4 3 2 1 0

0

1

2

3

4

5

6

7

计算机图形学

画线算法在光栅系统中，通过 像素绘制直线，水平 垂直方向的步长受到 像素的间距的限制 在离散位置上对直线 取样，并且在每个取 样位置上确定直线最 近的像素

yend

y0

x0

xend

计算机图形学

DDA算法(数值微分法)直线方程表示如下：

y m x b确定线段的端点后，可以计算出斜率m和截距b的值：

yend y0 m xend x0

b y0 mx0

对于任何沿直线给定的x增量Δ x可以计算出y方向的增量：

y m x5

计算机图形学

DDA算法(数值微分法)当斜率为正，且小于等于1,则以单位x间隔取样，逐个 计算y值为：

yk 1 yk m当斜率大于1时，交换x、y的位置：

1 xk 1 xk m6

计算机图形学

DDA算法(数值微分法)输入线段两个端点的像素位置，端点位置 间的水平和垂直差值赋给参数dx和dy 绝对值大的参数确定参数steps的值 从像素位置(x0,y0)开始，确定沿线段生 成下一个像素位置的每一步所需的偏移量， 并循环steps次。

计算机图形学

DDA算法(数值微分法)例：画直线段p(0,0)--P1(5,2)x 0 1 2 3 4 5 int(y+0.5) 0 0 1 1 2 2 y+0.5 0 0.4+0.5 0.8+0.5 1.2+0.5 1.6+0.5 2.0+0.5Line: P0(0, 0)-- P1(5, 2) 2 1 0 0 1 2 3 4 5

注：网格点表示像素

计算机图形学

DDA算法(数值微分法)DDA算法计算像素要比直接使用直线方程 计算的速度快。它利用了光栅特性消除了 直线方程中的乘法，而在x或y方向使用合 适的增量，从而沿路径逐步得到各像素的 位置 但是在连续迭代过程中，会产生误差的累 积，并且取整操作和浮点运算仍然非常耗 时9

计算机图形学

DDA算法实现#include<stdlib.h> #include<math.h> inline int round (const float a) {return int (a+0.5)} void lineDDA (int x0, int y0, int xEnd, int yEnd) { int dx = xEnd – x0, dy = yEnd – y0, steps, k; float xIncrement, yIncrement, x = x0, y = y0;

计算机图形学

DDA算法实现if (fabs (dx) > fabs (dy)) steps = fabs (dx); else steps = fabs (dy); xIncrement = float (dx) / float (steps); yIncrement = float (dy) / float (steps);

setpixel (round (x) , round (y));

计算机图形学

DDA算法实现for (k = 0; k < steps; k++){ x += xIncrement; y += yIncrement; setPixel ( round (x), round (y)); } }

计算机图形学

Bresenham画线算法需要确定下一步是点(11,10)还是(11,11)

12 11 10 10 11 12 13 1413

计算机图形学

Bresenham画线算法首先考虑斜率小于1的直线的扫描转换过程， 沿线路径的像素位置由以单位x间隔的取样 来确定。 从(x0,y0)开始，逐步处理 假设已经决定要显示在(xk,yk)那么下一 步需要确定在(xk+1,yk)还是在位置 (xk+1,yk+1)

计算机图形学

Bresenham画线算法

yk 1

y

yk

d

upper

dlower

xk 115

计算机图形学

Bresenham画线算法|m|<1输入线段的两个端点，将左端点存储在(x0,y0)中 将(x0,y0)装入帧缓存，画出第一个点 计算常量Δ x、Δ y、2Δ y和2Δ y-2Δ x,并得到决策参数 的第一个值： p0=2Δ y-Δ x 从k=0开始，在沿路径的每个xk处，进行下列检测： 如果pk<0,下一个要绘制的点是(xk+1,yk),且 pk+1=pk+2Δ y 如果pk>0,下一个要绘制的点是(xk+1,yk+1),且 pk+1=pk+2Δ y-2Δ x 重复步骤4,共Δ x-1次16