多边形分割
钢板建模的思路是，通过已经获得的钢板轮廓点集，生成钢板的两个底面，再将两个底面通过侧面闭合成三维模型：
由于侧面三角面片的生成我们已经在骨骼建模中应用，代码完全可以复用。可以说现在钢板建模的关键点，就在于如何生成两个底面模型（其实只需要生成一个底面，因为顶部可以由底部平移得到）。难点一，底部面片轮廓点组成的多边形可能是凹多边形，不利于面片模型的生成。难点二，如何才能让底部面片模型完全贴合骨骼模型的外表面。
本章将重点讨论难点一，凹多边形的处理，或者说如何将凹多边形切割为多个凸多边形。假设我们可以为凸多边形建立面片模型（事实上确实可以），那么将凹多边形切割为多个凸多边形，就可以为每个凸多边形分别计算面片模型，最后再将这些面片合并，便得到了凹多边形的面片模型。
多边形的基本信息主要由类Polygon负责。Polygon对象记录了钢板面片的所有轮廓点，以及哪些轮廓点是凹点。凹点的判断非常重要，它是多边形凸分解算法所倚仗的关键信息。在Polygon中，凹点判断函数为MarkConvex，该函数会将每个轮廓点标记为凹点(1)或是凸点(0)。凹点的判断思路有点类似于凸包检测的思路，首先需要将所有的轮廓点按顺时针方向排序，这样对于一点B，假设前一个点为A，后一个点为C，如果C位于向量AB的左侧，那么B就是凹点。方向判断可以通过矢量叉积运算得到，如果P x Q > 0，则向量P位于向量Q的顺时针方向。
public void MarkConvex() // 调用前确保轮廓点按顺时针方向排序
{
int nCount = 0;
nCount = listPolyNode.Count;
if (nCount < 4) return; // 三角形不需要处理，直接返回
for (int i = 0; i < nCount; i++)
{
Vector2 prev, mid, next;
prev = listPolyNode[(nCount + i - 1) % nCount].point;
mid = listPolyNode[(nCount + i + 0) % nCount].point;
next = listPolyNode[(nCount + i + 1) % nCount].point;
float nMul = Multiply(mid, next, prev); // 向量叉乘
bool bIsConvex = nMul < 0 ? true : false;
if (!bIsConvex)
listPolyNode[(i + 0) % nCount].nMark = 1; // 标记为凹点
else
listPolyNode[(i + 0) % nCount].nMark = 0;
}
}
public float Multiply(Vector2 op, Vector2 sp, Vector2 ep)
{
return ((sp.x - op.x) * (ep.y - op.y) - (ep.x - op.x) * (sp.y - op.y));
}
Rogers类专门负责多边形的凸分解。凸分解函数RogersDecompose输入一个多边形Polygon对象作为参数，输出一个Polygon链表，其中的Polygon对象均为凸多边形。
//////////////////////////////////////////////////////////////////////////
//----简单多边形凸分解算法，大致分为以下几个步骤：
//1. 判断多边形顺序
//2. 查找第一个凹点
//3. 选取分割点（最为关键的一步）
//4. 根据交点分割多边形
//5. 递归分解，直到所有多边形都为凸多边形
//////////////////////////////////////////////////////////////////////////
// 分区域分解算法：不考虑角度和顶点数
public void RogersDecompose(ref Polygon poly)
{
List<PolyNode> arrPoly = poly.listPolyNode; // 获取顶点列表
int nCount = arrPoly.Count;
if (nCount < 4)
{ // 三角形不需要处理，直接返回
listPolygon.Add(poly);
return;
}
// 0. 判断多边形顺序
poly.ProcAntic();
if (poly.isAntic)
{ // 保证多边形轮廓点按顺时针方向排序
poly.ConversPoly();
poly.ProcAntic();
}
// 1. 标记凹点
poly.ClearMark();
// 2. 查找第一个凹点
int nCur = 0;
nCur = poly.GetNotMarkConvex(); // 获取第一个凹点，不对原轮廓点做标记
if (nCur < 0)
{
listPolygon.Add(poly);
return; // 表示没有凹点，不需要继续分割
}
// 3. 选取分割点（最为关键的一步）
Vector2 splitPoint = Vector2.zero; // 交点
int nIntersectionIndex = -1;
if (GetSplitPointMeans(ref poly, nCur, ref nIntersectionIndex, ref splitPoint))
{ // 分区域法寻找分割点
Vector2 p1 = arrPoly[nIntersectionIndex].point;
Polygon lPoly = new Polygon();
Polygon rPoly = new Polygon();
// 4. 根据交点分割多边形
poly.Split(nCur, nIntersectionIndex, lPoly, rPoly);
poly.Clear();
lPoly.AddPoint(splitPoint);
if (splitPoint != p1)
{
rPoly.AddPoint(splitPoint);
}
// 5. 递归调用
RogersDecompose(ref lPoly);
RogersDecompose(ref rPoly);
}
else
{
listPolygon.Add(poly);
return; // 求不出交点，默认已经是凸多边形
}
}
如何选取分割点是凸分解算法的一个关键点。上述代码中，函数GetSplitPointMeans输入一个多边形和凹点，返回一个分割点序号和分割点对象。分割点的选取有多种方法，我们认为，好的分割点可以使分割后的多边形消除更多的凹点，并且分割后的两个多边形拥有相似的形态。
经典的分割点选取算法是Rogers算法。
设简单多边形顶点按逆时针方向排序，且以单向链表表示连接，如图(a)。算法可以从顶点a开始延链表方向寻找到第一个凹点c，从凹点c沿有向边bc(称为凹边)作射线，与多边形其余边求交，取离点c最近的交点，如图(b)所示的点j，沿线段cj将多边形一分为二，得到两个多边形abjhia和cdefgj'c，然后对这两个多边形再分别作同样的处理，这是一个递归的过程，直到所有新产生的多边形均为凸多边形。如图(c)，原凹多边形被分解为4个凸多边形abjka、hik'h、cdlj'c和efgl'e。
Rogers算法的时间复杂度为O(mn)，其中m为凹点个数，n为多边形顶点个数。Rogers算法简单清晰易实现，但其存在如下的缺陷：
(1) 计算量大。分割点需要凹边与其它所有线段求交得到。
(2) 剖分产生的凸多边形数量较多。如果分割点不是已有的凹点，那么凸多边形的数量为(m+1)个，这是绝大多数情况。而这往往是现有其它算法的最坏结果。
(3) 有可能产生非常细小或非常微小的凸多边形。这种情况出现在凹边与相邻边夹角较小时。
因此，通常我们不直接使用Rogers算法，而是使用基于顶部可见性的局部剖分算法，夏旸师兄在这里也是使用了该算法的变形。该算法类似Rogers算法，需要对多边形的顶点进行排序，并找到第一个凹点作为分割线的一个端点。不同的是，分割点的选取不再是凹边延长线的交点。
假设有如下多边形，其第一个凹点为vi，设M为与有向线段vi-1，vi方向一致的射线，设N为与有向线段vi+1，vi方向一致的射线。M和N所在直线将平面分为4个区域：A、B、C、D。
分别计算A、B、C区域中vi的可见点，即与vi连线间没有相交点的顶点，用SA、SB、SC表示这3个点集：SA=(s2,s3,s4,s5); SB=(s0,s1); SC=(s6,s7,s8,s9)。从可见点的几何特性可得到结论：如果SA为空，则SB和SC必不为空。证明不再给出。
基于顶点可见性的凹多边形局部剖分算法步骤如下：
1. 搜索凹点，如果多边形没有凹点，算法结束。
2. 搜索当前凹点的可见点集SA、SB、SC。
3. 如果SA不为空，则：
(1) 将SA中的顶点划分为凸点集SetA和凹点集SetB。
(2) 如果SetB不为空，选择SetB中与射线MN角平分线投影最长的凹点作为分割点。
(3) 如果SetB为空，选择SetA中与射线MN角平分线投影最长的凸点作为分割点。
4. 如果SA为空，由结论可知SB、SC必不为空，连接SB的最后一个顶点和SC的第一个顶点，做射线MN的角平分线与连线相交，即得到分割点。
5. 从凹点至分割点引分割线，将多边形切割成两个多边形。
6. 对新产生的两个多边形按上述步骤递归地进行凹多边形凸分解，直到所有多边形均为凸多边形为止。
在步骤3中，我们优先选取区域A中的凹点作为分割点，旨在一次消除两个凹点，减少多边形的数量。另外，为了保证分割后的两个多边形拥有相似的形态，我们取在角平分线上有最长投影的点作为分割点。设射线M的单位向量为m，射线N的单位向量为n，那么MN的角平分线有mid = m + n。选取分割点时，作向量(vi,si)，其中si为当前顶点，计算(vi,si)在角平分线mid上的投影长度，取长度最长的顶点作为分割点。
这部分的代码位于Rogers.cs中：
//分区域分割点选取方法
//poly： 简单多边形
//nCur： 凹点索引
//nIntersectionIndex：交点索引（如果有效）
//splitPoint：交点坐标
public bool GetSplitPointByRgnBCInter(ref Polygon poly, int nCur, ref int nIntersectionIndex, ref Vector2 splitPoint)
{
List<PolyNode> arrPoly = poly.listPolyNode; // 获取顶点列表
int nCount = arrPoly.Count;
if (nCount < 4) return false;
nIntersectionIndex = -1; // 如果存在交点，则为交点的索引值
// 1. 找Pi前后两个点Pi-1和Pi+1
int nPrev, nNext; // 前一个点、后一个点的索引
nPrev = (nCount + nCur - 1) % nCount;
nNext = (nCount + nCur + 1) % nCount;
Vector2 prevPoint, curPoint, nextPoint; // 前一个点坐标、交点坐标
prevPoint = arrPoly[nPrev].point;
curPoint = arrPoly[nCur].point;
nextPoint = arrPoly[nNext].point;
// 2. 建立存储四个分区的结构A、B、C、D
List<int> A = new List<int>();
List<int> B = new List<int>();
List<int> C = new List<int>();
List<int> D = new List<int>();
// 3. 循环判断每个点所属区域
int nMax = 0;
nMax = nNext <= nPrev ? nPrev : nPrev + nCount;
for (int i = nNext; i <= nMax; i++)
{
Vector2 dPoint = arrPoly[i % nCount].point;
float f1, f2;
f1 = FuncVal(prevPoint, curPoint, dPoint); // 计算dPoint相对于直线M的位置
f2 = FuncVal(nextPoint, curPoint, dPoint); // 计算dPoint相对于直线N的位置
if (f1 > 0 && f2 < 0)
{
A.Add(i % nCount);
}
else if (f1 <= 0 && f2 <= 0)
{
B.Add(i % nCount);
}
else if (f1 > 0 && f2 > 0)
{
C.Add(i % nCount);
}
else if (f1 < 0 && f2 > 0)
{
D.Add(i % nCount);
}
}
// 求ABCD可见点串A1B1C1D1
List<int> A1 = new List<int>();
List<int> B1 = new List<int>();
List<int> C1 = new List<int>();
List<int> D1 = new List<int>();
VisibleSets(ref poly, nCur, A, A1);
CopyArray(B, B1);
CopyArray(D, D1);
VisibleSets(ref poly, nCur, C, C1);
// 4. 如果A1不为空，则处理A
if (A1.Count > 0)
{
List<int> SetA = new List<int>();
List<int> SetB = new List<int>();
SetsSplit(ref poly, A1, SetA, SetB); // SetA：凸点集合，SetB凹点集合
if (SetB.Count > 0) // 凹点集合不为空，则优先处理凹点集合
{
nIntersectionIndex = GetBestPoint(ref poly, nCur, SetB);
}
else
{
nIntersectionIndex = GetBestPoint(ref poly, nCur, SetA);
}
if (nIntersectionIndex < 0 && nIntersectionIndex >= nCount) return false;
splitPoint = poly.listPolyNode[nIntersectionIndex].point;
return true;
}
else
{
int left = B1[B1.Count - 1]; // 最后一个
int right = C1[0]; // 第一个
Vector2 lPoint = poly.listPolyNode[left].point;
Vector2 rPoint = poly.listPolyNode[right].point;
// 线段LR
Vector2 d1 = rPoint - lPoint;
// 射线pL，端点是Pi
Vector2 d0, d00, d01;
d00 = (curPoint - prevPoint);
d01 = (curPoint - nextPoint);
Normalize(d00);
Normalize(d01);
d0 = (d00 + d01); // 角平分线
d0.x /= 2; d0.y /= 2;
// 求射线与线段的交点
if (Calculator.Intersection(curPoint, d0, lPoint, d1, ref splitPoint) != 1)
{
return false;
}
nIntersectionIndex = left; // 交点索引
return true;
}
}
通过计算，我们获得了一组凸多边形数组，这些凸多边形由原来的多边形分割所得。接下来，可以对这些凸多边形进行网格面片的生成了。