Сравнительно долго в представлении открытых пространств доминировала техника карт высот. Используя двухмерные изображения, каждой точке пространства могла быть задана высота рельефа в этом месте. Этот простой подход имеет очевидные ограничения, так, например, нельзя описать отвесные или нависающие скалы, пещеры, крупные валуны.

(a) (b)

Рис. 1. - Карта высот (a) и воксельные данные (b).

В противоположность этому, как видно на рис. 1, воксельные данные полностью описывают состояние каждой точки внутри заданного объёма. Соответственно, могут быть сохранены любые желаемые детали, как формы, так и содержимого. Но всё имеет свою цену. Во-первых, визуализация таких данных является нетривиальной задачей и отдельным предметом множества исследований. Во-вторых, как уже упоминалось, возникают проблемы из-за больших требований к памяти компьютера. Дело в том, что карту высот мы можем рассматривать как одно единственное изображение, тогда как воксельные данные представляют собой N таких изображений, где N - максимальная высота моделируемого объёма.

Чтобы в ряде случаев уменьшить как вычислительную нагрузку, так и количество занимаемой памяти, предлагаются различные решения, зачастую основанные на технологии SVO (Разреженное воксельное октодерево). Однако, данная технология в первую очередь предназначена для решения проблем производительности, особенно для приложений, использующих трассировку лучей. Поэтому требования к памяти остаются весьма значительными, что причисляется к одному из недостатков технологии [3, 4, 6].

Кроме того, иногда используют и аналитические методы моделирования поверхностей: комбинируя различные математические выражения, можно описать практически любую поверхность. Этот подход очень эффективен, с точки зрения затрат памяти, так как все данные о модели хранятся в виде относительно компактного аналитического описания [2]. В то же время, вычислительная сложность не позволяет применить его для приложений, работающих в реальном времени и для моделирования произвольных интерактивных ландшафтов. По этой причине предпочтение было отдано использованию воксельных данных, совместно с алгоритмом их компрессии, позволяющим оптимизировать затраты памяти.

Применение существующих алгоритмов компрессии, таких как Deflate [7, 8] оказалось неэффективным: они удобны для хранения данных на жестком диске с последующим извлечением содержимого архива перед работой. Специфика нашей задачи создает необходимость отказаться от декомпрессии в принципе: необходимо непрерывно держать данные в сжатом состоянии, но чтобы при этом были возможны операции чтения и записи.

В данной статье предлагается алгоритм произвольного доступа к сжатым данным без необходимости их декомпрессии, основанный на алгоритме группового кодирования. Его эффективность в заданной предметной области позволяет с минимальными издержками уйти от проблем перегрузки памяти вычислительной системы при использовании воксельных данных для моделирования реалистичных ландшафтов.

1. Структура представления данных

1.1 Групповое кодирование

Так как основой данной технологии является групповое кодирование (англ.run-LengthEncoding, RLE), первичными элементами данных становятся счётчики и блоки не-избыточных данных. В самом базовом алгоритме RLEединственный вид таких данных - один символ. В результате сжатые данные хранятся в формате: {<счётчик><символ>}, где счётчик - натуральное число, указывающее количество повторений символа. Очевидно, что отсутствие в исходных данных групп одинаковых символов приведёт к наихудшему результату компрессии: результат будет превышать исходный размер в два раза.

Дальнейшее развитие RLE вводит понятие пропускаемых блоков. При данном подходе отрицательные значения счётчика указывают на необходимое число пропусков. Так можно ликвидировать описанный выше недостаток, сведя потери к минимуму (1 лишний символ-счётчик на каждые 128 символов) [9, 10]. Именно такой подход подразумевается при дальнейших отсылках к RLE в этой статье.

1.2 Адаптивный размер блока