Прогрессивное безошибочное сжатие произвольных симплициальных комплексов

В последние годы были разработаны эффективные алгоритмы сжатия геометрических данных, однако главным образом они предназначены для замкнутых полигональных поверхностей, являющихся многообразиями или «почти многообразиями». В данной работе предлагается прогрессивная схема сжатия геометрии, способная обрабатывать как модели-многообразия, так и «наборы треугольников» и трёхмерные тетраэдральные сетки. Метод является безошибочным после завершения декомпрессии, что исключительно важно в таких областях, как медицина и метод конечных элементов. В то время как большинство существующих методов нумерует вершины сетки в порядке, зависящем от её связности, мы используем технику kd-дерева [Devillers and Gandoin 2000], не зависящую от связности. Затем мы вычисляем согласованную последовательность сеток, которую можно кодировать с помощью расширения рёбер [Hoppe et al. 1993] и расщепления вершин [Popović and Hoppe 1997]. Основные результаты работы включают идею использования кодирования геометрии с помощью kd-дерева для построения последовательности сеток; усовершенствованное кодирование расширения рёбер и расщепления вершин, поскольку вершины, подлежащие расщеплению, задаются неявно; схему предсказания, уменьшающую код для симплексов, инцидентных расщепляемой вершине; а также новое обобщение операции расширения рёбер на тетраэдральные сетки.