3D Convex hull of a working excavator - 2. Refinement, Filtering idea

• Since I found no better way to use GPU resource in Quickhull algorithm, implemented in Unity environment, I investigated other approach to achieve speedup.
•  I ended up with application-specific method that filters out a bunch of input points that cannot be an extreme point in result convex hull.
• So here is the comparison result of 3 approaches. The second one is explained in this post. The third one is new idea and I think I should clear up the assumption and theory behind it more on later post.

1. Raw points : Raw vertices processing
2. Extreme points : Using extreme vertices of convex hull of each components (swing, boom, arm and bucket)
3. Filtered points : Using filtered vertices

In this post, brief performance evaluation and result analysis will be shown.

• The first is comparison table. Difference is the number of points and as you can see the volume of result convex hull is same. Means same convex hull with different number of point input.

• Points are shown below. You may see significant reduction of points from left to right.

Raw points, extreme points and filtered points from left to right

• The final implementation use MIConvexHull ported by again, Skrawk. Why I couldn't find it when I started this?...Anyway it is faster than Qhull in Meshlab. I think the Qhull module integrated in Meshlab is rather old one. Latest version of Qhull is much faster than Meshlab.
• Also for the filtering method, I used GPU for speedup. It needs one time calculation for every vertices in each frame update without loop. So the performance improvement was significant. I'll explain it later in filtering approach.

• Here are result clips show actual run-time calculation.

• Raw points

• Extreme points

• Filtered points

Unity DirectCompute performance test

• I tested performance of DirectCompute feature in Unity where I planned to use it in 3D convex hull calculation.
• In short, there seems to be a performance issue when reading data from GPU to CPU, in Unity's direct compute feature.
• GPU is really faster when using it in well-aligned way with rendering pipeline. But I have to use it in different way in Convex hull. The point-plane test has to be done several times (300~500 in average for our excavator vertex set) on subset of points with newly generated planes in each loop repetition. The "Loop repetition" is a problem here. Since we need point-plane test result of previous loop in next loop calculation, we should send calculation result from GPU to CPU but it is extremely slow.
• As I mentioned in previous post, I predicted the problem but the amount of slowdown is far more than I expected. I also wrote the related question in Unity answers forum but no "answers" yet.
• The paper I read(CudaHull) also took similar approach with my plan. But there seems less slowdown in GPU to CPU data transfer. So I suspect that the problem is Unity-specific, or DirectCompute-specific one...

• Here is the first test result on 100,000 vertices with tetrahedron. Tetrahedron is changing in each frame and all the vertices are tested if it can be seen in each face of tetrahedron. As you can see, GPU is lot faster than CPU when without a loop.

• Test on 100,000 vertices.

• Following two clips are 100,000 vertices with 100 and 300 loop. In each loop, subset of points are tested and results are sent to GPU with GetData() function. You can see how long it takes to send data from GPU to CPU.

• I really hope to know how to solve this issue...

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.

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