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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Приклад полігонального мешу, що зображає мавпочку Сюзанну — один з примітивів програми Blender.

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

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

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

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

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

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

Представлення[ред.ред. код]

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

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

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

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

Вершинне представлення[ред.ред. код]

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

Список граней[ред.ред. код]

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

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

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

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

" Крилате " подання[ред.ред. код]

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

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

Формати файлів[ред.ред. код]

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

Дивіться також[ред.ред. код]

Зноски[ред.ред. код]