使用鏈碼於二維及三維物體之多重解析度表達及漸進式圖形顯示

Abstract

在電腦應用領域，如電腦輔助工件製造，物體碰撞偵測，物體分類，以及網路上的物體瀏覽等等中，物體的幾何形狀必須加以數學性的描述，以及圖形顯示。在本論文中，將處理使用串聯碼於二維及三維物體之多重解析度表達及漸進式圖形顯示。特別是用於網路環境中的電腦上，具多重解析度表達能力之物體瀏覽及比對。本研究所考慮的因素主要為包括網路資料傳輸以及圖形顯示在內的運算時間﹔能夠在不同的解析度下做顯示﹔以及較次要的因素：所需要的記憶體空間。 在本論文的第一個部份中，提出一種為有效率的網路瀏覽之黑白物體的遞迴式表示法以及漸進式顯示，可用於描述了一個凸或凹多邊型物體的表示及顯示。同時，物體模型在旋轉，放縮，平移下的修正方式。一般而言，我們的方法比起許多現有的方法，在資料傳輸率，漸進式顯示的能力，以及在R/S/T 變動下的觀視修正。模擬結果顯示我們的方法的效能較佳。 第二個部份中，提出一種簡單的使用對照表來將串連碼轉換成四分樹的遞迴式轉換法。這種對照表方法之設計是用以加速黑色四分樹節點以及新的串連碼元件的轉換。研究結果顯示我們的方法在觀念上較簡潔，而且執行較快。 第三個部份中，描述了一種用來將一組串連碼轉換成八分樹的遞迴式轉換法。主要描述了在串連碼的循跡中，如何產生旗號，以及如何由旗號的傳播來決定黑色八分樹節點的產生。定理的研究指出我們的方法在主要因子上的執行時間比其他方法來得快。

In computer applications such as computer–aided part manufacturing, object collision detection, object classification, and object browsing on the network, the geometric shape of objects must be mathematically represented and graphically rendered. In this dissertation we deal with the generation of multi-resolution geometric models and progressive graphic display of 2D/3D objects using chain code representation. We are concerned with object browsing and matching with a capability of multi-resolution representation of the object on computers, especially in a network environment. The consideration factors of the research are mainly the processing time including the network data transmission and the graphic display, the availability of different levels of detail for display, and the last and less important factor of memory storage size. In the first part of this dissertation, we present a recursive representation and progressive display of binary objects for efficient network browsing. We describe the representation and display of a convex and/or a concave polygonal object. Also, the object model modification under rotation, scaling, and translation variations is described. Our method is generally better than many existing methods in terms of data transmission rate, progressive display capability, and view modification under R/S/T variations. Simulation results are provided to illustrate the performance of our method. In the second part, we present a simple recursive method for converting a chain code into a quadtree with a lookup table. The table lookup method for generating the quadtree black nodes and the new chain code elements is designed to speed up the conversion process. The result indicates that our method is conceptually simpler and runs faster. In the third part, a recursive method for converting a set of chain codes into an octree is proposed. We describe the generation of the flags when tracing the chain codes, and the flag propagation for the generation of octree black nodes. Our conversion method runs faster than other method in terms of the total execution time of major operations, as indicated by the lemmas.