Материал: 252_337

Розглянемо фрагмент кола, що належить другому октанту

Для того щоб на і-му кроці визначити, яка з двох точок - зовнішня чи внутрішня - найкраще підходить для зображення кола, необхідно порівняти обчислені значення dps і dpt, обчислив­ ши значення dt = d - dpt. Якщо dt < 0, то вибирається зовнішня точка dps, а якщо а-^ 0, то вибирається внутрішня точка dpt.

Виконаємо покроково алгоритм Брезенхема для екранної побудови кола.

На першому кроці алгоритму розглядається точка з коорди­ натами (0; і?). Зрозуміло, вона лежить на колі.

На другому кроці необхідно визначитися, яку точку брати: зовнішню з координатами (1; і?) чи внутрішню з координатами (1; R - 1) (мал. 174, а). Виконаємо деякі обчислення і знайдемо для цього крока відхилення між значеннями d і d t: dl = = 1 + R2-R2-(R2-(1 + (R- І)2 ) = 3 - 2R. Таким чином отри­ маємо умову для вибору між зовнішньою та внутрішньою точ­ ками: якщо 3 - 2R < 0, то вибираємо зовнішню точку (1; R), а якщо 3 - 2R ^ 0, то внутрішню (1; R - 1).

Перейдемо до (і + 1)-го кроку. На цьому кроці вибір точки залежить від того, яка саме точка - внутрішня чи зовнішня - була вибрана на попередньому і-му кроці.

Нехай на і-му кроці була вибрана зовнішня точка, тобто виконалася умова di < 0 (мал. 174,6). При цьому значення dt бу­ де обчислене за формулою dt = (х + І) 2 + у2 - R2 - (R2 - (х + І) 2 - - (у - І)2 ). Аналогічно обчислимо відхилення зовнішньої і

внутрішньої точок на (і + 1)-му кроці: di+1 = (х + 2)2 + у2 - R2 - - (R2 - (х + 2)2 - (у - І)2 ). Виконавши нескладні перетворення,

можна виразити значення di+1 через попередньо обчислене зна­ чення dt: di+1 = di + 4х + 6. Як бачимо, отримана рекурентна формула, яка задає залежність для вибору зовнішньої точки на (і + 1)-му кроці від виконання попереднього і-го кроку.

Аналогічно проведемо дослідження для (і + 1)-го кроку в разі, якщо на і-му кроці була вибрана внутрішня точка (мал. 146, в).

Отже, представимо описаний алгоритм Брезенхема для кола у вигляді фрагмента програми:

x:=0;y:=R;d :=3 - 2*R; while х <=у do

begin

{Процедура виведення точок кола з центром у (хс; ус) та кольором с.}

circle_8(x, у, хс, ус, с);

if d< 0 then d:=d + 4*x + 6

else begin d := d + 4 * (x - y) + 10; dec(y) end;

inc(x)

end;

Процедура circle_8, що виводить на екран симетричні точки кола, може мати такий вигляд:

procedure circle_8 (х, у, хс, ус, с: integer); begin

PutPixel(xc + х, ус + у, с); PutPixel(xc + у, ус + х, с); PutPixel(xc - х, ус + у, с); PutPixel(xc - у, ус + х, с); PutPixel(xc + х, ус - у, с); PutPixel(xc + у, ус - х, с); PutPixel(xc - х, ус - у, с); PutPixel(xc - у, ус - х, с); end;

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

Визначення невидимих точок поверхні

Загальний підхід до розв'язання проблеми та основні поняття

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

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

308

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

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

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

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

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

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

Усі існуючі алгоритми визначення невидимих точок поверх­ ні можна поділити на два класи:

309

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

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

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

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

Метод плаваючого горизонту

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

Отже, нехай задана поверхня рівнянням F(x, у, z) = 0. Для більш зручної роботи алгоритму представимо графік цієї по­ верхні у вигляді функції від двох змінних z = f(x, у).

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

Надалі вважатимемо, що об'єкт - це деяка поверхня, яка описується рівнянням z = f(x, у). Навіть якщо цей об'єкт має складну структуру, то вважатимемо, що він розбитий на окремі фрагменти, які представляють собою поверхні.

Розберемося, яким чином розташована поверхня, за якою ведеться спостереження, і площина, на яку проектується її тривимірне зображення. Для представлення поверхні існує декартова система координат у просторі, де поверхня задана рівнянням z = f(x, у). Площина, на яку проектується зображен-

310

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

ся з перпендикуляром до картинної площини, необхідно задати два кути (р і ці. Кут ц/ утворюється між вектором нормалі і пло­ щиною хОу, а кут ф знаходиться між проекцією нормалі на пло­ щину хОу і віссю Оу (мал. 175). Враховуючи такі позначення, визначимо вектор, що задає напрям проектування:

Для того щоб виконати проектування поверхні на картинну площину, вісь г' нової системи координат x'y'z' повинна збіга­ тися з напрямом проектування (мал. 175).

Розглянемо перетворення системи координат хуг у систему x'y'z'. Це перетворення можна виконати за два кроки.

1. Перший поворот системи координат треба виконати відносно осі Ог на кут ф у напрямі від Оу до Ох (від'ємний на­ прям). Оскільки система координат хуг лівостороння, то цей поворот представляється таким записом:

совф -віпф 0

Д;(Ф)= ЗІПф СОвф 0

00

2.Другий поворот одержаної системи координат виконуєть ся відносно осі абсцис на кут — — v(/ | у напрямі від Ог до Оу.

Запис, що відповідає такому повороту, виглядає так:

311