Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Полігональна сітка



План:


Введення

Приклад полігональної сітки, що зображає дельфіна.

Полігональна сітка ( англ. polygon mesh ) Або неструктурована сітка це сукупність вершин, ребер і граней які визначають форму багатогранного об'єкта в тривимірної комп'ютерної графіки і об'ємному моделюванні. Гранями звичайно є трикутники, чотирикутники або інші прості опуклі багатокутники (полігони), так як це спрощує рендеринг, але так само може складатися з найбільш загальних увігнутих багатокутників, або багатокутників з дірками. Вчення про полігональних сітках це великий підрозділ комп'ютерної графіки та геометричного моделювання. Різні уявлення полігональних сіток використаються для різних цілей і додатків. Безліч операцій проведених над сітками можуть включати булевої алгебри, згладжування, спрощення та багато інших. Мережеві уявлення, такі як "потокові" і "прогресивні" сітки, використовуються для передачі полігональних сіток по мережі. Об'ємні сітки відрізняються від полігональних тим, що вони явно являють і поверхня і об'єм структури, тоді як полігональні сітки явно представляють лише поверхню (обсяг неявний). Так як полігональні сітки широко використовуються в комп'ютерній графіці, також існують алгоритми трасування променів, виявлення зіткнень і динаміки твердих тіл для полігональних сіток.


1. Елементи моделювання сітки

Елементи моделювання полігональної сітки.

Об'єкти створені за допомогою полігональних сіток повинні зберігати різні типи елементів, таких як вершини, ребра, грані, полігони і поверхні. У багатьох випадках зберігаються лише вершини, ребра і або грані, або полігони. Рендерер може підтримувати лише трьох-сторонні грані, так що полігони повинні бути побудовані з їх безлічі, як показано на рис. 1. Однак багато рендерера підтримують полігони з чотирма і більше сторонами, або вміють тріангуліровать полігони в трикутники на льоту, роблячи необов'язковим зберігання сітки в тріангулірованной формі. Також в деяких випадках, таких як моделювання голови, бажано вміти створювати і трьох-і чотирьох-сторонні полігони.

Вершина - це позиція разом з іншою інформацією, такий як колір, нормальний вектор і координати текстури. Ребро це з'єднання між двома вершинами. Грань це замкнуте безліч ребер, в якому трикутна грань має три ребра і чотирикутне - чотири. Полігон це безліч граней. У системах, які підтримують багатосторонні межі, полігони і грані рівнозначні. Однак, більшість апаратного забезпечення для рендеринга підтримує лише грані з трьома або чотирма сторонам, так що полігони представлені як безліч граней. Математично, полігональна сітка може бути представлена ​​у вигляді неструктурованої сітки, або неорієнтованого графа, з додаванням властивостей геометрії, форми і топології.

Поверхні, частіше звані групами згладжування, корисні, але не обов'язкові для групування гладких областей. Уявіть собі циліндр з кришками, такий як жерстяна банка. Для гладкого затінення сторін, всі нормалі повинні вказувати горизонтально від центру, тоді як нормалі кришок повинні вказувати в + / - (0,0,1) напрямках. Якщо рендери як єдину, затінену по Фонгу поверхню, вершини складок мали б неправильні нормалі. Тому, потрібен спосіб визначення де припиняти згладжування для того, щоб групувати гладкі частини сітки, також, як полігони групують тристоронні грані. Як альтернатива наданню поверхонь / груп згладжування, сітка може містити іншу інформацію для розрахунку тих же даних, така як розділяючий кут (полігони з нормалями вище цієї межі або автоматично розглядаються як окремі групи згладжування, або по відношенню до ребра між ними застосовується небудь техніка , як наприклад поділ або скошування). Також, полігональні сітки з дуже високим дозволом менш схильні до проблем, для вирішення яких потрібні групи згладжування, так як їх полігони настільки малі, що потреба в них пропадає. Крім того, інша альтернатива існує в можливості просто від'єднання самих поверхонь від решти сітки. Рендерера не намагаються згладжувати ребра між несуміжними полігонами.

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


2. Уявлення

