Abstract
Voxelization of solids, that is the representation of a solid by a set of voxels that approximates it, is an operation with important applications in fields like solid modeling, physical simulation or volume graphics. Moreover, the new generation of affordable 3D raster displays has renewed the interest on fast voxelization algorithms, as the scan-conversion of a solid is a basic operation on these devices.
In this paper a hardware accelerated method for computing a voxelization of a polyhedron is presented. The algorithm is simple, efficient, robust and handles any kind of polyhedron (self-intersecting, with or without holes, manifold or non-manifold). Three different implementations are described in detail. The first is a conventional implementation in the CPU, the second is a hardware accelerated implementation that uses standard OpenGL primitives, and the third exploits the capabilities of modern GPUs by using vertex programs.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Andres, E., Nehlig, P., Francon, J.: Tunnel-free supercover 3D polygons and polyhedra. Comput. Graph. Forum 16, 3–13 (1997)
Blundell, B., Schwarz, A.: Volumetric Three-Dimensional Display Systems. Wiley, New York (2000)
Cabral, B., Cam, N., Foran, J.: Accelerated volume rendering and tomographic reconstruction using texture mapping hardware. In: Proceedings of the 1994 IEEE Symposium on Volume Visualization, pp. 91–98 (1994)
Carucci, F.: Inside Geometry Instancing. In: GPU Gems 2: Programming Techniques for High-Performance Graphics and General Purpose Computation, pp. 47–68. Addison-Wesley, Boston (2004)
Chen, M., Tucker, J.V.: Constructive volume geometry. Comput. Graph. Forum 19, 281–293 (2000)
Ebert, D., Bedwell, E., Maher, S., Smoliar, L., Downing, E.: Realizing 3D visualization using crossed-beam volumetric displays. Commun. ACM 42, 101–107 (1999)
Fang, S., Chen, H.: Hardware accelerated voxelization. Comput. Graph. 24, 433–442 (2000)
Feito, F., Torres, J.C.: Orientation, simplicity and inclusion test for planar polygons. Comput. Graph. 19, 596–600 (1995)
Feito, F., Torres, J.C.: Inclusion test in general polyhedra. Comput. Graph. 21, 23–30 (1997)
Fernando, R., Kilgard, M.J.: The Cg Tutorial: The Definitive Guide to Programmable Real-time Graphics. Addison-Wesley, Boston (2003)
Fernando, R.: GPU Gems: Programming Techniques, Tips and Tricks for Real-Time Graphics. Addison-Wesley, Boston (2004)
Foley, J.D., van Dam, A., Feiner, S.K., Hughes, J.H.: Introduction to Computer Graphics. Addison-Wesley, Boston (1994)
Frisken, F.S.: Using distance maps for accurate surface representation in sampled volumes. In: IEEE Symposium on Volume Visualization, pp. 23–30 (1998)
Haumont, D., Warzie, N.: Complete polygonal scene voxelization. J. Graph. Tools 7, 27–41 (2002)
Huang, J., Yagel, R., Filippov, V., Kurzion, Y.: An accurate method to voxelize polygonal meshes. In: IEEE Symposium on Volume Visualization, pp. 119–126 (1998)
Jones, M.W.: The production of volume data from triangular meshes using voxelisation. Comput. Graph. Forum 15, 311–318 (1996)
Karabassi, E., Papaioannou, G., Theoharis, T.: A fast depth-buffer-based voxelization algorithm. ACM J. Graph. Tools 4, 114–124 (2002)
Kaufman, A., Shimony, E.: 3D scan-conversion algorithms for voxel-based graphics. In: Proceedings ACM Workshop on Interactive Graphics, pp. 45–76 (1986)
Kaufman, A.: Efficient algorithms for 3D scan-conversion of parametric curves, surfaces and volumes. Comput. Graph. 21, 171–179 (1987)
Kaufman, A.: Efficient algorithms for scan-conversing 3D polygons. Comput. Graph. 12, 213–219 (1988)
Kaufman, A., Cohen, D., Yagel, R.: Volume graphics. IEEE Comput. 26, 51–64 (1993)
Lee, Y. T, Requicha, A.: Algorithms for computing the volume and other integral properties of solids. Commun. ACM 25, 635–650 (1982)
Li, W., Fan, Z., Wei, X., Kaufman, A.: Flow simulation with complex boundaries. In: GPU Gems 2: Programming Techniques for High-Performance Graphics and General Purpose Computation, pp. 747–763. Addison-Wesley, Boston (2005)
Pastoor, S., Kiesewetter, R.: 3-D displays: A review of current technologies. DISPLAYS 17, 100–110 (1997)
Passalis, G., Kakadiaris, I.A., Theoharis, T.: Efficient Hardware Voxelization. In: Proceedings of the Computer Graphics International, pp. 374–377 (2004)
Pharr, M.: GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation. Addison-Wesley, Boston (2005)
Rueda, A.J., Segura, R., Feito, F.R., Ogayar, C.: Voxelization of solids using simplicial coverings. In: Proceedings of WSCG’2004, pp. 227–234 (2005)
Rueda, A.J., Segura, R., Ruiz de Miras, J., Feito, F.R.: Rasterizing complex polygons without tesselations. Graph. Models 26, 805–814 (2004)
Šrámek, M., Kaufman, A.: A. Alias-free voxelization of geometric objects. IEEE Trans. Visual. Comput. Graph. 5, 251–267 (1999)
Šrámek, M., Kaufman, A.: VXT: a C++ class library for object voxelization. In: Proceedings of the International Workshop on Volume Graphics, pp. 119–134 (1999)
Wang, S.W., Kaufman, A.: Volume-sampled 3D modelling. IEEE Comput. Graph. Appl. 14, 26–32 (1994)
Woo, M., Nedider, J., Davis, T., Shreiner, D.: The OpenGL Programming Guide, 3rd. edn. Addison-Wesley, Boston (1999)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ogáyar, C., Rueda, A., Segura, R. et al. Fast and simple hardware accelerated voxelizations using simplicial coverings . Visual Comput 23, 535–543 (2007). https://doi.org/10.1007/s00371-007-0097-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00371-007-0097-8