Дипломная (вкр): Технології побудови тривимірних моделей у ГІС

Рис. 2.3 Різні варіанти перетину зі скануючи ми рядками (див. пояснення у тексті)

.2 Задача вилучення невидимих ліній і поверхонь при відтворенні тривимірних моделей у ГІС

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

Необхідність видалення невидимих ліній, ребер, поверхонь або об'ємів проілюстрована мал. 2.5. На рис. 2.5, а наведене типове каркасне креслення куба. Його можна інтерпретувати подвійно: як вид куба зверху, ліворуч або знизу, праворуч. Видалення тих ліній або поверхонь, які невидимі з відповідної точки зору, дозволяють позбутися від неоднозначності. Результати показані на рис.2.5, b і c.

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

Для машинної мультиплікації потрібні алгоритми, які можуть генерувати складні реалістичні зображення, у яких представлені тіні, прозорість і фактура, що враховують ефекти відбиття й переломлення кольорів у дрібних відтінках. Подібні алгоритми працюють повільно, і найчастіше на обчислення потрібно кілька хвилин або навіть годин. Строго кажучи, вигляд ефектів прозорості, фактури, відбиття тощо не входить до завдання видалення невидимих ліній або поверхонь. Краще вважати їх частиною процесу візуалізації зображення. Процес візуалізації є інтерпретацією або поданням зображення або сцени в реалістичній манері. Однак багато із цих ефектів убудовані в алгоритми видалення невидимих поверхонь і тому будуть порушені. Існує тісний взаємозв'язок між швидкістю роботи алгоритму й детальністю його результату. Жоден з алгоритмів не може досягти гарних оцінок для цих двох показників одночасно. У міру створення усе більше швидких алгоритмів можна будувати усе більше детальні зображення. Реальні задачі, однак, завжди будуть вимагати обліку ще більшої кількості деталей.

Алгоритми видалення невидимих ліній або поверхонь можна класифікувати за способом вибору системи координат або простору, у якому вони працюють. Алгоритми, що працюють в об'єктному просторі, мають справу з „фізичною” системою координат, у якій описані ці об'єкти. Геоінофрмаційні системи потім відтворюють тривимірні моделі місцевості у географічних чи прямокутних координатах, відповідно до обраної картографічної проекції [20].

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

Об'єм обчислень для будь-якого алгоритму, що працює в об'єктному просторі, і об'єкт, що порівнює кожний, сцени з усіма іншими об'єктами цієї сцени, росте теоретично як квадрат числа об'єктів (n²). Аналогічно, об'єм обчислень будь-якого алгоритму, що працює в просторі зображення й об'єкт, що порівнює кожний, сцени з позиціями всіх системе у системі координат екрана, росте теоретично, як n. Тут n - кількість об'єктів (тіл, площин або ребер) у сцені, а N - число пікселів. Теоретично трудомісткість алгоритмів, працюючих в об'єктному просторі, менше трудомісткості алгоритмів, що працюють у просторі зображення, при n < N. Оскільки N звичайно дорівнює ( 512 )², те теоретично більшість алгоритмів варто реалізовувати в об'єктному просторі [33].

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

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

( x, в, z ) = 0

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

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

На рис. 2.6 наведений приклад, де зазначені паралельні площини визначаються постійними значеннями z. Функція F ( x, у, z ) = 0 зводиться до послідовності кривих, що лежать у кожній із цих паралельних площин, наприклад до послідовності

y = f ( x, z ) або y = g ( y, z )

де z постійно на кожній із заданих паралельних площин (рис. 2.2).

