二維輪廓布爾運(yùn)算干涉標(biāo)志算法研究

曹文杰， 胡德計(jì)

（1. 河北工業(yè)大學(xué)材料學(xué)院，天津 300130；2. 天津工程師范學(xué)院機(jī)械系，天津 300222）

1 二維布爾運(yùn)算與干涉標(biāo)志法

二維輪廓的布爾運(yùn)算是計(jì)算機(jī)圖形學(xué)的基本算法之一，它被廣泛的應(yīng)用于二維圖形的幾何造型中。由于一些復(fù)雜空間幾何造型問題可以轉(zhuǎn)化為二維輪廓的布爾運(yùn)算來解決，因此二維布爾運(yùn)算算法研究是計(jì)算圖形學(xué)的一個(gè)重要問題[1]。

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

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

圖1 干涉標(biāo)志示意圖

雖然干涉標(biāo)志法最初是應(yīng)用于型腔輪廓的等距輪廓生成的算法，通過研究發(fā)現(xiàn)其算法原理和思路也可以運(yùn)用于二維布爾運(yùn)算中。從而衍生出一個(gè)實(shí)現(xiàn)二維布爾運(yùn)算的新算法。算法的基本思路是：先計(jì)算所有參與布爾運(yùn)算的輪廓段的干涉標(biāo)志，注意計(jì)算干涉標(biāo)志時(shí)在相交點(diǎn)要把輪廓段打斷。然后在計(jì)算后的輪廓段中根據(jù)具體的布爾運(yùn)算操作的要求按規(guī)則挑選具有不同干涉標(biāo)志的輪廓段，從而可以得到相應(yīng)的布爾運(yùn)算結(jié)果集。

2 二維圖形輪廓表達(dá)

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

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

圖2 型腔輪廓的表達(dá)

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

KnotList = { Knot1, Knot2, …, Knotn}

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

在程序?qū)崿F(xiàn)上，整個(gè)型腔輪廓可以用單向鏈表來表達(dá)。

采用節(jié)點(diǎn)的描述方法，可以建立各輪廓段對(duì)外的統(tǒng)一接口。將各節(jié)點(diǎn)的指針壓入單向鏈表結(jié)構(gòu)中，便可以得到用于描述整條輪廓的邊界鏈，邊界鏈經(jīng)離散處理后便可形成一條只由直線和圓弧構(gòu)成的偏移邊界鏈來進(jìn)行操作。

3 布爾運(yùn)算算法

基于以上的輪廓表達(dá)方式，二維布爾運(yùn)算可以通過對(duì)各段相交輪廓設(shè)立干涉標(biāo)志來實(shí)現(xiàn)。結(jié)合一個(gè)具體的實(shí)例介紹其算法實(shí)現(xiàn)，在此主要介紹二維圖形的并運(yùn)算。規(guī)定沿著幾何輪廓逆時(shí)針走向定義節(jié)點(diǎn)并且材質(zhì)在左手邊。如圖3 所示，左邊為A 輪廓(A1-A7)，右邊為B 輪廓(B1-B4)。

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

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

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

圖3 平面圖形的布爾運(yùn)算

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

通過以上并運(yùn)算的算法過程可以看出，在分別計(jì)算完輪廓A、B 的干涉標(biāo)志后，在形成新環(huán)時(shí)，采用不同規(guī)則挑選具有不同干涉標(biāo)志的邊即可得到不同的布爾運(yùn)算結(jié)果集。其挑選規(guī)則如下：

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

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

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

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

圖4 干涉標(biāo)志與布爾運(yùn)算

4 結(jié) 論

基于干涉標(biāo)志法的二維布爾運(yùn)算首先計(jì)算二維輪廓段的干涉標(biāo)志，然后根據(jù)具體布爾運(yùn)算操作，在計(jì)算后的輪廓中根據(jù)挑選規(guī)則挑選具有不同干涉標(biāo)志的輪廓段構(gòu)成新鏈，從而得到布爾運(yùn)算結(jié)果集。采用干涉標(biāo)志法可以簡(jiǎn)化二維布爾運(yùn)算的計(jì)算過程。根據(jù)干涉標(biāo)志值采用不同的輪廓段拾取規(guī)則，經(jīng)過一次計(jì)算就可以得到所有的二維布爾運(yùn)算集。該算法具有輪廓表達(dá)清晰，算法實(shí)現(xiàn)簡(jiǎn)單，一致性好的特點(diǎn)。目前該算法已在計(jì)算機(jī)上實(shí)現(xiàn)，并運(yùn)用于數(shù)控車削和型腔銑削加工的等距輪廓生成算法中，取得了良好效果。

[1] 梅樹立, 張彥娥, 等. 計(jì)算機(jī)圖形學(xué)中二維布爾運(yùn) 算的穩(wěn)定性分析[J]. 中國(guó)農(nóng)業(yè)大學(xué)學(xué)報(bào), 2001, 6(4)： 81-84.

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

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

[4] 武運(yùn)興. 基于邊界識(shí)別的多邊形的布爾運(yùn)算[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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.