基本3D圖形:直線

作者：由賣可樂發表于收藏時間：2022-01-13

1。直線

1。1 2D 直線

1。2 3D 直線

1。3 直線光柵演算法

參考

1。直線

在我們直觀的意識裡，直線就是一條沒有彎曲，無限延長的線。這裡我們只討論歐幾里得幾何，在歐幾里得幾何體系中有一條關於直線的公理：過兩點有且只有一條直線，這就意味著兩點確定一條直線。下面我們討論直線方程在直角座標系（笛卡爾座標系）的表達形式。

1。1 2D 直線

一般式

［1］

上式不是直線唯一表達形式，當滿足約束條件

$A\geq0$

且

（最大公約數）時，直線有唯一表達形式。

斜截式

顧名思義，斜是斜率（slope），截便是截距的意思：

截距式

假設直線

軸的截距等於

，

軸截距等於

，那麼：

$\frac{x}{a} + \frac{y}{b} = 1.$

兩點式

假設直線穿過兩點

，

，則有方程組：

$\begin{cases}y = kx + b,\\y_1 = kx_1 + b,\\y_2 = kx_2 + b,\end{cases}\Rightarrow$

$\frac{x - x_1}{x_2 - x_1} = \frac{y- y_1}{y_2 - y_1}.$

已知直線方程的一般式

，直線穿過兩點

，

，可聯立線性方程組得：

$\begin{cases}Ax + By + C = 0,\\Ax_1 + By_1 + C = 0,\\Ax_2 + By_2 + C = 0.\end{cases}$

可以將方程組看成是關於

的三元一次齊次線性方程組，當其行列式等於零的時候，方程組有解且有無數解，否則，只有零解。所以直線也可以用行列式表示：

$Det =\begin{vmatrix} x&y&1 \\x_1&y_1&1 \\x_2&y_2&1\end{vmatrix}= 0.$

點斜式

從名稱上看，點斜式就是已知直線上一點

，和斜率

：

向量式

直線本身是沒有方向的，但是直線可以看成是一條射線的延展，已知點

，且射線方向為

$\vec{v}$

，求直線上任一點

：

$p = p_0 + \vec{v}t\quad(t\in{\mathbb{R}})$

引數式

引數式可由向量式展開得到，假設

$\vec{v}=(v_x, v_y)$

，則：

$\begin{cases}x = x_0 + v_xt,\\y = y_0 + v_yt.\end{cases}$

1。2 3D 直線

一般式

在三維空間中，兩個不平行的平面相交於直線

，因此，聯立兩個平面方程：

$\begin{cases}A_1x + B_1y + C_1z + D_1 = 0,\\A_2x + B_2y + C_2z + D_2 = 0.\end{cases}\Leftrightarrow\begin{cases}A_1x + B_1y + C_1z = -D_1,\\A_2x + B_2y + C_2z = -D_2.\end{cases}$

從上面的方程組可以看出，方程組有三個未知數

，但只有兩個方程，這意味著方程組有無數個解，亦即直線

上無限多個點。上面直線方程組表示式不是唯一的，穿過直線的無數多個平面方程都可以構成直線方程組。

對稱式

由引數式方程組知，當

相等時，有：

$\frac{x - x_0}{a} = \frac{y- y_0}{b}= \frac{z- z_0}{c}.$

兩點式

假設直線穿過兩點

，

，由引數方程可得：

$\begin{cases}x = x_1 + at,\\x_2 = x_1 + at_1.\end{cases}\&\quad\begin{cases}y = y_1 + at,\\y_2 = y_1 + at_1.\end{cases}\&\quad\begin{cases}z = z_1 + at,\\z_2 = z_1 + at_1.\end{cases}\\\Leftrightarrow\\\frac{x - x_1}{x_2 - x_1} = \frac{y - y_1}{y_2 - y_1} = \frac{z - z_1}{z_2 - z_1} = \frac{t}{t_1}$

同樣地，可以用行列式表示：

