Accelerating the Convex Hull Computation with a Parallel GPU Algorithm

The convex hull is a fundamental geometrical structure for many applications where groups of points must be enclosed or represented by a convex polygon. Although efficient sequential convex hull algorithms exist, and are constantly being used in applications, their computation time is often consider...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-09
Main Authors: Keith, Alan, Ferrada, Héctor, Navarro, Cristóbal A
Format: Article
Language:English
Subjects:
Algorithms
Central processing units
Clustering
Computational geometry
Convexity
CPUs
Filtration
Graphics processing units
Image processing
Virtual reality
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The convex hull is a fundamental geometrical structure for many applications where groups of points must be enclosed or represented by a convex polygon. Although efficient sequential convex hull algorithms exist, and are constantly being used in applications, their computation time is often considered an issue for time-sensitive tasks such as real-time collision detection, clustering or image processing for virtual reality, among others, where fast response times are required. In this work we propose a parallel GPU-based adaptation of heaphull, which is a state of the art CPU algorithm that computes the convex hull by first doing a efficient filtering stage followed by the actual convex hull computation. More specifically, this work parallelizes the filtering stage, adapting it to the GPU programming model as a series of parallel reductions. Experimental evaluation shows that the proposed implementation significantly improves the performance of the convex hull computation, reaching up to \(4\times\) of speedup over the sequential CPU-based heaphull and between \(3\times \sim 4\times\) over existing GPU based approaches.
ISSN:2331-8422