畫家算法也叫作優先填充，它是三維計算機圖形學中處理可見性問題的一種解決方法。當將三維場景投影到二維平面的時候，需要確定哪些多邊形是可見的，哪些是不可見的。
基本介紹
- 中文名：畫家算法
- 外文名： Painters algorithm
- 別名：優先填充
- 拼音：huà jiā suàn fǎ
- 實質：處理可見性問題的一種解決方法
- 屬性：計算機問題解決
- 歸類：教程
- 適用意見：指導性
- 相關算法：Newell
簡介,逆向畫家算法,深度緩衝技術,
簡介
首先繪製遠山，然後草地，最後樹木等“畫家算法”表示頭腦簡單的畫家首先繪製距離較遠的場景，然後用繪製距離較近的場景覆蓋較遠的部分。畫家算法首先將場景中的多邊形根據深度進行排序，然後按照順序進行描繪。這種方法通常會將不可見的部分覆蓋，這樣就可以解決可見性問題。
畫家算法無法處理相互重疊的多邊形在有些場合下，畫家算法可能無法解決可見性問題。在這個例子中，多邊形 A、B、C 互相重疊，我們無法確定哪一個多邊形在上面，哪一個在下面，我們也無法確定兩個多邊形什麼時候在三維空間中交叉。在這種情況下必須用一些方法對這些多邊形進行切分、排序。1972年提出的Newell算法就是切分類似多邊形的一種方法，在計算幾何領域人們已經提出了許許多多的解決方法。
一些基本的畫家算法實現方法也可能效率很低，因為這將使得系統將可見多邊形集合中的每個點都進行渲染，而沒有考慮這些多邊形在最終場景中可能被其它部分遮擋。這也就是說，對於細緻的場景來說，畫家算法可能會過度地消耗計算機資源。
逆向畫家算法
這種算法首先繪製距離觀察者較近的物體，已經進行繪製的部分不再進行其它的繪製過程。在計算機圖形系統中，這種方法由於無需根據光照、紋理等參數計算被較近物體遮擋的遠處物體的顏色，所以效率非常高。但是，這種方法也有許多與普通畫家算法同樣的問題。
深度緩衝技術
畫家算法的這些缺陷導致了深度緩衝技術的發展，深度緩衝技術可以看作是畫家算法的一個發展，它根據逐個像素的信息解決深度衝突的問題，並且拋棄了對於深度渲染順序的依賴。即使在這樣的系統中，有時也使用畫家算法的變體。由於深度緩衝實現通常是基於硬體中的固定精度深度緩衝暫存器，因此捨入誤差就會帶來一些顯示問題，即在多邊形連線的地方會出現重疊或者間隙。為了避免這種問題，一些圖形處理引擎使用了“過度渲染”的方法，即根據畫家算法的順序繪製兩個多邊形中受影響的邊界。這也就是說有些像素如同在畫家算法中那樣實際上繪製了兩次，但是由於圖像中只有很少的一部分才做這樣的處理，因此對於性能的影響很小。
