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

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

ПОБУДОВА ПРОСТОРОВОЇ ЛІНІЇ ПЕРЕТИНУ ПОЛІГОНАЛЬНИХ СІТОК

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

Постановка проблеми. Важливим розділом комп’ютерної графіки є комп’ютерне гео­метричне моделювання (CAGM – Computer-Aided Geometric Modeling), мета якого полягає в створенні моделей різних геометричних об'єктів – як двовимірних, так і тривимірних. Одним з найпоширеніших прийомів створення комп’ютерних моделей тривимірних об’єктів [1] є спосіб конструктивного геометричного моделювання суцільних тіл (CSM – Constructive Solid Modeling), в якому більш складні об’єкти утворюються з більш простих тривимірних примітивів (блоків, сфер, конусів, тороїдів тощо). Базовий метод такого роду конструювання полягає у виконанні над парами об’єктів теоретико-множинних (бульових) операцій [1] знаходження об’єднань, перетинів та різниці останніх.

Оскільки тривимірні об’єкти апроксимуються найчастіше полігональними сітками [2] (скорочено “полісітками”) з пласких трикутних та чотирикутних граней, то конструювання тривимірних об'єктів за допомогою теретико-множинних операцій має підтримуватись адекватними операціями над згаданими полісітками. Коли пара сіток частково суміщається в просторі, то знаходження результату будь-якої бульової операції вимагатиме побудови просторової ламаної лінії перетину(ПЛЛП), яка є спільною для поверхонь обох полісіток (рис. 1). Об’єкт, який буде результатом об’єднання, перетину або різниці суцільних тіл, що моделюються полісітками, включатиме побудовану просторову лінію до своєї моделі як складову частину множини його ребер.

Рис. 1. Композиція двох полісіток: а – просторова лінія перетину полісіток

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

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

Опис полісітки суцільного тіла

Довільна полісітка може бути описаною, як:

M = (V, E, F),

де V, E, F – множини вершин, ребер та граней відповідно.

Множина вершин визначається як

(1)

де x,y,z – декартові координати вершини; i – номер вершини; n – кількість вершин.

Множина ребер визначається як

(2)

де m – кількість ребер полісітки.

Множина граней визначається як

(3, a)

де t_i – кількість ребер, які є контуром і-ї грані.

Формула (3, a) визначає кожну грань як ланцюжок ребер, що зустрічаються при стандартному [3 ] обході грані за годинниковою стрілкою. Між тим, зустрічаються ситуації, де доводиться використовувати опис грані через множину її вершин у порядку обходу за годинниковою стрілкою:

(3, б)

Наведений опис полісітки не віддзеркалює в повній мірі топологічну інформацію про неї. У зв’язку з цим до наведеного часто додають ще таблицю ребер у так званому «крилатому» уявленні Б. Баумгарта [3], яке пояснюється на рисунку 2. На рисунку показане ребро a, яке проходить від вершини X до вершини Y; номерами 1 та 2 позначені грані, які розташовані відповідно зліва та справа від ребра; ребра b та d являють собою відповідно ребро-попередник та ребро-послідовник ребра а при обході лівої грані 1 за годинниковою стрілкою; така ж роль ребер e та c, але при обході правої грані 2.

Таблиця 1

Формат таблиці ребер для «крилатого» уявлення (Баумгарта) полісітки

 

Рис. 2. Ребро полісітки в «крилатому» уявленні

Структури даних за виразами (1)-(3) та таблиця Баумгарта є достатніми для маніпулювання даними в границях цілей, які були визначені вище.

Визначення пар граней, які гарантовано не перетинаються. Перша проблема, з якою зустрічається розробник програмного застосування для побудови ПЛЛП, є прискорення виконання попарного перебору граней полісіток, що перетинаються на предмет визначення, чи вони дійсно перетинаються чи ні. Реальні полісітки нерідко складаються з великої кількості граней. Очевидно, що загальна кількість розрахунків тут буде пропорційна N*M, де N та М – це кількості граней обох полісіток.

Визначення факту перетину двох непаралельних граней, обмежених багатокутниками G₁ та G₂ полягає у виконанні такої послідовності дій:

1. Визначити просторову пряму L – лінію перетину площин граней. При цьому і площини граней, і шукана лінія розглядаються як безграничні.

2. Пошук точок перетину L з G₁ та G₂. Навіть коли для кожного полігона G₁ та G₂ пари таких точок PG1_1,2 та PG2_1,2 знайдені, фактичний перетин граней матиме місце лише тоді, коли відрізки (PG1₁ - PG1₂) та (PG2₁ -PG2₂) матимуть спільну частину, яка, власне, і є новим ребром Е_G1-G2, спільним для G₁ та G₂. Очевидно, що визначення Е_G1-G2 є предметом додаткового аналізу.

З вищевикладеного зрозуміло, що примітивний підхід, який може полягати у виконанні цих дій повним перебором усіх пар граней двох тривимірних об’єктів, тобто N*M разів, небажаний з точки зору трудомісткості такого алгоритму. Дії (1) та (2) треба виконувати лише для таких пар граней, котрі не відносяться до таких, які гарантовано не пересікаються.

