Haskell-Things / Haskell-Things/ImplicitCAD
(Polyhedral) convex hulls for collections of points
- Dominant language
- JavaScript
- Stars
- 1.6k
- Forks
- 148
- PR merge metrics
- No merged PRs in 30d
Description
I think I saw in various other discussions (e.g. [this one](https://github.com/colah/ImplicitCAD/issues/169)) 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:
```openscad
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:
```openscad
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:
```openscad
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.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.