Compression of triangulation topological relations

Authors

  • A.V. Skvortsov

Keywords:

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

Abstract

The problem on packing topological relations of triangles of triangulation is considered. Several modifications of an algorithm for triangle shelling is proposed. On the average, these modifications allow one to achieve the packing density of order 2.12 bits per a triangulation node.

New computational technologies

Downloads

Published

2002-04-05

Issue

Vol. 3 (2002): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biography

A.V. Skvortsov

Tomsk Polytechnic University,
Institute of Applied Mathematics and Computer Science

References

  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.