next »

[qMopey]

Start by constructing an initial tetrahedron out of your point set. Then for each face, loop over the remaining verts and assign them to a linked list. Each face has one linked list. Assign a vert to a linked list if it is in front of that face. These linked lists are the “conflict list”. They represent points the hull can expand to.

Then the main iteration loop picks a point in a conflict list, and expands the hull to this point. The point is removed from the list. Now remove any other conflict points that are now intersecting the expanded hull.

To expand the hull, find all faces that are facing the point you are expanding to (the conflict point). You can find these faces by starting on the face the linked list is attached to, and perform a depth first search on the half edge mesh structure. Keep track of all faces visited that face the conflict, to avoid visiting them twice. You now have a CCW ordered set of faces. Each time you find a face that is facing away from the conflict, record the edge in an array (more about this edge below). Since the DFS searches in a CCW wind, your edge array is the ordered set of horizon edges.

If you imagine the conflict point as a bright light shining on the hull, the horizon is the set of ordered edges that sit on the boundary between lit and shadow faces. A lit face is facing the conflict point. A shadow face is pointing away. The edge between two of these faces is a horizon edge.

Once the horizon is found, delete all lit faces. Loop over the horizon. For each horizon edge make a new triangular face and attach it to the conflict point. Then hook up the half edges of all the new faces with another loop over the horizon edges. The hull is now expanded.

Finally, loop over the new faces and look for coplanar pairs to merge. This is difficult and will take time to implement properly. Dirks qhull lecture explains face merging.

[qMopey]

I wrote that on my iphone 

[gimymblert]

Thanks

I'm mostly having problem with turning that into actual code:
- you have a random number of list (after the first 4)
- the number of list change over time?
How do that works with code where declaration of lists is fixed and prior to operation?
Basically what data structure and organization I'm supposed to have?

[qMopey]

You can gather scratch memory and size it for the worst case using Euler's Characteristic: https://en.wikipedia.org/wiki/Euler_characteristic

It says that V - E + F = 2. V is number of verts. F is number of faces. E is number of edges. This is true for all convex hulls in 3D.

Given an input array of vertices, say V is the number of verts, you can do:

E = V * 3 - 6 (three edges per triangle, worst case)
F = 2 * V - 4

And finally, assert V - E + F = 2.

This is all in Dirk's lecture: http://box2d.org/files/GDC2014/DirkGregorius_ImplementingQuickHull.pdf

You can make it easy for yourself to create conflict lists by using double linked lists like this:

Code:

struct QHVert
{
    Vertex v;
    int next;
    int prev;
};

Where next and prev are indices of vertices. Personally when I implement this stuff I use circular linked lists. It is just a matter of getting comfortable with data structures and book-keeping at this point

Then you can write code like:

Code:

if (InFront(face, vert))
{
    AddConflictVert(face.list, vert);
}

[gimymblert]

I don't have that of a low level problem lol
I'm programming in unity and c#, I don't need to reimplement list!

I'm using that dirk's paper too

It's more about the design of the loop and how code manage conflict list.

I mean it's not an object, I can't create a random number of it or destroy it

even determining which point goes to each list is obscure (obviously a dot product, but it's an hemisphere, a point can be one two triangle hemisphere).

[qMopey]

Treat each face as a plane. Test point against plane and check the signed distance. Positive is in front of plane, negative is behind. Put a list in each of your face class instances. I’m not sure which part you’re stuck on? Maybe you can write down some pseudo code to express your thoughts?

Edit: You are on the right track! Quick hull is just a very difficult algorithm to implement correctly

[gimymblert]

I think I'm dumb dumb

I think the solution is to create a temp class that hold a list and a reference to a face, then create instance of it as face are created, and delete them when a face is deleted