Compression of triangulation topological relations

Authors

  • A.V. Skvortsov Tomsk Polytechnic University

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.

Author Biography

A.V. Skvortsov

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.

Published

05-04-2002

How to Cite

Скворцов А.В. Compression of Triangulation Topological Relations // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2002. 3. 124-132

Issue

Section

Section 1. Numerical methods and applications