1  Zhejiang University, China
2  University of North Carolina at Chapel Hill, USA
Interior point culling filter: For the input points, a tetrahedron is constructed as an initial pseudohull. Each facet of the pseudohull is updated by replacing it with three new facets. Each of these new facets is computed by connecting the edges of the old facet with the furthest point in the exterior set. All the points inside the expanding pseudohull are marked as interior points. After 4 iterations, most of the interior points are culled away. The pseudohull is incrementally updated till there are no exterior points. 

Performance comparison: Comparing to the optimized CPUbased implementation, our hybrid CPUGPU algorithm achieves 1327x speedups over the CPUbased QuickHull algorithm on an NVIDIA GeForce GTX580 for all these static benchmarks. 

Performance comparison: By testing on 10M, 30M, and 50M points that are randomly distributed in a spherical 3D space, the hybrid algorithm demonstrates higher speedup over the CPUbased algorithm as the size of the pointset increases. 
Culling Efficiency: By running the pseudohull filter, less than 5% of the original input points are not culled. As a result, the input size, in terms of points, to the final CPUbased computation algorithm is relatively small.  Running time ratios: The figure shows the breakdown of each phase of the hybrid algorithm on different benchmarks. Basically, this breakdown indicates that a majority of the overall time is spent in the GPUbased interior point filtering algorithm on these benchmarks. The time spent in datatransfer and CPUbased algorithm is relatively small. 
Culling efficiency for deforming point sets: By utilizing the spatial and temporal coherence between successive simulation time steps, a scan pass is performed to reuse pseudohulls at last simulation time step and remove interior points. Another pass is performed for interior point culling.  Speedups for deforming point sets: With the help of the lightweighted scan pass, the hybrid algorithm achieved up to 46x speedups for deforming point sets. 
Abstract
We present a hybrid algorithm to compute convex hull of points in three and higher dimensional spaces. Our formulation uses a GPUbased interior point filter to cull away many of the points that do not belong to the boundary. The convex hull of remaining points is computed on the CPU. The GPUbased filter proceeds in an incremental manner and computes a pseudohull that is contained inside the convex hull of the original points. The pseudohull computation involves only localized operations and therefore, maps well to GPU architectures. Furthermore, the underlying approach extends to high dimensional point sets and deforming points. In practice, our culling filter can reduce the number of candidate points by two orders of magnitude. We have implemented the hybrid algorithm on commodity GPUs, and evaluated its performance on several large point sets. In practice, the GPUbased filtering algorithm can cull up to 85M interior points per second on NVIDIA GeForce GTX 580 and the hybrid algorithm improves the overall performance of convex hull computation by 1027 times (for static point sets) and 2246 times (for deforming point sets).
Paper (PDF 1.08 MB)
Min Tang, Jieyi Zhao, Ruofeng Tong, and Dinesh Manocha, GPU accelerated Convex Hull Computation, Accepted by SMI 2012, 2012.
This research is supported in part by National Basic Research Program of China (2011CB302205), National Key Technology R\&D Program of China (2012BAD35B01), NSFC (61170140), Natural Science Foundation of Zhejiang, China (Y1100069). Manocha is supported in part by ARO Contract W911NF1010506, NSF awards 0917040, 0904990, 1000579 and 1117127, and Intel. Tong is partly supported by NSFC (61170141).
UNC dynamic model benchmark repository
CollisionStreams: Fast GPUbased Collision Detection for Deformable Models
Fast Continuous Collision Detection using Deforming NonPenetration Filters
MCCD: MultiCore Collision Detection between Deformable Models using FrontBased Decomposition
Fast Collision Detection for Deformable Models using RepresentativeTriangles
DeformCD: Collision Detection between Deforming Objects
SelfCCD: Continuous Collision Detection for Deforming Objects
Interactive Collision Detection between Deformable Models using Chromatic Decomposition
Fast Proximity Computation Among Deformable Models using Discrete Voronoi Diagrams
CULLIDE: Interactive Collision Detection between Complex Models using Graphics Hardware
RCULLIDE: Fast and Reliable Collision Culling using Graphics Processors
QuickCULLIDE: Efficient Inter and IntraObject Collision Culling using Graphics Hardware
CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 275993175
919.962.1749
geom@cs.unc.edu