Организация непрерывных LOD ландшафтов с использованием Адаптивных КвадроДерьев
Рис. 8. Каждая реберная вершина имеет 4 соседних подквадрата, которые используют ее как угловую. Если любой из этих квадратов включен, то и вершина должна быть включена. К примеру, черная вершина должна быть включена если включен один из серых квадратов.
Таким образом выключающий тест очень прост: если вершина включена, число ссылок равно 0 и vertex test для текущей точки камеры возвращает false, выключаем вершину. Иначе не трогаем ее. Условия выключения квадрата тоже довольно прямолинейны: если квадрат включен и он не корень дерева, и нет включеных реберных вершин и нет включеных подквадратов, квадрат проваливает BoxTest, выключаем его.
Особенности: Память
Очень важной чертой этого или любого другого LOD метода является потребление памяти. В полном quadtree один квадрат эквивалентен трем вершинам обычной сетки высот, так что требуется сделать структуру квадрата как можно компактнее. К счастью, Render() и Update() методы не требуют от каждого квадрата информации по всем 9 вершинам. Вот список требуемых данных:
· 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 для хорошей иллюстрации данного метода.
Немного больше о технологиях >>>
Изо всех лошадиных сил
В 1765 году англичанин Джеймс Уатт изобрел паровую
машину, положив начало длинной цепочке инноваций в двигателестроении. В 1860
году французский механик Этьен Ленуар разрабатывает первый поршневой двигатель
внутреннего сгорания. В 1889 году швед Карл Густав Патрик Лаваль, соверш ...
Эволюционный миф и современная наука
– "Дарвин был неправ... Теория
эволюции, возможно, самая страшная ошибка, совершенная в науке".
Эту мысль не так давно высказал член нью-йоркской
Академии наук И.Л.Коэн 1. В своем мнении Коэн далеко не одинок: Джон Вольфган
Смит – профессор орегонского Университета ...
