Рівень деталізації
У комп'ютерній графіці, поняття рівня деталізації[1][2][3] (англ. Level of detail або LOD) характеризує складність зображення 3D-моделі. Рівень деталізації можна зменшити, коли тривимірна модель рухається від глядача або відповідно до інших причин, таких як важливість об'єкту, відносна швидкість точки зору або його положення. Метод рівня деталізації підвищує ефективність рендерингу шляхом зменшення навантаження на етапах графічного конвеєра, це як правило, перетворення вершин. Зменшення візуальної якості моделі часто залишається непоміченими через невеликий вплив на зовнішній вигляд об'єкта, коли він знаходиться далеко чи рухається швидко.
Хоча у більшості ситуацій LOD застосовується тільки до геометричних елементів, основна концепція може бути узагальнена. Останнім часом метод LOD також включає управління шейдерами, для контролю складності пікселів. Форма рівня управління деталізацією застосовувалась до текстурованих карт протягом багатьох років, під назвою MIP-текстурування, що також забезпечує більш високу якість рендерингу.
Кажуть, що об'єкт був під впливом LOD-у (англ. LOD-ed), коли об'єкт спрощується базовим алгоритмом LOD-у.
Історична довідка[ред. | ред. код]
Походження[4] всіх алгоритмів LOD для комп'ютерної 3D графіки можна простежити в статті Джеймса Х. Кларка[en] у журналі Communications of the ACM за жовтень 1976 року. У той час комп'ютери були монолітними й рідкісними, а графікою займалися дослідники та науковці. А апаратне забезпечення було абсолютно різним, як в архітектурному, так і в плані швидкодії. Тому можна спостерігати багато розходжень щодо сучасних алгоритмів, але можна побачити й багато спільних елементів.
На відміну від підходів, які розглядаються тут, запропонований Кларком початковий алгоритм пропонує більш загальний підхід. Після опису алгоритмів, які можна використати для управління геометрією сцени, стверджується, що найбільшої продуктивності можна досягти при «… структуруванні середовищ, які рендеряться», що дозволяє використовувати швидкісні перетворення та операції відсікання.
Зараз таке ж структурування середовища застосовується як спосіб управління різними деталями, таким чином уникаючи зайвих обчислень, але забезпечуючи належну якість:
Наприклад, додекаедр виглядає як сфера з досить великої відстані, і, таким чином, може бути використаний для моделювання фігури до тих пір, поки вона розглядається з певного ракурсу, або далекої відстані. Однак, при ближчому розгляді, він буде мати вигляд додекаедру. Одне з рішень цієї проблеми полягає в тому, щоб просто описати об'єкт з максимально необхідною кількістю деталей для усіх можливих випадків. Однак, тоді буде значно більше деталей, ніж це потрібно у випадку, коли об'єкт знаходиться на великої відстані, а в складному середовищі з великою кількістю подібних об'єктів, буде залучено занадто багато полігонів (або інших геометричних примітивів), для того, щоб алгоритми візуалізації видимої поверхні працювали ефективно.
Запропонований Кларком алгоритм передбачає деревоподібну структуру даних, яка кодує перетворення і переходи до детальнішого зображення об'єктів в ребрах дерева. Таким чином, кожен вузол кодує об'єкт, і згідно зі швидкою евристикою, дерево опускається до листя, що надає кожному об'єкту більше деталей. У випадку коли листа буде досягнуто, можливе використання інших методів для більш детального зображення об'єкту, таких як рекурсивне розбиття, запропоноване Едвіном Кетмеллом[5].
Важливий момент, однак, полягає в тому, що в складному середовищі, кількість інформації, представленої про різні об'єкти навколишнього середовища змінюється в залежності від частини поля видимості, яку займають ці об'єкти.
У статті запроваджується відсікання (не варто плутати з відкиданням невидимих граней[en], хоча часто подібні), різні міркування про методи, спрямовані на вдосконалення якості зображення об'єктів, їх вплив на збереження продуктивності.
Загально відомі підходи[ред. | ред. код]
Хоча наведений вище алгоритм охоплює цілий ряд методів управління деталізацією, реальні програми, як правило, використовують інші методи, пристосовані до даних, які зображаються. В залежності від вигляду зображуваних об'єктів, використовуються два основні напрямки алгоритмів.[6]
Перший напрямок розбиває простір на кінцеву кількість областей, з визначеним рівнем деталізації для кожної з них. Результатом буде дискретна кількість рівнів деталізації, саме тому його називають DLOD (англ. Discrete LOD). Одним з недоліків цього напрямку є відсутність плавного переходу між рівнями LOD, хоча для уникнення візуального поппінгу[en] можна використати альфа-змішування або морфінг.
Другий напрямок використовує структуру, яка містить безперервно змінюваний спектр геометричних деталей. Потім можна дослідити структуру, щоб плавно вибрати відповідний рівень деталізації, необхідний для ситуації. Такі типи алгоритмів, як правило, називають CLOD (англ. Continuous LOD). Значною перевагою цього напрямку є можливість локального варіювання деталей; наприклад, сторона великого об'єкта, що знаходиться ближче до виду, може бути представлена з високою деталізацією, одночасно зменшуючи деталі на віддаленій стороні.
Дискретний LOD (DLOD)[ред. | ред. код]
Основна концепція дискретного LOD (DLOD) полягає у забезпеченні різних моделей, що представляють один і той же об'єкт. Отримання таких моделей вимагає застосування зовнішнього алгоритму, який часто є нетривіальним та використовує різноманітні методи спрощення полігонів. Для наступних алгоритмів LOD-у просто припускаємо, що ці методи доступні.
DLOD алгоритми часто використовуються в високопродуктивних додатках, які використовують невеликі набори даних, що легко розміщуються у пам'яті. Хоча можливе використання Out-of-core алгоритмів[en], рівень деталізації інформації не відповідає такого роду застосункам. Алгоритмам такого роду можна спростити функціювання, якщо забезпечити більшу продуктивність CPU.
Методи DLOD часто використовуються для «автономних» рухомих об'єктів, в тому числі можливе використання складних методів анімації. Інший підхід використовується в Geomipmapping[en][7], алгоритмі зображенні рельєфу, в ньому межі поверхні відрізняються від інших сіток як графічно, так і топологічно. Замість того щоб змінювати LOD відповідно до оцінки похибки, geomipmapping використовує зафіксований метод спрощення, який залежно від заданої похибки обчислює відстань, на якій ця похибка є прийнятною.
Приклад дискретного LOD'у[ред. | ред. код]
Як простий приклад, розглянемо сферу. Наближення дискретним LOD-ом буде кешувати кілька моделей, які будуть розміщуватися на різних відстанях. Оскільки модель може бути тривіально згенерована процедурою за її математичною формулою, тому використання різної кількості точок розподілених на поверхні забезпечують генерацію різноманітних моделей. Цей прохід не є LOD-алгоритмом.
| Зображення | 
|
|
|
|
|
|---|---|---|---|---|---|
| Кількість вершин | ~5500 | ~2880 | ~1580 | ~670 | 140 |
| Коментар | Максимальна деталізація (для дуже близької взаємодії з об'єктом) | Поступове зменшення деталізації (при віддалені об'єкту) | Мінімальна деталізація (для об'єктів, що знаходяться на дуже великій відстані) |
Для симуляції можливого сценарію зміни форми залежно від відстані, може бути використана спеціальна програма. Використання простих алгоритмів та операцій з фрагментами гарантує відсутність обмеження на потужність процесора. Для кожного кадру програма обчислює відстань до сфери та вибирати модель із пулу відповідно до цієї відстані. Для спрощення демонстрації, відстань до кожної моделі жорстко закодована.
OpenGL використовується для рендеринга через його високу ефективність в управлінні малими партіями об'єктів. Для яких він зберігає моделі в списку зображення[en], що дозволяє уникнути накладних витрат для пересилки інформації.
У наступній таблиці порівнюється продуктивність LOD (рендеринг і метод грубої сили).
| Метод грубої сили | DLOD | Порівняння | |
|---|---|---|---|
| Рендероване
зображення |
|
|
|
| Час рендерингу | 27.27 мс | 1.29 мс | 21 × скорочення |
| Вершини | 2,328,480 | 109,440 | 21 × скорочення |
Ієрархічний LOD[ред. | ред. код]
Оскільки апаратні засоби орієнтовані на великі обсяги деталей, що надають полігональні об'єкти низької якості, вони можуть скласти неоптимальне відображення. HLOD уникає проблеми шляхом групування різних об'єктів разом. Це забезпечує більшу ефективність.[8]
Практичне застосування[ред. | ред. код]
Відео ігри[ред. | ред. код]
LOD особливо корисний в 3D відеоіграх. Розробники відеоігор хочуть надати гравцям ігри з великими просторами, але вони завжди обмежені апаратними засобами та частотою кадрів. З появою 3D-ігри в 1990-х роках, багато відеоігор просто не відображають структури або об'єкти на далекій відстані. Тільки найближчі об'єкти буде детально зображено, а більш віддалені частини будуть поступово зникати, для цього використовують ефект туману. Відео ігри, які використовуючи LOD для рендерингу, уникають використання ефекту туману і можуть зображати великі ділянки простору. Деякі відомі приклади LOD рендеринга у 3D відеоіграх включають Spyro the Dragon, Crash Bandicoot: Warped, Unreal Tournament і рушій Serious Sam. Більшість сучасних 3D-ігор використовують комбінацію методів візуалізації LOD, використовуючи різні моделі для великих конструкцій та відсікання за відстань для деталей довкілля, таких як трава та дерева. Ефект іноді все ще помітний, наприклад, коли персонаж гравця летить над віртуальною місцевістю або використовує снайперський приціл для перегляду на великі відстані. Коли ви наближаєтеся, вам буде здаватися, що трава і листя вискакують назовні, що також називається видаленням листя[9]. LOD також може використовуватися для відображення фрактального ландшафту в режимі реального часу[10].
У популярній будівельній грі Cities: Skylines моди дозволяють використовувати різний ступінь LOD.
Геоінформаційні системи і тривимірні моделі міст[ред. | ред. код]
LOD використовується в геоінформаційних системах (ГІС) і 3D моделях міст[en] в аналогічній концепції. Це вказує на те, наскільки ретельно властивості реального світу були нанесені на карту і наскільки модель відповідає своєму реальному прообразу. Крім геометричної складності, інші показники, такі як просторово-смислова когерентність, роздільна здатність текстури та атрибути можуть бути розглянуті в LOD моделі.[11] Стандарт CityGML[en] містить одну з найвідоміших категорій LOD.[12]
Аналогія «LOD-у» в ГІС визначається як узагальнення.
Візуалізація і моделювання програмного забезпечення [ред. | ред. код]
- MeshLab — інструмент для обробки полігональної сітки з відкритим кодом, який може безпомилково спрощувати 3D полігональні сітки.
- Polygon Cruncher[en] — комерційне програмне забезпечення від Mootools, що зменшує кількість полігонів для об'єктів без зміни їх зовнішнього вигляду.
- Simplygon[en] — комерційний пакет для обробки загальних вхідних сіток в сітки, які обробляються в режимі реального часу.
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
- ↑ http://people.cs.clemson.edu/~dhouse/courses/405/notes/OpenGL-mipmaps.pdf
- ↑ http://computer-graphics.se/TSBK07-files/pdf/PDF09/10%20LOD.pdf
- ↑ http://rastergrid.com/blog/2010/10/gpu-based-dynamic-geometry-lod/
- ↑ 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 [Архівовано 10 вересня 2006 у Wayback Machine.].
- ↑ 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
- ↑ 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
- ↑ 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.
- ↑ 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.
- ↑ «Unreal Engine Documentation, Foliage Instanced Meshes, Culling»
- ↑ Musgrave, F. Kenton, Craig E. Kolb, and Robert S. Mace. «The synthesis and rendering of eroded fractal terrains.» ACM Siggraph Computer Graphics. Vol. 23. No. 3. ACM, 1989.
- ↑ 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.
- ↑ 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.