基于CGAL的三維空間布爾運(yùn)算功能分析與設(shè)計(jì)

賀 彪，趙志剛，夏 俊

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

一、引 言

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

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

二、CGAL概述

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

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

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

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

4)開(kāi)源，其類(lèi)庫(kù)的不同程序包分別以QPL或LGPL開(kāi)源證書(shū)的模式進(jìn)行開(kāi)源。

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

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

1．Halfedge

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

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

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

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

2．整體流程

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

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

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

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

圖3 空間體的布爾求交

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

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

3．問(wèn)題分析

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

1)CGAL中的Polyhedral中的面不能含有空洞，因此用來(lái)進(jìn)行布爾運(yùn)算的體不能有含有空洞的面。

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

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

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

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

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

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

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

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

四、結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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