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

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

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

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

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

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

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

Одна загальна проблема, що виникає при геометричній обраці, як об'єднати декілька уявлень одного об'єкта захопленого з різних кутів або позицій. Ця проблема відома як реєстрація. В реєстрації, ми хочемо знайти оптимальне жорстке перетворення, яке буде вирівнювати поверхню ${\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}$ невелика. Ітеративне рішення, наприклад, Ітераційна найближча точка(ІНТ) використовується, для вирішення малих перетворень послідовно, замість того, щоб вирішувати потенційно великі перетворення на одному диханні. В ІНТ обираються n зразкових точок з ${\displaystyle X}$ і проєктуються на ${\displaystyle Y}$. Тоді оптимальне перетворення обчислюється на основі різниці між кожним ${\displaystyle X}$ і його проекцією. У наступній ітерації, проекції обчислюються на підставі результату застосування попереднього перетворення на зразках. Процес повторюється до збіжності.

Коли форми визначені або відскановані, там може бути супроводжуючий шум, або сигнал, що діє на поверхню або на фактичну геометричну поверхню. Зниження шуму, раніше було відоме як шумопоглинання, зараз відомо як поверхневий обтічник. Завдання геометричного згладжування є аналогом зниження рівня сигналу шуму, і, отже, використовує аналогічні підходи. Відповідний лагранжіан, який треба звести до мінімуму, отримується шляхом запису відповідності вихідного сигналу ${\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)}$[3]

Іноді нам потрібно згладити 3D поверхню на площину. Цей процес відомий як параметризація. Мета полягає в тому, щоб знайти координати 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 координатних функціях. При такому підході цільової функцією стає енергія Діріхле на 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}$

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

${\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)
• Промислові КТ сканування
• Список інтерактивного програмного забезпечення геометрії

• Мертве посилання (Siggraph 2001 Course on Digital Geometry Processing, Пітера Шродера та Віма Швелденса)
• Симпозіум з геометричної обробки
• Багато-досліджувальна моделювальна група, Каліфорнійський технологічний інститут
• Математична група геометричної обробки, Вільний університет Берліна
• Група комп'ютерної графіки, університет Аахена
• Polygonal Книга з обробки сіток