【计算机图形学】画线算法——Bresenham算法(任意斜率)二、C语言实现

89 阅读 0 评论 59 点赞

我是靠谱客的博主满意火龙果，最近开发中收集的这篇文章主要介绍【计算机图形学】画线算法——Bresenham算法(任意斜率)二、C语言实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、Bresenham算法原理

二、C语言实现

一、Bresenham算法原理

由Bresenham提出的一种精确而有效的光栅线生成算法，可用于显示线、圆和其他曲线的整数增量运算。它是目前最有效的线段生成算法。

推导：

设线段端点：(,),(,),∆x和∆y为水平和垂直偏移量,m为斜率

当|m| <= 1时,对于给定的x增量∆x

当|m| >= 1时,对于给定的y增量∆y，

（当 0<m < 1）

假设已经确定了要显示的像素，那么，需要确定下一点是绘制在，

还是。

根据直线的方程，直线上处的y坐标为：

将m带入d1 – d2中，并变换得：

其中，为算法中第k步的决策参数，c为一常量，其值为。

那么：

若，即,有

若, 即,有

同理，可求得第k+1步的决策参数

因此，有如下递推关系：

因为0<m<1 因此，带入上式得：

 

其中，的值取决于的值：

当时，，

Bresenham算法描述 (0 < m < 1)

算法从线段的起始端点开始，反复计算每个点的决策参数并绘制像素。

起始端点处的决策参数为：

算法：

1、输入线段的两个端点，并将左端点存储在中；

2、将装入帧缓冲器，画出第一个点；

3、计算常量∆x，∆y，2∆y 和2∆y – 2∆x，并得到决策参数的第一个值：

4、从k = 0开始，在沿线的每个处，进行下列检测：

若，下一个待画点是，且

5、重复步骤4，共∆x次。

二、C语言实现

//Modified form https://rosettacode.org/wiki/Bitmap/Bresenhanm%27s_line_algorithm#c
void bresenham(int x0, int y0, int x1, int y1){
int dx = abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
int dy = abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
int erro = (dx > dy ? dx : -dy) / 2;
while(putpixel(x0,y0), x0 != x1 || y0 != y1){
int e2 = erro;
if(e2 > -dx) { erro -= dy; x0 += sx;}
if(e2 <
dy) { erro += dx; y0 += sy;}
}
}

main方法

int main() {
initgraph(640, 480);
setbkcolor(0xC1CDC1);
cleardevice();
bresenham(320, 240, 0, 0, BLACK);
bresenham(320, 240, 160, 0, BLUE);
bresenham(320, 240, 320,0,GREEN);
bresenham(320, 240, 480,0, CYAN);
bresenham(320, 240, 640, 0, RED);
bresenham(320, 240, 640, 120, MAGENTA);
bresenham(320, 240, 640, 240, BROWN);
bresenham(320, 240, 640, 360, LIGHTGRAY);
bresenham(320, 240, 640, 480, DARKGRAY);
bresenham(320, 240, 480, 480, LIGHTBLUE);
bresenham(320, 240, 320, 480, LIGHTGREEN);
bresenham(320, 240, 160, 480, LIGHTCYAN);
bresenham(320, 240, 0, 480, LIGHTMAGENTA);
bresenham(320, 240, 0, 360, YELLOW);
bresenham(320, 240, 0, 240, BROWN);
bresenham(320, 240, 0, 120, WHITE);
_getch();
return 0;
}

结果：