seblague / ear-clipping-triangulation Goto Github PK

Hello!

I've been using your code for my thesis project, and came across an edge case where triangulating the mesh for composite shape with holes fails. It happens when the very first hull point meets all the criteria to be the intersection for the hole's bridge point.

Code Error + Possible Fix

Here's the code that keeps failing (Triangulator.cs, line 161):

bool connectToThisDuplicateEdge = holeData.bridgePoint.y > potentialNewBridgeNode.Previous.Value.position.y;

When you are on the first run through the while (currentNode != null) loop, and potentialNewBridgeNode gets set to p0, there is no .Previous so it aborts with a null reference exception.

Based on my understanding of what's going on in the code, I changed it to this, and now everything seems to be working.

bool connectToThisDuplicateEdge = false;
if (potentialNewBridgeNode.Previous != null) {
      connectToThisDuplicateEdge = holeData.bridgePoint.y > potentialNewBridgeNode.Previous.Value.position.y;
}

Steps to Reproduce

The image below outlines a simple example that replicates the error. I want to create a composite shape that is rectangular, with a rectangular hole cut out of it. I have the following points, shown as vertices on the left and plotted on the graph in the center. The blue points represent the first shape in my shapeList, and the orange/red represents the second shape. I call (new CompositeShape(shapeList)).getMesh(). The red point marks the bridge point that connects the hole to the rest of the hull. Finally, GenerateVertices() gets called with the Polygon object on the right.

Hopefully this helps you figure out exactly what's going on. My fix seems to work fine for my use case, but I'm not 100% that it doesn't break under other circumstances.

Anyway, thanks for providing this code, along with a video tutorial! It's been super helpful.

I'm trying to make test mesh from 4 points and get this error:

Error triangulating mesh. Aborted.
UnityEngine.Debug:LogError(Object)
Sebastian.Geometry.Triangulator:Triangulate() (at Assets/Ear-Clipping-Triangulation/Triangulator.cs:72)
Sebastian.Geometry.CompositeShape:Process() (at Assets/Ear-Clipping-Triangulation/CompositeShape.cs:87)
Sebastian.Geometry.CompositeShape:GetMesh() (at Assets/Ear-Clipping-Triangulation/CompositeShape.cs:29)
TrianTest:Start() (at Assets/TrianTest.cs:29)

This is my code:

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

using Sebastian.Geometry;


public class TrianTest : MonoBehaviour {

    public MeshFilter meshFilter;
    public List<Shape> shapes = new List<Shape>();

    Shape basicShape = new Shape();

    void init(){
        shapes.Add(basicShape);
    }
	void Start () {

        init();

        addPointToShape(-1.0f, 0.0f);
	addPointToShape(1.0f, 0.0f);
        addPointToShape(1.0f, 2.0f);
        addPointToShape(-1.0f, 2.0f);

        CompositeShape compShape = new CompositeShape(shapes);
        meshFilter.mesh = compShape.GetMesh();
	}
	
    void addPointToShape(float newX, float newY) {
        basicShape.points.Add(new Vector3(newX, newY,0));
    }
}

The outer shape is:
List outerShapePoints = new List();
outerShapePoints.Add(new Vector3(0, 0, 0));
outerShapePoints.Add(new Vector3(0, 0, 1));
outerShapePoints.Add(new Vector3(1, 0, 1));
outerShapePoints.Add(new Vector3(1, 0, 0));

The two inner shapes are:
List shape = new List();
shape.Add(new Vector3(0.2f, 0, 0.2f));
shape.Add(new Vector3(0.2f, 0, 0.8f));
shape.Add(new Vector3(0.4f, 0, 0.8f));
shape.Add(new Vector3(0.4f, 0, 0.2f));
innerShapes.Add(shape);

shape = new List();
shape.Add(new Vector3(0.6f, 0, 0.2f));
shape.Add(new Vector3(0.6f, 0, 0.8f));
shape.Add(new Vector3(0.96f, 0, 0.8f));
shape.Add(new Vector3(0.8f, 0, 0.2f));
innerShapes.Add(shape);

It looks like this:

It will not be able to generate a mesh if you change the third vertex in the second inner shape to something like Vector3(0.98f, 0, 0.8f). It's working fine if you change the third coordinate to new Vector3(0.98f, 0, 0.79999f), so there might be some floating point precision issues going on somewhere?

I tried your code but it failed with an L shape like this

        points.Add(new Vector2(1, 0.25f));
        points.Add(new Vector2(1, 0));
        points.Add(new Vector2(0, 0));
        points.Add(new Vector2(0, 1));
        points.Add(new Vector2(0.25f, 1));
        points.Add(new Vector2(0.25f, 0.25f));
        points.Add(new Vector2(1, 0.25f));

Thank you very much SebLague for providing the scripts.
This is not an issue, just need your help.
As i am working on a project and in that i want to create a mesh from the given list of points such that all the exterior points got connected and we get the proper mesh. And we do not need to include any hole concept as I was going through your triangulator script which has all the Hole thing included.
I am not that much experienced in programming so i need your help in generating that mesh which connect all the exterior points and create triangles so that the mesh get visible.