基于點集的拉伸建模改進方法

楊　乃，賈　躍，蘇黎蘭，萬　林，楊　潔

(1. 中國地質大學信息工程學院，湖北 武漢 430074； 2. 揚州市城市規劃編制研究中心，江蘇揚州 225002； 3. 中國地質大學公共管理學院，湖北 武漢 430074)

?

基于點集的拉伸建模改進方法

楊乃1，賈躍2，蘇黎蘭3，萬林1，楊潔1

(1. 中國地質大學信息工程學院，湖北 武漢 430074； 2. 揚州市城市規劃編制研究中心，江蘇揚州 225002； 3. 中國地質大學公共管理學院，湖北 武漢 430074)

探討了拉伸建模存在公共基元重復構建、側面空間關系丟失、產生冗余基元等拓撲問題，指出了不同地物三維模型兩個側面之間拓撲關系存在的12種表現形式，提出了基于點集的自動拉伸建模方法，并分別介紹了點集的提取流程和體的構建流程，最后通過一個實例證明了以上方法對傳統拉伸建模方法在拓撲關系方面存在的不足有所改進。

拓撲關系；拉伸建模；三維建模；空間關系；地圖可視化

拓撲關系是最重要的一種空間關系[1-2]，是空間查詢與分析的基礎[3]，已廣泛應用于制圖綜合、空間推理、空間數據挖掘等實際應用中[4]。拓撲關系不一致將會導致空間認知錯誤，影響地圖的傳輸效果[2]。當前，三維模型的拓撲構建與分析已成為3DGIS的主要研究內容之一[5-10]。

以拉伸(Extrusion)的方式建立三維模型是3DGIS及三維建模軟件中常見的一種建模方法，尤其適用于具有規則形體結構的地物模型構建，如建筑物。這種建模方法往往不會考慮地物之間的拓撲關系，導致出現諸如公共面重復、垂直方向上空間關系丟失等問題，建立的模型常常僅限于可視化表達，無法進行進一步的空間分析[11]。針對這些問題，文獻[12]將整個區域的建筑和地形統一用一張Delaunay三角網表示，實現了類似拉伸的效果，但無法表達兩個相鄰建筑的垂直公共面；文獻[11]和文獻[13]基于約束性Delaunay三角網構建了拓撲一致的三維城市模型，其中產生的若干點、若干面仍然可以進一步綜合以降低拓撲復雜性。本文將對此進行改進，提出一種基于點集的自動拉伸建模方法，能夠改進傳統拉伸建模方法在拓撲關系方面存在的若干不足。

一、拉伸建模拓撲問題分析

三維空間中，體與體之間的拓撲關系共有8種[8-14]，在三維地籍與房產管理領域，建筑物的體對象之間只有相離和相鄰關系[5-6]，其底面也僅對應存在這兩種關系。拉伸建模是將一系列描述體狀地物底面的多邊形按指定高度進行拉伸拔高以形成塊狀多面體的三維建模方法，最適用于上述建筑體模型的建立[11]，如圖1所示。這種方式建立的三維模型主要存在如下拓撲問題。

圖1　拉伸建模圖示

1. 公共基元重復構建

結點、邊、面和體是4種拓撲基元[6]，如圖1(a)所示，多邊形A、B是俯視條件下相鄰地物的兩個底面示意圖，因高度不同，通過拉伸之后形成的三維模型如圖1(b)所示，其中，二者公共的部分(圖1(c)中mnde)的結點、邊、面在A、B拉伸時被分別構建。

2. 側面空間關系丟失

如圖1所示，即使底面A、B之間存在拓撲關系，但拉伸建模之后，側面形成的結點、邊、面，如圖1(a)邊def對應的側面(圖1(c))中共形成8個結點、10條邊、3個面，它們之間的相互關系并沒有得到有效存儲，不利于垂直方向上的空間分析。

3. 產生冗余基元

上文中公共基元重復構建將產生一些重復的基元。此外，還會產生一些不必要的基元，具體如下：

1) 在底面數據采集時，經常會出現多點重合的現象，拉伸建模后，頂面對應將會產生重合點。

2) 底面邊線中間的若干節點拉伸建模后，在頂面形成對應的節點，在對應側面上被拉伸成為一條條直線，將側面分割為多個子側面。如圖1(a)邊bcd拉伸后，點c在頂面對應形成點i，并被拉伸為直線ci，將側面bdjh分割為面bcih和面cdji(如圖1(c)所示)。

