二維輪廓布爾運算干涉標志算法研究

曹文杰， 胡德計

（1. 河北工業大學材料學院，天津 300130；2. 天津工程師范學院機械系，天津 300222）

1 二維布爾運算與干涉標志法

二維輪廓的布爾運算是計算機圖形學的基本算法之一，它被廣泛的應用于二維圖形的幾何造型中。由于一些復雜空間幾何造型問題可以轉化為二維輪廓的布爾運算來解決，因此二維布爾運算算法研究是計算圖形學的一個重要問題[1]。

二維布爾運算就是兩個或多個平面圖形作交、并、差、覆蓋和剪取等運算操作。目前人們在這方面已進行了大量有益的探索，并且有多種算法[2-4]。這些算法雖然各有特點，但是存在諸如線段的屬性規定較復雜、運算過程較繁復、對于不同的布爾運算集需要進行不同的運算過程、算法效率不高、算法實現的一致性不好等問題。

干涉標志法[5]最早用于型腔輪廓的等距輪廓生成算法，是型腔加工刀具軌跡生成的基本算法之一，干涉標志法的詳細算法實現參見文獻[6]的介紹。干涉標志法的基本思想是將輪廓以輪廓邊界分為材質區域（如圖1 中陰影區域）和非材質區域（如圖1 中空白區域），當某段外部輪廓進入材質區域中，則該輪廓段發生干涉，這時將其干涉標志賦值為1；如某段外部輪廓離開材質區域中，則該段輪廓段沒有發生干涉，這時將其干涉標志賦值為0。如圖1 所示。

圖1 干涉標志示意圖

雖然干涉標志法最初是應用于型腔輪廓的等距輪廓生成的算法，通過研究發現其算法原理和思路也可以運用于二維布爾運算中。從而衍生出一個實現二維布爾運算的新算法。算法的基本思路是：先計算所有參與布爾運算的輪廓段的干涉標志，注意計算干涉標志時在相交點要把輪廓段打斷。然后在計算后的輪廓段中根據具體的布爾運算操作的要求按規則挑選具有不同干涉標志的輪廓段，從而可以得到相應的布爾運算結果集。

2 二維圖形輪廓表達

零件表面的輪廓段一般由直線、圓弧和自由曲線等構成。為簡化處理過程，可以認為零件的整體輪廓均是由直線和圓弧構成的。其中，對于自由曲線可以將其離散為一系列直線段，根據自由曲線輪廓段的表面粗糙度要求，采用有理B 樣條插值算法確定該輪廓段內的插值點。這樣便可以建立整體輪廓的統一描述。經過這樣處理后，可以避免輪廓偏移過程中對自由曲線進行單獨處理時，求自由曲線的偏移過程中其起始點法矢難以確定以及自由曲線的偏移輪廓與鄰近輪廓段的偏移輪廓間的連接問題。在整個偏移算法中只需要處理直線和圓弧的偏移，便可以得到整段輪廓的偏移輪廓。簡化了算法的實現難度，提高了可靠性。

輪廓的邊界可由一系列有向的輪廓邊界組 成[5]（見圖2）。如果把構成輪廓表面的各輪廓段統一稱為節點(knot)，那么整條輪廓便是由多個首尾相連接的節點所組成。每一節點內含有一個描述邊界性質的幾何點點集。直線是一個包含起點和終點兩個幾何點的節點；圓弧是一個包含起點、終點和圓心3 個幾何點的節點；而自由曲線則是一個包含多個幾何點（型值點）點集的節點。

圖2 型腔輪廓的表達

對于輪廓邊界可以用集合表示如下：

KnotList = { Knot1, Knot2, …, Knotn}

其中：Knoti(1) = Knoti+1(0) i = 1, 2, …, n-1.

在程序實現上，整個型腔輪廓可以用單向鏈表來表達。

采用節點的描述方法，可以建立各輪廓段對外的統一接口。將各節點的指針壓入單向鏈表結構中，便可以得到用于描述整條輪廓的邊界鏈，邊界鏈經離散處理后便可形成一條只由直線和圓弧構成的偏移邊界鏈來進行操作。

3 布爾運算算法

