Организация безперервних LOD ландшафтів з допомогою Адаптивних КвадроДерьев

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

Александр Винюков.

Введение

: у яких проблема?

Рендеринг ландшафтів є проблемою при програмировании реалістичною графіки. Нині ми знаходимось у цікавою точці розвитку технологій рендеринга (тобто. «оцифровки «даних, якими будується ландшафт), оскільки увеличившаяся пропускну здатність сучасних відеокарт разом із опублікованими дослідженнями на задану тему алгоритмів реального часу LOD meshing дають можливість сучасним графічним движкам отрисовывать сильно деталізовані ландшафти. Проте він менш більшість використовуваних технологій пропонують компромис між розміром ландшафту та її детализированностью.

Проблемы

Что ми хочемо одержати від ландшафту? Один суцільний меш, який з заднього плану і триває до горизонту без розривів і Т-узлов. Ми ще хочемо бачити велику область з різноманітною деталізацією, починаючи з опуклостей під ногами і до горами на обрії. Для визначеності скажімо, що хочемо оперувати розмірами від 1 метри до 100 000 метрів із п’ятьма рівнями деталізації.

Как цього досягти? Метод рішення на лоб не підійде для середніх комп’ютерів нашого часу. Якщо ми Заведемо сітку 100 000×100 000 16-битных значень, і спробуємо її отрисовать, одержимо 2 великі проблеми. По-перше, це проблеми трикутників — ми слатиме до 20 млн. трикутників за кожен кадр. По-друге, проблема пам’яті - для зберігання карти висот нам знадобиться приблизно 20 Держбезпеки пам’яті. Ще нескоро зможемо використовувати такий метод і реально отримувати хороші результати.

.

Лобовое рішення для карти высот.

Несколько раніше опублікованих методів успішно вирішують проблему трикутників. Найширше які використовуються — сімейство рекурсивних алгоритмів [1], [2], [3] (дивіться наприкінці список літератури). Використовуючи ми їх можемо спокійно обробити наш меш і рендерить схожий ландшафт, використовуючи интелектуально обирані на льоту кілька сотень трикутників з десяти милионов.

Тем щонайменше, залишається проблема пам’яті, так як у зберігання карти висот потрібно близько 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 () при цьому квадрата.

Алгоритм: Обробка вершин і квадратів

Перейдем до самого вирахування — чи справді вершина бути включена. На це є кілька методів. Усі, що їх звернув увагу, називаються «vertex interpolation error «(помилка інтерполяції вершини), чи, коротше, vertex error. Це відмінність між заввишки вершини і заввишки ребра в трикутнику, який апроксимирует вершину, коли та виключена (Рис. 7). Вершини з більшою помилкою повинні прагнути бути краще вершин з маленької помилкою. Інший варіант грунтується на растоянии вершини від погляду. Інтуїтивно, маючи 2 вершини з однаковим помилкою ми маєте вибрати більш близьку.

.

Рис. 7. Vertex interpolation error. Коли вершина включена чи виключена, меш меняяет форму. Максимальне зміна, получающееся включення вершини показано пунктирною лінією. Величина зміни є відмінність між реальної заввишки вершини (чорна точка) і заввишки ребра під нею (біла точка). Біла точка — це середина між 2 сірими точками. (Wolverene: Середина — адже ми розглядаємо измельчающиеся квадрати в quadtree і край розподілу лежить рівно посередине).

Также є інші впливають чинники. Приміром, в [1] береться до уваги напрям між вершиною і думками. Ідея залежить від screen space error (екранної помилці) — інтуїтивно vertex error менш видимою що більш вертикально дане напрям. У [1] описана всі ці математика докладно.

Но мені здається що screen space error є хорошою метрикою з двох причин: по-перше, він ігнорує текстурную перспективу і depth buffering errors — навіть якщо вершина не рухається на екрані, т.к. вона зсувається суворо пенпердикулярно к/от погляду, Z значення впливає корекцію перспективи як і і depth-buffering. По-друге, думка прямо вниз є як легким випадком для LOD ландшафтів, не типовим випадком.

На погляд, немає сенсу оптимізувати для нетипового легкого випадку. Випадок, коли вісь зору більш горизонтальна і більшість ландшафту видимою визначає найменший framerate, і, отже, ефективність алгоритму.

Вместо screen-space geometric error я пропоную робити такий тест в тривимірному просторі з помилкою пропорційної дистанції. Він містить лише 3 величини: L1 норму вектора між вершиною і думками, vertex error і константный «поріг деталізації «(Threshold).

Vertex test:

L1 = max (abs (vertx — viewx), abs (verty — viewy), abs (vertz — viewz));

enabled = error * Threshold < L1;

