Общий подход к реализации методов построения триангуляций неявно заданных поверхностей, использующих разбиение пространства на ячейки

Авторы

  • А.Ю. Дижевский

Ключевые слова:

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

Аннотация

Описаны наиболее популярные алгоритмы триангуляции трехмерных объектов, разбивающие пространство на кубические и тетраэдрические ячейки. В работе предлагается общий подход к построению триангуляции трехмерных объектов, использующий разбиение пространства на произвольные ячейки. Представлена реализация данного подхода на примере новых методов триангуляции, разбивающих пространство на пирамиды и призмы. Приведены особенности реализации всех описанных методов. Выполнен сравнительный анализ качества получаемых триангуляций.

Новые вычислительные технологии

Загрузки

Опубликован

2007-10-10

Выпуск

Том 8 (2007): Выпуск 3.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

А.Ю. Дижевский

Московский государственный университет имени М.В. Ломоносова,
механико-математический факультет
Ленинские горы, 119899, Москва

Библиографические ссылки

  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.