基于多維動態(tài)空間索引的顯式曲面拓撲重建算法

　　針對STL文件格式存在網(wǎng)格頂點數(shù)據(jù)冗余以及缺乏面片鄰接信息等缺陷，提出一種基于多維動態(tài)空間索引的顯式曲面拓撲重建算法，在消除網(wǎng)格頂點數(shù)據(jù)復(fù)本的過程中逐步構(gòu)建網(wǎng)格曲面頂點的KD樹，通過該索引提高頂點數(shù)據(jù)復(fù)本消除效率，并基于KD樹葉節(jié)點層數(shù)據(jù)存儲的開放性融入半邊數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)曲面拓撲結(jié)構(gòu)的快速重建。最后，對6個不同規(guī)模的數(shù)據(jù)模型進行實驗：與采用R -Tree、數(shù)組、散列表作為索引等方法相比，所提出的KD樹與半邊結(jié)構(gòu)融合的動態(tài)空間索引在處理近百萬面片的數(shù)據(jù)文件時，去除冗余頂點用時11. 93 s，拓撲重建僅僅需要2. 87 s，大大減少了冗余頂點的去除時間和拓撲重建時間，并且有效支持網(wǎng)格曲面拓撲鄰域信息的快速查詢，查詢時間在1 ms之內(nèi)，遠小于對比算法所用時間。實驗結(jié)果表明：所提算法能夠提高網(wǎng)格曲面冗余頂點去除效率和拓撲重建效率，實現(xiàn)網(wǎng)格曲面拓撲鄰域信息的快速查詢。