【计算机图形学】壹 · 光栅图形学之直线段的扫描转换算法

冷不防 2023-07-18 03:13 5阅读 0赞

有两点 P 0 ( x 0 , y 0 ) , P 1 ( x 1 , y 1 ) P\_\{0\}(x\_\{0\},~y\_\{0\}),~P\_\{1\}(x\_\{1\},~y\_\{1\}) P0(x0,y0),P1(x1,y1)确定一条线段 L ( P 0 , P 1 ) L(P\_0,~P\_1) L(P0,P1)，设线段所在直线方程为 y = k x + b y=kx+b y=kx\+b其中斜率 k = ( y 1 − y 0 ) / ( x 1 − x 0 ) k=(y\_1-y\_0)/(x\_1-x\_0) k=(y1−y0)/(x1−x0)，截距 b = y 0 − k x 0 b=y\_0-kx\_0 b=y0−kx0。

注：以下算法中 ∣ k ∣ ≤ 1 |k| \\leq 1 ∣k∣≤1，对于 ∣ k ∣ > 1 |k| > 1 ∣k∣>1的情况可同理推导得出。

> # 1 直线方程法 #

### 1.1 基本思想： ###

根据直线的表达式确定线段路径上点的像素位置。

### 1.2 算法描述 ###

1.  **取 x x x坐标**：将区间 \[ x 0 , x 1 \] \[x\_0,~x\_1\] \[x0,x1\]均分，每段长 d d d，假设端点为 t i = x 0 + i ∗ d t\_i=x\_0+i\*d ti=x0\+i∗d， t 0 = x 0 , t n = x 1 t\_0=x\_0, t\_n=x\_1 t0=x0,tn=x1.（注： t i t\_i ti要为整数）
2.  **计算 y y y坐标**： y i = k t i + b y\_i=kt\_i+b yi=kti\+b
3.  **取整**：因为像素坐标都是整数，所以取整： y i ′ = ( i n t ) ( y i + 0.5 ) y\_\{i\}^\{'\}=(int)(y\_i+0.5) yi′=(int)(yi\+0.5)

### 1.3 算法评价 ###

*  主要运算：乘法+加法+浮点数运算（取整）
 *  计算量大，这种方法一般不使用。

> # 2 数值微分法（DDA算法） #

### 2.1 基本思想 ###

从 x x x的左端点 x 0 x\_0 x0开始，向x右端点步进，步长为1（像素），按 y = k x + b y=kx+b y=kx\+b计算相应的 y y y坐标，并取像素点 ( x , r o u n d ( y ) ) (x,~round(y)) (x,round(y))作为当前点的坐标。

### 2.2 算法描述 ###

设 x x x步长为 Δ x \\Delta x Δx，则 x i + 1 = x i + Δ x x\_\{i+1\}=x\_i+\\Delta x xi\+1=xi\+Δx，于是： y i + 1 = k x i + 1 + b = k x i + k Δ x + b = y i + k Δ x y\_\{i+1\}=kx\_\{i+1\}+b\\\\~~~~~~~~~~~~~~~~~=kx\_\{i\}+k\\Delta x+b\\\\~~~~~~~=y\_i+k\\Delta x yi\+1=kxi\+1\+b=kxi\+kΔx\+b=yi\+kΔx  
 Δ x = 1 \\Delta x=1 Δx=1时， y i + 1 = y i + k y\_\{i+1\}=y\_i+k yi\+1=yi\+k.

1.  起始点 ( x 0 , y 0 ) (x\_0,~y\_0) (x0,y0)；
2.  计算下一个点 ( x i + 1 , y i + 1 ) = ( x i + 1 , r o u n d ( y i + k ) ) (x\_\{i+1\},~y\_\{i+1\})=(x\_i+1,~round(y\_i+k)) (xi\+1,yi\+1)=(xi\+1,round(yi\+k))
3.  循环执行步骤2，直至 x i = x 1 x\_i=x\_1 xi=x1，结束。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70]

其中， r o u n d ( y i + k ) = ( i n t ) ( y i + k + 0.5 ) round(y\_i+k)=(int)(y\_i+k+0.5) round(yi\+k)=(int)(yi\+k\+0.5).  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70 1]

