0评论

Unity网格切割算法浅析

文章来自CSDN博客 2018-10-11 28浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏开发行业精英群711501594

这篇主要给大家简单介绍下网格切割算法。

算法主要的方法为: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