直線與三角形的光栅化算法
在進入具體的直線光栅化以及三角形光栅化算法之前，我們首先需要知道光栅化是一個什麼樣的過程。簡單來說光栅化的目的就是将想要展現的物體給真正現實到螢幕上的過程，因為我們的物體其實都是一個個頂點資料來表示的，如何表這些蘊含幾何資訊的資料轉化為螢幕上的像素就是光栅化所考慮的東西。比如說一條直線，究竟該用哪些像素點去逼近它，一個三角形，又用哪些像素集合表示它，這都是光栅化的過程。本節主要讨論介紹兩個直線光栅化和一個三角形光栅化算法。
1 螢幕像素的表示
螢幕中的每一個像素點我們都用整數坐标進行表示，最大最小值與分辨率相對應，考慮到每個像素都有一定的面積，我們定義(x+0.5,y+0.5)為該(x,y)像素的中心，如圖中黑圈所示。
2 直線光栅化算法
2.1 DDA數值微分算法
DDA算法是一個非常簡單直覺的算法。 首先當任何一條直線知道任意兩點時都可以用
來表示，其中k代表斜率，如果
，那麼它的主要行進方向就是x軸，即x軸的變化要比y軸快，相反如果如果
，那麼它的主要行進方向就是y軸，即y軸的變化要比x軸快。如下圖所示：
我們分别就圖上兩種情況進行考慮(假設起點與終點給定(确定了直線方程)，就像圖中一樣)
1 當 圖中的兩種情況的光栅化結果也已給出供參考。
2.2 中點Bresenham算法
我們首先規定想要光栅化的線段的起點
與終點
,則該直線方程可以用y = kx + b的形式來表示，定義
, 準備工作完成之後，接下來一起看看bresenham算法的具體過程！
中點Bresenham算法的思想其實也比較簡單，我們在這裡隻給出
的情況，其它情況可以類推，除卻起點與終點，我們每次的畫點隻會考慮右邊或者右上的點兩種情況(由斜率所決定的)，是以我們隻需要在這二者之間做出選擇。那麼該依據什麼進行判斷呢，給出如下兩種情況，第一：
我們已經成功畫出了前三個藍色方格之後，所要考慮的便是第三個藍色方格右邊或者右上的橙色方格，此時我們取這兩個橙色方格的中點，如圖中圓圈符号所對應的那個點，倘若這個點在直線方程的下面，那麼很明顯我們應該選擇右上的方格。
第二種情況：
此時中點位于直線方程的上方，此時選擇右邊的橙色方格。
至此，如何判斷兩種方格選擇的條件已很明顯，就是确定中點與直線的位置關系，這裡就可以使用到一開始定義的
的方程了。
顯然，當f(x+1,y+0.5) > 0的時候中點在直線上方，當f(x+1,y+0.5) < 0的時候中點在直線下方 （其中x+1，y+0.5是為了表示兩個橙色方格的中點，此時x，y為前一個确定的像素坐标）僞代碼如下：
其中的，some condition也就很明顯的是
目前為止，算法整體便已完成，但有一個問題是，我們每次都要進行一次F（x，y）的計算，倘若直線方程比較複雜，這是很消耗資源的(因為在底層可能是幾百萬次的重複調用)。是以一種改進方法便是利用增量算法。不難具體算出f(x,y)方程具體如下：
觀察可以得出
那麼算法隻需要算出第一次的 f(x+1,y+0.5) ，之後的每次隻需根據上述式子進行相應增量計算即可，如下：
如果還有不解，不妨具體的取兩個點推一邊算法便可加深了解。 當然中點bresenham算法其實還在這之上進一步做了一步優化，因為第一個d其中存在浮點數0.5,是以将有關d的等式兩邊都乘以2，消除了該0.5的浮點，增加了計算效率。
3 三角形光栅化算法
有讀者可能會疑問，為什麼不講四邊形五邊形的光栅化算法，偏偏要談三角形呢，因為三角形是最基本的多邊形，大部分的模型都是用一個個三角形面表示，且任意的其它多邊形其實都可以轉化成多個三角形的形式，是以三角形的光栅化可以說是圖形學中最基礎的部分了。那麼該怎麼去做呢？
其實有一個非常直覺的做法，我們對螢幕中的每一個像素進行采樣，如果這個像素點在三角形之中那麼這個像素點就應該被采用！對，這其實就是該算法的做法。那麼該如何去判斷一個點在不在三角形内部呢，那麼其中一種辦法就是利用叉乘的性質了
如圖所示，我們事先知道想要光栅化的三角形的三個頂點P0，P1，P2，以及檢測點Q。 隻要分别計算
，
，
，如果三者同号則代表點P在三條線段的同一邊，那麼必然處于三角形内部，如果不同号則代表該點一定在三角形外部！
是以自然的，隻需要周遊每一個點就可以得出三角形的光栅化結果了！當然我們還可以進一步的進行優化，因為顯然并沒有必要去測試螢幕中的每一個點，一個三角形面可能隻占螢幕很小的部分，可以利用一個bouding box 包圍住想要測試的三角形，隻對該bounding box内的點進行采樣測試，如下圖：
這樣就可以得到很大的效率提升了！
(強烈推薦闫令琪大佬的計算機圖形學，講的很棒B站有，本系列筆記可算作為該課程的對應筆記，并且會額外加上虎書以及其它計算機圖形學課程的一些補充内容)
Reference
[1] Fundamentals of Computer Graphics 4th
[2] GAMES101-現代計算機圖形學入門-闫令琪
[3] 華中科技大學-計算機圖形學-萬琳教授