羅 文，袁 林 旺，胡 勇，易 琳，閭 國 年

三維社區(qū)建模與分析的共形幾何代數(shù)方法

羅 文，袁 林 旺＊，胡 勇，易 琳，閭 國 年

（南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210046）

利用共形幾何代數(shù)的多維統(tǒng)一表達(dá)與分析優(yōu)勢，研究了集成多源數(shù)據(jù)的三維社區(qū)統(tǒng)一建模與分析方法。構(gòu)建了基于多重向量存儲結(jié)構(gòu)的社區(qū)場景整體建模流程，實(shí)現(xiàn)了City GML、DXF等多源數(shù)據(jù)的導(dǎo)入與集成，并設(shè)計(jì)了基于共形幾何代數(shù)的對象運(yùn)動表達(dá)與插值方法。以德國Waldbruecke村為例的驗(yàn)證結(jié)果顯示，基于共形幾何代數(shù)的三維社區(qū)建?？梢暂^好地表達(dá)復(fù)雜社區(qū)對象，并可以有效支撐幾何度量、動態(tài)對象跟蹤、運(yùn)動軌跡重建等功能實(shí)現(xiàn)。

三維社區(qū);共形幾何代數(shù);對象建模;動態(tài)分析

城市三維建模與可視化、數(shù)字城市建設(shè)是城市信息化的重要發(fā)展趨勢，三維社區(qū)建設(shè)是其中的重要內(nèi)容［1，2］。三維社區(qū)分析涉及領(lǐng)域的寬泛性決定了其數(shù)據(jù)的多源性，三維社區(qū)建模中常用的數(shù)據(jù)包含工程測量中的AutoCAD/DXF數(shù)據(jù)、交通測繪的shapefile數(shù)據(jù)、數(shù)字城市的City GML數(shù)據(jù)等。如何有效融合多源異構(gòu)數(shù)據(jù)，構(gòu)建多維統(tǒng)一的數(shù)據(jù)模型成為三維社區(qū)建設(shè)的難點(diǎn)和重點(diǎn)［3］;另一方面，成熟的三維社區(qū)建設(shè)不僅要求實(shí)現(xiàn)社區(qū)建筑、道路網(wǎng)絡(luò)等多種不同維度、不同類型的實(shí)體對象的建模與表達(dá)，更需要構(gòu)建適用于復(fù)雜地理場景中多維對象分析的各類分析算法。共形幾何代數(shù)（Conformal Geometric Algebra，CGA）具有優(yōu)越的多維表達(dá)與分析能力，前期研究表明CGA在GIS對象表達(dá)、關(guān)系計(jì)算及動態(tài)場景分析等方面具有優(yōu)勢［4，5］。本文以德國Waldbruecke村的社區(qū)規(guī)劃平面圖數(shù)據(jù)、社區(qū)三維建筑物模型數(shù)據(jù)、道路網(wǎng)絡(luò)數(shù)據(jù)等基礎(chǔ)地理信息數(shù)據(jù)為基礎(chǔ)，從多源數(shù)據(jù)整合與集成、場景構(gòu)建與建模、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、系統(tǒng)構(gòu)建與應(yīng)用分析等視角入手，探討基于幾何代數(shù)的三維社區(qū)建模與分析的思路與方法，對三維社區(qū)中各類建筑物與運(yùn)動對象進(jìn)行建模、表達(dá)與分析，嘗試為三維社區(qū)虛擬仿真、動態(tài)表達(dá)和空間分析研究提供參考。

1 三維社區(qū)場景建模

1.1 Grassmann結(jié)構(gòu)一致的幾何形體表達(dá)

共形幾何代數(shù)（CGA）是李洪波等［6］結(jié)合共形模型和幾何代數(shù)的主要優(yōu)勢，對幾何代數(shù)、射影幾何進(jìn)行拓展后建立的。定義由歐氏空間向共形幾何代數(shù)空間Cn?的變換C（x）為：

其中：e0和e∞為額外添加的維度支撐向量，分別表示原點(diǎn)和無窮遠(yuǎn)點(diǎn)。

共形幾何代數(shù)賦予幾何代數(shù)空間閔氏內(nèi)積結(jié)構(gòu)，使得五維向量空間的Grassmann分級結(jié)構(gòu)（C3?）完全對應(yīng)于幾何體的分級結(jié)構(gòu)，通過e∞的引入，消除無窮遠(yuǎn)點(diǎn)的奇異性，統(tǒng)一了線段和圓以及平面和球的表達(dá);同時使得內(nèi)積可以直接對應(yīng)于兩點(diǎn)間歐氏距離的表征，賦予了內(nèi)積明確的幾何意義。

