Тривимірна комп'ютерна графіка

Кемеровський Державний Університет кафедра математичного анализа.

Курсова робота з теме:

Тривимірна комп’ютерна графика.

Виконав: студент М-963.

Печёркин Ю. К.

Керівник: Кім У. Б.

Кемерово 1999.

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

Сьогодні створено дуже багато програм, дозволяють створювати й редагувати тривимірні сцени, і об'єкти. Серед найбільш популярних можна назвати як 3D studio Max, що дозволяє тривимірні комп’ютерні ролики. Область її застосування переважно реклама, мультиплікація й телевізійних передач. Інший щонайменше популярний пакет програм це Auto-CAD. Він застосовується у основному інженерами і проектувальниками до створення креслень і просторових моделей. Крім цих існує інших спеціалізованих програмних пакетів які охоплюють усі сторони людської жизни.

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

1. Введення ЄІАС у машинну графику.

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

Машинна графіка — складна й різноманітна дисципліна. Для вивчення її, передусім, необхідно розбити на доступні для огляду частини. Насамперед необхідно розглянути методи лікування й алгоритми растрової графіки. Це досить простий, але дуже не важливий розділ машинної графіки. У розділі розглядаються алгоритми малювання відрізків і окружностей на екрані монітора, методи растрової развёртки, заповнення многоугольников, усунення ступенчатости чи сходового ефекту. Окремо слід розглянути методи відсікання зображення, тобто. відбору інформації, що необхідно для візуалізації конкретної сцены.

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

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

2. Растрова графика.

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

1. Алгоритми креслення отрезков.

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

Є кілька алгоритмів виконують це завдання. Розглянемо два з них.

2. Цифровим диференціальний анализатор

Одне з методів розкладання відрізка в растр полягає у рішенні диференціального рівняння, описывающего той процес. Для прямий лінії имеем:

[pic] чи [pic]н Рішення представляється в виде.

[pic] де x1, y1 і x2, y2 — кінці разлагаемого відрізка і yi — початкова значення чергового кроку вздовж відрізка. Фактично рівняння (2.1.) представляє собою рекуррентное співвідношення для послідовних значень y вздовж потрібного відрізка. Цей метод, використовуваний для розкладання в растр відрізків, називається цифровим диференційним аналізатором (ЦДА). У простому ЦДА або [pic], або [pic] (більше з збільшень) вибирається як одиниця растра. Нижче наводиться простий алгоритм, працюючий переважають у всіх квадрантах:

