利用一致性加速光線追蹤法和立體資料描繪法

Abstract

由於在許多領域中具有高度實用性，使得「光線追蹤法」和「科學資料顯像」成為 計算機圖學中兩門重要的研究課題。然而，光線追蹤法和「立體資料描繪法」（科 學資料顯像的一個非常優良的技術）都必須耗費很長的計算時間才能畫出一張圖像 。在本論文中，我們將從「一致性」的觀點來探討如何改良光線追蹤法和立體資料 描繪法。 我們的第一個研究主題乃是利用兩種一致性來改善「階層圍細分法」（光線追蹤法 中一個著名的技巧）的執行速度。我們發掘出一種稱為「局部一致性」的一致性， 並利用其來加快處理從物體上所發射的光線的速度。基於「局部一致性」，我們設 計了一個新的階層圍搜尋法來減少此種光線與「物體圍」測試相交的數目；我們所 提出的是一種結合「由上而下」與「由下而上」的階層圍搜尋法。其次，利用「區 域一致性」，我們提出了一個「平面掃描法」來降低視線與物體圍測試相交的數目 。我們的演算法平均可縮短光線追蹤法的執行時間達15﹪－30﹪。 在第二個研究裡，我們將「漸進式改良法」應用於「光線投射立體資料描繪演算法 」。我們將三度空間資料放在一個完全的「八分樹」中，用以實現「物體一致性」 。當要描繪立體資料時，我們根據一使用者給定的特定值，用光線投射法來搜尋此 立體資料的八分樹。隨著逐漸地降低此一特定值，我們可以畫出愈見修飾的圖像。 我們並提出一稱之為「樣品暫存器」的資料結構，來儲存在漸進改良過程中所得到 的部份結果，用以降低描繪一連串逐步修飾的圖像所需的時間。藉著本方法，我們 可以在影像品質和計算時間二者之間獲得滿意的平衡點。 最後，我們根據兩個新的概念提出了一個快速的立體資料描繪演算法。首先，不同 於往用獨立的方法求取每個樣品的值，我們可以利用累加的方法求得一連串樣品的 值；我們把這個特性稱為「樣品值的一致性」。其次，為了實現「平行投影的一致 性」，我們建立了一些模版，用以儲存共有的資訊。當要描繪一立體資料時，我們 可以直接從一個適當的模版中取得需要的資訊，而無需重覆複雜的計算。我們的演 算法可以增快產生立體資料圖像的速度達２－３倍。