Unity 凹多边形三角剖分

游戏中需要实现一个小功能，显示一个玩家的能力图，这个图是一个有6个顶点任意摆放组合的多边形。而绘制多边形主要用到的知识就是Mesh构建，mesh的构建主要需要顶点列表，三角形列表，法线列表、uv列表等等等等，在这里我们只考虑顶点列表和三角形列表。那么我们需要做的就是给定一组顶点之后，如何用三角形进行划分，以便绘制。

以下讨论的多边形：1.三角形顶点列表为顺时针顺序。2.多边形不能包含空洞。

参照文章：https://blog.csdn.net/huangzengman/article/details/77114082，表示感谢

1.凸多边形

凸多边形三角剖分比较简单，可以使用第一个点依次连接后面的其他点来组成一组共同顶点的三角形。当然这是最简单的凸多边形剖分算法，还有其他最优剖分算法，需要考虑权重等，但我们不需要。

a b

图a为凸多边形，标出了顶点序号。

图b为三角剖分后，unity中所显示的三角形网格。

2.凹多边形

凹多边形的剖分则需要判断点与多边形的关系，以此来确定可划分顶点与不可划分顶点。

a b

图a为凹多边形（没有空洞），标出了顶点序号。

图b为三角剖分后，unity中所显示的三角形网格。

代码如下，参考上述连接：

1.MeshDrawBase.cs 基础类

1using System.Collections;
2using System.Collections.Generic;
3using UnityEngine;
4
5public abstract class MeshDrawBase : MonoBehaviour {
6
7    protected MeshFilter targetFilter;
8    protected Mesh mesh;
9    protected int[] tris;
10    protected Vector2[] uvs;
11    protected Vector3[] normals;
12
13    // Use this for initialization
14    void Awake () {
15        targetFilter = GetComponent<MeshFilter>();
16    }
17    
18    // Update is called once per frame
19    protected virtual void Update () {
20        DrawMesh();
21    }
22
23    protected abstract void DrawMesh();
24}

View Code

2.Polygon.cs 用于绘制多边形

1using System.Collections.Generic;
2using UnityEngine;
3
4public class Polygon : MeshDrawBase
5{
6    public List<Vector3> points = new List<Vector3>();
7    public List<int> indexes = new List<int>();
8    int index = 0;
9    Color[] colors;
10
11    void Start()
12    {
13        /*points.Add(new Vector3(0, 0, 0));
14        points.Add(new Vector3(0, 1, 0));
15        points.Add(new Vector3(1, 1, 0));
16        points.Add(new Vector3(0.7f, 0.8f, 0));
17        points.Add(new Vector3(1, 0.5f, 0));
18        points.Add(new Vector3(0.7f, 0.3f, 0));
19        points.Add(new Vector3(1, 0, 0));
20        indexes.Add(0);
21        indexes.Add(1);
22        indexes.Add(2);
23        indexes.Add(3);
24        indexes.Add(4);
25        indexes.Add(5);
26        indexes.Add(6);*/
27    }
28
29    protected override void DrawMesh()
30    {
31        if(Input.GetKeyDown(KeyCode.D))
32        {
33            DrawPolygon();
34        }
35    }
36
37    private void DrawPolygon()
38    {
39        mesh = new Mesh();
40        mesh.name = "Polygon";
41        mesh.vertices = points.ToArray();
42        
43        tris = Triangulation.WidelyTriangleIndex(new List<Vector3>(points), indexes).ToArray();
44
45        mesh.triangles = tris;
46
47        normals = new Vector3[mesh.vertices.Length];
48        for(int i = 0; i < mesh.vertices.Length; ++i)
49        {
50            normals[i] = new Vector3(0, 0, 1);
51        }
52
53        mesh.normals = normals;
54        
55        mesh.RecalculateBounds();
56        mesh.RecalculateTangents();
57
58        targetFilter.mesh = mesh;
59    }
60
61    protected override void Update()
62    {
63        base.Update();
64        if(Input.GetMouseButtonDown(0))
65        {
66            Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);
67            RaycastHit hit;
68            if(Physics.Raycast(ray, out hit, Mathf.Infinity))
69            {
70                var worldHitPos = hit.point;
71                var localHitPos = transform.InverseTransformPoint(worldHitPos);
72
73                points.Add(localHitPos);
74                indexes.Add(index++);
75            }
76        }
77
78        if(Input.GetKeyDown(KeyCode.R))
79        {
80            this.Reset();
81        }
82    }
83
84    private void Reset()
85    {
86        points.Clear();
87
88        targetFilter.mesh = null;
89        Destroy(mesh);
90    }
91
92    private void OnGUI()
93    {
94        if (points.Count == 0) return;
95
96        GUI.color = Color.red;
97
98        for(int i = 0; i < points.Count; ++i)
99        {
100            var worldPos = transform.TransformPoint(points[i]);
101            var screenPos = Camera.main.WorldToScreenPoint(worldPos);
102            var uiPos = new Vector3(screenPos.x, Camera.main.pixelHeight - screenPos.y, screenPos.z);
103
104            GUI.Label(new Rect(uiPos, new Vector2(100, 80)), i.ToString());
105        }
106    }
107
108    private void OnDrawGizmos()
109    {
110        if (points.Count == 0) return;
111
112        Gizmos.color = Color.cyan;
113        foreach(var pos in points)
114        {
115            var worldPos = transform.TransformPoint(pos);
116            Gizmos.DrawWireSphere(worldPos, .2f);
117        }
118    }
119}

