畫家深度排序


考慮一個CH4分子模型如下所示 :


如果您旋轉這個分子模型,則在某些角度時,中間的C原子有時會部份或完全遮蓋住外面的一個H分子,這是由於它們在深度上的不同所造成的遮蓋效果。

畫家演算法可用來解決不同深度的繪圖效果,其實簡單的說,就是將遠方的物體圖形先進行繪製,然後再繪製近方的圖形,如此後面繪製的圖形就會遮蓋住之前繪製的圖形,例如:



所以我在進行繪圖之前,必須先對要繪製的圖形之Z分量進行深度排序的動作,在物體的移動、旋轉等動作之運算完成之後,將所有的物體資訊儲存至陣列中,然後對這個陣列進行排序,之後依序繪製出陣列中的圖形。

由於必須額外進行排序的動作,所以在物體的數目多時,使用畫家演算法會耗用較多的運算資源與時間,所以通常會依據繪製對象先作一些處理,然後再進行畫家演算法。

例如在凹多面體的繪製時,由於圖形有凹陷的面,單先使用法線向量判定法來繪製圖形,某些面可能被更前面的平面遮蓋而造成圖形的錯亂(與平面的繪製順序有關),例如下面這個圖形:


在凹多面體的繪製中,我們可以應用畫家演算法,但為了加快處理的速度,我們可以先應用法線向量判定法,先將隱藏面去除,再依據所剩下的可視平面之重心來進行深度排序的動作:
  1. 先用法線向量判定法去除隱藏面
  2. 再用深度排序進行畫家演算法

畫家演算法並無法處理所有的深度問題,例如在有圖形貫穿或交疊時,就不能使用畫家演算法,例如下面這兩個圖形並無法使用畫家演算法來實現:


像以上的圖形有很多技巧可以解決,其中最簡單的一種就是補貼圖,先依畫家演算法處理,然後在必要的地方補上片段圖形(有些人戲稱為作弊)例如 :



有時會在報章雜誌上看到一些的不合理圖形,其中一些圖形也是使用這種補貼圖的方式產生,例如:



至於在進行深度排序時,要使用何種排序方式呢?在圖形數量不多時,常見的簡單排序像是氣泡排序法就足夠了,當然您也可以試試其它的高等排序來改進效能。