У зв’язку з цим виглядає раціональним попередньо вдатися до швидкого аналізу взаємного розташування граней у просторі за допомогою так званих «оболонок» граней [1].

«Оболонкою» H грані назвемо габаритний прямокутний паралелепіпед, в який вписується грань. Він описується шісткою максимальних та мінімальних координат вершин грані H = H(x_min, x_max, y_min, y_max, z_min, z_max). Програмне використання оболонок потребує включення такої структури до опису кожної грані.

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

Основною структурою даних, яка має бути одержаною в результаті такого аналізу, є матриця перетинів:

(4)

Кожна компонента цієї матриці дорівнює

 

 

1, якщо оболонка грані i перетинається з оболонкою грані j;

0 у противному випадку.

 

Якщо оболонки в тривимірному просторі перетинаються, то перетинаються також їх проекції на координатні осі OX, OY, OZ. Якщо хоча б одна пара проекцій оболонок першого і другого об’єкта не перетинається хоча б уздовж однієї координатної осі, то і самі оболонки не перетинаються. Тому процес заповнення матриці (4) має проходити в три кроки, відповідно до кількості декартових координат (x, y та z) . На кожному кроці в матрицю М_с вносяться нулі для тих пар індексів оболонок, проекції котрих на вісь, яка аналізується, не мають спільних ділянок. Якщо для деякої пари (i,j) на попередніх кроках був одержаний нуль, то на поточному кроці оболонки з цими індексами перевіряти не треба, вони вже не будуть перетинатись гарантовано.

Вважаємо відомими масиви оболонок усіх граней першого та другого об’єктів, що перетинаються:

MH₁ = {H_1i | i Î 1…N};

MH₂ = {H_1j | j Î 1…M}.

Процес заповнення матриці M_c можна описати С-подібним псевдокодом:

