[SOLVED] Draw Polygon2D Collider paths around a 2D Mesh

Here's a fun puzzle I've been mulling about for the last couple of days:

Given any 2D mesh, how would I write an algorithm to draw a series of polygon collider paths around the perimeter and inside the holes?

Assumptions:
Mesh is non manifold and 2D; all z coordinates are 0.
Mesh is built correctly in the sense that it has no intersecting or overlapping faces.
Mesh could potentially contain holes.
Mesh is built arbitrarily and procedurally, so we have all the information about it. For example, in what order the vertices were constructed.

Basically, I've got a procedural mesh generator, and I'd like to turn this:

Into this:

(Paths and points highlighted for clarity)

What do you guys think? @BoredMormon? @Gamer_Woods? @lordofduct?

 

You're just trying to find non-shared edges, right??

- An edge is defined as the line between vert A/B.
- An EdgeKey is a unique Key based on A/B
- Add each Edge to a dictionary<EdgeKey,int>, incrementing the value +1 each time
- Iterate all Dict entries that hold a value of 1 (i.e., no shared faces)
- sort and produce a "chain" them together based on the ends matching up as far as unique verts

Am I understanding what you want?

 

My first thought is Unity does this automatically when you add a polygon collider to a sprite. I wonder if there is a way to hook into that sort of behaviour.

Edit: @Kurt Dekker's solution will do the job well.

 

S*** man, that is brilliant. I would not have thought of that. I'm going to give that a shot.

Yeah, I thought of that as well, but I imagine it's an image edge detection algorithm. Like kurt said above though, if I just cycle through each edge, I'll bet it I can replicate the behaviour pretty easily.

 

Yup. I was sitting here looking for a solution based on some unique property of an edge vertex. Which of course is the wrong way to solve this problem.

 

@Kurt Dekker, thanks again. After a couple of days of scratching my head all it took was two hours to get it working after your input.

