计算机系统应用教程网站

网站首页 > 技术文章 正文

Bresenham画线算法及实践 bresenham画线算法例题详解

btikc 2024-10-31 12:29:17 技术文章 8 ℃ 0 评论

根据直线的一般表示形式y=mx+b我们可以很容易得出经过两点p0(x0,y0)、p1(x1,y1)的直接方程为

稍作变换表示成函数的形式如下

显示屏幕是由如下图所示一个个微小的像素组成的，屏幕坐标是离散的，绘制一条线段实际上就是设置一系列像素的颜色来近似模拟一条直线，Bresenham方式是一种采用中点算法来实现直线绘制的方法。

这里以直线斜率在(0,1]区间的情况为例来介绍Bresenham算法的核心内容，斜率在此区间内x轴的增长要快于y轴的增长，因此我们直接遍历x0~x1之间的像素（像素坐标都是整数），关键步骤就是确定x对应的y轴像素值。

假如已经绘制了像素(x,y)，下一步就是确定是绘制(x+1,y+1)还是(x+1,y)，Bresenham算法采用计算直线方程的函数形式的值f(x+1, y+0.5)，也就是y+1和y的中点来进行判别。

  • 如果f(x+1, y+0.5)>0说明直线在y+1和y中点的下方，此时绘制(x+1,y)比较合理；
  • 如果f(x+1, y+0.5)<0说明直线在y+1和y中点的上方，此时绘制(x+1,y+1)比较合理；
  • 如果f(x+1, y+0.5)=0说明直线刚好穿过y+1和y中点，此时绘制那一个都是可以的；
    表示为伪代码的形式为：
y = y0
for x = x0 to x1 do
	draw(x,y)
	if f(x+1, y+0.5) < 0 then
		y = y + 1


其他斜率曲线的判断方法是类似的，需注意的是如果y的变化快于x的变化，需要遍历y0到y1，通过中点算法来确定x的值。另外需要特别注意的就是直接方程f(x,y)的值大于0还是小于0的判断要仔细判别，这里判断方法并不是复杂，只是比较容易混淆。

x、y象限内直线斜率可以换分为(-∞,-1]、(-1,0]、(0,1]、(1,+∞)四个区间，见下图。

最后，我们用html的canvas元素来演示Bresenham画线算法，理解了该算法的原理，代码也就顺理成章了。示例绘制了四个斜率的线段，效果如下，可以看到某些斜率下的锯齿效果还是非常明显的，后续会继续介绍如何利用抗锯齿算法来生成更平滑的直线。


注：canvas的y轴正向是向下的。
index.html

<!DOCTYPE html>

<html lang="en">

<head>

    <meta charset="UTF-8">

    <meta http-equiv="X-UA-Compatible" content="IE=edge">

    <meta name="viewport" content="width=device-width, initial-scale=1.0">

    <title>Bresenham画线算法示例</title>

</head>

<body>

    <canvas id="canvas" width="780" height="780"></canvas>

    <script src="./bresenham.js"></script>

</body>

</html>

bresenham.js

var canvas = document.getElementById("canvas");

var ctx = canvas.getContext("2d");

  

function setPixel(x, y, color='rgba(255, 255, 255, 1.0)') {

    ctx.fillStyle = color;

    ctx.fillRect(x, y, 1, 1);

}

  

function  drawLine(p0, p1, color='rgba(255, 255, 255, 1.0)') {

    let x0, y0, x1, y1;

    // 保持x1>=x0

    if (p0.x > p1.x) {

        [x0, y0] = [Math.round(p1.x), Math.round(p1.y)];

        [x1, y1] = [Math.round(p0.x), Math.round(p0.y)];

    } else {

        [x0, y0] = [Math.round(p0.x), Math.round(p0.y)];

        [x1, y1] = [Math.round(p1.x), Math.round(p1.y)];

    }

    let m = (y1-y0)/(x1-x0);

    // 直线方程

    let f = (x,y) => (y0-y1)*x + (x1-x0)*y + x0*y1 - x1*y0;

    // 区间(0,1]

    if (m > 0 && m <= 1) {

        let y = y0;

        for (let x = x0; x < x1; x++) {

            this.setPixel(x, y, color);

            if (f(x+1, y+0.5) < 0) {

                y += 1;

            }

        }

    }

    // 区间(1,正无穷)

    else if (m > 1) {

        let x = x0;

        for (let y = y0; y < y1; y++) {

            this.setPixel(x, y, color);

            if (f(x+0.5, y+1) > 0) {

                x += 1;

            }

        }

    }

    // 区间(-1,0]

    else if (m > -1 && m <= 0) {

        let y = y0;

        for (let x = x0; x < x1; x++) {

            this.setPixel(x, y, color);

            if (f(x+1, y-0.5) > 0) {

                y -= 1;

            }

        }

    }

    // 区间(负无穷,-1]

    else if (m <= -1) {

        let x = x0;

        for (let y = y0; y > y1; y--) {

            this.setPixel(x, y, color);

            if (f(x+0.5, y-1) < 0) {

                x += 1;

            }

        }

    }

}

// (1,+∞)

drawLine({x: 300, y: 590}, {x: 480, y: 190}, 'rgba(255, 0, 0, 1.0)');  

// (-1,0]

drawLine({x: 300, y: 400}, {x: 480, y: 380}, 'rgba(255, 255, 0, 1.0)');

// (0,1]

drawLine({x: 300, y: 380}, {x: 480, y: 400}, 'rgba(0, 0, 255, 1.0)');  

// (-∞,-1]

drawLine({x: 300, y: 190}, {x: 480, y: 590}, 'rgba(0, 255, 0, 1.0)');

参考文献

[1]. 《fundamentals of computer graphics》9.1.1 line drawing, p179.

Tags：

猜你喜欢

本文暂时没有评论，来添加一个吧(●'◡'●)

欢迎 你 发表评论:

最近发表
标签列表