有效率的立體資料描繪演算法

Abstract

本論文提出兩種快速的立體資料(Volume Data)描繪方法。 就描繪規則性資料而言，最常運用的方法有兩類，其中之一是 Surface-extraction，另 一類則是Direct Volume Rendering，而Ray-casting與Marching Cubes分 別為此 兩類方法的代表。為改善這兩種方法的缺點，首先我們提出 Analytic Isosurface Rendering， 此法是在Cell中定義一個Density Distribution，以三次可解析方程式來 求得 Surface，再以此法為基礎， 提出數個加速的技巧，而成為一個兼顧描繪品質和速度要求的Algorithm 。我們 將此Algorithm應用在兩方面， 一是延伸到不規則資料上，發展出一個快速的描繪法，其中同時也對Cell 邊界 連續的問題加以討論；二是用來解 決Marching Cubes法所產生的Topological Inconsistency的問題，使得 資料 即使經過Supersampling之後，仍然維持Topology的一致性。 在本文的第二部分，我們提出一個更有效率的Two-Pass轉換矩陣分解法。 轉換矩陣分解不僅可讓轉換適合在 Parallel Machine執行，而且在單一處理器上也可發展為快速的描繪法。 我們提出的方法能在短短的數秒之間， 完成一張立體資料的描繪影像，提高了立體資料描繪的實用性。 Volume rendering algorithms and related problems are studied in this dissertation. We shall present a new approach, namely {\bf analytic isosurface rendering} which is an algorithm integrating the marching-cubes and ray casting methods. We define a density function for each cell and the isosurface is formed when a threshold is given. By this definition, an isosurface can be derived by solving an equation of degree three for each image pixel. Several speedup techniques are also provided based on this approach and thus a fast algorithm is produced. The analytic isosurface approach solves other problems in voulme rendering. First, it solves the ambiguity problem and the topological inconsistance problem in marching cube method. Then we show that it can be extended to process irregular volume data. Besides, we present another efficient volume rendering algorithm based on a two-pass transformation. It has been shown that a rotation transformation can be factorized into two passes so that each pass can be carried out efficiently. We present another way to factorize a rotation matrix and compare it to a previous fast method. The two-pass method renders volume data in few seconds and made volume rendering more practical.