3) 多個具有不同高度屬性的底面相接時，某些公共點拉伸建模后將會導致冗余基元的產生。如圖1(a)所示，底面A與底面B高度屬性不同，拉伸建模后，邊def對應的側面理應被分割為具有相接關系的2個子側面，但實際上被劃分為3個子側面(如圖1(b)、圖1(c)所示)，其原因在于底面A拉伸后在點e對應的頂面邊上產生了多余點k，側面上產生了多余邊km。文獻[11]和文獻[13]尚未解決該問題。

二、側面拓撲關系分析

上述拓撲問題主要體現在三維模型側面上，根據拉伸建模原理，側面不可能出現島、洞等情況，只能是規則的簡單多邊形。簡單多邊形存在8種拓撲關系[15-18]，但拉伸形成的三維模型側面之間只存在相離、相接、相交、覆蓋、覆蓋于、相等6種拓撲關系。以2個地物為例，具體表現形式有12種(如圖2所示)。

圖2　側面拓撲關系

其中，圖2(g)表示兩個側面存在相等關系，圖2(c)和圖2(l)、圖2(d)和圖2(k)、圖2(h)和圖2(j)盡管對稱，但因地物之間的高度及判斷目標的先后順序不同，本文實現過程并不相同，因此將其列在圖2中。對于2個以上的地物，拉伸建模后可能出現一個三維模型側面與其他多個三維模型側面存在拓撲關系的情況，但也只是圖2各種情況的排列組合，本文每次只需考慮兩個側面即可。

三、基于點集的自動拉伸建模方法

為解決上述問題，本文首先根據地物高度及其底面之間的拓撲關系，提取一系列點，然后基于這些點構建三維模型的各個面，最終由這些面封閉構成體。

1. 點集的提取

構成三維模型的點集主要包括底面、頂面的結(節)點及側面上與其他三維模型相關聯的點。

(1) 底面重合點的處理

要避免拉伸建模后產生重合點，首先必須對底面重合點進行處理。重合點可以通過坐標值是否相同進行判斷，也可以通過點與點之間的拓撲關系進行判斷，找出重合點之后，只需保留其中一個點即可。

(2) 底面及頂面非拐點的處理

當節點關聯的兩條邊之間的夾角為180°，稱之為非拐點。非拐點是拉伸建模產生冗余基元的重要因素，主要表現為：①底面邊上的非拐點，但與其他底面沒有關聯關系，拉伸后導致頂面邊上也產生非拐點，如圖3中的點a，拉伸后頂面形成非拐點d，并在側面形成邊ad；②底面邊上的非拐點，與其他底面存在關聯關系，同時也是其他底面的非拐點，拉伸后導致兩個三維模型的頂面邊上都產生非拐點，如圖3中的點b，拉伸后在兩個頂面上分別形成非拐點e和f，并在側面形成邊be、ef；③較高三維模型底面上的非拐點，與其他底面存在關聯關系，但不是其他底面的非拐點，拉伸建模后在較高三維模型頂面形成非拐點，如圖3中的c點拉伸后在底面A對應的三維模型頂面形成非拐點h。這些非拐點并不需要提取，主要通過與之相關聯的兩條邊之間的夾角是否為180°來判斷。

圖3　非拐點示意圖

(3) 頂面及側面點的提取

頂面點是指頂面輪廓邊上的點，側面點是指側面內域及與底面垂直的側面邊上的點。對獨立地物而言，不存在側面點，構建頂面點時，x、y坐標值與對應底面點相同，z坐標在對應底面點z坐標值基礎上增加地物高度值即可。對與其他地物相鄰的地物而言，底面點與其他底面不存在關聯關系時，其對應頂面點的構建方法與獨立地物相同；底面點與多個底面相關聯時，則根據關聯底面的高度屬性從低到高排序，依次構建側面點，其中當多個關聯底面高度屬性值相等時，對應只構建一個側面點，各側面點x、y坐標值與對應底面點相同，z坐標在對應底面點z坐標值基礎上增加各關聯底面高度屬性值即可。

(4) 拓撲信息存儲

