КОМПЬЮТЕРНАЯ ГРАФИКА
УДК 681.3.06
АДАПТИВНАЯ ТРИАНГУЛЯЦИЯ ЛАНДШАФТА С ПРЕДСТАВЛЕНИЕМ КВАДРАДЕРЕВА ВЕРШИННОЙ ТЕКСТУРОЙ И ВЕЙВЛЕТ-ОЦЕНКОЙ ЗНАЧИМОСТИ ВЕРШИН
© 2008 г. Е. А. Юсов, В. Е. Турлапов
Нижегородский государственный университет 603950 Нижний Новгород, пр. Гагарина, 23 E-mail: yusov-egor@mail.ru, vadim.turlapov@cs.vmk.unn.ru Поступила в редакцию 11.09.2006 г.
Предлагается метод аппаратнореализуемой адаптивной триангуляции ландшафта (ААТЛ), основанный на оценке статической погрешности узлов квадрадерева с помощью вейвлет-преобразований и представлении итогового квадрадерева вспомогательной вершинной текстурой. Характерными особенностями метода ААТЛ являются следующие: соседние узлы порождаемой алгоритмом адаптированной сетки могут отличаться на любое число уровней иерархии; процесс триангуляции не ограничен размерами сегмента разбиения, что решает проблему сшивки сегментов без вставки дополнительных узлов; многомасштабное представление рельефа, используемое методом, позволяет хранить уровни детализации в памяти графического процессора как многоуровневую вершинную текстуру, благодаря чему наиболее ресурсоемкая часть алгоритма эффективно реализуется в вершинном шейдере.
Алгоритм учитывает при построении триангуляции как локальные особенности поверхности, так и положение камеры, естественным образом поддерживает геоморфинг.
1. ВВЕДЕНИЕ
Высококачественная визуализация земной поверхности в реальном времени является необходимым требованием при создании имитационно-тренажерных комплексов наземного и летного транспорта, геоинформационных систем [1], компьютерных игр и других приложений компьютерной графики. Часто рельеф задан картой высот такого большого объема, что отображение ее в полном разрешении в реальном времени невозможно даже на самых мощных графических картах. Поэтому для оптимизации вывода ландшафта используют специальные алгоритмы, позволяющие динамически контролировать уровень детализации различных участков поверхности с учетом ее локальных особенностей и положения камеры в пространстве. В [2] и [3] перечислены требования, которым должна удовлетворять система визуализации ландшаф-
та. Наиболее значимые среди них: минимальная избыточность полученной триангуляции, исключение разрывов в геометрии и текстуре, отсутствие влияния локальных особенностей местности на общую сложность модели, использование межкадровой когерентности (схожести кадров, следующих непосредственно друг за другом). К данному списку следует добавить еще одно весьма важное требование: метод должен учитывать особенности современных графических процессоров и иметь эффективную реализацию, позволяющую наиболее полно использовать все предоставляемые ими возможности.
2. ОБЗОР РАБОТ
Обзоры общих методов управления уровнем детализации геометрических моделей представлены в работах [4, 5].
Наиболее просты в реализации алгоритмы, основанные на методе регулярного прореживания ([1, 3, 6]). Однако они порождают слишком избыточную модель, так как уровень детализации контролируется только на уровне целого блока. Другой подход к управлению уровнем детализации основан на использовании прогрессивных сеток [7, 8]. Подобные методы могут применяться к объекту, заданному произвольным набором вершин и треугольников. Однако они весьма сложны в реализации и требуют очень высоких вычислительных затрат. И поэтому, даже несмотря на то, что они порождают минимально избыточную триангуляцию, общей производительности системы визуализации ландшафта оказывается недостаточно для их использования в реальном времени [3].
Наиболее хорошо для решения задачи упрощения ландшафта зарекомендовали себя алгоритмы, использующие иерархические структуры данных. Среди этих методов можно выделить два основных направления. Первое из них - это алгоритмы, основанные на квадрадеревьях вершин [2, 9, 10, 11]. Квадрадерево, построенное по предлагаемой в данных работах схеме, включает в себя только узлы исходной карты высот. Последняя оказывается разбитой на подмножества узлов, составляющие различные уровни детализации. В результате узлы, принадлежащие различным уровням приближения, оказываются перемешанными, что затрудняет их эффективное разделение и, как следствие, хранение, подкачку по мере надобности и т.д. Кроме того, для исключения разрывов в триангуляции на дерево накладывается следующее ограничение: уровни детализации соседних узлов не должны отличаться более чем на 1 (иногда на 2).
Второе направление - алгоритмы, основанные на бинарных деревьях треугольников [12, 13]. Однако этим алгоритмам свойственны те же недостатки - затрудненное разделение масштабов приближения и ограничения, накладываемые на дерево. Достаточно подробный обзор различных алгоритмов упрощения на основе квадрадеревь-ев проведен в [14].
В [15] и [16] представлен близкий к предлагаемому в нашей работе подход, основанный на применении вейвлет-анализа и квадрадеревь-ев. Согласно предложенному авторами [15, 16]
методу, узлам дерева соответствуют квадратные ячейки, вершинами которых являются узлы исходной сетки высот. Уровень детализации ячейки определяется на основе анализа значений вейвлет-коэффициентов, а триангуляция производится отдельно для каждой ячейки путем просмотра специального словаря возможных соединений. При этом авторы накладывают ограничение: уровни детализации соседних ячеек должны отличаться не более, чем на 2.
В работах [17, 18] представлены методы, использующие вершинные текстуры. Их достоинством является то, что они практически все операции переносят на графический процессор, почти полностью освобождая основной. Однако триангуляция, порождаемая методами, никак не учитывает локальные особенности поверхности, а основана исключительно на положении камеры в пространстве и, как следствие, оказывается недостаточно адекватной.
Метод, предлагаемый в данной работе, основан на алгоритме, представленном в [19]. Для получения адаптированной триангуляции описанный метод строит иерархию сеток с уменьшающимся уровнем детализации (разрешением). Граф соответствия вершин сеток разного уровня является квадрадеревом. Построение адаптивной сетки заключается в том, что у изначально сбалансированного (все листовые вершины являются вершинами исходной сетки) квадрадерева по некоторому критерию исключается часть поддеревьев (такие поддеревья называются нуль-поддеревьями). Сетка, вершинам которой соответствуют листовые вершины такого квадродерева, и является исходной адаптивной сеткой. Иерархию сеток предлагается строить с помощью двумерного вейвлет-преобразования. Получаемые в процессе преобразования вейвлет-коэффициенты используются для определения значимости вершин и отсечения нуль-поддеревьев. В работе также предложен способ триангуляции полученного оптимального набора вершин.
Среди отечественных публикаций также следует отметить работы [2, 20].
3. ОПИСАНИЕ МЕТОДА
Новый метод, предлагаемый в данной работе, является развитием подхода, представленного в [19], и основан на применении вейвлет-
преобразования к исходной карте высот. Алгоритм, предложенный в [19], предназначался только для оптимизации сетки на этапе предпод-готовки путем удаления из нее незначащих вершин и не рассчитан на работу в реальном времени. Он никак не учитывает положение камеры в пространстве и поэтому не может быть использован для динамической визуализации ландшафта.
Отличительной особенностью метода ААТЛ является то, что триангуляция строится не только на узлах исходной сетки, но также и на дополнительных узлах, получаемых путем усреднения координат исходных узлов. Второе существенное отличие заключается в том, что на дерево не накладывается никаких ограничений, и триангуляция может быть построена по любому набору вершин.
Вейвлет-преобразование позволяет естественным образом построить иерархию уровней приближения карты высот, соответствующую квад-радереву. Однако использование дополнительных узлов повышает затраты памяти и время загрузки вершин в память видеокарты.
Новые возможности в реализации метода открывают сегодня вершинные текстуры (vertex textures), появившиеся в вершинных шейдерах, начиная с версии 3.0. Они позволяют хранить и обрабатывать дополнительные вершины старших уровней приближения рельефа, подобно старшим уровням детализации (LOD) текстуры. Различные уровни детализации поверхности реализуются при этом на основе соответствующих уровней детализации вспомогательной текстуры.
Использование вспомогательной текстуры позволяет реализовать многомасштабное квадра-дерево рельефа с вейвлет-коэффициентами (статической погрешностью) аппаратно с помощью вершинных текстур в вершинном шейдере.
3.1. Построение дерева вершин
Дерево вершин строится на исходной сетке высот, имеющей размеры 2n х 2n узлов и образующей n-ый, самый нижний уровень дерева (считается, что дерево растет вниз). Вся сетка разбивается на квадратные ячейки по 2 х 2 узла, составленные из четырех соседних вершин, и в центре каждой ячейки размещается новый узел. Этот новый узел считается родителем четырех узлов ячейки, а сами узлы - его потом-
^^ Уровень 0 (корень)
^ Уровень 1
О Уровень 2
Рис. 1. Трехуровневое квадрадерево.
ками. Координаты каждого центрального узла ячейки определяются путем усреднения координат его потомков. Описанным способом формируется п — 1 уровень квадрадерева, являющийся сеткой из 2п-1 х 2п-1 узлов. Аналогично получаются п — 2-ой, п — 3-ий уровни, и так далее до нулевого, содержащего единственную корневую вершину. Каждый следующий уровень иерархии является огрубленной версией нижележащего, таким образом, формируется многомасштабное представление ландшафта. В терминологии вейвлет-преобразований сетка, образующая г-ый уровень дерева, называется сигналом разрешения г. На рис. 1 представлено трехуровневое дерево, построенное на сетке 4 х 4 узла.
3.2. Выделение множества наиболее значимых вершин при помощи вейвлет-преобразования
3.2.1. Структура вейвлет-разложения сигнала
Вейвлет-преобразование - это разложение сигнала по системе функций, являющихся сдвинутыми и масштабированными копиями одной функции - порождающего вейвлета. Распр
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.