More efficient convex hull calculation

Post and discuss features you'd like to see in the BEPUphysics library.
Post Reply
Unjeffer
Posts: 1
Joined: Fri Mar 03, 2017 3:26 pm

More efficient convex hull calculation

Post by Unjeffer » Sun Mar 05, 2017 9:50 pm

Playing with demos i wanted to increase the definition of meshes of minkowski sums shapes.
So i set

Code: Select all

 InertiaHelper.GenerateSphere(2, out SampleDirections, out sampleTriangleIndices); 
to

Code: Select all

 InertiaHelper.GenerateSphere([b]4[/b], out SampleDirections, out sampleTriangleIndices);
The convex hull calculation was taking forever.
I tried to use this library https://github.com/DesignEngrLab/MIConvexHull, and it was much more fast.
Actually with subdivisionCount = 4 the result is wrong in either way, i think that there i some kind of bug, but with 3 it works ok.

Norbo
Site Admin
Posts: 4489
Joined: Tue Jul 04, 2006 4:45 am

Re: More efficient convex hull calculation

Post by Norbo » Sun Mar 05, 2017 10:51 pm

Yup, it's not great right now- that code is some of the oldest and ricketiest in the entire engine. It can sometimes produce wonky triangulations, especially when dealing with near degenerate triangles like those generated by the MinkowskiSumShape demo graphics at high subdivisions. It's something that I'd like to improve, but it'll probably wait until the core parts of v2 are in place.

For the purposes of physics representation, note that all shapes provide a constructor that bypasses calculations at runtime. Loading preprocessed data (including from external tools and libraries) can bypass the slowness and occasional bug, which tends to be important if you have a lot of shapes or very complicated shapes.

Also, again for the physics representation, I generally recommend convex hulls have a low number of vertices. The cost of collision detection with convex hulls is proportional to the number of vertices in the hull. Staying below 30 whenever possible is a good idea. Lower is always better. As a side benefit, smaller point counts tend to not break the convex huller.

Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest