Сравнительный анализ алгоритмов разбиения трехмерных сцен на деревья графических примитивов

Статья будет интересна всем разработчикам программ для трёхмерной визуализации, а особенно трёхмерной визуализации данных ГИС. Алгоритмы, рассмотренные в этой статье, часто применяются на практике. Но сложно выбрать, какой алгоритм лучше подходит для работы с конкретным набором данных, и как лучше реализовывать выбранный алгоритм.

В этой работе рассмотрены алгоритмы увеличения скорости вывода трёхмерных изображений на экран интерактивной системы ГИС - алгоритмы широко применяющегося октарного дерева [3], бинарного, и их модификаций. Описаны нюансы модификаций алгоритмов для работы с пространственными данными ГИС. Проведено сравнение алгоритмов по основным показателям работы, даны рекомендации по применению.

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

Введение

Современные исследовательские задачи, которые решаются с помощью ГИС программ становятся слишком сложными для понимания [6] - поэтому ведущие разработчики ГИС программ стараются реализовать в своих программах трёхмерную визуализацию.

Так как ГИС приложения работают с большим количеством визуализируемых данных, поэтому для любого приложения ГИС всегда актуальна задача минимизации времени перерисовки трёхмерной сцены. Обычно скорость перерисовки сцены измеряется количеством кадров в секунду (FPS - frames per second) . Существует несколько основных подходов, чтобы повысить FPS:
оптимизация существующих и изобретение более быстрых алгоритмов;
использование современной графической аппаратуры [5].

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