賀 彪，趙志剛，夏 俊

(1．深圳市數(shù)字城市工程研究中心，廣東 深圳518040;2．中冶南方(武漢)信息技術(shù)工程有限公司，湖北 武漢430223)

一、引 言

三維空間對象的布爾運算功能是3D CAD、3D GIS和其他三維建模分析軟件的核心功能，通過對三維空間的對象進行交、并、補、差等運算可以構(gòu)造出新的復(fù)雜實體。早年的CAD技術(shù)基于立方體、圓柱體、錐體等規(guī)則的基本體素，進行組合表達復(fù)雜的零件、建筑構(gòu)件等實體，即體素幾何造型［1］。隨著技術(shù)發(fā)展，建筑形體更加復(fù)雜，同時3D GIS的發(fā)展，側(cè)重表達現(xiàn)實中復(fù)雜的、不規(guī)則的地理現(xiàn)象的需求愈發(fā)明顯，體素幾何造型發(fā)展為能滿足對任意不規(guī)則實體表達的實體模型［2］。實體模型由于其實體構(gòu)造形態(tài)的任意性，實體間布爾運算算法的復(fù)雜程度遠(yuǎn)高于體素的布爾運算算法，開發(fā)出正確、穩(wěn)定、高效三維空間布爾運算功能是一項復(fù)雜且極具挑戰(zhàn)的工作，需要大量的幾何算法知識和高超的編程技巧［3-6］。

計算幾何是計算機科學(xué)的一個分支，主要研究解決幾何問題的算法。計算幾何所需解決的問題包括兩方面:一方面是相關(guān)幾何概念在計算機中的表示;另一方面是解決具體的幾何問題。要解決實際的幾何問題，首先要設(shè)計一套完整的幾何數(shù)據(jù)模型，用于在計算機中描述相關(guān)幾何概念，如點線面在計算機中的描述、向量在計算機中的描述等。在其基礎(chǔ)上，進一步實現(xiàn)具體算法來解決如下類似的幾何問題，如判斷折線段拐彎、判斷點是否在線段上、判斷兩線段是否相交等?！坝嬎銕缀巍弊鳛橐粋€被廣泛認(rèn)同的學(xué)科，擁有其獨立的學(xué)術(shù)刊物和學(xué)術(shù)會議，并形成了一個由眾多研究人員組成的學(xué)術(shù)團體。它在研究學(xué)科方面的生命力，一方面是因為其所研究問題和得到解決的優(yōu)美性，另一方面是由于其應(yīng)用領(lǐng)域的廣泛性。圖像處理、計算機圖形學(xué)、CAD/CAM、地理信息系統(tǒng)、機器人等領(lǐng)域中，研究人員會碰到大量與幾何有關(guān)的算法問題，計算幾何則提供了一系列解決此類問題的算法、數(shù)據(jù)結(jié)構(gòu)和幾何范式?；谟嬎銕缀晤I(lǐng)域成熟的CGAL算法庫可以開發(fā)出穩(wěn)定、高效的三維空間布爾運算功能。

二、CGAL概述

CGAL全稱為計算幾何算法庫(computational geometry algorithms library)，是一個大型的，基于C++的幾何數(shù)據(jù)結(jié)構(gòu)和算法庫，由計算幾何領(lǐng)域頂尖的高校聯(lián)合開發(fā)，包含了諸如Delaunay三角網(wǎng)構(gòu)建、網(wǎng)格生成、多邊形布爾運算等各種幾何處理算法。CGAL被廣泛應(yīng)用于計算機圖形學(xué)、科學(xué)可視化、計算機輔助設(shè)計與建模、地理信息系統(tǒng)、分子生物學(xué)、醫(yī)學(xué)影像學(xué)、機器人學(xué)和運動規(guī)劃，以及數(shù)值方法等領(lǐng)域。CGAL一共有60多個程序包，劃分成Geometry Kernels、Convex Hull Algorithms、Polygons等17個模塊(Parts)。作為比較成熟的計算幾何算法庫，CGAL具有如下優(yōu)點:

1)完整的三維數(shù)據(jù)模型和強大的三維幾何算法支持。

2)完整的開發(fā)文檔和示例程序，便于開發(fā)。

3)應(yīng)用于許多商業(yè)軟件，性能穩(wěn)定。

4)開源，其類庫的不同程序包分別以QPL或LGPL開源證書的模式進行開源。

三、設(shè)計與實現(xiàn)

為了實現(xiàn)三維空間的布爾運算，主要使用了CGAL Polyhedra模塊中的Halfedge Data Structures、3D Polyhedral Surface、3D Boolean Operations on Nef Polyhedra等程序包。

1．Halfedge

Halfedge(半邊)數(shù)據(jù)結(jié)構(gòu)也稱作雙向邊鏈表(doubly connected edge list，DCEL)，半邊結(jié)構(gòu)描述拓?fù)鋱D結(jié)構(gòu)，包含每個點、線、面的記錄，用來表達如平面圖、多面體或嵌入任意維空間的有向二維表面。在CGAL中Halfedge Data Structures(半邊數(shù)據(jù)結(jié)構(gòu))程序包描述的是模塊Polyhedra使用的底層數(shù)據(jù)結(jié)構(gòu)，其他各個程序包都是使用這個數(shù)據(jù)結(jié)構(gòu)來對空間體進行描述，