提取點集之后，需存儲各點與底面及底面點的對應關系，為方便后續體的構建，還需存儲各點的高程值及其排序。如圖4所示，具有同一底面關聯點的各點，可以通過高程值或高程排序判斷各點在Z方向上的連通關系；具有不同底面關聯點的各點(如點3、點4)，可以通過底面關聯點的排列序號及是否存在相同關聯底面來判斷在XY平面上是否存在連通關系等。

圖4　點的拓撲信息

2. 體的構建

若不考慮側面拓撲關系，底面點數為n時，拉伸建立的三維模型由n+2個面組成，但實際如上文所述，當地物相鄰時，某些側面將被分割為若干個子側面，組成三維模型的面數將大于n+2。因此，在體的構建過程中，為保證側面拓撲關系的正確性，最重要就是通過以上點集構建存儲拓撲信息的各個面。

(1) 底面構建

根據點集存儲的拓撲信息，找到地物關聯的底面點，連接封閉即可。

(2) 頂面構建

在點集中找到與底面點對應且高度屬性值為地物高度的點，連接封閉即可。

(3) 側面構建

根據上文分析可知，底面點在頂面上不一定有對應的點，如圖5中點c，因此在構建側面時，以頂面點為基準，在兩個連通頂面點對應的底面點之間尋找是否存在共享子側面，有則先構建該共享子側面，再判斷這兩個連通頂面點與對應底面點之間是否還存在非共享子側面，有則繼續構建該非共享子側面。如圖5所示，連通頂面點B、g對應的底面點A、d之間存在共享子側面，從點A開始尋找連通的底面點c，從點集中找到點A、c對應的側面點a、b，由這4個點即可構建共享子側面Aabc，構建完成后接著構建頂面點B、g與底面點A、d之間存在的非共享子側面aBgdcb，非共享子側面由共享子側面頂面點、不存在共享子側面的底面邊結點、連通頂面點共同構成。

圖5　側面構建圖示

(4) 體的構建及拓撲信息存儲

建立頂面、底面及側面后，為便于體的構建及空間查詢與分析，需存儲各面的類型信息，并建立4種拓撲基元的關聯關系，其中，建立面-面、面-體、體-體的拓撲關系是以拉伸的方式建立保持正確拓撲關系的三維地物模型的基礎。文獻[5]和文獻[6]指出了體的拓撲關系構建模型，由于拉伸建模形成的頂面、底面及側面都與底面點存在對應關系，因此，本文提出的方法中各面都記錄了底面關聯點。這樣，通過底面關聯點就可以判斷各面之間的拓撲關系，如圖5所示，側面aBgdcb的底面關聯點為點A、c、d，側面Aabc的底面關聯點為A、c，根據上文的側面拓撲關系分析及兩個面的共享基元點，很容易判斷兩者是相接關系。此外，對于頂面、底面而言，記錄包含它們的歸屬體及與它們有共享拓撲基元的關聯體；對于非共享子側面而言，記錄包含它們的歸屬體；對于共享子側面而言，記錄包含它們的所有關聯體(如圖6所示)。通過這種存儲方式，為面/面、面/體、體/體之間的空間查詢與分析提供了便利，構建體時只需根據以上存儲的拓撲信息找到相應的頂面、底面及側面封閉即可。

圖6　面的拓撲信息

3. 試驗與分析

本文基于VB.net+ArcGISEngine對以上方法進行了試驗，圖7(a)為某小區底面數據，提取點集后的結果如圖7(b)所示，最終提取點數為119個，而常見拉伸建模方法形成的點數為228個。基于提取的點集建立的三維模型如圖7(c)所示，該方法很好地解決了底面帶洞、島等復雜多邊形的建模問題。圖7(d)為ArcScene提供的Extrusion功能拉伸后的結果，將其與圖7(c)對比，二者內部結構不同(圖7(c)和(d)中底部區域)，本文建立的體模型結構更加簡單。此外，如圖7(e)所示，本文提出的方法還可用于基于面的空間查詢與分析。

圖7　試驗與分析

四、結束語

本文顧及三維模型的拓撲關系，提出了基于點集的自動拉伸建模改進方法，能夠改進拉伸建模在拓撲方面存在的若干不足。相比常見的拉伸建模方法，該方法提取的點數較少，并且隨著地物底面多邊形數及拓撲關系復雜性的增加，點數的減少量還將大大增加，以此構建的體的內部結構得到了簡化，并能提供面/面、面/體、體/體之間的空間查詢與分析。盡管如此，由于拉伸建模形成的三維模型還存在一些弱點[5]，對于側面為非規則多邊形、頂面非平行于底面的地物來說，如何建立保持其拓撲一致性的三維模型還有待進一步研究。