На практиці використання L1 норми означає велику глибину ділень вздовж діагоналей горизонтальній площині ландшафту. Не зміг помітити даний ефект оком, отже мені здається що питання стоїть тривожитися. [4] та інші використовують view-space-z замість L1 норми, що теоретично є навіть більше правильним ніж справжня дистанція між вершиною і думками. Попри це, L1 по-моєму працює найкращим способом мислення й в [3] вона також використовується.

Можно використовувати Threshold як регулятор підстроювання скорость/качество, але має усталеного геометричесой інтерпретації. Грубо кажучи, воно означає: для даного растояния z, гіршій помилкою з котрою буду мириться буде z / Threshold. Звісно, ви можете зробити деякі обчислення кута зору зв’язати Threshold з максимальною пиксельной помилкою, але ніколи не розглядав більш ніж значення для підстроювання відносини качество/скорость.

Вот так працює включення вершин. Але чому є важливішим, як працює включення подквадратов під час Update ()? Відповіддю є box test. Він задає таке запитання: розглядаємо вирівняний по осях 3D Box, у якому ділянку ландшафту (тобто. елемент quadtree), і Бог знаємо соответвующую йому максимальну vertex error всіх вершин всередині. Чи може vertex enable test повернути істину для будь-якої вершини від цього квадрата? Якщо можна, то ділимо.

Прелесть цього методу тому, що роблячи BoxTest ми можемо відразу відсікти тисячі вершин. Це Update () повністю масштабируемым: вартість їх залежить від розміру всього набору даних, а лише від розміру даних, включених в поточний LOD меш. І, як побічне явище, предпросчитанный вертикальний розмір Bounding Box може использоватся для frustim culling. (примітка wolverene — координати x і z ми знаємо з вибору квадрата як елемента quadtree, тобто. для побудови BoundBox потрібно знати лише вертикальний її розмір).

Box Test консервативний тому що вершина, через якої Box Test повернув «Так «(тобто. необхідність розподілу) може перебуває в боці bound box від ближньої до точки зору боку bound box, отже, сама вершина може цей тест провалити. Але насправді це не тягне великих накладних витрат — кілька box test і vertex test.

Box test має такий вигляд, дуже схожий на VertexTest:

Box test:

bc[x, y, z] == coordinates of box center.

ex[x, y, z] == extent of box from the center (i.e. ½ the box dimensions).

L1 = max (abs (bcx — viewx) — exx, abs (bcy — viewy) — exy, abs (bcz — viewz) — exz).

enabled = maxerror * Threshold < L1.

Особенности: Детали.

В попередньому розділі було описано суть алгоритму, але залишено осторонь маса деталей, деякі з них є ключовими. По-перше, де, власне зберігається інформацію про висоті? У попередніх алгоритми існувала регулярна сітка висот, де неявно [1] & [3] чи явно [3] визначався меш. Головною інновацією у моїй методі і те, що дані зберігаються власне в адаптивном quadtree. У результаті дістаємо 2 головні вигоди. По-перше, дані розташовуються адаптивно відповідно до тієї їх частиною, що потрібна додатку; в такий спосіб менше даних належить до згладженої частини ландшафту, у передбачається перебування камери. По-друге, дерево може динамічно зростати чи зменшаться залежно від перебування погляду спостерігача; процедурна деталізація то, можливо додана на льоту у регіоні, де знаходиться камера і потім видалена, щойно камера залишить даний регіон.

Для здобуття права зберігати інформацію про висотах кожен елемент quadtree повинен зберігати інформацію про висоті своєї центральної вершини і по крайнього заходу двох вершин, лежачих на ребрах. Всі інші висоти зберігаються у сусідніх вузлах дерева. Приміром, висота кутових вершин приходить із батьківського квадрата та її сусідів. Решта висоти реберних верших зберігаються у сусідніх квадратах. У поточній реалізації я зберігаю висоту центральної вершини і всі 4 висоти реберних вершин. Це спрощує роботу поза рахунок зарплати, що необхідних обробки квадрата дані доступні як дані квадрата чи параметри функції. Недоліком і те, кожна реберна точка зберігається до дереві двічі.

Так ж у поточної реалізації один і той ж quadtree використовується для зберігання висоти й у побудови меша. Узагалі-то було його розділити на 2 — одне для зберігання карти висот, друге для побудови меша. Потенційні принади такий підхід викладено нижче.

Большинство трюків реалізації грунтується загальних для двох сусідніх квадратів реберних вершин. Приміром, таке питання — який квадрат має виконувати vertex-enable test для реберної вершини? Моя відповідь — кожен квадрат перевіряє лише свої південну і східну реберні вершини і потрібно було на перевірки північного і західного сусіда для перевірки двох інших вершин.

