Convex Hull Computation in a Grid Space: A GPU Accelerated Parallel Filtering Approach
| dc.contributor.author | Antony, Joms | en_US |
| dc.contributor.author | Mukundan, Manoj Kumar | en_US |
| dc.contributor.author | Thomas, Mathew | en_US |
| dc.contributor.author | Muthuganapathy, Ramanathan | en_US |
| dc.contributor.editor | Chen, Renjie | en_US |
| dc.contributor.editor | Ritschel, Tobias | en_US |
| dc.contributor.editor | Whiting, Emily | en_US |
| dc.date.accessioned | 2024-10-13T18:04:14Z | |
| dc.date.available | 2024-10-13T18:04:14Z | |
| dc.date.issued | 2024 | |
| dc.description.abstract | Many 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. | en_US |
| dc.description.sectionheaders | Geometric Processing II | |
| dc.description.seriesinformation | Pacific Graphics Conference Papers and Posters | |
| dc.identifier.doi | 10.2312/pg.20241292 | |
| dc.identifier.isbn | 978-3-03868-250-9 | |
| dc.identifier.pages | 13 pages | |
| dc.identifier.uri | https://doi.org/10.2312/pg.20241292 | |
| dc.identifier.uri | https://diglib.eg.org/handle/10.2312/pg20241292 | |
| dc.publisher | The Eurographics Association | en_US |
| dc.rights | Attribution 4.0 International License | |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | |
| dc.subject | CCS Concepts: Computing methodologies → Parallel algorithms; Concurrent algorithms; Image processing | |
| dc.subject | Computing methodologies → Parallel algorithms | |
| dc.subject | Concurrent algorithms | |
| dc.subject | Image processing | |
| dc.title | Convex Hull Computation in a Grid Space: A GPU Accelerated Parallel Filtering Approach | en_US |