在構(gòu)成多面體的3要素(點、邊、面)中，半邊數(shù)據(jù)結(jié)構(gòu)以邊為核心，但它將一條邊表示成拓?fù)湟饬x上方向相反的兩條“半邊”，因此稱為半邊數(shù)據(jù)結(jié)構(gòu)，其結(jié)構(gòu)如圖1所示。

半邊是連接兩個頂點并具有固定方向的線段．半邊的關(guān)系是一個邊包含兩個相反方向的半邊(如圖1中的halfedge和opposite halfedge)，由這兩個半邊可以查詢交于這個邊的兩個面。半邊數(shù)據(jù)結(jié)構(gòu)是CGAL中表達多面體表面的核心結(jié)構(gòu)，本文不作詳細(xì)介紹。

圖1 半邊數(shù)據(jù)模型示意圖

2．整體流程

由于CGAL的三維數(shù)據(jù)結(jié)構(gòu)和各種不同應(yīng)用場景的三維系統(tǒng)中所使用的三維數(shù)據(jù)結(jié)構(gòu)不完全一致，因此需要進行兩種模型之間的轉(zhuǎn)換。CGAL采用拓?fù)鋽?shù)據(jù)結(jié)構(gòu)，高維對象由低維對象組合構(gòu)成，如三維體由空間面構(gòu)成，空間面都是由邊構(gòu)成。這與一般的三維系統(tǒng)基本類似，只是拓?fù)湓氐臉?gòu)建的接口有些許差異，如CGAL中構(gòu)建一個不含有空洞的面時只需順序傳入一串點即可，接口內(nèi)部會自動將相鄰點連接起來構(gòu)成線段，然后構(gòu)成不含有空洞的面;而一般的系統(tǒng)中構(gòu)建一個不含有空洞的面(與“不含有空洞的面”等效的拓?fù)湓胤Q為環(huán))可能需要先添加點，然后指明每一條線段兩端的端點指針，然后再指明每一個不含有空洞的面(環(huán))由哪些線段構(gòu)成。

三維數(shù)據(jù)模型差異可以由圖2粗略地表示出來，編號1和編號2框圖內(nèi)容表示無法直接創(chuàng)建的結(jié)構(gòu)，而是對象中包含的邏輯概念。

圖2 CGAL與一般三維數(shù)據(jù)模型對比

空間體的布爾運算主要指求解兩個三維空間體的交集、并集、差集。對兩個三維空間體進行空間布爾操作是為了能夠利用已有的三維空間體，通過求交、合并、求差等產(chǎn)生新的三維空間體。它與二維多邊形的布爾操作有類似之處，只是操作的對象和操作的結(jié)果提升到了三維。圖3展示了兩個三維空間體求交，即求取公共部分，得出新的體。圖3(b)中的白色部分就是圖3(a)深色體和淺色體求交的結(jié)果。

圖3 空間體的布爾求交

空間布爾操作的功能主要是借用CGAL庫的空間計算功能進行求解，主要思想是將在內(nèi)存中的空間三維體的結(jié)構(gòu)轉(zhuǎn)換為CGAL中對空間三維體的描述，然后利用它所提供的函數(shù)進行空間操作，最后將得到的CGAL結(jié)果轉(zhuǎn)換回來。由于一般三維系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)只能轉(zhuǎn)化為CGAL中的Polyhedral，而CGAL中支持空間布爾操作的是Nef-Polyhedral，因此轉(zhuǎn)換過程有兩個步驟:首先將三維產(chǎn)權(quán)體的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換成CGAL中Polyhedral的數(shù)據(jù)結(jié)構(gòu)，然后利用CGAL內(nèi)部的功能將Polyhedral轉(zhuǎn)化為Nef-Polyhedral，利用Nef-Polyhedral進行空間操作后，同樣要將得到的Nef-Polyhedral轉(zhuǎn)化為Polyhedral，最后轉(zhuǎn)化為三維產(chǎn)權(quán)體的數(shù)據(jù)結(jié)構(gòu)。主要流程如圖4所示，其中的空間判交操作詳見問題分析。

圖4 系統(tǒng)實現(xiàn)流程圖

3．問題分析

由于CGAL的一些限制，轉(zhuǎn)換過程中必須滿足一些約束:

1)CGAL中的Polyhedral中的面不能含有空洞，因此用來進行布爾運算的體不能有含有空洞的面。

2)只有封閉的CGAL Polyhedral才能轉(zhuǎn)化為CGAL Nef-Polyhedral。

3)只有簡單(simple)的CGAL Nef-Polyhedral才能轉(zhuǎn)化為CGAL Polyhedral，因此存在空間運算的結(jié)果無法轉(zhuǎn)換回Polyhedral的情況。如兩個三維空間體存在共面、共線或共點的情況時，進行空間操作就會產(chǎn)生不簡單的Nef-Polyhedral。

