- 學位論文
於光跡追蹤法中改良區塊航行演算法之研究
A Study on Improved Grid Traversal Algorithm for Ray Tracing
摘要
在加速光跡追蹤法的方式中，以空間切割法的使用最為常見，而空間切割法主要又可區分為兩類：一致性與非一致性的空間切割。在一致性空間切割法中，由於整個場景空間被切割成大小一致的區塊，因此可以使用3D DDA的方式來加速光射線與物體的交點測試。 早期在光跡追蹤法上，用來加速光射線航行的3D DDA方式是延伸自平面上的DDA畫線方法，因此在本論文中將從平面上DDA的畫線方式進行研究探討，接著再從現有的3D DDA方法進行探討，最後結合研究後的結果，提出一個改良型的區塊航行法，並將此方法與現有的3D DDA方式進行比較。 另外由於高密度的一致性空間切割法會佔用相當大的記憶體使用量，因此發展出使用階層式架構的方式來減少記憶體的使用量。針對這方面，本論文也將提出一個簡化型的階層式架構，並配合所提出的改良型區塊航行法，運用在高密度的一致性空間切割環境中，以提升光射線的航行速度，並減少記憶體的使用量。 因此，在本論文中除了提出一個改良型的區塊航行法之外，同時並提出一個搭配此改良型航行法之簡化型階層式架構，以期提升光跡追蹤法的效能與品質。
並列摘要
The spatial subdivision is the most popular method to accelerate ray tracing. The subdivision strategies can separate into two schemes, uniform and non-uniform spatial subdivision. In uniform spatial subdivision, the scenes space divided into many regular grids, so it can use 3D DDA to accelerate ray and object intersection testing. First, in the ray tracing, the 3D DDA that used to accelerate ray traversing is extended from DDA that draw line in the plane. In this paper, we will study on the vary methods of DDA and 3D DDA, and analysis the result of these studies, then introduce a improved grid traversal method. This method will compare with existing 3D DDA method. In addition, because the highly resolution uniform spatial subdivision have used large memory consumption. So the hierarchical structures were developed to reduce memory consumption. In this aspect, we will also introduce a simply hierarchical structure and collocate our improved grid traversal method to speed up ray traversing and reduce memory consumption in this highly resolution spatial subdivision environment. In this paper, besides introducing a improved grid traversal method, we also introduce a simply hierarchical structure that collocate our grid traversal method. We will use these methods to improve the ray tracing quality and efficiency.