Организация непрерывных LOD ландшафтов с использованием Адаптивных КвадроДерьев
К несчастью, выполнение геоморфинга требует хранения еще одного значения высоты для анимируемой вершины, что представляет собой реальную проблему для алгоритма адаптивных quadtre в той его реализации, которая была описана. Потребуется несколько дополнительных байтов на каждую вершину, что не так уж легко. В [3] такие данные хранятся на каждую вершину, но в [2] этого стараются избежать, так как на деле дополнительное значения высоты должно хранится лишь для вершины, которая включена в данный меш, но не для всего набора данных.
Есть три суждения по поводу геоморфинга. Первый подход - потратить дополнительную память на хранение дополнительного значения высоты для каждого меша. Второй альтернативой является улучшить алгоритм так, чтобы достигнуть действительно относительно маленьких ошибок, т.е. геоморфность просто не потребуется. К тому же согласно закону Мура вероятно это вскоре будет реализовываться на уровне hardware. Третьей альтернативой является разделить quadtree на 2 дерева: одно для хранения данных (дерево высот), второе для хранения отображаемого меша (дерево меша). В дереве высот будут хранится все высоты и предпросчитанные ошибки, но ничего из временных данных, таких как флаги включения, число ссылок, веса морфинга и так далее. При построении дерева меша можно не задумыватся об ограничениях памяти, поскольку его размер пропорционален числу деталей, отрисовывающихся в данный момент. В то же время дерево высот может сохранить немного памяти, так как оно является статическим и, таким образом, из него можно удалить множество ссылок на детей.
Кроме того такая концепция в дополнение к уменьшения требуемой памяти может увелить локальность данных и улучшить использование кэша алгоритмом.
Приложения
Работающая реализация
Графический движок Soul Rider является закрытым и вряд ли будет открыт в обозримом будущем, но я переписал основы алгоритма в качестве демонстрации для этой статьи. Эти исходники могут быть свободно использованы для изучения, экспериментов, модификации и включения в ваш собственный коммерческий/некоммерческий проект. Я лишь прошу упомянуть меня.
Я не использовал никаких запаковок данных в демо-коде. Это хорошая область для экспериментов. Также я не использовал отсечение по пирамиде видимости, но все необходимые данные доступны.
Упражнения для читателя
В дополнение к запаковке данных упомяну о некоторых других вещах, включенных в движок Soul Ride, но не включенных в демо. Одной из больших является однозначная-полноландшафтная система текстурирования (wolverene: наверное, имеется ввиду что на весь ландшафт накладывается 1 текстура), описание которой выходит за рамки данной статьи.
Другой вещью, с которой я не эксперементировал, но которую легко понять по демо-коду - это процедурная детализация по запросу. По-моему, это одно из перспективных направлений развития компьютерной графики. Просто не видно другого способа хранить и моделировать виртуальные миры в деталях достаточных для достижения богатства отображения реального мира. Я думаю что алгоритм quadtree в силу его масштабируемости может быть полезен для программистов, работающих над процедурной детализацией.
Другим полезным решением является подкачка по запросу подсекций дерева. На деле это не так сложно: просто следует завести специальный флаг для определенных подквадратов; в них будет содержаться ссылка на все гиганское поддерево, хранящееся на диске с просчитанной и хранящейся в обычном дереве максимальной ошибкой. Когда Update() старается включить "специальный" квадрат, последует пауза, подкачка данного квадрата с диска и подключение его в дерево, а затем возобновление работы Update(). Реализация этого в фоновом режиме без задержек была бы еще интерестнее, но я думаю, выполнима. В результате получим бесконечную подкачку. Процедурная детализация по запросу основана на той же самой идее: вместо того, чтобы забивать диск предподготовленными данными, вы просто запускаете алгоритм увеличения детализации на лету.
Немного больше о технологиях >>>
Электрические цепи с нелинейными преобразователями и оперативная коррекция режима энергосистемы
Рассматриваются электрические цепи с нелинейными преобразователями.
Показывается, что в такимх цепях достигается оптимум некоторой выпуклой функции
токов электрической цепи. Далее рассматривается задача оперативной коррекции
режима энергосистемы и формулируется критерий качества ...
В поисках инерцоида
Многие
века люди относились к массивным телам как своеобразным складам движения –
сколько в них вложишь, столько и вернешь. Но вот родилась дерзкая надежда
превратить склады в источники: нельзя ли так пошевелить грузами на тележке,
чтобы та поехала сама собой, за счет внутренни ...
