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

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

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

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

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

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

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

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

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

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

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

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

Залежно від того, як форма ініціалізаціалізована або «народжена» форма може існувати тільки як туманність діскретизуючих точок, які представляють її поверхню в просторі. Для перетворення точок поверхні у сітку, може бути використана стратегія реконструкції Пуассона . Цей метод стверджує, що індикаторна функція, функція, яка визначає, які точки в просторі належать до поверхні форми, насправді може бути обчислена з вибіркових точок. Ключовим поняттям є те, що градієнт індикаторної функції дорівнює 0 усюди, за винятком вибіркових точок, де вона дорівнює внутрішньої нормалі до поверхні. Більш формально, припустимо, що збір вибіркових точок від поверхні позначається як ${\displaystyle S}$, кожна точка в просторі як ${\displaystyle p_{i}}$, і відповідна нормаль в цій точці як ${\displaystyle n_{i}}$. Тоді градієнт індикаторної функції визначається наступним чином:

${\displaystyle \triangledown g={\begin{cases}{\textbf {n}}_{i},&\forall p_{i}\in S\\0,&{\text{в іншому випадку}}\end{cases}}}$

Потім завданням реконструкції стає варіаційним завданням. Для того, щоб знайти індикаторну функцію поверхні, ми повинні знайти функцію ${\displaystyle \chi }$ так, щоб ${\displaystyle \lVert \triangledown \chi -{\textbf {V}}\rVert }$ було зведено до мінімуму, де ${\displaystyle {\textbf {V}}}$ це векторне поле визначене зразками.

Реєстрація

Анімації зображення реєстрації часткової сітки на повну сітку, з частково-постійною аппроксимацією функції проєкції.

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

Одна загальна проблема, що виникає при геометричній обраці, як об'єднати декілька уявлень одного об'єкта захопленого з різних кутів або позицій. Ця проблема відома як реєстрація. В реєстрації, ми хочемо знайти оптимальне жорстке перетворення, яке буде вирівнювати поверхню ${\displaystyle X}$ з поверхнею ${\displaystyle Y}$. Більш формально, якщо ${\displaystyle P_{Y}(x)}$ це проєкція точки x з поверхні ${\displaystyle X}$ на поверхню ${\displaystyle Y}$, ми бажаємо знайти оптимальну матрицю обертання ${\displaystyle R}$ та вектор зміщення ${\displaystyle t}$ які мінімізують наступну цільову функцію:

${\displaystyle \int _{x\in X}||Rx+t-P_{Y}(x)||dx}$

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

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

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

${\displaystyle {\mathcal {L}}(f)=\int _{\Omega }\|f-{\bar {f}}\|^{2}+\lambda \|\nabla f\|^{2}dx}$.

беручи варіацію ${\displaystyle \delta f}$ на ${\displaystyle {\mathcal {L}}}$ виділяє необхідну умову

${\displaystyle 0=\delta {\mathcal {L}}(f)=\int _{\Omega }\delta f(\mathbf {I} +\lambda \nabla ^{2})f-\delta f{\bar {f}}dx}$.

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

${\displaystyle {\begin{aligned}\sum _{i}M_{i}\delta f_{i}{\bar {f}}_{i}&=\sum _{i}M_{i}\delta f_{i}\sum _{j}(\mathbf {I} +\lambda \nabla ^{2})f_{j}=\sum _{i}\delta f_{i}\sum _{j}(M+\lambda M\nabla ^{2})f_{j},\end{aligned}}}$

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

де наш вибір ${\displaystyle \nabla ^{2}}$ обирається бути ${\displaystyle M^{-1}\mathbf {L} }$ для контангенсу Лапласіана ${\displaystyle \mathbf {L} }$ і ${\displaystyle M^{-1}}$ - це термін, щоб відобразити зображення Лапласіан з областей до точок. Оскільки зміна є вільною, то це призводить до самосопряження лінійної задачі, яка вирішується з параметром ${\displaystyle \lambda }$: ${\displaystyle {\bar {f}}=(M+\lambda \mathbf {L} )f.}$ При роботі з трикутними сітками один спосіб визначення значень Лапласіана матриці ${\displaystyle L}$ через аналіз геометрії з'єднаних трикутників на сітці.

${\displaystyle L_{ij}={\begin{cases}{\frac {1}{2}}(cot(\alpha _{ij})+cot(\beta _{ij}))&{\text{edge ij exists}}\\-\sum \limits _{i\neq j}L_{ij}&i=j\\0&{\text{в іншому випадку}}\end{cases}}}$

Де ${\displaystyle \alpha _{ij}}$ та ${\displaystyle \beta _{ij}}$ кути напроти сторони ${\displaystyle (i,j)}$

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

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

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

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

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

${\displaystyle {\underset {U}{\text{min}}}\sum _{ij\in E}||u_{i}-u_{j}||^{2}}$

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

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

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

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

${\displaystyle {\underset {u,v}{\text{min}}}\int _{S}||\nabla u||^{2}+||\nabla v||^{2}dA}$

Є кілька інших речей для розглядання. Ми хотіли б мінімізувати кут викривлення для того, щоб зберегти ортогональність. Це означає, що ми хотіли б ${\displaystyle \nabla u=\nabla v^{\perp }}$.Крім того, ми також хотіли, щоб відображення мало пропорційно подібні зони розміру як оригінал. Це призводить до встановлення якобіану і і v координатної функції у 1.

${\displaystyle {\begin{bmatrix}{\dfrac {\partial u}{\partial x}}&{\dfrac {\partial u}{\partial y}}\\[1em]{\dfrac {\partial v}{\partial x}}&{\dfrac {\partial v}{\partial y}}\end{bmatrix}}=1}$

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

${\displaystyle {\underset {u,v}{\text{min}}}\int _{S}{\frac {1}{2}}||\nabla u||^{2}+{\frac {1}{2}}||\nabla v||^{2}-\nabla u\cdot \nabla v^{\perp }}$

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

Див. також

• Проектування за допомогою ЕОМ (CAD)
• ^[en]
• ^[en]

Посилання

1. Обробка сітки полігонів, Ботш та ін. 2010
2. . hhoppe.com. Архів оригіналу за 2 серпня 2017. Процитовано 8 травня 2017.
3. . www.ctralie.com. Архів оригіналу за 16 березня 2017. Процитовано 8 травня 2017.
4. Desbrun, Mathieu (2002). (PDF). Eurographics. 21. Архів оригіналу (PDF) за 11 серпня 2017. Процитовано 8 травня 2017.
5. Levy, Bruno (2002). (PDF). ACM Transactions on Graphics (TOG) - Proceedings of ACM SIGGRAPH 2002. 21: 362—371. Архів оригіналу (PDF) за 15 березня 2017. Процитовано 8 травня 2017.

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

• Мертве посилання (, Пітера Шродера та Віма Швелденса)
• Симпозіум з геометричної обробки [ 3 грудня 2008 у Wayback Machine.]
• Багато-досліджувальна моделювальна група [ 7 жовтня 2006 у Wayback Machine.], Каліфорнійський технологічний інститут
• Математична група геометричної обробки [ 6 вересня 2012 у Wayback Machine.], Вільний університет Берліна
• Група комп'ютерної графіки [ 22 травня 2022 у Wayback Machine.], університет Аахена
• Polygonal Книга з обробки сіток [ 24 квітня 2017 у Wayback Machine.]