View Code

3.Triangulation.cs 三角剖分工具类

1using UnityEngine;
2using System.Collections.Generic;
3
4/// <summary>
5/// 三维模型重建中的凹多边形三角剖分，适用于不带空洞的凹多边形
6/// ref: https://blog.csdn.net/huangzengman/article/details/77114082
7/// </summary>
8public static class Triangulation
9{
10    const double epsilon = 1e-7;
11
12    static bool floatLess(float value, float other)
13    {
14        return (other - value) > epsilon;
15    }
16
17    static bool floatGreat(float value, float other)
18    {
19        return (value - other) > epsilon;
20    }
21
22    static bool floatEqual(float value, float other)
23    {
24        return Mathf.Abs(value - other) < epsilon;
25    }
26
27    static bool Vector3Equal(Vector3 a, Vector3 b)
28    {
29        return floatEqual(a.x, b.x) && floatEqual(a.y, b.y) && floatEqual(a.z, b.z);
30    }
31
32    /// <summary>
33    /// 凸多边形，顺时针序列，以第1个点来剖分三角形，如下：
34    /// 0---1
35    /// |   |
36    /// 3---2  -->  (0, 1, 2)、(0, 2, 3)
37    /// </summary>
38    /// <param name="verts">顺时针排列的顶点列表</param>
39    /// <param name="indexes">顶点索引列表</param>
40    /// <returns>三角形列表</returns>
41    public static List<int> ConvexTriangleIndex(List<Vector3> verts, List<int> indexes)
42    {
43        int len = verts.Count;
44        //若是闭环去除最后一点
45        if (len > 1 && Vector3Equal(verts[0], verts[len - 1]))
46        {
47            len--;
48        }
49        int triangleNum = len - 2;
50        List<int> triangles = new List<int>(triangleNum * 3);
51        for (int i = 0; i < triangleNum; i++)
52        {
53            triangles.Add(indexes[0]);
54            triangles.Add(indexes[i + 1]);
55            triangles.Add(indexes[i + 2]);
56        }
57        return triangles;
58    }
59
60    /// <summary>
61    /// 三角剖分
62    /// 1.寻找一个可划分顶点
63    /// 2.分割出新的多边形和三角形
64    /// 3.新多边形若为凸多边形，结束；否则继续剖分
65    /// 
66    /// 寻找可划分顶点
67    /// 1.顶点是否为凸顶点：顶点在剩余顶点组成的图形外
68    /// 2.新的多边形没有顶点在分割的三角形内
69    /// </summary>
70    /// <param name="verts">顺时针排列的顶点列表</param>
71    /// <param name="indexes">顶点索引列表</param>
72    /// <returns>三角形列表</returns>
73    public static List<int> WidelyTriangleIndex(List<Vector3> verts, List<int> indexes)
74    {
75        int len = verts.Count;
76        if (len <= 3) return ConvexTriangleIndex(verts, indexes);
77
78        int searchIndex = 0;
79        List<int> covexIndex = new List<int>();
80        bool isCovexPolygon = true;//判断多边形是否是凸多边形
81
82        for (searchIndex = 0; searchIndex < len; searchIndex++)
83        {
84            List<Vector3> polygon = new List<Vector3>(verts.ToArray());
85            polygon.RemoveAt(searchIndex);
86            if (IsPointInsidePolygon(verts[searchIndex], polygon))
87            {
88                isCovexPolygon = false;
89                break;
90            }
91            else
92            {
93                covexIndex.Add(searchIndex);
94            }
95        }
96
97        if (isCovexPolygon) return ConvexTriangleIndex(verts, indexes);
98
99        //查找可划分顶点
100        int canFragementIndex = -1;//可划分顶点索引
101        for (int i = 0; i < len; i++)
102        {
103            if (i > searchIndex)
104            {
105                List<Vector3> polygon = new List<Vector3>(verts.ToArray());
106                polygon.RemoveAt(i);
107                if (!IsPointInsidePolygon(verts[i], polygon) && IsFragementIndex(i, verts))
108                {
109                    canFragementIndex = i;
110                    break;
111                }
112            }
113            else
114            {
115                if (covexIndex.IndexOf(i) != -1 && IsFragementIndex(i, verts))
116                {
117                    canFragementIndex = i;
118                    break;
119                }
120            }
121        }
122
123        if (canFragementIndex < 0)
124        {
125            Debug.LogError("数据有误找不到可划分顶点");
126            return new List<int>();
127        }
128
129        //用可划分顶点将凹多边形划分为一个三角形和一个多边形
130        List<int> tTriangles = new List<int>();
131        int next = (canFragementIndex == len - 1) ? 0 : canFragementIndex + 1;
132        int prev = (canFragementIndex == 0) ? len - 1 : canFragementIndex - 1;
133        tTriangles.Add(indexes[prev]);
134        tTriangles.Add(indexes[canFragementIndex]);
135        tTriangles.Add(indexes[next]);
136        //剔除可划分顶点及索引
137        verts.RemoveAt(canFragementIndex);
138        indexes.RemoveAt(canFragementIndex);
139
140        //递归划分
141        List<int> leaveTriangles = WidelyTriangleIndex(verts, indexes);
142        tTriangles.AddRange(leaveTriangles);
143
144        return tTriangles;
145    }
146
147    /// <summary>
148    /// 是否是可划分顶点:新的多边形没有顶点在分割的三角形内
149    /// </summary>
150    private static bool IsFragementIndex(int index, List<Vector3> verts)
151    {
152        int len = verts.Count;
153        List<Vector3> triangleVert = new List<Vector3>();
154        int next = (index == len - 1) ? 0 : index + 1;
155        int prev = (index == 0) ? len - 1 : index - 1;
156        triangleVert.Add(verts[prev]);
157        triangleVert.Add(verts[index]);
158        triangleVert.Add(verts[next]);
159        for (int i = 0; i < len; i++)
160        {
161            if (i != index && i != prev && i != next)
162            {
163                if (IsPointInsidePolygon(verts[i], triangleVert))
164                {
165                    return false;
166                }
167            }
168        }
169        return true;
170    }
171
172    /// <summary>
173    /// 射线与线段相交性判断
174    /// </summary>
175    /// <param name="ray">射线</param>
176    /// <param name="p1">线段头</param>
177    /// <param name="p2">线段尾</param>
178    /// <returns></returns>
179    private static bool IsDetectIntersect(Ray2D ray, Vector3 p1, Vector3 p2)
180    {
181        float pointY;//交点Y坐标，x固定值
182        if (floatEqual(p1.x, p2.x))
183        {
184            return false;
185        }
186        else if(floatEqual(p1.y, p2.y))
187        {
188            pointY = p1.y;
189        }
190        else
191        {
192            //直线两点式方程：(y-y2)/(y1-y2) = (x-x2)/(x1-x2)
193            float a = p1.x - p2.x;
194            float b = p1.y - p2.y;
195            float c = p2.y / b - p2.x / a;
196
197            pointY = b / a * ray.origin.x + b * c;
198        }
199        
200        if (floatLess(pointY, ray.origin.y))
201        {
202            //交点y小于射线起点y
203            return false;
204        }
205        else
206        {
207            Vector3 leftP = floatLess(p1.x, p2.x) ? p1 : p2;//左端点
208            Vector3 rightP = floatLess(p1.x, p2.x) ? p2 : p1;//右端点
209            //交点x位于线段两个端点x之外，相交与线段某个端点时，仅将射线L与左侧多边形一边的端点记为焦点(即就是：只将右端点记为交点)
210            if (!floatGreat(ray.origin.x, leftP.x) || floatGreat(ray.origin.x, rightP.x))
211            {
212                return false;
213            }
214        }
215
216        return true;
217    }
218
219    /// <summary>
220    /// 点与多边形的位置关系
221    /// </summary>
222    /// <param name="point">判定点</param>
223    /// <param name="polygonVerts">剩余顶点按顺序排列的多边形</param>
224    /// <returns>true:点在多边形之内，false:相反</returns>
225    private static bool IsPointInsidePolygon(Vector3 point, List<Vector3> polygonVerts)
226    {
227        int len = polygonVerts.Count;
228        Ray2D ray = new Ray2D(point, new Vector3(0, 1)); //y方向射线
229        int interNum = 0;
230
231        for (int i = 1; i < len; i++)
232        {
233            if (IsDetectIntersect(ray, polygonVerts[i - 1], polygonVerts[i]))
234            {
235                interNum++;
236            }
237        }
238
239        //不是闭环
240        if (!Vector3Equal(polygonVerts[0], polygonVerts[len - 1]))
241        {
242            if (IsDetectIntersect(ray, polygonVerts[len - 1], polygonVerts[0]))
243            {
244                interNum++;
245            }
246        }
247        int remainder = interNum % 2;
248        return remainder == 1;
249    }
250}

View Code

使用方法：新建一个Quad，将Polygon.cs脚本添加上，用鼠标点击来确定多边形的个顶点位置，之后按D进行绘制。

git：https://gitee.com/planefight/RunSprite\_Tri.git

参照论文：

三维模型重建中的凹多边形三角剖分：

Unity 凹多边形三角剖分

评论区

相关推荐