Рівень деталізації

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

У комп'ютерній графіці, поняття рівня деталізації[1][2][3] (англ. Level of detail або LOD) містить в собі зменшення складності 3D-модельного зображення, коли тривимірна модель рухається від глядача або відповідно до інших причин, таких як важливість об'єкту, відносна швидкість або його положення. Рівень деталізації, як метод, підвищує ефективність рендерингу шляхом зменшення навантаження на етапах графічного конвеєра[en], це як правило, перетворення вершин. Зменшення візуальної якості моделі часто залишається непоміченими через невеликий вплив на зовнішній вигляд об'єкта, коли він знаходиться далеко чи рухається швидко.

Хоча більша частина часу LOD застосовується тільки до геометричних елементів[en], основна концепція може бути узагальнена. Останнім часом метод LOD також включає управління шейдерами, щоб тримати під контролем складність пікселів. Форма рівня управління деталізацією застосовувалась до текстурованих карт протягом багатьох років, під назвою MIP-текстурування, що також забезпечує більш високу якість рендерингу.

Кажуть, що об'єкт був під впливом LOD-у, коли об'єкт спрощується базовим алгоритмом LOD-у.

Історична довідка[ред. | ред. код]

Походження[4] всіх алгоритмів LOD для 3D комп'ютерної графіки можна простежити в статті Джеймса Х. Кларка[en] у журналі Communications of the ACM за жовтень 1976 року. У той час комп'ютери були монолітними і рідкісними, і графіка розвивалася дослідниками. Саме обладнання було зовсім іншим, як за архітектурою так і за продуктивністю. Таким чином, багато розходжень можна спостерігати щодо сучасних алгоритмів, але простежується і багато спільних елементів.

Початковий алгоритм використовував набагато більш загальний підхід ніж той, що обговорюється тут. Після введення деяких доступних алгоритмів для управління геометрією сцени, стверджується, що найбільш плідні успіхи прийшли з «… структурування середовища, що рендериться», яке дозволяє використовувати більш швидкі перетворення і операції відсікання.

Таке ж структурування середовища в даний час пропонується як спосіб управління різним ступенем деталізації, тим самим, уникаючи непотрібних обчислень, але при цьому забезпечуючи адекватну візуальну якість:

Наприклад, додекаедр виглядає як сфера з досить великої відстані, і, таким чином, може бути використаний для моделювання його до тих пір, як вона розглядається з певного ракурсу, або далекої відстані. Однак, при ближчому розгляді, він буде мати вигляд додекаедру. Одним з рішень полягає в тому, щоб просто описати об'єкт з максимально необхідною кількістю деталей для усіх можливих ситуацій. Однак, тоді буде суттєво більше деталей, ніж це потрібно, коли об'єкт знаходиться на великих відстанях, і тоді в складному середовищі з великою кількістю подібних об'єктів, буде використовуватись занадто багато полігонів (або інших геометричних примітивів) щоб алгоритми візуалізації видимої[en] поверхні ефективно працювали.

Запропонований алгоритм передбачає структуру даних дерева, яка кодує в його ребрах одночасно перетворення і переходи до детальнішого зображення об'єктів. Таким чином, кожен вузол кодує об'єкт, і відповідно до швидкої евристики, дерево спускається до листків, кожен з яких забезпечує більш детальне зображення об'єкту. У випадку коли листок буде досягнуто, можливе використання інших методів для більш детального зображення об'єкту, таких як рекурсивне розбиття, запропоноване Едвіном Кетмеллом[5].

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

У статті запроваджується відсікання (не варто плутати з відкиданням невидимих граней[en], які дуже близькі), різні міркування про методи, спрямовані на вдосконалення якості зображення об'єктів, їх вплив на продуктивність, взаємодію, з метою збереження продуктивності.

Загально відомі підходи[ред. | ред. код]

Умовний приклад рівнів дискретної деталізації (DLOD).

Хоча наведений вище алгоритм охоплює весь діапазон методів управління деталізацією, реальні програми, як правило, використовують інші методи, пристосовані до даних, які зображаються. В залежності від вигляду зображаємих об'єктів, використовуються дві основні родини алгоритмів.[6]

Геоморфінг створює гладкий перехід між LOD1 та LOD2 за допомогою наближених мешів на проміжних кроках.

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

