2.4　定性立體操作

2.4.1　領域演算

雖然基本的領域網絡操作可以構建定性立體模型，但是領域演算是更有效的方法。對兩個具有確定空間關系的已有領域實施空間的且定性的和、差、積集合運算，在生成新的領域之后，可自動導出新領域與原來已有所有領域的關系，這樣的操作被稱為領域演算。領域演算包括弱和演算、強和演算、差演算和積演算［10，11］。

2.4.1.1　領域的弱和演算

對已有兩個領域A和B實施領域的弱和演算，將產生包容這兩個領域的最小領域。包容任意兩個領域的最小領域一定存在而且是唯一的。弱和演算的結果是一個領域。該領域有可能不僅僅包容原來的兩個領域所占據的空間，而且也包容其他部分空間。領域的弱和演算不是嚴格意義上的空間集合運算。

實現領域弱和演算的具體步驟見表2-4。其基本操作是，將線段的和演算應用于已知兩個領域的相應坐標軸方向的分量，得到新領域與已知領域的關系在相應坐標軸方向的分量。

所謂線段演算是指以空間中的線段作為對象的操作，其中的線段相當于時間區間。已知兩條線段，根據它們之間的關系，可以定義相應的和演算從而產生新的線段。這些被定義的線段和演算被用作操作規則。線段和演算規則見表2-5。圖2-14給出線段的和演算示例。其中細線段代表原來的線段，粗線段代表生成的新線段。

圖2-15為領域弱和演算的示例。對圖中的領域D2和D3實施弱和演算，得到新領域D4。圖2-15（a）中加上底線的領域關系為經推導得到的新內容。領域的弱和演算主要用于定性立體模型的簡化處理。例如，將圖2-15（a）中的領域D2、D3（被操作領域）刪除后，可以得到如圖2-15（b）所示的僅僅由三個領域構成的定性立體模型。考慮到概念設計階段，設計人員主要處理簡略的形狀，可以認為領域的弱和演算為設計人員提供了一個簡化形狀的手段。

2.4.1.2　領域的強和演算

對兩個領域A和B實施領域強和演算，將生成包容這兩個領域的最小空間。由于任意兩個領域的最小包容空間并不一定是一個唯一的領域，所以領域強和演算的實現不能利用線段的和演算。圖2-16（a）所示的兩個領域D0和D1的最小包容空間，不是唯一的領域，見圖2-16（b）。即使兩個領域的最小包容空間不是單一的領域，它也一定能夠被坐標軸的垂直平面切割成幾個領域，即它是領域的復合體。通過領域的強和演算可以生成構成最小包容空間的領域，并能推導出這些領域間的關系。

下面提出一種有效的領域強和演算方法，該方法引入了領域圖的新概念，基于領域圖的操作實現領域的強和演算。

定義2.10　所謂領域圖，是一個3×3×3規模的二值矩陣，它對應兩個領域間的定性空間關系，定性描述每個領域或者兩個領域的和、差演算結果占據空間的狀況。

領域圖中的元素可取值為0或1。取值為0的元素表示領域不占據相應位置的空間，取值為1的元素表示領域占據相應位置的空間。領域圖也可以表示成擁有27個小格的箱體，如圖2-17（a）所示，每個小格并不需要考慮具體的尺寸大小。每一個領域或者每兩個領域的和、差演算結果均可以最大切分成27個小領域，這些小領域分別按序布置在圖2-17（a）所示領域圖的小格中。如果某一小格被一個小領域所占據，則將對應領域圖的二值矩陣中的元素設置為1，未被小領域占據的小格所對應領域圖二值矩陣中的元素取值為0。另外，表示領域圖的箱體被放置在正交坐標系中，可以被坐標軸的垂直平面切割，得到如圖2-17（b）～（d）所示的總共9片薄板，每片薄板由9個小格組成。沿X軸方向有X1、X2和X3，沿Y軸方向有Y1、Y2和Y3，沿Z軸方向有Z1、Z2和Z3。這些薄板被稱作領域圖的面。每個領域圖的面對應3×3的二值矩陣。

領域圖之所以被定義為3×3×3規模的二值矩陣，其原因如下。由定義2.10可知，領域圖取決于兩個領域間的關系。換言之，通過比較兩個領域對應的領域圖必須能夠確定兩個領域間的關系。首先，由于領域圖表示三維領域（或者領域的和、差），所以需要x×y×z個小格。其中，x、y、z分別表示X軸、Y軸、Z軸方向領域圖的規模（小格的數目）。其次，由于各軸方向兩個領域間可能的關系數目相同，均為13，所以x、y、z也必須相等。這里依次考慮x、y、z為1、2、3的情況。1×1×1規模的領域圖只能表示領域關系（ReReRe）。2×2×2規模的領域圖只能表示領域關系（ReRmRmi）?？梢则炞C，表現兩個領域間所有可能關系領域圖的最小規模為3×3×3。