$\begin{vmatrix}x&y&1\\x_1&y_1&1\\x_2&y_2&1\end{vmatrix}=\begin{vmatrix}y&z&1\\y_1&z_1&1\\y_2&z_2&1\end{vmatrix}=\begin{vmatrix}z&x&1\\z_1&x_1&1\\z_2&x_2&1\end{vmatrix}= 0.$

向量式

假設直線穿過點

，且方向向量

$\vec{v} = (v_0, v_1, v_2)$

，直線的向量方程表示：

$p = p_0+\vec{v}t.\quad(t \in{\mathbb{R}})$

引數式

設

$\vec{v} = (a, b, c)$

由向量方程可以得到：

$\begin{cases}x=x_0+at,\\y=y_0+bt,\\z=z_0+ct.\end{cases}$

1。3 直線光柵演算法

直線光柵化的目的是把向量圖形轉化成光柵圖形，光柵圖形由畫素陣列構成。

數字微分分析法（Digital Differential Analyzer）

［2］

DDA 演算法的基本思想是利用光柵圖形的特性從

（或者

）方向以單位間隔（增量

）發出射線掃描直線，再計算另一方向

（或者

）的增量，在射線與直線的交點位置繪製畫素。

直線方程：

上面方程式直線的斜率

$k=\frac{\delta{y}}{\delta{x}}$

，

$\delta{y}$

，

$\delta{x}$

分別是

和

方向上的增量，從斜率公式可以得到：

$\begin{cases}\delta{x} = \frac{\delta{y}}{k},\\\delta{y} = k\delta{x}.\end{cases}\tag{1.1}$

當斜率

$\vert{k}\vert\leq 1$

時，選擇從

軸方向以單位間隔（

$\delta{x} = 1$

）發出射線，這時計算

方向上的增量

$\delta{y} = k\delta{x} = k$

。

當斜率

$\vert{k}\vert>1$

時，選擇從

軸方向以單位間隔（

$\delta{y} = 1$

）發出射線，這時計算

方向上的增量

$\delta{x} = \frac{\delta{y}}{k} = \frac{1}{k}$

。

DDA 演算法程式碼實現如下：