При іншому підході функція створення полігональної сітки оцінюється так, щоб уникнути надмірних помилок, що є евристичною функцією залежною від відстаней. Задана функція «сітки» потім неперервно оцінюється і обирається найкраща версія, яка є компромісом між візуальною якістю і обчислювальними витратами. Такі типи алгоритмів, як правило, називають CLOD (англ. Continuous LOD).

Подробиці дискретного LOD (DLOD)[ред. | ред. код]

Приклад різних діапазонів DLOD. Більш темні ділянки визначають візуалізацію з більш високою деталізацією. Додаткова операція очищення використовується для відкидання інформації за межами усічення (кольорові ділянки).

Основна концепція дискретного LOD (DLOD), полягає в тому, щоб для представлення одного й того ж об'єкта мати різні моделі. Отримання таких моделей вимагає зовнішнього алгоритму, який часто є нетривіальним та використовує різноманітні методи спрощення полігонів. Для наступних алгоритмів LOD-у просто припускаємо, що ці методи доступні.

DLOD алгоритми часто використовується в високо продуктивних додатках, які використовують невеликі набори даних, що легко розміщуються у пам'яті. Хоча можливе використання Out-of-core алгоритмів[en], рівень деталізації інформації не відповідає такого роду застосункам. Алгоритмам такого роду можна полегшити функціювання, якщо забезпечити більшу продуктивність та менше використання CPU.

Методи DLOD часто використовуються для «автономних» рухомих об'єктів, в тому числі, можливе використання складних методів анімації. Інший підхід використовується в Geomipmapping[en][7], алгоритмі зображенні рельєфу, тому що, меші поверхні відрізняються як графічно так і топологічно від інших мешів. Замість того щоб змінювати LOD відповідно до оцінки похибки, geomipmapping використовує зафіксований метод спрощення, який залежно від заданої похибки обчислює відстань, на якій ця похибка є прийнятною.

Дискретний приклад LOD[ред. | ред. код]

Як простий приклад розглянемо сферу. Наближення дискретним LOD-ом буде кешувати кілька моделей, які будуть використовуватися на різних відстанях. Оскільки модель може бути тривіальна процедурно генерується[en] його математичне формулювання, використання різної кількості простих точок забезпечують генерацію різноманітних моделей. Цей прохід не є алгоритм LOD-кий.

