poster

gHull: a three-dimensional convex hull algorithm for graphics hardware

Authors:

Mingcen Gao,

Thanh-Tung Cao,

Tiow-Seng Tan,

Zhiyong HuangAuthors Info & Claims

I3D '11: Symposium on Interactive 3D Graphics and Games

Page 204

https://doi.org/10.1145/1944745.1944784

Published: 18 February 2011 Publication History

Get Access

Abstract

We present a novel approach, termed gHull, to compute the convex hull for a 3D point set using the GPU. We exploit the fast computation of the digital Voronoi diagram and its relationship with the convex hull to compute the answer from the former rather than directly. Our algorithm is robust, while able to maximizes the parallelism available in the GPU to achieve significant speed up.

References

[1]

Barber, C. B., Dobkin, D. P., and Huhdanpaa, H. 1996. The Quickhull algorithm for convex hulls. ACM Trans. Mathematical Software 22, 4, 469--483.

Digital Library

Google Scholar

[2]

Cao, T.-T., Tang, K., Mohamed, A., and Tan, T.-S. 2010. Parallel banding algorithm to compute exact distance transform with the GPU. In SI3D: Proc. Symp. Interactive 3D Graphics and Games, 83--90.

Digital Library

Google Scholar

[3]

Shewchuk, J. R. 2005. Splaying: an algorithm for repairing delaunay triangulations and convex hulls. In SCG '05: Proc. 21st ACM Symp. Computational Geometry, Press, 237--246.

Digital Library

Google Scholar

Cited By

View all

Karmakar NBiswas A(2015)Construction of 3D Orthogonal Convex Hull of a Digital ObjectProceedings of the 17th International Workshop on Combinatorial Image Analysis - Volume 944810.1007/978-3-319-26145-4_10(125-142)Online publication date: 24-Nov-2015
https://dl.acm.org/doi/10.1007/978-3-319-26145-4_10
Machado e Silva REsperança CMarroquim ROliveira A(2014)Image Space Rendering of Point Clouds Using the HPR OperatorComputer Graphics Forum10.1111/cgf.1226533:1(178-189)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1111/cgf.12265
Stein AGeva EEl-Sana J(2012)Applications of Geometry ProcessingComputers and Graphics10.5555/2189434.218972236:4(265-271)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.5555/2189434.2189722
Show More Cited By

Index Terms

gHull: a three-dimensional convex hull algorithm for graphics hardware
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

gHull: A GPU algorithm for 3D convex hull

A novel algorithm is presented to compute the convex hull of a point set in ℝ³ using the graphics processing unit (GPU). By exploiting the relationship between the Voronoi diagram and the convex hull, the algorithm derives the approximation of the ...
A GPU accelerated algorithm for 3D Delaunay triangulation
I3D '14: Proceedings of the 18th meeting of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games

We propose the first algorithm to compute the 3D Delaunay triangulation (DT) on the GPU. Our algorithm uses massively parallel point insertion followed by bilateral flipping, a powerful local operation in computational geometry. Although a flipping ...
Computing 2D Constrained Delaunay Triangulation Using the GPU

We propose the first graphics processing unit (GPU) solution to compute the 2D constrained Delaunay triangulation (CDT) of a planar straight line graph (PSLG) consisting of points and edges. There are many existing CPU algorithms to solve the CDT ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

I3D '11: Symposium on Interactive 3D Graphics and Games

February 2011

207 pages

ISBN:9781450305655

DOI:10.1145/1944745

General Chairs:
Michael Garland
NVIDIA Research
,
Rui Wang
University of Massachusetts

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 February 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

I3D '11

Sponsor:

SIGGRAPH

I3D '11: Symposium on Interactive 3D Graphics and Games

February 18 - 20, 2011

California, San Francisco

Acceptance Rates

I3D '11 Paper Acceptance Rate 24 of 64 submissions, 38%;

Overall Acceptance Rate 148 of 485 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
323
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Karmakar NBiswas A(2015)Construction of 3D Orthogonal Convex Hull of a Digital ObjectProceedings of the 17th International Workshop on Combinatorial Image Analysis - Volume 944810.1007/978-3-319-26145-4_10(125-142)Online publication date: 24-Nov-2015
https://dl.acm.org/doi/10.1007/978-3-319-26145-4_10
Machado e Silva REsperança CMarroquim ROliveira A(2014)Image Space Rendering of Point Clouds Using the HPR OperatorComputer Graphics Forum10.1111/cgf.1226533:1(178-189)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1111/cgf.12265
Stein AGeva EEl-Sana J(2012)Applications of Geometry ProcessingComputers and Graphics10.5555/2189434.218972236:4(265-271)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.5555/2189434.2189722
Tang MZhao JTong RManocha D(2012)SMI 2012Computers and Graphics10.1016/j.cag.2012.03.01536:5(498-506)Online publication date: 1-Aug-2012
https://dl.acm.org/doi/10.1016/j.cag.2012.03.015
Stein AGeva EEl-Sana J(2012)CudaHull: Fast parallel 3D convex hull on the GPUComputers & Graphics10.1016/j.cag.2012.02.01236:4(265-271)Online publication date: Jun-2012
https://doi.org/10.1016/j.cag.2012.02.012

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

gHull: A GPU algorithm for 3D convex hull

A GPU accelerated algorithm for 3D Delaunay triangulation

Computing 2D Constrained Delaunay Triangulation Using the GPU

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations