Геометрическое сжатие посредством топологической хирургии

Обилие и важность сложных трехмерных баз данных в основных сегментах промышленности, доступность интерактивной трехмерной визуализации для офисного и потребительского применения, а также использование Интернета для распространения и совместного использования трехмерных данных усилили потребность в эффективной технологии геометрического сжатия трехмерных данных, которая могла бы значительно сократить время передачи трехмерных моделей по цифровым каналам связи и объем памяти или дискового пространства, необходимый для их хранения. Поскольку преобладающим представлением трехмерных моделей в графике является полиэдральное, а полиэдральные модели для визуализации обычно триангулируются, в статье предлагаются новое сжатое представление сложных триангулированных моделей и простые, но эффективные алгоритмы сжатия и распаковки. В рамках этой схемы положения вершин квантуются с заданной точностью, а для предсказания положения каждой вершины используются от 2, 3 или 4 ее предков в остовном дереве вершин; векторы поправок кодируются энтропийным методом. Атрибуты, такие как нормали, цвета и текстурные координаты, сжимаются аналогичным образом. Связность кодируется без потери информации со средним расходом менее двух бит на треугольник. Остовное дерево вершин и небольшой набор ребер-переходов используются для разбиения модели на простой многоугольник. Для кодирования триангуляции многоугольника применяются остовное дерево треугольников и последовательность марширующих битов. Наш подход превосходит пионерские результаты Майкла Диринга за счет использования геометрической корреляции нескольких предков в остовном дереве вершин, сохранения связности без потери информации, исключения повторений вершин и сокращения затрат на кодирование связности примерно на три бита. Однако, поскольку распаковка требует произвольного доступа ко всем вершинам, этот метод необходимо модифицировать для аппаратной визуализации с ограниченным объемом встроенной памяти. Наконец, мы демонстрируем результаты реализации для различных моделей VRML, содержащих до двух или...