王育堅，許承福，劉立平

(北京聯(lián)合大學信息學院，北京 100101)

建筑物是城市中的主要地物，建筑物三維建模是計算機圖形學、地理信息系統(tǒng)、攝影測量學及其相關學科研究的熱點，并在虛擬現(xiàn)實、復雜場景設計、計算機視覺和三維GIS等領域得到了廣泛應用［1-2］。建筑物三維建模方法直接影響到城市三維可視化的速度和效果，如何快捷、逼真地構建建筑物三維模型是很多研究人員重點研究的課題。筆者在分析了多種三維空間數(shù)據(jù)模型的基礎上，針對建筑物的結構特點，提出了一種基于八叉樹和NURBS的混合三維數(shù)據(jù)模型。

1 三維空間數(shù)據(jù)模型

空間數(shù)據(jù)模型是在實體概念的基礎上發(fā)展起來的。近年來，國內外很多學者對三維空間數(shù)據(jù)模型理論和應用進行了深入的研究，提出了多種三維空間數(shù)據(jù)模型建模方法［3-4］。按照模型的存儲元素類型分類，三維空間數(shù)據(jù)模型可分為柵格數(shù)據(jù)模型、矢量數(shù)據(jù)模型、柵格和矢量混合模型3類。按照模型的構成元素分類，三維空間數(shù)據(jù)模型可分為基于面元的模型、基于體元的模型和面元體元混合模型3類。

基于面元的模型是利用微小的面元素來描述空間實體的幾何形態(tài)，通過表面表示形成實體的三維空間輪廓?；诿嬖哪Ｐ桶ǜ窬W(Grid)、不規(guī)則三角形格網(TIN)、線框(Wire Frame)、邊界表示(Boundary Representation)、斷面(Section)和參數(shù)函數(shù)表示(Parameter Function)等。其中，基于三角形格網的模型已成為三維空間數(shù)據(jù)建模的通用方法。

基于體元的模型是以基本體元分割空間實體，將三維空間實體抽象為一系列鄰接但不交叉的三維體元的集合，通過對體元的描述實現(xiàn)三維實體的空間表示?；隗w元的模型包括四面體格網(TEN)、八叉樹(Octree)、結構實體幾何法(CSG)、三維柵格(Array)、塊段(Block)、六面體(Hexahedral)、多面體(Polyhedral)和棱柱體(Prism)等。

基于面元模型的優(yōu)點為數(shù)據(jù)存儲量小，建?？旖?，實體顯示和更新的速度快，不足之處為不能描述實體的內部屬性，難以進行實體的三維空間分析和查詢。基于體元模型的優(yōu)點為適于空間操作和分析，不足之處為數(shù)據(jù)結構復雜，存儲空間大，建模速度慢。

面元模型和體元模型有不同的特點和適用對象，而混合模型綜合了面元模型和體元模型的優(yōu)點［5］，實際應用中可以根據(jù)實體的不同特性采用不同的混合模型。構造混合模型需要考慮以下3個維:模型的構成元素維，包括面元、體元和混合3種;存儲類型維，包括柵格、矢量和混合3種;構成元素的形狀維，包括規(guī)則、不規(guī)則和混合3種。研究者根據(jù)不同需要將這些維組合起來構造了多種混合模型［6-7］，有同一維上的混合模型，如TIN-CSG面和體混合模型、Octree-TEN矢量和柵格混合模型、混合面片的規(guī)則和不規(guī)則體素混合模型;還有不同維之間的混合模型，如TIN-Octree面和柵格的混合模型。

2 三維混合數(shù)據(jù)模型

2.1 八叉樹結構

八叉樹結構是一種規(guī)則的數(shù)據(jù)結構，通過用樹結構對模型進行遞歸，按X、Y、Z 3個不同方向，將所要表示的三維空間實體V分割為8個大小相等的子立方體。然后根據(jù)每個子立方體中所含的目標來決定是否對子立方體繼續(xù)進行8等分的劃分。一直劃分到每個子立方體被一個目標所充滿，或沒有目標，或其大小已成為預先定義的不可再分的體素為止。如圖1所示，八叉樹每個節(jié)點有8個子節(jié)點或者沒有子節(jié)點。圖1(c)中，小圓圈表示該立方體未被某個目標填滿，需要繼續(xù)劃分?；叶刃【匦伪硎驹摿⒎襟w被某個目標填滿，空白小矩形表示該立方體中沒有目標，這兩種情況都不需繼續(xù)劃分。八叉樹每個維度每劃分一次，其分辨率都將增大到原來的兩倍。