圖1列出了三維空間中常見幾何形體的CGA表達(dá)，其Grassmann結(jié)構(gòu)一致性直觀表現(xiàn)在形體表達(dá)形式與幾何體維度相一致。表達(dá)形式的一致性為幾何形體的多維統(tǒng)一建模奠定了基礎(chǔ)，也是構(gòu)建三維社區(qū)場景中對象無關(guān)、維度無關(guān)分析功能的基本前提。

圖1 Grassmann結(jié)構(gòu)一致的幾何形體表達(dá)Fig.1 Geometric representation with consistent Grassmann structure

1.2 基本數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

基本幾何形體數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)如圖2所示，鑒于CGA中基本幾何形體表達(dá)形式具有一致性，可以先設(shè)計(jì)幾何形體基類CGA＿Geo，聲明一個32長度的浮點(diǎn)型數(shù)組成員變量m＿c用于存儲各維度blade系數(shù)（blade的概念參見文獻(xiàn)［4］），m＿gu用于存儲當(dāng)前對象的維度。在CGA＿Geo的基礎(chǔ)上分別派生出點(diǎn)對象（CCA＿Point）、點(diǎn)對＼線段對象（CCA＿Pt Pair）、直線對象（CCA＿Line）、圓對象（CCA＿Circle）、平面對象（CCA＿Plane）和球面對象（CCA＿Sphere），并針對各對象特點(diǎn)分別定義其特有的屬性和方法。

圖2 基本幾何形體的數(shù)據(jù)結(jié)構(gòu)Fig.2 Data structure of basic geometric objects

CGA＿Geo類的另一重要作用在于：當(dāng)幾何體未知時可以先將其聲明成CGA＿Geo類型，經(jīng)過運(yùn)算后，通過提取grade運(yùn)算判斷其維度，進(jìn)而分析得到其具體類型。當(dāng)形體已知時，聲明其對應(yīng)類型，可有效提升存儲空間效率和運(yùn)算時間效率。基于上述特性，在分析功能設(shè)計(jì)中，可將任意幾何體當(dāng)做CGA＿Geo類參與運(yùn)算，從而實(shí)現(xiàn)對象無關(guān)的表達(dá)與運(yùn)算。

1.3 三維社區(qū)建模與組織

三維社區(qū)場景建模要求實(shí)現(xiàn)三維場景中基本幾何對象幾何、拓?fù)潢P(guān)系的重建及語義關(guān)系的嵌入。同維度幾何對象可通過關(guān)系表、鏈表等結(jié)構(gòu)簡單連接，但不同維度對象統(tǒng)一建模與表達(dá)則是幾何、拓?fù)浣５碾y點(diǎn)所在。多重向量（multivector）是幾何代數(shù)中與blade相對應(yīng)的一個概念，multivector通過“＋”連接不同維度的blade，實(shí)現(xiàn)混合維度對象的存儲，且在幾何代數(shù)理論體系中已經(jīng)形成一套相對完備的針對multivector的分析方法［7］。據(jù)此，可以將基本幾何形體用“＋”連接成如下形式：

式（2）同時包含了點(diǎn)、線段和面對象，其連接順序采用基于對象類別的分類排列方法，式中“＋”僅用于表達(dá)關(guān)系計(jì)算，而不進(jìn)行數(shù)值上的累加與歸并。語義關(guān)系的嵌入則以關(guān)系表為基礎(chǔ)，通過ID與幾何對象相鏈接。

1.4 多源數(shù)據(jù)集成框架

基于上述場景建模思路構(gòu)建空間數(shù)據(jù)解析流程（圖3）。首先應(yīng)用數(shù)據(jù)解析器得到幾何數(shù)據(jù)和屬性數(shù)據(jù)，判斷幾何數(shù)據(jù)類別，分別將其存儲為對應(yīng)的結(jié)構(gòu)，然后根據(jù)數(shù)據(jù)本身的層次結(jié)構(gòu)生成相應(yīng)的多重向量的統(tǒng)一存儲。以地理對象為單位對多重向量進(jìn)行ID標(biāo)識，并將其與存入屬性表中的屬性數(shù)據(jù)相關(guān)聯(lián)。以CityGML數(shù)據(jù)和AutoCAD的DXF交換格式兩種主要數(shù)據(jù)類型的解析與集成方法為例，進(jìn)行基于幾何代數(shù)的三維社區(qū)建模示范。

圖3 空間數(shù)據(jù)解析流程Fig.3 Parsing flow of spatial data

