Сжатие топологических связей триангуляции

Авторы

  • А.В. Скворцов

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

триангуляция Делоне
вычислительная устойчивость
вычислительная геометрия
машинная графика
геоинформационные системы
многоугольники
триангуляционные модели

Аннотация

Рассматривается задача упаковки топологических связей треугольников в триангуляции. Приводится несколько модификаций алгоритма шелушения треугольников, позволяющих достичь в среднем плотности упаковки порядка 2.12 бит на узел триангуляции.

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

Загрузки

Опубликован

2002-04-05

Выпуск

Том 3 (2002): Выпуск 1.

Раздел

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

Автор

А.В. Скворцов

Томский государственный университет,
Институт прикладной математики и компьютерных наук
пр. Ленина, 3, 634050, г. Томск

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

  1. Кнут Д. Искусство программирования для ЭВМ. 2. Получисленные алгоритмы. М.: Мир, 1977.
  2. Кнут Д. Искусство программирования для ЭВМ. 3. Сортировка и поиск. М.: Мир, 1978.
  3. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989.
  4. Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование. 2002. 3, № 1. 18-43 (http://num-meth.srcc.msu.su).
  5. Chow M.M. Optimized geometry compression for real-time rendering // IEEE Visualization Proceedings. Phoenix. 1997. 347-354.
  6. Deering M. Geometry compression // Computer Graphics. Proceedings of ACM SIGGRAPH. Los Angeles. 1995. 13-20.
  7. Evans F., Skiena S., Varshney A. Optimizing triangle strips for fast rendering // IEEE Visualization Proceedings. San Francisco. 1996. 319-326.
  8. De Floriani L., Magillo P., Puppo E. Compressing triangulated irregular networks // Geoinformatica. 2000. 1, N 4. 67-88.
  9. Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Transactions on Information Theory. 1977. 23, N 3. 337-343.