一種多通道八叉樹模型的研究

一種多通道八叉樹模型的研究

1線性八叉樹/點線下結(jié)構(gòu)優(yōu)化采用分段樹型，四叉樹三維延伸。在體圖形學領(lǐng)域，作為一種有效三維實體模型，八叉樹是體素模型的壓縮和改進。許多學者對八叉樹的原理與應(yīng)用、遍歷與查詢、壓縮與漸進傳輸、指針八叉樹與線性八叉樹編碼，以及體繪制等方面進行了廣泛而深入的研究。八叉樹模型的編碼和實現(xiàn)方式主要有常規(guī)/指針八叉樹、線性八叉樹(linearoctree）、深度優(yōu)先(depthfirst,DF)編碼和三維行程編碼，后兩者的空間壓縮效率較高，但由于訪問效率方面的原因，實際中的應(yīng)用并不多見。指針八叉樹是一種顯式實現(xiàn)方式，它采用一組指針建立結(jié)點及其父子之間關(guān)系，最終形成一種樹狀結(jié)構(gòu)，其查詢過程可以看作是根據(jù)給定條件在樹上進行一系列條件判斷和指針選擇的過程。指針八叉樹的優(yōu)勢是查詢效率高，主要得益于內(nèi)存指針高效的隨機訪問特性，但大量內(nèi)存指針也浪費了存儲空間。線性八叉樹主要面向結(jié)點數(shù)據(jù)壓縮，它僅保存葉結(jié)點，每個葉結(jié)點中存儲了屬性和空間位置兩部分信息。在線性八叉樹上進行查詢可以看作是根據(jù)給定Morton碼進行遍歷和一系列Morton碼比較的過程。與指針八叉樹相比，線性八叉樹的結(jié)點查詢效率較低。后者的另一個不足是查詢過程與存儲順序相關(guān)，當八叉樹結(jié)構(gòu)發(fā)生變化后，需要重新排序，這在實際應(yīng)用中受到很大限制。無論采用哪種編碼方式，八叉樹結(jié)點的查詢過程可以看作兩個步驟：以線性八叉樹為例，首先根據(jù)查詢條件求解目標結(jié)點的八叉樹坐標，即Morton碼；然后根據(jù)這個Morton碼查找結(jié)點的實際存儲位置。前者可以看作理論坐標查詢，后者是實際存儲位置查詢。對于指針八叉樹而言，第1步是隱式的，體現(xiàn)在條件判斷和指針選擇上，第2步比較明顯和直觀，根據(jù)指針直接定位到實際存儲位置。2虛擬八叉樹模型多級線性結(jié)構(gòu)是虛擬八叉樹模型的基礎(chǔ)，在此之上，利用規(guī)則分塊方式進行數(shù)據(jù)壓縮和建立索引，最終實現(xiàn)虛擬八叉樹模型。線性八叉樹模型將八叉樹所有層級的葉結(jié)點混在一起，按照Morton碼從小到大的順序依次存儲，因此，整體上呈一種線性排列關(guān)系。與之相比，本文提出的虛擬八叉樹模型采用了分層存儲策略，如圖1所示。分層存儲策略將八叉樹上的所有結(jié)點分層處理，每層結(jié)點（空、灰和實結(jié)點）分別按照Z-Order順序（即Morton碼從小到大的順序）進行存儲。因此，虛擬八叉樹模型的理論基礎(chǔ)是一種金字塔狀的多級線性結(jié)構(gòu)，每一級分別對應(yīng)一個一維線性存儲空間。新模型可以表示如下：在圖1中，中間是Z-Order(N-Order,MortonOrder或Lebesgue)曲線，它的作用是將三維分布的體元映射到一維存儲空間。在每個層次i上，結(jié)點的Morton碼的取值范圍是0～8i-1ㄢ多級線性結(jié)構(gòu)具有以下優(yōu)勢：(1)結(jié)點中不必包含指針和Morton碼信息，結(jié)點之間的空間關(guān)系隱含在存儲順序中。(2)利用二進制運算可以快速實現(xiàn)格網(wǎng)坐標和Morton碼（十進制，下文同）之間的快速轉(zhuǎn)換。(3)父/子結(jié)點的Morton碼之間存在簡單的乘/除八關(guān)系，同樣可以用二進制運算快速實現(xiàn)。(4)臨域查詢和子結(jié)點查詢的Morton碼計算同樣高效。假設(shè)當前結(jié)點的Morton碼為M，則(5)結(jié)點的Morton碼就是該結(jié)點在相應(yīng)的一維空間中的下標，即結(jié)點的理論坐標和實際存儲位置之間存在簡單的對應(yīng)關(guān)系；以第2～第4條為基礎(chǔ)，可以實現(xiàn)快速的結(jié)點查詢。圖1所示的理論模型具有很高的查詢效率，但這是以存儲空間為代價的，并沒有考慮任何數(shù)據(jù)壓縮，其實質(zhì)是滿樹結(jié)構(gòu)。而空結(jié)點和均質(zhì)結(jié)點合并是八叉樹的優(yōu)勢，因此，虛擬八叉樹模型必須進行編碼和改進。無論采用哪種編碼，結(jié)點合并就意味著實際存儲位置發(fā)生變化，不同的八叉樹編碼方法采用不同的策略來建立理論位置和存儲位置之間的聯(lián)系。如上文所述，線性八叉樹模型采用葉結(jié)點中存儲Morton碼的方式，指針八叉樹模型采用父子指針的方式。與指針八叉樹和線性八叉樹不同，虛擬八叉樹模型以規(guī)則分塊為基礎(chǔ)進行編碼，不僅實現(xiàn)了高效的壓縮，而且實現(xiàn)了高效的查詢。同時，虛擬八叉樹模型還繼承了圖1中的一個優(yōu)勢，即結(jié)點中不必包含任何指針或Morton碼信息，節(jié)省了存儲空間。新模型中的結(jié)點結(jié)構(gòu)定義如下：實際應(yīng)用中，將所有屬性值進行分級，利用各屬性分級與屬性值之間的映射表就能夠滿足要求。特殊情況，可采用Short、Long或更長的數(shù)據(jù)類型，前提是結(jié)點記錄大小一致。3x-q-qp-ro》收率及核心條件設(shè)置按照圖1所示的分層存儲與多級線性結(jié)構(gòu)，以規(guī)則分塊為基礎(chǔ)，虛擬八叉樹模型針對每一層或每個一維存儲空間進行數(shù)據(jù)壓縮，并建立索引。在此引入一個概念——塊因子，即分塊大小或其中的結(jié)點個數(shù)。需要指出的是，各層之間互相獨立，可以采用不同的塊因子以實現(xiàn)最佳壓縮效率。以圖2所示的某個八叉樹的第5層為例，對基于規(guī)則分塊的壓縮和結(jié)點查詢機制進行說明：塊因子為512，如圖2右邊部分；共劃分成64個分塊，如圖2左邊部分。所有分塊按照Z-Order順序保存成一個一維索引表，表中的各個索引項與分塊相對應(yīng)。如果某個塊是空塊，則設(shè)置相應(yīng)索引項為-100；如果某個塊是均質(zhì)塊，則設(shè)置相應(yīng)索引項為-i,i代表該塊所屬的最大均質(zhì)結(jié)點的所在層級；如果某個塊是灰塊，則將該塊中的所有結(jié)點按照Z-Order順序保存到一個一維存儲空間，并設(shè)置相應(yīng)的索引項為該存儲空間的起始位置或內(nèi)存指針。圖3顯示了結(jié)點查詢的基礎(chǔ)——Morton碼的二進制分解，其分解位置與塊因子有關(guān)，以圖2為例，塊因子512，因此，Morton碼的分解位置為9ㄢ由于索引項和結(jié)點都按照Z-Order順序進行保存，因此分解后左半部分的值就指向了該結(jié)點所屬的分塊或索引項；而右半部分的值則指向了該結(jié)點在所屬分塊中的位置。具體查詢過程如下：下面對新的壓縮和查詢機制進行分析，具體測試結(jié)果參照第4節(jié)。新機制在數(shù)據(jù)壓縮方面涉及兩個層次：(1)對空塊和均質(zhì)塊進行壓縮與標記，節(jié)省了存儲空間；(2)對于灰塊，將其所有結(jié)點依Z-Order順序存儲，保持了塊的規(guī)則性，不僅有利于提高查詢效率，而且可以避免在結(jié)點中保存位置碼或指針信息?？梢钥闯?，在第(2)個層次：灰塊中的空結(jié)點和均質(zhì)結(jié)點浪費了存儲空間；無位置碼/無指針的結(jié)點結(jié)構(gòu)則節(jié)省了存儲空間。如概述部分所述，高效的內(nèi)存指針運算使指針八叉樹結(jié)構(gòu)具有很高的查詢效率，但需要進行逐級比較和指針選擇。與之相比，虛擬八叉樹模型的查詢機制以效率同樣高效的一維數(shù)組運算為基礎(chǔ)，并且數(shù)組訪問和比較運算的次數(shù)通常要少于指針八叉樹。4壓縮效率的測試StanfordBunny由35947個頂點和69451個三角形組成。由于研究的是實體內(nèi)部非均質(zhì)屬性建模，因此需要利用實體體素化算法和PerlinNoise算法進行處理，以得到測試用的真三維體數(shù)據(jù)(5123)，如圖4所示。該實例在均質(zhì)條件下具有1803562個八叉樹結(jié)點，在完全不均質(zhì)條件下有31283107個八叉樹結(jié)點。圖5是虛擬八叉樹模型與指針八叉樹在查詢效率方面的測試：左邊是遍歷查詢；中間是62萬次隨機查詢；右邊是62萬次鄰域查詢?？梢钥闯觯摂M八叉樹與指針八叉樹的查詢效率相當。在鄰域查詢方面甚至優(yōu)于后者，原因主要在于虛擬八叉樹模型在鄰域結(jié)點Morton碼計算、根據(jù)Morton碼查找實際位置這兩個過程的簡單和高效，而指針八叉樹需要按照鏡面反射方式進行逐層比較和訪問，效率相對較低。圖6是虛擬八叉樹與線性八叉樹在空間壓縮效率方面的測試結(jié)果。為了得到空間壓縮效率隨屬性分布的變化規(guī)律，定義一個屬性均質(zhì)系數(shù)P來衡量實體內(nèi)部屬性的均質(zhì)性：其中，P為均質(zhì)系數(shù)，范圍0.0～1.0;N為八叉樹結(jié)點個數(shù)；Nmin為完全均質(zhì)的八叉樹結(jié)點個數(shù)；Nmax為完全不均質(zhì)的八叉樹結(jié)點個數(shù)。在圖6的測試數(shù)據(jù)中，線性八叉樹的結(jié)點長度為7字節(jié)(4字節(jié)位置碼，1字節(jié)層號和兩字節(jié)標志和屬性)；虛擬八叉樹的結(jié)點長度為2字節(jié)（標志和屬性），塊索引項4字節(jié)。圖中的格網(wǎng)模型只是用作參考，其分辨率是5123，每個單元占用1字節(jié)。測試平臺：CPUAMD2500+,RAM1GBDDR,GPUGeForce5200ㄢ本文選擇從完全均質(zhì)（P=0.0）到完全不均質(zhì)（P=1.0）等7種情況進行測試。對于每種情況，又分別采用7種塊因子(8,32,64,128,256,512,1024)進行壓縮，并將最小值及其對應(yīng)的最優(yōu)塊因子顯示在圖6中。測試數(shù)據(jù)表明：(1)隨著屬性不均質(zhì)性的提高，最優(yōu)塊因子逐漸增大；(2)隨著屬性不均勻性的提高，線性八叉樹的存儲空間增長很快，而虛擬八叉樹模型增長緩慢，后者的優(yōu)勢逐漸明顯，最終趨向于一個定值。與三維格網(wǎng)所占空間相比，這個定值也反映了物體在整個外包中所占的比例。需要補充兩點：(1)圖6中虛擬八叉樹模型的數(shù)據(jù)已經(jīng)包含了索引結(jié)構(gòu)所占用的空間，而線性八叉樹模型并沒有包含索引數(shù)據(jù)。(2)不同的塊因子會對存儲效率產(chǎn)生影響，對結(jié)點查詢效率基本不產(chǎn)生影響。原因在于不同的塊因子只帶來Morton碼分解位置的不同，而索引結(jié)構(gòu)、查詢機制和過程都沒有發(fā)生