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

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

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

（南京師范大學虛擬地理環(huán)境教育部重點實驗室，江蘇 南京 210046）

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

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

城市三維建模與可視化、數(shù)字城市建設是城市信息化的重要發(fā)展趨勢，三維社區(qū)建設是其中的重要內(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ū)建設的難點和重點［3］;另一方面，成熟的三維社區(qū)建設不僅要求實現(xiàn)社區(qū)建筑、道路網(wǎng)絡等多種不同維度、不同類型的實體對象的建模與表達，更需要構(gòu)建適用于復雜地理場景中多維對象分析的各類分析算法。共形幾何代數(shù)（Conformal Geometric Algebra，CGA）具有優(yōu)越的多維表達與分析能力，前期研究表明CGA在GIS對象表達、關(guān)系計算及動態(tài)場景分析等方面具有優(yōu)勢［4，5］。本文以德國Waldbruecke村的社區(qū)規(guī)劃平面圖數(shù)據(jù)、社區(qū)三維建筑物模型數(shù)據(jù)、道路網(wǎng)絡數(shù)據(jù)等基礎地理信息數(shù)據(jù)為基礎，從多源數(shù)據(jù)整合與集成、場景構(gòu)建與建模、數(shù)據(jù)結(jié)構(gòu)設計、系統(tǒng)構(gòu)建與應用分析等視角入手，探討基于幾何代數(shù)的三維社區(qū)建模與分析的思路與方法，對三維社區(qū)中各類建筑物與運動對象進行建模、表達與分析，嘗試為三維社區(qū)虛擬仿真、動態(tài)表達和空間分析研究提供參考。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

DXF數(shù)據(jù)是AutoCAD的繪圖交換文件，是由很多的“代碼”和“值”組成的“數(shù)據(jù)對”構(gòu)造而成［9］。這些“代碼”包含對DXF文件頭、塊、圖層及實體對象等的定義。DXF數(shù)據(jù)的解析過程與CityGML基本類似，但需進行數(shù)據(jù)中塊的處理。此外，由于DXF數(shù)據(jù)本身不具備嚴密的拓撲信息，所以前期需要對數(shù)據(jù)的拓撲加以修正。

2 對象運動表達與插值

2.1 基本幾何分析

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

2.2 對象運動表達

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

2.3 對象運動插值

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

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

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

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

設計基于共形幾何代數(shù)的三維社區(qū)集成構(gòu)建系統(tǒng)對上述思路加以驗證，系統(tǒng)層次架構(gòu)如圖4所示。數(shù)據(jù)資源層包括CityGML、DXF和Shape等常用的空間數(shù)據(jù)，數(shù)據(jù)組織層為前述多源數(shù)據(jù)集成方法及基于CGA的多維統(tǒng)一存儲，設計場景動態(tài)監(jiān)控與運動對象插值的功能分析層，最后是基于VTK渲染的場景可視化與場景交互的表現(xiàn)層。該系統(tǒng)以共形幾何代數(shù)為理論支持，多維統(tǒng)一建模為主線，場景動態(tài)分析為最終目標，實現(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)可視化模塊進行渲染可視化（圖5a）。在基于幾何代數(shù)的三維社區(qū)建模中，由于不同維度幾何對象均處于同一場景，可對其集中管理。圖5b演示了場景中對三維建筑對象的交互式選取與可視化功能。基于CGA框架的三維場景建?？蓪崿F(xiàn)場景中對象幾何關(guān)系的批量計算及運動對象動態(tài)插值。應用車輛模型和車輛位置模擬數(shù)據(jù)，可對車輛在場景中的運動情況進行動態(tài)模擬，并實時計算其距離與角度等基本幾何關(guān)系（圖5c），圖中雷達圖與箭頭圖分別顯示的是車與選中建筑的距離和角度。圖5d為運動對象插值計算演示，圖中黑色軌跡為讀取的原始數(shù)據(jù)，灰色軌跡為經(jīng)過versor插值后的樣點數(shù)據(jù)，由結(jié)果可知，基于versor的運動插值可保證插值軌跡相對均勻、平滑，且可推算出任意時刻車輛所在的位置信息及其運動參數(shù)。

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

4 結(jié)論與討論

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

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

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

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

［3］宋關(guān)福，鐘耳順，劉紀遠，等.多源空間數(shù)據(jù)無縫集成研究［J］.地理科學進展，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］.中國科學（D輯），2010，40（12）：1450－1461.

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

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

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

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

［10］刑燕，檀結(jié)實.圖形變換和運動的共形幾何代數(shù)表示方法［J］.計算機應用研究，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ù)與運動和形狀的刻畫［J］.計算機輔助設計與圖形學學報，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

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

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