總結(jié)一下要點（剛好最近要復(fù)習(xí)）：

1. 保證對稱性海蔽，畫一條線段不能依賴于點的起點和終點晓淀，(a, b)畫出的線段和(b, a)畫出的線段應(yīng)該是一樣的谭梗。
2. 如果k大于1坚芜，畫出的線會有了類似于“孔洞”的效果屉佳。
3. 優(yōu)化Line()的性能谷朝。因為畫線會通過一個for循環(huán)，解決方法是加入增量（for循環(huán)中移除了除法運算）武花，因為除法比較占用資源圆凰。
4. 消除浮點數(shù)。經(jīng)過Breas算法的改進(jìn)体箕，代碼中除了error的計算以外专钉，沒有一個×或者÷的運算。

其他博客的精華：

1. 由于圖形學(xué)所有的渲染都是依靠無數(shù)線段的渲染來完成的累铅，所以直線的光柵化算法的效率顯得尤為重要跃须。
2. 在顯示器上由于像素呈現(xiàn)四邊形，理論上無法完全模擬線段（因為在數(shù)學(xué)的觀點來看線段是筆直的娃兽，沒有寬度的）菇民。只能用近似的方法來讓它“看起來”是一條線段，這就是直線的光柵化投储。
3. 數(shù)值微分算法（DDA算法）引進(jìn)了圖形學(xué)中很重要的增量思想（為了消除乘法k * x）第练。但是DDA算法的2個問題：

• 每次遞增x時不能斜率過大（k不能大于1）。斜率過大會導(dǎo)致屏幕上顯示的點少而且稀疏玛荞。（可以在斜率小于1的時候采用遞增x的方式娇掏，在斜率大于1的時候采用遞增y的方式來畫直線。）
• 效率仍然比較低（雖然已經(jīng)沒有了乘法勋眯，但是加法是一個浮點數(shù)的加法）

4. 中點畫線算法達(dá)到了和DDA算法一樣的效率(浮點數(shù)加法)驹碍，并且避開了浮點數(shù)加法。因此凡恍，中點畫線算法已經(jīng)把直線光柵化的效率推至極限(整數(shù)加法)志秃。
5. Bresenham算法擴展了中點畫線算法的適用范圍，它可以根據(jù)任何形式的直線方程都可以畫出直線嚼酝，并且保持效率最佳浮还。
6. Bresenham算法的思想是將像素中心構(gòu)造成虛擬網(wǎng)格線，按照直線起點到終點的順序闽巩，計算直線與各垂直網(wǎng)格線的交點钧舌，然后根據(jù)誤差項的符號確定該列像素中與此交點最近的像素担汤。

7. Bresenham算法總結(jié)了DDA算法和中點畫線算法的優(yōu)點，應(yīng)用更加廣泛洼冻。

   
   
   Bresenham算法流程

最近在Github上復(fù)現(xiàn)了一個渲染器render的項目：
Github鏈接：tiny render

我希望在博客上可以記錄自己的學(xué)習(xí)過程崭歧，博客主要分為兩大類：《原理篇》和《語法篇》。
原理篇則主要講的是——實現(xiàn)渲染器過程中所需要的算法知識撞牢。
語法篇則主要講的是——實現(xiàn)渲染器過程中使用到的C++的語法知識率碾。

首先，我們來康康屋彪，渲染器實現(xiàn)后的成效是什么樣的所宰？
like this ——

TinyRender

一、 首次嘗試

大家的第一個目標(biāo)可以定為渲染出金屬絲網(wǎng)畜挥。

所以仔粥，第一步，應(yīng)該學(xué)習(xí)如何畫線段蟹但。

畫線段用到了算法：Bresenham's line algorithm躯泰，不知道的可以看這個鏈接：Bresenham's line algorithm

這個算法講到了如何畫一個從(x0, y0)到(x1, y1)的直線段，code如下：

void line(int x0, int x1, int y0, int y1, TGAImage &image, TGAColor color)
{
    //  for (float t = 0.; t < 1; t+=0.1)
    for (float t = 0.; t < 1.; t += .01)    //  上句code沒有將所有寫成float類型
    {
        int x = x0 + t * (x1 - x0);
        int y = y0 + t * (y1 - y0);
        image.set(x, y, color);
    }
}

上述code中华糖，image使用了引用reference, 對color沒有表示麦向。

t表示斜率，直接定義缅阳。
最后一句code使用了接口set來完成。核心就是for循環(huán)來不斷的畫線景描。

