Triangulating mesh from collider points

Hi,
I’ve been writing a script to copy a section of any 2D collider with a circle collider. Basically, the player can draw a circle on the screen and it will copy whatever is inside of that circle and nothing that is outside it. I get collider points from the circle collider by looping through 360 degrees of the circumference of the circle.
[89320-capture2.png*_|89320]
Here is a quick summary of how it works:

  • Get the 2D Collider the circle is triggered by.
  • Get the collider type (Circle, polygon, box)
  • Loop through the points of the collider clockwise and add them to a list
  • Loop through the points in the collider and see which ones are inside the circle
  • Loop through the points in the original circle collider and see which ones are contained in the other shapes collider
  • Add both lists of points together
  • Use the [triangulation script][2] to get a shape from the points.

I will get the shape I want some of the time, but it is often formed wrong.
[89321-final-shapes.png*_|89321]
The Left shape is an attempt to copy the left end of a box collider and the right shape is a copy of the right side of the same box collider. It seems to be consistent that this will be the issue depending on which side of the box I copy from.

Getting the intersection between two circle colliders always works, but box colliders and polygon colliders give me trouble.

Some steps I have tried:

  • Reversing the order of the box collider (this makes it worse)
  • Adding the circle colliders points before the triggered colliders points (this doesn’t affect anything)
  • Reversing the order of the circle collider (makes things worse)
  • Decreasing the number of points for a circle collider (no change)
  • Using mesh.Optimize() (do not see any changes)

Any Ideas on how to make this more robust? I thought of using the delauny triangulation, but I don’t need any complex shapes and would like to keep this running fast.

Here is my current script:

using UnityEngine;
using System.Collections;
using System;
using System.Collections.Generic;
using System.Linq;

public class CopyCircle : MonoBehaviour {

    Vector2 startPoint;
    Vector2 endPoint;
    float diameter;

    MeshRenderer meshRenderer;

    List<GameObject> collidedObjects;
    GameObject copy;

    CircleCollider2D circleCollider;

    public int degreesToScan = 360; // Set to how accurate collisions should be saved.
    public float percentageToCircle = .80f;

    void Awake ()
    {
        meshRenderer = GetComponent<MeshRenderer>();
        meshRenderer.enabled = false;

        circleCollider = GetComponent<CircleCollider2D>();
        collidedObjects = new List<GameObject>();
    }
	
