Bresenham画线算法(Three.js实现)

àì夳堔傛蜴生んèń 2022-05-11 12:16 237阅读 0赞

**Bresenham算法是一种精确而有效的光栅线生成算法，该算法仅仅使用增量计算。**

**为了说明该算法，我们先考虑斜率小于1的直线的绘制过程。沿线路径的像素为止由以单位x间隔的取样来确定。从给定线段的左端点 ( x 0 , y 0 ) (x\_0,y\_0) (x0,y0)开始，逐步处理每个后继列（ x x x位置），并在其扫描线y值最接近线段的像素上绘出一点。**

**假如已经决定要显示的像素在 ( x k , y k ) (x\_k,y\_k) (xk,yk)，那么下一步需要确定在列 x k + 1 = x k + 1 x\_\{k+1\}=x\_k+1 xk\+1=xk\+1上绘制哪个像素，是位置 ( x k + 1 , y k ) (x\_k+1,y\_k) (xk\+1,yk)还是 ( x k + 1 , y k + 1 ) (x\_k+1, y\_k+1) (xk\+1,yk\+1)。**

为了确定下一个点的位置，我们需要分别计算出 y k y\_k yk， y k + 1 y\_\{k+1\} yk\+1与y（就是 x k + 1 x\_k+1 xk\+1对应的y值）的距离。我们分别使用 d l o w e r d\_\{lower\} dlower和 d u p p e r d\_\{upper\} dupper  
来表示这两个距离。

**在 x k + 1 x\_k+1 xk\+1处y的坐标可计算为：**  
 y = m ( x k + 1 ) + b y=m(x\_k+1)+b y=m(xk\+1)\+b

所以 d l o w e r = d\_\{lower\}= dlower=  
 y − y k = m ( x + k + 1 ) + b − y k y-y\_k =m(x+k+1)+b-y\_k y−yk=m(x\+k\+1)\+b−yk  
且 d u p p e r = d\_\{upper\}= dupper=  
 ( y + k + 1 ) − y = y k + 1 − m ( x k + 1 ) − b (y+k+1)-y =y\_k+1-m(x\_k+1)-b (y\+k\+1)−y=yk\+1−m(xk\+1)−b

**若要确定两个像素哪一个离直线更近，我们需要测试 d l o w e r d\_lower dlower与 d u p p e r d\_upper dupper的差：**

d l o w e r − d u p p e r = ( y k + 1 ) − y = y k + 1 − m ( x k + 1 ) − b d\_\{lower\}-d\_\{upper\}=(y\_k+1)-y=y\_k+1-m(x\_k+1)-b dlower−dupper=(yk\+1)−y=yk\+1−m(xk\+1)−b

**设线的两端点的竖直和水平偏移量分别为 Δ y Δy Δy和 Δ x Δx Δx，将上面的距离差两边同时乘于 Δ x Δx Δx，我们便可以得到画线算法第k步的决策参数p**

p k = Δ x ( d l o w e r − d u p p e r ) = 2 Δ y ⋅ Δ x − 2 Δ x ⋅ y k + c p\_k=Δx(d\_\{lower\}-d\_\{upper\})=2Δy·Δx-2Δx·y\_k+c pk=Δx(dlower−dupper)=2Δy⋅Δx−2Δx⋅yk\+c

经过推导后：  
 p k + 1 = p k + 2 Δ y − 2 Δ x ( y k + 1 − y k ) p\_\{k+1\}=p\_k+2Δy-2Δx(y\_\{k+1\}-y\_k) pk\+1=pk\+2Δy−2Δx(yk\+1−yk)  
且  
 p 0 = 2 Δ y − Δ x p\_0=2Δy-Δx p0=2Δy−Δx

总结：

1.  输入线段两个端点，并将左端点存储在 ( x 0 , y 0 ) (x\_0,y\_0) (x0,y0)中。
2.  将左端点画出
3.  计算常量 Δ x Δx Δx、 Δ y Δy Δy和 2 Δ y − 2 Δ x 2Δy-2Δx 2Δy−2Δx，并得到决策参数的第一个值 p 0 p\_0 p0  
     p 0 = 2 Δ y − Δ x p\_0=2Δy-Δx p0=2Δy−Δx
4.  从k=0开始，在沿线段路径的每个x处，进行如下检测  
    如果 p k < 0 p\_k<0 pk<0，下一个要绘制的点是 ( x k + 1 , y k ) (x\_k+1,y\_k) (xk\+1,yk)，并且  
     p k + 1 = p k + 2 Δ y p\_\{k+1\}=p\_k+2Δy pk\+1=pk\+2Δy  
    否则，下一个要绘制的点是 ( x k + 1 , y k + 1 ) (x\_k+1,y\_k+1) (xk\+1,yk\+1)，并且  
     p k + 1 = p k + 2 Δ y − 2 Δ x p\_\{k+1\}=p\_k+2Δy-2Δx pk\+1=pk\+2Δy−2Δx
5.  重复步骤4，共 Δ x − 1 Δx-1 Δx−1次。

**最终实现结果：**  
![在这里插入图片描述][70]

截图中效果实现代码放在[Github][]

[70]: /images/20220505/3c823e0f83004c3e9e39ff42f263ec20.png
[Github]: https://github.com/Meskjei/Bresenham