unity 中关于含有凹型的三角面剖分论文TriangulationByEarClipping的阅读小记

最近在做模型切割方面的工作，遇到三角面的剖分仿麦呢的不懂，在查资料的时候看到一篇对三角面片剖分方面的文章感觉写的很好，https://www.geometrictools.com/论文网址在此。

一下只代表个人的分析，

文章主要介绍了一种耳廓三角测量法，对于多边形或者复杂的有孔的多边形的三角面片剖分算法，也算是解决了对含有凹面的模型剖分算法。首先介绍n个顶点可以构成n-2个三角形，

如果一个多边形是简单的，当你穿过边缘是，内部有界区域总在一边。在此假设多边形是逆时针排列的，所以当你穿过边缘时，内部就在你的左边，将简单的多边形可以分解为多个三角形，

耳廓剪辑算法主要时把定点进行分类，分为突出的和凹进的两种，然后一步一步把突出的点给剪辑掉，

最后变成这样的

剖分成许多三角形。

然后就是带有孔的多边形，首先考虑一个带有一个孔的多白女性，如下图

它由一个外部多边形和一个内部多边形组成。外顶点和内顶点的排序必须相反，如果外定点逆时针排序，则内顶点必须顺时针排序。蓝色的顶点时相互可见的，我们可以通过引入蓝色顶点的两条重合边来将其专函为简单多白女性的拓扑。数字11显示两条新边，一条以蓝色绘制，一一奥以红色绘制。边缘重合；在定点数据结构不同的意义上，互相可见的顶点必须被复制。每个这样的数据结构将存储顶点时凸的还是反射的。即使重复的顶点与原始位置具有相同的位置，也可以时凸起的而两一个是反射的，例如，底部的蓝色点由两个与之管来奶的顶点V11和V18，原始顶点时外部反射的多变，与红边关联的V11是反射顶点，但与蓝色边管来奶的V18是凸顶点。原始的外部多边形具有顶点{0，1，2，3，4，5，6，7，8，9，10，11，12，13，14}

原始的内部多边形具有顶点{15，16，17}顶点V16与V19以及顶点V11与V18发生复制，引入两个新边后的多边形是{0，1，2，3，4，5，6，7，8，9，10，11，16，17，15，19，18，12，13，14}新的多边形可以通过耳廓裁剪进行三角测量。

具体算法如下：

1，在内部多白女性种搜索最大X之的顶点M。

2，将光线M+T（1，0）与M外部多白女性的所有有向边（Vi,Vi+1)与包含边线的左侧相交，让I成为这条线上的最接近M的可见点。

3，如果I是外部所败女性的顶点，那么M和I是相互可见的，并且算法终止。

4，否则I是边（Vi,Vi+1)的内点。选择P作为该边的最大值X的终点。

5.搜索外部多百姓的反射顶点如果所有这些顶点严格在三角形M,I,P之外，则M和P是相互可见的，并且算法终止。

6.否则至少有一个反射顶点位于M,I,P线段之家角度最小的反射R，然后M和R是相互可见的，算法中值。在这个步骤中可能由很多个反射顶点使角度最小化