Методи й алгоритми комп'ютерної графіки

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

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

Перенос точки з положення в нове положення можна виконувати по формулах типу

де — приріст по координаті . Однак зручніше операції перетворення представляти в єдиній матричній формі

(4.1)

де — перетворююча матриця. При цьому крапки й у двовимірному випадку зображують векторами-рядками 1×3, у яких крім значень двох координат, що мають назву при такім поданні однорідними, додатково вказують масштабний множник . Тоді перенос для випадку 2D можна виразити у вигляді (4.1), де є Табл. 4, а .

Таблиця 4

Для операцій масштабування й повороту матриці представлені в табл. 5 і табл. 6 відповідно, де , — масштабні множники, — кут повороту.

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

де , — матриця переміщення, — матриця повороту.

Таблиця 5

 

Таблиця 6

 

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

1.

2.

3. якщо , то інакше

4.

5. перехід до пункту 3, поки не досягнута точка .

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

Виділення вікна потрібно при визначенні тієї частини сцени, що повинна бути виведена на екран дисплея.

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

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

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

3. якщо й , то вершина залишається в списку вершин, а вершина з аміняється новою вершиною з координатами в нашому прикладі такою новою вершиною буде ;

4. якщо й , то вершина заміняється новою вершиною з координатами а вершина залишається в списку вершин; у нашому прикладі новою вершиною буде .

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

Рис. 4. Виділення вікна

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

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

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

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

аналогічно розраховується координата точки .

Рис. 5. Побудова центральної проекції точки A

 

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

Моделювання ефектів відбиття світла від поверхні об'єкта в геометричних моделях називають рендерінгом. Зафарбування матових поверхонь засновані на законі Ламберта, відповідно до якого яскравість відбитого від поверхні світла пропорційні , де — кут між нормаллю до поверхні й напрямком луча падаючого світла. В алгоритмі Гуро яскравість внутрішніх точок розглянутої поверхні визначається лінійною інтерполяцією яскравості у вершинах багатокутника. При цьому спочатку проводиться інтерполяція в крапках ребер, а потім по рядках горизонтального розгорнення. Більш реалістичними виходять зображення в алгоритмі Фонга, заснованому на лінійній інтерполяції векторів нормалей до поверхні. Один з алгоритмів рендерінгу полягає в трасуванні променів — моделюванні проходження променів світла між джерелами, поверхнями й спостерігачем.