### 2.3 算法评价 ###

*  如博文开篇所述，上述算法仅仅适用于 ∣ k ∣ ≤ 1 |k| \\leq 1 ∣k∣≤1的情况，在这种情况下， x x x每增加1， y y y最多增加1。对于 ∣ k ∣ > 1 |k|>1 ∣k∣>1的情况，必须把 x x x和 y y y的地位互换， x x x随着 y y y的变化而变化， y y y每增加1， x x x相应增加 1 / k 1/k 1/k。
 *  主要运算：加法+浮点数运算（取整），仍有浮点数运算，不利于硬件实现。

> # 3 中点画线法 #

依旧分析 ∣ k ∣ ≤ 1 |k| \\leq 1 ∣k∣≤1的情况。

### 3.1 基本思想 ###

根据上文，我们可以知道，当 x i + 1 = x i + 1 x\_\{i+1\}=x\_i+1 xi\+1=xi\+1， y i + 1 y\_\{i+1\} yi\+1经过四舍五入之后只有两种情况：

1.   y p + 1 = r o u n d ( y i + 1 ) < y p + 0.5 ⇒ y p + 1 = y p y\_\{p+1\}=round(y\_\{i+1\})<y\_\{p\}+0.5~~\\Rightarrow ~~y\_\{p+1\}=y\_\{p\} yp\+1=round(yi\+1)<yp\+0.5⇒yp\+1=yp
2.   y p + 1 = r o u n d ( y i + 1 ) ≥ y p + 0.5 ⇒ y p + 1 = y p + 1 y\_\{p+1\}=round(y\_\{i+1\})\\geq y\_\{p\}+0.5~~\\Rightarrow ~~y\_\{p+1\}=y\_\{p\}+1 yp\+1=round(yi\+1)≥yp\+0.5⇒yp\+1=yp\+1

（假设第 i i i个像素点为 ( x p , y p ) (x\_p,~y\_p) (xp,yp)，则它的下一个像素点为 ( x p + 1 , y p + 1 ) (x\_\{p+1\},~y\_\{p+1\}) (xp\+1,yp\+1)，注意区分 y i y\_i yi和 y p y\_p yp）  
可以发现，下一个像素点 y p + 1 y\_\{p+1\} yp\+1的取值，与 y p y\_\{p\} yp和 y p + 1 y\_\{p\}+1 yp\+1的中点（ y p + 0.5 y\_p+0.5 yp\+0.5）有很大的关系，所以我们可以直接用这个中点去判断 y p + 1 y\_\{p+1\} yp\+1的取值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_10_color_FFFFFF_t_70]  
如图所示，假设 A A A点为当前像素点，而且已确定，接下来的像素点确定如下：

*  下一个像素点 B B B，在 B 1 B\_1 B1和 B 2 B\_2 B2之间选择，由于 B 中 B\_中 B中在直线下方，所以直线更靠近 B 2 B\_2 B2点，则下一个像素点 ( x p + 1 , y p + 1 ) (x\_\{p+1\},~y\_\{p+1\}) (xp\+1,yp\+1)选择 B 2 B\_2 B2。
 *  下一个像素点 C C C，在 C 1 C\_1 C1和 C 2 C\_2 C2之间选择，由于 C 中 C\_中 C中在直线上方，所以直线更靠近 C 1 C\_1 C1点，则下一个像素点 ( x p + 2 , y p + 2 ) (x\_\{p+2\},~y\_\{p+2\}) (xp\+2,yp\+2)选择 C 1 C\_1 C1。
 *  下一个像素点 D D D，在 D 1 D\_1 D1和 D 2 D\_2 D2之间选择，由于 D 中 D\_中 D中刚好在直线上，所以直线距离 D 1 D\_1 D1和 D 2 D\_2 D2同样远，则下一个像素点 ( x p + 3 , y p + 3 ) (x\_\{p+3\},~y\_\{p+3\}) (xp\+3,yp\+3)可以选择任一点。（一般提前统一好，选择任一点都可以）

### 3.2 算法描述 ###

