Convex Hull from Half Spaces (Planes)

[a-day-old-bagel]

I have a use case where my inputs are sets of half spaces, given by planes, and my outputs are convex polyhedra (one per set of half spaces).

To achieve this currently, I start with some bounding volume, and use trimByPlane to slice away the inverse of each half space in serial.

This is... not as fast as I expected, and seems to be the bottleneck in my use case. Is there a better way to produce such a convex polyhedron, given only oriented planes (half spaces) as input?

These are not large sets of half spaces, by the way. Only a dozen or so faces on the average polyhedron I'm producing, with an even smaller median face count.

If there were such a thing as a "batch" trim by plane, for example, I think it would solve my issue. I don't know if the trim operation is easily parallelized, though.

I've looked through the other issues and discussions, and some, such as issue 884, are adjacent to my question. So far, though, I'm not sure if I've seen a very clear answer. Perhaps I haven't read carefully enough, but I decided to just make an issue.

[elalish]

Indeed, we don't have a dedicated algorithm for this. What you're describing is basically a Nef polyhedron, so CGAL might do this well, given that's their native data structure.

Our Booleans do automatically batch, but trim by plane will not because it needs to evaluate the the size of the incoming mesh to know how large to make a safe cube to represent the half-space. If you know a bound on the size of your output object, you could intersect the cubes yourself as a batch.

[a-day-old-bagel]

Thanks, I'll try a custom batch of cubes and see if I can get a speedup.

Also sorry for making it an issue at first. I wasn't sure which to do in this case.