Convex Hull algorithm in Unity - 5. Quickhull, Real-time, Refined

Dynamic Convex hull Generation using Quickhull

• Version 2 Implementation
• Added function to handle numerically unstable cases, which caused crashes sometime in previous implementation.
• Refine data structure and conflict list update algorithm. It turns out that loop traversing method has significant effect on performance, of course.
• At this time, hash set helped me a lot.
• Still there exist some parts of codes that may need refinement.

• Demo Clip

• Same test case with my previous post. Refined version achieved at least 30Hz update rate.

• Test with recorded position of 100 moving points during 2 seconds in 0.1 seconds interval.
• So, when we have about 2,000 points as an input, we can generate convex hull in 30Hz.

• Test with recorded position of 300 moving points during 2 seconds in 0.1 seconds interval.
• I designed my implementation such that process stops when 10Hz is not achievable. In this case, result shows incomplete convex hull.