3D Convex Hull

[pca006132]

I was trying to port some tests from OpenSCAD to python for more test cases and performance check. I'm currently looking at https://gist.github.com/ochafik/2db96400e3c1f73558fcede990b8a355 . It seems that quite a lot of the more complicated cases are using hull(), so I guess it would be desirable to implement it.

Not sure if we should implement it by ourselves or use an existing implementation. I saw a header only library here: https://github.com/leomccormack/convhull_3d/blob/master/convhull_3d.h and can probably be parallelized if needed.

[elalish]

Maybe; I wouldn't say OpenSCAD's test cases are the best reason to implement a feature; I don't think I've ever used hull in OpenSCAD to design anything. I'm also taking a somewhat unusual approach to computational geometry in this library, in an attempt to get robustness without an exact geometry kernel. Therefore I'd like to be a bit careful about what other algorithms we pull in.

[pca006132]

I've used hull before in some of my designs, but they are mainly for chamfer which can be done via warp now. It seems that what those test cases use hull for can be implemented via warp/refine or sweep, so we don't have to implement hull right now.

Anyway maybe we should leave this open and revisit this later when we want to implement the OpenSCAD transpiler? I think we won't be far from that :)

[elalish]

I'm going to move this to a discussion for now. I would like to have an OpenSCAD transpiler, but I think it's okay if it doesn't support a few of their less-common operations. Minkowski comes to mind as well.

[pca006132]

I found that it is common to use hull to merge parts and make the transition smooth, e.g. joining a cylinder with a cube to make something like a D shape. It is possible to do it without hull, but it is not very natural. I guess it is still desirable to have this implemented.

I think the algorithm above should not change the manifoldness property, considering it should only return a manifold constructed from a subset of the original vertex set? Maybe we need to merge vertices that are closer than precision or something.