3D Convex hull of a working excavator - 2. Refinement, Filtering idea

• Since I found no better way to use GPU resource in Quickhull algorithm, implemented in Unity environment, I investigated other approach to achieve speedup.
•  I ended up with application-specific method that filters out a bunch of input points that cannot be an extreme point in result convex hull.
• So here is the comparison result of 3 approaches. The second one is explained in this post. The third one is new idea and I think I should clear up the assumption and theory behind it more on later post.

1. Raw points : Raw vertices processing
2. Extreme points : Using extreme vertices of convex hull of each components (swing, boom, arm and bucket)
3. Filtered points : Using filtered vertices

In this post, brief performance evaluation and result analysis will be shown.

• The first is comparison table. Difference is the number of points and as you can see the volume of result convex hull is same. Means same convex hull with different number of point input.

• Points are shown below. You may see significant reduction of points from left to right.

Raw points, extreme points and filtered points from left to right

• The final implementation use MIConvexHull ported by again, Skrawk. Why I couldn't find it when I started this?...Anyway it is faster than Qhull in Meshlab. I think the Qhull module integrated in Meshlab is rather old one. Latest version of Qhull is much faster than Meshlab.
• Also for the filtering method, I used GPU for speedup. It needs one time calculation for every vertices in each frame update without loop. So the performance improvement was significant. I'll explain it later in filtering approach.

• Here are result clips show actual run-time calculation.

• Raw points

• Extreme points

• Filtered points