圖1 八叉樹結構

八叉樹體素分解是將空間三維物體逐級分解，最終形成八叉樹體素表示的結構。八叉樹的主要優(yōu)點為可以方便地實現(xiàn)物體的并、交、差等集合運算，適用于較規(guī)則實體的建模，但對于不規(guī)則實體的建模則不太適用［8］。

2.2 NURBS參數(shù)函數(shù)表示

參數(shù)函數(shù)表示的指導思想是利用有限的空間數(shù)據(jù)，構造一個函數(shù)的解析式，用這個解析式來生成新的空間點，用以逼近原有物體。參數(shù)函數(shù)表示包括解析函數(shù)模型和非解析函數(shù)模型。解析函數(shù)模型的優(yōu)點為數(shù)學運算簡便、數(shù)據(jù)存儲量小，但復雜的空間對象很難用統(tǒng)一的函數(shù)參數(shù)方程來表達。為了克服解析函數(shù)的局限性，人們提出了非解析函數(shù)。B樣條函數(shù)是比較實用的參數(shù)函數(shù)，具有存儲量小、分析運算速度快、空間幾何不變性等特點，是構建三維空間實體邊界曲面的有效方法。

非均勻有理B樣條(non-uniform rational B-splinc，NURBS)函數(shù)是在B樣條函數(shù)基礎上發(fā)展起來的，已被廣泛應用于工程設計中。計算機圖像處理技術的發(fā)展，推動了NURBS技術在三維建模領域中的應用［9］。

如圖 2所示，一條 NURBS曲線 s(u)=(x(u)，y(u)，z(u))可通過式(1)表示:

圖2 NURBS擬合曲線

式中:Pi=(xi，yi，zi)(i=0，1，…，n)為控制點;wi(i=0，1，…，n)為權因子;k為階數(shù);0，1，…，n)為B樣條基函數(shù)，其遞推定義如下:

u 向節(jié)點矢量為{u0，u1，…，un+k|ui≤ui+1，i=0，1，…，n+k-1|}。

si(u)(i=0，1，…，n)為由控制點分段擬合的曲線段，u∈［ui，ui+1］，i=k-1，k，…，n。

如圖3所示，設一個 NURBS曲面給定了(n+1) ×(m+1)的網格控制點 Pij(0≤i＜n，0≤j＜m)，則該NURBS曲面可定義為:

式中:wij(0≤i＜n，0≤j＜m)為相應于控制點Pij的權因子;k、l為階數(shù);(0≤i≤n)和(0≤j≤m)分別是定義在u、v向節(jié)點向量:U={u0，u1，…，un+k|ui≤ ui+1，i=0，1，…，n+k-1}V={v0，v1，…，vm+l|vj≤ vj+1，i=0，1，…，m+l-1}

k、l階 B樣條基函數(shù)遞推定義同式(2);Sij(u，v)表示擬合的曲面段，u∈［ui，ui+1］，i=k-1，k，…，n;v∈［vj，vj+1］，j=l-1，l，…，m。

圖3 NURBS擬合曲面

2.3 建筑物三維混合數(shù)據(jù)模型

建筑物在幾何和拓撲上有較大差異，傳統(tǒng)的八叉樹模型表示不規(guī)則的實體不夠精確，很難用于各種類型建筑物的建模。針對城市建筑物種類繁多、結構復雜、信息量大的特點，筆者采用八叉樹與NURBS曲面相結合的混合數(shù)據(jù)模型。

在混合數(shù)據(jù)模型中，利用八叉樹對建筑物實體進行三維空間分割，利用NURBS擬合建筑物不規(guī)則的表面。當分割后的建筑物子體位于實體邊界且外形不是規(guī)則立方體時，采用NURBS曲面描述該體元的表面，如圖4所示。將實體轉換為八叉樹結構時，在邊界灰度節(jié)點中加入子體的面、邊、頂點信息，從而形成擴展的八叉樹結構［10］。

