// remove any triangles not part of hull
discard (p0, p1, p2) from candidates where exists p in points s.t (p - p0) dot normal (p0, p1, p2) > 0
// remove any degenerate triangles (still allowing 0-area triangles).
discard (p0, p1, p2) from candidates where p0 == p1 || p0 == p2 || p1 == p2
return candidates;
}
Now, this works for some test cases (including simple (perfect) boxes) in that it gives me a set of triangles which as a whole can unify to give the convex hull, but i'm interested in how you can take this further to produce a minimal set of triangles as many of the triangles returned by this implementation will be overlapping.
I imagine that without drastically changing the algorithm, you could identify those triangles that are coplanar, collect vertices, order by angle in plane and do a trivial triangulation as a fan. But I would worry about numerical issues with determining coplanar planes in the general case here.
I've so far avoided that I can tell numerical issues by doing a lexicographical sort (which in the general case involves computing a tangent and bitangent for the given axis to additionally project onto for the sorting if projections on primary axis are equal).
Why don't you triangulate while at it?
I don't understand every aspect of your algorithm, but it seems similar to the algo I had in mind (though I only implemented a 2D version).
if you find a candidate triangle, why don't you just use the indices of them to fill the triangle list on the spot?
Maybe my algo is different, it's something like this:
RecursiveFunction(triangle_normal, current_edge) // edges are defined by the two end vertex indices, and should have a consistent vertex winding (CCW)
{
calculate current_edge_vector using the consistent winding;
Perp_edge_vector = normalize( current_edge_vector cross triangle_normal);
// this vector points away from the triangle, perpendicular to the current edge and perpendicular to the triangle_normal
loop through all the vertices
{
Perp_vector_new = normalize( current_edge_vector cross potential_triangle_normal); // I'm not sure about signs here
Find next vertex:
with the biggest dot product between Perp_edge_vector and Perp_vector_new
} // no need to do extra checks, if the first triangle is selected correctly, only convex edges can occur now.
if( triangle is not constructed yet ) // ATM i can only think of looping through all already constructed triangles to check
// there's got to be a better way
{ With the found vertex and the current edge, build a new triangle, and add the vertex indices to the triangle list;
call RecursiveFunction(new_triangle_normal, third_edge);
// one of the edges of the new_triangle is the same as the current_edge fed to recursiveFunction. So no need to call the function for the third neighbour triangle
}
}
......
BuildConvexHull()
{
Get the first triangle: the first three vertices on one of the axes // I'm not sure about this one....
Store indices in the triangle list;
call RecursiveFunction(first_triangle_normal, first_edge):
call RecursiveFunction(first_triangle_normal, second_edge):
call RecursiveFunction(first_triangle_normal, third_edge):
// maybe you don't even have to call the third one, because I think the convex hull will be complete by this time
}
No sorting in this algo, except for the rather trivial one to fist the first triangle.
Since the Quickhull algorithm iteratively improves an inner approximation of the convex hull you need to calculate the normals of faces of the inner approximation and you can store the points of those faces too if you want to.
But if you found something that works I guess you should stick to that.
