Відкрити головне меню

Геометрична обробка, або обробка полігональної сітки - це область дослідженнь, яка використовує поняття з прикладної математики, інформатики і інженерії для розробки ефективних алгоритмів для збору, реконструкції, аналізу, обробки, моделювання та передачі складних 3D-моделей. Вона аналогічна обробці сигналів і обробці зображень. Багато понять, структур даних і алгоритмів запозичені безпосередньо з цих областей. Наприклад, де згладження зображень може згортати сигнал інтенсивності з ядром розмиття, утвореного за допомогою оператора Лапласа, згладжування лапласіаном[en] може бути досягнуте шляхом згортки геометрії поверхні ядром розмиття, утвореного за допомогою оператора Лапласа-Бельтрамі[en]. Застосування алгоритмів обробки геометрії вже охоплюють широкий спектр областей від мультимедіа, розваг і класичного автоматизованного проектування, до біомедичного обчислення, зворотнього інжинирінгу і обчислювальних наук[en]. [1]

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

Зміст

Геометрична обробка як життєвий циклРедагувати

 
Сітка кактуса, яка показує Гаусову кривину в кожній вершині, за допомогою використання методу дефекту кута.

Геометрична обробка включає в себе роботу з формами[en], як правило, в 2D або 3D, хоча форма може бути в просторі довільної вимірності. Обробка форми включає в себе три етапи, які відомі, як її життєвий цикл. На етапі створення, форма може бути реалізована за допомогою одного з трьох методів: функціонального, 3D-моделювання або 3D-сканера. Після того, як форма створена, вона може бути проаналізована і відредагована кілька разів в циклі. Це, як правило, включає в себе отримання різних вимірів, наприклад, відстаней між точками форми, гладкість форми, або її характеристики Ейлера. Редагування може включати шумозаглушення, деформування або виконання жорстких перетворень. Нарешті, на заключному етапі «життя» фігури, вона використовується як продукт. Наприклад, вона може бути направлена у 3D-принтер для використання як фізичної моделі.

Дискретне представлення формиРедагувати

 
Полігональна сітка знаменитого стенфордського кролика. Форми, як правило, представляються у вигляді сітки, тобто, набору багатокутників, які окреслюють контури форми.

Як і будь-яка інша форма, форма, яка використовується при геометричній обробці має властивості, що відноситься до її геометрії і топології. Геометрія форми розглядає положення точок форми в Евклідовому просторі, дотичні, нормалі і кривину. Вона також включає в себе вимірність простору, в якому форма знаходиться (наприклад,   або  ). Топологія форми являє собою сукупність властивостей, які не змінюються навіть після того, як гладкі перетворення були застосовані до форми. Це стосується вимірів, таких як кількість отворів і кордонів, а також орієнтовність форми. Одним із прикладів неорієнтовної форми є стрічка Мебіуса.

Реконструкція поверхніРедагувати

Реконструкція Пуассона від точок поверхні до сіткиРедагувати

 
Трикутна сітка побудована з хмари точок. Іноді форми ініціалізуються тільки як «хмара точок», колекція відібраних точок від поверхні фігури. Часто ці хмари точок повинні бути перетворені в сітки.

Залежно від того, як форма ініціалізаціалізована або «народжена» форма може існувати тільки як туманність діскретизуючих точок, які представляють її поверхню в просторі. Для перетворення точок поверхні у сітку, може бути використана стратегія реконструкції Пуассона [2]. Цей метод стверджує, що індикаторна функція, функція, яка визначає, які точки в просторі належать до поверхні форми, насправді може бути обчислена з вибіркових точок. Ключовим поняттям є те, що градієнт індикаторної функції дорівнює 0 усюди, за винятком вибіркових точок, де вона дорівнює внутрішньої нормалі до поверхні. Більш формально, припустимо, що збір вибіркових точок від поверхні позначається як  , кожна точка в просторі як  , і відповідна нормаль в цій точці як  . Тоді градієнт індикаторної функції визначається наступним чином:

 

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

РеєстраціяРедагувати

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

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

 

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

ЗгладжуванняРедагувати

Коли форми визначені або відскановані, там може бути супроводжуючий шум, або сигнал, що діє на поверхню або на фактичну геометрічну поверхність. Зниження шуму, раніше було відоме як шумопоглинання, зараз відомо як поверхневий обтічник[en]. Завдання геометричного згладжування є аналогом зниження рівня сигналу шуму, і, отже, використовує аналогічні підходи. Відповідний лагранжіан, який треба звести до мінімуму, отримується шляхом запису відповідності вихідного сигналу   і гладкості результуючого сигналу, який апроксимується величиною градієнта з вагою  :

 .

беручи варіацію   на   виділяє необхідну умову

 .

Дискретизуючи це на частково-постійних елементах з нашим сигналом на вершинах, ми отримаємо

 

 
Гучна сфера ітеративно згладжується

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

 

Де   та   кути напроти сторони  [3]

ПарамеризаціяРедагувати

Іноді нам потрібно згладити 3D поверхню на площину. Цей процес відомий як параметризація[en]. Мета полягає в тому, щоб знайти координати u і v, на які ми можемо зіставити поверхню, так щоб спотворення були мінімальними. Таким чином, параметризацію можна розглядати як задачу оптимізації. Одним з основних застосувань сітки параметризації це відображення текстури.

Метод масових джерелРедагувати

 
Вкладення Тата показує негладкі параметризації на стороні жука.

Одним із способів виміру перекручувань накопиченого в процесі відображення, є визначення того, наскільки довжина ребер на відображенні 2D відрізняється від їх довжини в оригінальній 3D поверхні. У більш формальних термінах, цільова функція може бути записана у вигляді:

 

Де   набір сторін сітки та   набір вершин. Проте, ця оптимізація цільової функції призведе до вирішення, яке відображає всі вершини в одну вершину в uv - координати. Запозичуючи ідею з теорії графів, ми застосовуємо картографію Тата[en] і обмежуємо граничні вершини сітки на одиничному колі або іншому опуклому багатокутнику. Це запобігає руйнування усіх вершин в одну вершину, при застосованні відображення. Неграничні вершини потім розташовуються в барицентричній системі координат своїх сусідів. Картографія Тата, однак, до сих пір страждає від сильних спотворень, тому що він намагається зробити довжини ребер рівними, і, отже, не може правильно врахувати розміри трикутника на фактичній поверхні сітки.

Конформне відображення найменьших квадратівРедагувати

 
Порівняння параметризації вкладення Тата і конформного відображення найменьших квадратів(КВНК). Зверніть увагу на те, як КВНК параметризація гладка на стороні жука.

Інший спосіб вимірювання спотворень є розгляд варіації на u і v координатних функціях. Люфт і спотворення проявляється у засобах масової пружини через високі варіації в і і v координатних функціях. При такому підході цільової функцією стає енергія Діріхле[en] на u і v:

 

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

 

Підставивши ці вимоги разом, ми можемо збільшити енергію Діріхле так, що наша цільова функція стає:[4][5]

 

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

Дивіться такожРедагувати

ПосиланняРедагувати

  1. Обробка сітки полігонів, Ботш і ін. 2010
  2. Poisson surface reconstruction. hhoppe.com. 
  3. Chris Tralie : Laplacian Meshes. www.ctralie.com. 
  4. Desbrun, Mathieu (2002). Intrinsic Parameterizations of Surface Meshes. Eurographics 21. 
  5. Levy, Bruno (2002). Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics (TOG) - Proceedings of ACM SIGGRAPH 2002 21: 362–371. 

Додаткові посиланняРедагувати