本章所提出的領域強和演算的實現方法是基于領域圖操作的，見表2-6。下面對該算法予以詳細說明。

1）根據領域關系生成領域圖

根據已知兩個領域A和B之間的關系SR（A B），以及領域關系與取值為1的元素在領域圖中所在面的對應關系（見表2-7），生成領域A和B的領域圖dm A、dm B。分別考慮三個坐標軸方向，在確定A的領域圖中取值為1的元素在領域圖中所在面的所有標號之后，進行組合便可以確定A的領域圖中取值為1的元素的具體位置，從而生成領域A的領域圖。例如，根據圖2-16（a）所示領域D0和D1的X軸方向的分量關系Rfi，D0的領域圖中取值為1的元素應該處于圖2-17（b）中領域圖的面X1、X2、X3。同樣，根據Y軸方向的分量關系Rsi和Z軸方向的分量關系Ro可以確定，取值為1的元素位于領域圖的面Y1、Y2、Y3、Z1、Z2。綜合上述所得結果，可以生成如圖2-18（a）所示的領域D0的領域圖dm D0。領域D1的領域圖dm D1也可按照相同的步驟得以生成。不過，這時應該首先將領域D0和D1的關系予以反置，得到領域D1和D0的關系，即SR（D1 D0）=（Rf Rs Roi）。根據這一關系，從表2-5可以得知，領域D1的領域圖中取值為1的元素應該位于領域圖的面X3、Y1、Z2、Z3。

2）領域圖的和

領域強和演算的第二步是求兩個領域圖的和。任意兩個領域A和B的最小包容空間也可以用領域圖表示。最小包容空間的領域圖dm（A+B）是兩個領域的領域圖dm A和dm B的和。兩個領域圖的和由式（2-13）求得。

其中，dAijk、dBijk、dCijk分別代表領域圖dm A、dm B、dm C的元素；i、j、k分別表示領域圖的X面、Y面、Z面的標號，取值可以分別為1、2、3。

圖2-18（c）表示領域圖dm D0（圖2-18（a））和dm D1（圖2-18（b））的和，即dm（D0+D1）。

3）領域圖的分解

領域強和演算的第三步對領域圖的和重新分解。由于任意兩個領域的最小包容空間雖然不一定是唯一確定的單純領域，但是可以被坐標軸的垂直平面切分為多個領域，所以對應這樣的最小包容空間的領域圖的和需要進行重新分割。用于切割最小包容空間的坐標軸的垂直平面被稱為切割面。一般，切割最小包容空間需要考慮三個坐標軸方向的切割面，而且每一坐標軸方向最多考慮兩片切割面。當需要考慮多個坐標軸方向的切割面時，最小包容空間的切割結果因切割順序的不同而不同。為了減小定性立體模型的復雜程度，確定能使構成最小包容空間的領域數目最小的切割面以及切割順序成為重要問題。例如，用Z軸的切割面切割圖2-18（c）中兩個領域的最小包容空間可得到兩個構成領域，用X軸或Y軸的切割面切割該最小包容空間會得到三個構成領域。

兩個領域最小包容空間的切割借助領域圖得以實現。首先，用某坐標軸方向的切割面將兩個領域圖的和切割成面（見圖2-17）。然后，比較相鄰領域圖的面，將相鄰而且相同的領域圖的面予以合成。所謂兩個領域圖的面相同，當且僅當所有的對應元素取值相等。之后，檢查領域圖的各面或者合成面是否表示單純的領域。表示單純領域的領域圖的面具有以下特征：同一行或同一列中取值為1的元素之間不存在取值為0的元素。當領域圖的面或合成面的所有的元素都為0時，可以判定為不存在領域；當領域圖或合成面表示領域時，生成新的3×3×3規模的領域圖，將原來的領域圖的面或合成面的元素所取值賦予新的領域圖的相應元素，而新的領域圖的其他元素的值設為0；當領域圖的面或合成面不表示領域時，用其他坐標軸方向的切割面進一步對領域圖的面或合成面進行切割。通過變換不同坐標軸方向的切割面的組合方式對領域圖的面或合成面進行試切割，得到最佳切割方案（生成最少領域的切割面和切割順序）。

圖2-18（d）（e）可表示將圖2-18（c）所示的領域圖的和用Z軸切割面切割得到的表示單純領域的領域圖。

4）通過比較領域圖推導領域關系

領域強和演算的第4步通過將由上述步驟得到的、表示新領域的領域圖與原領域A和B的領域圖進行比較，再次利用表2-7，推導出新領域與原領域的關系，同樣也推導出新領域之間的關系。圖2-19（a）表示對圖2-16（a）所示領域D0和D1實施領域強和演算后所得的結果。其中，領域D2和D3是新生成的領域，原領域D0和D1以及相關的領域關系已被刪除。

