Haskell-Things / Haskell-Things/ImplicitCAD

(Polyhedral) convex hulls for collections of points

Open
#270 0 comments 0 reactions 0 assignees View on GitHub
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);
}
```
![hull-pyramid](https://user-images.githubusercontent.com/3887189/85812950-d5104c00-b716-11ea-87fc-d263b2b83ab3.png)

(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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.