УДК 681.3.082.5

 

С.О. Нестеренко, канд. техн. наук

Чернігівський національний технологічний університет, м. Чернігів, Україна

Алгоритм зшивання полігональних сіток

С.А. Нестеренко, канд. техн. наук

Черниговский национальный технологический университет, г. Чернигов, Украина

Алгоритм СшиванИя полИгональнЫх сЕТЕЙ

Serhii Nesterenko, PhD in Technical Sciences

Chernihiv National University of Technology, Chernihiv, Ukraine

The algorithm for polygonal networks of cross-linking

Стаття містить аналітичний виклад головних кроків алгоритму поєднання двох відкритих полігональних сіток третьою додатковою. Вирішені задачі пошуку вільного краю відкритої полісітки як просторової полілінії, визначення підмножин з’єднуваних вершин на обох вільних краях та побудови проміжної поєднальної сітки, яка описується способом Б. Баумгарта.

Ключові слова: комп’ютерне геометричне моделювання, тривимірні поверхневі моделі, полігональна сітка, уявлення Баумгарта, цілісність.

Статья содержит аналитическое изложение основных этапов алгоритма соединения двух открытых полигональных сетей третьей дополнительной. Решены задачи поиска свободного края открытой полисети как пространственной полилинии, определения подмножеств соединяемых вершин на обоих свободных краях и построения промежуточной соединяющей сети, которая описывается способом Б. Баумгарта.

Ключевые слова: компьютерное геометрическое моделирование, трехмерные поверхностные модели, полигональная сеть, представление Баумгарта, целостность.

The article contains an analytical summary of the main stages of the algorithm for connecting two open polygonal networks with third one. The problems of the search the open polymesh free edge as 3D polyline, a specific subset of connected vertices on both free ends and building the intermediate connecting network which is described in the B.Baumgart’s representation are solved.

Key words: computer geometric modeling, 3D surface models, polygonal networ, representation by Baumgart, integrity.

Постановка проблеми. Побудова просторових поверхневих моделей на основі полігональних сіток (мереж) для реальних тіл нерідко виконується з використанням лазерних технологій [1]. Реальне тривимірне тіло освітлюється променем лазера, координати яскравої точки на поверхні тіла від лазерного променя фіксуються тим чи іншим способом і на базі масиву координат подібних точок будується математичний опис поверхні тіла у формі полігональної сітки (полісітки). Як показує практика [2], полігональні сітки, одержані таким способом, нерідко є розривними, тобто неоднозв’язними. Типовим варіантом результату є такий, коли замість єдиної замкненої полісітки, яка описувала б все тіло, ми маємо кілька незамкнених сегментів (відсіків) полісіток.

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

Аналіз останніх досліджень і публікацій. Найбільш детальний огляд алгоритмів та методів роботи з просторовими полігональними сітками наведено в [3]. Разом з тим слід зазначити, що ці автори апріорі вважають просторові полігональні моделі цілісними та внутрішньо несуперечними. Проблема ремонту просторової сітки, який має на меті надання останній цілісності, не розглядається взагалі.

Деякі технічні аспекти надійного одержання множини координат просторових точок при лазерному скануванні реальних об’єктів обговорюються в [1] та [2]. Яким чином результати замірів мають перетворюватись в адекватну 3D-модель, придатну для комп’ютерного моделювання, автори не зазначають.

Таким чином, задача опису регулярного алгоритму відновлення цілісності полігональ­них сіток поки не знайшла висвітлення в літературі і тому є актуальною.

Мета статті. Головною метою цієї роботи є розроблення і формальний опис алгоритму поєднання двох відкритих полігональних сіток за допомогою додаткової третьої.

Виклад основного матеріалу.

Побудова просторової полілінії вільного краю відкритої полісітки.

Припустимо, що дана відкрита (незамкнена) полігональна сітка, тобто така, яка має вільний край. Першою підзадачею алгоритму, що описується, є одержання опису просторової полілінії, яка і є, власне, вільним краєм. Умовою приналежності ребра до вільного краю є те, що у нього з одного боку розташована грань полісітки, а з протилежного – нічого, тобто точки вільного модельного простору. Таким чином, для пошуку полілінії вільного краю нам потрібен спосіб опису полісіток, адекватний поставленій задачі. З досвіду побудови поверхневих моделей тривимірних тіл найбільш функціональ­ною виглядає [3] модель Б. Баумгарта, яка відома також як «крилата» модель.

