Advisor: Prof. Chin-Shyurng Fahn

TEL: 02-2733-3141 # 7425

Location: RB307-3

Designer: Yu-Ta Lin

H. K. Chen, C. S. Fahn , J. P. Tsai, R. M. Chen, and M. B. Lin, “A Linear Time Algorithm for High Quality Mesh Simplification,” in Proc. of the 6th Int. Symp. on Multimedia Software Eng. , Miami , Florida , U. S. A., pp. 169-176, 2004.

  為了有效簡化由數百萬個以上的頂點與數十萬個以上的平面所構成的大型三維物件,我們提出一個能在線性時間複雜度完成的演算法,它不僅可達到即時快速的需求且能符合高品質的繪圖效果。此演算法係以管線(pipeline)的處理方式執行簡化誤差代價計算、最佳簡化頂點選擇,以及邊線縮減(edge collapse)三個程序,其中選取頂點的動作是採用一個固定容量的小型最小值堆積(min-heap)所完成,它有別於一般大型的貪婪佇列(greedy queue),因而能將演算法的時間複雜度降低至線性的等級。

 

註:H. K. Chen (陳宏光) 為申請人與本校電子系M. B. Lin (林銘波) 教授共同指導的博士班研究生 (民國95年1月畢業);J. P. Tsai (蔡進發)為亞洲大學資訊與設計學系講座教授,而R. M. Chen (陳榮銘) 為亞洲大學資訊與設計學系副教授。