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）。可以验证，表现两个领域间所有可能关系领域图的最小规模为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）给出了复合领域差演算的一个结果示例。