Згідно з [4], така модель спирається на класичне використання таблиць вершин, ребер та граней полігональної сітки. Таблиця вершин є масивом тривимірних точок

(1)

де x_i, y_i, z_i – декартові координати вершини.

Другою, найбільш інформативною, частиною моделі в уявленні Б. Баумгарта є таблиця ребер, доповнена топологічною інформацією. Зміст останньої пояснимо таким чином. Традиційна репрезентація ребра зводиться до простої пари інцидентних вершин, кожна з яких однозначно визначається індексом i (1…n) з формули (1). Б. Баумгарт доповнив це уявлення топологічними даними, для використання яких були введені додаткові обмеження логічної моделі полігональної сітки:

• ребро а (рис. 1) є орієнтованим від початкової вершини M до кінцевої N. Порядок вершин неявно задається порядком запису термінальних вершин ребра в елементі масиву ребер;

• порядок обходу ребер кожної грані – за годинниковою стрілкою, дивлячись ззовні тіла.

Додаткові топологічні дані, що були запропоновані [4] Б. Баумгартом, пояснюються схемою на рис. 1.

Рис. 1. Ребро полісітки в уявленні Б. Баумгарта

Відносно традиційного варіанта, коли ребро а ↔ {M; N} в цьому випадку суттєвими доповненнями є:

