Материал: 252_337

Враховуючи обидва кроки, пояснення об'єднання яких ви­ ходить за межі даного посібника, загальне перетворення систе­ ми координат xyz у систему x'y'z' задається таким записом:

Це означає, що точка (х; у; z) із заданої поверхні переходить у точку (х'; у') на картинній площині, де

х' = х coscp + у snup, у' = -х sincp sin\|/ + у coscp simp + z cosy. Можна визначити і зворотне перетворення, яке описується

такими співвідношеннями:

х = х' coscp - у' sincp sinij/ + z' cos\|/ sincp; у = x' sincp + y' sinv|/ coscp - z' cosy coscp; z = y' cosi|/ + z' siny.

Останнє представлення значень x, у, z через x'y'z' дає змо­ гу виконати заміну змінних і отримати рівняння поверхні F(x', у', z') = 0 у новій системі координат x'y'z', в якій уже на­ прям проектування паралельний осі Oz' і проектування ведеть­ ся на площину х'Оу'. Надалі координати х', у', z' будемо позна­ чати через х, у, z. Отримане перетворене рівняння поверхні можна представити у вигляді z = f(x, у).

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

Тепер перейдемо на мову математики. Розглянемо побудову графіків функцій, що відповідають сталим значенням z. Це оз­ начає, що для кожного z, що змінюється у циклі від zx до z2 (zt < z2), перебираються значення х із деякого діапазону і таким чином підраховуються точки (х; у; z), що лежать на поверхні.

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

Зведемо тривимірну задачу до двовимірної: вся задана по­ верхня може бути представлена у вигляді послідовності ліній

312

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

Визначимо поетапне виконання алгоритму плаваючого го­ ризонту.

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

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

Розглянемо область екрана між верхньою та нижньою лінією горизонту - вона є проекцією частини графіка функції

у = f(x, z) у смузі z1<z < z2. Для інших ліній у = f(x, z) при і > 2

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

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

313

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

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

Пояснимо математично основні моменти, на яких базується описаний алгоритм. Нехай проекцією лінії у = f(x, zt) на кар­ тинну площину є лінія у = yt(x), де (х; у) - координати точки на картинній площині. Тоді контурні лінії у™"* (х) і у™п (х) визнача­ ються такими співвідношеннями:

уГх(х)=тахуі(х), у™п(х)= тіп Уі(х).

На екран виводяться тільки ті частини лінії у = yh{x), які знаходяться вище від лінії у™ах(х) або нижче від лінії у™т(х).

Є різні способи представлення ліній горизонту, але однією з найпростіших і найефективніших реалізацій цього методу є ре­ алізація, при якій кожна лінія горизонту задається набором значень з кроком 1 піксель, тобто для кожного цілого значення змінної х (хтіп < х < хтах) обчислюються відповідні значення

уГ(х)іуГ(х).

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

Для зручнішого оперування значеннями ліній горизонту введемо масиви h_max[x] та h_min[x], елементами яких будуть відповідно поточні максимальне та мінімальне значення для кожного х.

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

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

коефіцієнта k = — -. Якщо воно менше від 1, то із збільшенням

2 _ * 1

314

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

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

Можна запропонувати такий варіант основної частини про­ грами:

then begin PutPixel(x, у, d ) ; h_min[x] := у end

{якщо значення ординати поточної точки більше від лінії} else if у > h_max[x] {верхнього горизонту, ТО}

{виведення точки і перевизначення значення лінії верхнього горизонту.}

then begin PutPixel(x, у, с2); h max[x] := у end;

end;

end;

315

Для вертикального розташування точок процедура може бу­ ти такою:

procedure k_more_1; begin

if U О х {Перевизначення значення лінії верхнього горизонту.} then

begin

if sy > 0 then h_max[xO] := yO else h_max[x] := y; xO:=u;yO:=v

end; end

else if u <> x then begin xO u; yO := vend x := u; у := v

end;

end;

Варто звернути увагу на деякі недоліки описаного методу плаваючого горизонту.

1.Може статися так, що при деякому значенні х значення у(х) невідоме. У такому разі можна запропонувати взяти у якості цього значення середнє між двома сусідніми значеннями.

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

316