Unity网格切割算法浅析
发表于2018-10-11
这篇主要给大家简单介绍下网格切割算法。
算法主要的方法为：publicstaticList<List<Vector3>>GetEndCuttingPolygonVerticles(List<Vector3>originPoints,Vector3startPos,Vector3endPos)，
list数组存的是网格的顶点，第二个参数和第三个参数表示切割线段的起始节点和线段的末节点，首先我们会判断线段两头的点是否在多边形内。
代码如下：
private static bool PointInPolygon(Vector3 pointToCheck, List<Vector3> polygon)
｛
var flag = false;
if (polygon.Count >= 3)
｛
var lastPoint = new Vector3(polygon[polygon.Count - 1].x, polygon[polygon.Count - 1].y);
for (var i = 0; i < polygon.Count; i++)
｛
Vector3 minPoint;
Vector3 maxPoint;
var curPoint = new Vector3(polygon[i].x, polygon[i].y);
if (curPoint.x > lastPoint.x)
｛
minPoint = lastPoint;
maxPoint = curPoint;
｝
else
｛
minPoint = curPoint;
maxPoint = lastPoint;
｝
var p1 = pointToCheck - minPoint;
var p2 = maxPoint - minPoint;
bool b = (curPoint.x < pointToCheck.x) == (pointToCheck.x <= lastPoint.x);
if (b && (p1.x * p2.y - p1.y * p2.x > 0))
｛
flag = !flag;
｝
lastPoint = curPoint;
｝
｝
return flag;
｝
如果我们切割线段的2个顶点都不在该多边形网格图形内的话，表示可以切割，反之则表示无法切割。如果可以切割的话，先取出线段与多边形的交点数组。方法如下：
public static List<VertexPoint> GetCuttingPoints(List<Vector3> originPoints, Vector3 startPos, Vector3 endPos)
｛
List<VertexPoint> tempVertexPoints = new List<VertexPoint>();//list中存储切割线和多边形网格的所有交点。
var count = originPoints.Count;
for (int i = 0; i < count; i++)
｛
var list = GetLinesIntersection(originPoints[i], originPoints[((i + 1) % count)], startPos, endPos);//通过当前方法，得到切割点
if (list.Count == 1)
｛
if (list.Count == 1)//如果2条线段相交的交点的个数，是否为1
｛
var pre = 0;
var next = 0;
if (list[0].VeIndex == 0)
｛
pre = i;
next = i;
｝
else if (list[0].VeIndex == 1)
｛
pre = (i + 1) % count;
next = (i + 1) % count;
｝
else
｛
pre = i;
next = (i + 1) % count;
｝
tempVertexPoints.Add(new VertexPoint(list[0].Pos, pre, next));
｝
else if (list.Count == 2)//2条线段相交如果存在2个交点的话。那么就只有一种情况了，就是他们不但平行，而且网格中相邻的2个点组成的线段在切割线段中间（大家考虑是不是这样）
｛
tempVertexPoints.Add(new VertexPoint(list[0].Pos, i, i));
tempVertexPoints.Add(new VertexPoint(list[1].Pos, (i + 1) % count, (i + 1) % count));
｝
｝
｝
tempVertexPoints = GetDistinctPoints(tempVertexPoints);
return tempVertexPoints;
｝
求完了切割线段和网格的所有交点后。接下来就是通过交点来分割整个网格了，那么接下来写通过交点来分割网格，同时他也是对外的重要方法：
public static List<List<Vector3>> GetEndCuttingPolygonVerticles(List<Vector3> originPoints, Vector3 startPos, Vector3 endPos)
｛
List<List<Vector3>> endValues = new List<List<Vector3>>();
bool[] visited = new bool[originPoints.Count];
originPoints = ReversePoints(originPoints);//将所有的点变成顺时针。
List<VertexPoint> tempPoints = GetCuttingPoints(originPoints, startPos, endPos);//得到所有的交点。
tempPoints = tempPoints.OrderBy(t => t.KeyVector3.x).ToList();//讲所有的交点由x排序
if (tempPoints.Count == 1)
return null;
for (int i = 0; i < tempPoints.Count - 1; i++)
｛
int cur = i, next = i + 1;
List<Vector3> tempList = new List<Vector3>();
tempList = GetPointByTwoIntersec(cur, next, originPoints, tempPoints);//得到2个交点中间包含所有的节点。
if (tempList.Count >= 3)
｛
if (Triangulate.Area(tempList) < 0)
｛
endValues.Add(tempList);
for (int j = 0; j < tempList.Count; j++)
｛
int index = GetVerticleIndex(tempList[j], originPoints);
if (index != 100)
visited[index] = true;
｝
｝
｝
｝
var lastTri = new List<Vector3>();
for (int i = 0; i < originPoints.Count; i++)
｛
if (!visited[i])
｛
lastTri.Add(originPoints[i]);
｝
for (int j = 0; j < tempPoints.Count; j++)
｛
var cur = tempPoints[j].PreIndex;
if (cur == i)
｛
lastTri.Add(tempPoints[j].KeyVector3);
｝
｝
｝
endValues.Add(lastTri);
return endValues;
｝
这里贴出所有工具类，个人觉得对于网格的操作是非常重要的，同时也较基本的游戏-三消，塔防，卡牌类游戏制作较为麻烦，同时任何一个游戏引擎都会用到，这些都是关于渲染的问题，可能比一些游戏逻辑理解起来费劲，但是个人还是建议大家可以好好学学，这样才可能走的更远，接触到低层渲染问题。来自：https://blog.csdn.net/u012565990/article/details/51817439