前言
? 學完GAMES101后，打算學習寫一個軟渲染器來加深對渲染的理解，了解一下圖形管線前前后后都做了哪些作業
? 但本系列重在說明原理，完整的源代碼不會展示出，想了解的請移步至ssloy/tinyrenderer: A brief computer graphics / rendering course (github.com)
?
Bresenham演算法介紹
? 畫線演算法有三種，分別是DDA演算法、中點演算法、Bresenham演算法，但為什么我們選擇Bresenham演算法呢？因為Bresenham演算法僅僅使用整數加法、減法和位移，是一種增量誤差演算法，這些操作省時高效精確，是當前最有效的畫線演算法，并且，此演算法并不局限于直線，圓等其他曲線同樣可以畫，更重要的是，該演算法用于繪圖儀等硬體和現代顯卡的圖形芯片中，以及非常多的軟體圖形庫中都可以看到他的身影，鑒于Bresenham演算法的簡單高效，因此我們選用他作為實作渲染器的一部分
Bresenham演算法思想
? 在圖形學中，螢屏是一個二維陣列，陣列里的每一個元素都為一個像素,其中每個像素都必須是整數
? Bresenham演算法是設定一個起點，一個終點，按照起點到終點的順序，計算直線和垂直網格線的交點，再根據誤差項error變數來確定該列兩像素點中離此交點最近的那個，也就是說，假設一點(x,y)，若交點并不是在像素點上，那么就會從(x + 1, y)和(x+1, y+1)中去選擇一個最合適的點，那么怎么才是最合適的呢？很簡單，我們取兩點之間的中點，若這個交點在中點上面，則選取(x+1, y+1)；若交點在中點下面，則選取(x+1,y)
Bresenham演算法實作
? 我們假設每次x增加1，y增量為0或1,k為斜率;鑒于每次都需要計算中點且中點是浮點數，過于麻煩，因此我們將誤差量設為d = 0,d = d + k( 0 < k < 1 ）；每當d > 0.5，則d -= 1,y+1
? 實作如下：
void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
bool steep = false;
//dy需要小于dx，否則畫出的線不夠密集，有空隙
if (std::abs(x0-x1)<std::abs(y0-y1)) {
std::swap(x0, y0);
std::swap(x1, y1);
steep = true;
}
//因為后面的for回圈是從x0遞增到x1，所以這里必須保證x0小于x1
if (x0>x1) {
std::swap(x0, x1);
std::swap(y0, y1);
}
int dx = x1-x0;
int dy = y1-y0;
//誤差值
float derror = std::abs(dy/float(dx));
float error = 0.0;
int y = y0;
for (int x=x0; x<=x1; x++) {
if (steep) {
image.set(y, x, color);
} else {
image.set(x, y, color);
}
error += derror;
if (error > 0.5) {
y += ( y1 > y0 ? 1 : -1 );
error -= 1.0;
}
}
}
? 優化 上面的方法其實已經可以實作畫線了，但這并不是Bresenham演算法的靈魂，它精彩的地方在于僅僅使用整數加減，想想上面這段代碼還有什么地方可以優化的？
? 我們發現 float derror = std::abs(dy/float(dx))和if (error > 0.5)都包含浮點數，Bresenham演算法的精髓并沒有體現，那么怎么做呢？
? 我們可以做一種嘗試，讓初始值e\(0\) = d - 0.5, e = e + k;每當e大于0，e -= 1;但我們會發現還是稍有不足，e、k依舊為浮點數,我們需要想辦法消除e、k，怎么做呢？
? 下面，我們來做另一種嘗試，定義一個E = e * 2 * dx代替e,如此e的浮點數0.5即可消除;每走一步有E = (e + k) * 2 * dy = E + 2 * dy，也就是說每次E增加2dy;每當e大于0,E = (e-1) * 2 * dx = E - 2 * dx
? 代碼如下：
void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
bool steep = false;
if (std::abs(x0-x1)<std::abs(y0-y1)) {
std::swap(x0, y0);
std::swap(x1, y1);
steep = true;
}
if (x0>x1) {
std::swap(x0, x1);
std::swap(y0, y1);
}
int dx = x1-x0;
int dy = y1-y0;
int derror2 = std::abs(dy)*2;
int error2 = 0;
int y = y0;
for (int x=x0; x<=x1; x++) {
if (steep) {
image.set(y, x, color);
} else {
image.set(x, y, color);
}
error2 += derror2;
if (error2 > dx) {
y += (y1>y0?1:-1);
error2 -= dx*2;
}
}
}
? 此時，我們才真正實作了Bresenham演算法,加減都是整數簡單高效！
?
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/525934.html
標籤：其他