CSG Solids 的快速多邊形化

Abstract

本論文中, 我們提出一個新的方法直接對 CSG 實體表面做多邊形化。在 此方法中, 我們先將實體空間利用 CSG tree 中的每一個 primitive的 S-bound 和樹的內點的 S-bound 作切割, 得到一個樹狀空間階層。此空 間分割法能使其 voxel 具最小的 localized CSG tree, 如此可大量減少 分類的時間。接著對切割後的每一個子空間做分類, 若此子空間與 CSG 實體表面相交, 我們就對此子空間做多邊形化。對這些相交的子空間 , 我們利用 marching cube 中的 surface tracking 技巧使得我們只對那 些被 CSG 實體經過的小 cells 做多邊形化。對於 CSG 實體表面與 cell 邊線的交點與法向量的尋找上, 我們捨棄以往所用的內插法, 直接 找尋此點所在的 primitive 來算, 可以得到較精確的結果。 An efficient method to render the CSG solids is proposed. In this thesis, we proposed a method that polygonize a CSG solid directly on its boundary face. The procedure employes marching cube algorithm on a regular grid that covers the object space, which is subdivided based on S-bound of internal nodes and primitives of the CSG tree. Among leaf voxels of the space subdivision, only voxels that overlap with the boundary of solid are tracked. And the surfce-edge intersection and vertex normal, which are usually interpolated in the standard marching cube algorithm, are computed directly from the exact boundary surface of the CSG solid.