基于以上的輪廓表達方式，二維布爾運算可以通過對各段相交輪廓設立干涉標志來實現。結合一個具體的實例介紹其算法實現，在此主要介紹二維圖形的并運算。規定沿著幾何輪廓逆時針走向定義節點并且材質在左手邊。如圖3 所示，左邊為A 輪廓(A1-A7)，右邊為B 輪廓(B1-B4)。

（1） 分別求出兩條鏈中每一條邊的交點P1, P2, …, P6。

（2） 在交點處，將兩條鏈的邊打斷，并將打斷后形成的新邊插入輪廓鏈中。如圖中P6A3， A3P5, P5A4 等均為形成的新邊。

（3） 分別遍歷兩條輪廓鏈，為每一條邊設立干涉標志：對于A 鏈，從A1A2 開始設其干涉標志為0，如果鏈中的某一條邊進入到另一條鏈的材質區內（例如A2A3），則該條邊進入材質區內的部分干涉標志加1（例如P6A3 為1）；對于離開另一條鏈的材質區內的部分，其干涉標志減1（例如P5A4 被設為0）；每一條邊的起點的干涉標志等于上一條邊的干涉標志，例如A2P6 為0, A3P5 為1，A4P4 為1 等等。

圖3 平面圖形的布爾運算

（4） 在兩條鏈中分別刪除干涉標志為1 的輪廓段，即干涉段。重新鏈接兩條鏈中干涉標志為0 的輪廓段，即未干涉段。這樣可以得到c、 d、 e 三條新鏈，如圖3 所示。所形成的新鏈即為兩條鏈A 和B 作布爾并運算所得到的新鏈。

通過以上并運算的算法過程可以看出，在分別計算完輪廓A、B 的干涉標志后，在形成新環時，采用不同規則挑選具有不同干涉標志的邊即可得到不同的布爾運算結果集。其挑選規則如下：

1） 并運算：分別提取初始輪廓A、B 的干涉標志為0 的輪廓段，形成新的并運算輪廓，如圖4(a)所示；

2） 交運算：分別提取初始輪廓A、B 的干涉標志為1 的輪廓段，形成新的交運算輪廓，如圖4(b)所示；

3） 差運算(A–B)：分別提取初始輪廓A 中干涉標志為0 的輪廓段和B 中干涉標志為1 的輪廓段，形成新的差運算輪廓，如圖4(c)所示；

4） 差運算(B–A)：分別提取初始輪廓A 中干涉標志為1 的輪廓段和B 中干涉標志為0 的輪廓段，形成新的差運算輪廓。如圖4(d)所示。

圖4 干涉標志與布爾運算

4 結 論

基于干涉標志法的二維布爾運算首先計算二維輪廓段的干涉標志，然后根據具體布爾運算操作，在計算后的輪廓中根據挑選規則挑選具有不同干涉標志的輪廓段構成新鏈，從而得到布爾運算結果集。采用干涉標志法可以簡化二維布爾運算的計算過程。根據干涉標志值采用不同的輪廓段拾取規則，經過一次計算就可以得到所有的二維布爾運算集。該算法具有輪廓表達清晰，算法實現簡單，一致性好的特點。目前該算法已在計算機上實現，并運用于數控車削和型腔銑削加工的等距輪廓生成算法中，取得了良好效果。

[1] 梅樹立, 張彥娥, 等. 計算機圖形學中二維布爾運 算的穩定性分析[J]. 中國農業大學學報, 2001, 6(4)： 81-84.

[2] 謝步瀛, 張 巖. 用分段法與鏈表法的二維布爾運算算法[J]. 工程圖學學報, 2003, 24(2)： 78-84.

[3] 鄭家驤, 方 向, 等. 刀位軌跡的干涉標志量的改進算法[J]. 機械制造, 1999, (1)： 17-19.

[4] 武運興. 基于邊界識別的多邊形的布爾運算[J]. 計算機輔助設計與圖形學學報, 1994, 6(4)： 260-265.

[5] Held M, Lukacs G, Andor L. Pocket machining based on contour —— parallel tool generated by means of proximity maps [J]. Computer-Aided Design, 1994, 26(3)： 189-203.

[6] ALLAN HANSEN, FARHD ARBAB. An algorithm for generating Nc tool paths for arbitrarily shaped pockets with islands [J]. ACM Transaction on Graphics, 1992, 11(2)： 152-182.