设函数 F ( x , y ) = y − k x − b F(x,y)=y-kx-b F(x,y)=y−kx−b，则： d = F ( x M , y M ) = F ( x p + 1 , y p + 0.5 ) = y p + 0.5 − k ( x p + 1 ) − b d=F(x\_M,y\_M)=F(x\_p+1,y\_p+0.5)=y\_p+0.5-k(x\_p+1)-b d=F(xM,yM)=F(xp\+1,yp\+0.5)=yp\+0.5−k(xp\+1)−b  
根据下述方法更新下一个像素点的相关值：

*   d p < 0 ⇒ 中 点 在 直 线 下 方 ⇒ x p + 1 = x p + 1 , y p + 1 = y p + 1 d\_p<0\\Rightarrow 中点在直线下方\\Rightarrow x\_\{p+1\}=x\_p+1,~y\_\{p+1\}=y\_\{p\}+1 dp<0⇒中点在直线下方⇒xp\+1=xp\+1,yp\+1=yp\+1，知道下一个像素点之后，可求 d p + 1 = F ( x p + 2 , y p + 1.5 ) = y p + 1.5 − k ( x p + 2 ) − b = \[ y p + 0.5 − k ( x p + 1 ) − b \] + 1 − k = d p + 1 − k d\_\{p+1\}=F(x\_p+2,y\_p+1.5)\\\\~~~~~~~~~~~~~~~~~=y\_p+1.5-k(x\_p+2)-b\\\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=\[y\_p+0.5-k(x\_p+1)-b\]+1-k\\\\=d\_p+1-k~~~~~~~~ dp\+1=F(xp\+2,yp\+1.5)=yp\+1.5−k(xp\+2)−b=\[yp\+0.5−k(xp\+1)−b\]\+1−k=dp\+1−k
 *   d > 0 ⇒ 中 点 在 直 线 上 方 ⇒ x p + 1 = x p + 1 , y p + 1 = y p d > 0\\Rightarrow 中点在直线上方\\Rightarrow x\_\{p+1\}=x\_p+1,~y\_\{p+1\}=y\_\{p\} d>0⇒中点在直线上方⇒xp\+1=xp\+1,yp\+1=yp，同理可推：  
     d p + 1 = d p − k d\_\{p+1\}=d\_p-k dp\+1=dp−k
 *   d = 0 d = 0 d=0同 d > 0 d > 0 d>0

