Организация непрерывных LOD ландшафтов с использованием Адаптивных КвадроДерьев
    Александр Винюков Введение: в чем проблема?
    Рендеринг ландшафтов является сложной проблемой при програмировании реалистичной графики. В настоящий момент мы находимся в интересной точке развития технологий рендеринга (т.е. "оцифровки" данных, по которым строится ландшафт), поскольку увеличившаяся пропускная способность современных видеокарт в совокупности с опубликованными исследованиями на тему алгоритмов реального времени 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) вместо регулярной сетки для представления информации о высоте. Используя это квадродерево мы можем закодировать данные с различным разрешение в различных областях. К примеру, в автосимуляторе нам требуется высокая детализация дороги и ее окресностей, в идеале до каждой выпуклости, но окружающие пустоши, по которым мы не можем ехать, можно отображать и с меньшей детализацией. Нам нужна лишь информация для генерации холмов и долин.
    Квадродерево также можно использовать и для другого подхода к решению проблемы памяти: процедурная детализация. ............