A general approach to the implementation of methods for the implicit surface triangulation using space partitioning into cells

Authors

  • A.Yu. Dizhevskii

Keywords:

триангуляция
таблица случаев
разбиение пространства
марширующие кубы
марширующие призмы
пространственная триангуляция

Abstract

The most popular algorithms for constructing a triangulation of 3D-objects via space partitioning into cubic and tetrahedral cells are considered. А general approach to the triangulation on the basis of space partitioning into arbitrary cells is proposed. As examples, two new methods of triangulation are discussed. These methods use a space division into pyramids and prisms. Some peculiarities of computer implementation of these methods are analyzed. A qualitative comparative analysis of the resulting triangulations is given.

New computational technologies

Downloads

Published

2007-10-10

Issue

Vol. 8 (2007): Issue 3.

Section

Section 1. Numerical methods and applications

Author Biography

A.Yu. Dizhevskii

Lomonosov Moscow State University,
Faculty of Mechanics and Mathematics

References

  1. Lorensen W.E., Cline H. Marching cubes: a high resolution 3d surface construction algorithm // ACM SIGGRAPH Computer Graphics. 1987. 21, N 4. 163-169.
  2. Gueziec A. Exploiting triangulated surface extraction using tetrahedral decomposition // IEEE Transactions on Visualization and Computer Graphics. 1995. 1, N 4. 328-342.
  3. Skala V. Precision of iso-surface extraction from volume data and visualization // Electronic Proc. of the Conf. on Scientific Computing 2000. 368-378 (http://www.emis.de/journals/AMUC/_contributed/algo2000/skala.pdf).
  4. Carneiro B.P., Silva C.T., Kaufman A.E. Tetra-Cubes: an algorithm to generate 3D isosurfaces based upon tetrahedra // Proc. of SIGGRAPH’96. Vol. 9. New Orleans, 1996. 205-210.
  5. Montani C., Scateni R., Scopigno R. Discretized marching cubes // Proc. of the Conf. on Visualization’94. Washington, DC, 1994. 281-287.
  6. Bourke P. Polygonising a scalar field. 1997 (http://astronomy.swin.edu.au/ pbourke/modelling/polygonise).
  7. Shephard M., Georges M. Automatic three-dimensional mesh generation by the finite octree technique // Int. J. for Numerical Methods in Engineering. 1991. 32. 709-749.
  8. Bloomenthal J. An implicit surface polygonizer // Graphics Gems IV. Boston: Academic Press, 1994. 324-349.
  9. Natarajan B.K. On generating topologically consistent isosurfaces from uniform samples // The Visual Computer: Int. J. of Computer Graphics. 1994. 11, N 1. 52-62.
  10. Семенихин А., Игнатенко А. Сравнительный анализ методов интерактивной триангуляции сеточных функций // Графика и мультимедиа. Вып. 6. 2004 (http://cgm.graphicon.ru/issue6/triangulation_comp/).
  11. Tavares G., Santos R., Lopes H., Lewiner T., Vieira A.W. Topological reconstruction of oil reservoirs from seismic surfaces // Proc. of the Conf. of the Int. Association for Mathematical Geology. Vol. 1. Portsmouth, 2003. 27-34.
  12. Hoppe H. Progressive meshes // Proc. of SIGGRAPH’96. New Orleans, 1996. 99-108.
  13. Evans F., Skiena S., Varshney A. Efficiently generating triangle strips for fast rendering. Technical Report. Department of Computer Science. State Univ. of New York at Stony Brook, USA, 1997.
  14. Schroeder W.J., Zarge J., Lorensen W.E. Decimation of triangle meshes // Computer Graphics. 1992. 26, N 2. 65-70.