[1]鄧敏，李志林，李光強. 簡單面目標與帶孔洞面目標間拓撲關系的層次表達方法[J]. 測繪學報， 2008，37(3):330-337.

[2]詹陳勝，武芳，翟仁健，等. 基于拓撲一致性的線目標空間沖突檢測方法[J]. 測繪科學技術學報，2011，28(5):387-390.

[3]吳信才. 地理信息系統原理與方法[M]. 北京: 電子工業出版社, 2009: 48-51.

[4]鄧敏，馬杭英. 線與面目標間拓撲關系的層次表達方法[J]. 測繪學報，2008，37(4):507-513.

[5]郭仁忠，應申，李霖. 基于面片集合的三維地籍產權體的拓撲自動構建[J]. 測繪學報，2012，41(4):620-626.

[6]李霖，趙志剛，郭仁忠，等. 空間體對象間三維拓撲構建研究[J]. 武漢大學學報(信息科學版)，2012，37(6):719-723.

[7]賀彪，李霖，郭仁忠，等. 顧及外拓撲的異構建筑三維拓撲重建[J]. 武漢大學學報(信息科學版)，2011，36(5):579-583.

[8]劉新，劉文寶，李成名. 三維體目標間拓撲關系與方向關系的混合推理[J]. 武漢大學學報(信息科學版)，2010，35(1):74-78.

[9]鄧念東，侯恩科. 三維體元拓撲數據模型的修正及其形式化描述[J]. 武漢大學學報(信息科學版)，2009，34(1):52-56.

[10]陳鵬，孟令奎，宋楊. 三維GIS中基于空間拓撲約束條件的R樹研究[J]. 武漢大學學報(信息科學版)，2007，32(4):347-349.

[11]LEDOUXH,MEIJERSM.TopologicallyConsistent3DCityModelsObtainedbyExtrusion[J].InternationalJournalofGeographicalInformationScience，2011, 25(4):557-574.

[12]TSEROC,DAKOWICZM,GoldCM,etal.BuildingReconstructionUsingLiDARData[C]∥Proceedingsof4thISPRSWorkshoponDynamicandMulti-dimensionalGIS.Pontypridd,Wales,UK：[s.n.], 2005：156-161.

[13]LEDOUXH,MEIJERSM.ExtrudingBuildingFootprintstoCreateTopologicallyConsistent3DCityModels[J].UrbanandRegionalDataManagement-UDMSAnnuals，2009(1): 39-48.

[14]ZLATANOVAS,RAHMANAA,SHIW.TopologicalModelsandFrameworksfor3DSpatialObjects[J].Computers&Geosciences, 2004(30):419-428.

[15]劉波，李大軍，鄒時林，等. 帶孔洞面域間的拓撲關系的組合推理[J]. 測繪學報，2011，40(2):262-267.

[16]沈敬偉，閭國年，溫永寧，等. 拓撲和方向空間關系組合描述及其相互約束[J]. 武漢大學學報(信息科學版)，2011，36(11):1305-1308.

[17]汪西莉，覃婧嬋，曹菡，等. 基于SRC-Ontology的空間拓撲關系拓展表示方法及實現[J]. 武漢大學學報(信息科學版)，2009，34(3):339-343.

[18]劉波，李大軍，阮見，等. 帶空洞面對象間拓撲關系形式化描述[J]. 武漢大學學報(信息科學版)，2009，34(1):68-71.

ImprovedExtrusionModelingMethodBasedonPointSet

YANGNai,JIAYue,SULilan,WANLin,YANGJie

2015-05-26

國家自然科學基金(41201474；41401449)

楊乃(1984—)，男，博士，講師，主要研究方向為三維地圖可視化。E-mail：naigeer@163.com

P208

B

0494-0911(2016)05-0041-04

引文格式： 楊乃，賈躍，蘇黎蘭,等. 基于點集的拉伸建模改進方法[J].測繪通報，2016(5)：41-44.DOI:10.13474/j.cnki.11-2246.2016.0151.