Полігональні сітки можуть бути представлені безліччю способів, використовуючи різні способи зберігання вершин, ребер і граней. У них входять:

  • Список граней: опис граней відбувається за допомогою покажчиків в список вершин.
  • "Крилатий" уявлення: в ньому кожна точка ребра вказує на дві вершини, дві грані і чотири (за годинниковою стрілкою і проти годинникової) ребра, які її стосуються. Крилатий подання дозволяє обійти поверхню за постійне час, але у нього великі вимоги по пам'яті зберігання.
  • Полуреберние сітки: спосіб схожий на "крилатий" уявлення, за винятком того, що використовується інформація обходу лише половини грані.
  • Чотириреберний сітки [ невідомий термін ], які зберігають ребра, полуребра і вершини без будь-якої вказівки полігонів. Полігони прямо не виражені в поданні, і можуть бути знайдені обходом структури. Вимоги по пам'яті аналогічні полуреберним сеткам.
  • Таблиця кутів, які зберігають вершини в зумовленою таблиці, такої що обхід таблиці неявно задає полігони. По суті, це " віяло трикутників ", використовуваний в апаратному рендеринге. Подання більш компактне і більш продуктивне для знаходження полігонів, але операції по їх зміні повільні. Більш того, таблиці кутів не представляють сітки повністю. Для уявлення більшості сіток потрібно кілька таблиць кутів (віял трикутників).
  • Вершинний уявлення: представлені лише вершини, що вказують на інші вершини. Інформація про гранях і ребрах виражена неявно в цьому поданні. Однак, простота представлення дозволяє проводити над сіткою безліч ефективних операцій.

Кожне з уявлень має свої переваги і недоліки. [1]

Вибір структури даних визначається застосуванням, необхідною продуктивністю, розміром даних, операціями, які будуть виконуватися. До прикладу, легше мати справу з трикутниками, ніж з багатокутниками загального вигляду, особливо в обчислювальної геометрії. Для певних операцій необхідно мати швидкий доступ до топологічної інформації, такої як ребра або сусідні грані; для цього потрібні більш складні структури, такі як "крилатий" уявлення. Для апаратного рендеринга потрібні компактні, прості структури; тому в API низького рівня, такі як DirectX і OpenGL зазвичай включена таблиця кутів (віяло трикутників).


2.1. Вершинний уявлення

Малюнок 2. Вершинний уявлення

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

Однак, сітки ВП отримують вигоду від малого використання пам'яті та ефективної трансформації. Малюнок 2 показує приклад паралелепіпеда зображений з використанням ВП сітки. Кожна вершина індексує її сусідні вершини. Зауважте, що останні дві вершини, 8 і 9 зверху і знизу паралелепіпеда, мають чотири пов'язаних вершини, а не п'ять. Головна система повинна справлятися з довільним числом вершин пов'язаних з будь даної вершиною.

Для більш детального опису сіток ВП див. Smith (2006) (англ.). [1]


2.2. Список граней

Малюнок 3. Список граней

Сітка з використанням списку граней представляє об'єкт як безліч граней і безліч вершин. Це саме широко використовуване уявлення, будучи вхідними даними типово прийнятими сучасним графічним обладнанням.

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

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

Моделювання вимагає легкого обходу всіх структур. З сіткою використовує список граней дуже легко знайти вершини грані. Також, список вершин містить список всіх граней пов'язаних з кожною вершиною. На відміну від вершинного уявлення, і грані і вершини явно представлені, так що знаходження сусідніх граней і вершин постійні за часом. Однак, ребра не задані явно, так що пошук все ще потрібен, щоб знайти всі грані, навколишні задану межу. Інші динамічні операції, такі як розрив або об'єднання грані, також складні зі списком граней.


2.3. "Крилатий" уявлення

Малюнок 4.

Представлене Брюсом Баумгартен в 1975, "Крилатий" уявлення явно являє вершини, грані і ребра сітки. Це уявлення широко використовується в програмах для моделювання для надання найвищої гнучкості в динамічній зміні геометрії сітки, тому що можуть бути швидко виконані операції розриву і об'єднання. Їх основний недолік - високі вимоги пам'яті і збільшена складність через вміст безлічі індексів.

