Геометрична обробка

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

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

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

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

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

Реконструкція поверхні

[ред. | ред. код]

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

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

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

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

Реєстрація

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

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

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

Згладжування

[ред. | ред. код]

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

.

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

.

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

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

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

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

Парамеризація

[ред. | ред. код]

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

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

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

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

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

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

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

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

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

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

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

Див. також

[ред. | ред. код]

Посилання

[ред. | ред. код]
  1. Обробка сітки полігонів, Ботш та ін. 2010
  2. Poisson surface reconstruction. hhoppe.com. Архів оригіналу за 2 серпня 2017. Процитовано 8 травня 2017.
  3. Chris Tralie : Laplacian Meshes. www.ctralie.com. Архів оригіналу за 16 березня 2017. Процитовано 8 травня 2017.
  4. Desbrun, Mathieu (2002). Intrinsic Parameterizations of Surface Meshes (PDF). Eurographics. 21. Архів оригіналу (PDF) за 11 серпня 2017. Процитовано 8 травня 2017.
  5. Levy, Bruno (2002). Least squares conformal maps for automatic texture atlas generation (PDF). ACM Transactions on Graphics (TOG) - Proceedings of ACM SIGGRAPH 2002. 21: 362—371. Архів оригіналу (PDF) за 15 березня 2017. Процитовано 8 травня 2017.

Додаткові посилання

[ред. | ред. код]