Optimize convex hull algorithm

[pca006132]

Outline

Optimize the current convex hull algorithm to improve robustness and efficiency.

Details

The current implementation (quickhull) have cases in which it cannot handle, and will resort to deleting those problematic points. We should try to look at alternative algorithms or improve on existing algorithm to make it more stable.

Also, we should try to perform parallelization to optimize convex hull performance.

Expected Outcome

A faster and/or more robust convex hull implementation

Project Properties

Skills

• C++
• Knowledge about algorithms
• Knowledge about graph data structure.

Difficulty

• Medium to hard.

Size

• Medium to long

Additional Information

• Potential mentor(s): @zalo @pca006132
• Organization website: https://manifoldcad.org/
• Communication channels: https://github.com/elalish/manifold/discussions

[MJ2021]

Hi @pca006132 I am interested in this project and would like to know more about this so can you provide some information like what is expected out of this and what are the current algorithms ?
Thanks

[pca006132]

We expect some performance improvement and better robustness, by either changing to another algorithm or optimizing the existing one. The current algorithm we use is quickhull (https://github.com/akuukka/quickhull).

[MJ2021]

So I guess there are other algorithms available for this so would you recommend to study those algorithms first or understand the currently implemented algorithm and try to optimize it ?

[pca006132]

Well, there are multiple approaches, I would suggest you to try multiple algorithms, evaluate their pros and cons, and then choose the promising ones to study them. You can also study the currently used algorithm and try to optimize it.

[elalish]

And to be clear, we aren't necessarily expecting you to write an algorithm from scratch - ideally just find the best open source one and update our dependency or fork it for our purposes. I think if you search our issues/discussions you'll find a few people have mentioned as good alternatives.

[MJ2021]

Oh nice I would look upon some algorithms
Thanks

[zalo]

My starting recommendation would be to try out the one in the VHACD implementation, which has been adapted from Julio Jerez's Newton Physics Engine, and has gone through several iterations optimizing for speed and robustness:
https://github.com/kmammou/v-hacd/blob/master/include/VHACD.h#L2321

[MJ2021]

Sure I will look into this code and see how it can be implemented

[MJ2021]

@zalo I was trying to understand the code in the VHACD implementation but I am facing a bit difficulty in that code because it is an 8500 line code with very few comments so is there a documentation available to help understand better ?
Also are there any resources available to study convex hull, quick hull so that I can understand the problem statement better ?

[pca006132]

I think you should first just try them out, run the convex hull on different meshes. Understanding the algorithm can be hard and we are not requiring that in this project.

I think the implementation VHACD uses is https://github.com/MADEAPPS/newton-dynamics/tree/master/newton-4.00/sdk/dCore ? Seems nicely written with some comments, but I think this still requires quite a bit of time to understand.

[zalo]

I had something more like this in mind, where the original VHACD.h was imported into manifold's project, and its functions are called as a separate wrapper function (like the one here, which is Hull2): zalo/manifold@9c72757

Initial benchmarks with VHACD's hull appear to be slower, but I think there's some funny pathological case happening in its algorithm... or perhaps it's just faster for approximate convex hulls, and slower for exact ones 🤔

There are several dozen versions of Stan Melax's Implementation of the Quickhull Algorithm:
Stan Melax's Original Convex Hull Algorithm: https://github.com/melax/sandbox/blob/master/include/hull.h
Or an updated one found in PhysX: https://github.com/NVIDIAGameWorks/PhysX-3.4/blob/master/APEX_1.4/shared/general/stan_hull/src/StanHull.cpp
Or the variant here: https://github.com/hunter-packages/stanhull
Or the version found in Bullet: https://github.com/bulletphysics/bullet3/blob/master/Extras/ConvexDecomposition/cd_hull.cpp#L2709

Likewise, Valve programmer Dirk Gregorius did a presentation on QuickHull here:
https://gdcvault.com/play/1020606/Physics-for-Game-Programmers Presentation PDF Here

EDIT: Just added Stan's Original Quickhull to the comparison
The results are not looking good for the alternative implementations in terms of speed or accuracy 😅

For the TicTac test:
Current Manifold Implementation: 4s
Original Stan Melax Implementation: 18s (Incorrect Hull)
VHACD Implementation: 1073s

[zalo]

After doing a bit more profiling on the Single-Threaded TicTac Test (which takes 4s on my machine), it seems like the ConvexHull part only takes 580ms!

From this, the biggest speedup would come from having the convex hull implementation share its half-edge datastructure with manifold, since recreating that takes 630ms, which is longer than the convex hull calculation itself!

EDIT: After figuring out how to get TBB working again on Windows, these are the multithreaded numbers

It seems like sharing the halfedges will be less beneficial (but still fairly useful).

About 30% of the convex hull time is spent in here: https://github.com/akuukka/quickhull/blob/1ffbc6f884ea1da89e104a5996cf8a726db673d5/QuickHull.cpp#L271-L286
So finding a way to parallelize this (especially, addPointToFace, which takes up 22% of the overall time) would yield significant benefits too...

[pca006132]

VHACD Implementation: 1073s

Wow, not expecting this to be that slow comparing with quickhull.

[Kushal-Shah-03]

Hello @pca006132 and @zalo , I wanted to know what sort of improvements are expected in the algorithm, as stated in the description, we not only have to improve efficiency but we also have to consider the cases where the quickhull algorithm suffers, so I wanted to understand what parameters to focus on while selecting the base algorithm. For example is it to prioritize handling the cases like Collinear points or Proximity, where the quickhull algorithm is known to suffer or do we priorities the efficiency over it? I feel a clarity on what parameters should be prioritized would help in determining a suitable algorithm that can be used as a base and then it can be tweaked further for optimizations.

Also I was going through, a previous post on parallelization and found them using the TicTacTest, and from what I could find on VHACD, it performs poorly on less complex hulls, due to the number of hierarchies it accounts for, and was wondering what level did you run it on?, and we can maybe try tweaking the number of circular segments in the Test (when compring with quickhull) as well to try comparing for more complex hull? To see if there are certain conditions where we can use the VHACD over quickhull.

PS: I recently finished a course on Computer Graphics and was deeply fascinated by the concepts, I was also looking into the documentation of Open3D module for another project, that's where I ran into the quickhull algorithm, I read about it's implemenation and working, and thus was interested in this project. I am particulary new to OpenSource, and my inclination to the field of Computer Graphics motivated me to attempt this project. In the Graphics course, we explored some fundamentals of Ray Tracing like Radiometry and Reflection Equations, Texture Mapping, etc, and optimization techniques, like BVH, Monte Carlo Estimation and Light Sampling, We also expored some aspects of Rasterization, During the course I also worked with Blender and OpenGL. I wanted to know if there's some other project that you would recommend given these. I was considering the "Implement 3D mesh offset", because I had read about minkowski sum and it's implementation, but was unsure about attempting it, because of the project length given my less experience with OpenSource.

[pca006132]

@Kushal-Shah-03 To be frank, the answer to this question is "I don't know". For example, we know that quickhull will output a warning message and drop the point when it fails to solve horizon edge, but so far no one looked into what is the implication of that --- will it make the convex hull invalid, or is the result still epsilon-valid? Can we make the convex hull used in VHACD faster and comparable with quickhull? What can we do to optimize quickhull further?

I think this project is more like, play with different convex hull implementations, try to understand why some of them fail in some cases, and dig into the low level stuff to try to optimize them. Optimization is the most probable outcome for this project, we are not expecting contributors to vastly improve the algorithm in a few weeks.

It is nice that you also consider 3D mesh offset. It is not easy: minkowski is slow and we want to avoid it, but other approaches either use voxel (which we want to avoid) or are vaguely described by some paper that missed some important detail. But on the other hand it can also be fun if you are into coming up with new ideas. I think it is fine to not have too much experience with open source, GSoC exists to bring students into open source. I think it should be fine if you are able to (vaguely) understand what we were talking about in elalish/manifold#192. Feel free to ask us any questions.

[helloboyxxx]

Hi, @pca006132 and @zalo. I am a junior college student in UIUC. I just found this project from GSoC. It really attracts me as it is related to the computational geometry course I have taken. I explored some convex hull algorithms in the two-dimensional cases, including the Jarvis March's selection hull, the Graham's scan algorithm, the "three penny algorithm", and touched on Timothy Chan's algorithm. They are all in 2D, and we assumed general positions previously. I find it interesting to read these algorithms, but I was also suffering in finding some meaning out from it. Now that this project exists, I think it will be fun to challenge it this summer!

I will try to dive into some of these resources mentioned above in the coming few days. Before, that I would like to play with some tests just as @zalo mentioned above. Where can I find the tools that are used for that test? Is there any documentations for them? I am new to projects at this size, but I am willing to learn from these experiences as I am considering the open-source development as my career path seriously. I appreciate in advanced for any suggestions!

[zalo]

@helloboyxxx My recommendation would be to branch off of my branch: elalish/manifold@master...zalo:manifold:feat-julio-hull
And to just start adding more convex hull implementations (as Hull3() Hull4() etc.) and new test cases.

Then you can just run manifold_test and get the timings for how long each test takes to complete. (But, for your sanity, I'd get rid of the tests that take too long 😅).

Some more simple convex hull implementations to test:
https://github.com/karimnaaji/3d-quickhull
https://github.com/leomccormack/convhull_3d
https://github.com/tomilov/quickhull
https://github.com/andreacasalino/Fast-Quick-hull

[Kushal-Shah-03]

@zalo, I was trying to go through the code in the past few days, to identify where to introduce new implementations, and attempt to parallelize the algorithm, after feeling somewhat accustomed to the code, I attempted to introduce VHACD on my own, and once setup, I started experimenting with the code, I was trying some tests of my own, for now I am only running the tictactest with some changes and I experimented with different hull complexities, to compare time and although in terms of time complexity the VHACD still continues to struggle, but I noticed that in some cases the quickhull algorithm failed while the VHACD algorithm worked, although I saw the exact opposite of that too, but from the tests I ran the VHACD algorithm was more consistent (this is given the assumption that

the above message is not a message that states that the hull input is wrong, but since the VHACD algorithm didn't give the same message, I am confident it's an error in the algorithm and just wanted to confrim that once.

I have also attached an example of where the quick hull algorithm failed, and am trying to identify a workaround

But before I proceed further I wanted to confrim, if my interpretation of the error message was correct.

Also I am considering the Graham's Scan Algorithm and Chan's algorithm, I will try to integrate those and the implementations you have suggested as well. I have also set up a profiling tool, which will help in identifying which functions to improve upon, I attempted to parallelize the suggested piece of code in the quickhull approach, and wasn't having much success in including libraries with that, and was wondering if you could guide me in setting up the OpenMP headers, tbh I have set it up on my own by doing random changes in the cmakelists but wanted to set it up cleanly. Also, I wanted to know if there were any common tests that you have generally seen the quickhull algorithm struggle in, so that we can consider those when comparing with the other algorithms.

[pca006132]

I am not sure if the 2/3 vertex different constitute a failure, these algorithms usually have some error threshold, to deal with imprecision in floating point representation and operation. For example, you don't want to include every points when computing the convex hull of 8 points of a cube + some point samples from the cube surface, but because floating point imprecision those point will probably not form a perfect plane. You probably need to look at which vertex is missing, calculate its distance from the nearest plane if it is outside the convex hull, and see if it matches with the error threshold. If the result doesn't make sense, you should check the actual mesh instead on relying these simple checks.

Also, we are not using OpenMP, we use thrust/std parallel algorithms. See https://github.com/elalish/manifold/blob/master/src/utilities/include/par.h for their definitions, as well as some usage examples in

https://github.com/elalish/manifold/blob/9b1d25593172d134d06199b7570cb8574c243723/src/manifold/src/sort.cpp#L359-L373

[Kushal-Shah-03]

Thank you for clearing that misinterpretation, I will use the points you suggested, to evaluate the results better. I will also look into the thrust/std parallel algorithms and the resources, and will try to incorporate it.

[elalish]

Agreed, this is why many of our tests use EXPECT_NEAR on the volume and surface area of the mesh instead. These give a good checksum that the mesh is correct within precision without being sensitive to unimportant details like how many nearly coplanar verts there are.

[Kushal-Shah-03]

I attempted to fix the VHACD implementation of the last commit on your branch, but I haven't had much success with it, and was wondering if you could give some suggestions for that. Apart from that I've added this implementation https://github.com/karimnaaji/3d-quickhull , I checked the hull created as well, and it's correct, as well as some testcases [It doesn't seem to work for very large cases I'm trying to look into that], and I'm almost done with another implementation, and wanted to know if I've added it in the way that is expected (because I had to write some code to convert the vertices in the format that our Manifold function takes), so should I send a merge request to your branch or something? I've also been reading on thrust/std for parallelization, and will try to implement that on the quickhull algorithm as well.

[elalish]

Yes, a PR is the best way to get review and feedback. Try to separate them as much as you can so we can review them independently if you're working on multiple ideas/approaches.

[Kushal-Shah-03]

I have made a PR : elalish/manifold#781, looking forward to your feedback. Also for the google-cla verification, do I have do to that now, or is it if I get selected? (apologies if it's a silly question, as I had previously stated I am new to open source)

[elalish]

Thanks. It's trivial, so go ahead and sign it. You can't submit any code unless you do, so there won't generally be a review until you sign. We'll be happy to review your PR when it's working, but if you're stuck, please ask us specific questions in the PR.