Convex Hull algorithm in Unity - 6. Performance Benchmark

Quickhull Benchmark Test

• Version 2.1 Implementation
• Added additional property for face adjacency data. This data enables faster calculation in horizontal finding.

• Benchmark test vs MeshLab
• MeshLab also has convex hull calculation function. (Filters -> Remeshing, Simplification... -> Convex hull, based on the version 1.3.3)
• Test set are prepared from my Unity3D application, that generates random 3D locations inside unit sphere with designated number of times.
• Prepared points sets have 1,000~9,000 (1st interval), 10,000~90,000 (2nd interval) and 100,000~900,000 (3rd interval) number of points.
• Processing time and number of triangles in result convex hulls are recorded.

Full result table. As table shows, number of result triangle is identical in my implementation and MeshLab. Therefore I can argue that the result convex hulls from my implementation is valid.

(Interval 1) When the number of input point is small, processing time of MeshLab module is faster than my implementation.

(Interval 2) Around 60,000 number of input points, my implementation starts to show faster processing time than MeshLab module 

(Interval 3) Above hundred thousands of points, my implementation shows way better result than MeshLab

• I think there exist not optimized code in the early stage(ex, initial conflict list building) of process in my implementation, which I think, is convincing since mine finished slower in Interval 1(with smaller input points).
• I'm not sure why my implementation is faster with larger input points. Maybe due to the newly implemented face adjacency data? As far as I know, the same procedure is done by half-edge traverse in MeshLab implementation.

• Demo Clip
• My implementation in Unity3D C# and MeshLab
• The last point set (102,334 points) results 2,870 triangles both in my result and MeshLab