畫出的圖是這樣：

常數(shù)0.01

二十办、第二次嘗試

上述code的問題在于低效，還有一個就是常數(shù)的選擇超棺，上面取它為0.01——

常數(shù)取0.01

如果將常數(shù)取為0.1向族，上面code所畫的圖則會變?yōu)橄聢D——

常數(shù)取0.1

通過這個，大家可以發(fā)現(xiàn)棠绘，上述代碼的核心部分就是：將要繪制的像素數(shù)量件相，那么有人會將代碼改成下面這樣——

void line(int x0, int x1, int y0, int y1, TGAImage &image, TGAColor color)
{
    // for (int x = x0; x <= x1; x += .1)
    for (int x = x0; x <= x1; x++)
    {
        // float t = (x - x0)/(float)(x1 - x);
        float t = (x - x0)/(float)(x1 - x0);
        int y = y0 * (1. - t) + y1 * t;
        image.set(x, y, color);
    }
}

上述code我寫的有兩處錯誤：

• 第一個是line3中的條件3是x++
• 第二個是line5中分母應(yīng)該是(x1 - x0)

• 代碼中的錯誤： 整數(shù)除法
  • 像這種(x - x0)/(x1 - x0)

第二個代碼中的首要錯誤就是上述整數(shù)除法的這種錯誤。

三氧苍、 第三次嘗試

3.1 出現(xiàn)問題

大家可以先用上述的兩段code來畫三條Lines夜矗。調(diào)用函數(shù)line:

line(13, 20, 80, 40, image, white);
line(20, 13, 40, 80, image, red);
line(80, 40, 13, 20, image, red);

寫了3條線的代碼，但只顯示了2條線

有同學(xué)可能要問了让虐，明明三條線的code紊撕，怎么只顯示了2條線。

因為第一句和第三句的命令是一樣的赡突，只不過是不同的起終點和不同的方向对扶。也就是說区赵，第三條線畫出來后，可以覆蓋第一條線浪南，因為第一條線是白色的笼才，第三條線是紅色的。

理論上络凿，白色呢條線是要被紅色覆蓋的骡送。

可是沒有，那么怎么改喷众？

可以說各谚，這3行代碼是對對稱性的一個測試。

也就是說到千，畫一條線不應(yīng)該依賴于點的起點或者終點昌渤，

(a, b)畫出的線段和(b, a)畫出的線段應(yīng)該是一樣的。

3.2 修正直線

好憔四，接下來膀息，咱們來想辦法讓消失的紅線重新浮現(xiàn)出來。

大家可以通過交換點的位置來改變了赵，所以x0是永遠(yuǎn)低于x1的潜支。

再加上，高度遠(yuǎn)大于寬度的原因柿汛，所以畫出的線上會有孔洞冗酿。

但是，很多人會這樣改code——

if (dx > dy)
{
    for (int x)
}
else
{
    for (int y)
}

這上面2行核心代碼络断，我屬實沒看懂裁替。而且是不對的。

應(yīng)該按下面這樣改：

void line (int x0, int x1, int y0, int y1, TGAImage &image, TGAColor color)
{
    bool steep = false; //這次把斜率考慮進(jìn)去了
    if (std::abs(x0 - x1) < std::abs(y0 - y1))
    {
        std::swap(x0, y0);
        std::swap(x1, y1);
        steep = true;
    }
    
    if (x1 < x0) //因為這個是在改左右貌笨，所以關(guān)注x0和x1的大小就好
    {
        std::swap(x0, x1);
        //這里漏了一句弱判，以為不用改
        std::swap(y0, y1);
        //其實換的話，應(yīng)該是一起換的
    }
    
    for (int x = x0; x <= x1; x++)
    {
        float t = (x - x0)/(float)(x1 - x0);
        int y = (1. - t) * y0 + t * y1;
        
        if (steep)
        {
            image.set(y, x, color);
        }
        else
        {
            image.set(x, y, color);
        }
    }
}
// 就是第二個if判斷那里锥惋，少寫了個 std::swap(y0, y1)