CityGML數(shù)據(jù)以XML文本標(biāo)識語言為基礎(chǔ)，以樹型結(jié)構(gòu)存儲其幾何拓?fù)湫畔ⅲ?］。通過其最頂層的數(shù)據(jù)根節(jié)點(diǎn)City ObjectsRoots管理場景，以下依次為City Object、Geometry、面、線、點(diǎn)，每個節(jié)點(diǎn)都有與之對應(yīng)的屬性信息，包含用于區(qū)分對象類型（屋頂、墻壁等）的數(shù)據(jù)標(biāo)簽以及用于可視化渲染的顏色和材質(zhì)信息。City GML數(shù)據(jù)的解析與集成類似于樹的中序遍歷，即先讀取當(dāng)前節(jié)點(diǎn)，再讀取其各個組成部分，從而實(shí)現(xiàn)拓?fù)潢P(guān)系的重建。結(jié)合分析需要，將數(shù)據(jù)按一定的粒度進(jìn)行對象劃分，并為其分配唯一的ID進(jìn)行標(biāo)識，連接屬性信息。

DXF數(shù)據(jù)是AutoCAD的繪圖交換文件，是由很多的“代碼”和“值”組成的“數(shù)據(jù)對”構(gòu)造而成［9］。這些“代碼”包含對DXF文件頭、塊、圖層及實(shí)體對象等的定義。DXF數(shù)據(jù)的解析過程與CityGML基本類似，但需進(jìn)行數(shù)據(jù)中塊的處理。此外，由于DXF數(shù)據(jù)本身不具備嚴(yán)密的拓?fù)湫畔?，所以前期需要對?shù)據(jù)的拓?fù)浼右孕拚?/p>

2 對象運(yùn)動表達(dá)與插值

2.1 基本幾何分析

共形幾何代數(shù)的閔氏內(nèi)積結(jié)構(gòu)使得內(nèi)積運(yùn)算具有表達(dá)對象距離的幾何意義，進(jìn)而實(shí)現(xiàn)了內(nèi)蘊(yùn)距離、方向等幾何關(guān)系的共形幾何代數(shù)表達(dá)。如對于兩個給定點(diǎn)p、q，其距離計(jì)算公式為：p、q分別為經(jīng)共形轉(zhuǎn)換后點(diǎn)的表達(dá)。而直線間的角度則可根據(jù)二者所在向量內(nèi)積與向量模的比值確定。

2.2 對象運(yùn)動表達(dá)

CGA中平移、旋轉(zhuǎn)和縮放等歐氏變換可統(tǒng)一于同一變換框架下［10］?；贑GA的運(yùn)動表達(dá)的一般形式為：Or＝RoR′，其中o為運(yùn)動對象，R為運(yùn)動的統(tǒng)一表達(dá)，也稱作versor表達(dá)。對于任意的versor表達(dá)，很難直觀地獲得其確切的幾何意義，但奇次階的versor則可通過其指數(shù)形式揭示其內(nèi)蘊(yùn)的幾何意義。如指數(shù)形式表達(dá)的變換R＝e－φl/2表示以l為旋轉(zhuǎn)軸、旋轉(zhuǎn)角度為φ的rotor，其證明過程如下：

2.3 對象運(yùn)動插值

基于指數(shù)形式的versor表達(dá)可通過對數(shù)變換將其線性化，從而獲得相關(guān)運(yùn)動參數(shù)，進(jìn)行運(yùn)動軌跡重構(gòu)及線性運(yùn)動平滑插值。任意歐氏空間的剛體運(yùn)動與變換均可通過共形空間中的versor精確表達(dá)［11］。由于任意奇次階versor均可表達(dá)為bi-vector的指數(shù)形式，即：V＝eB，對該式兩邊分別取對數(shù)可得：B＝ln（V），且任意bi-vector均為線性結(jié)構(gòu)，因此基于指數(shù)形式表達(dá)的versor可以直接進(jìn)行諸如平均、插值、外推等數(shù)值運(yùn)算。如基于rotor指數(shù)形式表達(dá)，其插值公式為：

式（4）實(shí)現(xiàn)了將R1到R2的運(yùn)動插值為n次的運(yùn)動r?；谏鲜鏊阕涌蓪?shí)現(xiàn)歐氏空間中復(fù)雜運(yùn)動的表達(dá)與分析。由于基于幾何代數(shù)的旋轉(zhuǎn)表達(dá)算子的符號直接表征了其運(yùn)動方向［12］，類似地可從基于幾何代數(shù)的運(yùn)動表達(dá)中解析出運(yùn)動內(nèi)在的特性信息。

3 系統(tǒng)實(shí)現(xiàn)與驗(yàn)證

3.1 系統(tǒng)架構(gòu)