Другой интерестный питання — чи потрібно нам скидати все прапори перед Update () або ж продовжувати зі станом, які залишилися від попереднього циклу отрисовки? Моя відповідь — продовжуємо роботу від попереднього стану, як і [2], але як в [1] і [4]. Це призводить до більшої деталізованості - ми перевіряли умови вмикання, але ми можемо вимкнути вершину чи квадрат? Як ми пам’ятаємо з алгоритму Update () включення вершини змушує включиться залежні від неї вершини, тощо з дерева. Не можемо так просто вимкнути вершину у середині одній з таких ланцюгів залежностей, якщо вершина залежить від якась інша включеної вершини. Інакше в нас вийдуть розриви в меше, або важливі включені вершини ні отрисованы.

На рис. 8 видно що реберна вершина має 4 сусідніх квадрата, що використовують її як кутову вершину. Якщо будь-якій з цих подквадратов включений, має бути включена дана вершина. Оскільки квадрат включений коли центральна його вершина включена, то однією з підходів буде перевірити все сусідні подквадраты перед відключенням. Проте, у моїй реалізації це завжди буде занадто важко, оскільки перебування сусідніх квадратів доведеться обегать ве дерево. Натомість вважаю число посилань кожної реберної вершини. Воно одно числу подквадратов, від 0 до запланованих 4, які входять. Це означає що завжди ми включаем/выключаем квадрат, ми повинні оновити число посилань у двох вершинах. На щастя, число посилань змінюється від 0 до 4, тобто. це можна запакувати в 3 біта.

.

Рис. 8. Кожна реброва вершина має 4 сусідніх подквадрата, що використовують її як кутову. Якщо будь-якій з цих квадратів включений, те й вершина мусить бути включена. Приміром, чорна вершина повинна бути включена якщо включений одне із сірих квадратов.

Таким чином выключающий тест дуже проста: якщо вершина включена, число посилань одно 0 і vertex test для поточної точки камери повертає false, виключаємо вершину. Інакше не торкаємо її. Умови вимикання квадрата теж досить прямолінійні: якщо квадрат включений і не корінь дерева, немає і включеных реберних вершин немає і включеных подквадратов, квадрат провалює BoxTest, виключаємо его.

Особенности: Пам’ять

Очень важливою рисою цьогорічних чи іншого LOD методу є споживання пам’яті. У quadtree один квадрат еквівалентний трьом вершин звичайній сітки висот, отже слід зробити структуру квадрата як і компактніші. На щастя, Render () і Update () методи не вимагає від кожного квадрата інформації з всім 9 вершин. Ось список необхідних даних:

· 5 висот (кути і центр).

· 6 значень помилок (вершини на східному і південному ребрах і 4 подквадрата).

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

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

· 4 покажчика на подквадраты.

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

· 1 1-битный прапор, що складає що це квадрат не то, можливо удален.

В залежність від потреб докладання значення висот можуть бути комфортно упаковані у вісім чи 16 біт. Значення помилок можуть використовувати той ж найбільш формат, але, використовуючи нелінійне стиснення ви можете запакувати їх ще більше. Усі лічильники заслань та статистичний прапор помістяться один байт. Прапори включення теж пакуються один байт. Розмір покажчиків на подквадраты залежить від максимальної кількості вузлів, які можна використані. Зазвичай це сотні чи тисячі, отже я використовую 20 біт за кожен покажчик принаймні. Мінімальна і забезпечити максимальне значення висоти також можуть бути стиснуті різними способами, але 8 біт за кожен виглядає розумним мінімумом. Усе це займає 191 біт (24 байта) на квадрат при 8-битных значеннях висоти. 16-битные значення висот вимагають 29 байтів. 32-байтный розмір розмір квадрата виглядає хорошою метою для ощадливою реалізації. 36 байтів змушений використовувати, так який у мене не намагався упаковувати покажчики на подквадраты. Інший трюк — використовувати фіксований масив заміняючи алокаторов для quadsquare: new і quadsquare: delete. Це стискує 4 байта накладних витрат стандартного для З++ аллокатора (який у мене припускаю) до 1 біта.

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

С одного боку це надзвичайно багато, але з іншого боку адаптивна структура quadtree дозволяє зберігати зріджені дані в рівних областях чи областях, котрим непотрібен висока деталізація. У той самий час у високо важливих областях можна досягти високої деталізації; приміром, у тій игре-автосимуляторе можна зберігати навіть нерівності і вибоїни на дороге.

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

[2] і [3] також використовують морфинг вершин чи, по іншому, геоморфинг. Ідея у цьому, що з включенні вершин виходять різкі стрибки між попереднім мешом, у якому дана вершина відключили і отрисованным у цьому кадрі, у якому вершина було включено. А, щоб позбудеться цього ефекту застосовується плавна анімація з интерполированного становища вершини у її справжнє значення. Це чудово видається і усуває неприємні ефекти стрибків, дивися McNally «p.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 З. 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. internet This is a good practical introduction to Binary Triangle Trees from [2]. Also see internet, a game which uses methods from [2].

[5] Ben Discoe, internet. This web site is an excellent survey of algorithms, implementations, tools and techniques related to terrain rendering.