1.  初始点 P 0 ( x 0 , y 0 ) ， P\_0(x\_0,y\_0)， P0(x0,y0)，计算 d 0 = F ( x 0 + 1 , y 0 + 0.5 ) = y 0 + 0.5 − k ( x 0 + 1 ) − b = 0.5 − k d\_0=F(x\_0+1,y\_0+0.5)=y\_0+0.5-k(x\_0+1)-b=0.5-k d0=F(x0\+1,y0\+0.5)=y0\+0.5−k(x0\+1)−b=0.5−k
2.  根据 \{ d p < 0 ⇒ x p + 1 = x p + 1 , y p + 1 = y p + 1 , d p + 1 = d + 1 − k d i ≥ 0 ⇒ x p + 1 = x p + 1 , y p + 1 = y p , d p + 1 = d − k \\left\\\{\\begin\{matrix\} d\_p<0 \\Rightarrow x\_\{p+1\}=x\_p+1,~y\_\{p+1\}=y\_\{p\}+1,d\_\{p+1\}=d+1-k\\\\d\_i \\geq 0\\Rightarrow x\_\{p+1\}=x\_p+1,~y\_\{p+1\}=y\_\{p\},~~~~~~d\_\{p+1\}=d-k~~~~~~~ \\end\{matrix\}\\right. \{ dp<0⇒xp\+1=xp\+1,yp\+1=yp\+1,dp\+1=d\+1−kdi≥0⇒xp\+1=xp\+1,yp\+1=yp,dp\+1=d−k  
    更新。
3.  循环步骤2，直至 x p = x 1 x\_p=x\_1 xp=x1，结束。

### 3.3 算法评价 ###

*  该算法只涉及加法。但在计算 d 0 d\_0 d0时，涉及到( 0.5 0.5 0.5)浮点数计算，可以将 2 d 2d 2d代替 d d d以消除浮点数计算。

### 3.4 算法实现 ###

[**C++实现代码（任意k值）**][C_k]

> # 4 Bresenham算法 #

### 4.1 基本思想 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70 2]  
如上图所示， x i + 1 = x i + 1 x\_\{i+1\}=x\_i+1 xi\+1=xi\+1， y i + 1 = y i + k y\_\{i+1\}=y\_i+k yi\+1=yi\+k，现在设一个误差项 d d d：

*   d 0 = 0 d\_0=0 d0=0
 *  如果只在 x x x方向上走一步： d i + 1 = d i + k d\_\{i+1\}=d\_i+k di\+1=di\+k
 *  一旦 y y y方向上走了一步， d i + 1 = d i + k − 1 d\_\{i+1\}=d\_\{i\}+k-1 di\+1=di\+k−1

那么我们就可以比较 d d d和 0.5 0.5 0.5，来确定下一个像素点的坐标。

*   d p < 0.5 ： d\_\{p\}<0.5： dp<0.5：直线更接近下面的点，所以下一个像素点： x p + 1 = x p + 1 , y p + 1 = y p x\_\{p+1\}=x\_p+1,~y\_\{p+1\}=y\_p xp\+1=xp\+1,yp\+1=yp。同时更新 d p + 1 = d p + k d\_\{p+1\}=d\_\{p\}+k dp\+1=dp\+k。
 *   d p ≥ 0.5 ： d\_\{p\}\\geq0.5： dp≥0.5：直线更接近上面的点，所以更新 x p + 1 = x p + 1 , y p + 1 = y p + 1 x\_\{p+1\}=x\_p+1,~y\_\{p+1\}=y\_p+1 xp\+1=xp\+1,yp\+1=yp\+1。同时更新 d p + 1 = d p + k − 1 d\_\{p+1\}=d\_\{p\}+k-1 dp\+1=dp\+k−1。

### 4.2 算法描述 ###

1.   d 0 = 0 d\_0=0 d0=0
2.   d p + 1 = d p + k d\_\{p+1\}=d\_\{p\}+k dp\+1=dp\+k，判断 d i d\_i di：
    
     *  若 d p < 0.5 d\_p<0.5 dp<0.5， x p + 1 = x p + 1 , y p + 1 = y p x\_\{p+1\}=x\_p+1,~y\_\{p+1\}=y\_p xp\+1=xp\+1,yp\+1=yp；
     *  若 d p ≥ 0.5 d\_p \\geq 0.5 dp≥0.5， x p + 1 = x p + 1 , y p + 1 = y p + 1 x\_\{p+1\}=x\_p+1,~y\_\{p+1\}=y\_p+1 xp\+1=xp\+1,yp\+1=yp\+1， d p = d p − 1 d\_\{p\}=d\_\{p\}-1 dp=dp−1；
3.  重复步骤2，直到画到 P 1 P\_1 P1，结束。

### 4.3 算法评价 ###

*  **改进一**：用 e = d − 0.5 e=d-0.5 e=d−0.5代替 d d d， e 0 = − 0.5 e\_0=-0.5 e0=−0.5，这样可以减少一点运算量。
 *  **改进二**：同中点画线算法，用 2 e Δ x 2e\\Delta x 2eΔx代替 e e e。
 *  该算法与中点画线法差不多，个人认为只是计算 d d d的顺序不同：中点画线法是确定像素点之后更新 d d d，而Bresenham算法是先计算 d d d，再去确定像素点。两者大同小异。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70]: /images/20230528/a837ce72e6854b2e908d58a73be9849d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70 1]: /images/20230528/f42ec47a20dd473ca2011879a3d5e8b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_10_color_FFFFFF_t_70]: /images/20230528/f9cb96af1b8d4ff9bfb48e989a8b9028.png
[C_k]: https://blog.csdn.net/Vici__/article/details/106027340
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpY2lfXw_size_16_color_FFFFFF_t_70 2]: /images/20230528/77ffc4fcad474b44be654b7d38cbd8ac.png