The calculation of the convex hull never ends

[SergeyBaryshev]

Hello @RossNordby !
While playing with generating of random points for convex hull, i found a strange bug. Usually there are two results: successful constructed shape, or throwing some of errors like "Point set must have volume" or "Point set is degenerate; convex hulls must have volume" etc. But there is another unexpected way - the function never returns, eternal internal execution.

This code for test:

    internal static string TestConvexHull()
    {
        List<int> indices = new List<int>();
        List<BEPUutilities.Vector3> vertices = new List<BEPUutilities.Vector3>();
        List<BEPUutilities.Vector3> points = InvalidMesh();
        BEPUutilities.ConvexHullHelper.ConvexHullHelper.GetConvexHull(points, indices, vertices);
        BEPUutilities.ConvexHullHelper.ConvexHullShape chs = new BEPUutilities.ConvexHullHelper.ConvexHullShape(points);
        return $"{points.Count} / {indices.Count} / {vertices.Count}";
    }

    internal static List<Vector3> InvalidMesh(){
        List<Vector3> list1 = new List<Vector3>();
	list1.Add(New BEPUutilities.Vector3(0.146501064F, 0.04575193F, 0.0469997227F));
	list1.Add(New BEPUutilities.Vector3(0.0217511654F, 0.0557500124F, 0.04774934F));
	list1.Add(New BEPUutilities.Vector3(0.146001339F, 0.0465019941F, -0.06300023F));
	list1.Add(New BEPUutilities.Vector3(0.146001339F, 0.0465019941F, -0.06300023F));
	list1.Add(New BEPUutilities.Vector3(0.0217511654F, 0.0557500124F, 0.04774934F));
	list1.Add(New BEPUutilities.Vector3(0.0212495327F, 0.0565000772F, -0.0622506142F));
	list1.Add(New BEPUutilities.Vector3(0.1454997F, -0.01574862F, -0.0632499158F));
	list1.Add(New BEPUutilities.Vector3(-0.005499363F, -0.0450005531F, -0.06275058F));
	list1.Add(New BEPUutilities.Vector3(0.146000624F, -0.0164988041F, 0.04649937F));
	list1.Add(New BEPUutilities.Vector3(0.146000624F, -0.0164988041F, 0.04649937F));
	list1.Add(New BEPUutilities.Vector3(-0.005499363F, -0.0450005531F, -0.06275058F));
	list1.Add(New BEPUutilities.Vector3(-0.005000353F, -0.0457505F, 0.0472494364F));
	list1.Add(New BEPUutilities.Vector3(-0.005499363F, -0.0450005531F, -0.06275058F));
	list1.Add(New BEPUutilities.Vector3(0.1454997F, -0.01574862F, -0.0632499158F));
	list1.Add(New BEPUutilities.Vector3(0.0212495327F, 0.0565000772F, -0.0622506142F));
	list1.Add(New BEPUutilities.Vector3(0.0212495327F, 0.0565000772F, -0.0622506142F));
	list1.Add(New BEPUutilities.Vector3(0.1454997F, -0.01574862F, -0.0632499158F));
	list1.Add(New BEPUutilities.Vector3(0.146001339F, 0.0465019941F, -0.06300023F));
	list1.Add(New BEPUutilities.Vector3(0.146501064F, 0.04575193F, 0.0469997227F));
	list1.Add(New BEPUutilities.Vector3(0.146000624F, -0.0164988041F, 0.04649937F));
	list1.Add(New BEPUutilities.Vector3(0.0217511654F, 0.0557500124F, 0.04774934F));
	list1.Add(New BEPUutilities.Vector3(0.0217511654F, 0.0557500124F, 0.04774934F));
	list1.Add(New BEPUutilities.Vector3(0.146000624F, -0.0164988041F, 0.04649937F));
	list1.Add(New BEPUutilities.Vector3(-0.005000353F, -0.0457505F, 0.0472494364F));
	list1.Add(New BEPUutilities.Vector3(0.146001339F, 0.0465019941F, -0.06300023F));
	list1.Add(New BEPUutilities.Vector3(0.1454997F, -0.01574862F, -0.0632499158F));
	list1.Add(New BEPUutilities.Vector3(0.146501064F, 0.04575193F, 0.0469997227F));
	list1.Add(New BEPUutilities.Vector3(0.146501064F, 0.04575193F, 0.0469997227F));
	list1.Add(New BEPUutilities.Vector3(0.1454997F, -0.01574862F, -0.0632499158F));
	list1.Add(New BEPUutilities.Vector3(0.146000624F, -0.0164988041F, 0.04649937F));
	list1.Add(New BEPUutilities.Vector3(-0.005000353F, -0.0457505F, 0.0472494364F));
	list1.Add(New BEPUutilities.Vector3(-0.005499363F, -0.0450005531F, -0.06275058F));
	list1.Add(New BEPUutilities.Vector3(0.0217511654F, 0.0557500124F, 0.04774934F));
	list1.Add(New BEPUutilities.Vector3(0.0217511654F, 0.0557500124F, 0.04774934F));
	list1.Add(New BEPUutilities.Vector3(-0.005499363F, -0.0450005531F, -0.06275058F));
	list1.Add(New BEPUutilities.Vector3(0.0212495327F, 0.0565000772F, -0.0622506142F));
        return list1;
    }

