计算机应用
計算機應用
계산궤응용
Journal of Computer Applications
2015年
9期
2611-2615
,共5页
郭洪帅%孙殿柱%李延瑞%李聪
郭洪帥%孫殿柱%李延瑞%李聰
곽홍수%손전주%리연서%리총
STL文件格式%K维树%半边结构%曲面拓扑重建%k-近邻查询
STL文件格式%K維樹%半邊結構%麯麵拓撲重建%k-近鄰查詢
STL문건격식%K유수%반변결구%곡면탁복중건%k-근린사순
Stereo Lithography (STL) file format%K-Dimensional Tree (KD Tree)%half-edge data structure%surface topology reconstruction%k-neighborhood query
针对STL文件格式存在网格顶点数据冗余以及缺乏面片邻接信息等缺陷,提出一种基于多维动态空间索引的显式曲面拓扑重建算法,在消除网格顶点数据复本的过程中逐步构建网格曲面顶点的KD树,通过该索引提高顶点数据复本消除效率,并基于KD树叶节点层数据存储的开放性融入半边数据结构,实现曲面拓扑结构的快速重建.最后,对6个不同规模的数据模型进行实验:与采用R*-Tree、数组、散列表作为索引等方法相比,所提出的KD树与半边结构融合的动态空间索引在处理近百万面片的数据文件时,去除冗余顶点用时11.93 s,拓扑重建仅仅需要2.87 s,大大减少了冗余顶点的去除时间和拓扑重建时间,并且有效支持网格曲面拓扑邻域信息的快速查询,查询时间在1 ms之内,远小于对比算法所用时间.实验结果表明:所提算法能够提高网格曲面冗余顶点去除效率和拓扑重建效率,实现网格曲面拓扑邻域信息的快速查询.
針對STL文件格式存在網格頂點數據冗餘以及缺乏麵片鄰接信息等缺陷,提齣一種基于多維動態空間索引的顯式麯麵拓撲重建算法,在消除網格頂點數據複本的過程中逐步構建網格麯麵頂點的KD樹,通過該索引提高頂點數據複本消除效率,併基于KD樹葉節點層數據存儲的開放性融入半邊數據結構,實現麯麵拓撲結構的快速重建.最後,對6箇不同規模的數據模型進行實驗:與採用R*-Tree、數組、散列錶作為索引等方法相比,所提齣的KD樹與半邊結構融閤的動態空間索引在處理近百萬麵片的數據文件時,去除冗餘頂點用時11.93 s,拓撲重建僅僅需要2.87 s,大大減少瞭冗餘頂點的去除時間和拓撲重建時間,併且有效支持網格麯麵拓撲鄰域信息的快速查詢,查詢時間在1 ms之內,遠小于對比算法所用時間.實驗結果錶明:所提算法能夠提高網格麯麵冗餘頂點去除效率和拓撲重建效率,實現網格麯麵拓撲鄰域信息的快速查詢.
침대STL문건격식존재망격정점수거용여이급결핍면편린접신식등결함,제출일충기우다유동태공간색인적현식곡면탁복중건산법,재소제망격정점수거복본적과정중축보구건망격곡면정점적KD수,통과해색인제고정점수거복본소제효솔,병기우KD수협절점층수거존저적개방성융입반변수거결구,실현곡면탁복결구적쾌속중건.최후,대6개불동규모적수거모형진행실험:여채용R*-Tree、수조、산렬표작위색인등방법상비,소제출적KD수여반변결구융합적동태공간색인재처리근백만면편적수거문건시,거제용여정점용시11.93 s,탁복중건부부수요2.87 s,대대감소료용여정점적거제시간화탁복중건시간,병차유효지지망격곡면탁복린역신식적쾌속사순,사순시간재1 ms지내,원소우대비산법소용시간.실험결과표명:소제산법능구제고망격곡면용여정점거제효솔화탁복중건효솔,실현망격곡면탁복린역신식적쾌속사순.
