增強型α-Shapes之幾何重建

這幾年來，虛擬實境與網路多媒體技術的搭配應用相當地普遍。對於這類的3D的物體模型，往往是利用一堆可參數化的數學模組來組合出所需要的模型；而反相工程就是一個可以做出這些模型的新方法。反相工程即是對現實生活中的物體模型，利用雷射掃描或斷層掃描來擷取模型表面上的頂點，再根據演算法來將所取得的頂點之間的關係重新建立，即可得到最後的模型資料。藉由這個方式可以有很多的優點。方法很簡單而且儲存空間也很小；而且在網際網路上的使用上也很適合。目前在使用反相工程來重建點和點之間的關係上的速度仍是個瓶頸。α-Shapes是反相工程中的一個舊方法，在本篇研究中，我們提出一些方法來增進它的效能。一開始，先得到每個點上頭的鄰近點資訊。而且用全部的邊長來估算不合理的三角片，再用Delaunay test來測試剩餘的三角片我們將此方法與原有的α-Shapes演算法作實例比較，在刪除率上面比原方法優異，同時我們針對各種不同的三度空間幾何模型進行重建，平均的刪除率大約為45﹪左右，有些模型甚至可以達到62﹪以上。至於速度方面，由於我們的演算法是在原先的演算法上外加判斷，所以重建的部分所花費的時間均會比原先的演算法多一些，但是速度上仍是很快，這是因為原先的演算法加上我們修正的部份，其演算法十分簡單，也不至於浪費太多的記憶體空間，因此在模型重建上，可以獲得正確而更少三角片的模型。

關鍵字

電腦繪圖；幾何圖形；幾何重建；反相工程

並列摘要

It is popular for application to combine virtual reality and network multimedia technique. The 3D geometry models are used in such applications. It is difficult to build mathematical models by human. The Reverse-engineering is a new method to build 3D models. The vertices of surfaces is got from the realistic object model by laser scan or CT(Computed Tomography) slice. The relationship between vertices are built by algorithm. Therefore, there are many advantages within such a models. It is simple and occupies a little storage space. It is suitable for Internet transmission. It is still a bottleneck for using the Reverse-engineering to reconstruct relationship between vertices quickly. The α-Shapes is an old method for it. In this study, we propose some methods to improve its efficiency. First, the nearby information is built for each point. The total edge length is used to eliminate invalid triangles. The Delaunay test is instead by these two steps. We present our algorithm to compare with original algorithm. On the ratio of triangle deletion, we get better value. And we use a lot of different kinds of 3D geometry model to do reconstruction, the radio of triangle deletion is about 45%, on some models can be more that 62%. As to reconstruct speed, because our algorithm add some determined factors from original algorithm, the execute time will be more than the execute time of original algorithm. But the speed is still fast than other algorithm. That is because our algorithm that combines original algorithm and our determined factor is very simple, and it does not need to waste many memory space. So in the part of model reconstruction, we can get the correct and least triangles model data.

並列關鍵字

Computer Graphics ； Geometry Object ； Geometry Reconstruction ； Reverse Engineering

參考文獻

[1] A. Fischer, A. Manor, Y. Barhak, “Adaptive Parameterization for Reconstruction of 3D Freeform Objects from Laser-Scanned Data. ” IEEE Computer Graphics and Applications, 1999. Proceedings. Seventh Pacific Conference, Page(s): 188 –197, 1999

[3] Benjamin F. Gregorski, Bernd Hamann, and Kenneth I. Joy. “Reconstruction of B-spline Surfaces From Scattered Data Points.” IEEE Computer Graphics International, 2000. Proceedings , Page(s): 163 -170, 2000

[7] Franz Aurenhammer, “Voronoi Diagrans – A Survey of a Fundamental Geometric Data Structure. ” ACM Comput. Surv. 23, 3 (Sep. 1991), Pages 345 – 405, 1991

[10] Jean-Daniel Boissonnat, Frédéric Cazals. “Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions. ” ACM Proceedings of the sixteenth annual symposium on Computational geometry, Pages 223 - 232, 2000

[11] Marek Teichmann and Michael Cappsm, “Surface reconstruction with anisotropic density-scaled alpha shapes.” ACM Proceedings of the conference on Visualization '98, Pages 67 – 72, 1998

國際替代計量

增強型α-Shapes之幾何重建

未授權

主題瀏覽