"Крилатий" уявлення вирішує проблему обходу від ребра до ребра і забезпечує впорядковане безліч граней навколо ребра. Для будь-якого заданого ребра число вихідних ребер може бути довільним. Щоб спростити це, "крилатий" уявлення надає лише чотири, найближчі ребра за годинниковою і проти годинникової стрілки на кожному кінці ребра. Інші ребра можна обійти поступово. Тому інформація про кожному ребрі нагадує метелика, тому уявлення називається "крилатим". Малюнок 4 показує приклад паралелепіпеда в "крилатому" поданні. Повні дані по ребру складаються двох вершин (кінцеві точки), двох граней (по кожну сторону), і чотири ребра ("крила" ребра).

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

Див Baumgart (1975) для подробиць (англ.) [2]


3. Зведення уявлень сіток

Операція Вершинний уявлення Список граней "Крилатий" уявлення
VV Всі вершини навколо вершини Явно V → f1, f2, f3, ... → v1, v2, v3, ... V → e1, e2, e3, ... → v1, v2, v3, ...
EF Всі ребра грані F (a, b, c) → {a, b}, {b, c}, {a, c} F → {a, b}, {b, c}, {a, c} Явно
VF Всі вершини грані F (a, b, c) → {a, b, c} Явно F → e1, e2, e3 → a, b, c
FV Всі грані навколо вершини Пошук пари Явно V → e1, e2, e3 → f1, f2, f3, ...
EV Всі ребра навколо вершини V → {v, v1}, {v, v2}, {v, v3}, ... V → f1, f2, f3, ... → v1, v2, v3, ... Явно
FE Обидві грані ребра Порівняння списків Порівняння списків Явно
VE Обидві вершини ребра E (a, b) → {a, b} E (a, b) → {a, b} Явно
Flook Знайти грань з даними вершинами F (a, b, c) → {a, b, c} Перетин множин v1, v2, v3 Перетин множин v1, v2, v3
Розмір пам'яті V * avg (V, V) 3F + V * avg (F, V) 3F + 8E + V * avg (E, V)
Приклад з 10 вершин, 16 граней, 24 ребра:
10 * 5 = 50 3 * 16 + 10 * 5 = 98 3 * 16 + 8 * 24 + 10 * 5 = 290
Малюнок 5: зведення операцій уявлень сіток

У представленій вище таблиці, явно вказує на те, що операція може бути виконана за постійне час, так як зберігаються безпосередні дані; порівняння списків вказує на те, що для виконання операції повинно бути виконано порівняння двох списків; та пошук пари вказує на те, що повинен бути виконаний пошук двох індексів. Позначення avg (V, V) означає середнє число вершин, з'єднаних із заданою вершиною; avg (E, V) означає середнє число ребер з'єднаних із заданою вершиною, і avg (F, V) - середнє число граней, з'єднаних із заданою вершиною.

Позначення "V → f1, f2, f3, ... → v1, v2, v3, ..." показує що для виконання операції необхідний обхід навколо декількох елементів. Наприклад, щоб отримати "всі вершини навколо заданої вершини V" використовуючи список граней, потрібно спочатку знайти грані навколо заданої вершини V використовуючи список вершин. Потім, з цих граней, використовуючи список граней, знайти вершини навколо них. Зауважте, що "крилате" уявлення зберігає майже всю інформацію в явному вигляді, і інші операції завжди обходять спочатку ребро, щоб отримати додаткову інформацію. Вершинний уявлення - єдине уявлення, яке в явному вигляді зберігає сусідні вершини заданої вершини.

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

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


4. Інші уявлення

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

Прогресивні сітки передають дані про вершин і гранях з підвищуються рівнем деталізації. На відміну від потокових сіток, прогресивні сітки дають загальну форму цілого об'єкта, але на низькому рівні деталізації. Додаткові дані, нові ребра і грані, прогресивно збільшують деталізацію сітки.

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


5. Файлові формати

Полігональні сітки можуть зберігатися в безлічі файлових форматів :


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Сітка Рабиця
Рибальська сітка
Сітка (сузір'я)
© Усі права захищені
написати до нас
Рейтинг@Mail.ru