for(i=1; i++; i

// визначення неперетинань вздовж OX

for(i=1; i++; i

for(j=1; j++; j

if(m[i][j] = =1){ // раніше факт неперетину не був виявлений

if (!((x_min2[j]max1[i]) && (x_max2[j]>=x_max1[i]) | |

((x_min2[j]min1[i]) && (x_max2[j]>=x_min1[i])))

m[i][j] = 0; // пара [i][j] не перетинається }}}.

Потім ті ж самі дії повторюються для координат y та z. У результаті ми одержимо сильно проріджену матрицю М_с. Подальшому аналізові слід піддавати тільки ті пари граней, для яких m_ij = 1, що суттєво зменшує загальний обсяг роботи. При цьому слід зауважити, що факт не перетинання оболонок є гарантією не перетину самих граней, але зворотне твердження несправедливе. Остаточна відповідь на питання «чи дійсно перетинаються грані» дається на подальших кроках описуваного алгоритму.

Визначення загальної лінії двох граней.

Вважатимемо для конкретності, що розглядається пара непаралельних пласких граней F₁ та F₂, і для кожної з них обчислене рівняння площини:

a₁*x + b₁*y + c₁* z + d₁ = 0 – для грані F₁ та a₂*x + b₂*y + c₂* z + d₂ = 0 – для грані F₂. (5)

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

Направляючий вектор знаходиться [5] за формулою:

(6)

Опорну точку (x₀,y₀,z₀) прямої знаходять [5] як точку її перетину з якоюсь з коорди­натних площин XOY, XOZ або YOZ. Для цього призначають нульове значення одній з трьох координат x₀,y₀,z₀, а дві інших заходять як рішення лінійної системи з двох рівнянь, як показано нижче. Правильне призначення початкової нульової координати вимагає попередньої перевірки положення вектора D на можливу паралельність координатним осям. Можливі варіанти згаданого положення наведені в таблиці 2.

Таблиця 2

Варіанти розташування вектора D відносно координатних осей

Пояснимо вищезгадане на прикладі варіанта 6. Покладаємо x₀ = 0. Значення y₀ та z₀ знайдемо з системи рівнянь

a₁*x₀ + b₁*y₀ + c₁* z₀ + d₁ = 0;
a₂*x₀ + b₂*y₀ + c₂* z₀ + d₂ = 0.

Пропускаючи тривіальні алгебраїчні перетворення, одержуємо:

Таким чином буде визначена безкінечна пряма, яка достовірно проходить через точку P₀(x₀,y₀,z₀) в напрямку вектора D( D_x, D_y, D_z). Довільну точку P на цій прямій можна знайти, використовуючи скалярний параметр t:

P = P₀ + tD. (7)

Пряма за рівнянням (7) є спільною прямою для двох безграничних непаралельних площин з рівняннями (5). Де на цій прямій розташоване ребро дійсного перетину полігональних граней F₁ та F₂ аналізується нижче.

Визначення загального ребра двох граней.

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

У1. Спільна лінія площин граней (P_o, D) дійсно перетинає полігони обох граней;

У2. У випадку виконання умови (У1) відрізки (x_F1—x_F2)та (x_F3—x_F4 ) додатково мають спільну частину, тобто ребро ↔ (x_F1—x_F2)∩( x_F3—x_F4).

Рис. 3, а показує випадок невиконання умови (У1), рис. 3, б ілюструє випадок виконання умови (У1), але не виконання умови (У2), а на рис. 3, в зображено випадок виконання обох умов, коли спільне ребро дійсно існує.

Рис. 3. Різні випадки розташування двох граней та спільної для них прямої:
а, б – випадки, коли грані не мають спільного ребра; в – випадок, коли спільне ребро існує

Для визначення факторів, що забезпечують виконання умови (У1), нам знадобиться метод перерахунку координат вершин граней з «світової» системи координат (СК) OXYZ систему координат, пов’язану з гранню P_oX_FY_FZ_F (рис. 4).

Рис. 4. Система координат грані PoXFYFZF

Цю систему коодинат визначимо так. Вісь P₀X_F спрямована від Р₀ вздовж направляючого вектора D. Вісь Р₀Z_F паралельна нормалі до грані F. Якщо описати базис СК грані як{i_F;j_F;k_F}, то

За цих умов СК грані є правою, як і світова СК OXYZ.

Перехід від світової СК до СК грані виконаємо за методикою [4], яка полягає у виконанні чотирьох кроків, у результаті яких СК OXYZ суміститься в просторі з СК P_oX_FY_FZ_F.

Крок 1. Суміщення початків координат, воно описується однорідною матрицею [5]:

(8)

Крок 2. Обертання базису світової СК {i;j;k}навкруги орту j з метою розташування ортів i та i_F в одній площині, перпендикулярній ортові k . Функції кута θ обертання

, .

Матриця перетворення кроку 2 має вигляд

На кроці 2 знаходимо й обчислюємо скореговані орти i_F та j_F, які знадобляться нижче (знак «штрих» означає «скорегований»):

, .

Тут треба використовувати опис векторів в однорідних компонентах, з умовною четвертою компонентою, що дорівнює 1.

Крок 3. Обертання базису {i;j;k}навкруги орту k на кут α з метою суміщення ортів i та i’_F. Функції кута обертання

, .

Матриця перетворення кроку 3:

На кроці 3 також обчислюємо .

Крок 4. Обертання базису {i;j;k}навкруги орту i= i’_F на кут β з метою суміщення ортів i та i’_F. Функції кута обертання

, .

Матриця перетворення кроку 4:

Загальна матриця переходу до СК грані

M = T₁ * R₁* R₂* R₃. (9)

Тепер треба розрахувати для кожної вершини грані її координати (x_F, y_F, z_F) в СК грані. Зауважимо, що z_F = 0 та її обчислювати не треба.

Щоб швидко визначити ті ребра (припустимо без втрати загальності, що розглядається ребро V₁ ‑V₂) полігону грані, які перетинаються з віссю P₀X_F, використаємо критерій y_F1*y_F2<0, який практично означає, що кінці ребра знаходяться по різні боки осі P₀X_F. Якщо таких ребер у полігоні грані не визначено, то ми маємо випадок грані F₂ на рис. 3, а. Це означає, що дії із знаходження перетину поточної пари граней тут треба припиняти і переходити до розгляду наступної пари граней відповідно до процесу обходу ненульових компонент матриці (4).

Після знаходження такого ребра координати точки перетину (x_ПF, 0, 0) знаходяться просто:

.

Знаходження координат кінців реального ребра, спільного для граней F₁ та F₂ (випадок на рис. 3, в) виконується після визначення x_Fi (i=1…4) звичайним порівнянням координат, тому тут не описується внаслідок простоти.

Включення нових ребер до моделі полісітки.

Коли нове ребро визначене, його треба занести до таблиці 1, а його кінці мають бути записані до множини (1). Перша дія є предметом досить складного топологічного аналізу, обговорення якого виходить за межі цієї статті. Друге потребує зворотного перерахунку координат кінців ребра з СК грані до світової СК за рівнянням

,

де М^-1 – матриця, зворотна до (9).

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

Висновки.

1. Побудова просторової ламаної лінії перетину двох полісіток може бути виконана за регулярним алгоритмом, основні кроки якого викладені в статті.

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

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

Список використаних джерел

Фоли Д. Основы интерактивной машинной графики: в 2-х книгах. Кн. 2 / Д. Фоли, вэн Дэм А. – М.: Мир, 1985. – 368 с.

Шикин Е. Компьютерная графика. Полигональные модели / Е. Шикин, А. Боресков. – М.: Диалог-МИФИ, 2000. – 464 с.

Никулин Е. А. Компьютерная геометрия и алгоритмы машинной графики / Е. А. Никулин. – СПб.: БХВ-Петербург, 2003. – 560 с.

Роджерс Д. Математические основы машинной графики: пер. с англ. / Д. Роджерс, Д. Адамс. – М.: Машиностроение, 1980. – 240 с.

Справочник по математике для инженеров и учащихся вузов / И. Н. Бронштейн, К. А. Семенляев. – М.: Наука, 1981.– 720 с.