(Polyhedral) convex hulls for collections of points

[kwshi]

I think I saw in various other discussions (e.g. this one) that ImplicitCAD doesn't yet support arbitrary convex hull operations, because no one has quite figured out a good way to represent convex hulls using signed distance fields (the "implicit function" representation of solids used by ImplicitCAD, as opposed to the more traditional triangle/polygon "boundary" representation used by CGAL/OpenSCAD, etc.).

Even then, polyhedral convex hulls have a known solution, since in that context traditional polygon-based/B-rep convex hull algorithms can be used, and the final result is merely an intersection of half-planes. In a lot of my projects, I only use convex hulls on polyhedral shapes anyway (for things like simple bevels and chamfers). For those fairly common (80%) use cases, I think it's worth having a polyhedralHull function that generates the convex hull of a set of points, providing partial support for a much-missed feature from OpenSCAD.

In fact, a polyhedral hull is in several cases even more versatile than OpenSCAD's hull feature. Suppose, for example, you want to construct a square pyramid. OpenSCAD's hull can only act on 3D objects, not "degenerate" shapes like planes or points, which means the closest you can get to a square pyramid using hull is by making the base square and tip extremely small, but never zero:

epsilon = 0.1;
hull() {
  linear_extrude(height=epsilon)
    square([2, 2], center=true);
  linear_extrude(height=1)
    square(epsilon * [1, 1], center=true);
}

(Yes, you can make epsilon much smaller, like 1e-4, to make it "practically" perfect, but the underlying model will always be imperfect to a small degree, and tiny dimensions and imprecisions like these can introduce numerical errors all over the place--not an ideal solution, and definitely not a satisfying one.)

The next best solution is to manually construct its B-rep:

polyhedron(
  [
    [1, 1, 0],
    [-1, 1, 0],
    [-1, -1, 0],
    [1, -1, 0],
    [0, 0, 1],
  ], 
  [
    [0, 1, 2, 3],
    [0, 4, 1],
    [1, 4, 2],
    [2, 4, 3],
    [3, 4, 0],
  ]
);

which is perfect, but quite low-level.

Having a polyhedral hull would make it much simpler, since all you need to specify are the vertices without worrying about faces and their orientation:

polyhedralHull([[1, 1, 0], [-1, 1, 0], [-1, -1, 0], [1, -1, 0], [0, 0, 1]]);

So there is a good argument that such a feature would be useful and even better than existing features in other tools.