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

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

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

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

Математичний еквівалент полігональних сіток — неструктуровані сітки — вивчаються методами дискретної геометрії[en].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також[ред.ред. код]

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