空間分割首先采用八叉樹空間分解法生成曲面離散點集，選取一個立方體包圍盒圈定空間曲面，將包圍盒作為八叉樹的根節(jié)點來初始化八叉樹數(shù)據(jù)結構。然后將該包圍盒分解成8個子區(qū)域，作為大立方體的8個子節(jié)點，生成子體曲面上的空間離散點集。空間分割時注意采集實體不規(guī)則部分的外圍散點，將不規(guī)則體元剖分成參數(shù)函數(shù)曲面，生成子體的NURBS曲面。

圖4 八叉樹-NURBS混合結構

混合結構用一個特殊的屬性值實現(xiàn)八叉樹與NURBS曲面的鏈接，若八叉樹某節(jié)點編碼的屬性值為N，表示該節(jié)點關聯(lián)一個局部的NURBS曲面。通過節(jié)點與對應的8個子節(jié)點體內的特征點相結合，形成局部NURBS曲面。實現(xiàn)時采用網格細化和求交切割的方法［11］，用不規(guī)則體元填充八叉樹與表面模型之間的空隙，完成模型的自適應分割。

曲面模型的數(shù)學表示是一個帶符號的代數(shù)距離函數(shù)，為了簡化曲面建模，也可以采用一個均勻的雙三次B樣條函數(shù)［12］。假設在二維平面上有n個點(xi，yi)(i=1，2，…，n)，并有 hi=F(xi，yi)，這樣在三維空間中可以構成一個點的集合P={(xi，yi，zi)}。構造一個均勻的雙三次B樣條曲面來逼近集合P，該雙三次曲面片由覆蓋在子節(jié)點的控制點網格φ來定義。設φij是網格φ中序號為ij的控制點的值，則由這些控制點定義的雙三次B樣條函數(shù)為:

式中:Bk、Bl為均勻雙三次B樣條基函數(shù)。

控制點陣列 φkl(k，l=0，1，2，3)決定了點(xc，yc)的函數(shù)值 f(xc，yc)，即有:

式中:s=xc-1;t=yc-1。

有許多組的值可以滿足式(4)，根據(jù)最小二乘法原理，用偽逆矩陣可以求出一組解為:

2.4 建筑物數(shù)據(jù)結構

隨著城市化進程的加快，城市建筑物的結構和形狀不斷發(fā)生變化。數(shù)據(jù)結構是三維建模的基礎，必須設計出合理的數(shù)據(jù)結構，以便高效地存儲建筑物的屬性和幾何數(shù)據(jù)。根據(jù)八叉樹-NURBS混合三維數(shù)據(jù)模型，采用面向對象的程序設計語言C++為建筑物設計相應的數(shù)據(jù)結構，其形式化表示如下:

在存儲結構上，采用擴展節(jié)點(面、邊、頂點)和混合式的八叉樹結構，在八叉樹較高的層次上使用指針式結構建立節(jié)點的索引，而在較低的層次上按節(jié)點編碼的大小排序，建立該局部空間內包含的所有非空葉節(jié)點的線性表。這樣既減少了存儲空間，又提高了顯示的精度和搜索效率。

通過八叉樹節(jié)點編碼可以得到其對應的8個子節(jié)點，編碼方案直接影響節(jié)點的存取效率。這里采用八進制前綴編碼方案，即對同一父節(jié)點的8個兄弟節(jié)點，其具有最小(x，y，z)值的節(jié)點編號為0，相鄰兄弟節(jié)點的編號沿x方向增加1，沿y方向增加2，沿z方向增加4，并將父節(jié)點的編碼作為其8個子節(jié)點編碼的前綴。為保證八叉樹中每一節(jié)點編碼的長度相同，在編碼后增加一串區(qū)別于0～7八進制數(shù)的特殊字符“T”，使每個節(jié)點編碼的長度均為樹的最大深度H。這樣，節(jié)點編碼可表示為 q1q2…qiTT…T，其中 q1，q2，…，qi∈{0，1，…，7}，0≤i≤H。顯然，q1q2…qn表示了空間最低層次(第n層)立方體網格單元，q1q2…qiTT…T表示了空間分割至第i層時的立方體網格。

實體模型的多個子體相互關聯(lián)，多個子體結合成為模型總體。每個子體由一組節(jié)點和一個NURBS曲面重構形成，CreatNURBS()函數(shù)用于建立建筑物的NURBS曲面對象。一些八叉樹葉節(jié)點可能被同一個NURBS曲面對象包含，即一個NURBS曲面對象可能同時與多個八叉樹節(jié)點相關聯(lián)。通過對八叉樹按層次遍歷逐步細分作用區(qū)域，在求交層中對區(qū)域內的每個節(jié)點進行精確的NURBS關聯(lián)運算。實際應用中，有些建筑物的墻體或屋頂為曲面，需要采集或內插一些特征點，然后按一定的規(guī)則對建筑物的子體建立NURBS曲面模型。