設(shè)計(jì)基于共形幾何代數(shù)的三維社區(qū)集成構(gòu)建系統(tǒng)對上述思路加以驗(yàn)證，系統(tǒng)層次架構(gòu)如圖4所示。數(shù)據(jù)資源層包括CityGML、DXF和Shape等常用的空間數(shù)據(jù)，數(shù)據(jù)組織層為前述多源數(shù)據(jù)集成方法及基于CGA的多維統(tǒng)一存儲，設(shè)計(jì)場景動態(tài)監(jiān)控與運(yùn)動對象插值的功能分析層，最后是基于VTK渲染的場景可視化與場景交互的表現(xiàn)層。該系統(tǒng)以共形幾何代數(shù)為理論支持，多維統(tǒng)一建模為主線，場景動態(tài)分析為最終目標(biāo)，實(shí)現(xiàn)面向多源數(shù)據(jù)的三維社區(qū)場景建模與分析。

圖4 三維社區(qū)集成構(gòu)建系統(tǒng)架構(gòu)Fig.4 The architecture of 3D resident community integration system

3.2 案例數(shù)據(jù)

以德國Waldbruecke村為研究樣區(qū)，使用的主要數(shù)據(jù)及格式如表1所示。其中社區(qū)三維建筑物的模型數(shù)據(jù)與數(shù)字化的道路網(wǎng)數(shù)據(jù)主要用于場景的構(gòu)建，車輛模型數(shù)據(jù)和車輛位置數(shù)據(jù)則用于場景動態(tài)模擬及場景內(nèi)動態(tài)對象的插值分析。

表1 主要數(shù)據(jù)及其格式Table 1 The main data and its format

3.3 三維建模與分析

首先對City GML場景數(shù)據(jù)、DXF車輛數(shù)據(jù)和Shape格式的道路數(shù)據(jù)集成建模，建模結(jié)果可通過系統(tǒng)可視化模塊進(jìn)行渲染可視化（圖5a）。在基于幾何代數(shù)的三維社區(qū)建模中，由于不同維度幾何對象均處于同一場景，可對其集中管理。圖5b演示了場景中對三維建筑對象的交互式選取與可視化功能?；贑GA框架的三維場景建?？蓪?shí)現(xiàn)場景中對象幾何關(guān)系的批量計(jì)算及運(yùn)動對象動態(tài)插值。應(yīng)用車輛模型和車輛位置模擬數(shù)據(jù)，可對車輛在場景中的運(yùn)動情況進(jìn)行動態(tài)模擬，并實(shí)時計(jì)算其距離與角度等基本幾何關(guān)系（圖5c），圖中雷達(dá)圖與箭頭圖分別顯示的是車與選中建筑的距離和角度。圖5d為運(yùn)動對象插值計(jì)算演示，圖中黑色軌跡為讀取的原始數(shù)據(jù)，灰色軌跡為經(jīng)過versor插值后的樣點(diǎn)數(shù)據(jù)，由結(jié)果可知，基于versor的運(yùn)動插值可保證插值軌跡相對均勻、平滑，且可推算出任意時刻車輛所在的位置信息及其運(yùn)動參數(shù)。

圖5 三維社區(qū)對象建模與運(yùn)動分析Fig.5 Modeling and motion analysis of 3D resident community

4 結(jié)論與討論

本文以CGA為基礎(chǔ)，設(shè)計(jì)了基于多重向量的三維社區(qū)統(tǒng)一存儲模型，利用其在多維對象建模與分析上的優(yōu)勢，構(gòu)造了可支撐多源數(shù)據(jù)集成的三維社區(qū)建模與分析的整體流程。利用幾何代數(shù)算子與基于versor的運(yùn)動表達(dá)，構(gòu)造了包括幾何度量、動態(tài)對象運(yùn)動表達(dá)及運(yùn)動插值等場景對象動態(tài)表達(dá)和分析方法。對德國Waldbruecke村三維社區(qū)的實(shí)例分析顯示，本文提出的三維社區(qū)建模與分析方法可以很好地支撐復(fù)雜三維社區(qū)場景對象的表達(dá)與建模，并可有效支撐三維社區(qū)中運(yùn)動對象的模擬與分析，從而為三維社區(qū)建設(shè)提供良好的理論支撐與開發(fā)工具。