– з орієнтованим ребром MN пов’язуються грані R та L, розташовані відповідно справа та зліва від ребра. На практиці вказуються або індекси i цих граней (i∈[1; G_max], (G_max – кількість граней полісітки), або вказівники на них. Домовимось використовувати константу NULL як значення вказівника на будь-який відсутній елемент полігональної сітки;

– з ребром MN зв’язуються інцидентні йому сусідні ребра правої та лівої граней, які передують йому (d та c) або слідують за ним (b та e) в порядку обходу відповідної грані.

Отже, множина ребер полігональної сітки згідно з Баумгартом може бути описана як

Е = {{a_i; M_i; N_i ; b_i ; c_i ; d_i ; e_i ; L_i ; R_i }_i | i∈[1; G_max]}, (2)

де сенс згаданих змінних ясний із викладеного вище.

Множина (2) програмно відображається на таблицю ребер, елементами якої є записи зі структурою, що відповідає параметрам ребра в уявленні Баумгарта. Ми використаємо таку логічну модель полісітки як найбільш адекватну поставленій задачі.

Тепер припустимо, що дана відкрита (незамкнена) однозв’язна полігональна сітка, тобто така, яка має вільний край (рис.2).

Рис. 2. Полісітка з відкритим краєм

Для пошуку множини вершин просторової полілінії вільного краю можна запропонувати таку послідовність дій.

Початок алгоритму 1.

Крок 1. Знайти будь-яке ребро E₀, в якого відсутня грань чи справа, чи зліва. Критерій пошуку такого ребра в нотації мови програмування С:

((L == NULL) ^ (R == NULL)) == TRUE. (3)

Запам’ятати початкову вершину V₀ цього ребра і записати її до масиву M_Vfree вершин полілінії вільного краю полісітки. Очевидно, що масив M_Vfree є фізичною реалізацією множини вершин вільного контуру

V_free = {V_{free i} | i ∈ [1… k]}, (4)

де k – кількість вершин вільного контуру.

Прийняти V₀ як поточну початкову вершину V_k поточного ребра, яке розглядається.

Крок 2. Перейти на поточному ребрі до протилежної вершини ребра V_k+1 і записати його до масиву M_Vfree вершин полілінії вільного краю полісітки. Якщо V_k+1 = = V₀, вийти з циклу на точку 4. Якщо ні, то перебором усіх ребер, які інцидентні цій вершині, знайти ребро, що відповідає умові (3).

Крок 3. Прийняти V_k+1 як V_k наступної ітерації і перейти на крок 2.

4. Точка виходу з циклу.

Кінець алгоритму 1.

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

Виділення множини з’єднуваних вершин у парі крайових контурів.

Постановка задачі. Розглянемо пару вільних країв двох полісіток, що мають бути поєднані описуваним алгоритмом (рис. 3). З очевидних практичних міркувань можна сформулювати обмеження на множину вершин вільних країв першої та другої полісітки, що будуть поєднуватись додатковою полісіткою: нею мають «зшиватись» вершини контурів, просторово найближчі одні до одних. Такі вершини показані на рис. 3 білими точками, на відміну від тих, які в поєднанні задіяні не будуть, і вони показані чорними точками.

Рис. 3. Пара вільних контурів (проекція на площину малюнка):  – вершини, які будуть поєднуватись;
 – вершини, які не будуть поєднуватись

Наведемо евристичний алгоритм, за яким у множинах V_free¹ та V_free² вершин вільних контурів 1 і 2 виділяються підмножини V_free^1с та V_free^2с вершин, придатних для подальшого поєднання (показані на рис. 3 білими точками). Ідея алгоритму полягає в наступному.

Для кожного вільного контуру знаходиться умовний центр С і тим самим визначається пара міжцентрових векторів та . Вектор визначає перпендикулярну йому площину П₁, яка проходить через точку С_1. Аналогічно через вектор і точку С₂ визначається площина П₂. На рис. 3 показані сліди цих площин на площині рисунка. Подальші дії стосуються визначення того, з якої сторони відповідної площини знаходяться точки множин V_free¹ та V_free². У підмножини V_free^1с та V_free^2с мають входити тільки точки, розташовані з додаваної сторони відповідної площини.

Початок алгоритму 2.

Крок 1. Обчислити координати усереднених точок (умовних центрів) С₁ та С₂ вільних контурів за формулою (наводиться для одного контуру):

(5)

де V_i – радіус-вектор i-ї вершини.

Крок 2. Обчислити міжцентрові вектори

a₁ = C₂ - C₁; a₂ = C₁ - C₂. (6)

Крок 3. Визначити рівняння площин П₁ і П₂ :

• для площини П₁

(P_П1-С₁)⋅ a₁ = 0; (7а)

• для площини П₂

(P_П2-С₂)⋅ a₂ = 0, (7б)

де P_П1 – довільна точка площини П₁ ;

P_П2 – довільна точка площини П₂.

Крок 4. Перебором точок множини {V_free¹} сформувати підмножину {V_free^1с} за умовою (V_{free i} ^1с - С₁)⋅ a₁ > 0.

Крок 5. Перебором точок множини {V_free²} сформувати підмножину {V_free^2с} за умовою (V_{free i} ^2с – С₂)⋅ a₂ > 0.

Кінець алгоритму 2.

Побудова поєднувальної полігональної сітки

Попередній розділ як результат мав дві просторові полілінії (опорні лінії) A та B (рис. 4, а), на основі яких ми можемо побудувати проміжну полігональну сітку (ППС), що є метою цього дослідження. Без втрати геометричної загальності з метою побудови простого алгоритму в подальшому викладі будемо спиратись на спрощену топологічно тотожну [5] геометричну модель цих ліній (рис. 4, б), в якій вершини рівномірно розташовані на прямій, паралельній довільній осі х, а повна модельна довжина ліній A та B умовно приймається однаковою. Лінії, що поєднуватимуть вершини ліній A та B, наприклад А₁-B₁, умовно назвемо «меридіани» полісітки, яку ми проектуємо. Також у подальшому завжди вважатимемо лінією А ту, яка має кількість вершин N більшу, або рівну кількості вершин М лінії В.

Рис. 4. Схеми до побудови проміжної поєднувальної сітки: а – бажаний результат;
б – топологічно тотожна модель для побудови проміжної полісітки; показані меридіани

Першою підзадачею в побудові ППС є визначення пар вершин ліній A та B, поєднання яких формує множину меридіанів ППС.

Як видно з рис. 4, б, меридіани мають поєднувати всі вершини A_i | i ∈ [1…N] з усіма вершинами B_j | j ∈ [1…M]. Очевидно, що при N>M виконання цієї умови приводить до того, що кожній вершині A_i | i ∈ [1…N] завжди інцидентний рівно один меридіан, а на лінії В будуть існувати вершини, інцидентні кільком меридіанам. Для визначення матриці інцидентності меридіанів введемо модельну метрику розташування вершин вздовж осі х (рис. 4, б). За цією метрикою будемо вважати повну модельну довжину ліній A та B рівній (N-1)·(M-1), а х-координати вершин A_i становлять арифметичну прогресію (M-1)·(i-1) | i ∈ [1…N] . Аналогічно, х-координати вершин B_j становлять арифметичну прогресію (N-1)*(j-1) | j ∈ [1…M]. Як критерій існування меридіана, який поєднує вершину A_i з вершиною B_j , приймемо мінімальність модельної відстані між ними. Іншими словами, при фіксованій вершині A_i | i ∈ [1…N] інцидентний їй меридіан буде проводитись до вершини лінії B з таким індексом j ∈ [1…M] , за якого модельна відстань

D_ij = |x_Ai – x_Bj| = |(M-1)·(i-1) - (N-1)·(j-1)|

буде мінімальною.

Назвемо матрицею меридіанів H таку матрицю {H_ij}| i [1…N], | j [1…M], в якій H_ij = 1, якщо існує меридіан між A_i та Bj, в іншому випадку H_ij = 0. Очевидно, що побудова такої матриці може бути виконана двома вкладеними циклами (в нотації мови С):

// Початок програмного фрагмента.

Всі елементи {H_ij}=0;

for( i=1; i< N; i++) {

Dmin = (N-1)*(M-1);

for(j=1; j<M; j++)

Dij = abs((M-1)*(i-1) - (N-1)*(j-1));

If (Dij<=Dmin)

Dmin = Dij;

Else {j - -; break;}

H_ij = 1; // меридіан буде проведений між A_i та Bj

}

// Кінець програмного фрагмента.

Таким чином, підзадачу побудови множини меридіанів проміжної з’єднувальної полісітки можна вважати вирішеною.

Другою підзадачею будемо вважати побудову матриці вершин Р проміжної сітки. Оскільки канонічна поверхнева модель у вигляді полігональних сіток завжди оперує [6], крім іншого, таблицею вершин {V_k}={x_k, y_k, z_k} (де k – індекс вершини полісітки), то елементами Р можуть бути просто індекси тих вершин, які входитимуть до ППС.

Побудову Р пояснимо на конкретному прикладі ППС з М=6 і N=4 (рис. 5).

Рис. 5. Схема до побудови матриці вершин Р проміжної полісітки

Спочатку в цій матриці Р визначені тільки перший та останній рядки, в яких перелічуються вершини поліліній А та В:

A₁ A₂ A₃ A₄ A₅ A₆

? ? ? ? ? ?

… … … … … …

? ? ? ? ? ?

B₁ B₂ B₂ B₃ B₃ B₄

Треба розділити меридіани на менші відрізки додатковими точками С, індекси яких ми будемо розміщувати в додаткових проміжних рядках матриці Р.

Кількість додаткових проміжних рядків матриці Р дорівнює кількості додаткових точок на кожному меридіані, і вона може призначатись з практичних міркувань. Одним з можливих критеріїв може бути намагання забезпечити довжину часткового відрізка меридіана (скажімо, А₁-С₁₁ на рис. 5) можливо близькою до середньої довжини ребра полісіток, що поєднуються.

Просторові координати проміжних вершин розраховуються, виходячи з відомих просторових координат крайніх точок відповідного меридіана та визначеної кількості точок ділення С. Кожна розрахована нова вершина вноситься до таблиці вершин {V_k}, а її індекс – до матриці Р.

Таким чином, друга підзадача може вважатись вирішеною.

Третя підзадача – формування нових ребер та граней ППС. Вона досить тривіальна і вирішується на основі побудованої матриці вершин Р.

Формування нових ребер ППС можна виконати процедурою обходу матриці вершин з послідовним розглядом пар сусідніх вершин як вздовж меридіанів ППС, так і в перпендикулярному напрямку. Кожна з названих пар вершин є основою для внесення запису про нове ребро в таблицю ребер Е (див. (2)). Треба зазначити, що на цьому етапі роботи елементи L_i та R_i, в записах про нове ребро, які є індексами правої та лівої граней, тимчасово є невизначеними. Причина цього в тому, що в таблиці граней полігональ­ної моделі об’єднаної полісітки поки що нема записів про згадані грані. Після внесення цих нових записів у таблицю граней потрібно повернутись до таблиці ребер та доповнити записи нових ребер відповідними даними.

Формування нових граней ППС також виконується послідовним розглядом четвірок