Both "GetConvexHull" and constructor of "ConvexHullShape" will hanging when calling "TestConvexHull".

[RossNordby]

Appears to be numerical error; it is getting stuck unable to include remaining outside points in the hull.

You can technically get it to pass by changing this to >= instead of >: https://github.com/bepu/bepuphysics1/blob/master/BEPUutilities/ConvexHullHelper.cs#L159

But it's been so long that I cannot immediately say with confidence what other consequences that will have.

A perhaps more reliable workaround would be to call ConvexHullHelper.RemoveRedundantPoints(points, threshold); prior to creating the convex hull. I'd advise simplifying input geometry in general before creating convex hulls- performance is proportional to final hull point count.

I'm short on time for the foreseeable future (focusing on v2 stuff), so I won't be able to dig into this. If you happen to figure out a deeper/better fix, I would take a PR.

[SergeyBaryshev]

It's all very odd!
Originally this code was written in VB.NET, therefore it was translated into C#. Furthermore C# version is NOT hanging when creating convex hull, but VB.NET it does. Below I provide both identical versions of the code in two languages, besides I have reduced the number of points at which this problem occurs.

VB:

Friend Shared Function TestConvexHull() As String
	Dim indices As New List(Of Integer), vertices As New List(Of BEPUutilities.Vector3)
	Dim points As List(Of BEPUutilities.Vector3) = InvalidMesh()
	BEPUutilities.ConvexHullHelper.GetConvexHull(points, indices, vertices)
	Dim chs As New BEPUphysics.CollisionShapes.ConvexShapes.ConvexHullShape(points)
	Return $"{points.Count} / {indices.Count} / {chs.Vertices.Count}"
End Function

Friend Shared Function InvalidMesh() As List(Of BEPUutilities.Vector3)
	Return New List(Of BEPUutilities.Vector3) From {
		New BEPUutilities.Vector3(0.146000624F, -0.0164988041F, 0.04649937F),
		New BEPUutilities.Vector3(-0.005000353F, -0.0457505F, 0.0472494364F),
		New BEPUutilities.Vector3(0.146501064F, 0.04575193F, 0.0469997227F),
		New BEPUutilities.Vector3(0.146000624F, -0.0164988041F, 0.04649937F),
		New BEPUutilities.Vector3(-0.005000353F, -0.0457505F, 0.0472494364F),
		New BEPUutilities.Vector3(0.0217511654F, 0.0557500124F, 0.04774934F),
		New BEPUutilities.Vector3(-0.005499363F, -0.0450005531F, -0.06275058F),
		New BEPUutilities.Vector3(0.0212495327F, 0.0565000772F, -0.0622506142F)}
End Function

C#

internal static string TestConvexHull()
{
	List<int> indices = new List<int>();
	List<BEPUutilities.Vector3> vertices = new List<BEPUutilities.Vector3>();
	List<BEPUutilities.Vector3> points = InvalidMesh();
	BEPUutilities.ConvexHullHelper.GetConvexHull(points, indices, vertices);
	BEPUphysics.CollisionShapes.ConvexShapes.ConvexHullShape chs = new BEPUphysics.CollisionShapes.ConvexShapes.ConvexHullShape(points);
	return $"{points.Count} / {indices.Count} / {chs.Vertices.Count}";
}

internal static List<Vector3> InvalidMesh()
{
	return new List<Vector3>
	{
		new BEPUutilities.Vector3(0.146000624F, -0.0164988041F, 0.04649937F),
		new BEPUutilities.Vector3(-0.005000353F, -0.0457505F, 0.0472494364F),
		new BEPUutilities.Vector3(0.146501064F, 0.04575193F, 0.0469997227F),
		new BEPUutilities.Vector3(0.146000624F, -0.0164988041F, 0.04649937F),
		new BEPUutilities.Vector3(-0.005000353F, -0.0457505F, 0.0472494364F),
		new BEPUutilities.Vector3(0.0217511654F, 0.0557500124F, 0.04774934F),
		new BEPUutilities.Vector3(-0.005499363F, -0.0450005531F, -0.06275058F),
		new BEPUutilities.Vector3(0.0212495327F, 0.0565000772F, -0.0622506142F)
	};
}

Or is there something I don't know? Why is there a difference in calculations?

[RossNordby]

I see it still happen on the new C# snippet, for the same reasons as before. The same workarounds also work.