有效率的等值面產生法

Abstract

在三度空間等值面的尋找方法，文獻上已有了許多方法．而其中最有名的 即為 marching cube。此法雖然非常簡單，但是卻有許多問題。在本論文 中，我們將提出一個有效率的等值面求法．這個方法利用一改良過的 branch-on-need八元樹並略過不含等值面的區域，且在產生三角形的同時 ，根據一些條件將鄰近的三角形結合起來以減少產生的三角形個數．為了 減少建立八元樹所需之空間，我們亦提出一減少空間的八元樹。因此，此 方法將更有效率且需要較少的空間．此外，為了分散等值面產生所需的運 算，我們結合了一種平行運算的軟體 PVM至我們的方法中，經由動態工作 的分配，我們將使網路上各機器的工作量平均，而減少整個工作處理的時 間． An efficient method to extract an isosurface in the volume data is proposed. The method utilizes a modified branch-on-need octree to bypass regions of no current interset. Neighboring triangles are merged according to some criteria during the generation of triangle meshes. Method are also given to obtain a significant reduction of the space requirement for octrees. Consequently, the method is much more efficient and generates much less triangles than marching cube algorithm. The proposed method is implemented and its performance is compared to other existing methods, thus as marching cube, branch-on-need octree approach, and splitting box algorithm. Distributed computation of the proposed method is also implemented using PVM. With the dynamic load balancing scheme, the experimental implementation shows an effective reduction of the computation time.