受限条件的恢复

发布网友发布时间：2022-05-16 07:28

共1个回答

热心网友时间：2023-10-15 06:10

点集的带权Delaunay四面体化算法得到的是点集的凸包或四面体化，没有考虑PLC中的边界边及边界面的*。为了得到边界一致的域的四面体化，必须要恢复PLC中的边界边和边界面。很多文献均已经证明了在不加点的情况下，存在不可四面体化的物体，如Schordart四面体，因此，本文采用向域中加点的方法来恢复受限条件。基本思路是先恢复受限边，再恢复受限面。

1.恢复受限边

恢复受限边的思想是：将受限边集合中的受限线段与四面体集合中的四面体的边进行比较，如果某条线段在四面体集合中没有出现，则加点细分该线段。当加点细分到一定程度时，线段的必然存在一个正交球不与其他带权点相干涉，受限边出现在剖分结果中，从而达到恢复受限边的目的。恢复边界边的算法有时又被称为带权的边界细分算法。

算法：恢复受限边的算法

地下水三维可视化系统开发与应用

2.恢复受限面

恢复受限面是三维受限网格剖分中最难解决的。因为即使所有的受限边都存在或者已经被恢复了，也不能保证一个面一定存在。一个受限面可能是一个非常复杂的PSLG，内部可能存在空洞。

根据Delaunay三角化的性质，如果一个面在Delaunay四面体化中是由子三角形面组成，那么这些子三角形面必定形成该面的Delaunay三角网格。其原因也是很明显的，如果一个四面体满足Delaunay准则，那么它的四个三角形面的外接圆必定为空，因为这些外接圆包含的空间也是四面体的最小外接球所包含的空间。该性质对于加权的Delaunay三角化同样有效。利用这个性质，可以为每个受限面形成该面的二维带权的受限Delaunay三角化，该三角化与当前网格的四面体化是无关的，而是我们认为这些三角形面应该存在于四面体网格化中。通过比较三角化和四面体化中的三角形面可以判断出哪些子三角形面丢失了，然后强制插入到四面体化中来恢复整个受限面。恢复受限面的思想是当PLC中的某个面上的三角剖分中的三角形在四面体网格中没有出现时，将该三角形的正交中心分别加入面的三角剖分和PLC的四面体剖分中去。基于此，恢复受限面的算法有时又被称为带权的边界面细分算法。其实恢复受限边的方法采用的是同样的方法，只是生成边的“一维Delaunay网格化”的过程被忽略了。

值得注意的一个问题是，如果在受限面上存在四点共圆以及四个带权点共正交圆的情况，那么该面的受限Delaunay三角化就不是唯一的，这就给判断子三角形面是否存在带来极大的麻烦。例如，可能存在着这样的情况，即一个面的三角化的结果和该面在四面体网格中形成的子三角形面的集合并不相同，但都是Delaunay三角化，如图3-8所示。带权的Delaunay三角化存在着同样的问题，为简单起见，图3-8给出Delaunay三角化的情况。这时，在寻找受限面时，会发现面丢失。这种情况普遍存在，特别是在浮点运算时会将许多近似为共圆的四个点也当成共圆的情况。如果不能很好地处理这个问题，将造成恢复受限面的算法不能收敛。

图3-8 四点共圆情况处理

对于这种情况，解决办法是当发现四点共圆（包含四个带权点共正交圆的情况）而且两个三角形面不匹配时，在面的Delaunay三角化中执行换边操作，使它和四面体化中的子三角形面相匹配，如图3-8所示。这种做法比调整四面体化中的子三角形面要方便得多，而且在四面体中的换面操作还存在着不能交换的情况。为了能够在面的三角化中执行换边操作，在生成面的受限Delaunay三角剖分后，同时维护三角形单元表和邻接三角形单元表，以便快速找到要换边两侧的三角形单元，并在这两个三角形中执行换边操作就可以了。使用了邻接三角形单元表的好处还在于不用专门去判断是否存在四点共圆的情况，如图3-8所示，当发现没有和Δabc匹配的三角形面时，取得边ac的邻接三角形的顶点d形成一个临时的三角形Δacd再返回到四面体化中去比较，如果发现Δacd存在，则在面三角化中执行换边操作，将边ac换掉，这大大简化了编程的工作。

算法：恢复受限面的算法

地下水三维可视化系统开发与应用

if PQ的bIsSharpSegment为TRUE

将点H的权值赋为PQ中的dW eight值endif

将点H加入四面体集合中；

将点H加入其所在的平面的三角剖分中；

从ConformingSegmentSet中删除线段PQ，将线段PH和HQ加入ConformingSegmentSet中，将PH和HQ的bIsSharpSegment值赋为PQ的bIsSharpSegment值；

调用算法重新进行恢复受限边

地下水三维可视化系统开发与应用