Taking set of 3d points, and computing convex hull formed by triangles.

What I have so far (as a candidate solution; doesn't need to be more optimal), based on quick-hull ideas:

fun convex_hull(points) { // cannot form a hull if (points.length < 3) return [] // trivial; degenerate hull formed by points if (points.length == 3) return [points, [points[0], points[2], points[1]]] sort points lexicographically along axis (1, 0, 0) p0 = points[0] p1 = points[sorted.length - 1] p2 = point furthest from line containing p0, p1 fun recurse(points, p0, p1, p2) { n = normal(p0, p1, p2) discard p from points where p in [p0, p1, p2] or (p-p0) dot n < 0 if (points.length == 0) return [p0, p1, p2] else { sort points lexicographically along axis n return recurse(points, p0, p1, p3) concat recurse(points, p1, p2, p3) concat recurse(points, p2, p0, p3) } candidates = recurse(points, p0, p1, p2) concat recurse(points, p0, p2, p1) // 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).

**Edited by luca-deltodesco, 27 June 2012 - 05:32 PM.**