/**

* 畫素位置取整。

Vector2i

Round

（

const

Vector2i

）

{

return

Vector2i

（

0。5f

，

0。5f

）；

}

void

DrawPixel

（

const

Vector2i

）

{

。。。

}

void

DDA

（

const

Vector2i

start

，

const

Vector2i

end

）

{

float

end

。

start

。

；

float

end

。

start

。

；

float

fabsX

fabs

（

）；

float

fabsY

fabs

（

）；

Vector2i

outPoint

start

；

DrawPixel

（

Round

（

outPoint

））；

// |k| <= 1 or |k| > 1

int

step

（

fabsX

fabsY

）

？

fabsX

：

fabsY

；

// 增量 deltaX， deltaY

float

deltaX

fabsX

（

float

）

step

；

float

deltaY

fabsY

（

float

）

step

；

for

（

int

；

step

；

）

{

outPoint

。

deltaX

；

outPoint

。

deltaY

；

DrawPixel

（

Round

（

outPoint

））；

}

DDA 演算法的優點是相對直線方程來說速度更快，它利用光柵圖形特性（畫素陣列）減少了直線方程中的乘法運算（x 或者 y 方向上畫素位置間隔是 1，這樣可以先確定 x 或者 y 方向上的增量，再求取另一個方向上的增量），缺點是計算過程中的畫素位置取整運算會使得光柵圖形偏離實際直線，並且取整和浮點運算仍然比較耗時。

佈雷森漢姆演算法（Bresenham Algorithm）

Bresenham 演算法與 DDA 演算法類似，它同樣利用了光柵圖形的特性，首先假設直線斜率為

，

方向固定增量為

，當前顯示的畫素位置是

，那麼要判定下一個畫素的顯示位置是

$(x_{k+1},y_k)$

，還是

$(x_{k+1},y_{k} + 1)$

，判定的依據是什麼？下面介紹作為判定依據的決策函式值

（decision function）。

接上文，顯然，應該選擇兩個畫素當中位置更接近直線的那個繪製。下一個要顯示的畫素位置其

軸座標為

$x_{k+1}$

，代入直線斜截式方程得到：

$y = mx_{k+1} + b.\quad\Leftrightarrow\quad y = m(x_k+1) + b.\tag{1.2}$

計算

$(x_{k+1},y_k)$

與

$(x_{k+1},y)$

的距離：

$d_{lower} = y - y_k.\tag{1.3}$

計算

$(x_{k+1},y_{k} + 1)$

與

$(x_{k+1},y)$

的距離：

$d_{upper} = y_{k} + 1 - y.\tag{1.4}$

式

$\text{(1.3)}$

減去式

$\text{(1.4)}$

得到：

$d_{lower} - d_{upper}=\\2y - 2y_k - 1.\tag{1.5}$

當

$d_{lower} - d_{upper} \leq{0}$

時，說明畫素位置

$(x_{k+1},y_k)$

離直線的距離更近，將

$\text{(1.2)}$

代入式

$\text{(1.5)}$

：

$d_{lower} - d_{upper}=\\2m(x_k+1) - 2y_k - 1 + 2b=\\2mx_k - 2y_k + 2m + 2b - 1.\tag{1.6}$

斜率

$m =\frac{\Delta{y}}{\Delta{x}} \Rightarrow \Delta{y} = m\Delta{x}$

，式

$\text{(1.6)}$

兩邊都乘以

$\Delta{x}$

（消除計算決策函式時的浮點運算）：

$P_k=\Delta{x}(d_{lower} - d_{upper})=\\2\Delta{y}x_k - 2\Delta{x}y_k + \Delta{x}(2m + 2b - 1).\tag{1.7}$

由式

$\text{(1.7)}$

可以得到第

步的決策函式值：

$P_{k+1} = 2\Delta{y}x_{k+1} - 2\Delta{x}y_{k+1} + \Delta{x}(2m + 2b -1).\tag{1.8}$

這時，

$x_{k+1} = x_{k} + 1$

，而

$y_{k+1} - y_k$

等於

或者

這取決於

的符號，式

$\text{(1.8)}$

減去式

$\text{(1.7)}$

得：

$P_{k+1} - P_k = 2\Delta{y} - 2\Delta{x}(y_{k+1} - y_k).$

從以上遞迴式可以看出，計算決策函式的過程已經沒有浮點運算，也沒有取整運算。

起始點決策函式值：

$\begin{cases}P_0=2\Delta{y}x_0-2\Delta{x}y_0+\Delta{x}(2m+2b-1),\\m=\frac{\Delta{y}}{\Delta{x}},\\\Delta{x}b = \Delta{x}y_0 - \Delta{y}x_0.\end{cases}\Rightarrow P_0=2\Delta{y}-\Delta{x}$

Bresenham 演算法程式碼實現（斜率

）：

/**

* start。x < end。x

void

Bresenham

（

const

Vector2i

start

，

const

Vector2i

end

）

{

int

deltaX

end

。

start

。

；

int

deltaY

end

。

start

。

；

// 起始點決策函式值

int

decision

deltaY

deltaX

；

// 繪製起始點

DrawPixel

（

start

）；

int

factor

；

int

start

。

；

int

start

。

；

// x 軸座標以步長 1 遞進

for

（；

end

。

；

）

{

（

decision

）

{

// 決策值小於0，y座標不變

decision

（

deltaY

）；

}

else

{

// 決策值大於等同於0，y座標加1

；

decision

（

deltaY

deltaX

）；

}

// 繪製畫素

DrawPixel

（

Vector2i

（

，

））；

}

上文程式碼只實現了斜率

，且起始點

座標值小於終點

座標值的情形，考慮平面區域對稱性，其他情形只需要交換或者改變

和

方向增量規則即可（1、比如先從

方向遞進，再判定

方向座標值；2、增量等於

$\pm1$

）。

Bresenham 演算法相對 DDA 演算法速度要快，缺點是線寬是固定的，只支援整型座標，且光柵圖形鋸齒比較嚴重。

吳小林直線演算法

Wu 畫線演算法支援反走樣，與 Bresenhanm 演算法不同的是，它會繪製離直線最近的一個畫素對（兩個畫素），並且計算畫素對中兩個畫素與直線的距離，根據距離的大小給予畫素不同的亮度。［5］文中對線段端點提出特別處理，猜測是因為演算法支援線段端點為非整型座標的緣故。提供了 N 種不同語言的程式碼實現。

其他直線光柵演算法

Miloyip 在文［4］中提供了多種光柵化線段的演算法實現，除 Bresenham 演算法外，還包括了單取樣、超取樣、帶符號距離場以及 AABB 最佳化的帶符號距離場等，這幾種方法用帶面積的形狀表示直線，文中採用的是膠囊體（capsule），這樣可以改變直線的寬度，且支援浮點座標，也更方便做反走樣處理。

文中所採用的膠囊體可參見下圖：

圖 1。1。1

上圖其實是膠囊體的一個穿過中心線的截面，從圖中可以看到膠囊體截面由一個矩形和兩個半圓弧連線而成，

，

是膠囊體的兩個端點，膠囊體的半徑為

，

是膠囊體內外的五個點，取樣法就是要判斷這些點是否在膠囊體內，如果是就繪製對應的畫素。分析文中點與膠囊體相交測試的一段程式碼：

int

capsule

（

float

，

float

，

float

，

float

，

float

，

float

，

float

）

{

float

pax

，

pay

，

bax

，

bay

；

float

fmaxf

（

fminf

（（

pax

bax

pay

bay

）

（

bax

bay

），

1。0f

），

0。0f

）；

float

pax

bax

，

pay

bay

；

return

；

}

上文描述了膠囊體截面的形狀由一個矩形和兩個半圓弧銜接而成，如何判定點在膠囊體內或外，可以充分利用圓的特點（一點與圓相交與否可以透過點到圓心的距離

和圓半徑

進行比較即可）。圖 1。1。1，穿過點

與點

分別畫一條垂直於線段

的直線，這兩條直線夾住的空間我們假定為

，它的左側和右側空間分別是

，

，顯然，空間

與

中的點

是否與膠囊體相交我們可以比較點到圓心的距離

和半徑

大小即可。對於空間

中的點，只需要比較點

到線段

的距離和半徑

大小即可。那麼，如何判斷點

在哪個空間呢？下面以點

為例來分析。

我們知道一個向量

$\vec{v} = \vec{AP}$

在另一個向量

$\vec{n} = \vec{AB}$

上的投影可以表示為：

$v_{\|} = n\frac{v\cdot{n}}{\vert{n}\vert^2}.$

從上式可以得到投影向量的模（有符號）為：

$\pm\vert{v_{\|}}\vert = \frac{v\cdot{n}}{\vert{n}\vert}.\tag{1.9}$

當式

$\text{(1.9)}$

小於或等於

時，表示向量

$\vec{v}$

與向量

$\vec{n}$

的夾角度數大於或等於

，此時點

位於空間

，當式

$\text{(1.9)}$

大於或等於

$\vert{n}\vert$

，此時點

位於空間

，當式

$\text{(1.9)}$

大於

且小於

$\vert{n}\vert$

時，則表示點

位於空間

。圖 1。1。1 中點

和

位於空間

。總結下來可以用數學式表示：

$h = \frac{v\cdot{n}}{\vert{n}\vert^2},\\$

$\vec{AP} = \vec{AB} + \vec{BP}.$

$Dist =\begin{cases}\vert{\vec{AP}}\vert,\quad(h\leq{0})\\\vert{\vec{BP}}\vert,\quad(h\geq{1})\\\vert{\vec{AP}- h\vec{AB}}\vert,\quad(0< h < 1)\end{cases}$