• 這個代碼的邏輯是什么呢昌腰？
• 邏輯是這樣，更改了line()函數(shù)膀跌。
• 1. 在line()函數(shù)中遭商，加入了bool型變量steep，初值定為false捅伤，表示沒有斜率株婴。
• 2. 比較(x1 - x0)和(y1 - y0)的絕對值大小，如果x坐標(biāo)的絕對值小，那就把x和y上的坐標(biāo)對換困介，也就是x0和y0換大审，x1和y1換，換完后座哩，將steep置為true徒扶，表示有斜率。例如：原先坐標(biāo)是(2, 4)和(5, 9)根穷，這樣子姜骡，y軸的絕對值是5，x軸的絕對值是3屿良，這樣子圈澈，y=kx中，斜率k是大于1尘惧。我們要做的就是讓斜率不要大于1康栈，所以交換x0和y0的值，交換x1和y1的值喷橙。原坐標(biāo)就會變?yōu)?4, 2)和(9, 5)啥么，這樣x軸的絕對值就是5，y軸的絕對值是3贰逾，這樣悬荣，y=kx的斜率k就比1小了。
• 3. 比較x1和x0的大小疙剑，如果x1比x0小氯迂，就交換x1和x0的值。注意：此時y1和y0也要換言缤，要保持同步嚼蚀，不然坐標(biāo)點的值就變了。例如：原先坐標(biāo)是(8, 5)和(2, 7)轧简，交換后驰坊，就變成(2, 7)和(8, 5)匾二。
• 4. 接下來的邏輯差不多哮独，重新盤一下：枚舉x坐標(biāo)，初值x0察藐，終值x1皮璧。定義一個float型的斜率t。y的大小就由斜率t和y0分飞、y1來計算悴务。
• 5. 如果steep是true，說明我們原先交換過x和y，在畫圖的時候需要轉(zhuǎn)回來讯檐。所以set函數(shù)的命令是(y, x, color); 如果steep是false羡疗，說明沒有交換過x和y，那就原先的(x, y, color)别洪。

改了后叨恨，結(jié)果就是這樣：

原先的白線變成了想要的紅線

那么也許有同學(xué)會問了，更改后的代碼挖垛，前面交換x和y的意義在哪里痒钝？
意義就在于我們要完成：畫一條線是不應(yīng)該依賴于坐標(biāo)的起點和終點的。這樣子痢毒，增強了代碼的對稱性送矩，這樣，像上一節(jié)的情況就不會出現(xiàn)哪替。我們重新畫了一條線栋荸，只是改了顏色和坐標(biāo)起點，那么結(jié)果就是線不變顏色會變夷家。

四蒸其、計時：第四次嘗試

當(dāng)我們修改好了code，讓他可以看起來work fine以后库快，我們需要提高它的性能摸袁，想辦法優(yōu)化代碼。

那么優(yōu)化之前义屏，大家可以猜猜靠汁，上述code中的哪個步驟是最占用資源的STEP？

答案是：

• line(int, int, int, int, TGAImage&, TGAColor)

它占用了70%的資源闽铐，所以這句code就是大家需要優(yōu)化的步驟蝶怔。

五、優(yōu)化line()

大家一定都知道兄墅，上述的除法

(x-x0)/(x1-x0)

中都有相同的因子踢星。因為x1和x0是不變的。

因為這個語句是在for循環(huán)中的隙咸，我們可以把它從for循環(huán)中取出來沐悦。

這個誤差變量給了從當(dāng)前(x, y)像素到最佳直線的距離。

每一次的誤差都會大于一個像素五督。

對此藏否，我可以給出的解決方案是：

• 將y增加1，相應(yīng)地將誤差也減少1充包。

改正后的代碼如下：

這次調(diào)整的思路是：

• 加入了差分dx dy derror
• 之前算斜率t是放在for loop中副签，斜率t的計算是除法(除法中分子分母還都是減法)。現(xiàn)在換成了derror，derror的計算是加法淆储。(提高性能)
• 初始化了error和y
• 取而代之的是在for循環(huán)中加入了error的遞推式冠场，和error與y之間的對應(yīng)增減關(guān)系(消除誤差變量)

