Abstract
光跡追蹤成像法是廣為人知用來產生三維空間擬真實影像的方法。此法追 蹤從視點的位置射出光線，穿過成像面，進入景像模型中的路徑。但是， 因為需要作大量的相交測試，需耗費很長的時間。且因為每一像素的光線 可獨立處理，所以光線追蹤法本身即具有可平行處理的特性。 Whitted 提出光線追蹤法時，即考慮平行處理的可行性。他建議將計算繁重的求交 點問題，分配給多個處理器，而由主機擔任前置的分工與事後的塗彩。在 本文中，我們將研究如何有效地平行化光跡追蹤成像法，並且在平行虛擬 機器 (Parallel Virtual Machine PVM) 程式環境下實作我們的演算法。 對於以影像切割為基礎的平行方法，我們在主僕架構 (master-slave model) 中使用動態負載平衡 (dynamic load balance)的策略以達到在異 質性（heterogeneous)環境中分工上的平衡。另外，系統的容錯性及避免 死結的發生也將被考慮。同時我們也提出一個利用緩衝區的概念，藉著將 計算與通訊重疊減少避免因等待而浪費系統資源。在許多的實驗中顯示這 種方法可以得到較佳的效能。但因使用主僕架構可能會導至瓶頸問題( bottleneck)發生在單一的主處理機，我們提出了對等式架構 (pear- to- pear model) 來克服此問題。在許多的例子中利用對等式架構確實解決了 瓶頸的問題。由實驗結果得知，當系統之處理機數量加大 (scaleup) 的 時候，此一演算法仍能充分利用增加的資源，並維持其效能不墜。對於以 物件切割為基礎的平行方法，我們提出了一個將複雜的場景切割成數個較 單純的場景然後利用影像切割為基礎的平行方法來解決產生複雜的影像必 須切割物件的問題。利用與此方法相同的觀念，我們提出了一個加速動畫 影像產生的方法。