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)
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.
Shit 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!)
struct Edge {
public Vector2 a;
public Vector2 b;
public override bool Equals (object obj)
{
if (obj is Edge) {
var edge = (Edge)obj;
//An edge is equal regardless of which order it's points are in
return (edge.a == a && edge.b == b) || (edge.b == a && edge.a == b);
}
return false;
}
public override int GetHashCode ()
{
return a.GetHashCode() ^ b.GetHashCode();
}
public override string ToString ()
{
return string.Format ("["+a.x+","+a.y+"->"+b.x+","+b.y+"]");
}
}
static bool CoordinatesFormLine(Vector2 a, Vector2 b, Vector2 c){
//If the area of a triangle created from three points is zero, they must be in a line.
float area = a.x * ( b.y - c.y ) +
b.x * ( c.y - a.y ) +
c.x * ( a.y - b.y );
return Mathf.Approximately(area, 0f);
}
static Vector2[] CoordinatesCleaned(List<Vector2> coordinates) {
List<Vector2> coordinatesCleaned = new List<Vector2> ();
coordinatesCleaned.Add (coordinates [0]);
var lastAddedIndex = 0;
for (int i = 1; i < coordinates.Count; i++) {
var coordinate = coordinates [i];
Vector2 lastAddedCoordinate = coordinates [lastAddedIndex];
Vector2 nextCoordinate = (i + 1 >= coordinates.Count) ? coordinates[0] : coordinates [i + 1];
if (!CoordinatesFormLine(lastAddedCoordinate, coordinate, nextCoordinate)) {
coordinatesCleaned.Add (coordinate);
lastAddedIndex = i;
}
}
return coordinatesCleaned.ToArray ();
}
static List<Vector2[]> BuildColliderPaths(Dictionary<Edge, int> edges) {
var outerEdges = new List<Edge>();
foreach(var keyVal in edges)
if (keyVal.Value == 1)
outerEdges.Add (keyVal.Key);
var orderedPaths = new List<List<Edge>>();
List<Edge> orderedEdges = null;
while (outerEdges.Count > 0) {
int addedThisRound = 0;
if (orderedEdges == null) {
orderedEdges = new List<Edge>();
orderedEdges.Add (outerEdges[0]);
outerEdges.RemoveAt(0);
orderedPaths.Add (orderedEdges);
}
var removeIndexes = new List<int>();
for (int i = 0; i < outerEdges.Count; i++) {
var edge = outerEdges [i];
if (edge.b == orderedEdges [0].a) {
orderedEdges.Insert (0, edge);
removeIndexes.Add (i);
}
else if (edge.a == orderedEdges[orderedEdges.Count - 1].b) {
orderedEdges.Add(edge);
removeIndexes.Add (i);
}
}
for (var i = removeIndexes.Count - 1; i >= 0; i --)
outerEdges.RemoveAt(i);
//If there wasn't any added this round, then we must need to start a new path, because the remaining edges arn't connected.
if (addedThisRound == 0)
orderedEdges = null;
}
var cleanedPaths = new List<Vector2[]>();
foreach(var builtPath in orderedPaths) {
var coords = new List<Vector2>();
foreach(var edge in builtPath)
coords.Add (edge.a);
cleanedPaths.Add (CoordinatesCleaned(coords));
}
return cleanedPaths;
}
public static void DrawColliderPaths(PolygonCollider2D collider, Mesh mesh)
{
var edges = CreateEdgesFromMesh(mesh);
var paths = BuildColliderPaths(edges);
collider.pathCount = paths.Count;
for (int i = 0; i < paths.Count; i++) {
var path = paths [i];
collider.SetPath(i, path);
}
}
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:
using UnityEngine;
using System.Collections.Generic;
using UnityEditor;
[RequireComponent(typeof(MeshFilter))]
[RequireComponent(typeof(PolygonCollider2D))]
[ExecuteInEditMode]
public class Mesh2DColliderMaker : MonoBehaviour {
MeshFilter filter;
PolygonCollider2D polyCollider;
#region Unity Callers
void Start()
{
filter = GetComponent<MeshFilter>();
polyCollider = GetComponent<PolygonCollider2D>();
}
#if UNITY_EDITOR
void Update()
{
if (!Application.isPlaying)
CreatePolygon2DColliderPoints();
}
#endif
#endregion
#region API
public void CreatePolygon2DColliderPoints()
{
var edges = BuildEdgesFromMesh();
var paths = BuildColliderPaths(edges);
ApplyPathsToPolygonCollider(paths);
}
#endregion
#region Helper
void ApplyPathsToPolygonCollider(List<Vector2[]> paths)
{
if (paths == null)
return;
polyCollider.pathCount = paths.Count;
for (int i = 0; i < paths.Count; i++) {
var path = paths [i];
polyCollider.SetPath(i, path);
}
}
Dictionary<Edge2D, int> BuildEdgesFromMesh()
{
var mesh = filter.sharedMesh;
if (mesh == null)
return null;
var verts = mesh.vertices;
var tris = mesh.triangles;
var edges = new Dictionary<Edge2D, int>();
for (int i = 0; i < tris.Length - 2; i += 3) {
var faceVert1 = verts[tris[i]];
var faceVert2 = verts[tris[i + 1]];
var faceVert3 = verts[tris[i + 2]];
Edge2D[] faceEdges;
faceEdges = new Edge2D[] {
new Edge2D{ a = faceVert1, b = faceVert2 },
new Edge2D{ a = faceVert2, b = faceVert3 },
new Edge2D{ a = faceVert3, b = faceVert1 },
};
foreach(var edge in faceEdges) {
if (edges.ContainsKey(edge))
edges[edge]++;
else
edges[edge] = 1;
}
}
return edges;
}
static List<Edge2D> GetOuterEdges(Dictionary<Edge2D, int> allEdges)
{
var outerEdges = new List<Edge2D>();
foreach(var edge in allEdges.Keys) {
var numSharedFaces = allEdges[edge];
if (numSharedFaces == 1)
outerEdges.Add (edge);
}
return outerEdges;
}
static List<Vector2[]> BuildColliderPaths(Dictionary<Edge2D, int> allEdges)
{
if (allEdges == null)
return null;
var outerEdges = GetOuterEdges(allEdges);
var paths = new List<List<Edge2D>>();
List<Edge2D> path = null;
while (outerEdges.Count > 0) {
if (path == null) {
path = new List<Edge2D>();
path.Add (outerEdges[0]);
paths.Add (path);
outerEdges.RemoveAt(0);
}
bool foundAtLeastOneEdge = false;
int i = 0;
while (i < outerEdges.Count) {
var edge = outerEdges [i];
bool removeEdgeFromOuter = false;
if (edge.b == path[0].a) {
path.Insert (0, edge);
removeEdgeFromOuter = true;
}
else if (edge.a == path[path.Count - 1].b) {
path.Add(edge);
removeEdgeFromOuter = true;
}
if (removeEdgeFromOuter) {
foundAtLeastOneEdge = true;
outerEdges.RemoveAt(i);
} else
i++;
}
//If we didn't find at least one edge, then the remaining outer edges must belong to a different path
if (!foundAtLeastOneEdge)
path = null;
}
var cleanedPaths = new List<Vector2[]>();
foreach(var builtPath in paths) {
var coords = new List<Vector2>();
foreach(var edge in builtPath)
coords.Add (edge.a);
cleanedPaths.Add (CoordinatesCleaned(coords));
}
return cleanedPaths;
}
static bool CoordinatesFormLine(Vector2 a, Vector2 b, Vector2 c)
{
//If the area of a triangle created from three points is zero, they must be in a line.
float area = a.x * ( b.y - c.y ) +
b.x * ( c.y - a.y ) +
c.x * ( a.y - b.y );
return Mathf.Approximately(area, 0f);
}
static Vector2[] CoordinatesCleaned(List<Vector2> coordinates)
{
List<Vector2> coordinatesCleaned = new List<Vector2> ();
coordinatesCleaned.Add (coordinates [0]);
var lastAddedIndex = 0;
for (int i = 1; i < coordinates.Count; i++) {
var coordinate = coordinates [i];
Vector2 lastAddedCoordinate = coordinates [lastAddedIndex];
Vector2 nextCoordinate = (i + 1 >= coordinates.Count) ? coordinates[0] : coordinates [i + 1];
if (!CoordinatesFormLine(lastAddedCoordinate, coordinate, nextCoordinate)) {
coordinatesCleaned.Add (coordinate);
lastAddedIndex = i;
}
}
return coordinatesCleaned.ToArray ();
}
#endregion
#region Nested
struct Edge2D {
public Vector2 a;
public Vector2 b;
public override bool Equals (object obj)
{
if (obj is Edge2D) {
var edge = (Edge2D)obj;
//An edge is equal regardless of which order it's points are in
return (edge.a == a && edge.b == b) || (edge.b == a && edge.a == b);
}
return false;
}
public override int GetHashCode ()
{
return a.GetHashCode() ^ b.GetHashCode();
}
public override string ToString ()
{
return string.Format ("["+a.x+","+a.y+"->"+b.x+","+b.y+"]");
}
}
#endregion
}
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!
I’ve not tried this out… but if I had a 3d mesh could this generate a 2d polygon collider like a cross section where you just specify where it should cut through and create the 2d collider mesh, so you just control a the z intersection on a 3d mesh ?
wanting to mix 3d meshes but use 2d physics and collision instead of sprites for everything