void line (int x0, int x1, int y0, int y0, TGAImage &image, TGAColor color)
{
    bool steep = false;
   // if (std::abs(y0-x0) > std::abs(y1-x1))
   // {
    //    std::swap(x0, x1);
    //    std::swap(y0, y1);
    //    steep = true;
    //}
    
    if (std::abs(x0 - x1) < std::abs(y0 - y1))
    {
        std::swap(x0, y0);
        std::swap(x1, y1);
        steep = true;
    }
    
    
    if (x1 < x0)
    {
        std::swap(x1, x0);
        std::swap(y1, y0);
    }
    
    int dx = x1 - x0;
    int dy = y1 - y0;
    //float derror = dy / (float)(dx);
    ////float derror = std::abs(dy/(float)(dx));
    float derror = std::abs(dy/float(dx));
    
    float error = 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 > 5)
        if (error > .5)
        {
            y += (y1 > y0 ? 1 : -1);
            error -= 1;
        }
    }
}
// 這次寫代碼碰到了3個錯誤：
// 1. 第一段代碼中x0 y0、x1 y1互換本砰，但是比較是x0 x1的差值和y0 y1的差值比較慈鸠。
// 2. 算derror的時候，要加abs灌具，float可以不帶括號青团，float(dx)
// 3. 判斷y是+1還是-1的時候，條件是error 是否比 .5 大咖楣。 大的話督笆，y + 1 or -1(取決于y1是否比y0大)， 然后對應(yīng)地诱贿，error 也 -1娃肿。

這次寫代碼碰到了3個錯誤：

1. 第一段代碼中x0 y0、x1 y1互換珠十，但是比較是x0 x1的差值和y0 y1的差值比較料扰。
2. 算derror的時候，要加abs焙蹭，float可以不帶括號晒杈，float(dx)
3. 判斷y是+1還是-1的時候，條件是error 是否比 .5 大孔厉。 大的話拯钻，y + 1 or -1(取決于y1是否比y0大)， 然后對應(yīng)地撰豺，error 也 -1粪般。

上面說到，line的資源占用率達(dá)到了70%污桦，這次代碼的優(yōu)化后亩歹，差不多下降到了40%。

原因就是在for循環(huán)中移除了除法運算的代碼凡橱。

所以+ - 還可以接受小作，但是/就比較占用資源了。

并且在code語句中梭纹，優(yōu)化前和優(yōu)化后的代碼區(qū)別是——

• 將斜率和y分開運算了躲惰。優(yōu)化前致份，y的運算包含了t变抽，而且是×運算。
  • 而且t是斜率，error是微分斜率绍载，解讀為誤差诡宗。
• 優(yōu)化后，error是error击儡，通過derror累加塔沃。y只是—-+1的操作，對應(yīng)的error也-1阳谍。
  • 唯一的y和error對應(yīng)的是 當(dāng)error大于.5的時候蛀柴，y才開始+1或-1。

結(jié)果圖：

優(yōu)化后結(jié)果圖

為什么畫出來的是藍(lán)色的矫夯？因為代碼的這里改了：

• image.set(y, x, TGAColor(255, 1));

調(diào)用了另一個構(gòu)造函數(shù)鸽疾，1個字節(jié)數(shù)，顏色值為255训貌，顯示出來是藍(lán)色制肮。

六、浮點數(shù)存在的必要性递沪？

大家應(yīng)該發(fā)現(xiàn)了豺鼻，一直對于error和斜率steep均用的是float型變量。

• 那么使用float型變量的原因是什么款慨？

唯一的原因就是除法中的一個因子為dx和在for循環(huán)體中的比較(error > .5)這兩個操作儒飒。

• 那么如何消除浮點數(shù)？

大家可以通過使用另一個變量來替代原先的誤差變量來消除浮點數(shù)檩奠。

可以稱這個變量為error2约素， 假設(shè)它為error × dx × 2。

改進(jìn)的code如下：

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);
    }
    
    //這次的error就直接是只跟dy相關(guān)了笆凌，去掉了dx圣猎，因為dx帶有浮點數(shù)。
    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;//erro2的疊加還是之前呢個樣子
        if (error2 > dx)//但是比較就不再是之前的與.5比較了乞而，而是dx比大小
        {
            y += (y1 > y0 ? 1 : -1);
            error2 -= dx * 2;//相應(yīng)的送悔，y加減1，error2和dx進(jìn)行運算爪模。
            //我猜測原因應(yīng)該是derror2的初始化欠啤，是直接通過dy生成的。所以error2在for循環(huán)中的累加屋灌，與dx進(jìn)行運算不會收到影響洁段。
        }
    }
}

這次的error就直接是只跟dy相關(guān)了。
去掉了float型的dx共郭，變成了int型的dx祠丝。之前derror的計算是這樣：

• float derror = std::abs(dy / float(dx));

derror是浮點型的疾呻，dx也被強制轉(zhuǎn)化了，而且derror的值由dy和dx一起計算得到写半。