2.4.1.3　領域的差演算

兩個領域A與B的差是指領域A占據的而領域B不占據的最小空間。領域的差演算實現方法與領域的強和演算實現方法雖思路一致，但也有不同。首先，領域的差演算不是進行領域圖的和的計算，而是進行式（2-14）中的領域圖的差的計算。其次，領域的差演算并不一定生成領域。

1-1=0，1-0=1，0-1=0，0-0=0

其中，dAijk、dBijk、dCijk分別代表領域圖dm A、dm B、dm C的元素；i、j、k分別表示領域圖的X面、Y面、Z面的標號，取值可以為1、2、3。

圖2-20給出了對圖2-16（a）所示的兩個領域實施差演算得到的領域圖。其中，領域圖的切割首先利用Z軸的切割面，然后利用Y軸的切割面完成。而圖2-19（b）給出差演算的結果。其中，D2、D3、D4為新的領域。

2.4.1.4　領域的積演算

兩個領域共同占據的空間為兩個領域的積。如果兩個領域沒有共同占據的空間，則領域的積演算不對定性立體模型產生任何影響。

領域的積演算的實現與領域的弱和演算具有相同的算法。在領域的積演算步驟中，利用表2-8所示的線段積演算規則，將其應用于兩個領域對應坐標軸方向的分量關系，推導出新的領域及其與原來領域的關系。圖2-21給出線段積演算示例。其中細線段代表原來的線段，粗線段代表生成的新線段。圖2-19（c）給出對圖2-16（a）所示兩個領域實施積演算后得到的結果。其中，D2為新領域。為了明確起見，圖2-19（c）中并未刪除原來的領域。

2.4.1.5　領域演算后領域網絡的更新

上述領域演算推導出新的領域間關系以及新領域與被演算領域間的關系。另外，還需要自動推導出新領域與原來整個領域網絡中其他領域間的關系。下面提出借助于被演算領域求取新領域與原有領域關系的方法（見圖2-22），實現領域網絡的更新。原來的領域網絡包括三個領域A、B、D。假設對領域A和B實施領域演算得到新領域C，并且推導出領域關系SR（C A）和SR（C B）。領域網絡的更新需要推導領域關系SR（C D）。首先在由領域C、A、D組成的三角領域網絡中，應用領域關系傳遞律求得領域關系SR1（C D），在由領域C、B、D組成的三角領域網絡中，應用領域關系傳遞律求得領域關系SR2（C D），然后求取SR1（C D）和SR2（C D）對應領域關系的共同項，最終可以確定領域關系SR（C D）。

圖2-23以圖2-15（a）中的領域弱和演算為例，說明領域演算后的領域網絡更新方法。該示例主要以領域關系SR（D4 D1）的推導為內容。

2.4.2　領域變換操作

一般來說，立體的變換方式包括平移、旋轉、比例伸縮、坐標軸平面對稱、坐標系對稱等。本書中的研究考慮領域的平移、旋轉和比例伸縮三類變換方式。具體而言，所謂領域的變換指的是以單個領域為操作對象的平移、旋轉和比例伸縮。以往的形狀建模手法主要通過坐標變換來實現形狀的變換。在本節提出的定性立體建模方法中，立體或領域的變換是通過變化領域間的關系實現的。各種領域變換方法的實現步驟將在下文予以詳述。

2.4.2.1　領域的平移

沿某坐標軸的平行方向變動某領域（稱為對象領域）的位置，使得對象領域與另一指定領域（稱為參考領域）的關系發生變化。

領域平移的可能方向限定為3個坐標軸的正、負方向，共計6個方向。對領域進行平移操作時，需要指定對象領域、參考領域和平移方向。對象領域與參考領域間的關系按照如圖2-24所示的領域平移規則變化。當對象領域與參考領域間的關系為Rb且平移方向為X軸負方向（-X）、Y軸負方向（-Y）或Z軸負方向（-Z）時，移動后兩領域間的關系不變；當對象領域與參考領域間的關系為Ra且平移方向為X軸正方向（+X）、Y軸正方向（+Y）或Z軸正方向（+Z）時，移動后兩領域間的關系也不變；當對象領域與參考領域間的關系為Ro且平移方向為X軸負方向（-X）、Y軸負方向（-Y）或Z軸負方向（-Z）時，移動后兩領域間的關系根據相應坐標軸方向兩領域的長度，可取Rfi、Re或Rs；當對象領域與參考領域間的關系為Roi且平移方向為X軸正方向（+X）、Y軸正方向（+Y）或Z軸正方向（+Z）時，移動后兩領域間的關系根據相應坐標軸方向兩領域的長度，可取Rf、Re或Rsi。

