Content-Length: 68811 | pFad | https://zh.wikipedia.org/zh-tw/%E7%94%BB%E5%AE%B6%E7%AE%97%E6%B3%95

畫家演算法 - 維基百科,自由的百科全書 跳至內容

畫家演算法

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

畫家演算法也叫作優先填充,它是3D電腦圖形學中處理可見性問題的一種解決方法。當將三維場景投影到二維平面的時候,需要確定哪些多邊形是可見的,哪些是不可見的。

「畫家演算法」表示頭腦簡單的畫家首先繪製距離較遠的場景,然後用繪製距離較近的場景覆蓋較遠的部分。畫家演算法首先將場景中的多邊形根據深度進行排序,然後按照順序進行描繪。這種方法通常會將不可見的部分覆蓋,這樣就可以解決可見性問題。

首先繪製遠山,然後繪製較近的草地,最後繪製場景中最近的樹木等
畫家演算法無法處理相互重疊的多邊形

在有些場合下,畫家演算法可能無法解決可見性問題。在這個例子中,多邊形 A、B、C 互相重疊,我們無法確定哪一個多邊形在上面,哪一個在下面,我們也無法確定兩個多邊形什麼時候在三維空間中交叉。在這種情況下必須用一些方法對這些多邊形進行切分、排序。1972年提出的Newell演算法就是切分類似多邊形的一種方法,在計算幾何領域人們已經提出了許許多多的解決方法。

一些基本的畫家演算法實現方法也可能效率很低,因為這將使得系統將可見多邊形集合中的每個點都進行彩現,而沒有考慮這些多變性在最終場景中可能被其它部分遮擋。這也就是說,對於細緻的場景來說,畫家演算法可能會過度地消耗電腦資源。

人們有時候也使用逆向畫家演算法進行處理,這種演算法首先繪製距離觀察者較近的物體,已經進行繪製的部分不再進行其它的繪製過程。在電腦圖形系統中,這種方法由於無需根據光照、紋理等參數計算被較近物體遮擋的遠處物體的顏色,所以效率非常高。但是,這種方法也有許多與普通畫家演算法同樣的問題。

畫家演算法的這些缺陷導致了深度緩衝技術的發展,深度緩衝技術可以看作是畫家演算法的一個發展,它根據逐個像素的資訊解決深度衝突的問題,並且拋棄了對於深度彩現順序的依賴。即使在這樣的系統中,有時也使用畫家演算法的變體。由於深度緩衝實現通常是基於硬體中的固定精度深度緩衝暫存器,因此捨入誤差就會帶來一些顯示問題,即在多邊形連接的地方會出現重疊或者間隙。為了避免這種問題,一些圖形處理引擎使用了「過度彩現」的方法,即根據畫家演算法的順序繪製兩個多邊形中受影響的邊界。這也就是說有些像素如同在畫家演算法中那樣實際上繪製了兩次,但是由於圖像中只有很少的一部分才做這樣的處理,因此對於效能的影響很小。









ApplySandwichStrip

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier!      Saves Data!


--- a PPN by Garber Painting Akron. With Image Size Reduction included!

Fetched URL: https://zh.wikipedia.org/zh-tw/%E7%94%BB%E5%AE%B6%E7%AE%97%E6%B3%95

Alternative Proxies:

Alternative Proxy

pFad Proxy

pFad v3 Proxy

pFad v4 Proxy