Отже, поверхня тепер складається з послідовності кривих, що лежать у кожній із цих площин, як показано на рис. 2.7. Тут передбачається, що отримані криві є однозначними функціями незалежних змінних. Якщо спроецировать отримані криві на площину z = 0, то відразу стає ясна ідея алгоритму видалення невидимих ділянок вихідної поверхні. Алгоритм спочатку впорядковує площини z = const по зростанню відстані до них від точки спостереження. Потім для кожної площини, починаючи з найближчої до точки спостереження, будується крива, що лежить на ній. Алгоритм видалення невидимої лінії полягає в наступному: якщо на поточній площині при деякім заданому значенні x відповідне значення y на кривій більше значення y для всіх попередніх кривих при цьому значенні x, то поточна крива видима в цій точці; у противному випадку вона невидима (рис. 2.3).

Реалізація даного алгоритму досить проста. Для зберігання максимальних значень y при кожному значенні x використається масив, довжина якого дорівнює числу помітних крапок (дозволу) по осі x у просторі зображення. Значення, що збеігаюься в цьому масиві, являють собою поточні значення «обрію». Тому в міру малювання кожної черговий кривий цей обрій «спливає». Фактично цей алгоритм видалення невидимих ліній працює щораз із однією лінією.

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

Рис. 2.6 Січні площини з постійною координатою

Рис. 2.7 Криві в січних площинах з постійною

алгоритм буде вважати їх невидимими. Нижня сторона поверхні робиться видимої, якщо модифікувати цей алгоритм, включивши в нього нижній обрій, що опускається вниз по ходу роботи алгоритму (рис. 2.8) [22, 33].

Це реалізується за допомогою другого масиву, довжина якого дорівнює числу помітних крапок по осі x у просторі зображення. Цей масив містить найменші значення y для кожного значення x. Алгоритм тепер стає таким: якщо на поточній площині при деякім заданому значенні x відповідне значення y на кривій більше максимуму або менше мінімуму по y для всіх попередніх кривих при цьому x, то поточна крива видима. У противному випадку вона невидима (рис. 2.8). У викладеному алгоритмі передбачається, що значення функції, тобто y, відомо для кожного значення x в просторі зображення.

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

У такому випадку використається лінійна інтерполяція значень у між відомими значеннями для того, щоб заповнити масиви верхніх і нижнього плаваючих обріїв, як показано на схемі (рис 2.9). Якщо видимість кривої міняється, то метод з такою простою інтерполяцією не дасть коректного результату. Припускаючи, що операція по заповненню масивів проводиться після перевірки видимості, одержуємо, що при переході поточної кривої від видимого до невидимого стану (сегмент АВ на рис. 2.9), точка (x_n+k, y_n+k ) вважається невидимою.

Рис. 2.8 Принцип „плаваючого горизонту”

Тоді ділянка кривої між точками (x_n, y_n) і (x_n+k, y_n+k) не зображується й операція по заповненню масивів не виконується.

Утвориться зазор між поточною й попередньою кривими Якщо на ділянці поточної кривої відбувається перехід від невидимого стану до видимого, то точка (x_m+k, y_m+k ) „оголошується” видимою, а ділянка кривої між крапками (x_m, y_m) і (x_m+k, y_m+k ) зображується й операція по заповненню масивів проводиться. Тому зображується й невидимий відрізок сегмента CD.

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

Отже, точне значення точки перетинання двох прямолінійних відрізків, які інтерполюють поточна й попередня криві, між точками (x_n, y_n) і (x_n+k, y_n+k ) (рис. 2.6) задається формулами [22, 33]:

Рис.2.9

де

а індекси c і p відповідають поточній і попередній кривим. Отриманий результат показаний на мал. 2.6. Тепер алгоритм викладається більш формально.

Якщо на поточній площині при деякім заданому значенні x відповідне значення y на кривій більше максимуму або менше мінімуму по y для всіх попередніх кривих при цьому x, то поточна крива видима. У противному випадку вона невидима.

Якщо на ділянці від попередні (x_n) до поточні (x_n+k) значення x видимість кривої змінюється, то обчислюється крапка перетинання (x_i).

Якщо на ділянці від x_n до x_n+k сегмент кривій повністю бачимо, то він зображується цілком; якщо він став невидимим, то зображується фрагмент від x_n до x_i; якщо ж він став видимим, то зображується фрагмент від x_i до x_n+k.

