??推薦關注公眾號「鹵蛋實驗室」或訪問博客原文，更新更及時，閱讀體驗更佳
第一天我們搭建了 C++ 的運行環境并畫了一個點，根據 點 → 線 → 面 的順序，今天我們講講如何畫一條直線，
本文主要講解直線繪制演算法的推導和思路（莫擔心，只涉及到一點點的中學數學知識），最后會給出代碼實作，大家放心的看下去就好，
1.DDA 直線演算法
1.1 簡單實作
我們先來回顧一下中學的幾何知識，如何在二維平面內表示一條直線？最常見的就是斜截式了：
其中斜率是 ，直線在 軸上的截距是 ，
斜截式在數學上是沒啥問題的，但是在實際的工程專案中，因為硬體資源是有限的，我們不可能也沒必要表示一條無限長度的直線，現實往往是已知一條線段的起點 和終點 )，然后把它畫出來，
這時候用兩點式表示一根直線是最方便的，其中 ，：
把上面的式子稍作變形，可以把 和 用引數 表示：
這時候我們只要取不同的 ，就可以得出對應的 x 和 y，
按照以上的思路，我們可以用代碼實作一下，C++ 的實作也很簡單，如下所示（dl 表示 ）：
void line(
int x1, int y1,
int x2, int y2,
TGAImage &image, TGAColor color) {
const float dl = 0.01;
int dx = x2 - x1;
int dy = y2 - y1;
for (float t=0.0; t<1.0; t+=dl) {
int x = x1 + dx * t;
int y = y1 + dy * t;
image.set(x, y, color);
}
}
這個是直線演算法的初步實作，只能說「能用」，地位和排序演算法里的「冒泡排序」一樣，目的達到了，但是性能不太好：
每畫一個點，都要運行兩次乘法 大量使用浮點運算（眾所周知， < < ） 如果 dl取的比較小，會導致一個像素點會被繪制多次，重復計算如果 dl取的比較大，會導致直線斷掉
1.2 優化
下面我們就一步一步優化上面的演算法，
首先我們注意到，對于螢屏繪制直線這個場景，理論上是連續的，但實際是離散的，
比如說 從 變化到 時，每次繪制時， 都是按步長 1 增長的，也就是 ，
這時候 ，
我們把上面的公式寫成代碼，就是下面這個樣子：
void line(
int x1, int y1,
int x2, int y2,
TGAImage &image, TGAColor color) {
float x = x1;
float y = y1;
float step = std::abs(x2 - x1);
float dlx = (x2 - x1) / step;
float dly = (y2 - y1) / step;
for (int i=1; i<step; i++) {
image.set(x, y, color);
x = x + dlx;
y = y + dlx;
}
}
這個演算法其實還有一點兒問題，就是繪制斜率大于 1 的直線時，繪制出的直線會斷掉，比如說從 (0, 0) 點繪制到 (2, 4) 點，按照上面的演算法只會繪制兩個點，但是我們期望的是右圖那樣，起碼各個像素要連接起來：
解決方法也很簡單，繪制這種比較「陡峭」的直線時（斜率絕對值大于 1），以 y 的變化為基準，而不是以 x，這樣就可以避免上面直線不連續情況，
最后的直線演算法就是這樣：
void line(
int x1, int y1,
int x2, int y2,
TGAImage &image, TGAColor color) {
float x = x1;
float y = y1;
int dx = x2 - x1;
int dy = y2 - y1;
float step;
float dlx, dly;
// 根據 dx 和 dy 的長度決定基準
if (std::abs(dx) >= std::abs(dy)) {
step = std::abs(dx);
} else {
step = std::abs(dy);
}
dlx = dx / step;
dly = dy / step;
for (int i=1; i<step; i++) {
image.set(x, y, color);
x = x + dlx;
y = y + dly;
}
}
然后我們用這個演算法測驗一下不同起點不同斜率的直線，看效果運行良好：
這個演算法就是經典的 DDA (Digital differential analyzer) 演算法，他比我們一開始的代碼要高效的多：
消除了回圈內的乘法運算 避免了重復的繪制運算 保證線段連續不會斷掉
但是它還有個很耗性能的問題：計算程序中涉及大量的浮點運算，
作為渲染器最底層的演算法，我們肯定希望是越快越好，下面我們就來學習一下，消除浮點運算的 Bresenham’s 直線演算法，
2.Bresenham’s 直線演算法
2.1 初步實作
本節內容不會從一開始就講完善版的 Bresenham’s 演算法，我們先從一個小節開始推導，最后推匯出完善的演算法，
最一開始，我們先考慮所有直線里的一個子集，即斜率范圍在 之間的直線：，
上一小節里我們說過，對于螢屏繪制直線這個場景，理論上是連續的，但實際是離散的，我們先假設已經繪制了一個點 ，那么在像素螢屏上，下一個新點的位置，只可能有兩種情況：
那么問題就轉化為，下一個新點的位置該如何選擇？
我想大家應該都想到方案了，大體思路如下
先把 這個值帶入直線方程里，算出來 的值 然后比較 和 的大小 ，選點 ，選點
我們再把思路完善一下，把每次取舍時的誤差考慮進去：
如上圖所示，實際上繪制的點的位置是 ，理論上點位置是 ，
當點從 移動到 時，理論上新點的位置應該是 ，其中 k 是直線的斜率，
實際繪制時，要比較 和 的大小：
，選點 ，選點
對于下一個新點 ，我們可以按照下式更新誤差 ：
若前一個點選擇的是 ，則 若前一個點選擇的是 ，則
把上面的思考程序用偽代碼表示一下：
2.2 消除浮點運算
觀察上面的偽代碼，我們可以發現這里面出現了 0.5，也就是說存在浮點運算，下面我們就通過一些等價的數學變換消除浮點數，
首先對于不等式 ，我們給它不等號左右兩邊同時乘以 2 倍的 ，這樣就可以同時消除斜率除法和常量 0.5 帶來的浮點運算:
然后用 表示 ，上式可以轉換為
同樣的，我們在更新 時，把它也替換為 ，也就是對于下面兩式：
等號兩邊同時乘以 ，有：
然后用 表示 ，可以得到：
這時候我們就可以得到一個去掉浮點數運算的偽代碼：
C++ 實作如下：
void line(Screen &s,
int x1, int y1,
int x2, int y2,
TGAImage &image, TGAColor color) {
int y = y1;
int eps = 0;
int dx = x2 - x1;
int dy = y2 - y1;
for (int x = x1; x <= x2; x++) {
image.set(x, y, color);
eps += dy;
// 這里用位運算 <<1 代替 *2
if((eps << 1) >= dx) {
y++;
eps -= dx;
}
}
}
這樣我們就實作了斜率在 區間的高效演算法，也就是說，現在我們可以繪制 1/8 個象限的直線了，剩下范圍的直線，可以通過交換 xy 等方式實作繪制，具體的實作都是些臟活累活，就不擺出來了，感興趣的可以去 GitHub 上看代碼的完整實作，
3.繪制模型
這一部分可以結合原英文教程學習，我只做一些細節上的補充，
前面兩個小節都是演算法基礎學習，本小節開始加載一個非洲人的 .obj 模型，然后把模型上每個三角形面的點連接起來，
??OBJ 檔案是一種被廣泛使用的 3D 模型檔案格式（obj 為后綴名），用來描述一個三維模型，模型關鍵字較為繁瑣，限于篇幅本文暫不展開，大家可以自行搜索學習，
這一節的流程也很清楚：從磁盤上加載 .obj 檔案 → 按行分析 .obj 檔案 → 構建 model → 回圈 model 中的每個三角形 → 連接三角形的三條邊 → 渲染出圖
上訴流程的前三步已經被原作者封裝好了，我們直接把原始碼里的 model.h 和 model.cpp 拖到主工程里就可以了，感興趣的人可以看一下原始碼實作，非常簡單，在一個 while 回圈里一直 readline 就可以了，因為和圖形學關系不大，我這里就略過了，
最后的畫三角形的代碼如下，關鍵步驟我已經用注釋標注了：
// 實體化模型
model = new Model("obj/african_head.obj");
// 回圈模型里的所有三角形
for (int i = 0; i < model->nfaces(); i++) {
std::vector<int> face = model->face(i);
// 回圈三角形三個頂點，每兩個頂點連一條線
for (int j = 0; j < 3; j++) {
Vec3f v0 = model->vert(face[j]);
Vec3f v1 = model->vert(face[(j + 1) % 3]);
// 因為模型空間取值范圍是 [-1, 1]^3，我們要把模型坐標平移到螢屏坐標中
// 下面 (point + 1) * width(height) / 2 的操作學名為視口變換（Viewport Transformation）
int x0 = (v0.x + 1.) * width / 2.;
int y0 = (v0.y + 1.) * height / 2.;
int x1 = (v1.x + 1.) * width / 2.;
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/250610.html
標籤：其他