error2的疊加還是之前呢個樣子岸蜗。
但是比較就不再是之前的與.5比較了，而是dx比大小
相應(yīng)的叠蝇，y加減1璃岳，error2和dx進(jìn)行運算。
我猜測原因應(yīng)該是derror2的初始化悔捶，是直接通過dy生成的铃慷。所以error2在for循環(huán)中的累加，與dx進(jìn)行運算不會收到影響蜕该。

現(xiàn)在枚冗，我們對code的改進(jìn)，已經(jīng)去除掉了函數(shù)調(diào)用中對color進(jìn)行引用傳遞的不必要的copies蛇损。(或者只是啟用編譯標(biāo)志-O3)

代碼中除了error的計算以外赁温，沒有一個×或者÷的運算。

line的執(zhí)行時間也降低了(從2.95將到了0.64)淤齐。

七股囊、線框渲染

在對code進(jìn)行優(yōu)化完后，大家需要做的就是對線框進(jìn)行渲染更啄。

模型的保存使用Wavefront.obj稚疹，OBJ是一種幾何定義文件格式。

詳細(xì)的介紹看這里Wavefront.obj file

這里祭务，也提供了一個OBJ文件内狗，內(nèi)容長這樣。

渲染所需要的就是從文件中讀取以下類型的頂點數(shù)組

v 0.608654 -0.568839 -0.416318

上面這三個是x, y, z坐標(biāo)义锥，這個v表示頂點數(shù)組

f 1193/1240/1193 1180/1227/1180 1179/1226/1179

每個文件行和面都有一個頂點柳沙。上面這行則是說明其中一個三角形的構(gòu)成是分別由1193， 1180拌倍，1179個頂點構(gòu)成的赂鲤。

v -0.000581696 -0.734665 -0.623267; //這個v表示頂點數(shù)組，后面3個數(shù)字表示的是x, y, z坐標(biāo)
vt  0.438 0.333 0.000;
vn  0.556 0.801 -0.221;
f 175/155/175 214/194/214 213/193/213; //每個文件行和面都有一個頂點

大家需要對第4行中的代碼多加注意：

關(guān)注每一個空格后的第一個數(shù)字柱恤。這個第一個數(shù)字是我們上面第一行代碼表示V的呢個數(shù)組中頂點總共的數(shù)量数初。

所以，這個頂點第4行代碼的意思是175梗顺、214和213個頂點構(gòu)成一個三角形泡孩。

在model.cpp中包含了一個簡單的解析器。將下面的for loop寫進(jìn)main.cpp寺谤，大家的線框渲染就大功告成了仑鸥。

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]); 
        
        int x0 = (v0.x+1.)*width/2.; 
        int y0 = (v0.y+1.)*height/2.; 
        int x1 = (v1.x+1.)*width/2.; 
        int y1 = (v1.y+1.)*height/2.; 
        
        line(x0, y0, x1, y1, image, white); 
    } 
}

線框渲染后的效果是這樣的吮播，大家可以康康：

線框渲染

重新打開了一遍，成白色了：

線框渲染2

學(xué)習(xí)之初锈候，我整理了每節(jié)課中代碼的變化，現(xiàn)在看來用處不大敞贡，但是刪了可惜泵琳，大家有需要的可以看看哈~~

這篇博客用到的代碼文件的變化是這樣的：

• tgaimage.h

(初始導(dǎo)入)

• tgaimage.cpp

(初始導(dǎo)入)

• african_head.obj

(線框渲染)

• geometry.h

(線框渲染)

• main.cpp

(樸素線段追蹤)->(線段追蹤、減少劃分的次數(shù))->(線段追蹤：all integer Bresenham)->(線框渲染)

• model.cpp

(線框渲染)

• model.h

(線框渲染)

解釋一下上述文件括號中的文字——
只有tgaimage.h/.cpp這兩個文件是從初始導(dǎo)入到Lesson1最后的線框渲染過程中沒有變化過的誊役，所以一直顯示是初始導(dǎo)入获列。
main.cpp變化較多，從一開始的簡單的線段追蹤蛔垢，到減少劃分次數(shù)的線段追蹤击孩，再到所有integer Bresenham的線段追蹤，直到最后的線段渲染鹏漆。
剩下的巩梢，.obj文件、geometry.h文件艺玲、model.h/.cpp文件都是在線框渲染時才一起出來的括蝠。
其中model時用來test測試的。