基于CGAL的三維空間布爾運算功能分析與設計

賀 彪，趙志剛，夏 俊

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

一、引 言

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

計算幾何是計算機科學的一個分支，主要研究解決幾何問題的算法。計算幾何所需解決的問題包括兩方面:一方面是相關幾何概念在計算機中的表示;另一方面是解決具體的幾何問題。要解決實際的幾何問題，首先要設計一套完整的幾何數據模型，用于在計算機中描述相關幾何概念，如點線面在計算機中的描述、向量在計算機中的描述等。在其基礎上，進一步實現具體算法來解決如下類似的幾何問題，如判斷折線段拐彎、判斷點是否在線段上、判斷兩線段是否相交等。“計算幾何”作為一個被廣泛認同的學科，擁有其獨立的學術刊物和學術會議，并形成了一個由眾多研究人員組成的學術團體。它在研究學科方面的生命力，一方面是因為其所研究問題和得到解決的優美性，另一方面是由于其應用領域的廣泛性。圖像處理、計算機圖形學、CAD/CAM、地理信息系統、機器人等領域中，研究人員會碰到大量與幾何有關的算法問題，計算幾何則提供了一系列解決此類問題的算法、數據結構和幾何范式。基于計算幾何領域成熟的CGAL算法庫可以開發出穩定、高效的三維空間布爾運算功能。

二、CGAL概述

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

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

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

3)應用于許多商業軟件，性能穩定。

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

三、設計與實現

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

1．Halfedge

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

在構成多面體的3要素(點、邊、面)中，半邊數據結構以邊為核心，但它將一條邊表示成拓撲意義上方向相反的兩條“半邊”，因此稱為半邊數據結構，其結構如圖1所示。

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

圖1 半邊數據模型示意圖

2．整體流程

由于CGAL的三維數據結構和各種不同應用場景的三維系統中所使用的三維數據結構不完全一致，因此需要進行兩種模型之間的轉換。CGAL采用拓撲數據結構，高維對象由低維對象組合構成，如三維體由空間面構成，空間面都是由邊構成。這與一般的三維系統基本類似，只是拓撲元素的構建的接口有些許差異，如CGAL中構建一個不含有空洞的面時只需順序傳入一串點即可，接口內部會自動將相鄰點連接起來構成線段，然后構成不含有空洞的面;而一般的系統中構建一個不含有空洞的面(與“不含有空洞的面”等效的拓撲元素稱為環)可能需要先添加點，然后指明每一條線段兩端的端點指針，然后再指明每一個不含有空洞的面(環)由哪些線段構成。

三維數據模型差異可以由圖2粗略地表示出來，編號1和編號2框圖內容表示無法直接創建的結構，而是對象中包含的邏輯概念。

圖2 CGAL與一般三維數據模型對比

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

圖3 空間體的布爾求交

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

圖4 系統實現流程圖

3．問題分析

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

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

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

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

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

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

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

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

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

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

四、結束語

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

表1 空間體空間關系規則表

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

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

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

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

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

［6］ 楊蘭．三維網格模型實體布爾運算方法的研究與實現［D］．長沙:中南大學，2011．

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

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

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

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

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

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

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

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

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