3 基于OpenGL的建筑物三維可視化

模型系統(tǒng)以Visual C++6.0為開發(fā)平臺，采用面向對象的建模方法，利用OpenGL技術實現(xiàn)實體的三維建模和可視化。在建立NURBS曲面模型時，以OpenGL的NURBS接口函數(shù)為基礎，通過編寫程序對節(jié)點相關聯(lián)的NURBS曲面建模。NURBS對實體表面的擬合，主要通過計算控制點實現(xiàn)。先求出控制多邊形的頂點，根據(jù)已知的數(shù)據(jù)擬合NURBS曲面，通過插值法最終實現(xiàn)所有子體表面的NURBS曲面構造。該模型系統(tǒng)不僅可以表達規(guī)則實體，也可以表達不規(guī)則實體，使用該模型系統(tǒng)生成的三維模型如圖5所示。

圖5 建筑物三維模型

對于簡單結構建筑物的建模，混合模型并沒有體現(xiàn)出比傳統(tǒng)的八叉樹模型更優(yōu)越。但在處理不規(guī)則的建筑物時，在相同分辨率要求的前提下，混合模型對三維空間實體的分割次數(shù)要遠遠小于八叉樹模型。如對弧面形狀的建筑物，前者的分割次數(shù)為后者的1/8左右。因此，即使考慮NURBS曲面對象的建模，混合模型的數(shù)據(jù)存儲量比八叉樹模型少50%以上，相應的模型顯示速度提高了20%，模型的精度也更高。

4 結論

筆者在對城市建筑物三維建模理論和方法進行深入研究的基礎上，設計了一個基于八叉樹和NURBS的混合數(shù)據(jù)模型系統(tǒng)。實踐證明，該模型具有一定的實用性和可行性，可視化效果較好，具有較精確表示復雜空間實體的特點。由于數(shù)據(jù)結構的復雜性，該模型在判斷何時需要構造NURBS曲面時，條件不夠精確，理論和算法還需深入研究。

［1］THIELE A，CADARIO E，SCHULZ K，et a1.Building reconstruction from InSAR data by detail analysis of phase profiles［C］//The International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences.Beijing:［s.n.］，2008:191-196.

［2］楊淼.基于圖像的城市建筑物三維自動重建參數(shù)化建模方法研究［D］.青島:中國海洋大學圖書館，2009.

［3］王彥兵，吳立新，李小娟.3維GIS空間建模方法評述［J］.中國圖象圖形學報，2007，12(8):1430-1434.

［4］KATSIANIS M，TSIPIDIS S，KOTSAKIS K，et a1.A 3D digital workflow for archaeological intra-site research using GIS［J］.Journal of Archaeological Science，2008，35(3):655-667.

［5］張傳明，潘懋，徐繪宏.基于分塊混合八叉樹編碼的海量體視化研究［J］.計算機工程，2007，33(14):33-78.

［6］吳慧欣，薛惠鋒.基于塊段模型的三維GIS混合數(shù)據(jù)結構模型研究［J］.計算機應用研究，2007，24(10):273-275.

［7］荊永濱，王李管，畢林，等.復雜礦體的塊段模型建模算法［J］.華中科技大學學報:自然科學版，2010，38(2):97-100.

［8］FREY P J.Generation and adaptation of computational surface meshes from discrete anatomical data［J］.International Journal for Numerical Methods in Engineering，2004，60(2):1049-1074.

［9］HU S M，LI Y F，JU T，et a1.Modifying the shape of NURBS surfaces with geometric constraints［J］.Computer Aided Design，2001，33(12):903-912.

［10］郭銳鋒，劉春輝，丁萬夫.改進的八叉樹模型在3D刀軌顯示系統(tǒng)中的應用［J］.小型微型計算機系統(tǒng)，2010，31(2):373-376.

［11］任銘，李振平.基于八叉樹與RBF神經網絡的曲面三角網格生成［J］.中原工學院學報，2011，22(1):32-34.

［12］李鵬，劉永鴻.一種運用OpenGL快速構建三維模擬地形的方法［J］.計算機仿真，2005，22(12):174-177.