Convex Hull algorithm in Unity - 3. Quickhull

Quickhull Implementation on Unity

• Quickhull
• Implementing Quickhull

•  My Implementation - version 1
• Focused on understanding the algorithm and validation
• Step by step visualization for debugging

• Demo Clip1

• Tested using 50 randomly generated points in unit sphere
• Visualized lines
• Red line : triangles made in previous iteration
• Green line : triangles made in current iteration
• Yellow line : found horizon in current iteration
• Cyan line : normal vector of triangles
• 25 iterations to finish, and 0.0279 second elapsed (sum of calculation time of 25 iteration)
• Therefore, 30Hz update is possible with 50 points?

• Demo Clip2

• Tested using 300 randomly generated points in same domain
• 82 iterations to finish, 0.1747 second elapsed
• 5.7 Hz?

• Plans for version2
• Performance improvement
• Implement conflict list managing functionality, that shortens search time for next candidate vertex
• Horizon finding using half edge traverse?
• Test for real-time scenario
• Test for complex offset model