3d Convex Hull #489
3d Convex Hull #489
Conversation
Codecov ReportPatch coverage:
Additional details and impacted files@@ Coverage Diff @@
## master #489 +/- ##
==========================================
- Coverage 90.35% 90.27% -0.09%
==========================================
Files 35 35
Lines 4396 4410 +14
==========================================
+ Hits 3972 3981 +9
- Misses 424 429 +5
☔ View full report in Codecov by Sentry. |
|
RE: libraries this one is the top result, and seems like it'd be easy to vendor and use if we want to just go the dependency route. It's an implementation of QuickHull which I believe is better than what I have here. It also supports multithreading but via OMP, maybe forking and adapting it to Manifold's flexible OMP/TBB use via thrust would be worthwhile. There are a couple papers that say they have something faster than QHull but I just looked at summaries/abstracts last night. This was a good experience in imperative-izing and general C++ practice anyways 😅. This is the other article about 3d hull algorithms with example implementations that I meant to link before (deleted wrong paste for 2d). While I'm listing options, here are some simpler to consume quickhull implementations that I've come across for reference: |
|
I'll go ahead try out the header quickhulls implementations that I linked above on then. Not necessary to start with I don't think, but might be interesting to try out a strategy like described here in this video and article in the future. I'm curious how this and another similar paper I've seen along the way actually play out with the kind of inputs we'd have in Manifold, since many of the benchmarks that are shown off in these things are clouds rather than separate sphere meshes (that are already hollow) for example. |
|
So far out of the non-qhull options,
I guess I'm going to actually have to try edit: Actually, when using |
|
After trying the above mentioned libs
8000
it seems like Akuukka's QuickHull implementation is the way to go, with very few lines of code and |
|
The time to hull I mentioned before was actually an over-estimate since it included the time to get the huge mesh and export it 😅, here is a rough idea of scaling over vertex count. TEST(Manifold, TictacBench) {
const float tictacRad = 100;
const float tictacHeight = 500;
const float tictacMid = tictacHeight - 2 * tictacRad;
const std::vector<int> tictacSegs{36, 360, 720, 1000, 2000,
3000, 4000, 5000, 6000};
for (int seg : tictacSegs) {
auto sphere = Manifold::Sphere(tictacRad, seg);
auto spheres = sphere + sphere.Translate({0, 0, tictacMid});
auto t0 = std::chrono::system_clock::now();
auto tictac = spheres.Hull();
double ms = std::chrono::duration_cast<std::chrono::milliseconds>(
std::chrono::system_clock::now() - t0)
.count();
std::printf("segs = %i; verts = %i; time = %f\n", seg, spheres.NumVert(),
ms);
}
} |
src/manifold/src/manifold.cpp
Outdated
|
|
||
| Manifold Manifold::Hull() const { | ||
| auto mesh = GetMeshGL(); |
There was a problem hiding this comment.
So this is to get 1:1 properties to positions? Of course that means we'll get duplicate positions with different properties, so it's going to be basically random which properties end up in the output. Also, it'll be hard to make sense of them without an originalID, since some of those properties might mean different things. Actually it's worse that than: you could end up with a face interpolating UV coordinates into vertex colors or something, since there's no guarantee the verts are from the same input object.
I wonder if we should just remove properties from the Hull entirely and do just geometry for this reason. I can't think of a way to make it sensical otherwise.
There was a problem hiding this comment.
I wasn't really sure myself since I don't know much about theesh properties business. I just did it this way to try and preserve properties as you said, hoping that you or pca could point out what more I should be preserving (or not). I did consider triangles ending up with weirdly disparate properties as a possibility, but I don't know/understand what is done with properties during booleans either.
There was a problem hiding this comment.
The nice thing about Booleans is we can guarantee a bunch of things: every result triangle is a subset of exactly one input triangle, so it will only every interpolate properties from that triangle. Our decimator is also aware, so it won't merge triangles that don't come from the same original triangle.
Each triangle in a hull is either an input triangle, or a new triangle. I suppose we could try to maintain properties (and faceIDs) for input triangles, but we'd have no choice but to drop them for new triangles. Personally I think it sounds like more trouble than it's worth.
There was a problem hiding this comment.
Ok, sounds good 👍. I've stripped out all of the properties stuff and just get the vertices via GetMesh.
|
I'll follow up soon with some bindings updates (2d and 3d hull). |
Add convex hull methods to Manifold using newly vendored https://github.com/akuukka/quickhull
This adds a 3d convex hull operation to Manifold. Implementation is a port of what I have in OCADml, which is a port of BOSL2. I've made some effort to get the performance reasonable (for this algorithm anyway, there may be smarter ones out there). From my rough measurement, the vast majority of the time is spent on the
DistanceToPlaneoperation, so I'm not sure what can be wrung out.I've set it up to try and preserve some properties info, but I'm not too familiar with that API, so I'm hoping that what I've missed can get filled in with review.