GPU accelerated convex hull computation

We present a hybrid algorithm to compute the convex hull of points in three or higher dimensional spaces. Our formulation uses a GPU-based interior point filter to cull away many of the points that do not lie on the boundary. The convex hull of remaining points is computed on a CPU. The GPU-based filter proceeds in an incremental manner and computes a pseudo-hull that is contained inside the convex hull of the original points. The pseudo-hull computation involves only localized operations and 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 GPU-based filtering algorithm can cull up to 85 M interior points per second on an NVIDIA GeForce GTX 580 and the hybrid algorithm improves the overall performance of convex hull computation by 10–27 times (for static point sets) and 22–46 times (for deforming point sets).

Figure optionsDownload high-quality image (255 K)Download as PowerPoint slideHighlights
► We design a GPU-based interior point filter to cull away many of the points that do not lie on the boundary.
► The pseudo-hull computation involves only localized operations and maps well to GPU architectures.
► 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.