3D Convex hull of a working excavator - 1.Problem definition and the first development

• Problem Def
• The reason why I've been investigating 3D, dynamic convex hull is to calculate and visualize it with working excavator, for safety control.
• The concept is similar with the objective of proximity sensor mounted in vehicle, which allows safety stop of a vehicle by detecting obstacles before crashing.
• So far, we're developing simulator of it focusing on excavator, where safety control of excavator is much complex due to it's kinematic characteristic.
• Same problem in 2D space is simpler and we already have a result.

• As you may notice, the area is predicted using angular velocity of the cabin so it is became wider along its rotation heading.
• It stops when detecting an obstacle in "danger area".
• The prediction of actual danger area is much complicated and emergency stop algorithm considers many variables. It will be studied by other research group. And is not included in video clip.
• What I have done is calculate and visualize 2D danger area by 2D convex hull algorithm using series of offset points of cabin where the movement of it is simply predicted from linear extrapolation.
• In this new series of posts, I will study the method to calculate and visualize 3D danger area in real-time rate. In 3D, all movement of its components(cabin, boom, arm and bucket) will be precisely reflected in danger area.

• Preparation
• First step I did for 3D is reducing the number of points for convex hull calculation. The target source model of mine has 26,805 points(vertices).

Target excavator mesh. Cabin, boom, arm and bucket are separated, but shown as an assembly.

• As you may seen in previous post regarding my implementation of 3D convex hull using QuickHull method, it is hard to achieve real-time rate(let our first, ambitious target number as 30Hz, around 30ms)with that much point input. It results 280ms to calculate 3D convex hull in MeshLab.
• We don't need all these points in runtime. We only need the points that has a possibility to contribute in result convex hull.
• As a preprocessing, convex hull of each component(cabin, boom, arm and bucket) mesh with 1 unit(=meter in application) offset has been made and recorded the information of point(actually, index of vertices).
• In runtime, only those points are considered for convex hull calculation.
• As a result, 1,750 point set is a minimum number of input point when excavator doesn't move.

Example of arm mesh preprocessing. With 1 unit offset, convex hull was calculated with 233 out of 2,687 points, so we can filter out rest points in run time calculation.

Convex hull of all components. 1,750 out of 26,805 points contributes to result convex hull.

• First development
• Unfortunately, we have to deal with up to 35,000 points in runtime.
• Since danger area should be "predictive", number of points are larger than 1,750. For example, we set the prediction interval as 100 ms and prediction time up to 2000 ms. Therefore up to 1,750 x (2000/100) = 35,000 number of points are became input for each frame.
• The first version of application is implemented with features below

1. Simple excavator manipulation using keyboard
2. Component movement prediction using linear extrapolation and several global-local coordinate conversion between orientation of components
3. Some debug & logging modules for further performance test
4. Of course, 3D convex hull calculation using points from 2.

• To prevent convex hull calculation affects rendering-related executions, 4. was implemented as a separated thread.
• Result video clip is here.

• Without movement, calculation from 1,750 point input can be done around 80~90ms.
• When there is a movement, so prediction starts, (you may see the predictive danger area covers ahead from current position of components) around 20,000 points are passed as an input so calculation takes around 250ms.
• Therefore for 30ms calculation, about 10 times faster calculation is required.

• Next
• I'm considering to develop parallelized calculation for convex hull.
• There is a PAPER studied Quickhull algorithm with CUDA(named CudaHull), but I'm not sure it may fit to our application. GPU-CPU data transfer takes time and if we follow the method of CudaHull, the transfer should happened in every single frame.

Convex Hull algorithm in Unity - 7. Tentative Final

Quickhull Benchmark Test2

• Version 2.2 Implementation
• Optimize data structure. Cleaning up.

• Benchmark test vs MeshLab Qhull
• Same performance test as previous pose, was conducted after optimization.
• Result shows good enough numbers. Result of test interval 3 shows still far faster calculation time compared with MeshLab Qhull, and difference of result numbers in interval 1 has been decreased.

Full result table

(Interval 1) Calculation time graph. My implementation is marked as blue

(Interval 2) Calculation time graph

(Interval 2) Calculation time graph

• Next?
• For the next step, real-time calculation combined with actual application (excavator simulation) will be investigated.

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

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.