Александр Винюков
Введение: в чем проблема?
Рендеринг ландшафтов является сложной проблемой при програмировании реалистичной графики. В настоящий момент мы находимся в интересной точке развития технологий рендеринга (т.е. "оцифровки" данных, по которым строится ландшафт), поскольку увеличившаяся пропускная способность современных видеокарт в совокупности с опубликованными исследованиями на тему алгоритмов реального времени LOD meshing дают возможность современным графическим движкам отрисовывать сильно детализированные ландшафты. Тем не менее большинство используемых технологий предлагают компромис между размером ландшафта и его детализированностью.
Проблемы
Что мы хотим получить от ландшафта? Один сплошной меш, начинающийся с заднего плана и продолжающийся до горизонта без разрывов и Т-узлов. Мы хотим видеть большую область с различной детализацией, начиная от выпуклостей под ногами и заканчивая горами на горизонте. Для определенности скажем, что мы хотим оперировать размерами от 1 метра до 100000 метров с пятью уровнями детализации.
Как этого добиться? Метод решения в лоб не подойдет для средних компьютеров наших дней. Если мы заведем сетку 100000х100000 16-битных значений, и просто попытаемся ее отрисовать, то получим 2 большие проблемы. Во-первых, это проблемы треугольников - мы будет посылать до 20 млн. треугольников на каждый кадр. Во-вторых, проблема памяти - для хранения карты высот нам понадобится приблизительно 20 Гб памяти. Еще не скоро мы сможем использовать такой метод и получать хорошие результаты.
Возможно вы искали - Реферат: Окружение и локализация корня нелинейной функции действительной переменной
Лобовое решение для карты высот.
Несколько ранее опубликованных методов успешно решают проблему треугольников. Наиболее широко использующиеся - семейство рекурсивных алгоритмов [1], [2], [3] (смотрите в конце список литературы). Используя их мы можем спокойно обработать наш меш и рендерить похожий ландшафт, используя интелектуально выбираемые на лету несколько сотен треугольников из 10 милионов.
Тем не менее, все еще остается проблема памяти, так как на хранение карты высот требуется около 20 гб плюс некоторое количество на алгоритм интелектуального выбора вершин.
Одним из явных решений является уменьшение детализации путем увеличения размера ячейки. 1Kx1K является хорошим практически используемым размером карты высот. Недавно выпущенная игра TreadMarks использует набор данных 1k x 1k с великолепным эффектом [4]. К сожалению, 1k x 1k далеко от 100k x 100k. Итак, мы пришли к компромису между детализацией переднего плана и размером ландшафта.
Решение, предлагаемое в этой статье - это использовать адаптивное квадродерево (quadtree) вместо регулярной сетки для представления информации о высоте. Используя это квадродерево мы можем закодировать данные с различным разрешение в различных областях. К примеру, в автосимуляторе нам требуется высокая детализация дороги и ее окресностей, в идеале до каждой выпуклости, но окружающие пустоши, по которым мы не можем ехать, можно отображать и с меньшей детализацией. Нам нужна лишь информация для генерации холмов и долин.
Похожий материал - Реферат: Фракталы и автоколебания в геоморфосистемах
Квадродерево также можно использовать и для другого подхода к решению проблемы памяти: процедурная детализация. Идея состоит в том, чтобы определять форму ландшафта на грубом уровне и автоматически генерировать высокодетализированный ландшафт на лету вокруг точки зрения. По адаптивной природе квадродерева все эти сгенерированные детали могут быть отброшены после смены точки зрения, таким образом высвобождая память для создания процедурной детализации в другом регионе.
Алгоритм: Создание меша
Алгоритм базирован на [1], но также использовались мысли из [2] и [3]. В отличии от [1] существует несколько ключевых модификаций, но базис тот же самый, поэтому мы будем придерживатся терминологии [1].
Рендер делится на 2 части: первую называем Update(), а вторую Render(). Во время Update(), мы решаем, какие вершины включить в выводимый меш. Затем, во время Render() уже генерируем по этим вершинам треугольники. Начнем с простой сетки 3х3 для объяснения действия Update() и Render(). Во время Update() мы рассматриваем каждую из необязательных вершин и решаем, включать ли ее в меш. Следуя терминологии [1] мы говорим, что вершина будет использована в меше тогда и только тогда, когда она "включена".
Рис. 2. Сетка 3х3. Пунктирные линии и вершины необязательны для LOD ммеша.
Очень интересно - Реферат: Об энтропийной оценке сверхпластичности
Пусть центральная и угловые точки включены (из иерархии выше). Тогда задача состоит в том, чтобы вычислить для каждой из точек, лежащих на ребрах, ее состояние, руководствуясь некоторыми LOD вычислениями, основанными на точке зрения и параметрах вершины.
Как только мы узнаем, какие из вершин включены, мы можем воспользоваться функцией Render(). Это просто - мы составляем веер треугольников (triangle fan) вокруг центральной вершины, включая каждую включенную вершину по часовой стрелке. См. рис. 3.
Рис. 3. Сетка 3х3. Выключенные вершины помечены черным.
Для Update() и Render() адаптивного квадродерева мы повторяем изложенный выше процесс при помощи рекурсивного деления, начиная с сетки 3х3. В процессе деления мы можем получить новые вершины и обрабатываем их также как и вершины исходного квадрата. Но, для того чтобы избежать разрывов, мы руководствуемся несколькими следующими правилами.
Вам будет интересно - Доклад: Определение размерности Хаусдорфа фракталов с циклически повторяющимися структурами
Во первых, мы можем поделить любую комбинацию из четырех квадратов. Когда мы делим квадрант, мы обрабатываем его как подквадрат и включаем его центральную вершину. Также мы должны включить 2 лежащие на ребрах вершины родительского квадрата, которые являются углами нашего подквадрата (рис. 4). То есть включение подквадрата означает включение его четырех угловых и центальной вершины.
Рис. 4. Деление Северо-Восточного (СВ) квадранта квадрата. Про сервые вершины мы уже знаем что они включены, но черные включаются в результате деления квадрата.
Но, кроме того, вершина, лежащая на ребре подквадрата, является общей для соседнего подквадрата. Таким образом, когда мы включаем реберную вершину, надо убедится что и в соседнем подквадрате она тоже включена. Включение ее в соседнем квадрате может, в свою очередь, включить ее у нас, т.е. флаг включения должны передаватся через квадродерево. Синхронизация этих флагов у соседних квадратов необходима для обеспечения целосности меша. См. [1] для хорошего описания правил зависимости включения.
Похожий материал - Реферат: Фрактальная теория пространственно-временных размерностей
Рис. 5. Во время Update() для NE квадранта мы принимаем решение включить черную вершину. Так как эта вершина общая с SE квадрантов (помеченным серым), то мы должны включить этот квадрант тоже. Включение SE вкадранта в свою очередь заставит нас включить помеченные серым вершины.
После того как мы закончим с Update() мы можем вызвать Render(). Рендер очень прост - все вычисления по сохранению целостности меша уже были выполнены в Update(). Идея, на которой основан Render() - это рекурсивный вызов Render для включенных подквадратов и затем отрисовка всех треугольников квадрата, которые не были покрыты включенными подквадратами.
Рис 6. Пример меша. Включенные вершины помечены черным. Серые треугольники отрисованы во время рекурсивного вызова Render() для сопоставленных им подквадратов. Белые треугольники отрисоввываются во время изначального вызова Render() для этого квадрата.
Алгоритм: Обработка вершин и квадратов