Advisor: Prof. Chin-Shyurng Fahn

TEL: 02-2733-3141 # 7425

Location: RB307-3

Designer: Yu-Ta Lin

H. K. Chen, C. S. Fahn , and M. B. Lin, “The Storage Independent Polygonal Mesh Simplification System,” Accepted to publish in Lecture Notes in Computer Science and also to appear in Proc. of the 12th Int. Conf. on Human-Computer Interaction , Beijing, China , 2007.

  我們創新地發展一套與儲存體不相依的(storage independent)多邊形網格化簡系統,它可劃分為資料管理與演算兩層,其中資料管理層負責記憶體的配置與管理,並提供一組與儲存裝置不相依的存取指令給演算層的演算使用。假如演算層的記憶體需求小於現存的記憶體大小時,則資料管理層會自動將資料配置於主記憶體中,並進行高效能的內核式(in-core)操作;反之,當演算層的記憶體需求超出現存的記憶體大小時,則資料管理層將自動進行外核式(out-of-core)的操作,並利用現有的記憶區塊做為快取緩衝區(cache buffer),以有效提高外部記憶體存取的效率。藉由此一資料存取的抽象化,我們可以將大多數的多邊形網格化簡演算法(包括內核式與外核式)移植到所提的化簡系統中。 除了可將已有的內核式演算法自動拓展成外核式的操作,以處理巨量多邊形網格的高解析度物件外,傳統的外核式演算亦可透過記憶體管理層的快取緩衝區來提高外部存取的效能。另外,我們也可利用此系統進行兩階段甚至多階段式的演算法耦合。為驗證系統的有效性,我們實作三種不同類型的演算方式:第一種為傳統內核式之最著名的遞迴式邊緣縮減的演算,我們係以先前發表的一個線性時間複雜度的演算法為例;第二種為傳統的外核式操作的演算,這裡我們移植的是一個知名的均格點篩式(uniform-grid vertex-resampling)演算法(此為Lindstrom等人所提出);第三種類型的演算則為第一種與第二種類型演算的耦合。由於此系統可限定記憶體的需求為一個常數值,它能自動切換內核式與外核式的操作,並提供快取緩衝區以加速外核式的操作,吾人相信此系統為一個相當成功的多邊形網格化簡平台。

 

註:本文收錄於EI與SCI; H. K. Chen (陳宏光) 為申請人與本校電子系M. B. Lin (林銘波) 教授共同指導的博士班研究生 (民國95年1月畢業)。