Visual impact comparisons and measurements
Зображення A finely tassellated wireframe sphere featuring over 5000 sample points. A highly tassellated wireframe sphere, almost 2900 points. A wireframe sphere with roughly 1600 sample points. A wireframe sphere with almost 700 vertices, good when viewed from a distance. A wireframe sphere with less than 150 sample points but still enough for far away objects.
Кількість вершин ~5500 ~2880 ~1580 ~670 140
Коментар Максимальна деталізація (для дуже близької взаємодії з об'єктом) Поступове зменшення деталізації (при віддалені об'єкту) Мінімальна деталізація (для об'єктів, що знаходяться на дуже великій відстані)

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

OpenGL використовується для рендеринга через його високу ефективність в управлінні малими партіями, зберігання кожної моделі в списку зображення[en], таким чином, уникаючи накладних витрат для комунікації.

У наступній таблиці порівнюється продуктивність LOD (рендеринг і метод грубої сили).

Visual impact comparisons and measurements
Метод грубої сили DLOD Порівняння
Рендероване

зображення

Scene at maximum detail. Same scene as above with lodding enabled. Almost black difference image shows no easily noticeable difference.
Час рендерингу 27.27 мс 1.29 мс 21 × скорочення
Вершини 2,328,480 109,440 21 × скорочення

Ієрархічний LOD[ред. | ред. код]

Оскільки апаратні засоби орієнтовані на великі обсяги деталей, що надають полігональні об'єкти низької якості можуть скласти неоптимальне уявлення. HLOD уникає проблеми шляхом групування різних об'єктів разом. Це забезпечує більш високу ефективність.[8]

Практичне застосування[ред. | ред. код]

Відео ігри[ред. | ред. код]

LOD особливо корисна в 3D відеоіграх. Розробники відеоігор хочуть надати гравцям ігри з великими світом, але завжди обмежені апаратними засобами, частотою кадрів. З появою 3D-ігри в 1990-х роках, багато відеоігор просто не роблять далекі (на далекій відстані) структури або об'єкти. Тільки поблизу об'єктів буде надана деталізація і більш віддалені частини будуть поступово зникати, по суті. Відео ігри, використовуючи LOD рендеринг уникають цього ефекту туману і може зробити великі площі. Деякі відомі ранні приклади LOD рендеринга в 3D відеоігор включають Spyro the DragonCrash Bandicoot: WarpedUnreal Tournament і двигун Serious Sam.

Рівень деталізації в ГС і міського моделювання 3D[ред. | ред. код]

LOD використовується в ГС і 3D моделях міст[en] в аналогічній концепції. Це вказує на те, наскільки ретельно властивості реального світу були нанесені на карту і наскільки модель своєму реальному прообразу. Крім геометричної складності, інші показники, такі як просторово-смислова когерентність, роздільна здатність текстури і атрибути можуть бути розглянуті в LOD моделі.[9] Стандарт CityGML[en] містить одну з найвідоміших категорій LOD.[10]

Аналогія «LOD-у» в ГС називається як узагальнення[en].

Візуалізація і моделювання програмного забезпечення [ред. | ред. код]

  • MeshLab[en] відкритий інструмент обробки джерела сітки, який здатний точно спростити 3D полігональні сітки.
  • Polygon Cruncher[en] комерційне програмне забезпечення від Mootools, що зменшує кількість полігонів об'єктів без зміни їх зовнішнього вигляду.
  • VizUp оптимізація 3D-моделі і зменшення полігонів SDK, щоб зменшити розмір моделі і збільшення швидкості рендеринга при збереженні якості візуалізації.
  • Rational Reducer
  • Pro Optimizer
  • GPure комерційне програмне забезпечення від DeltaCAD, який адаптує DMU для планшета і дисплея смартфона.

Примітки[ред. | ред. код]

  1. http://people.cs.clemson.edu/~dhouse/courses/405/notes/OpenGL-mipmaps.pdf
  2. http://computer-graphics.se/TSBK07-files/pdf/PDF09/10%20LOD.pdf
  3. http://rastergrid.com/blog/2010/10/gpu-based-dynamic-geometry-lod/
  4. Communications of the ACM, October 1976 Volume 19 Number 10. Pages 547-554. Hierarchical Geometric Models for Visible Surface Algorithms by James H. Clark, University of California at Santa Cruz. Digitalized scan is freely available at http://accad.osu.edu/~waynec/history/PDFs/clark-vis-surface.pdf.
  5. Catmull E., A Subdivision Algorithm for Computer Display of Curved Surfaces. Tech. Rep. UTEC-CSc-74-133, University of Utah, Salt Lake City, Utah, Dec. 1
  6. Ribelles, López, and Belmonte, "An Improved Discrete Level of Detail Model Through an Incremental Representation", 2010, Available at http://www3.uji.es/~ribelles/papers/2010-TPCG/tpcg10.pdf
  7. de Boer, W.H., Fast Terrain Rendering using Geometrical Mipmapping, in flipCode featured articles, October 2000. Available at http://www.flipcode.com/tutorials/tut_geomipmaps.shtml.
  8. Carl Erikson's paper at http://www.cs.unc.edu/Research/ProjectSummaries/hlods.pdf provides a quick, yet effective overlook at HLOD mechanisms. A more involved description follows in his thesis, at https://wwwx.cs.unc.edu/~geom/papers/documents/dissertations/erikson00.pdf.
  9. Biljecki, F.; Ledoux, H.; Stoter, J.; Zhao, J. (2014). Formalisation of the level of detail in 3D city modelling. Computers, Environment and Urban Systems 48: 1–15. doi:10.1016/j.compenvurbsys.2014.05.004. 
  10. Biljecki, F.; Ledoux, H.; Stoter, J. (2016). An improved LOD specification for 3D building models. Computers, Environment and Urban Systems 59: 25–37. doi:10.1016/j.compenvurbsys.2016.04.005. 

de Boer, W.H., Fast Terrain Rendering using Geometrical Mipmapping, in flipCode featured articles, October 2000. Available at http://www.flipcode.com/tutorials/tut_geomipmaps.shtml.