Процедура розкладання в растр відрізка методом цифрового диференціального аналізатора (ЦДА) предполагается, що кінці відрізка (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) початок основного циклу і =1 while (і (Довжина).

Plot (Integer (x), Integer (y)) x = x + (x y = y + (y і = і + 1 end while finish.

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

3. Алгоритм Брезенхема.

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

Алгоритм побудований отже потрібно перевіряти лише знак цієї помилки. На рис. 2.1 це ілюструється для відрізка в первом.

Ѕ ((y (1 (помилка (0).

0 ((y/(x < Ѕ (помилка (x then.

Брешемо = (x.

(x = (y.

(y = Врем.

Обмін = 1 else.

Обмін = 0 end if ініціалізація [pic] що з поправкою наполовину пиксела [pic] = 2 * (y ((x основний цикл for і = 1 to (x.

Plot (x, y).

While ([pic] (0).

If Обмін = 1 then x = x + s1 else y = y + s2 end if.

[pic] = [pic] (2 * (x end while if Обмін = 1 then y = y + s2 else x = x + s1 end if.

[pic] = [pic] + 2 * (y next і finish.

Цей алгоритм задовольняє найсуворішим вимогам. Вона має прийнятну швидкість і то, можливо легко реалізований на апаратній чи микропрограммном уровне.

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 равна.

[pic].

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

При (< 0 діагональна точка (xi + 1, yi (1) перебуває всередині реальної окружності, т. е. це випадки 1 чи 2 на рис. 2.6. Зрозуміло, що у цій ситуації слід вибрати або піксел (xi + 1, yi) т. е. mH, або піксел (xi + 1, yi (1), т. е. mD. І тому спочатку розглянемо випадок 1 і перевіримо різницю квадратів відстаней від окружності до пікселів в горизонтальному і диагональном направлениях:

[pic].

При (< 0 відстань від окружності до діагонального пиксела (mD) більше, як на горизонтального (mH). Навпаки, якщо (> 0, відстань до горизонтального пиксела (mH) більше. Отже, при (< 0 вибираємо mH (xi + 1, уi) при (> 0 вибираємо mD (xi + 1, уi — 1).

При (= 0, коли відстані від окружності до обох пікселів однакові, вибираємо горизонтальний шаг.

Кількість обчислень, необхідні оцінки величини (, можна скоротити, якщо помітити, у разі 1.

[pic] оскільки діагональний піксел (xi + 1, уi — 1) завжди лежить всередині окружності, а горизонтальний (xi + 1, уi) — за її межами. Отже, (можна визначити по формуле.

[pic].

Доповнення до квадрата члена (yi)2 з допомогою додавання і вирахування — 2уi + 1 дает.

[pic] У квадратних дужках стоїть з визначення (і, та її подстановка.

(= 2((i + yi) — 1.

существенно спрощує выражение.

Розглянемо випадок 2 на рис. 2.6 зауважимо, що саме може бути обраний горизонтальний піксел (xi + 1, уi), тому що в є монотонно убутній функцією. Перевірка компонент (показує, что.

[pic] оскільки у разі 2 горизонтальний (xi + 1, уi) і діагональний (xi + 1, уi — 1) пикселы лежать всередині окружності. Отже, (< 0, і за використанні того самого критерію, що у разі 1, вибирається піксел (xi + 1, уi).

Якщо (і > 0, то діагональна точка (xi + 1, уi — 1) перебуває поза окружності, т. е. це випадки З і 4 на рис. 2.6. У такій ситуації ясно, що може бути обраний або піксел (xi + 1, уi — 1), т. е. mD, або (xi, уi — 1), т. е. mV. Аналогічно розбору попереднього випадку критерій вибору можна отримати роботу, розглядаючи спочатку випадок З і перевіряючи різницю між квадратами відстаней від окружності до діагонального mD і вертикального mV пікселів, т. е.

[pic].

При (< 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, т. е. коли відстані рівні, обраний діагональний шаг.

Перевірка компонент (показує, что.

[pic] бо випадку З діагональний піксел (xi + 1, уi — 1) перебуває поза окружності, тоді як вертикальний піксел (xi, уi — 1) лежить всередині її. Це дозволяє записати (в виде.

[pic] Доповнення до квадрата члена (xi)2 з допомогою додавання і вирахування 2xi + 1 дает.

[pic].

Використання визначення (і наводить вираз до виду.

[pic].

Тепер, розглядаючи випадок 4, знову зауважимо, що можна вибрати вертикальний піксел (xi, уi — 1), оскільки y є монотонно убутній функцією за умов зростання x. перевірка компонент (для випадку 4 показує, что.

[pic] оскільки обидва пиксела виходять за межі окружності. Отже, (> 0 і за використанні критерію, розробленого для випадку 3, відбувається вірний вибір mV.

Залишилося перевірити лише випадок 5 на рис. 2.7, який зустрічається, коли діагональний піксел (xi + 1, уi — 1) лежить окружності, т. е. (і = 0. Перевірка компонент (показує, что.

[pic] Отже, (> 0 і вибирається діагональний піксел (xi + 1, уi — 1). Так оцінюємо компоненти (:

[pic] і (< 0, яке є умовою вибору правильного діагонального кроку до (хi + 1, уi — 1). Отже, випадок (і = 0 підпорядковується до того ж критерію, як і випадок (і < 0 чи (і > 0.

Підіб'ємо підсумок отриманих результатів: (і < 0 ((0 вибираємо піксел (хi + 1, уi) (mH (> 0 вибираємо піксел (хi + 1, уi — 1) (mD (і > 0 ((0 вибираємо піксел (хi + 1, уi — 1) (mD (> 0 вибираємо піксел (хi, уi — 1) (mV (і = 0 вибираємо піксел (хi + 1, уi — 1) (mD.

Легко розробити прості рекуррентные співвідношення дня реалізації покрокового алгоритму. Спочатку розглянемо горизонтальний крок mH до пикселу (хi + 1, уi). Означимо це нове становище пиксела як (і + 1). Тоді координати нового пиксела і значення (і равны.

[pic] Аналогічно координати нового пиксела і значення (і для кроку mD до пикселу (хi + 1, уi — 1) таковы:

[pic] Це ж для кроку mV до (хi, уi — 1).

[pic] Реалізація алгоритму Брезенхема для окружності наводитися ниже.

Пошаговый алгоритм Брезенхема для генерації окружності у першому квадранте все перемінні цілі xi = 0 yi = R (і = 2(1 — R) Межа = 0 1. Plot (xi, yi) if yi (Межа then 4 виділення випадку 1 чи 2, 4 чи 5, чи 3 if (і < 0 then 2 if (і > 0 then 3 if (і = 0 then 20 визначення випадку 1 чи 2 2. (= 2(i + 2yi — 1 if ((0 then 10 if (> 0 then 20 визначення випадку 4 чи 5 3. (= 2(i + 2xi — 1 if ((0 then 20 if (> 0 then 30 виконання кроків крок mH 10. xi = xi +1.

(і = (і +2xi + 1 goto 1 крок mD 20. xi = xi +1 yi = yi — 1.

(і = (і +2xi — 2yi + 2 goto 1 крок mV 30 yi = yi — 1.

(і = (і - 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 < x < б поза багатокутника б (x (8 всередині багатокутника x > 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). Скануючі рядки із першого по 4 мають перетину з ребрами багатокутника при x = 1 і п’яти. Піксел адресується координатами свого лівого нижнього кута, отже, кожної з цих скануючих рядків будуть активовані пикселы з x-координатами 1, 2, 3, 4 і п’яти. На рис. 2.8 показаний результат. Зауважимо, що загальна площа, покрываемая активированными пикселами, дорівнює 20, тоді як справжня площа прямокутника дорівнює 12.

Модифікація системи координат що сканує рядки — і тесту активації усуває цієї проблеми, як і показано на рис. 2.8,b. Вважається, що скануючі рядки проходять через центр рядків пікселів, т. е. через середину інтервалу, як і показано на рис. 2.8,b. Тест активації модифікується так: перевіряється, лежить чи всередині інтервалу центр пиксела, розташованого праворуч від перетину. Проте пикселы досі адресуються координатами лівого нижнього кута. Як зазначено на рис. 2.8,b, результат цього методу корректен.

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

Додаткова труднощі виникає після перетину що сканує рядки — і багатокутника точно по вершині, як і показано на рис. 2.9. При використанні домовленості про середині інтервалу між сканирующими рядками отримуємо, що рядок у = 3.5 перетне багатокутник у два, 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 + ½ > 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 < Xправ) if Прапор = 0 then Прапор = 1 x = x + 1 end while поміщаємо в стік крайній справа піксел if Прапор =1 then if (x = Xправ and Піксел (x, y) (Гран_значение and Піксел (x, y) (Нов_значение) then.

Push Піксел (x, y) else.

Push Піксел (x (1, y) end if.

Прапор = 0 end if продовжимо перевірку, якщо інтервал був прерван.

Xвход = x while ((Піксел (x, y) = Гран_значение or.

Піксел (x, y) = Нов_значение) and x < Xправ) x = x + 1 end while упевнимося що координата пиксела збільшена if x = Xвход then x = x + 1 end while перевіримо, що рядок нижче ні кордоном багатокутника, ні повністю заполненной.

Ця частина алгоритму цілком аналогічна перевірці для рядки вище, крім, те, що замість y = y + 1 треба підставити y = y (1 end while finish.

3. Видалення невидимих ліній і поверхностей.

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

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

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

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

Обсяг обчислень нічого для будь-якого алгоритму, працював у об'єктному просторі, і який би порівняв кожен об'єкт сцени із іншими об'єктами цієї сцени, зростає теоретично як квадрат числа об'єктів (n2). Аналогічно, обсяг обчислень будь-якого алгоритму, працював у просторі зображення який би порівняв кожен об'єкт сцени з позиціями всіх пікселів у системі координат екрана, зростає теоретично, як nN. Тут n позначає кількість об'єктів (тіл, площин чи ребер) в сцені, а N — число пікселів. Теоретично трудомісткість алгоритмів, работаюoих в об'єктному просторі, менше трудомісткості алгоритмів, що працюють у просторі зображення, при n < N. Оскільки N зазвичай одно (512)2, то теоретично більшість алгоритмів слід реалізовувати в об'єктному просторі. Проте за це негаразд. Річ у тім, що алгоритми, працюють у просторі зображення, ефективніші бо них легше скористатися перевагою когерентності при растрової реализации.

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

1. Алгоритм плаваючого горизонта.

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

F (x, у, z) = 0 Такі функції виникають у багатьох додатках у математиці, техніці, природних науках та інших дисциплинах.

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

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

Отже, поверхню тепер складається з послідовності кривих, що у кожної з цих площин, як показано на рис. 3.3. Тут передбачається, що отримане криві є однозначними функціями незалежних змінних. Якщо спроектувати отримані криві на площину z = 0, одразу стає зрозуміла ідея алгоритму видалення невидимих ділянок вихідної поверхні. Алгоритм спочатку впорядковує плоскости.

z = const зі збільшення відстані перед тим від точки спостереження. Потім для кожної площині, починаючи із найближчого до точки спостереження, будується крива, що у ньому. Алгоритм видалення невидимою лінії залежить від следующем:

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

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

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

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

Полученный результат показаний на рис. 3.4, b.

У викладеним алгоритмі передбачається, що значення функції, т. е. y, відомо кожному за значення x у просторі зображення. Але якщо кожному за значення x не можна вказати (обчислити) відповідне йому значення у, то неможливо підтримувати масиви верхнього й нижнього плаваючих горизонтів. У разі використовується лінійна інтерполяція значень у між відомими значеннями у тому, для заповнення масиви верхнього і нижнього плаваючих горизонтів, як показано на рис. 3.5. Якщо видимість кривою змінюється, то метод з такою простий интерполяцией дасть коректного результату. Цей ефект проілюстровано рис. 3.6,а. Припускаючи, що операція з заповнення масивів проводиться після перевірки видимості, отримуємо, що з переході поточної кривою від видимого до невидимому стану (сегмент АВ на рис. 3.6,а), точка (xn+k, yn+k) оголошується невидимою. Тоді ділянку кривою між точками (xn, yn) і (xn+k, yn+k) не змальовується і операція з заповнення масивів немає. Утворюється зазор між поточної і попередньої кривими Коли ділянці поточної кривою відбувається перехід від невидимого стану до видимому (сегмент CD на рис. 3.6,а), то точка (xm+k, ym+k) оголошується видимої, а ділянку кривою між точками (xm, ym) і (xm+k, ym+k) змальовується і операція з заповнення масивів проводиться. Тому змальовується і невидимий шматок сегмента CD. З іншого боку, масиви плаваючих горизонтів ні утримувати точних значень у. І це може викликати у себе додаткові небажані ефекти для наступних криві. Отже, потрібно вирішувати завдання про пошуку точок перетину сегментів поточної і попередньої кривых.

Є кілька методів отримання точок перетину кривих. На растрових дисплеях значення координати x можна збільшувати на 1, починаючи з xn чи xm (рис. 3.6,а). Значення у, відповідне поточному значенням координати x у просторі зображення, виходить шляхом додавання до значенням у, відповідному попередньому значенням координати x, вертикального збільшення (y вздовж заданої кривою. Потім визначається видимість нової точки з координатами (x + 1, y + (y). Якщо це точка видимою, то активується пов’язаний із нею піксел. Якщо невидима, то піксел не активується, а x поповнюється 1. Цей процес відбувається триває до того часу, доки зустрінеться xn+k чи xm+k. Перетин для растрових дисплеїв визначаються викладеним методом з достатньої точністю. Близький і навіть елегантніший метод визначення перетинань грунтується на двоичном поиске.

Точне значення точки перетину двох прямолінійних відрізків, які интерполируют поточну і попередню криві, між точками (xn, yn) і (xn+k, yn+k) (рис. 3.6) задається формулами:

[pic] где.

[pic].

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

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

Коли ділянці від попереднього (xn) до поточного (xn+k) значення x видимість кривою змінюється, то обчислюється точка перетину (xi).

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

Заповнити масиви верхнього й нижнього плаваючих горизонтов.

Викладене алгоритм призводить до деяким дефектів, коли крива, що у одній з віддаленіших від точки спостереження площин, з’являється зліва чи справа з-під безлічі кривих, що у площинах, які ближче до до зазначеної точці спостереження. Цей ефект продемонстровано на рис. 3.7, де вже оброблені площині n — 1 і n розташовані ближчі один до точці спостереження. На малюнку показано, що при обробці площині n + 1. Після опрацювання кривих n — 1 і n верхній обрій для значень x = 0 і одну дорівнює початковому значенням у; для значень x від 2 до 17 він дорівнює ординатам кривою n; а значень 18, 19, 20 — ординатам кривою n — 1. Нижній обрій для значень x = 0 і одну дорівнює початковому значенням у; для значень x = 2, 3, 4 — ординатам кривою n; а значень x від 5 до 20 — ординатам кривою n — 1. Після обробітку поточної кривою (n + 1) алгоритм оголошує її видимої при x = 4. Це показано суцільний лінією на рис. 3.7. Аналогічний ефект і його справа при x = 18. Такий ефект призводить до появі зазубрених бічних ребер. Проблема з зазубренностью бічних ребер вирішується включенням до масиви верхнього й нижнього горизонтів ординат, відповідних штриховым лініях на рис. 3.7. Це можна виконати ефективно, створивши хибні бічні ребра. Наведемо алгоритм, який реалізує цю ідею для обох ребер.

Обробка лівого бічного ребра:

Якщо Pn є першою точкою на першої кривою, то запам’ятаємо Pn як Pn (1 і закінчимо заповнення. Інакше створимо ребро, з'єднуюче Pn і Pn (1.

Занесемо в масиви верхнього й нижнього горизонтів ординати цього ребра та й запам’ятаймо Pn як Pn (1.

Обробка правого бічного ребра:

Якщо Pn є останньою точкою на першої кривою, то запам’ятаємо Pn як Pn (1 і закінчимо заповнення. Інакше створимо ребро, з'єднуюче Pn і Pn (1.

Занесемо в масиви верхнього й нижнього горизонтів ординати цього ребра та й запам’ятаймо Pn як Pn (1.

Тепер повний алгоритм виглядає так:

Для кожної площині z = const.

Обробити ліве бічне ребро.

Для кожної точки, лежачої на кривою із поточного плоскости:

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

Коли сегменті від попереднього (xn) до поточного (xn+k) значення x видимість кривою змінюється, то обчислюється те що (xi).

Коли ділянці від xn до (xn+k) сегмент кривою повністю бачимо, він змальовується повністю; коли він cтал невидимим, то змальовується його шматок від xn до xi; якщо він став видимим, то змальовується його шматок від xi до xn+k.

Заповнити масиви верхнього й нижнього плаваючих горизонтов.

Обробити праве бічне ребро.

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

На рис. 3.8 показаний типовий результат роботи алгоритму плаваючого горизонту. Запис цього алгоритму наводитися ниже.

Алгоритм плаваючого горизонта Гэкран — дозвіл екрана в горизонтальному напрямі Вэкран — дозвіл екрана в вертикальному напрямі Верх — масив, у якому координати верхнього горизонту Низ — масив, у якому координати нижнього горизонту Y — поточне значення функції y = f (x, z) при z = const Тфлаг — прапор видимості для поточної точки Пфлаг — прапор видимості для попередньої точки, равный.

0 = невидима.

1 = видимою і від верхнього горизонта.

— 1 = видимою і від нижнього горизонту Draw — графічна команда, яка креслить видиму лінію між точками, заданими їх координатами. Xmin, Xmax — мінімальна та максимальна абсциссы функції Xшаг — крок збільшення вздовж осі x Zmin, Zmax — мінімальна та максимальна аппликата функції Zшаг — крок між площинами z = const Dimension Верх (Гэкран), Низ (Гэкран) ініціалізація змінних Xлевое = (1; Yлевое = (1; Xправое = (1; Yправое = (1 ініціалізація масивів горизонтів Верх = 0 Низ = Вэкран Обчислення функції з кожної площині z = const, починаючи із найближчого до спостерігачеві площині Zmax for z = Zmax to Zmin step (Zшаг ініціалізація попередніх значень по x і y: Xпред і Yпред.

Xпред = Xmin.

Yпред = f (Xmin, z) якщо використовується видове перетворення, її потрібно застосувати к.

Xпред, Yпред, z у цій точці обробка лівого бічного ребра call Обрребра (Xпред, Yпред, Xлев, Yлев; Верх, Низ) call Видимість (Xпред, Yпред, Верх, Низ; Пфлаг) кожної крапки над кривою, що у площині z = const for x = Xmin to Xmax step Xшаг y = f (x, z) якщо використовується видове перетворення, її потрібно застосувати до цієї точці перевірка видимості поточної крапки й заповнення відповідного масиву горизонту call Видимість (x, y, Верх, Низ; Тфлаг) if Тфлаг = Пфлаг then if (Тфлаг = 1) or (Тфлаг = (1) then.

Draw (Xпред, Yпред, x, y) call Обрій (Xпред, Yпред, x, y; Верх, Низ) end if якщо видимість змінилася, то обчислюється те що і заповнюється масив горизонту else if Тфлаг = 0 then if Пфлаг = 1 then call Перетин (Xпред, Yпред, x, y, Верх; Xi, Yi) else call Перетин (Xпред, Yпред, x, y, Низ; Xi, Yi) end if.

Draw (Xпред, Yпред, Xi, Yi) сall Обрій (Xпред, Yпред, Xi, Yi, Верх, Низ) else if Тфлаг = 1 then if Пфлаг = 0 then call Перетин (Xпред, Yпред, x, y, Верх; Xi, Yi).

Draw (Xi, Yi, x, y) сall Обрій (Xi, Yi, x, y; Верх, Низ) else call Перетин (Xпред, Yпред, x, y, Низ; Xi, Yi).

Draw (Xпред, Yпред, Xi, Yi) call Обрій (Xпред, Yпред, Xi, Yi; Верх, Низ) call Перетин (Xпред, Yпред, x, y, Верх; Xi, Yi).

Draw (Xi, Yi, x, y) call Обрій (Xi, Yi, x, y; Верх, Низ) end if else if Пфлаг = 0 then call Перетин (Xпред, Yпред, x, y, Верх; Xi, Yi).

Draw (Xi, Yi, x, y) call Обрій (Xi, Yi, x, y; Верх, Низ) else call Перетин (Xпред, Yпред, x, y, Верх; Xi, Yi).

Draw (Xпред, Yпред, Xi, Yi) call Обрій (Xпред, Yпред, Xi, Yi; Верх, Низ) call Перетин (Xпред, Yпред, x, y, Низ; Xi, Yi).

Draw (Xi, Yi, x, y) call Обрій (Xi, Yi, x, y; Верх, Низ) end if end if end if end if знову форматувати Пфлаг, Xпред, Yпред.

Пфлаг = Тфлаг.

Xпред = x.

Yпред = y next x обробка правого концевого ребра call Обрребра (x, y, Xправ, Yправ; Верх, Низ) next z finish.

підпрограма обробки бічного ребра Subroutine Обрребра (x, y, Xребра, Yребра; Верх, Низ) якщо Xребра = (1, то зустрінута перша крива і ребро не створюється if Xребра = (1 then 1 call Обрій (Xребра, Yребра, x, y; Верх, Низ) 1 Xребра = x.

Yребра = y return підпрограма визначення видимості точки Subroutine Видимість (x, y, Верх, Низ; Тфлаг) видимість точки визначається стосовно верхньому і нижньому плаваючим обріям. Якщо точка лежить на жіночих самому обрії, вона вважається видимой.

Тфлаг = 0, якщо точка невидима.

= 1, якщо вона видимою і від верхнього горизонта.

= (1, якщо вона видимою і від нижнього горизонту x вважається цілої if (y < Верх (x)) and (y > Низ (x)) then Тфлаг = 0 if y (Верх (x) then Тфлаг = 1 if y (Низ (x) then Тфлаг = (1 return.

підпрограма заповнення масивів плаваючих горизонтів Subroutine Обрій (X1, Y1, X2, Y2; Верх, Низ).

Ця програма використовує лінійну інтерполяцію заповнення масивів горизонтів між X1 і X2.

Max (a, b) — визначає більше з a і b.

Min (a, b) — визначає менше з a і b перевірка вертикальності нахилу if (X2 (X1) = 0 then.

Верх (X2) = Max (Верх (X2), Y2).

Низ (X2) = Min (Низ (X2), Y2) else.

Нахил = (Y2 (Y1)/(X2 (X1) for x = X1 to X2 step 1 y = Нахил * (x (X1) + Y1.

Верх (x) = Max (Верх (x), y).

Низ (x) = Min (Низ (x), y) next x end if return.

підпрограма обчислення перетину поточної кривою з обрієм Subroutine Перетин (X1, Y1, X2, Y2, Масив; Xi, Yi).

Цю процедуру обчислює те що двох відрізків прямых.

Масив містить інформацію про відповідному горизонте.

Sign — функція приймаюча значення (1, 0, 1, якщо знак її аргумента.

0 відповідно перевірка нескінченності нахилу if (X2 — X1) = 0 then.

Xi = X2.

Yi = Масив (X2) else обчислення перетину обхід починається із дуже лівої використовуваної точки те що вважається виявлених, коли змінюється знак різниці значень y.

Нахил = (Y2 — Y1)/(X2 — X1).

Ysign = Sign (Y1 + Нахил (Масив (X1 + 1)).

Csign = Ysign.

Yi = Y1 + Наклон.

Xi = X1 + 1 while Csign = Ysign.

Yi = Y1 + Наклон.

Xi = X1 + 1.

Csign = Sign (Yi — Масив (Xi)) end while вибирається найближче ціла кількість if |Yi (Нахил (Масив (X1 — 1)| (|Yi (Нахил (Масив (X1)| then.

Yi = Y1 — Наклон.

Xi = X1 — 1 end if end if return.

У наведених вище алгоритмі і прикладі функція у = f (x, z) розглядалася лише за z = const. Часто буває зручно викреслювати криві, вважаючи постійними як z, і x. У цьому виникає ефект перехресною штрихування. На погляд може бути, що перехресну штрихування можна отримати роботу шляхом накладення два результати, освічених площинами z = const і x = const. Але це негаразд. Вірний результат виходить при обробці тих кривих у складі що у площинах z = const і x = const, які стоять найближче до горизонтальним при звичайному порядку їх прямування. Проте після обробки кожної кривою, найближчій до горизонтальній, необхідно обробляти ділянки кривих, що у ортогональних їй площинах, що є між зазначеної кривою і кривою, наступній з ним. Зрозуміло, при обробці обох послідовностей кривих потрібно використовувати одні й самі масиви верхнього й нижнього плаваючих горизонтів. Якщо використовується перехресна штрихування, то ми не формувати ліве та праве бічні ребра.

2. Алгоритм Робертса.

Алгоритм Робертса є перше відоме вирішення завдання про видаленні невидимих ліній. Це математично елегантний метод, працював у об'єктному просторі. Алгоритм, передусім, видаляє з кожного тіла ті ребра чи межі, які екрануються самим тілом. Потім кожна з видимих ребер кожного тіла порівнюється зі кожним із решти тіл визначення того, яка його частину або частини, якщо вони є, екрануються цими тілами. Тому обчислювальна трудомісткість алгоритму Робертса зростає теоретично як квадрат числа об'єктів. Саме це факт призвела до зниження інтересу до алгоритму Робертса. Проте математичні методи, використовувані в цьому алгоритмі, прості, потужні і точні. З іншого боку, цей алгоритм можна використовуватиме ілюстрації деякі важливі концепцій. Нарешті, більш пізні реалізації алгоритму, використовують попередню пріоритетну сортування вздовж осі z й прості габаритні чи минимаксные тести, демонструють майже лінійну залежність від кількості объектов.

У алгоритмі Робертса потрібно, щоб усе зображувані тіла чи об'єкти були опуклими. Невыпуклые тіла повинні прагнути бути розбиті на опуклі частини. У цьому алгоритмі опукле багатогранне тіло з пласкими гранями має представлятися набором від перетинання площин. Рівняння довільній площини у тривимірному просторі має вид.

ох + by + cz + d = 0 (3.1).

В матричної формі це відбувається так:

[pic] или.

[pic] де [pic] є площину. Тому будь-яка опукле тверде тіло можна сформулювати матрицею тіла, що з коефіцієнтів рівнянь площин, т. е.

[pic].

где кожен стовпець містить коефіцієнти однієї плоскости.

Нагадаємо, будь-яка точка простору представима в однорідних координатах вектором.

[pic].

Понад те, якщо точка [P.S] лежить площині, то [S]*[P]T = 0. Якщо ж [P.S] не лежить площині, то знак цього скалярного твори показує, з якого боку від площині розташована точка. У алгоритмі Робертса передбачається, що точки, що лежать всередині тіла, дають позитивне скалярне произведение.

Хоча рівняння площині (3.1) містить чотири невідомих коефіцієнта, може бути нормувати те щоб d = 1 отже, трьох неколлинеарных точок достатньо визначення цих коефіцієнтів. Підстановка координат трьох неколлинеарных точок (x1, y1, z1), (x2, y2, z2), (x2, y2, z2) в нормоване рівняння (3.1) дает:

ax1 + by1 + cz1 = (1 ax2 + by2 + cz2 = (1 ax3 + by3 + cz3 = (1.

В матричної формі це відбувається так:

[pic] или.

[pic] (3.2).

Вирішення цього рівняння дає значення коефіцієнтів рівняння плоскости:

[pic].

Інший спосіб використовується, якщо відомий вектор нормальний до площині, т. е. n = ai + bj + ck.

где і, j, k — поодинокі вектори осей x, y, z відповідно. Тоді рівняння площині прийме вид.

ax + by + cz + d = 0 (3.3).

Розмір d обчислюється з допомогою довільній крапки над площині. У частковості, якщо компоненти цієї крапки над площині (х1, y1, z1) то: d = ((aх1 + by1 + cz1) (3.4).

Оскільки обсяг обчислень в алгоритми видалення невидимих ліній чи поверхонь зростає зі збільшенням кількості многоугольников, для описи поверхонь вигідно використовувати багатокутники з більш як трьома сторонами. Ці багатокутники може бути як невыпуклыми, і неплоскими. Метод, запропонований Мартіном Ньюэлом, дозволяє знайти як точне рішення для рівнянь площин, містять плоскі багатокутники, і «найкраще» наближення для неплоских многоугольников. Цей метод еквівалентний визначенню нормальний у кожному вершині багатокутника у вигляді векторного твори що прилягають ребер і усереднення результатів. Якщо a, b, з, d — коефіцієнти рівняння площині, то.

[pic] (3.5) де if і =n then j = 1 else j = і + 1.

а d обчислюється з допомогою будь-який крапки над плоскости.

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

Якщо [У] - матриця однорідних координат, що становить вихідні вершини тіла, а [Т] - матриця розміром 4×4 видового перетворення, то перетворені вершини таковы:

[ЗТ] = [В][T] (3.6).

где [ЗТ] - перетворена матриця вершин. Використання рівняння (3.2) дозволяє їм отримати рівняння вихідних площин, обмежують тело:

[В][V] = [D] (3.7).

где [V] - матриця тіла, а [D] у правій частині - нульова матриця. Аналогічно рівняння перетворених площин задаються наступним образом:

[ВТ][VТ] = [D] (3.8).

где [VТ] - перетворена матриця тіла. Прирівнюючи ліві частини рівняння (3.7) і (3.8), получаем.

[ВТ][VT] = [В][V].

Подставляя рівняння (3.6), скорочуючи на [У] і примножуючи зліва на [T]-1 имеем.

[VT] = [T]-1[V].

Итак, перетворена матриця тіла виходить множенням вихідної матриці тіла зліва на зворотний матрицю видового преобразования.

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

Якщо глядач знаходиться у нескінченності на позитивної полуоси z і дивиться початку координат, його погляд направлений у бік негативною полуоси z. У однорідних координатах вектор такого напрями равен:

[pic].

который служить, ще, чином точки, що у нескінченності на негативною полуоси z. Фактично [Є] представляє будь-який пункт, що лежить на площині z = ((, т. е. будь-який пункт типу (x, y, ((). Тому, якщо скалярне твір [Є] на стовпець, відповідний який-небудь площини у матриці тіла, негативно, то [Є] лежить по негативну бік цьому відношенні. Отже, ці площині невидимі з точки спостереження, що у площині z = (, а пробна точка на z = ((екранується самим тілом, як показано на рис. 3.8. Такі площині називаються не лицьовими, а відповідні їм межі задніми. Следовательно,.

[Е][V] < 0.

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

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

Цей метод можна використовувати також і простий закраски. Інтенсивність чи колірної відтінок багатокутника робиться пропорційним проекції нормальний до на напрям взгляда.

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

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

Після визначення нелицевых площин залишається знайти нелицевые відтинки. Нелицевой відрізок утворюється внаслідок перетину пари нелицевых площин. Після першим етапом видалення нелицевых відрізків необхідно з’ясувати, чи існують такі відтинки, які екрануються іншими тілами на картинці чи сцені. І тому кожен що залишилося відрізок чи ребро потрібно порівняти коїться з іншими тілами сцени чи картинки. У цьому використання пріоритетною сортування (z-сортировки) і простого минимаксного чи габаритного з прямокутної объемлющей оболонкою тестів дозволяє видалити цілі групи чи кластери відрізків і тіл. Наприклад, якщо все тіла в сцені упорядковані у певній пріоритетному списку, использующем значення z найближчих вершин до подання відстані до спостерігача, то ніяке тіло із списку, яка має найближча вершина перебуває далі від спостерігача, ніж сама віддалена з кінцевих точок ребра, неспроможна закривати це ребро. Понад те, жоден з решти тіл, прямокутна оболонка якого розташована повністю справа, зліва, над або під руба, неспроможна екранувати це ребро. Використання цих прийомів значно скорочує число тіл, з якими потрібно порівнювати кожен відрізок чи ребро.

Порівняйте відрізка P1P2 з тілом зручно використовувати параметрическое представлення цього проекту отрезка:

Р (t) = P1 + (Р2 — P1) t 0 (t (1.

v = p. s + dt.

где v — вектор крапки над відрізку, p. s — початкова точка, d — напрям відрізка. Необхідно визначити, було б відрізок невидимим. Якщо він невидимий, треба знайти значення t, котрим він невидимий. І тому формується інший параметричний відтинок від точки Р (t) до точки спостереження g:

Q (a, t) = u = v + ga = p. s + dt + ga 0 (t (1, a (0.

Тут a і t виконують аналогічні функції. Заданий значення t вказує точку на відрізку P (t), а a вказує точку на відрізку, проведеному від точки P (t) до точки спостереження. Фактично Q (a, t) є площину в тривимірному просторі. Кілька (a, t) визначає точку в цій площині. Значення a позитивно, оскільки тіла, экранирующие P (t) можуть бути лише у тієї частину цієї площині, яка міститься між відрізком P (t) і точкою наблюдения.

Скалярне твір будь-який точки, лежачої всередині тіла, на матрицю тіла позитивно. Якщо ж точка лежить всередині тіла, вона невидима. Тож визначення частини відрізка, яка екранується тілом, досить знайти значення a і t, котрим скалярне твір Q (a, t) = u на матрицю тіла позитивно. Це скалярне твір равно:

h = u * [VT] = p. s * [VT] + td * [VT] + ag * [VT] >0 0 (t (1, a (0.

Якщо всі компоненти h неотрицательны декому t і a, відрізок при цих значеннях t екранується даним тілом. Означимо p = p. s * [VT] q = d * [VT] w = g * [VT] запишемо умови як hj = pj + tqj + awj 0 (t (1, a (0 де j — номер шпальти в матриці тіла. Ці умови їх необхідно виконувати при всіх значеннях j, т. е. всім площин, обмежують обсяг тіла. Прикордонний випадок між видимістю і невидимістю виникає, коли hj = 0. При hj = 0 точка лежить площині. Вважаючи hj = 0 всім площин, ми одержимо систему рівнянь щодо a і t, які мають задовольнятися одночасно. Результат можна отримати роботу шляхом спільного розв’язання різноманітних пар рівнянь з цього системи, у своїй знайдуть все значення a і t, у яких змінюється значення видимості відрізка. Схема рішення показано на рис. 3.10. Кількість можливих рішень при j рівняннях (площинах) одно j (j (1)/2. Кожне рішення, у діапазонах 0 (t (1, a (0, підставляється в інші рівняння для перевірки того, що умова hj (0 виконано. Пошук коректних рішень виробляється для здобуття права знайти мінімальне серед максимальних значень параметра t (tminmax) і забезпечити максимальне серед мінімальних значень t (tmaxmin). Відтинок невидимий при (tmaxmin) < t < (tminmax). Останнє вимога є простим наслідком з класичної завдання лінійного программирования.

Рішення за українсько-словацьким кордоном a = 0 виникає у разі протыкания (объектов).

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

З практики відомо, що рішення задовольняють неравенствам hj > 0, можуть існувати й з-поза меж області, обмеженою умовами 0 (t (1 і a = 0. Тому три рівняння, описують межі, тобто. t = 0, t (1 = 0 і a = 0, потрібно додати безлічі рівнянь hj = 0. Тепер кількість рішень одно (j + 2)(j + 3)/2, де j — кількість площин, обмежують опуклий обсяг тела.

Як згадувалося раніше, вибір максимального з мінімального і мінімального з максимальних значень t серед можливих коректних рішень зазначеної системи рівнянь є простою завданням лінійного програмування. Її вирішення еквівалентно визначенню коректною обмеженою області, получающейся внаслідок графічного рішення. Передбачається, що це алгоритм використовується лише таких відрізків, про яких відоме, що вони частково чи цілком невидимі. Усі нелицевые і все повністю видимі відтинки виявлено і віддалені на початок роботи алгоритму. Алгоритм розпочинає свою роботу з цими значеннями t і a, які є рішеннями пари лінійних рівнянь з номерами е1 і е2, ні з tmin і tmax (поточними мінімальним і максимальним значеннями t) і з n (потужністю безлічі рівнянь). У першому етапі алгоритму перевіряється виконання умов hj > 0. Якщо такі умови виконані, то, на другому етапі обчислюються значення tmin і tmax. Результатом є значення tmaxmin і tminmax.

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

u = p. s + td + ag.

При a = 0 значення u задає сам відрізок. Далі, якщо a = 0, при t = 0 і t = 1 виходять кінцеві точки відрізка. Відомо також, что.

hj = u *[VT] = pj + qjt+ wja.

и зауважимо, що з t = 0 pj є скалярним твором кінцевий точки відрізка і j-й площині, яка обмежує тіло. Аналогічно pj + qj є скалярним твором інший кінцевий точки відрізка і j-й площині, яка обмежує тіло. Нарешті, нагадаємо, що j-я площину, що обмежує тіло, видимою, якщо wj = 0. Тому, якщо wj (Про і pj (0, то один кінець відрізка лежить чи видимої площині чи торгівлі між видимої площиною і точкою спостереження. Якщо ж pj + qj (0, то інший край відрізка також лежить або на видимої площині, або між цієї площиною і точкою спостереження. Отже, відрізок повністю бачимо, для будь-якого j.

wj (Про і pj (0 і pj + qj (0.

Ці умови гарантують, що нерівності hj (0 неможливо знайти виконані ані за яких a (0 і 0 (t (1. Тому ніяка частина відрізка може бути невидимою, т. е. відрізок повністю видим.

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

Удаление нелицевых плоскостей.

До кожного тіла в сцене:

Сформувати багатокутники граней і ребра, з списку вершин тела.

Обчислити рівняння площині кожної полигональной межі тела.

Перевірити знак рівняння плоскости:

Взяти будь-який пункт всередині тіла, наприклад усереднивши координати його вершин.

Обчислити скалярне твір рівняння площини і точки всередині тела.

Якщо це скалярне твір < Про, то змінити знак рівняння цієї плоскости.

Сформувати матрицю тела.

Помножити її зліва на матрицю, зворотний матриці видового перетворення, що включає перспективу.

Обчислити і запам’ятати габарити прямокутної объемлющей оболонки перетвореного обсягу: xmin, xmax, ymin, ymax.

Визначити нелицевые плоскости:

Обчислити скалярне твір пробної точки, що у нескінченності, на перетворену матрицю тела.

Якщо це скалярне твір < Про, то площину невидима.

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

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

Якщо поставлено лише одна тіло, то алгоритм завершается.

Сформувати пріоритетний список цих тел:

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

До кожного тіла з пріоритетного списка:

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

Провести перевірки екранізування для прямокутних объемлющих оболонок пробного об'єкту і пробного тела:

Якщо xmin (пробне тіло) > xmax (пробний об'єкт) чи xmax (пробне тіло) < xmin (пробний об'єкт) чи ymin (пробне тіло) > ymax (пробний об'єкт) чи ymax (пробне тіло) < ymin (пробний объект),.

то пробне тіло неспроможна екранувати жодного ребра пробного объекта.

Перейти ось до чого спробному тілу. У протилежному случае:

Провести попередні перевірки протыкания, аби побачити, не проштрикується чи пробне тіло пробним об'єктом та чи існує можливість часткового екранізування першого последним.

Порівняти максимальне значення z у пробного об'єкта з мінімальним значенням z у пробного тела.

Якщо zmax (пробний об'єкт) < zmin (пробне тіло), то протыкание неможливо. Перейти ось до чого тілу. У протилежному случае:

Перевірити видиме протыкание.

Якщо zmin (пробний об'єкт) > zmax (пробне тіло), то пробний об'єкт може проколоти передню грань пробного тела.

Встановити прапор видимого протыкания на подальше использования.

Занести проткнутое тіло у список протыканий.

Якщо xmax (пробне тіло) > xmin (пробний об'єкт) чи xmin (пробне тіло) < xmax (пробний об'єкт), то пробний об'єкт може проколоти бік пробного тела.

Встановити прапор видимого протыкания на подальше использования.

Завести тіло до список протыканий.

Якщо ymax (пробне тіло) > ymin (пробний об'єкт) чи ymin (пробне тіло) < ymax (пробний об'єкт), то пробний об'єкт може проколоти гору чи віз пробного тела.

Встановити прапор видимого протыкания на подальше использования.

Занести проткнутое тіло у список протыканий.

Якщо список протыканий порожній, то встановлювати прапор протыкания не надо.

Провести перевірки екранізування ребер:

Обчислити p. s і d для ребра.

Ви вважати p, q, w кожної площині, несучою грань пробного тела.

Перевірка повної видимості. Якщо ребро повністю, певне, то можливість перейти до наступному ребру.

Сформувати рівняння hj = 0 і розв’язати їх, об'єднуючи попарно та включивши до системи рівняння кордонів t = 0 і t = 1. Якщо встановлено прапор видимого протыкания, то систему треба включити й рівняння кордону a = 0. Запам’ятати точки протыкания. Інакше кордон a = 0 не учитывать.

Для кожної пари (t, a), що є рішенням перевірити виконання умов 0 (t (1, a (0 і hj > 0 всіх інших площин. Якщо такі умови виконані, то знайти tmaxmin і tminmax.

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

Определить видимі відтинки, котрі пов’язують точки протыкания:

Якщо прапор видимого протыкания не встановлено, можливість перейти до процедурі визуализации.

Якщо точок протыкания нема, можливість перейти до процедурі визуализации.

Сформувати всіх можливих ребра, що з'єднують точки протыкания, для пар тіл, пов’язаних ставленням протыкания.

Перевірити екранування всіх що з'єднують ребер обома тілами, пов’язаними ставленням протыкания.

Перевірити екранування решти що з'єднують ребер іншими тілами сцени. Запам’ятати видимі отрезки.

Візуалізувати решта видимі відтинки ребер.

3. Алгоритм використовує Z-буфер

Це з найпростіших алгоритмів видалення невидимих поверхонь. Працює цей алгоритм у просторі зображення. Ідея z-буфера є простим узагальненням ідеї про буфері кадру. Буфер кадру використовується для запам’ятовування атрибутів (інтенсивності) кожного пиксела у просторі зображення. Z-буфер — це окремий буфер глибини, використовуваний для запам’ятовування координати z чи глибини кожного видимого пиксела в просторі зображення. У процесі роботи глибина чи значення z кожного нового пиксела, що потрібно занести в буфер кадру, порівнюється зі глибиною того пиксела, які вже занесли у z-буфер. Якщо це порівняння показує, новий піксел розташований попереду пиксела, що у буфері кадру, то новий піксел заноситься у цей буфер та, крім того, виробляється коригування z-буфера новим значенням z. Якщо ж порівняння дає протилежний результат, те дій немає. По суті, алгоритм є пошуком по x і y найбільшого значення функції z (z, y).

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

Основна хиба алгоритму — великий обсяг необхідної пам’яті. Якщо сцена піддається видовому перетворенню і відсікається до фіксованого діапазону координат z значень, можна використовувати z-буфер з фіксованою точністю. Щодо глибині потрібно обробляти з більшою точністю, ніж координатну інформацію на площині (x, y); зазвичай буває досить 20 біт. Буфер кадру розміром 512×512×24 біт в комбінації з zбуфером розміром 512×512×20 біт вимагає майже 1.5 мегабайтів пам’яті. Проте зниження ціни пам’ять робить економічно виправданим створення спеціалізованих запам’ятовувальних пристроїв для z-буфера і що з ним аппаратуры.

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

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

Більше формальне опис алгоритму z-буфера таково:

Заповнити буфер кадру фоновим значенням інтенсивності чи цвета.

Заповнити z-буфер мінімальним значенням z.

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

До кожного Пиксел (x, y) в многоугольнике обчислити його глибину z (x, y).

Порівняти глибину z (x, y) багатозначно Z буфер (x, y), хранящимися в zбуфері у цій самій позиции.

Якщо z (x, y) > z буфер (x, y), то записати атрибут цього багатокутника (інтенсивність, колір тощо. п.) в буфер кадру і замінити zбуфер (x, y) на z (x, y).

Інакше ніяких дій не производить.

Як попереднього кроку там, де це доцільно, застосовується видалення нелицевых граней.

Якщо відомо рівняння площині, несучою кожен багатокутник, то обчислення глибини кожного пиксела на що сканує рядку можна проробити покроковим способом. Як відомо рівняння площині має вид.

ax + by + cz + d =0 z = ((ax + by + d)/c (0.

Для що сканує рядки y = const. Тому глибина пиксела наэтой рядку, у якого x = x + (x, равна.

z1 (z = ((ax1 + d)/c + (ax + d)/c = a (x (x1)/c чи z1 = z — (a/c)(x.

Но (x = 1, тому z1 = ((а/с).

Алгоритм, використовує z-буфер, можна також ознайомитися застосувати для побудови перетинів поверхонь. Зміниться лише оператор порівняння: z (x, y) > z-буфер (x, y) and z (x, y) (Zсечения де Zсечения — глибина шуканого перерізу. Ефект у тому, що залишаються лише елементи поверхні, що лежать на сечении чи позаду него.

4. Алгоритм визначення видимих поверхонь шляхом трасування лучей.

Оцінки ефективності всіх алгоритмів видалення невидимих поверхонь, викладених раніше, залежить від певних характеристик когерентності тієї сцени, на яку ведеться пошук її видимих ділянок. На відміну від нього трасування променів є методом грубої сили. Головна ідея, що у підставі цього методу, у тому, що спостерігач бачить будь-який об'єкт у вигляді испускаемого якимось джерелом світла, який вихоплює цей об'єкт і далі якимось шляхом сягає спостерігача. Світло може сягнути спостерігача, позначившись від поверхні, переломившись чи пройшовши крізь неї. Якщо простежити за променями світла, випущеними джерелом, можна переконатися, що дуже деякі їх дійдуть до спостерігача. Отже, цей процес б вычислительно неефективний. У слідстві цього було запропоновано відстежувати (трасувати) проміння на напрямку, т. е. від спостерігача об'єкта, як показано на рис. 3.11. У першому алгоритмі трасування припинялася, щойно промінь перетинав поверхню видимого непрозорого об'єкта; т. е. промінь використовувався лише обробки прихованих чи видимих поверхонь. З часом реалізували алгоритм трасування променів з допомогою загальних моделей висвітлення. Ці алгоритми враховують ефекти відображення одного об'єкта від поверхні іншого, заломлення, прозорості й затінення. Виробляється також усунення ступенчатости. Розглянемо застосуванням методу трасування променів для визначення видимих чи прихованих поверхностей.

Рис. 3.11 служить ілюстрацією алгоритму трасування променів. У цьому вся алгоритмі передбачається, що сцена вже перетворять на простір зображення. Перспективний перетворення немає. Вважається, що думка чи спостерігач перебуває у нескінченності на позитивної полуоси z. Тому всі світлові промені рівнобіжні осі z. Кожен промінь, який з спостерігача, проходить через центр пиксела на растре до сцени. Траєкторія кожного променя відстежується, щоб визначити, які саме об'єкти сцени, якщо існують, перетинаються з цим променем. Необхідно перевірити те що кожного об'єкта сцени з кожним променем. Якщо промінь перетинає об'єкт, то визначаються різноманітні точки перетину променя і об'єкта. Можна отримати дуже багато перетинань, якщо розглядати багато об'єктів. Ці перетину упорядковуються за глибиною. Перетин з максимальним значенням z представляє видиму поверхню для даного пиксела. Атрибути цього об'єкта йдуть на визначення характеристик пиксела.

Якщо думка перебуває у нескінченності, алгоритм трасування променів лише трохи ускладнюється. Тут припускається, що спостерігач продовжує перебувати на позитивної полуоси z. Картинна площину, т. е. растр, перпендикулярна осі z, як показано на рис 3.12. Завдання полягає у тому, щоб побудувати одноточечную центральну проекцію на картинну плоскость.

Найважливішим елементом алгоритму визначення видимих поверхонь шляхом трасування променів, є процедура визначення перетинань. У склад сцени можна включати будь-який об'єкт, котрій можна створити процедуру побудови перетинань. Об'єкти сцени можуть бути з набору пласких многоугольников, багатогранників чи тіл, обмежених чи визначених квадратичными чи биполиномиальными параметрическими поверхнями. Оскільки 75−95% часу, затрачуваного алгоритмом трасування променів, забирають визначення перетинань, то ефективність процедури пошуку перетинань надає значно впливом геть продуктивність всього алгоритму. Обчислювальна вартість визначення перетинань довільній просторової прямий (променя) з однією виділеним об'єктом може бути високої. Щоб позбутися непотрібного пошуку перетинань, виробляється перевірка перетину променя з об'ємної оболонкою аналізованого об'єкта. Та навіть якщо промінь не перетинає оболонки, то ми не потрібно більше шукати перетинань цього об'єкта з променем. Як оболонки можна використовувати прямокутний паралелепіпед чи сферу. Хоча, як показано, на рис. 3.13, використання сфери у ролі оболонки може бути неефективним, факт перетину тривимірного променя зі сферою визначається досить легко. Зокрема, якщо відстань від центру сферичної оболонки до променя перевершує радіус цієї сфери, промінь не перетинає оболонки. Отже, вона може перетинатися й з объектом.

Тому тест зі сферичної оболонкою зводиться до визначення відстані від точки до тривимірної прямий, т. е. променя. Використовуватимемо параметрическое уявлення прямий, що проходить через точки P1(x1, y1, z1) і P2(x2, y2, z2) т. е.:

Р (t) = P1 + (P2 (P1)t з компонентами x = x1 +(x2 (x1)t = x1 +at y = y1 +(y2 (y1)t = y1 +bt z = z1 +(z2 (z1)t = z1 +ct.

Тогда мінімальне відстань d від цього прямий до точки P0(x0, y0, z0) одно: d2 = (x (x0)2 + (y (y0)2 +(z (z0)2.

а параметр t, визначальний найближчу точку Р (t) равен:

[pic].

Если d2 > R2, де R — радіус сферичної оболонки, то промінь неспроможна перетнутися з объектом.

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

Однією простий процедурою можна звести дослідження з прямокутної оболонкою до порівнянню знаків, спрощуючи цим обчислення перетинань з об'єктом, а також порівняння за глибиною серед точок перетину. У цьому процедурі використовуються перенесення поворотів навколо координатних осей у тому, щоб домогтися збіги променя з віссю z. Аналогічним перетворенням піддається і прямокутна оболонка об'єкта. Промінь перетинає оболонку, тоді як нової перенесеної і поверненою системі координат знаки xmin і xmax, а як і ymin і ymax. протилежні, як показано на рис. 3.14.

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

Q (x, y, z) = a1x2 + a2y2 + a3z2 + b1yz + b2xz + b3xy + c1x + c2y + c3z +d = 0.

После застосування перетворення, що є комбінацією перенесення і повороту і використовується для суміщення променя з віссю z, те що цього променя з поверхнею, якщо воно має місце, виникає при x = y = 0. Тому у випадку точки перетину є рішеннями уравнения:

[pic] т. е.

[pic].

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

Обчислення перетинань для елементів биполиномиальных параметричних поверхонь складніші. Уиттед запропонував простий метод розбивки для елемента бикубической поверхні. Обчислення виконуються з елементом поверхні у його вихідному становищі. Якщо промінь перетинає сферичну оболонку елемента поверхні, цей шматок розбивається з допомогою алгоритму розбивки запропонованого Кэтмулом. Потім промінь перевіряється на те що зі сферичними оболонками подэлементов. Якщо те що не виявлено, то промінь не перетинається і із самою елементом. Якщо ж промінь перетинається зі сферичної оболонкою якогось подэлемента, то останній розбивається далі. Процес завершується, якщо жодна з сферичних оболонок не пересічена або якщо досягнуть наперед визначений їх мінімальний розмір. Ці сферичні оболонки мінімальної відстані і є шуканими перетинами променя і елемента поверхности.

При реалізації перетворення, котрий сполучає промінь з віссю z, метод розбивки можна використовувати скоріш стосовно прямокутним оболонок, ніж до сферичним. Це скорочує число разбиений збільшує ефективність алгоритму. Для параметричних поверхонь, які мають властивістю опуклої оболонки, наприклад для поверхонь Безьє і В-сплайнов, число разбиений можна скоротити додатково з допомогою ускладнення алгоритму, для подэлементов скористатися їхніми опуклими оболонками замість прямоугольных.

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

Q (u, w) = 0 з компонентами x = f (u, w) y = g (u, w) z = h (u, w).

в реформованій системі координат виконано умова x = y = 0. Отже, f (u, w) = 0 g (u, w) = 0.

Совместное розв’язання цієї пари рівнянь дає значення u і w для точок перетину. Підстановка цих значень в рівняння z = h (u, w) дає компоненту z для точок перетину. Невдача спроби знайти дійсне рішення означає, що промінь не перетинає поверхню. Ступінь системи рівнянь для u, w дорівнює твору ступенів биполиномиальных поверхонь. Бикубическая поверхню, наприклад, має шосту ступінь. Отже, у випадку знадобляться чисельні на методи вирішення. Там, де це припустимо, для початкового наближення u і w можна використовувати перетину променя з опуклої оболонкою. Для отримання перетинань в вихідної системі координат, як й раніше, варто використовувати зворотне преобразование.

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

Алгоритм трасування променів простих непрозорих поверхонь можна уявити наступним образом:

Підготовка даних для сцены:

Створити список об'єктів, у якому по меншою мірою таку информацию:

Повне опис об'єкта: тип, поверхню, характеристики тощо. п.

Опис сферичної оболонки: центр і радиус,.

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

Опис прямокутної оболонки: xmin, xmax, ymin, ymax, zmin, zmax.

До кожного трассируемого луча:

Виконати кожному за об'єкта тривимірний тест зі сферичної оболонкою в вихідної системі координат. Якщо промінь перетинає цієї сфери, то занести об'єкт до списку активних об'єктів. Якщо список активних об'єктів порожній, то зобразити даний піксел з фоновим значенням інтенсивності і продовжувати роботу. Інакше, перенести повернути промінь те щоб він совместился з віссю z.

Запам’ятати це комбіноване преобразование.

До кожного об'єкта зі списку активних объектов:

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

Якщо список перетинань порожній, то зобразити даний піксел з фоновим значенням интенсивности.

Інакше визначити z для списку пересечений.

Обчислити перетворення, зворотне комбінованому преобразованию.

Використовуючи це зворотне перетворення, визначити точку перетину в вихідної системі координат.

Зобразити даний піксел, використовуючи атрибути пересеченного об'єкту і відповідну модель освещенности.

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

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

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

Викладене вище простий алгоритм не використовує тієї обставини, що деякі межі багатогранника є нелицевыми і можна відразу видалити, до уваги береться тут і можлива когерентність сцени. Наприклад, несуттєвий порядок обробки пікселів. Разом про те розгляд цих пікселів в порядку сканування рядки розгорнення дозволило б скористатися в алгоритмі когерентністю скануючих рядків. Інший підхід може полягати у підрозділі сцени, причому облік когерентності областей привела б до зменшення числа об'єктів, аналізованих кожному за променя і, отже, підвищення ефективності алгоритму. Хоча використання подібних прийомів підвищує ефективність алгоритму визначення видимості непрозорих поверхонь їх застосувати загалом алгоритмі трасування променів, що враховує відбиток, переломлення і. Наприклад, тоді як алгоритмі враховано відбиток, то об'єкт, що цілком закритий іншим об'єктом, може бути видимим, відбитка від третього об'єкта. Оскільки метод трасування променів є метолом грубої сили, алгоритми визначення видимості непрозорих поверхонь, обговорювані раніше, є як эффективными.

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

Якщо видима поверхню для Пиксел (x, y) відповідає фону чи відрізняється від видимої поверхні для Пиксел (x — 1, y) чи для.

Пиксел (x, y — 1), то зобразити цей піксел. Інакше піксел не изображать.

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

[pic].

где lx і ly — відстань між променями за горизонталлю і вертикалі відповідно. Кожне складова (zi-1 — zi) є ділянку променя, внутрішній заданого тіла. Обсяг тіла, отже, дорівнює сумі обсягів усіх таких прямокутних паралелепіпедів. Точність результатів залежить від кількості використаних променів. Точність можна підвищити, помірковано збільшивши обсяг обчислень і рекурсивно зменшивши розмір «пиксела», у цьому разі, якщо обсяги суміжних прямокутних паралелепіпедів різняться понад заздалегідь задану величину. За такого підходу точніше визначаються обсяги тих елементів тіла, де мають місце зміни, наприклад, у околицях ребер тіл, обмежених криволинейными поверхностями.

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

Резюме.

У роботі детально обговорювалося кілька основних алгоритмів, що використовуються виконання завдання видалення невидимих ліній чи поверхонь. Однак подія ця в усіх, що є. Крім вище сказаного може бути алгоритм видалення невидимих ліній запропонований Хеджли, який грунтується на використанні списку пріоритетів, розбивки і построчного сканування. Цей алгоритм працює у просторі об'єкта, отримує на вході опуклі чи невыпуклые багатокутники, а оцінка його ефективності лінійно залежить від кількості объектов.

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

Наприкінці сказати, що комп’ютерна графіка не на місці. Давно вже існують численні програмні і апаратні реалізації алгоритмів побудови зображення. На ринку цілком вистачає широко представлені різноманітні графічні акселератори і масиви швидкої пам’яті. Провідні виробники електронних компонентів підтримують обробку зображення на рівні процессорной техніки (MMX — Intel, 3D Now — AMD), отже, стає можливим реалізація «повільних», але дають найкраща чеснота зображення алгоритмів. Окремо треба сказати таке явища, як віртуальна реальність, що вже нині отримує широке поширення. Одне слово, комп’ютерна графіка розвиватиметься до того часу — поки що розвиватись агресивно та вдосконалюватися комп’ютерна техніка. Содержание.

| Запровадження |1 | |1. Введення ЄІАС у машинну графіку |2 | |2. Растрова графіка |3 | | 2.1. Алгоритми креслення відрізків |3 | | 2.2. Цифровим диференціальний аналізатор |3 | | 2.3. Алгоритм Брезенхема |5 | | 2.4. Алгоритм Брезенхема для генерації окружностей |7 | | 2.5. Растрова развёртка суцільних областей |14 | | 2.6. Растрова развёртка многоугольников |14 | | 2.7. Алгоритм з упорядкованим списком ребер |17 | | 2.8. Алгоритм заповнення по ребрам |18 | | 2.9. Алгоритм заповнення з запалом |19 | | 2.10. Порядковий алгоритм заповнення з запалом |20 | |3. Видалення невидимих ліній і поверхонь |23 | | 3.1. Алгоритм плаваючого горизонту |26 | | 3.2. Алгоритм Робертса |38 | | 3.3. Алгоритм використовує z-буфер |50 | | 3.4. Алгоритм визначення видимих поверхонь |53 | |шляхом трасування променів | | | Резюме |63 | Литература:

I. Д. Роджерс «Алгоритмічні основи машинної графики».

Москва «Світ» 1989.

II. Є. У. Шикин, А. У. Боресков, А. А. Зайцев.

«Почала комп’ютерної графики».

Москва «Діалог — МІФІ» 1993.

———————————;

Рис. 2.11. Гранично-определённая область.

Рис. 2.10. Внутрішньо — певна область.

2.).

2. Основна ідея алгоритму Брезенхема.

2. Розбір випадків для обобщённого алгоритму Брезенхема.

3. Генерація повної окружності з дуги у першому октанте.

4. Окружність у першому квадранте.

5. Вибір пікселів у першому квадранте.

6. Перетин окружності і сітки растра.

7. Растрова развёртка суцільний области.

8. Системи координати рядків сканирования.

9. Особливості перетину зі рядками сканирования.

3. Необхідність видалення невидимих линий.

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

3. Криві в січних областях із постійною координатой.

4. Обробка нижньої боку поверхности.

5. Лінійна інтерполяція між заданими точками.

6. Ефект від перетинання кривых.

7. Ефект зазубленого ребра.

8. Функція y = (1/5) sin x co z ((3/2) co (7a/4) * exp ((a), a = (x (.

()2 + (z (()2, изображённая в інтервалі (0, 2() з допомогою алгоритму плаваючого горизонта.

9. Не лицьові плоскости.

10. Схема рішення про a і t.

11. Проста трасування лучей.

12. Трасування променя з урахуванням перспективы.

13. Сферична і прямокутна оболочки.

14. Перетин прямокутної області у реформованій системі координат.