Організація безперервних 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) замість регулярної сітки для представлення
інформації про висоту. Використовуючи це квадродерево ми можемо закодувати дані з
різним дозвіл в різних областях. Приміром, у автосимулятор нам потрібно
висока деталізація дороги та її околиць, в ідеалі до кожної опуклості, але
навколишні пустки, по яких ми не можемо їхати, можна відображати і з меншою
деталізацією. Нам потрібна лише інформація для генерації пагорбів і долин.
Квадродерево також можна використовувати і для іншого
підходу до вирішення проблеми пам'яті: процедурна деталізація. Ідея полягає в тому,
щоб визначати форму ландшафту на грубому рівні і автоматично генерувати
високодеталізірованний ландшафт на льоту навколо точки зору. За адаптивної
природі квадродерева всі ці згенеровані деталі можуть бути відкинуті після
зміни точки зору, таким чином звільняючи пам'ять для створення процедурної
деталізації в іншому регіоні.
Алгоритм: Створення Меша
Алгоритм базовані на [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 норми означає більшу
глибину поділок вздовж діагоналей горизонтальній площині ландшафту. Я не зміг
помітити даний ефект оком, так що я не думаю що про це варто
турбуватися. [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 (ie 1/2 the box dimensions)
L1 = max (abs (bcx --
viewx) - exx, abs (bcy - viewy) - exy, abs (bcz - viewz) - exz)
enabled = maxerror
* Threshold
Особливості : Деталі
У попередньому розділі була описана суть алгоритму, але
залишена осторонь маса деталей, деякі з яких є ключовими.
По-перше, де, власне зберігається інформація про висоту? У попередніх
алгоритмах існувала регулярна сітка висот, на якій неявно [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-бітний прапор, що показує що цей квадрат не
може бути вилучений.
В залежності від потреб програми значення висот можуть
бути комфортно упаковані в 8 або 16 біт. Значення помилок можуть використовувати той
самий формат, але, використовуючи нелінійне стиснення ви можете запакувати їх ще
більше. Всі лічильники посилань і статистичний прапор помістяться в 1 байт. Прапори
включення теж пакуються в 1 байт. Розмір покажчиків на подквадрати залежить від
максимального числа вузлів, які можуть бути використані. Зазвичай це сотні
або тисячі, так що я використовую 20 біт на кожен покажчик як мінімум.
Мінімальна і максимальна значення висоти теж можуть бути стислі різними
способами, але 8 біт на кожен виглядає розумним мінімумом. Усе разом це
займає 191 біт (24 байти) на квадрат за 8-бітових значеннях висоти. 16-бітові
значення висот вимагають 29 байтів. 32-байтним розмір розмір квадрата виглядає
хорошою метою для економною реалізації. 36 байтів я змушений використовувати, так
як я не намагався упаковувати покажчики на подквадрати. Другий трюк --
використовувати фіксований масив з заміною алокаторов для quadsquare:: new і
quadsquare:: delete. Це стискає 4 байти накладних витрат стандартного для C + +
аллокатора (як я припускаю) до 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.
