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