幾何代數(shù)優(yōu)越空間構(gòu)造能力與多維對象統(tǒng)一表達(dá)機(jī)制可以有效支撐三維場景中復(fù)雜對象的表達(dá)與分析，基于幾何代數(shù)的動態(tài)對象表達(dá)與分析不僅可以再現(xiàn)對象動態(tài)運(yùn)動與演化的軌跡與過程，實(shí)現(xiàn)對象運(yùn)動過程的直觀再現(xiàn)，更可以有效保持原有運(yùn)動軌跡的運(yùn)動參數(shù)特征，從而直接支撐復(fù)雜的時空及運(yùn)動分析。以幾何代數(shù)為基礎(chǔ)，對現(xiàn)有三維社區(qū)分析方法及更廣泛的地理分析模型進(jìn)行重建與集成，有望提升現(xiàn)有三維社區(qū)GIS的建模、表達(dá)與分析能力，為其向時態(tài)GIS方向的發(fā)展及更廣泛的領(lǐng)域應(yīng)用提供數(shù)據(jù)建模、計(jì)算方法以及分析模型支撐。

［1］田宜平，李偉忠，何珍文.數(shù)字城市中三維數(shù)字社區(qū)的解決方案［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40（1）：223－226.

［2］孫敏，馬藹乃，陳軍.三維城市模型的研究現(xiàn)狀評述［J］.遙感學(xué)報(bào)，2002，6（2）：155－161.

［3］宋關(guān)福，鐘耳順，劉紀(jì)遠(yuǎn)，等.多源空間數(shù)據(jù)無縫集成研究［J］.地理科學(xué)進(jìn)展，2000，19（2）：110－115.

［4］YUAN L W，YU Z Y，CHEN S F，et al.CAUSTA：Clifford algebra based unified spatio-temporal analysis［J］.Transactions in GIS，2010，14（s1）：59－83.

［5］袁林旺，俞肇元，羅文，等.基于共形幾何代數(shù)的GIS三維空間數(shù)據(jù)模型［J］.中國科學(xué)（D輯），2010，40（12）：1450－1461.

［6］李洪波.共形幾何代數(shù)——幾何代數(shù)的新理論和計(jì)算框架［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17（11）：2383－2393.

［7］PERWASS C.Geometric Algebra with Applications in Engineering［M］.Heidelberg：Springer-Verlag，2009.

［8］巫兆聰，歐陽群東，李芳芳.基于City GML的遙感信息共享研究［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2010，35（4）：423－426.

［9］孫曉莉，趙俊三.DXF文件到Shape文件無損轉(zhuǎn)換方法的研究［J］.科學(xué)技術(shù)與工程，2011，11（14）：3336－3341.

［10］刑燕，檀結(jié)實(shí).圖形變換和運(yùn)動的共形幾何代數(shù)表示方法［J］.計(jì)算機(jī)應(yīng)用研究，2008，25（9）：2842－2844.

［11］DORST L，F(xiàn)ONTIJNE D，MANN S.Geometric algebra for computer science［A］.The Morgan Kaufmann Series in Computer Graphics［C］.Morgan Kaufmann Elsevier，2007.

［12］李洪波.共形幾何代數(shù)與運(yùn)動和形狀的刻畫［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（7）：895－901.

Conformal Geometric Algebra-Based 3D Resident Community Modeling and Analysis

LUO Wen，YUAN Lin－wang，HU Yong，YI Lin，LV Guo－nian
（KeyLaboratoryofVGE，MinistryofEducation，NanjingNormalUniversity，Nanjing210046，China）

Conformal Geometric Algebra（CGA）is a relatively new geometric model for geometric primitives representation，it also offers a language of operations to manipulate those primitives.Based on these advantages，this paper explored the method for multi-source data integration and unified modeling and analysis of the three dimensional resident community.As well as the storage structure founded on multi-vectors，the modeling procedures of the whole community scene were constructed，supporting multi-format data importing and integration such as City GML and DXF.Furthermore，the moving object expression and dynamical interpolation methods were illustrated.The proposed modeling and analysis methods were experimented on the German Waldbruecke village data.The results suggest that the three dimensional resident community modeling based on CGA can effectively express complex community objects，as well as analysis functions e.g.geometric measurements，dynamical objects tracking and motion trajectory reconstruction.

3D resident community;CGA;object modeling;dynamical analysis

P208

A

1672－0504（2012）03－0020－04

2011－10- 30;

2011－12－31

國家自然科學(xué)基金“基于幾何代數(shù)的多維統(tǒng)一空間關(guān)系計(jì)算模型及并行化方法”（41171300）;國家863資助課題 “基于Clifford代數(shù)的時空統(tǒng)一數(shù)據(jù)模型關(guān)鍵技術(shù)研究”（2009AA12Z205）

羅文（1986－），男，博士研究生，主要從事GIS理論與算法研究。＊通訊作者E－mail：yuanlinwang＠njnu.edu.cn