oskarsigvardsson/unity-quickhull

An implementation in Unity of the Quickhull algorithm for generating 3D convex hulls

unity-quickhull's Issues

Non-coplanar points being identified as coplanar

I have the following point set:

a = (-0.125, 0.125, -0.125)
b = (-0.149, 0.125, -0.125)
c = (-0.125, 0.125, -0.192)
d = (-0.125, 0.0, -0.125)

When finding the initial points for the hull generation, these points are identified as coplanar, so the generation fails.

The problem probably comes from the input point coordinates being smaller than 1, so the cross product becomes smaller and smaller (eventually they become smaller than epsilon).

Maybe this could be fixed by taking the normalized vector after the cross product (or choose a different method to calculate if points are coplanar)?
(I haven't checked if this solution is actually correct, but it seems to be working)

bool AreCoplanar(Vector3 a, Vector3 b, Vector3 c, Vector3 d)
{
    var n1 = Cross(c - a, c - b).normalized;
    var n2 = Cross(d - a, d - b).normalized;

    return AreCollinear(Vector3.zero, n1, n2);
}

The given key was not present in the dictionary

Hello! First of all I want to thank you for this code snippet which I have found very useful. I just wanted to report an error I have been running into when attempting to generate a hull for a specific mesh -

GK.ConvexHullCalculator.FindHorizon (System.Collections.Generic.List`1[T] points, UnityEngine.Vector3 point, System.Int32 fi, GK.ConvexHullCalculator+Face face) (at ConvexHullCalculator.cs:666)

I think this may be related to points being too close to one another, so I was messing around with the epsilon setting. But decreasing the epsilon value actually led to many more errors of the same kind, which I was not expecting.

Is it possible to increase number of faces?

Is it possible to increase the resolution, so that the hull has more faces?

it can't work when all the points are on the plane

generate convex hull fail. I run the code on a plane mesh.

Generating convex collider for box mesh skips one vertex

I understand that generating a convex collider for a box mesh is pointless, but its running runtime on pre-made and dynamic objects unanimously.

The box in question is ProBuilder generated box with a size of [6.05, 0.16, 6.59].

I would export the mesh and put it here, but I have no idea where ProBuilder meshes are stored at :(

Besides this minor issue, no issues found. This lib is amazing! Thanks for sharing it with the community!

EDIT: The missing vertex is not actually missing, it is rather put inside the resulting vertices array as a duplicate of a different vertex. This effectively renders it useless though, so its as good as missing.

It has error in this model

input data(X,Y,Z):
-0.06270732 , 0.03174151 , 0.025
-0.06097341 , 0.03174151 , 0.025
-0.06270732 , 0.03174151 , 0
-0.06097341 , 0.03174151 , 0
-0.05804581 , 0.03174151 , 0.025
0.0850401 , 0.03174151 , 0.025
-0.05804581 , 0.03174151 , 0
0.0850401 , 0.03174151 , 0
-0.06874499 , -0.05041299 , 0.025
-0.06874499 , 0.03174151 , 0.025
-0.06874499 , -0.05041299 , 0
-0.06874499 , 0.03174151 , 0
0.0850401 , -0.05041299 , 0.025
0.0850401 , -0.05041299 , 0
-0.06563492 , 0.03174151 , 0
-0.06563492 , 0.03174151 , 0.025
-0.06558505 , 0.03136266 , 0.025
-0.06520618 , 0.03070645 , 0.025
-0.06543881 , 0.03100961 , 0.025
-0.06092353 , 0.03136266 , 0.025
-0.06313606 , 0.03070645 , 0.025
-0.0607773 , 0.03100961 , 0.025
-0.06290343 , 0.03100961 , 0.025
-0.06275719 , 0.03136266 , 0.025
-0.05809569 , 0.03136266 , 0.025
-0.05824192 , 0.03100961 , 0.025
-0.06417112 , 0.03027771 , 0.025
-0.06454998 , 0.03032759 , 0.025
-0.06490302 , 0.03047382 , 0.025
-0.05847454 , 0.03070645 , 0.025
-0.05877771 , 0.03047382 , 0.025
-0.05913075 , 0.03032759 , 0.025
-0.05950961 , 0.03027771 , 0.025
-0.05988847 , 0.03032759 , 0.025
-0.06343922 , 0.03047382 , 0.025
-0.06379226 , 0.03032759 , 0.025
-0.06054467 , 0.03070645 , 0.025
-0.06024151 , 0.03047382 , 0.025
-0.05824192 , 0.03100961 , 0
-0.05809569 , 0.03136266 , 0
-0.06290343 , 0.03100961 , 0
-0.06313606 , 0.03070645 , 0
-0.06343922 , 0.03047382 , 0
-0.06275719 , 0.03136266 , 0
-0.06092353 , 0.03136266 , 0
-0.0607773 , 0.03100961 , 0
-0.06054467 , 0.03070645 , 0
-0.05913075 , 0.03032759 , 0
-0.05877771 , 0.03047382 , 0
-0.05847454 , 0.03070645 , 0
-0.06558505 , 0.03136266 , 0
-0.06543881 , 0.03100961 , 0
-0.06520618 , 0.03070645 , 0
-0.06490302 , 0.03047382 , 0
-0.06454998 , 0.03032759 , 0
-0.06417112 , 0.03027771 , 0
-0.06379226 , 0.03032759 , 0
-0.06024151 , 0.03047382 , 0
-0.05988847 , 0.03032759 , 0
-0.05950961 , 0.03027771 , 0

Passing in a mesh with 30000 coplanar vertices causes a very long hang

This is quite the edge case, but there is a quadruple-for loop in FindInitialHullIndices each vertex that can cause programs to stall. It's a O(n^4) algorithm.