Antony, JomsMukundan, Manoj KumarThomas, MathewMuthuganapathy, RamanathanChen, RenjieRitschel, TobiasWhiting, Emily2024-10-132024-10-132024978-3-03868-250-9https://doi.org/10.2312/pg.20241292https://diglib.eg.org/handle/10.2312/pg20241292Many real-world applications demand the computation of a convex hull (CH) when the input points originate from structured configurations such as two-dimensional (2D) or three-dimensional (3D) grids. Convex hull in grid space has found applications in geographic information systems, medical data analysis, path planning for robots/autonomous vehicles etc. Conventional as well as existing GPU-accelerated algorithms available for CH computation cannot operate directly on 2D or 3D grids represented in matrix format and do not exploit the inherent sequential ordering in such rasterized representations. This work introduces novel filtering algorithms, initially developed for a 2D grid space and subsequently extended to 3D to speed up the hull computation. They are further extended as GPU-CPU hybrid algorithms and are implemented and evaluated on a commercial NVIDIA GPU. For a 2D grid, the number of contributing pixels is always restricted to ≤ 2n for an (n×n) grid. Moreover, they are extracted in lexicographic order, ensuring an efficient O(n) computation of CH. Similarly, in 3D, the number of contributing voxels is always limited to ≤ 2n2 for an (n×n×n) voxel matrix. Additionally, 2D CH filtering is enabled across all slices of the 3D grid in parallel, leading to a further reduction in the number of contributing voxels to be fed to the 3D CH computation procedure. Comparison with the state of the art indicated that our method is superior, especially for large and sparse point clouds.Attribution 4.0 International LicenseCCS Concepts: Computing methodologies → Parallel algorithms; Concurrent algorithms; Image processingComputing methodologies → Parallel algorithmsConcurrent algorithmsImage processing10.2312/pg.2024129213 pages