Кемеровський Державний Університет кафедра математичного аналізу
Курсова робота з теми:
Тривимірна комп'ютерна графіка
Виконав: студент М-963
Печеркін Ю. К.
Керівник: Кім В. Б.
Кемерово 1999
Введення
Машинна графіка в даний час вже цілком сформувалася як наука.
Існує апаратне і програмне забезпечення для отримання різноманітнихзображень - від простих креслень до реалістичних образів природнихоб'єктів. Машинна графіка використовується майже в усіх наукових та інженернихдисциплінах для наочності сприйняття і передачі інформації. Знання їїзасад у наш час необхідно будь-якому вченому або інженеру. Машинна графікавладно вторгається в бізнес, медицину, рекламу, індустрію розваг.
Застосування під час ділових нарад демонстраційних слайдів,підготовлених методами машинної графіки та іншими засобів автоматизаціїконторського праці, вважається нормою. У медицині стає звичайнимотримання тривимірних зображень внутрішніх органів за даними комп'ютернихтомографів. У наші дні телебачення та інші рекламні підприємства частовдаються до послуг машинної графіки та комп'ютерної мультиплікації.
Використання машинної графіки в індустрії розваг охоплює такінесхожі області як відеоігри та повнометражні художні фільми.
На сьогоднішній день створено велику кількість програм, що дозволяютьстворювати і редагувати тривимірні сцени та об'єкти. Серед найбільшпопулярних можна назвати такі як 3D studio Max, яка дозволяєтривимірні комп'ютерні ролики. Область її застосування в основному реклама,мультиплікація та оформлення телевізійних передач. Інший не меншпопулярний пакет програм це Auto-CAD. Він застосовується в основномуінженерами і проектувальниками для створення креслень і просторовихмоделей. Крім цих існує безліч інших спеціалізованихпрограмних пакетів що охоплюють практично всі сторони людськоїжиття.
Серед різноманіття можливостей, що надаються сучаснимиобчислювальними засобами, ті, що засновані на просторово-образномумисленні людини, займають особливе місце. Сучасні програмно -оперативні засоби комп'ютерної графіки є вельмиефективний інструмент підтримки такого мислення при виконанні робіт самихрізних видів. З іншого боку саме просторово-образне мисленняє неформальною творчої основою для розширення образотворчихможливостей комп'ютерів. Це важлива обставина припускає взаємнозбагачує співробітництво все більш досконалої техніки і людини з усімбагатством знання, накопиченого попередніми поколіннями. Око і ранішебув ефективним засобом пізнання людиною світу і себе. Тому настількипривабливою виявляється комп'ютерна візуалізація, особливовізуалізація динамічна, яку слід розглядати як найважливішийінструмент для навчання наукам.
1. Введення в машинну графіком
Сучасна машинна графіка - це ретельно розроблена дисципліна.
Докладно досліджені сегменти геометричних перетворень і описівкривих і поверхонь. Також вивчені, але все ще продовжують розвиватисяметоди растрового сканування, відсікання, видалення ліній і поверхонь,колір, зафарбування, текстура і ефекти прозорості. Зараз найбільший інтереспредставляють саме ці розділи машинної графіки.
Машинна графіка - складна і різноманітна дисципліна. Для вивчення її,перш за все, необхідно розбити на частини доступні для огляду. Перш за всенеобхідно розглянути методи і алгоритми растрової графіки. Це доситьпростий, але дуже важливий розділ машинної графіки. У цьому розділірозглядаються алгоритми малювання відрізків і кіл на екранімонітора, методи растрової розгортки, заповнення багатокутників,усунення ступінчастості або сходового ефекту. Окремо слідрозглянути методи відсікання зображення, тобто відбору тієї інформації,яка необхідна для візуалізації конкретної сцени.
При побудові тривимірної сцени виникає проблема видалення невидимихліній і поверхонь. Це одна з найбільш складних складовихвізуалізації тривимірних об'єктів. Способи досягнення ефектів прозорості,відображення і т.п., строго кажучи, не входять в завдання видалення невидимихчастин тривимірних об'єктів і, тим не менш, деякі з них тісно пов'язаніз цією проблемою. Наприклад, побудова тіней. Не дивлячись на це, вкомп'ютерній графіці виділяється досить великий розділ, присвяченийпобудови реалістичних зображень, у якому докладно розглядаютьсяметоди створення таких ефектів як дзеркальне відображення, заломлення променівв різних середовищах, тіні, фактура об'єкта. Так само розглядаються різніджерела світла, їх спектральні характеристики і форма. Сюди ж відносятьсяколірні ефекти, згладжування поверхонь і багато іншого.
Як видно з вище сказаного комп'ютерна графіка це доситьоб'ємна дисципліна, тому я зупинюся лише на деяких її найбільшцікавих аспектах.
2. Растрова графіка
Будь-яке зображення, в тому числі і тривимірне, складається з графічнихпримітивів. Тому, перш за все, необхідно знати спеціальні методигенерації зображення, креслення прямих і кривих ліній, зафарбовуваннябагатокутників, що створює враження суцільних об'єктів. Розглянемодеякі з цих методів.
1. Алгоритми креслення відрізків
Оскільки екран дисплея можна розглядати як матрицю дискретнихелементів (пікселів), кожен з яких може бути підсвічений, не можнабезпосередньо провести відрізок з однієї точки в іншу. Процесвизначення пікселів, найкращим чином апроксимуючих заданий відрізок,називається розкладом в растр. Для горизонтальних, вертикальних інахилених під кутом 45 (відрізків вибір растрових елементів очевидний. Прибудь-якої іншої орієнтації вибрати потрібні пікселі важче.
Існують різні алгоритми виконують цю задачу. Розглянемо дваз них.
2. Цифровий диференціальний аналізатор
Один з методів розкладання відрізка в растр полягає у вирішеннідиференціального рівняння, що описує цей процес. Для прямої лініїмаємо:
або н
Рішення видається у вигляді
де x1, y1 і x2, y2 - кінці розкладаного відрізка і yi - початкове значеннядля чергового кроку вздовж відрізка. Фактично рівняння (2.1.) Являєсобою рекурентні співвідношення для послідовних значень y уздовжпотрібного відрізка. Цей метод, що використовується для розкладання в растр відрізків,називається цифровим диференціальних аналізатором (ЦБА). У простому ЦБА або
, Або (більше з збільшень) вибирається в якості одиницірастру. Нижче наводиться простий алгоритм, який працює у всіх квадрантах:
Процедура розкладання в растр відрізка за методом цифрового диференціальногоаналізатора (ЦБА)
передбачається, що кінці відрізка (x1, y1) та (x2, y2) не збігаються
Integer - функція перетворення дійсного числа в ціле.
Примітка: у багатьох реалізаціях функція Integer означає взяття цілоїчастини, тобто Integer ((8.5) = (9, а не (8. В алгоритмі використовується саметака функція.
Sign (функція, що повертає (1, 0, 1 для негативного нульового іпозитивного аргументу відповідно.
if abs (x2 (x1) (abs (y2 (y1) then
Довжина = abs (x2 (x1)else
Довжина = abs (y2 (y1)end ifдумаємо більше з збільшень (x або (y рівним одиниці растру
(x = (x2 (x1)/Довжина
(y = (y2 (y1)/Довжинаокругляємо величини, а не відкидаємо дробову частинавикористання знакової функції робить алгоритм придатним для всіхквадрантівx = x1 + 0.5 * Sign ((x)y = y1 + 0.5 * Sign ((y)початок основного циклуi = 1while (i (Довжина)
Plot (Integer (x), Integer (y)) x = x + (xy = y + (yi = i + 1end whilefinish
За допомогою цього алгоритму отримують прямі, цілком задовільноговиду, але в нього є ряд недоліків. По-перше, погана точність у кінцевихточках. По-друге, результати роботи алгоритму залежать від орієнтаціївідрізка. До того ж запропонований алгоритм використовує дійсну арифметику,що помітно знижує швидкість виконання.
3. Алгоритм Брезенхема
Алгоритм Брезенхема вибирає оптимальні растрові координати дляподання відрізка. У процесі роботи одна з координат - або x, або у
(в залежності від кутового коефіцієнта) - змінюється на одиницю. Змінаінший координати (або на нуль, або на одиницю) залежить від відстаніміж дійсним станом відрізка і найближчими координатами сітки.
Таку відстань називається помилкою.
Алгоритм побудований так, що потрібно перевіряти лише знак цієї помилки.
На Рис.2.1 це ілюструється для відрізка в першу
Ѕ ((y (1 (помилка (0)
0 ((y/(x <Ѕ (помилка (x then
Врем = (x
(x = (y
(y = Врем
Обмін = 1else
Обмін = 0end ifініціалізація з поправкою на половину пікселя
= 2 * (y ((xосновний циклfor i = 1 to (x
Plot (x, y)
While ((0)
If Обмін = 1 then x = x + s1 else y = y + s2 end if
= (2 * (x end while if Обмін = 1 then y = y + s2 else x = x + s1 end if
= + 2 * (ynext ifinish
Цей алгоритм відповідає найсуворішим вимогам. Він маєприйнятну швидкість і може бути легко реалізований на апаратному абомікропрограмного рівні.
4. Алгоритм Брезенхема для генерації кіл
У растр потрібно розкладати не тільки лінійні, але й інші, більш складніфункції. Розкладання конічних перерізів, тобто кіл, еліпсів,парабол, гіпербол присвячено значну кількість робіт. Найбільшу увагу,зрозуміло, приділено кола. Один з найбільш ефективних і простих длярозуміння алгоритмів генерації кола належить
Брезенхему. Для початку зауважимо, що необхідно згенерувати тільки однувосьму частину кола. Решта її частини можуть бути отриманіпослідовними відбитками, як це показано на рис. 2.3. Якщозгенерований перший Октант (від 0 (до 45 (проти годинникової стрілки), то другийОктант можна отримати дзеркальним відображенням відносно прямої у = x, щодає в сукупності перший квадрант. Перший квадрант відбиваєтьсявідносно прямої x = 0 для отримання відповідної частини кола піддругий квадранті. Верхня півколо відбивається відносно прямої у =
0 для завершення побудови. На ріс.2.3. наведено двовимірні матрицівідповідних перетворень.
Для виведення алгоритму розглянемо першу чверть кола з центром упочатку координат. Зауважимо, що якщо робота алгоритму починається в точці x =
0, у = R, то при генерації колу за годинниковою стрілкою в першому квадрантіу є монотонно спадної функцією аргументу x (рис. 2.4). Аналогічно,якщо вихідною точкою є y = 0, x = R, то при генерації колапроти годинникової стрілки x буде монотонно спадної функцією аргументу у. Унашому випадку вибирається генерація за годинниковою стрілкою з початком в точці x =
0, у = R. Передбачається, що центр кола та початкова точка знаходятьсяточно в точках растру.
Для будь-якої заданої точки на колі при генерації за годинниковою стрілкоюіснує тільки три можливості вибрати наступний піксель, найкращимчином наближує коло: горизонтально вправо, по діагоналі вниз івправо, вертикально вниз. На ріс.2.5 ці напрямки позначенівідповідно mH, mD, mV. Алгоритм вибирає піксель, для
якого мінімальний квадрат відстані між одним з цих пікселів іколом, тобто щонайменше з mH = | (xi + 1) 2 + (yi) 2 - R2 | mH = | (xi + 1) 2 + (yi (1) 2 - R2 | mH = | (xi) 2 + (yi (1) 2 - R2 |
Обчислення можна спростити, якщо зауважити, що в околиці точки (xi, yi) можливі тільки п'ять типів перетинів кола та сітки растру,наведених на ріс.2.6.
Різниця між квадратами відстаней від центру кола додіагонального піксела (xi + 1, yi (1) і від центру до точки на колі
R2 дорівнює
Як і в алгоритмі Брезенхема для відрізка, для вибору відповідногопікселя бажано використовувати тільки знак помилки, а не її величину.
При (<0 діагональна точка (xi + 1, yi (1) знаходиться всерединіреальної кола, тобто це випадки 1 або 2 на ріс.2.6. Ясно, що в ційситуації слід вибрати або піксель (xi + 1, yi) тобто mH, або піксель (xi + 1, yi (1), тобто mD. Для цього спочатку розглянемо випадок 1 іперевіримо різниця квадратів відстаней від окружності до пікселів вгоризонтальному і діагональному напрямках:
При (<0 відстань від кола до діагонального піксела
(mD) більше, ніж до горизонтального (mH). Навпаки, якщо (> 0, відстаньдо горизонтального піксела (mH) більше. Таким чином, при (<0 вибираємо mH (xi + 1, уi) при (> 0 вибираємо mD (xi + 1, уi - 1)
При (= 0, коли відстані від окружності до обох пікселів однакові,вибираємо горизонтальний крок.
Кількість обчислень, необхідних для оцінки величини (, можнаскоротити, якщо зауважити, що у випадку 1
так як діагональний піксель (xi + 1, уi - 1) завжди лежить всерединікола, а горизонтальний (xi + 1, уi) - поза нею. Таким чином, (можна обчислити за формулою
Доповнення до повного квадрата члена (yi) 2 за допомогою додавання івіднімання - 2уi + 1 дає
У квадратних дужках стоїть за визначенням (i, і його підстановка
(= 2 ((i + yi) - 1
істотно спрощує вираз.
Розглянемо випадок 2 на ріс.2.6 і зауважимо, що тут повинен бути вибранийгоризонтальний піксель (xi + 1, уi), так як у є монотонноубутної функцією. Перевірка компонент (показує, що
оскільки в разі 2 горизонтальний (xi + 1, уi) і діагональний (xi + 1,уi - 1) пікселі лежать в колі. Отже, (<0, і привикористанні того ж самого критерію, що й у випадку 1, вибирається піксель
(Xi + 1, уi).
Якщо (i> 0, то діагональна точка (xi + 1, уi - 1) знаходиться позакола, тобто це випадки З та 4 на ріс.2.6. У даній ситуації зрозуміло, щоповинен бути вибраний або піксель (xi + 1, уi - 1), тобто mD, або (xi, уi
- 1), тобто mV. Аналогічно розбору попереднього випадку критерій виборуможна отримати, розглядаючи спочатку випадок З і перевіряючи різниця міжквадратами відстаней від окружності до діагонального mD і вертикального mVпікселів, тобто
При (<0 відстань від кола до вертикального піксела (xi, уi -
1) більше і слід вибрати діагональний крок mD, до пикселя (xi + 1, уi -
1). Навпаки, у випадку (> 0 відстань від кола до діагональногопікселі більше і слід вибрати вертикальний рух до пикселя (xi, уi -
1). Таким чином,
при ((0 вибираємо mD в (xi + 1, уi - 1) при (<0 вибираємо mV в (xi, уi - 1)
Тут у разі (= 0, тобто коли відстані рівні, обраний діагональнийкрок.
Перевірка компонент (показує, що
оскільки для випадку З діагональний піксель (xi + 1, уi - 1) знаходиться позакола, тоді як вертикальний піксель (xi, уi - 1) лежить всередині її.
Це дозволяє записати (у вигляді
Доповнення до повного квадрата члена (xi) 2 за допомогою додавання івіднімання 2xi + 1 дає
Використання визначення (i призводить вираз до виду
Тепер, розглядаючи випадок 4, знову зауважимо, що слід вибративертикальний піксель (xi, уi - 1), так як y є монотонно спадноїфункцією при зростанні x. перевірка компонент (для випадку 4 показує,що
оскільки обидва піксела знаходяться за колом. Отже, (> 0 і привикористанні критерію, розробленого для випадку 3, відбувається вірнийвибір mV.
Залишилось перевірити тільки випадок 5 на ріс.2.7, який зустрічається,коли діагональний піксель (xi + 1, уi - 1) лежить на колі, тобто (i
= 0. Перевірка компонент (показує, що
Отже, (> 0 і вибирається діагональний піксель (xi + 1, уi - 1).
Аналогічним чином оцінюємо компоненти (:
і (<0, що є умовою вибору правильного діагонального кроки до (хi
+ 1, уi - 1). Таким чином, випадок (i = 0 підпорядковується тому ж критерію,що й випадок (i <0 або (i> 0.
Підіб'ємо підсумок отриманих результатів:
(i <0
((0 вибираємо піксель (хi + 1, уi) (mH
(> 0 вибираємо піксель (хi + 1, уi - 1) (mD
(i> 0
((0 вибираємо піксель (хi + 1, уi - 1) (mD
(> 0 вибираємо піксель (хi, уi - 1) (mV
(i = 0 вибираємо піксель (хi + 1, уi - 1) (mD
Легко розробити прості рекурентні співвідношення дня реалізаціїпокрокового алгоритму. Спочатку розглянемо горизонтальний крок mH до пикселя (хi + 1, уi). Позначимо це нове положення піксела як (i + 1). Тодікоординати нового пікселя і значення (i рівні
Аналогічно координати нового пікселя і значення (i для кроку mD до пикселя (хi + 1, уi - 1) такі:
Те ж саме для кроку mV к (хi, уi - 1)
Реалізація алгоритму Брезенхема для окружності приводиться нижче.
Покроковий алгоритм Брезенхема для створення кола в першій квадранті
всі змінні ціліxi = 0yi = R
(i = 2 (1 - R)
Межа = 0
1. Plot (xi, yi)if yi (Межа then 4виділення випадку 1 або 2, 4 або 5, або 3if (i <0 then 2if (i> 0 then 3if (i = 0 then 20визначення випадку 1 або 2
2. (= 2 (i + 2yi - 1if ((0 then 10if (> 0 then 20визначення випадку 4 або 5
3. (= 2 (i + 2xi - 1if ((0 then 20if (> 0 then30 виконання кроківкрок mH
10. xi = xi 1
(i = (i 2 xi + 1 goto 1крок mD
20. xi = xi +1yi = yi - 1
(i = (i +2 xi - 2yi + 2 goto 1 крок mV
30 yi = yi - 1
(i = (i - 2xi + 1 goto 1
4 finish
5. Растрова розгортка суцільних областей
До цих пір мова йшла про подання на растровому графічному пристроївідрізків прямих ліній. Проте однією з унікальних характеристик такогопристрою є можливість представлення суцільних областей. Генераціюсуцільних областей з простих описів ребер або вершин будемо називатирастрової розгорткою суцільних областей, заповненням багатокутників абозаповненням контурів. Для цього можна використовувати різні способи,які зазвичай поділяються на дві широкі категорії: растрова развертка іпочатковий заповнення.
У методах растрової розгортки намагаються визначити в порядкусканування рядків, чи лежить точка всередині багатокутника або контуру. Ціалгоритми зазвичай йду від «верху» багатокутника або контуру до «низу».
У методах початковий заповнення передбачається, що відомадеяка точка (запал) всередині замкнутого контуру. В алгоритмах шукаютьточки, сусідні з початковий і розташовані всередині контура. Якщо сусідняточка розташована не всередині, значить, виявлена межа контуру. Якщо жточка опинилася всередині контуру, то вона стає новою точкою початковийі пошук триває рекурсивно.
6. Растрова розгортка багатокутників
Можна розробити ефективний метод растрової розгорткибагатокутників, якщо скористатися тим фактом, що сусідні пікселі,ймовірно, мають однакові характеристики (крім пікселів граничних ребер).
Ця властивість називається просторової когерентністю.
Характеристики пікселів на цьому рядку змінюються тільки там, деребро многокутника перетинає рядок. Ці перетину ділять скануєрядок на області.
Для простого многокутника на рис. 2.7 рядок 2 перетинаєбагатокутник при x = 1 і x = 8.
Отримуємо три області:
x <1 поза багатокутника
1 (x (8 всередині багатокутника x> 8 поза багатокутника
Рядок 4 ділиться на п'ять областей: x <1 поза багатокутника
1 (x (4 всередині багатокутника
4 8 поза багатокутника Зовсім необов'язково, щоб точки перетину для рядка 4 відразувизначалися у фіксованому порядку (зліва направо). Наприклад, якщобагатокутник задається списком вершин P1, P2, P3, P4, а список ребер (послідовними парами вершин P1P2, P2P3, P3P4, P4P5, P5P1, то для рядка
4 будуть знайдені наступні точки перетину з ребрами багатокутника: 8, 6,
4, 1. Ці точки треба відсортувати у зростаючому порядку по x, тобтоотримати 1,4, 6, 8.
При визначенні інтенсивності, кольори і відтінки пікселів на скануючоїрядку розглядаються пари відсортованих точок перетинів. Для кожногоінтервалу, що задається парою перетинів, використовується інтенсивність абоколір заповнюваного багатокутника. Для інтервалів між парами перетинів ікрайніх (від початку рядка до першого точки перетину і від останньої крапкиперетину до кінця рядка) використовується фонова інтенсивність або колір.
Точне визначення тих пікселів, які повинні активуватися,вимагає деякої обережності. Розглянемо простий прямокутник,зображений на рис. 2.8. Прямокутник має координати (1,1), (5,1),
(5,4), (1,4). Скануючі рядки з 1 по 4 мають перетину з ребрамибагатокутника при x = 1 і 5. Пікселів адресується координатами свого лівогонижнього кута, значить, для кожної з цих скануючих строк будутьактивовані пікселі з x-координатами 1, 2, 3, 4 і 5. На рис. 2.8 показанийрезультат. Зауважимо, що площа, що покривається активованими пікселами,дорівнює 20, у той час як справжня площа прямокутника дорівнює 12.
Модифікація системи координат скануючої рядки і тесту активаціїусуває цю проблему, як це показано на рис. 2.8, b. Вважається, щоскануючі рядка проходять через центр рядків пікселів, тобто черезсередину інтервалу, як це показано на рис. 2.8, b. Тест активаціїмодифікується наступним чином: перевіряється, чи лежить всередині інтервалуцентр піксела, розташованого праворуч від перетину. Однак пікселі все щеадресуються координатами лівого нижнього кута. Як показано на ріс.2.8, b,результат даного методу коректний.
Горизонтальні ребра не можуть перетинати сканує рядок і, такимчином, ігноруються. Це зовсім не означає, що їх немає на малюнку. Ціребра формуються верхній і нижній рядками пікселів.
Додаткова складність виникає при перетині скануючої рядки ібагатокутника точно за вершині, як це показано на рис. 2.9. Привикористанні угоди про середину інтервалу між рядками скануючимиотримуємо, що рядок у = 3.5 перетне багатокутник в 2, 2 і 8, тобтовийде непарну кількість перетинів. Отже, розбивкапікселів на пари дасть невірний результат, тобто пікселі (0,3), (1,3) і від
(3,3) до (7,3) будуть фоновими, а пікселі (2,3), (8,3), (9,3) забарвляться вколір багатокутника. Якщо враховувати тільки одну точку перетину звершиною. Тоді для рядки у = 3.5 отримаємо правильний результат. Однакрезультат застосування методу до рядку у = 1.5, що має дві перетину в
(5,1), показує, що метод невірний. Для цього рядка саме розбивка напари дасть вірний результат, тобто буде пофарбований тільки піксель (5,1). Якщож враховувати у вершині тільки одне перетинання, то пікселі від (0,1) до
(4,1) будуть фоновими, а пікселі від (5,1) до (9,1) будуть пофарбовані в колірбагатокутника.
Правильний результат можна отримати, враховуючи точку перетину ввершині два різу, якщо вона є точкою локального мінімуму абомаксимуму і з огляду на один раз в іншому випадку. Визначити локальниймаксимум чи мінімум багатокутника в розглянутій вершині можна здопомогою перевірки кінцевих точок двох ребер. Якщо у обох ребер у більше,ніж у вершини, значить, вершина є точкою локального мінімуму. Якщоменше, значить, вершина - точка локального максимуму. Якщо один більше, аінша менше, отже, вершина не є ні точкою локальногомінімуму, ні точкою локального максимуму. На ріс.2.10 точка Р1 - локальниймінімум, Р3 - локальний максимум, а Р2, Р4 - ні те ні інше.
Отже, в точках Р1 та Р3 враховуються два перетину з скануючимирядками, а в Р2 і Р4 - одне.
7. Алгоритм з впорядкованим списком ребер
Використовуючи описані вище методи, можна розробити ефективніалгоритми растрової розгортки суцільних областей, які називаються алгоритмами звпорядкованим списком ребер. Ефективність цих алгоритмів залежить відефективності сортування. Наведемо дуже простий алгоритм.
Алгоритм з впорядкованим списком ребер, що використовує список активних ребер.
Підготувати дані:
Використовуючи скануючі рядки, проведені через середини відрізків, т . тобто через у + Ѕ визначити для кожного ребра багатокутника найвищу сканує рядок, перерізану ребром.
Занести ребро многокутника в у-групу, що відповідає цієї скануючої рядку.
Зберегти в зв'язкового списку значення: початкове значення координат x точок перетину, (y - число скануючих строк, що перетинаються ребром багатокутника, і ~ (x - крок збільшення по x при переході від однієї скануючої рядка до іншого.
Перетворити ці дані в растрову форму:
Для кожної скануючої рядка перевірити відповідну у-групу на наявність нових ребер. Нові ребра додати до списку активних ребер.
Відсортувати координати x точок перетину з САР в порядку зростання; т . тобто х1 передує x2, якщо х1 <х2
Виділити пари точок перетинів з відсортовані за x списку. Активувати на скануючої рядку y пікселі для цілих значень x, таких, що x1 (x + Ѕ (x2. Для кожного ребра з САР зменшити (у на 1. Якщо (у <0, то виключити дане ребро з САР.
Обчислити нове значення координат x точок перетину xнов = xстар +
( x
Перейти до наступної скануючої рядку
В алгоритмі передбачається, що всі дані попередньо перетворенідо подання, прийняте для багатокутників.
8. Алгоритм заповнення по ребрах
Алгоритм, що використовує список ребер і прапор, є двох кроковим.
Перший крок полягає у змалюванні контура, в результаті чого на кожнійскануючої рядку утворюються пари обмежують пікселів. Другий крокполягає в заповненні пікселів, розташованих між обмежують. Більшеточно алгоритм можна сформулювати у наступному вигляді:
Алгоритм зі списком ребер і прапором
Змалювання контуру:
Використовуючи угоди про середину інтервалу між скануючими рядками для кожного ребра, перетинає сканує рядок, відзначити самий лівий піксель, центр якого лежить праворуч від перетину; тобто x + 1/2> xпересеченія
Заповнення:
Для кожної скануючої рядки, що перетинає багатокутник
Всередині = FALSE for x = 0 (ліва кордон) to x = xmax, (права кордон) if піксель в точці x має граничне значення then Інвертувати значення змінної Всередині if Всередині = TRUE then привласнити пикселя в x значення кольору багатокутника else привласнити пикселя в x значення кольору фону end if next x
В даному алгоритмі кожен піксель обробляється тільки один раз, такщо витрати на ввід/вивід значно менше, ніж в алгоритмі зі спискомребер, внаслідок чого, за його апаратної реалізації, він працює наодин-два порядки швидше ніж алгоритм з впорядкованим списком ребер.
9. Алгоритми заповнення з затравкою
У обговорювалися вище алгоритми заповнення відбувається в порядкусканування. Інший підхід використовується в алгоритмах заповнення з затравкою.
У них передбачається, що відомий хоча б один піксель з внутрішньоїобласті багатокутника. Алгоритм намагається знайти і пофарбувати всі іншіпікселі, що належать внутрішній області. Області можуть бути абовнутрішні, або гранично-визначені. Якщо область відноситься до внутрішньо
- Певним, то всі пікселі, що належать внутрішньої частини, мають одині той же колір або інтенсивність, а всі пікселі, зовнішні по відношенню дообласті, мають інший колір. Це продемонстровано на рис. 2.10. Якщообласть відноситься до гранично-визначеним, то всі пікселі на кордоніобласті мають вибраного значення або колір, як це показано на рис. 2.11.
Алгоритми, що заповнюють внутрішньо - певні області, називаютьсявнутрішньо - заповнюють, а алгоритми для гранично-певних областей --гранично-заповнюють. Далі будуть обговорюватися гранично-заповнюютьалгоритми, однак відповідні внутрішньо заповнюють алгоритми можнаотримати аналогічним чином.
Внутрішньо-або гранично-певні області можуть бути 4 - або 8 --зв'язними. Якщо область 4-зв'язкова, то будь-який піксель в області можна досягти задопомогою комбінацій рухів тільки в 4-х напрямках: ліворуч, праворуч,вгору, вниз. Для 8-і зв'язковий області додаються ще й діагональнінапряму. Алгоритм заповнення 8-зв'язковий області заповнить і 4-зв'язний, алезворотне не вірно. Однак у ситуації, коли потрібно заповнити різнимиквітами два окремі 4-зв'язківці області, використання 8-зв'язкового алгоритмудасть не вірний результат. Далі мова піде про алгоритми для 4-зв'язковихобластей, проте їх легко адаптувати і для 8-зв'язкових.
10. Порядковий алгоритм заповнення з затравкою
Використовуючи стек, можна розробити алгоритм заповнення гранично -певній галузі. Стек - це просто масив або інша структура даних,в яку можна послідовно поміщати значення і з якої їх можнапослідовно витягувати. Як показує практика, стек може бутидосить великим. Часто в ньому міститься дублююча інформація. Упорядковому алгоритмі заповнення з затравкою стек мінімізується за рахунокзберігання тільки початковий пікселя для будь-якого безперервного інтервалу наскануючої рядку. Безперервний інтервал - це група примикають один додругу пікселів (обмежена вже заповненими або граничними пікселами). Мидля розробки алгоритму використовуємо евристичний підхід, проте такожможливий і теоретичний підхід, заснований на теорії графів.
Даний алгоритм застосуємо гранично-певним 4-зв'язковим областям,які можуть бути як опуклими, так і не опуклими, а також можутьмістити діри. В області, зовнішньої і що примикає до нашої, не повинно бутипікселів з кольором, яким область або багатокутник заповняться. Схематичнороботу алгоритму можна розбити на чотири етапи.
порядковий алгоритм заповнення з затравкою
початковий піксель на інтервалі витягується з стека, що містить початковий пікселі.
Інтервал з початковий пікселів заповнюється ліворуч і праворуч від затравки уздовж скануючої рядки до тих пір, поки не буде знайдена кордон.
У змінної Xлев і Xправ запам'ятовуються крайній лівий і правий крайній пікселі інтервалу
У діапазоні Xлев (x (Xправ перевіряються рядки розташовані безпосередньо над в під поточної рядком. Визначається, чи є на них ще не заповнені пікселі. Якщо такі пікселі є (тобто не всі пікселі граничні, або вже заповнені), то в зазначеному діапазоні крайній правий піксель кожному інтервалі відзначається як початковий і поміщається в стек.
При ініціалізації алгоритму в стек збожеволіє єдиний початковийпіксель, робота завершується при спустошення стека. Нижче наводиться більшдокладний опис алгоритму на псевдокоді.
порядковий алгоритм заповнення з затравкою
запал (x, y) видає початковий піксель
Pop - процедура, яка витягує піксель з стека
Push - процедура, яка поміщає піксель в стек
ініціюємо стек
Push запал (x, y)
While (стек не порожній)
Витягуємо піксель з стека і надаємо йому нове значення Pop
Пікселів (x, y)
Пікселів (x, y) = Нов_значеніе зберігаємо x-координату початковий піксела
Врем_х = x заповнюємо інтервал праворуч від затравки x = x +1 while Пікселів ( x, y) (Гран_значеніе
Пікселів (x, y) = Нов_значеніе x = x +1 end while зберігаємо крайній праворуч піксель
Xправ = x (1 відновлюємо x-координату затравки x = Врем_х заповнюємо інтервал ліворуч від затравки x = x (1 while Пікселів (x, y) (Гран_значеніе
Пікселів (x, y) = Нов_значеніе x = x (1 end while зберігаємо крайній ліворуч піксель
Xлев = x +1 відновлюємо x-координату затравки x = Врем_х перевіримо, що рядок вище не є ні кордоном багатокутника, ні вже повністю заповненої; якщо це не так, то знайти затравки, починаючи з лівого краю подінтервала скануючої рядки x = Xлев y = y +1 while x (Xправ шукаємо затравки на рядок вище
Прапор = 0 while (Пікселів (x, y) (Гран_значеніе and
Пікселів (x, y) (Нов_значеніе and x Push Пікселів (x, y) else
Push Пікселів (x (1, y) end if
Прапор = 0 end if продовжимо перевірку, якщо інтервал був перерваний
Xвход = x while ((Пікселів (x, y) = Гран_значеніе or
Пікселів (x, y) = Нов_значеніе) and x Ця частина алгоритму абсолютно аналогічна перевірки для рядки вище, за винятком, того що замість y = y + 1 треба підставити y = y (1end whilefinish
3. Видалення невидимих ліній і поверхонь
Завдання видалення невидимих ліній і поверхонь є однією знайбільш складних у машинній графіці. Алгоритми видалення невидимих ліній іповерхонь служать для визначення ліній ребер, поверхонь або обсягів,які видимі або невидимі для спостерігача, що знаходиться в заданій точціпростору.
Необхідність видалення невидимих ліній, ребер, поверхонь або обсягівпроілюстрована мал.3.1. На ріс.4.1, а наведений типовий каркасний кресленнякуба. Його можна інтерпретувати двояко: як вид куба зверху, ліворуч абознизу, справа. Видалення тих ліній або поверхонь, які невидимі звідповідної точки зору, дозволяють позбутися неоднозначності.
Результати показані на ріс.4.1, b і c.
Складність завдання видалення невидимих ліній і поверхонь призвела допояви великого числа, різних способів її рішення. Багато хто з нихорієнтовані на спеціалізовані програми. Найкращого вирішення загальноїзавдання видалення невидимих ліній і поверхонь не існує. Длямоделювання процесів в реальному часі, наприклад, для авіа тренажерів,необхідні швидкі алгоритми, які можуть породжувати результати з частотоювідео генерації (30 кадр/с). Для машинної мультиплікації потрібніалгоритми, які можуть генерувати складні реалістичні зображення, вяких представлені тіні, прозорість і фактура, що враховують ефективідбиття і заломлення кольору в найдрібніших відтінках. Подібні алгоритмипрацюють повільно, і зачас?? ую на обчислення потрібно декілька хвилин абонавіть годин. Строго кажучи, облік ефектів прозорості, фактури, відображення іт. п. не входить у завдання видалення невидимих ліній або поверхонь.
Природніше вважати їх частиною процесу візуалізації зображення. Процесвізуалізації є інтерпретацією або поданням зображення абосцени в реалістичній манері. Однак багато хто з цих ефектів вбудовані валгоритми видалення невидимих поверхонь і тому будуть зачеплені.
Існує тісний взаємозв'язок між швидкістю роботи алгоритму ідетальністю його результату. Ні один з алгоритмів не може досягтихороших оцінок для цих двох показників одночасно. У міру створення всебільш швидких алгоритмів можна будувати все більш детальні зображення.
Реальні завдання, однак, завжди будуть вимагати обліку ще більшогокількості деталей.
Алгоритми видалення невидимих ліній або поверхонь можнакласифікувати за способом вибору системи координат або простору, вякому вони працюють. Алгоритми, що працюють в об'єктних просторі, маютьсправу з фізичною системою координат, у якій описані ці об'єкти. Прицьому виходять досить точні результати, обмежені, взагалі кажучи, лишеточністю обчислень. Отримані зображення можна вільно збільшувати підбагато разів. Алгоритми, що працюють в об'єктних просторі, особливо кориснів тих додатках, де необхідна висока точність. Алгоритми ж,що працюють в просторі зображення, мають справу з системою координат тогоекрана, на якому об'єкти візуалізуються. При цьому точність обчисленьобмежена роздільною здатністю екрану. Результати, отримані впросторі зображення, а потім збільшені у багато разів, не будутьвідповідати вихідної сцені. Алгоритми, що формують список пріоритетівпрацюють поперемінно в обох згаданих системах координат.
Обсяг обчислень для будь-якого алгоритму, що працює в об'єктнихпросторі, і порівнювати кожен об'єкт сцени з усіма іншимиоб'єктами цієї сцени, теоретично зростає як квадрат числа об'єктів (n2
). Аналогічно, обсяг обчислень будь-якого алгоритму, що працює впросторі зображення і порівнює кожен об'єкт сцени з позиціямивсіх пікселів в системі координат екрана, росте теоретично, як nN.
Тут n позначає кількість об'єктів (тел, площин або ребер) у сцені,а N - кількість пікселів. Теоретично трудомісткість алгоритмів, работаюoіх воб'єктному просторі, менше трудомісткості алгоритмів, що працюють впросторі зображення, при n Далі дається виклад деяких алгоритмів, що працюють як в об'єктнихпросторі, так і в просторі зображення. Кожен з них іллю
