Fast computation of three-dimensional convex hulls using graphics hardware

摘要

This paper describes an algorithm for computing three-dimensional convex hulls. First, we introduce a simple algorithm to compute two-dimensional convex hulls using graphics hardware. This algorithm computes the edges and the facets of the convex hulls by analyzing bitmap images drawn using given points. Graphics hardware can generate bitmap images of three-dimensional objects very rapidly. We then expand the algorithm to compute three-dimensional convex hulls. Finally, we apply the algorithm to compute Delaunay diagrams. The algorithm is very simple. Hoff et al. reported an algorithm to draw Voronoi diagrams using graphics hardware [3]. Our algorithms are based on the same technique used by [3]. However, our algorithm employs an analyzing phase of the images and obtains topological information from the image. The diagrams produced by our algorithm are not strict Delaunay diagrams, because the images we obtain using graphics hardware are bitmap images and are not continuous. Therefore, they may contain some errors but, because of the simplicity of the algorithm, they are stable compared with ordinary algorithms, without a requirement for special techniques, such as symbolic perturbation. The algorithms can be easily implemented.