paper - 2004 - self intersection removal in triangular mesh offseting
Jung W, Shin H, Choi B K. Self-intersection removal in triangular mesh offsetting[J]. Computer-Aided Design and Applications, 2004, 1(1-4): 477-484.
主要目的是为了找到有效区域（有效区域指的是，定义外边界的三角形集合）。从一个种子点三角形出发，找到自相交的三角形，然后对自相交区域进行处理，继续沿着valid region进行遍历。这样对于非valid region中的三角形不会进行额外的处理，减少了很多不必要的计算。
1. Introduction
2. Basic observations
本篇文章的目的是，从法向量偏移后的三角形中找到外边界的三角形集合。输入的三角网格可以分为三类：valid triangles（完整的位于valid区域中的三角形），invalid triangles（完全不位于valid区域的三角形，最后被直接删除的），partially valid triangle（valid region和invalid region之间的三角形，其中的部分会被保留，需要进行三角形划分，subtriangle会进一步分为valid和invalid triangles）。具体如下图所示：
3. Mesh regularization algorithm
假设输入的网格在raw offset之前是闭合的曲面，是2-manifold的网格。算法的整体流程如下所示：
第四步中，还包括将partially valid triangle分割的过程。
3.1 removing degenerate triangles
这里退化三角形指的是三角形面积为0的情况。
这里对于退化三角形去除的方法是，如果一条边的长度小于一定的阈值，那么直接做edge collapse。如果一个三角形的角度小于一定阈值，那么进行边swapping diagonal edges 操作。如上图所示。
3.2 computing self-intersection
为了避免invalid region中的三角形相交检测，我们使用了bucket的结构。每个bucket三角形数量要少于C（bucket的容量）。
如果bucket中的三角形数量大于C，那么沿着AABB的最长边，将其分成两个bucket。被切割面相交的三角形会存储到两个bucket中。然后再每个bucket中执行所有三角形对的相交测试。三角形对的相交测试基于Moller T. A fast triangle-triangle intersection test[J]. Journal of Graphics Tools, 1997, 2(2): 25-30.，[[paper-impl-a-fast-triangle-triangle-intersection-test]]。每个相交对存储了指向相交三角形的指针，以及每个三角形存储了相交对列表，并计算得到了相交线段。
3.3 Finding a seed triangle
此处我们假设和AABB接触的三角形至少有一个是valid的。可以选择一个作为seed triangle。
3.4 Valid region growing
详细过程如下：
- 每个三角形有三个状态：unvisited, valid, partially valid。一开始的时候，所有三角形都是unvisited；
- 找到seed triangle，标记为valid，插入到S 中（S 是区域增长对应的三角形集合）；
- 如果S为空，goto 5.否则从S 中删除一个三角形T。
- 找到T三角形领域的所有unvisited Ta。如果Ta没有相交对，那么标记为valid，并insert到S 中。否则，Ta标记为partially valid triangle，并将Ta insert到P 中（面临的partially valid triangle集合）。同时记录的还有三角形T和Ta（此时为Tp）共享的边ep。然后goto 3.
- 如果P 为空，那么goto 7.否则从P 中移除一个Tp和关联的ep。
- 对Tp进行三角剖分（详细见section 3.5）。跨过Tp的有效区域进行传播（详细见 3.6）。如果找到另一个seed triangle，插入到seed queue中，然后 goto 2. 否则goto 4.
- valid region grow完成。
3.5 sub triangulation
partially valid triangle Tp上会有相交线段。这个步骤完成两个任务：1）将Tp依据intersection segments进行三角剖分，fig8(a)，2）、在sub-triangular网格的valid region进行传播，fig8(b)。详细过程如下：
- 利用Tp关联的所有相交线段，对ei进行切分；
- 将每个相交线段进行切分；
- 利用2D constrained delaunay triangulation对Tp进行剖分；
如下图b中所述，在对细分后的三角形region growing中，遇到intersection segment的时候，该intersection segment关联的另一个三角形为下一节中描述的Tc。
3.6 crossing the river
region growing process的过程，怎么跨过self intersection部分，参见下图：
通过结合法向量的朝向可以选择t4为valid one，可以作为区域增长的seed triangle。进一步会找到t5，Tv。
3.7 Trimming & stitching
删除invalid三角形，并对自相交部分进行拓扑连接。
4 results
The experiments were done on a PC with Pentium 1.8GHz CPU and 1GB memory.
根据文中的测试结果，整个过程跑下来，性能并不是特别理想。
主要的时间开销位于自相交计算中。
标签：triangle,self,triangular,相交,mesh,region,三角形,intersection,valid From： https://www.cnblogs.com/grass-and-moon/p/16647591.html