Convex Hull algorithm in Unity - 4. Quickhull, Real-time

Dynamic Convex hull Generation using Quickhull

• My Implementation - version 1.5?
• Similar with 2D CASE, point set recorded from moving object are stored and calculated
• Target frequency was set as 30Hz, but result showed less frequency
• (Planned performance improvement method is not implemented yet...)
• While testing real-time calculation, application crashed very often, due to the miscalculated normal directions
• The problem has fixed now, but not completely...

• Demo Clip

• Maximum number of points in point set : 480(8 points from object x 2 seconds x 30Hz)
• Fps observed dropped to 8, since next rendering frame starts when convex hull generation is finished

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

Convex Hull algorithm in Unity - 2. 3D problem

Real-time visualization of 3D proximity area of moving vehicle during some period

• Proximity area

• Can be generated by offsetting mesh surface

• Off-line generation is okay, but on-line is preferred if possible

• Intersection problem is not a big issue since final 3D proximity area will be obtained by 3D convex hull algorithm

• Only vertices will be delivered to the convex hull process.

• 3D Convex Hull

• Generated by calculating convex hull from trajectory of offset vertices

• Must be generated in real-time.

• Since orientation of vehicle will be limited (e.g. upside-down), we may limit the number of vertex applied.

•  Test, so far

• Implement extremely simplified version of offsetting method for proximity area

• MIConvexHull library for 3D convex hull

• Next?

• 3D convex hull implementation in Unity3D development environment.

Solid colored mesh : source model / Red dots : offset vertices / Wireframe : convex hull from offset vertices

0.003 unit offset from surface

In real-time scenario, vertices that never contributes to convex hull can be excluded in calculation. For example, vertices located behind bunny's neck.

Convex Hull algorithm in Unity

Convex hull algorithm in Unity - 1. 2D problem

• Convex hull algorithm
• To visualize offset area of freely moving vehicle over time, I developed 2D convex hull algorithm in Unity3D environment.

Moving Vehicle, expressed as connected cubes

• There's nice library for convex hull algorithm, but is not possible to use it in Unity3D, since the library was implemented based on .NET 4.
• So, I implemented Graham's scan by myself, by firstly implement the algorithm in MATLAB and converting it into C#.

• Result in MATLAB
• Circles : trajectory of vertices of vehicle offset 
• Lines : calculated convex hull

• Result in Unity3D
• Store vertices data 30 times per second
• Maintain up to 2 seconds data from current frame
• From those vertices, calculate convex hull in every frame and generate 3D shape by extruding result.
• For better visualization, add outlines for edges

• Next?
• 2D offset --> 3D offset