當對象領域與參考領域間的關系確定后，利用領域關系傳遞律，可以求得對象領域與其他領域間的關系。圖2-25表示將圖2-15（b）中的領域D1（對象領域）以領域D0為參考領域沿Y軸負方向平移后的結果。領域D0與D1在Y軸方向的關系由Rfi變為Rdi。

2.4.2.2　領域的旋轉

由于領域關系的各分量間是相互獨立的，不能直接確定單一領域旋轉后與其他領域的關系，只能仍然借助基本領域網絡操作來實現領域的旋轉。

2.4.2.3　領域的弱比例伸縮

領域的弱比例伸縮指沿指定的移動方向移動對象領域的指定面，使之伸縮直至對象領域與領域網絡中其他領域在移動方向的分量發生變化為止。表2-9給出了領域弱比例伸縮的實現步驟。

領域弱比例伸縮方式指定對象領域的移動面（在正交坐標系中，frt代表領域的X軸方向的前面、Y軸方向的右面或Z軸方向的頂面，而blb代表領域的X軸方向的后面、Y軸方向的左面或Z軸方向的底面）以及對象領域的伸縮類別［l（lengthen）表示伸長，s（shorten）表示縮短］。對象領域移動面的移動方向（也是對象領域伸縮方向或變形方向）由比例伸縮方式可以確定。例如，導致對象領域伸長的X軸方向前面的移動方向為X軸的正方向。本節的研究中規定一次領域弱比例伸縮只限于一個方向上的領域伸縮。

領域的弱比例伸縮的第一步是根據變形方向的領域關系分量確定與對象領域關系最早發生變化的領域，這樣的領域被稱作目標領域。目標領域可能同時存在若干個，也可能不存在。當目標領域不存在時，領域的弱比例伸縮不會影響領域網絡，盡管對象領域發生了變形。第二步，基于表2-10的線段比例伸縮規則以及原來的對象領域與目標領域間的關系，推導出新的領域關系。對象領域與目標領域以外的領域間的關系不發生變化。

這里考慮將圖2-15（b）中的領域D1（對象領域）通過移動其X軸方向的后面予以縮小的操作。領域D3被確定為目標領域。該領域弱比例伸縮后的結果如圖2-26（a）所示。

2.4.2.4　領域的強比例伸縮

領域的強比例伸縮是指移動對象領域的指定面，直至對象領域與指定的目標領域的關系發生變化為止。由于領域的強比例伸縮需要事先指定目標領域，因此可以直接利用表2-10得到對象領域與目標領域間的新的關系。對象領域與除目標領域以外的其他領域間的關系可能會發生變化，需要基于對象領域與目標領域的新的關系，經過領域關系定義操作，決定對象領域與其他領域的空間關系。圖2-26（b）給出了領域的強比例伸縮的一個例子。其中，對象領域D1的X軸方向的后面為移動面，領域D2為目標領域，對領域D1予以縮小。

2.4.3　復合領域操作

領域操作是有效的定性立體建模的基本方法。由于領域操作只考慮以領域為操作對象，而且實際上一般的立體不是簡單的領域，所以以復合領域為操作對象的研究也非常必要。

所謂復合領域是指由若干領域構成的立體，復合領域及其關系如圖2-27所示。復合領域操作將以領域操作為基礎，是若干領域演算算法的組合。本節重點研究復合領域演算。復合領域演算是以復合領域為對象的定性空間集合運算，與領域演算一樣，包括復合領域的弱和演算、強和演算、差演算和積演算。

2.4.3.1　復合領域的弱和演算

兩個復合領域的弱和演算結果為包容兩個復合領域的所有領域的一個最小包容領域。復合領域的弱和演算可以有多種方法。這里只討論思路最簡單的一種方法，其算法見表2-11。圖2-28（a）給出對圖2-27（c）所示復合領域實施弱和演算的結果。D4為最小包容領域。為了便于理解，原來的領域及關系均未做刪除處理。

2.4.3.2　復合領域的強和演算

兩個復合領域的強和演算結果為包容兩個復合領域的最小空間。這個最小包容空間通常由若干個領域構成。因此，復合領域的強和演算目的在于求得這些構成領域及關系。復合領域強和演算算法見表2-12。圖2-28（b）給出了復合領域強和演算的結果示例。

2.4.3.3　復合領域的積演算

兩個復合領域的積演算結果為兩個復合領域共同占據的空間。與領域的積演算不同，兩個復合領域的積可能不存在，也可能是唯一的領域，更可能的情況是結果仍為一個復合領域。復合領域積演算算法見表2-13。圖2-28（c）給出了復合領域積演算的結果示例。

2.4.3.4　復合領域的差演算

復合領域A和B的差演算結果為被復合領域A占據而不被復合領域B占據的空間。復合領域的差演算算法見表2-14。圖2-28（d）給出了復合領域差演算的一個結果示例。