	// Update is called once per frame
	void Update () {
        if (Input.GetMouseButtonDown(1))
        {
            startPoint = GetMousePosition();
        }
        else if (Input.GetMouseButton(1)) // If left click is down
        {
            endPoint = GetMousePosition();

            Debug.DrawLine(startPoint, endPoint);

            transform.position = new Vector3((startPoint.x + endPoint.x) / 2, (startPoint.y + endPoint.y) / 2, -1);
            diameter = Vector2.Distance(startPoint, endPoint);

            transform.localScale = new Vector2(diameter, diameter);
            meshRenderer.enabled = true;
        }
        else if (Input.GetMouseButtonUp(1)) // Released
        {
            meshRenderer.enabled = false;
        }
        else if (Input.GetMouseButtonDown(0) && collidedObjects.Count > 0) // Left mouse down
        {
            if (copy)
                Destroy(copy);
            copy = Copy();
        }
        else if (Input.GetMouseButton(0) && copy)
        {
            copy.transform.position = GetMousePosition();
        }
        else if (Input.GetMouseButtonUp(0) && copy)
        {
            for (int i = 0; i < copy.transform.childCount; i++)
            {
                for (int o = 0; o < collidedObjects.Count; o++)
                {
                    if (o != i && 
                        copy.transform.GetChild(o).GetComponent<Collider2D>().IsTouching(copy.transform.GetChild(i).GetComponent<Collider2D>()) &&
                        (!collidedObjects[o].GetComponent<Rigidbody2D>() || !collidedObjects*.GetComponent<Rigidbody2D>()))*

{
// connect the objects
copy.transform.GetChild(o).gameObject.AddComponent().connectedBody = copy.transform.GetChild(i).gameObject.GetComponent();
}
}
copy.transform.GetComponentsInChildren().isKinematic = false;
copy.transform.GetComponentsInChildren().isTrigger = false;
}
}
* }*

Vector2 GetMousePosition()
{
return Camera.main.ScreenToWorldPoint(Input.mousePosition);
}

void OnTriggerStay2D(Collider2D col)
{
if (meshRenderer.enabled && col.gameObject.tag != “Copy” && !collidedObjects.Contains(col.gameObject))
{
collidedObjects.Add(col.gameObject);
}
}

void OnTriggerExit2D(Collider2D col)
{
if(collidedObjects.Contains(col.gameObject))
{
collidedObjects.Remove(col.gameObject);
}
}

GameObject Copy()
{
GameObject copy = new GameObject(“New Copy”);

// Do the hard stuff here

// First loop through the other objects collider to see which points are inside the copy circle

for (int o = 0; o < collidedObjects.Count; o++)
{
List OthersColliderPoints = new List();
GameObject collidedObject = collidedObjects[o];

if (collidedObject.GetComponent()) // Box
OthersColliderPoints.AddRange(GetBoxColliderEdges(collidedObject.GetComponent()));
else if (collidedObject.GetComponent()) // Polygon
OthersColliderPoints.AddRange(GetPolygonColliderPoints(collidedObject.GetComponent()));
else // Circle
OthersColliderPoints.AddRange(GetCircleColliderPoints(collidedObject.GetComponent(), circleCollider, degreesToScan));

List PointsToAdd = new List();

// Loop through the other shapes points and add the ones that are inside the bounds of the circle
for (var p = 0; p < OthersColliderPoints.Count; p++)
{
if (circleCollider.OverlapPoint(OthersColliderPoints[p]))
{
PointsToAdd.Add(OthersColliderPoints[p]);
Debug.Log(OthersColliderPoints[p]);
}
}

List CirclesColliderPoints = new List();
CirclesColliderPoints.AddRange(GetCircleColliderPoints(circleCollider, collidedObjects[o].GetComponent(), degreesToScan));

bool isMostlyCircle = CirclesColliderPoints.Count / degreesToScan >= percentageToCircle;

PointsToAdd.AddRange(CirclesColliderPoints);

for (int i = 0; i < PointsToAdd.Count; i++)
{
PointsToAdd -= new Vector2(transform.position.x, transform.position.y); // center the points to the object
}

Vector2[] booleanShape = new HashSet(PointsToAdd).ToArray();

for (int i = 0; i < booleanShape.Length; i++)
{
Debug.Log(booleanShape*);*
}

Mesh msh = CreateMeshFromPoints(booleanShape);

GameObject subCopy = new GameObject();
// Add required components to the copy object
subCopy.AddComponent().material = collidedObjects[o].GetComponent().material;
subCopy.AddComponent().mesh = msh;
subCopy.AddComponent().isKinematic = true;
subCopy.GetComponent().useAutoMass = true;
if (isMostlyCircle)
subCopy.AddComponent();
else
subCopy.AddComponent().points = booleanShape;
subCopy.GetComponent().isTrigger = true;
subCopy.transform.SetParent(copy.transform);
subCopy.layer = LayerMask.NameToLayer(“Solid”);
subCopy.tag = “Copy”;
}

copy.layer = LayerMask.NameToLayer(“Solid”);
copy.tag = “Copy”;
return copy;
}

public static Vector2 PointOnCircle(float radius, float angleInDegrees, Vector2 origin)
{
// Convert from degrees to radians via multiplication by PI/180
float x = (float)(radius * Math.Cos(angleInDegrees * Math.PI / 180F)) + origin.x;
float y = (float)(radius * Math.Sin(angleInDegrees * Math.PI / 180F)) + origin.y;

return new Vector2(x, y);
}

Vector2[] GetBoxColliderEdges(BoxCollider2D col)
{
return new Vector2[]
{
col.gameObject.transform.TransformPoint(col.offset + new Vector2(col.size.x, -col.size.y) * 0.5f),
col.gameObject.transform.TransformPoint(col.offset + new Vector2(col.size.x, col.size.y) * 0.5f),
col.gameObject.transform.TransformPoint(col.offset + new Vector2(-col.size.x, col.size.y) * 0.5f),
col.gameObject.transform.TransformPoint(col.offset + new Vector2(-col.size.x, -col.size.y) * 0.5f)
};
}

// Returns a list of points of circle that are inside of collider
List GetCircleColliderPoints(CircleCollider2D circleCol, Collider2D col, int degreeResolution)
{
List points = new List();

for (var d = 0; d < degreeResolution; d++)
{
float degree = (360 / degreeResolution) * d;
Vector2 pointOnCircle = PointOnCircle(circleCol.radius * circleCol.transform.lossyScale.x, degree, circleCol.transform.position);
if (col.OverlapPoint(pointOnCircle)) // If point on circle is inside other collider
points.Add(pointOnCircle);
}

return points;
}

List GetPolygonColliderPoints(PolygonCollider2D polyCol)
{
List polyPoints = new List();
for (int i = 0; i < polyCol.points.Length; i++)
{
polyPoints.Add(polyCol.transform.TransformPoint(polyCol.points*));*
}
return polyPoints;
}

Mesh CreateMeshFromPoints(Vector2[] booleanShape)
{
// Use triangulator to get verticies for mesh
Triangulator triangulator = new Triangulator(booleanShape);
int[] indices = triangulator.Triangulate();

// Create Vector2 Verticies
Vector3[] verticies = new Vector3[booleanShape.Length];
for (int i = 0; i < verticies.Length; i++)
{
verticies = new Vector3(booleanShape_.x, booleanShape*.y, 0);
}*_

// Create a mesh
Mesh msh = new Mesh();
msh.vertices = verticies;
msh.triangles = indices;
msh.RecalculateNormals();
msh.RecalculateBounds();
//msh.Optimize();
msh.name = “Copy”;
return msh;
}
}
*
[2]: http://wiki.unity3d.com/index.php?title=Triangulator*_
_

Okay. Found a solution that worked for me.

Used [this Delauny script][1] to convert the points before using them for the polygon collider and mesh.

Here was the function I wrote to simplify it for myself:

Vector2[] ConvertPointsToDelauny(Vector2[] points)
    {
        List<uint> colors = new List<uint>();
        float xMax = -1000;
        float xMin = 1000;
        float yMax = -1000;
        float yMin = 1000;

        for (int i = 0; i < points.Length; i++)
        {
            colors.Add(0);
            if (points*.x > xMax)*

xMax = points*.x;*
if (points*.x < xMin)*
xMin = points*.x;*
if (points*.y > yMax)*
yMax = points*.y;*
if (points*.y < yMin)*
yMin = points*.y;*
}
float xSize = xMax - xMin;
float ySize = yMax - yMin;
Delaunay.Voronoi v = new Delaunay.Voronoi(points.ToList(), colors, new Rect(0, 0, xSize, ySize));

return v.HullPointsInOrder().ToArray();
}
I use this function before the rest of my script to re-arrange the points so the lines won’t interesect.
_*[1]: https://github.com/adamgit/Unity-delaunay*_