Реферат: Организация непрерывных LOD ландшафтов с использованием Адаптивных КвадроДерьев

· 5 высот (углы и центр)

· 6 значений ошибок (вершины на восточном и южном ребрах и 4 подквадрата)

· 2 счетчика включенных подквадратов (для вершин на восточном и южном ребрах)

· 8 1-битовых флагов включения (по 1 для каждой вершины и каждого подквадрата)

· 4 указателя на подквадраты

· 2 значения высоты для минимального/максимального вертикального размера

· 1 1-битный флаг, показывающий что этот квадрат не может быть удален.

В зависимости от нужд приложения значения высот могут быть комфортно упакованы в 8 или 16 бит. Значения ошибок могут использовать тот же самый формат, но, используя нелинейное сжатие вы можете запаковать их еще больше. Все счетчики ссылок и статистический флаг поместятся в 1 байт. Флаги включения тоже пакуются в 1 байт. Размер указателей на подквадраты зависит от максимального числа узлов, которые могут быть использованы. Обычно это сотни или тысячи, так что я использую 20 бит на каждый указатель как минимум. Минимальное и максимальное значения высоты тоже могут быть сжаты различными способами, но 8 бит на каждый выглядит разумным минимумом. Все вместе это занимает 191 бит (24 байта) на квадрат при 8-битных значениях высоты. 16-битные значения высот требуют 29 байтов. 32-байтный размер размер квадрата выглядит хорошей целью для бережливой реализации. 36 байтов я вынужден использовать, так как я не пытался упаковывать указатели на подквадраты. Другой трюк - использовать фиксированный массив с заменой алокаторов для quadsquare::new и quadsquare::delete. Это сжимает 4 байта накладных расходов стандартного для С++ аллокатора (как я предполагаю) до 1 бита.

Существует много трюов и схем компресии для того чтобы сжать данные еще сильнее, но они увеличивают сложность и уменьшают производительность. В любом случае, 36 байтов на 3 вершины не совсем плохо. Это 12 байтов на вершину. В [1] было достигнуто 6 байтов на вершину.

С одной стороны это очень много, но с другой стороны адаптивная структура quadtree позволяет хранить разреженные данные в ровных областях или областях, для которых не требуется высокая детализация. В то же время в высоко важных областях можно достигнуть высокой детализации; к примеру, в той же игре-автосимуляторе можно хранить даже неровности и рытвины на дороге.

Особенности: Геоморфинг

[2] и [3] также используют морфинг вершин или, по другому, геоморфинг. Идея в том, что при включении вершин получаются резкие скачки между предыдущим мешом, в котором данная вершина была отключена и отрисованным в данном кадре, в котором вершина была включена. Для того, чтобы избавится от этого эффекта применяется плавная анимация из интерполированного положения вершины в ее настоящее значение. Это отлично выглядит и устраняет неприятные эффекты скачков, смотри McNally's TreadMarks для хорошей иллюстрации данного метода.

К несчастью, выполнение геоморфинга требует хранения еще одного значения высоты для анимируемой вершины, что представляет собой реальную проблему для алгоритма адаптивных quadtre в той его реализации, которая была описана. Потребуется несколько дополнительных байтов на каждую вершину, что не так уж легко. В [3] такие данные хранятся на каждую вершину, но в [2] этого стараются избежать, так как на деле дополнительное значения высоты должно хранится лишь для вершины, которая включена в данный меш, но не для всего набора данных.

Есть три суждения по поводу геоморфинга. Первый подход - потратить дополнительную память на хранение дополнительного значения высоты для каждого меша. Второй альтернативой является улучшить алгоритм так, чтобы достигнуть действительно относительно маленьких ошибок, т.е. геоморфность просто не потребуется. К тому же согласно закону Мура вероятно это вскоре будет реализовываться на уровне hardware. Третьей альтернативой является разделить quadtree на 2 дерева: одно для хранения данных (дерево высот), второе для хранения отображаемого меша (дерево меша). В дереве высот будут хранится все высоты и предпросчитанные ошибки, но ничего из временных данных, таких как флаги включения, число ссылок, веса морфинга и так далее. При построении дерева меша можно не задумыватся об ограничениях памяти, поскольку его размер пропорционален числу деталей, отрисовывающихся в данный момент. В то же время дерево высот может сохранить немного памяти, так как оно является статическим и, таким образом, из него можно удалить множество ссылок на детей.

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

Приложения

Работающая реализация

Графический движок Soul Rider является закрытым и вряд ли будет открыт в обозримом будущем, но я переписал основы алгоритма в качестве демонстрации для этой статьи. Эти исходники могут быть свободно использованы для изучения, экспериментов, модификации и включения в ваш собственный коммерческий/некоммерческий проект. Я лишь прошу упомянуть меня.

Я не использовал никаких запаковок данных в демо-коде. Это хорошая область для экспериментов. Также я не использовал отсечение по пирамиде видимости, но все необходимые данные доступны.

Упражнения для читателя

В дополнение к запаковке данных упомяну о некоторых других вещах, включенных в движок Soul Ride, но не включенных в демо. Одной из больших является однозначная-полноландшафтная система текстурирования (wolverene: наверное, имеется ввиду что на весь ландшафт накладывается 1 текстура), описание которой выходит за рамки данной статьи.

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

Другим полезным решением является подкачка по запросу подсекций дерева. На деле это не так сложно: просто следует завести специальный флаг для определенных подквадратов; в них будет содержаться ссылка на все гиганское поддерево, хранящееся на диске с просчитанной и хранящейся в обычном дереве максимальной ошибкой. Когда Update() старается включить "специальный" квадрат, последует пауза, подкачка данного квадрата с диска и подключение его в дерево, а затем возобновление работы Update(). Реализация этого в фоновом режиме без задержек была бы еще интерестнее, но я думаю, выполнима. В результате получим бесконечную подкачку. Процедурная детализация по запросу основана на той же самой идее: вместо того, чтобы забивать диск предподготовленными данными, вы просто запускаете алгоритм увеличения детализации на лету.

И еще одной интересной работой было бы обнаружение узких мест в алгоритме.

Список литературы

[1] Peter Lindstrom, David Koller, William Ribarsky, Larry F. Hodges, Nick Faust and Gregory A. Turner. "Real-Time, Continuous Level of Detail Rendering of Height Fields". In SIGGRAPH 96 Conference Proceedings, pp. 109-118, Aug 1996.

[2] Mark Duchaineau, Murray Wolinski, David E. Sigeti, Mark C. Miller, Charles Aldrich and Mark B. Mineev-Weinstein. "ROAMing Terrain: Real-time, Optimally Adapting Meshes." Proceedings of the Conference on Visualization '97, pp. 81-88, Oct 1997.

[3] Stefan Rцttger, Wolfgang Heidrich, Philipp Slusallek, Hans-Peter Seidel. Real-Time Generation of Continuous Levels of Detail for Height Fields. Technical Report 13/1997, Universitдt Erlangen-Nьrnberg.

[4] Seumas McNally. http://www.longbowdigitalarts.com/seumas/progbintri.html This is a good practical introduction to Binary Triangle Trees from [2]. Also see http://www.treadmarks.com/, a game which uses methods from [2].

[5] Ben Discoe, http://www.vterrain.org/ . This web site is an excellent survey of algorithms, implementations, tools and techniques related to terrain rendering.