Polyhedral僅能表達簡單的二維流形(manifold)，Nef-Polyhedral可以表達非二維流形，因此存在Nef-Polyhedral不能轉(zhuǎn)化為Polyhedral的情形。理論上二維流形的布爾運算結(jié)果并不能保證是一個二維流形，因此并不是所有三維空間體的布爾運算結(jié)果都能轉(zhuǎn)換回Polyhedral。由轉(zhuǎn)換過程中的約束可以總結(jié)出CGAL中進行布爾操作時的局限性如下:

1)合并時，只要有公共點或邊，就會得出非簡單(非二維流形)的體，其他情況下都能正確運行。

2)求交時，情況比較復(fù)雜，只有在相交且沒有共面、共邊和共點的情況下才能正常工作。

3)求差時，只有既有相交的部分，又有重合的面的時候會出現(xiàn)非簡單(非二維流形)的體，其他情況下都能正確運行。

4)另外如前面所述，進行空間操作和空間關(guān)系判斷的空間三維體不能包含帶有空洞的面。

CGAL庫中沒有提供直接判斷兩個三維空間體的空間關(guān)系的函數(shù)，在實踐中可以通過兩個體空間布爾操作的結(jié)果來進行兩個空間三維體關(guān)系的判斷。表1中，Volume數(shù)是指Nef-Polyhedral作為空間操作的結(jié)果時，將對應(yīng)空間進行剖分后得到的數(shù)目。具體判斷空間體之間的空間關(guān)系時，相應(yīng)規(guī)則由表1分析得出:當(dāng)兩個體相離時求交結(jié)果的Volume數(shù)必然為1且簡單;當(dāng)兩個體相切時求交結(jié)果的Vomume數(shù)必然為1且不簡單;當(dāng)兩個體相交時求交結(jié)果的Volume數(shù)必然大于1。表1對三維空間體的關(guān)系判斷給出了建議，表中V表示Volume數(shù)，S表示是否為簡單體，可以作為三維空間體判交操作的依據(jù)。

四、結(jié)束語

本文對基于CGAL實現(xiàn)三維空間布爾運算功能進行了分析，給出了實現(xiàn)流程，并對CGAL的約束和局限進行了詳細(xì)闡述。基于文本的思想，筆者在深圳市三維地籍信息系統(tǒng)中的開發(fā)中實現(xiàn)了三維空間布爾運算功能模塊，效率和穩(wěn)定性在實踐中得到了良好的驗證。

表1 空間體空間關(guān)系規(guī)則表

［1］ 陳輝．基于實體模型的布爾運算算法與實現(xiàn)［D］．泰安:山東科技大學(xué)，2007．

［2］ 王紅娟．三維實體建模及布爾運算造型技術(shù)［D］．泰安:山東科技大學(xué)，2007．

［3］ 崔璨，王結(jié)臣．一種基于梯形剖分的多邊形布爾運算方法［J］．測繪學(xué)報，2011，40(1):104-110．

［4］ 周志超．基于降維的三維布爾運算算法與實現(xiàn)［J］．微計算機信息，2009，25(6):176-177，164．

［5］ 孫殿柱，李心成，田中朝，等．基于動態(tài)空間索引結(jié)構(gòu)的三角網(wǎng)格模型布爾運算［J］．計算機輔助設(shè)計與圖形學(xué)學(xué)報，2009，21(9):1232-1237．

［6］ 楊蘭．三維網(wǎng)格模型實體布爾運算方法的研究與實現(xiàn)［D］．長沙:中南大學(xué)，2011．

［7］ 劉金義，歐宗瑛．多面體布爾運算中位置關(guān)系的判別［J］．計算機工程，1994(3):7-10，26．

［8］ 武運興．基于邊界識別的多邊形的布爾運算［J］．計算機輔助設(shè)計與圖形學(xué)學(xué)報，1994，6(4):260-265．

［9］ 曹偉，陸長德．多面體模型布爾運算算法及其穩(wěn)定性［J］．西安工業(yè)學(xué)院學(xué)報，1997，17(1):23-28．

［10］ 楊振羽，鄭文庭，彭群生．一般點模型的交互式布爾運算［J］．計算機輔助設(shè)計與圖形學(xué)學(xué)報，2005，17(5):954-961．

［11］ 姚輝學(xué)，盧章平．海量數(shù)據(jù)多邊形布爾運算的區(qū)域分割算法［J］．中國圖象圖形學(xué)報，2007，12(3):552-557．

［12］ 劉紅軍，王從軍，黃樹槐．帶有孔洞的多邊形的布爾運算［J］．華中科技大學(xué)學(xué)報:自然科學(xué)版，2003，31(8):18-20．

［13］ 邵士春．軌道交通構(gòu)筑物的CSG/B-rep三維模型布爾運算算法研究［D］．石家莊:石家莊鐵道大學(xué)，2012．

［14］ 朱振華．二維布爾運算的奇異情況研究［D］．上海:上海交通大學(xué)，2008．

［15］ 周志超．基于降維的三維布爾運算算法與實現(xiàn)［D］．上海:上海交通大學(xué)，2008．