3. Моделювання рельєфу і операції з ЦМР із використанням методів растрової і векторної графіки

.1 Застосування методів комп’ютерної графіки і обчислювальної геометрії для створення тривимірних карт

.1.1 Растрові моделі

У ГІС існують два основних методи представлення географічного простору взагалі і рельєфу земної поверхні зокрема. Перший метод використовує квантування (quantization), або ж розбивку простору на безліч елементів, кожний з яких представляє малу, але цілком певну ділянку земної поверхні. Це растровий (raster) метод. Він дозволяє використати елементи будь-якої придатної геометричної форми за умови, що вони можуть бути з'єднані для утворення суцільної поверхні, що представляє весь простір області, що картографується.

Форми елементів (комірок, ячейок) растру можуть бути різноманітними, наприклад, трикутними або шестикутними. Однак набагато простіше використати прямокутники, а ще краще - квадрати, які називають растровими комірками, або ячейками (grid cells). У растрових моделях ячейки однакові за розміром, але це не є обов'язковою вимогою для розбивки простору на елементи (наприклад у методі квадродерева комірки можуть мати різний розмір). У нашій роботі ми розглядаємо моделі, у яких всі ячейки - однакового розміру.

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

Це специфічна форма зміни просторової розмірності, яка використовується у ГІС дуже часто і яка полягає у тому, що ми зображуємо об'єкт, що не має розмірів (точку), за допомогою об'єкта (ячейки), що має довжину й ширину. Лінії, тобто одномірні об'єкти, зображуються як ланцюжки з'єднаних ячейок. Знову ж, тут має місце зміна просторової розмірності від одномірних об'єктів до двомірних структур. Кожна точка лінії представляється коміркою растра, і кожна точка лінії повинна перебувати всередині одного з осередків растра. Ця структура даних зображує лінії східчастим образом. Цей східчастий вид також виявляється при зображенні областей за допомогою осередків растра.

У растрових системах є два способи включення атрибутивної інформації про об'єкти. Найпростішим є присвоювання значення атрибута (наприклад, абсолютної висоти місцевості) кожній ячейці растра. Розподіляючи ці значення, ми в остаточному підсумку „дозволяємо” позиціям значень атрибутів відігравати роль місць розташування об'єктів. Наприклад, якщо числом 130 ми представляємо певну ячейку растру, то за умовчанням цей осередок є ділянкою земної поверхні, вся територія якого має висоту 130 м над рівнем моря. У такий спосіб ми можемо кожній ячейці на даній карті присвоїти тільки одне значення атрибута. Альтернативний підхід полягає у пов’язуванні кожної ячейки растру з базою даних, так що будь-яке число атрибутів може бути присвоєно кожній комірці растру. Цей підхід стає все більш популярним у ГІС-технологіях, тому що він зменшує обсяг даних, необхідних для зберігання і може забезпечувати зв'язок з іншими структурами даних, які також використають СУБД для зберігання й пошуку даних.

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

Зрозуміло, що чим більше розмір ячейки, тим більшу площу землі вона покриває, тобто, тим менше (грубіше) роздільна здатність (resolution) растра, тим менша точність положень точок, ліній і областей, представлених даною структурою [21].

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

Растрові структури мають суттєвий недолік - відсутність точної інформації про місцерозташування. Однак растрові структури геопросторових даних мають і багато переваг перед іншими. Зокрема, вони відносно легко розуміються як метод подання простору. Існує також багато спільного споріднення між пікселом, використовуваному в дистанційному зондуванні, і ячйкою растру, використовуваній у ГИС. Це забезпечує легкий перенос супутникових зображень у ГІС, що оперує растрами і це не вимагає яких-небудь змін форматів файлів. Ще однією важливою характеристикою растрових систем є те, що багато функцій, особливо пов'язаних з операціями з поверхнями й накладенням (overlay), легко виконуються за умови представлення даних як растрових файлів [21, 26].