论文标题
使用平行GPU算法加速凸船体计算
Accelerating the Convex Hull Computation with a Parallel GPU Algorithm
论文作者
论文摘要
凸壳是许多应用的基本几何结构，其中必须由凸多边形封闭或表示点的点组。尽管存在有效的顺序凸赫尔算法，并且不断地用于应用程序，但它们的计算时间通常被认为是时间敏感任务的问题，例如实时碰撞检测，聚类或图像处理虚拟现实等，以及其他需要快速响应时间的问题。在这项工作中，我们提出了基于GPU的Heaphull的平行改编，这是CPU算法的最先进的状态，该状态通过首先进行有效的过滤阶段来计算凸船体，然后进行实际的凸赫尔计算。更具体地说，这项工作使过滤阶段并行，将其调整为GPU编程模型，作为一系列并行降低。实验评估表明，拟议的实施显着提高了凸船体计算的性能，在基于顺序的CPU的Heaphull上，高达$ 4 \ times的加速$ 4 \ times \ sim 4 \ sim 4 \ times $在现有基于GPU的方法上。
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.