Relevant code, if anyone is interested:
(It's not factored, organized, commented or thoroughly tested, I just wrote it. Seems to work though!)

Code (CSharp):

1.  
2. struct Edge {
3.  
4.     public Vector2 a;
5.     public Vector2 b;
6.  
7.     public override bool Equals (object obj)
8.     {
9.         if (obj is Edge) {
10.             var edge = (Edge)obj;
11.             //An edge is equal regardless of which order it's points are in
12.             return (edge.a == a && edge.b == b) || (edge.b == a && edge.a == b);
13.         }
14.  
15.         return false;
16.        
17.     }
18.    
19.     public override int GetHashCode ()
20.     {
21.         return a.GetHashCode() ^ b.GetHashCode();
22.     }
23.  
24.     public override string ToString ()
25.     {
26.         return string.Format ("["+a.x+","+a.y+"->"+b.x+","+b.y+"]");
27.     }
28.  
29. }
30.  
31. static bool CoordinatesFormLine(Vector2 a, Vector2 b, Vector2 c){
32.    
33.     //If the area of a triangle created from three points is zero, they must be in a line.
34.     float area = a.x * ( b.y - c.y ) +
35.                  b.x * ( c.y - a.y ) +
36.                  c.x * ( a.y - b.y );
37.    
38.     return Mathf.Approximately(area, 0f);
39.    
40. }
41.  
42. static Vector2[] CoordinatesCleaned(List<Vector2> coordinates) {
43.    
44.     List<Vector2> coordinatesCleaned = new List<Vector2> ();
45.     coordinatesCleaned.Add (coordinates [0]);
46.    
47.     var lastAddedIndex = 0;
48.    
49.     for (int i = 1; i < coordinates.Count; i++) {
50.        
51.         var coordinate = coordinates [i];
52.        
53.         Vector2 lastAddedCoordinate = coordinates [lastAddedIndex];
54.         Vector2 nextCoordinate = (i + 1 >= coordinates.Count) ? coordinates[0] : coordinates [i + 1];
55.        
56.         if (!CoordinatesFormLine(lastAddedCoordinate, coordinate, nextCoordinate)) {
57.            
58.             coordinatesCleaned.Add (coordinate);
59.             lastAddedIndex = i;          
60.            
61.         }
62.        
63.     }
64.    
65.     return coordinatesCleaned.ToArray ();
66.    
67. }
68.  
69. static List<Vector2[]> BuildColliderPaths(Dictionary<Edge, int> edges) {
70.    
71.     var outerEdges = new List<Edge>();
72.    
73.     foreach(var keyVal in edges)
74.         if (keyVal.Value == 1)
75.             outerEdges.Add (keyVal.Key);
76.    
77.     var orderedPaths = new List<List<Edge>>();
78.     List<Edge> orderedEdges = null;
79.    
80.     while (outerEdges.Count > 0) {
81.        
82.         int addedThisRound = 0;
83.        
84.         if (orderedEdges == null) {
85.             orderedEdges = new List<Edge>();
86.             orderedEdges.Add (outerEdges[0]);
87.             outerEdges.RemoveAt(0);
88.             orderedPaths.Add (orderedEdges);
89.         }
90.  
91.         var removeIndexes = new List<int>();
92.         for (int i = 0; i < outerEdges.Count; i++) {
93.             var edge = outerEdges [i];
94.             if (edge.b == orderedEdges [0].a) {
95.                 orderedEdges.Insert (0, edge);
96.                 removeIndexes.Add (i);
97.             }
98.  
99.             else if (edge.a == orderedEdges[orderedEdges.Count - 1].b) {
100.                 orderedEdges.Add(edge);
101.                 removeIndexes.Add (i);
102.             }
103.         }
104.        
105.         for (var i = removeIndexes.Count - 1; i >= 0; i --)
106.             outerEdges.RemoveAt(i);
107.        
108.         //If there wasn't any added this round, then we must need to start a new path, because the remaining edges arn't connected.
109.         if (addedThisRound == 0)
110.             orderedEdges = null;
111.  
112.     }
113.  
114.     var cleanedPaths = new List<Vector2[]>();
115.  
116.     foreach(var builtPath in orderedPaths) {
117.         var coords = new List<Vector2>();
118.  
119.         foreach(var edge in builtPath)
120.             coords.Add (edge.a);
121.  
122.         cleanedPaths.Add (CoordinatesCleaned(coords));
123.     }
124.  
125.  
126.     return cleanedPaths;
127. }
128.  
129. public static void DrawColliderPaths(PolygonCollider2D collider, Mesh mesh)
130. {
131.     var edges = CreateEdgesFromMesh(mesh);
132.     var paths = BuildColliderPaths(edges);
133.  
134.     collider.pathCount = paths.Count;
135.     for (int i = 0; i < paths.Count; i++) {
136.         var path = paths [i];
137.         collider.SetPath(i, path);
138.     }
139. }

Woo!

 

If anyone happens across this problem again, I've adapted the above code into a component. Just attach it to a gameObject with a 2D mesh and it'll do the rest.

Make sure that the mesh you're using is a non-manifold 2D mesh without any intersecting or overlapping faces, otherwise the Polygon2DCollider wont make it's edges correctly.

It could be adapted to add warnings for such cases in the future. For now:

Code (CSharp):

1. using UnityEngine;
2. using System.Collections.Generic;
3. using UnityEditor;
4.  
5. [RequireComponent(typeof(MeshFilter))]
6. [RequireComponent(typeof(PolygonCollider2D))]
7. [ExecuteInEditMode]
8. public class Mesh2DColliderMaker : MonoBehaviour {
9.  
10.     MeshFilter filter;
11.     PolygonCollider2D polyCollider;
12.  
13.     #region Unity Callers
14.  
15.     void Start()
16.     {
17.         filter = GetComponent<MeshFilter>();
18.         polyCollider = GetComponent<PolygonCollider2D>();
19.     }
20.  
21. #if UNITY_EDITOR
22.     void Update()
23.     {
24.         if (!Application.isPlaying)
25.             CreatePolygon2DColliderPoints();
26.     }
27. #endif
28.  
29.     #endregion
30.  
31.     #region API
32.  
33.     public void CreatePolygon2DColliderPoints()
34.     {
35.         var edges = BuildEdgesFromMesh();
36.         var paths = BuildColliderPaths(edges);
37.         ApplyPathsToPolygonCollider(paths);
38.     }
39.  
40.     #endregion
41.  
42.     #region Helper
43.  
44.     void ApplyPathsToPolygonCollider(List<Vector2[]> paths)
45.     {
46.         if (paths == null)
47.             return;
48.  
49.         polyCollider.pathCount = paths.Count;
50.         for (int i = 0; i < paths.Count; i++) {
51.             var path = paths [i];
52.             polyCollider.SetPath(i, path);
53.         }
54.     }
55.  
56.     Dictionary<Edge2D, int> BuildEdgesFromMesh()
57.     {
58.         var mesh = filter.sharedMesh;
59.  
60.         if (mesh == null)
61.             return null;
62.  
63.         var verts = mesh.vertices;
64.         var tris = mesh.triangles;
65.         var edges = new Dictionary<Edge2D, int>();
66.  
67.         for (int i = 0; i < tris.Length - 2; i += 3) {
68.  
69.             var faceVert1 = verts[tris[i]];
70.             var faceVert2 = verts[tris[i + 1]];
71.             var faceVert3 = verts[tris[i + 2]];
72.  
73.             Edge2D[] faceEdges;
74.             faceEdges = new Edge2D[] {
75.                 new Edge2D{ a = faceVert1, b = faceVert2 },
76.                 new Edge2D{ a = faceVert2, b = faceVert3 },
77.                 new Edge2D{ a = faceVert3, b = faceVert1 },
78.             };
79.  
80.             foreach(var edge in faceEdges) {
81.                 if (edges.ContainsKey(edge))
82.                     edges[edge]++;
83.                 else
84.                     edges[edge] = 1;
85.             }
86.         }
87.  
88.         return edges;
89.     }
90.  
91.     static List<Edge2D> GetOuterEdges(Dictionary<Edge2D, int> allEdges)
92.     {
93.         var outerEdges = new List<Edge2D>();
94.  
95.         foreach(var edge in allEdges.Keys) {
96.             var numSharedFaces = allEdges[edge];
97.             if (numSharedFaces == 1)
98.                 outerEdges.Add (edge);
99.         }
100.  
101.         return outerEdges;
102.     }
103.  
104.     static List<Vector2[]> BuildColliderPaths(Dictionary<Edge2D, int> allEdges)
105.     {
106.  
107.         if (allEdges == null)
108.             return null;  
109.  
110.         var outerEdges = GetOuterEdges(allEdges);
111.  
112.         var paths = new List<List<Edge2D>>();
113.         List<Edge2D> path = null;
114.      
115.         while (outerEdges.Count > 0) {
116.          
117.             if (path == null) {
118.                 path = new List<Edge2D>();
119.                 path.Add (outerEdges[0]);
120.                 paths.Add (path);
121.  
122.                 outerEdges.RemoveAt(0);
123.             }
124.  
125.             bool foundAtLeastOneEdge = false;
126.  
127.             int i = 0;
128.             while (i < outerEdges.Count) {
129.                 var edge = outerEdges [i];
130.                 bool removeEdgeFromOuter = false;
131.  
132.                 if (edge.b == path[0].a) {
133.                     path.Insert (0, edge);
134.                     removeEdgeFromOuter = true;
135.                 }
136.                 else if (edge.a == path[path.Count - 1].b) {
137.                     path.Add(edge);
138.                     removeEdgeFromOuter = true;
139.                 }
140.  
141.                 if (removeEdgeFromOuter) {
142.                     foundAtLeastOneEdge = true;
143.                     outerEdges.RemoveAt(i);
144.                 } else
145.                     i++;
146.             }
147.  
148.             //If we didn't find at least one edge, then the remaining outer edges must belong to a different path
149.             if (!foundAtLeastOneEdge)
150.                 path = null;
151.          
152.         }
153.      
154.         var cleanedPaths = new List<Vector2[]>();
155.      
156.         foreach(var builtPath in paths) {
157.             var coords = new List<Vector2>();
158.          
159.             foreach(var edge in builtPath)
160.                 coords.Add (edge.a);
161.          
162.             cleanedPaths.Add (CoordinatesCleaned(coords));
163.         }
164.      
165.      
166.         return cleanedPaths;
167.     }
168.  
169.     static bool CoordinatesFormLine(Vector2 a, Vector2 b, Vector2 c)
170.     {
171.         //If the area of a triangle created from three points is zero, they must be in a line.
172.         float area = a.x * ( b.y - c.y ) +
173.             b.x * ( c.y - a.y ) +
174.                 c.x * ( a.y - b.y );
175.      
176.         return Mathf.Approximately(area, 0f);
177.      
178.     }
179.  
180.     static Vector2[] CoordinatesCleaned(List<Vector2> coordinates)
181.     {
182.         List<Vector2> coordinatesCleaned = new List<Vector2> ();
183.         coordinatesCleaned.Add (coordinates [0]);
184.      
185.         var lastAddedIndex = 0;
186.      
187.         for (int i = 1; i < coordinates.Count; i++) {
188.          
189.             var coordinate = coordinates [i];
190.          
191.             Vector2 lastAddedCoordinate = coordinates [lastAddedIndex];
192.             Vector2 nextCoordinate = (i + 1 >= coordinates.Count) ? coordinates[0] : coordinates [i + 1];
193.          
194.             if (!CoordinatesFormLine(lastAddedCoordinate, coordinate, nextCoordinate)) {
195.              
196.                 coordinatesCleaned.Add (coordinate);
197.                 lastAddedIndex = i;          
198.              
199.             }
200.          
201.         }
202.      
203.         return coordinatesCleaned.ToArray ();
204.      
205.     }
206.  
207.     #endregion
208.  
209.     #region Nested
210.  
211.     struct Edge2D {
212.      
213.         public Vector2 a;
214.         public Vector2 b;
215.  
216.         public override bool Equals (object obj)
217.         {
218.             if (obj is Edge2D) {
219.                 var edge = (Edge2D)obj;
220.                 //An edge is equal regardless of which order it's points are in
221.                 return (edge.a == a && edge.b == b) || (edge.b == a && edge.a == b);
222.             }
223.          
224.             return false;
225.          
226.         }
227.  
228.         public override int GetHashCode ()
229.         {
230.             return a.GetHashCode() ^ b.GetHashCode();
231.         }
232.      
233.         public override string ToString ()
234.         {
235.             return string.Format ("["+a.x+","+a.y+"->"+b.x+","+b.y+"]");
236.         }
237.      
238.     }
239.    #endregion
240. }
241.  

And heres a working scene:

 

Thank you @BenZed. I'm using SVGImporter from the asset store and I couldn't get the correct colliders to be generated for "holes" in my SVG. Dropping this in worked first time. Perfect!

 

Just chiming in to say this script was awesome and worked like a charm @BenZed! Works perfectly with my mesh generator for a zoning component I am working on which required a 2D polygon collider! Was struggling to find good documentation on it, so this is definitely a time saver! Thanks!!

 

Still works like a treat!!!
I took liberty and made it static so my mesh generator after generating itself on start just creating new polygon collider and adjusting it with your script!
Works on massive meshes as well as small. Great work!