Комп'ютерна графіка

Комп'ютерна графіка 24.07.2015 10:23

Міністерство освіти і науки України
Український державний університет водного господарства і природокористування
Кафедра прикладної математики

 

100-66

 

П.В.Ольшанський
Комп'ютерна графіка

 

 

Рекомендовано до друку методичною комісією
факультету комп’ютерних інтегрованих систем
та прикладної математики як конспект лекцій для студентів спеціальностей “Прикладна математика”, “Автоматизація управління виробничими процесами” заочної форми навчання
Протокол № 9 від 26 квітня 2004 р.

 

 

Рівне, 2004

Комп’ютерна графіка. Конспект лекцій для студентів спеціальностей „Прикладна математика”, “Автоматизоване управління технологічними процесами” заочної форми навчання. / П. В. Ольшанський, - Рівне: УДУВГП, 2004, - 52 с.
Укладач П. В. Ольшанський, старший викладач кафедри обчислювальної математики.
Відповідальний за випуск А.П. Власюк, доктор технічних наук, професор, завідувач кафедри прикладної математики.

ЗМІСТ
ПЕРЕДМОВА 3
ЕЛЕМЕНТИ АНАЛІТИЧНОЇ ГЕОМЕТРІЇ 4
ПРОЕКТУВАННЯ ТРИВИМІРНИХ ОБ’ЄКТІВ 14
ПЕРЕТВОРЕННЯ, ПОВ’ЯЗАНІ ІЗ СИСТЕМОЮ КООРДИНАТ 19
ДВОВИМІРНІ МАТРИЧНІ ПЕРЕТВОРЕННЯ 20
ОДНОРІДНІ КООРДИНАТИ І МАТРИЧНИЙ ВИГЛЯД ДВОВИМІРНИХ ПЕРЕТВОРЕНЬ 22
ТРИВИМІРНІ МАТРИЧНІ ПЕРЕТВОРЕННЯ 25
ПИТАННЯ ЕФЕКТИВНОСТІ ОБЧИСЛЕНЬ 27
АЛГОРИТМИ РАСТРОВОЇ ГРАФІКИ 28
ПЕРЕТВОРЕННЯ НОРМУВАННЯ ВИДИМОГО ОБ’ЄМУ 33
АЛГОРИТМИ ВИЛУЧЕННЯ НЕВИДИМИХ РЕБЕР І ГРАНЕЙ 35
МОДЕЛІ РОЗРАХУНКУ ОСВІТЛЕНОСТІ ГРАНЕЙ ТРИВИМІРНИХ ОБ’ЄКТІВ 38
КУБІЧНІ СПЛАЙНИ 40
ФОРМАТИ ГРАФІЧНИХ ФАЙЛІВ 44
СТИСКАННЯ ЗОБРАЖЕНЬ 46
СПИСОК ЛІТЕРАТУРИ 52

 

 

 

 

 

ПЕРЕДМОВА

Розглянемо коротко історію розвитку комп'ютерної графіки. Точкою відліку вважається 1930 рік, коли в США Володимиром Зворикіним, який працював у компанії “Вестингхаус” (Westinghouse), була винайдена електронно-променева трубка. Це вперше дозволило одержати зображення на екрані без використання механічних рухомих частин. Вона була прообразом сучасних телевізійних кінескопів і комп'ютерних моніторів. Початком ери власне комп'ютерної графіки можна вважати грудень 1951 року, коли в Масачусетському технологічному інституті (МТІ) для системи протиповітряної оборони військово-морського флоту США був розроблений перший дисплей для комп'ютера “Вихор”. Винахідником цього дисплея був інженер із МТІ Джей Форестер.
Одним з батьків-засновників комп'ютерної графіки вважається Айвен Сазерленд (Ivan Sotherland), який у 1962 році все в тому ж МТІ створив програму комп'ютерної графіки з назвою “Блокнот” (Sketchpad). Ця програма могла малювати досить прості фігури (точки, прямі, дуги кіл), могла обертати фігури на екрані. Після цієї програми деякі великі фірми, такі як “Дженерал моторз”, “Дженерал електрик”, приступили до розробок в області комп'ютерної графіки. У 1965 році фірма IBM випустила перший комерційний графічний термінал з назвою IBM-2250. Наприкінці 70-х років для космічних кораблів “Шаттл” з'явилися засновані на комп'ютерній графіці льотні тренажери. У 1982 році на екрани кінотеатрів вийшов фільм “Трон”, у якому вперше використовувалися кадри, синтезовані на комп'ютері. Ще в 1979 році Джордж Лукас, глава фірми “Lucasfilm” і творець серіалу “Зоряні війни”, організував у своїй фірмі відділ, що займався впровадженням останніх досягнень комп'ютерної графіки в кіновиробництво.
Існують фірми, що спеціалізуються на розробці комп'ютерів для графічних програм, такі як “Silicon Graphics”, “Evans&Sotherland”. Області використання комп'ютерної графіки в наш час дуже широкі. У промисловості використовується комп'ютерне моделювання процесів із графічним відображенням на екрані. Розробка нових автомобілів проходить на комп'ютері від стадії первинних ескізів зовнішнього вигляду корпуса автомобіля до аналізу поведінки деталей автомобіля в різних дорожніх умовах. У медицині застосовуються комп'ютерні томографи, які дозволяють заглянути всередину тіла і поставити правильний діагноз. В архітектурі широко застосовуються системи автоматизованого проектування (CAD – Computer Aided Design) які дозволяють розробити повністю проект будинку, використовуючи методи комп'ютерної графіки. Хіміки вивчають складні молекули білків, користуючись засобами комп'ютерного відображення даних. У телебаченні і кінематографії комп'ютерна графіка стала повсякденним явищем. У світі регулярно проводяться виставки, наприклад, такі як SIGGRAPH, картин, намальованих за допомогою комп'ютера. У математиці розвиток теорії фракталів був би неможливий без комп'ютерів з відповідними засобами графічного відображення даних. Засоби мультимедіа привели до появи нових джерел інформації, які об'єднують у собі статичні і відеозображення, текст і звук. Новітні операційні системи працюють в графічному режимі і реалізують у своїх функціях методи комп'ютерної графіки.

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

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

Рис.2. Лівостороння і правостороння системи координат.

Вісь при цьому може проходити як у напрямку від спостерігача в площину сторінки, так і від площини сторінки до спостерігача. У першому випадку система координат буде називатися лівою чи лівосторонньою, а в другому випадку – правою чи правосторонньою. Більш точно визначити праву і ліву систему координат можна так. Якщо подивитися з позитивної півосі в напрямку початку координат, то для співпадіння додатньої півосі з додатньою піввіссю необхідно повернути відносно початку координат проти годинникової стрілки – в цьому випадку маємо праву систему координат; якщо ж поворот відбувається за годинниковою стрілкою – те система координат ліва*. Існує також легкий спосіб визначення виду системи координат за правою чи лівою рукою, як показано на рис. 3. Для лівої руки великий, вказівний і середній пальці утворюють ліву трійку ортогональних векторів. Те ж відноситься і до їхніх циклічних перестановок.

Рис. 3. Визначення лівосторонньої системи координат за лівою рукою.
Декартові координати точок дозволяють описувати статичне положення об'єктів у просторі. Однак для проведення яких-небудь дій над об'єктами необхідно мати додаткові математичні конструкції. Як одну з таких конструкцій застосовують радіус-вектори. Радіус-вектори мають всі властивості векторів, але мають одну особливість: початок радіус-вектора знаходиться завжди в початку координат, а кінець радіус-вектора лежить в даній точці простору. Ця властивість радіус-векторів дозволяє поставити у взаємно однозначну відповідність всім точкам простору відповідні їм радіус-вектори. Формально цю відповідність запишемо так. Нехай точка має координати , тобто , і – радіус-вектор, кінець якого знаходиться в точці , де – трійка одиничних базисних векторів, чи просто нормований базис. Тоді точці взаємно однозначно відповідає радіус-вектор , чи . Таким чином, можна легко переходити від координат точок до радіус-векторів і навпаки. Далі ми побачимо, що представлення радіус-вектора у вигляді лінійної комбінації векторів базису має цілком конкретне практичне застосування. Відзначимо, що радіус-вектор іноді визначають як перетворення перенесення точки з початку координат у задану точку простору з відомими координатами. При цьому множення радіус-вектора на число означає перенесення точки з початку координат у напрямку вектора на відстань , де прямі дужки означають операцію взяття модуля вектора:

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

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

Попарно розділивши ці рівняння одне на інше для того, щоб позбутися від коефіцієнта , одержуємо таку систему рівнянь, що визначає нашу пряму в тривимірному просторі:
(2)
У практичних задачах іноді буває потрібно визначити чи лежить деяка точка, що належить прямій, всередині відрізка, заданого координатами своїх кінців на даній прямій, чи зовні. Для розв’язування цієї задачі перепишемо рівняння (1) в такому вигляді:
(3)
При одержуємо точки прямої, що лежать між і . При – точки, що лежать на прямій за , при – точки, що лежать на прямій за . Для перевірки цього можна просто підставити в рівняння замість значення 0 і 1.
Перейдемо тепер до виведення рівняння площини. Ми зможемо одержати його трьома шляхами. Але спочатку нагадаємо визначення скалярного добутку. Для двох радіусів-векторів і скалярним добутком називається число , де - кут між векторами і . Для векторів запис виду чи також буде позначати скалярний добуток. Скалярний добуток можна виразити через координати векторів:
,
тому що при розкритті дужок скалярні добутки перпендикулярних векторів базису за визначенням перетворюється в нуль.
Використаємо властивості скалярного добутку для виведення рівняння площини. Розглянемо деяку площину в просторі і деякій точці , про яку ми знаємо, що вона лежить у цій площині, як показано на малюнку 5.

Рис. 5. Виведення рівняння площини в тривимірному просторі.

Візьмемо також деякий радіус-вектор , перпендикулярний до нашої площини. Цей вектор назвемо нормаллю до площини. Нехай тепер потрібно визначити, чи належить деяка точка (чи радіус-вектор) площині чи ні. Для цього відзначимо, що для будь-якої точки , що належить площині, вектор і радіус-вектор нормалі – перпендикулярні. А це значить, що їхній скалярний добуток дорівнює нулю:
(4)
Так ми одержали рівняння площини. Розкриємо дужки і запишемо його в більш зручному виді: , де константа . Якщо , а , то в координатному записі наше рівняння площини запишеться у вигляді
(5)
Відомо, що площина може бути задана трьома точками, які не лежать на одній прямій, тобто якщо вони не колінеарні. Одержимо рівняння площини для трьох заданих точок. Для цього розглянемо визначення векторного добутку. Результатом векторного добутку двох векторів є вектор , модуль якого дорівнює , і спрямований він перпендикулярно до площини, в якій лежать вектори і , причому вектори – утворять праву трійку векторів (див. визначення правої системи координат), тут також кут між векторами і . Для векторів одиничного базису, що утворюють праву трійку, як випливає з визначення: , , . Векторний добуток також підкоряється дистрибутивному закону як і скалярний добуток. Однак векторний добуток не комутативний, а саме, якщо для векторів , то , що також прямо випливає з визначення. Координати векторного добутку легко одержати, розклавши вектори-співмножники, за базисом, а потім розкривши дужки, як це вже було пророблено для скалярного добутку. Є й інший, неформальний, спосіб одержання, координат векторного добутку, за допомогою розкладання такого визначника за його першим рядком. Якщо і , тоді

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

Рис. 6. Виведення рівняння площини, що проходить через три точки.

Результат векторного добутку будь-яких двох неколінеарних векторів, перпендикулярних до нашої площини, буде вектором, перпендикулярним до площини. І саме такими є вектори різниці і . Виберемо їхній векторний добуток як вектор нормалі, тобто . Тоді, якщо – довільний радіус-вектор, що належить площині, то шуканим рівнянням площини буде, аналогічно формулі (4):
,
причому в останніх дужках замість вектора можна було використовувати, наприклад, вектори чи . Не будемо далі розписувати це рівняння через координати, тому що це легко зробити самостійно.
Розглянемо ще кілька визначень і типових задач.
Іноді буває необхідно обчислити довжину проекції радіус-вектора не на вісь системи координат, а на інший радіус-вектор. Знайдемо довжину проекції вектора на вектор . Ця ситуація зображена на рис.7, з якого випливає і розв’язок задачі.

Рис. 7. Проекція вектора на вектор .
Шукана довжина проекції: = = .
Як видно, якщо довжина вектора, на який проектується інший вектор, дорівнює одиниці, то довжина проекції буде просто дорівнювати скалярному добутку цих векторів.
За допомогою формули довжини проекції вектора на вектор можна ще одним способом одержати рівняння площини, якщо помітити, що довжини проекцій радіус-векторів, що належать площині, на вектор нормалі до площини завжди рівні між собою.
Розв’яжемо задачу знаходження мінімальної відстані від початку координат до площини. Очевидно, що цю відстань необхідно відкладати вздовж прямої, обумовленої вектором нормалі до площини. Але для знаходження цієї відстані треба знайти спочатку точку перетину прямої з площиною. Тому вирішимо в загальному виді задачу знаходження точки перетину прямої і площини. Нехай шукана точка, чи відповідний радіус-вектор називається x. Тоді ця точка повинна одночасно задовольняти рівнянням прямої і площини, наприклад, і . Підставивши x з першого рівняння в друге, знайдемо значення константи , яку потім підставимо у вихідне рівняння прямої для одержання координат шуканої точки:

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

Звідси шукана відстань від початку координат до площини дорівнює

Якщо вектор нормалі є нормованим, константа в рівнянні площини дорівнює відстані від початку координат до даної площини.
Крім визначення положення точок у просторі радіус-вектори також визначають деякий напрямок у просторі. Напрямок, обумовлений радіус-вектором, зручно описувати за допомогою так званих направляючих косинусів. Нехай радіус-вектор складає з осями координат , і кути, відповідно, і (малюнок 8). Тоді його направляючими косинусами будуть:
, ,

Рис. 8. Направляючі косинуси.
Звідси такі властивості направляючих косинусів:
.
Направляючі косинуси пропорційні відповідним координатам:
,
а у випадку, коли вектор нормований, значення його координат рівні відповідним направляючим косинусам.
Розглянемо однорідне рівняння площини. Для цього в рівнянні (5) перенесемо константу з правої частини в ліву і запишемо функцію трьох змінних . Якщо підставити координати точки, що належить даній площині, в це рівняння, то . Якщо ж точка не належить площині, то значення функції, буде більше чи менше нуля. Цікавий той факт, що для всіх точок простору, які знаходяться з однієї сторони від площини, функція одного знаку. За допомогою рис. 9 , легко показати, що для точок півпростору з тієї сторони від площини, де розміщений початок координат, функція негативна, а для точок протилежного півпростору, як, наприклад, для точки на малюнку, вона додатня. У загальному ж випадку необхідно враховувати напрям вектора нормалі.

Рис. 9. Однорідне рівняння площини.
Властивість збереження знака функції зручно використовувати в алгоритмах вилучення невидимих ребер і граней для визначення розташування точок з однієї сторони від плоскої грані. Для цього досить підставити значення координат точок у функцію для відповідної грані і перевірити знаки функції. Аналогічні міркування можна повторити і для більш простого випадку прямої на площині. Для будь-якої точки на площині можна визначити її знаходження в одній з напівплощин, на які пряма ділить площину. Ця властивість використовується також в наступному прикладі.
Розглянемо три методи розв’язування класичної задачі визначення належності точки до внутрішньої чи граничної області трикутника. Нехай на площині задані три точки і , що утворюють трикутник (рис. 10).

Рис. 10. Внутрішня область трикутника відповідає
від’ємним напрямам векторів нормалей.
Користуючись вектором нормалі можна записати рівняння прямої на площині: . Ідея першого методу полягає в тому, щоб записати однорідні рівняння сторін трикутника таким чином, щоб внутрішня область трикутника відповідала від’ємним значенням функції . Тоді умовою належності точки до внутрішньої області трикутника будуть від’ємні значення трьох функцій. Основною проблемою в цьому методі є правильний вибір напрямку вектора нормалі до прямої.
Наступний метод заснований на перетворенні трикутника за допомогою операції переносу в такий спосіб, щоб точка, яка перевіряється, співпала з початком координат. Поворотом площини навколо початку координат розташуємо одну з вершин трикутника на осі . Якщо знаки координат двох точок, що залишилися, збігаються, то шукана точка лежить поза трикутником. Якщо ж знаки різні, то беремо наступну з вершин трикутника, що залишилися, і поворотом площини встановлюємо її на вісь . Після чого знову перевіряємо знаки координат двох інших вершин, і т.д.

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

Рис. 12.Точка всередині трикутника.
Знаходження точки на одній зі сторін трикутника визначається за розбіжністю знаків -координат двох вершин, які після одного з поворотів будуть лежати на осі . Цей метод ефективний у випадках, коли більш імовірно, що точка лежить поза трикутником. Недоліком є необхідність обчислення синусів і косинусів кутів при поворотах системи координат.
Третій з методів є найбільш компактним і швидким з обчислювальної точки зору. Дуже просто можна визначити належність точки до внутрішньої області трикутника – одиничного симплекса, тобто трикутника, утвореного точками з координатами , , . Для цього досить, щоб координати шуканої точки лежали у відрізку , і виконувалась умова , де і координати точки. Нагадаємо також, що за допомогою базисних (афінних) перетворень координат будь-який трикутник можна деформувати в одиничний симплекс.

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

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

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

Рис. 14. Центральна проекція. Рис. 15. Паралельна проекція.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 17. Види проекцій.

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

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

Рис. 19. Виведення формул центральної перспективної проекції.

Точка проектується на екран як . Відстань від спостерігача до проекційної площини дорівнює k. Необхідно визначити координати точки на екрані. Позначимо їх і . З подібності трикутників і знаходимо
(1)
аналогічно для x: .
Нагадаємо, що k -це відстань, а спостерігач знаходиться в точці .
Якщо точку спостереження помістити в початок координат, а проекційну площину на відстань , як показано на малюнку 20, то формули для і набудуть вигляду:
, (2)

Рис. 20. Інший спосіб обчислення координат точок
у центральній перспективній проекції.
Формули (1) більш зручні при необхідності простим способом наближати чи віддаляти спостерігача до чи від проекційної площини. Формули (2) вимагають менше обчислень за рахунок відсутності операції додавання.
Розглянемо далі деякі фактори. що впливають на сприйняття людиною тривимірності. Одним із простих способів представлення тривимірних об'єктів є так звані дротяні (wired) чи каркасні зображення. Криві лінії при цьому апроксимуються відрізками прямих. Це найбільш швидкий і простий спосіб побудови і виведення зображення.
Для посилення ефекту тривимірної глибини в дротяних зображеннях об'єктів виллучають невидимі лінії. Лінії їхньої частини, закритої лицьовими поверхнями об'єкта, не зображуються. Для цього застосовується спеціальні алгоритми, які вимагають значних обчислень. Передача глибини може здійснюватися зміною рівня яскравості. Об'єкти, що знаходяться ближче до джерела світла, зображуються яскравіше, ніж ті, котрі розташовані далі від нього. Рух об'єктів також дає додатковий ефект глибини. Наприклад, обертання об'єктів навколо вертикальної осі дозволяє відрізнити точки, що знаходяться на різній відстані від осі за рахунок розходження лінійної швидкості обертання точок. Це так званий кінетичний чи динамічний ефект глибини.
Більш тонко тривимірність об'єктів може бути представлена за рахунок відмінностей відбивних властивостей поверхонь, їхнього рельєфу і текстури, а також розрахунку тіней, що відкидаються поверхнями об'єкта. Одним з найбільш ефективних способів досягнення ефекту тривимірності є стереоскопія. При цьому окремо для правого і лівого ока спостерігача формуються зображення, що незначно відрізняються, подібно тому, як це відбувається в реальності. Це викликає так званий бінокулярний ефект. Він полягає в тому, що наш мозок зливає два окремих образи в один, який сприймається свідомістю як тривимірний. Ці два роздільних зображення називаються стереопарою.

Рис. 21. Бінокулярний ефект, стереоскопія.

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

Перетворення, позв'язані із системою координат
Необхідно навчитися керувати зображенням на екрані, вносити зміни в його положення, форму, орієнтацію, розмір. Для цього існують спеціальні геометричні перетворення, що дозволяють змінювати ці характеристики об'єктів у просторі. Уявимо задачу створення комп'ютерного імітатора польотів на військовому літаку. Об'єкти на землі, як і сам літак, змінюють своє положення: обертається антена локатора, рухається танк. При цьому, спостерігач бачить цю картину з визначеної точки в просторі в обраному напрямку. Необхідно описати ці складні перетворення математично.
Введемо три види систем координат. Перша з них – світова система координат – задається осями . Ми розміщаємо її в деякій точці, і вона залишається нерухомою завжди. Друга – система координат спостерігача. Цю систему назвемо . Вона визначає положення спостерігача в просторі і задає напрямок погляду. І третя – система координат об'єкта. У нашому випадку їх дві: системи координат локатора і система координат танка. Ці системи також можуть переміщуватися і змінювати своє положення в просторі щодо світової системи координат. Координати точок об'єктів задаються в системах координат об'єктів, кожна з яких, у свою чергу, прив'язана до світової системи координат. Система координат спостерігача також переміщається віносно світової системи координат. Тепер стає зрозуміло, щоб побачити тривимірний об'єкт на екрані комп'ютера, потрібно виконати наступні кроки.
1. Перетворити координати об'єкта, задані у власній системі координат, у світові координати.
2. Перетворити координати об'єкта, задані у світовій системі координат, у систему координат спостерігача.
3. Спроектувати отримані координати на проекційну площину в системі координат спостерігача.
Відзначимо, визначену подвійність вражень, що виникають при взаємних переміщеннях систем координат одна відносно іншої. Уявимо собі, що ми спостерігаємо об’єкт у просторі. Нехай тепер цей об’єкт почне обертатися навколо вертикальної осі. Ми побачимо, що він обертається. Але той же самий візуальний ефект ми одержимо, якщо самі почнемо облітати навколо і розглядати об’єкт з різних сторін. Візуальний ефект залишається тим же самим, хоча в першому випадку наша система координат залишається нерухомою, а в другому – обертається по орбіті. Цей ефект можна використовувати для виведення формул руху в просторі.

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


Рис. 22. Операція перенесення чи трансляції точки в точку .

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

Рис. 23. Операція маштабування.

Після застосування операції однорідного маштабування з коефіцієнтом 2 він переходить у трикутник . Позначимо матрицю маштабування . Для точок і операція маштабування в матричному вигляді виглядає так:
.
Розглянемо далі операцію обертання чи повороту точки на деякий кут відносно початку координат. На малюнку 24 точка переходить у точку поворотом на кут .

Рис. 24. Операція повороту точки на кут .

Знайдемо перетворення координат точки А в точку В. Позначимо кут, який утворює радіус-вектор з віссю Оx. Нехай r – довжина радіус-вектора , тоді


Тому що і , то підставляючи ці вирази в рівняння для і , одержуємо:


У матричному виді поворот точки А на кут виглядає так:

Однорідні координати і матричне представлення двовимірних перетворень
У попередньому параграфі були розглянуті три види перетворень точок на площині. Два з них – повороту і маштабування - описуються як добуток матриці на вектор, а третій – перенесення – описується як сума двох векторів. У випадку послідовного виконання будь-якої комбінації операцій обертання і маштабування результат легко можна записати у виді добутку матриць відповідних перетворень. Це буде матриця результуючого повороту і маштабування. Очевидно, що зручніше застосовувати результуючу матрицю замість того, щоб щораз заново обчислювати добуток матриць. Однак, таким способом не можна одержати результуючу матрицю перетворення, якщо серед послідовності перетворень присутнє хоча б одне перенесення. Було б зручніше мати математичний апарат, який дозволяв би описувати всі базисні перетворення з допомогою матричного добутку. Введення однорідних координат дає таку можливість.
Двовимірний вектор в однорідних координатах записується у вигляді , де . Число називається маштабуючим множником. Для того, щоб з вектора, записаного в однорідних координатах, одержати вектор у звичайних координатах необхідно розділити перші дві координати на третю: .
Розглянемо деякі властивості однорідних координат. Деякі точки, невизначені в n-мірному просторі, стають цілком визначеними при переході до однорідних координат. Наприклад, однорідний вектор у тривимірному просторі відповідає нескінченно віддаленій точці . Оскільки в однорідних координатах цю точку можна представити у вигляді , при , то в тривимірному просторі це відповідає точці .
Розглянемо точку тривимірного простору . Якщо представити цю точку як однорідне представлення точки двовимірного простору, то її координати будуть . Порівнюючи ці координати з іншим видом формул, виведених для центральної перспективної проекції, легко помітити, що двовимірне представлення точки з координатами виглядає як її проекція на площину , як показано на рис. 25.
Аналогічно, розглядаючи застосування однорідних координат для векторів тривимірного простору, можна представити тривимірний простір як проекцію чотиривимірного простору на гіперплощину , якщо .

Рис. 25. Проекція точки на площину .
В однорідних координатах перетворення центральної перспективи можна визначити матричною операцією. Ця матриця записується у вигляді:

Покажемо, що ця матриця визначає перетворення точки об'єкта, заданої в однорідних координатах, у точку перспективної проекції (також в однорідних координатах). Нехай – точка в тривимірному просторі. Її однорідне представлення . Помножимо v на P:

це точно повторює формули (1), виведені для центральної перспективи.
Тепер точки двовимірного простору будуть описуватися триелементними векторами-рядками, тому і матриці перетворень, які будуть змінювати вектор точки, мають розміри 33. Запишемо матричне перетворення операції перенесення для однорідних координат:

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

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

Для перетворення повороту матрична форма буде такою:

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

Отже, два, а значить і будь-яку кількість послідовних поворотів можна записати у вигляді однієї матриці сумарного повороту.
Тепер можна узагальнити. Будь-яка послідовність операцій, що включає в себе перенесення, маштабування та поворот в однорідних координатах, представляється однією матрицею, що є добутком матриць базисних елементарних перетворень.
Розглянемо детальніше, як за допомогою композиції матричних перетворень можна одержати одне загальне результуюче перетворення. Для цього будемо використовувати матриці T, S і R. З обчислювальної точки зору набагато простіше і швидше застосовувати матрицю результуючого перетворення замість того, щоб застосовувати їх послідовно одну за другою.
Для прикладу розглянемо задачу повороту об'єкта на площині відносно деякої довільної точки . Поки що ми навчились повертати об'єкти тільки навколо початку координат. Але можна представити цю задачу як послідовність кроків, на кожному з яких буде застосовуватися тільки елементарне перетворення: перенесення, маштабування чи поворот.
Послідовність елементарних перетворень для повороту навколо (рис. 26):
1. Перенесення точки у початок координат. 2.Поворот на заданий кут.
3. Перенесення, при якому точка з початку координат повертається в первісне положення .

Рис. 26. Послідовність перетворень при повороті об'єкта навколо точки на кут .
Точка . Перше перенесення відбувається на вектор , а протилежне на вектор .

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


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

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

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


Найчастіше для прискорення операції повороту є відмова від обчислення синуса і косинуса кута під час виконання програми, а використання їх заздалегідь підрахованих значень у вигляді таблиці. В цій таблиці досить зберігати значення синусів і косинусів кутів повороту з кроком у 1 градус. Тоді ціла кількість градусів кута повороту може служити як індекс при одержання відповідних значень синусів і косинусів з таблиці. Такий прийом називається табличним поворотом.
Додатковим способом прискорення операції повороту є зменшення кількості операцій множення. Розглянемо виведення формули О. Б’юнемана з використанням тангенса половинного кута, у якій поворот точки навколо початку координат виконується трьома операціями множення і трьома операціями додавання. Оскільки більшість мікропроцесорів операції множення виконують довше ніж операції додавання, то економія часу досягається за рахунок зменшення операцій множення.
Формулу одержуємо з геометричної побудови на рис.27.

Рис. 27. Виведення формули О. Б’юнемана.

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

Останні три рівності називають формулою Б’юнемана.

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

Рис. 28. Растеризація відрізка прямої лінії.

Термін “піксель” утворений від англійського pixel (picture element - елемент зображення) - тобто точка на екрані. Будемо вважати, що пікселі мають цілочисельні координати. Нехай кінцеві точки відрізка мають цілочисельні координати, і рівняння прямої, що відповідає відрізку: . Для спрощення міркувань будемо також вважати, що тангенс кута нахилу прямої лежить у межах від 0 до 1. Тоді для зображення відрізка на растрі досить для всіх цілих , що належать відрізку, виводити на екран точки з координатами . Однак у цьому методі присутня операція множення . Бажано мати алгоритм без використання порівняно громіздкої операції множення дійсних чисел. Позбутися від операції множення можна в такий спосіб. Оскільки , а один крок по осі , то буде збільшуватися на величину . Ітераційна послідовність виглядає так:
,
Коли , то крок по буде приводити до кроку по , тому і потрібно поміняти місцями. Надаючи одиничне збільшення, будемо збільшувати на одиниць. Для реалізації даного алгоритму все-таки потрібно виконувати операції з дійсними числами з плаваючою комою. Найбільш раціональний варіант алгоритму для растрового розгорнення відрізків прямих був запропонований Брезенхемом. В цьому алгоритмі взагалі не використовуються операції з дійсними числами, не використовуються операції множення і ділення, а переважно реалізовані в елементарних наборах мікропроцесорних команд операції інкременту та декременту.

Рис. 29. Малювання відрізків прямих за методом Брезенхема.
Нехай початок відрізка має координати , а кінець . Позначимо , . Не порушуючи спільності, будемо вважати, що початок відрізка збігається з початком координат, і пряма має вид , де . Вважаємо, що початкова точка знаходиться зліва. Нехай на -му кроці поточною точкою відрізка є . Вибір наступної точки чи залежить від знака різниці . Якщо , то і тоді , , якщо ж , то і тоді , .
, ,

.
Оскільки знак збігається зі знаком різниці , то будемо перевіряти знак виразу . Тому що і , то .
Нехай на попередньому кроці , тоді і . Якщо ж на попередньому кроці , то і .
Залишилося обчислити . Тому що при :
, .
Далі наводиться процедура мовою Паскаль, що реалізує алгоритм Брезенхема.
Procedure Bresenham(x1,y1,x2,y2,Color: integer);
var dx,dy,incr1,incr2,d,x,y,xend: integer;
begin dx:= ABS(x2-x1); dy:= Abs(y2-y1);
d:=2*dy-dx; {початкове значення для d}
incr1:=2*dy; {збільшення для d<0}
incr2:=2*(dy-dx); {збільшення для d>=0}
if x1>x2 then {починаємо з точки з меншим знач. x}
begin x:=x2; y:=y2; xend:=x1 end
else begin x:=x1; y:=y1; xend:=x2 ;end;
PutPixel(x,y,Color); {перша точка відрізка}
While x<xend do
begin
x:=x+1;
if d<0 then d:=d+incr1{вибираємо нижню точку}
else{вибираємо верхню точку,y-зростає}
begin y:=y+1;d:=d+incr2 end;
PutPixel(x,y,Color);
end;{while}
end;{procedure}
Розглянемо проблему, що неявно входить складовою частиною до більшості задач комп'ютерної графіки. Ця проблема відсікання зображення по деякій границі, наприклад, по границі екрана, чи, у загальному випадку, деякого прямокутного вікна. Розглянемо цю задачу для відрізків прямих. Деякі з них цілком лежать всередині області екрана, інші цілком поза нею, а деякі перетинають границю екрана. Правильне відображення відрізків означає знаходження точок перетину їх із границею екрана і малювання тільки тих їх частин, що попадають на екран. Один з очевидних способів відсікання відрізків складається у визначенні точок перетину прямої, що містить відрізок, з кожною із чотирьох прямих, на яких лежать границі вікна і перевірки, чи не лежить хоча б одна точка перетину на границі. У цьому випадку для кожної пари бік-відрізок необхідно розв’язати систему з двох рівнянь, використовуючи операції множення і ділення. При цьому зручно використовувати параметричне задання прямих:

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

Розглянемо алгоритм Коэна-Сазерленда для відсікання відрізків прямих. Цей алгоритм дозволяє легко визначати знаходження відрізка цілком всередині чи цілком зовні вікна, і якщо так, то його можна малювати чи не малювати, не піклуючись про відсікання по границі вікна.
Для роботи алгоритму вся площина, в якій лежить вікно, розбивається на дев'ять підобластей чи квадрантів, як показано на рис. 30.

Рис. 30. Розбивання на підобласті в методі Коена-Сазерленда.

Вікну відповідає область, позначена кодом 0000. Кінцевим точкам відрізка приписується 4-бітний код “поза/всередині” у залежності від знаходження відрізка у відповідної підобласті. Кожному біту привласнюється значення 1 у відповідності з наступним правилом.
Біт 1 - точка знаходиться вище вікна; Біт 2 – точка знаходиться нижче вікна;
Біт 3 - точка знаходиться справа від вікна;
Біт 4 - точка знаходиться зліва від вікна;
Інакше біту привласнюється нульове значення. Значення цих бітів для кінцевих точок відрізків легко визначити за знаками відповідних різниць: - для 1-го біта, - для 2-го біта, - для 3-го біта і - для 4-го біта. Відрізок малюється без відсікання, тобто повністю, якщо обидва коди рівні 0000, чи АБО , де АБО – бінарна операція. Відрізок відкидається без обчислень, якщо обидва його кінці знаходяться вище, нижче, правіше чи лівіше вікна. У цих випадках відповідні біти в обох кодах рівні 1 і це легко визначити, перемноживши їх з допомогою бінарної операції І (побітова кон’юнкція) . Якщо результат операції І дорівнює 0000, то відрізок може перетинатися з вікном. У цьому випадку застосовується послідовний поділ відрізка, на кожному кроці кінцева точка відрізка з ненульовим кодом поза/усередині заміняється на точку, що лежить на стороні вікна чи на її продовженні. При цьому порядок перебору сторін вікна не має значення.
Далі наводиться текст процедури мовою Паскаль з реалізацією цього методу. Відрізок, заданий граничними точками , , границі вікна: xmin, xmax, ymin, ymax. Використовуються виклики процедур: Accept_Check – виконує перевірку на повне прийняття відрізка; Reject_Check – на повну відмову від малювання відрізка; Outcodes – обчислює 4-х бітовий код “поза/усередині”; SWAP – обмін місцями координат двох точок.
Procedure CLIP(x1,x2,y1,y2,xmin,xmax,ymin,ymax: real);
type
outcode = array[1..4] of boolean;
var
accept,reject,done: boolean;
outcode1,outcode2,
outcode3,outcode4:outcode;{коди поза/усередині}
begin
accept:= false; reject:= false; done:= false;
repeat
Outcodes(x1,y1,outcode1);Outcodes(x2,y2,outcode2);
{перевірка на відкидання}
reject:=Reject_Check(outcode1,outcode2);
if reject then done:= true
else
begin {можливе прийняття цілком}
accept:=Accept_Check(outcode1,outcode2);
if accept then done:=true
else
begin {розділити відрізок}
{якщо P1 усередині, то за допомогою SWAP зробити зовні}
if not((outcode1[1])or(outcode1[2])or
(outcode1[3])or(outcode1[4])) then SWAP;
{тепер P1 переміщується в точку перетинання}
if outcode1[1] then
begin {відкинути верхню частину}
x1:=x1+(x2-x1)*(ymax-y1)/(y2-y1);y1:=ymax;end
else if outcode1[2] then
if outcode1[1] then
begin {відкинути нижню частину}
x1:=x1+(x2-x1)*(ymin-y1)/(y2-y1);y1:=ymin;end
else if outcode1[3] then
begin {відкинути праву частину}
y1:=x1+(y2-y1)*(ymax-x1)/(x2-x1);x1:=xmax; end
else if outcode1[4] then
begin {відкинути ліву частину}
y1:=x1+(y2-y1)*(ymin-x1)/(x2-x1); x1:=xmin; end;
end;
end;
until done;
if accept then Line(x1,y1,x2,y2);{намалювати відрізок}
end;{procedure}

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

Рис 31. Видимий об’єм, вид збоку.
Однієї з важливих задач комп'ютерної графіки є знаходження ефективного способу відсікання тривимірних об'єктів по границі видимого об’єму і вилучення невидимих ребер і граней. Наприклад, у випадку центральної перспективи, для задачі відсікання довелося б для кожної грані чи ребра знаходити точки перетинання з площинами зрізаної піраміди, що в загальному випадку вимагало б значних обчислень. Розв’язок полягає в перетворенні видимого об’єму до виду, в якому обчислення проводилися б значно простіше. Ідея полягає в тому, щоб звести перетворення центральної перспективи математично до виду паралельної проекції, в якій проектування зводиться до простого відкидання -координати точок.
Будемо розв’язувати задачу в два етапи. Спочатку приведемо видимий об’єм до нормованого виду. При цьому значення , а границі по осях і лежать в діапазоні , як показано на рис. 32.
Нормуючим перетворенням у цьому випадку буде операція маштабування, що для довільної точки виражається у виді:
,

Рис. 32. Нормований видимий об’єм.
де , і відповідно, .
Нормований видимий об’єм дозволяє легко вирішувати задачу відсікання по границі. А саме, у цьому випадку може застосовуватися модифікований варіант алгоритму Коена-Сазерленда, в якому замість 4-бітових використовуються 6-бітові коди поза/всередині для опису знаходження точки у відповідній області простору.

Рис. 33. Канонічний видимий об’єм.

Рівняння бічних граней видимого об’єму спрощуються, наприклад, для правої бічної відтинаючої площини рівняння , а для лівої і т.д. Для точки умови встановлення бітів в одиницю такі:
1-й біт: ; 2-й біт: ; 3-й біт: ;
4-й біт: ; 5-й біт: ; 6-й біт: .
Для ефективного розв’язування задачі вилучення невидимих ребер/граней перетворимо нормований видимий об’єм до канонічного виду, як показано на рис. 33. Це досягається за допомогою матриці
.
Після застосування матриці нормований видимий об’єм стає прямокутним паралелепіпедом, що дозволяє перейти від центральної перспективної до паралельної проекції. Легко перевірити, як показано на рис. 32, 33: , , , , а також, наприклад, .
Отже, нормуючі перетворення видимого об’єму можна проводити за два кроки.
1 крок - перетворення до нормованого видимого об’єму і відсікання з допомогою тривимірного алгоритму Коена-Сазерленда.
2 крок - перетворення до прямокутного паралелепіпеда за допомогою матриці і вилучення невидимих поверхонь за умови рівності координат і .

Алгоритми вилучення невидимих ребер і граней
Алгоритми вилучення невидимих граней діляться на два великі класи в залежності від простору, в якому вони працюють. Перший клас – це алгоритми в тривимірному просторі об'єктів. Для визначення видимості даної грані порівнюється її взаємне розташування з всіма іншими гранями в тривимірній сцені. Нехай N – кількість граней у тривимірній сцені. Для побудови тривимірної сцени в цьому випадку необхідно порівняти положення кожної грані з усіма іншими, що вимагає порядку операцій. Наприклад, кількість граней у тривимірній сцені , тоді час роботи алгоритмів цього класу порядку 1 000 000 операцій.
Інший клас - алгоритми, що працюють у просторі зображення, заснований на знаходженні точки найближчої грані, яку перетинає промінь зору, що проходить через задану точку на растрі. Оскільки число точок на растровому екрані фіксоване, то алгоритми цього класу менш чуттєві до збільшення кількості об'єктів у тривимірній сцені. Нехай n - число точок на растровому екрані. Тоді кількість операцій, необхідних для побудови тривимірної сцени, буде порядку . Наприклад, для екранної роздільної здатності 320 200 точок 64000, тоді кількість операцій для 1000 граней буде порядку 64 000 000. Вибір класу алгоритму може залежати від особливостей конкретної задачі, а також від способів реалізації алгоритму.
Розглянемо алгоритм вилучення невидимих граней з використанням z-буфера, що найбільш часто використовується в пакетах комп'ютерної графіки. Він працює в просторі зображення і застосовується в таких популярних графічних бібліотеках, як OpenGL і Direct3D.
Алгоритм працює в паралельній проекції. Нехай розміри вікна виведення чи екрана складають X точок у ширину і Y точок у висоту. Для z-буфера використовується двовимірний масив розмірністю X Y. У z-буфері будуть зберігатися поточні значення z-координат кожного пікселя.
На початку роботи алгоритму в z-буфер заносяться значення, що відповідають нескінченності. Кожна грань тривимірного об'єкта, представлена у виді многокутника, переводиться в растрову форму. При розкладанні в растр для кожної точки многокутника обчислюється значення її z-координати. Якщо z-координата виявляється меншою, ніж поточне значення в z-буфері, то в z-буфер заноситься z-координата точки, і на екран виводиться точка кольору поточного многокутника. Після растеризації всіх многокутників зображення тривимірної сцени готове.
Розглянемо спосіб прискореного обчислення z-координат при розкладанні многокутників у растр. Запишемо рівняння площини, утвореної многокутником у просторі: .
Виразимо z-координату точки: . Нехай . Знайдемо z-координату для сусідньої точки . Для сусіднього пікселя на екрані , тоді , звідси випливає, що . Таким чином, обчислення z-координати сусіднього пікселя зводиться до однієї операції віднімання.
Розглянемо далі алгоритм вилучення невидимих граней методом сортування за глибиною. Частина цього методу працює в просторі об'єктів, а частина - в просторі зображення.
Просторовою оболонкою тривимірного об'єкта називається мінімальний паралелепіпед, в якому повністю міститься даний об'єкт.
Метод складається з трьох основних кроків:
1. Впорядкування всіх многокутників відповідно до їхніх найбільших z-координат.
2. Усунення всіх невизначеностей, що виникають при перекритті z-оболонок многокутників.
3. Перетворення кожного з многокутників у растрову форму в порядку зменшення їхньої найбільшої z-координати.
Найближчі многокутники перетворюються в растрову форму останніми і закривають більш віддалені многокутники, тому що зображуються понад попередніми. Реалізація пунктів 1 і 3 досить очевидна. Розглянемо докладніше пункт 2.
Нехай многокутник P після впорядкування знаходиться наприкінці списку, тобто є найбільш віддаленим. Усі многокутники Q, чиї оболонки перекриваються з z-оболонкою P повинні проходити перевірку за п'ятьма тестами (кроками). Якщо на деякому кроці отримана позитивна відповідь, то P відразу перетвориться в растрову форму.
П'ять тестів:
1. x-оболонки многокутників не перекриваються, тому самі многокутники теж не перекриваються.
2. y-оболонки многокутників не перекриваються, тому самі многокутники теж не перекриваються.
3. P цілком розташований з тієї сторони від площини Q, що далі від точки зору (цей тест дає ствердну відповідь, як показано на рис. 36а).
4. Q цілком розташований з тієї сторони від площини P, що ближче до точки зору. Цей тест дає ствердну відповідь, як показано на рис. 36b).
5. Проекції многокутників на площині xOy, тобто на екрані, не перекриваються (це визначається порівнянням ребер одного многокутника з ребрами іншого).

Рис. 35. -оболонки трикутників P і Q – перетинаються.

Рис. 36а, 36b.Взаємне розташування трикутників у просторі.

Рис. 37.
Якщо у всіх п'ятьох тестах отримано негативну відповідь, то P – дійсно закриває Q. Тоді обмінюємо P і Q у списку місцями. У випадку, показаному на рис. 37, алгоритм зациклюється.
Для запобігання зациклення вводиться обмеження: многокутник, переміщений у кінець списку (тобто позначений), не може бути повторно переміщений. Замість цього многокутник P чи Q розділяється площиною іншого на два нових многокутники. Ці два нових многокутники включаються у відповідні місця впорядкованого списку, і алгоритм продовжує роботу.
На відміну від універсальних алгоритмів вузькоспеціалізований алгоритм вилучення невидимих граней опуклих тіл дозволяє виконувати обчислення набагато швидше. Він працює для центральної перспективної проекції. Розглянемо роботу цього алгоритму на прикладі, показаному на рис. 38.

Рис. 38. Перетинання прямої AB із площинами граней призми.

Нехай спостерігач знаходиться в точці A. Виберемо точку B всередині опуклої фігури, у даному випадку призми. Виберемо деяку грань, яку ми хочемо перевірити, видима вона з точки A, чи не видима. Побудуємо площину, в якій лежить обрана грань. Знайдемо точку перетинання площини і прямої, що утворена відрізком AB. Якщо точка перетину прямої і площини лежить всередині відрізка AB, то робимо висновок, що дана грань видима. Якщо точка перетину знаходиться поза відрізком AB, то грань невидима. У випадку, коли пряма і площина паралельні, вважаємо що грань невидима.

Моделі розрахунку освітленості граней тривимірних об'єктів
Основною характеристикою світла в комп'ютерній графіці є яскравість. Оскільки яскравість є суб'єктивним поняттям, заснованим на людському сприйнятті світла, то для чисельних розрахунків застосовується термін інтенсивність, що відповідає яскравості і є енергетичною характеристикою світлової хвилі. У розрахунках інтенсивність звичайно приймає значення від 0 до 1. При цьому інтенсивність дорівнює нулю при повній відсутності світла, а значення 1 відповідає максимальної яскравості.
У комп'ютерній графіці для розрахунку освітленості граней об'єктів найчастіше застосовується трикомпонентна колірна модель “Червоний, Зелений, Синій”, що в англійському варіанті записується RGB (Red, Green, Blue). Ця модель дозволяє задавати будь-який колір у виді трьох компонентів інтенсивностей базових кольорів: червоного, зеленого і синього. Інтенсивність відбитого світла точок просторових об'єктів обчислюють окремо для кожної із трьох складових колірних компонентів, а потім об’єднують у результуючу трійку кольорів. Надалі будемо вважати, що приклади розрахунку інтенсивностей відбитого світла застосовуються до кожного із трьох базових кольорів.
При розрахунку освітленості граней застосовують наступні типи освітлення і відбивання світла від поверхонь.
1) Розсіяне 2) Дифузне 3) Дзеркальне

Рис. 39. Розрахунок інтенсивності відбитого світла.
Інтенсивність освітлення граней тривимірних об'єктів розсіяним світлом вважається постійною в будь-якій точці простору. Вона обумовлена сумарним відбиванням світла від всіх об'єктів у просторі. При освітленні тривимірного об'єкта розсіяним світлом інтенсивність відбитого світла обчислюється як , де - інтенсивність падаючого світла, - коефіцієнт розсіяного відбивання, залежить від розсіювальних властивостей матеріалу грані.
Для розрахунку інтенсивності дифузного відбивання світла може застосовуватися закон косинусів Ламберта: , де - кут падіння, розраховується як кут між напрямом на джерело світла і нормаллю до поверхні. Нехай напрям на джерело світла задається одиничним вектором , а - одиничний вектор нормалі. Тоді - скалярний добуток векторів. Тоді , де - коефіцієнт дифузного відбивання.
Обчислення дзеркально відбитого світла виконується також за допомогою різних емпіричних моделей, що дозволяють враховувати реальну шорсткість поверхонь. Наприклад, у моделі, запропонованої Фонгом, інтенсивність дзеркально відбитого світла розраховується в залежності від ступеня відхилення від точного значення вектора дзеркально відбитого променя світла. Нехай - вектор дзеркально відбитого променя світла, а - вектор, що визначає напрямок на спостерігача. Тоді інтенсивність дзеркально відбитого світла по моделі Фонга розраховується так: , де - кут між векторами і . Константа n – може приймати значення від 1 до приблизно 200, у залежності від відбиваючих властивостей матеріалу. Великим значенням n відповідає великий ступінь “гладкості” чи “дзеркальності” поверхні. Якщо вектори і - нормовані, то формула перетворюється до виду: .
Інтенсивність відбитого світла зменшується обернено пропорційно квадрату відстані від джерела до спостерігача. Тому можна записати формулу розрахунку інтенсивності відбитого променя світла для трьох складових: розсіяного, дифузного і дзеркально відбитого з врахуванням відстані:
,
де - відстань від точки відображення до спостерігача, а - деяка константа. Іноді, для прискорення обчислень, беруть не другий, а перший степінь відстані .
У системах комп'ютерної візуалізації також враховуються такі властивості матеріалів відбиваючих поверхонь, як прозорість, заломлення і світіння. Ступінь прозорості матеріалу грані може описуватися за допомогою константи, що приймає значення від нуля до одиниці, причому значення 1 відповідає повної непрозорості матеріалу грані. Нехай інтенсивності відбитого світла двох поверхонь, що перекриваються, рівні і . Нехай перша поверхня знаходиться ближче до спостерігача і є напівпрозорою з коефіцієнтом прозорості . Тоді сумарна інтенсивність відбитого світла може бути обчислена як зважене середнє: .
Моделі для обчислення ефектів заломлення і світіння тут не розглядаються.

Кубічні сплайни
Розглянемо задачу проведення гладких кривих по заданих граничних точках, чи задачу інтерполяції. Оскільки через дві точки можна провести як завгодно багато гладких кривих, то для розв’язування цієї задачі необхідно обмежити клас функцій, що будуть визначати шукану криву. Математичними сплайнами називають функції, які використовують для апроксимації кривих. Важливою їх властивістю є простота обчислень. На практиці найчастіше використовують сплайны типу поліномів третього ступеня. З їх допомогою досить зручно проводити криві, що інтуїтивно відповідають людському суб'єктивному поняттю гладкості. Термін “сплайн” походить від англійського spline – що означає гнучку смужку стали, яку застосовували креслярі для проведення плавних кривих, наприклад, для побудови контурів кораблів чи літаків.
Розглянемо спочатку сплайнову функцію для побудови графіка функції однієї змінної. Нехай на площині задана послідовність точок , , причому . Визначимо шукану функцію , причому поставимо дві умови:
1) Функція повинна проходити через усі задані точки: , .
2) Функція повинна бути двічі неперервно диференцьовною, тобто мати неперервну другу похідну на всьому відрізку .
На кожному з відрізків , будемо шукати нашу функцію у виді полінома третього степеня:
.

Рис. 40. Сплайнова функція.

Задача побудови полінома зводиться до знаходження коефіцієнтів . Оскільки для кожного з відрізків необхідно знайти 4 коефіцієнти , то всього кількість шуканих коефіцієнтів буде . Для знаходження всіх коефіцієнтів виведемо відповідну кількість рівнянь. Перші рівнянь одержуємо з умов рівності значень функції у внутрішніх вузлах , . Наступні рівнянь одержуємо аналогічно з умов рівності значень перших і других похідних у внутрішніх вузлах. Разом з першою умовою одержуємо рівнянь. Відсутні два рівняння можна одержати заданням значень перших похідних у кінцевих точках відрізка . Так можуть бути задані граничні умови.
Перейдемо до більш складного випадку – заданню кривих у тривимірному просторі. У випадку функціонального завдання кривої можливі багатозначності у випадку самоперетинань і незручності при значеннях похідних рівних . Через це будемо шукати функцію в параметричному виді. Нехай - незалежний параметр, такий що . Кубічним параметричним сплайном назвемо наступну систему рівнянь:

Координати точок на кривій описуються вектором , а три похідні задають координати відповідного дотичного вектора в точці. Наприклад, для координати :
.
Одним зі способів задання параметричного кубічного сплайна є вказування координат початкової і кінцевої точок, а також векторів дотичних у них. Такий спосіб задання називається формою Ерміта. Позначимо кінцеві точки і , а дотичні вектори в них і . Індекси обрані в такий спосіб з врахуванням подальшого викладу.
Будемо вирішувати задачу знаходження четвірки коефіцієнтів , тому що для двох рівнянь, які залишилися, коефіцієнти знаходяться аналогічно. Запишемо умову для побудови сплайна:
, , , (*)
Перепишемо вираз для у векторному виді:
.
Позначимо вектор-рядок і вектор-стовпчик коефіцієнтів , тоді .
З (*) випливає, що , . Для дотичних , , . Звідси одержуємо векторно-матричне рівняння:
.
Ця система розв’язується відносно знаходженням оберненої матриці розміром .
.
Тут - Ермітова матриця, - геометричний вектор Ерміта. Підставимо вираз для знаходження : . Аналогічно для інших координат: , .
Випишемо в явному виді формули для обчислення координат точок сплайна. Тому що , то помноживши справа на , одержимо:
.
Чотири функції в дужках називаються функціями сполучення.
Форму кривої, заданої у формі Ерміта, легко змінювати, якщо враховувати, що напрямок вектора дотичної задає початковий напрямок, а модуль вектора дотичної задає ступінь витягування кривої в напрямку цього вектора, як показано на рис. 41.

Рис. 41. Параметричний сплайн у формі Ерміта.
Витягування кривої вправо забезпечується тим, що .
Розглянемо форму Безье, що відрізняється від форми Ерміта способом задання граничних умов, а саме, замість векторів і вводяться точки (і відповідні їм радіус-вектори) і , як показано на рис.42, такі що виконуються умови: і .

Рис. 42. Параметричний сплайн у формі Безье.

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

Формати графічних файлів
Файли з розширеннями BMP, PCX, GIF, TIF і JPG містять растрові графічні зображення. Розширення в імені файлу говорить про те, у якому форматі зберігається інформація. Наприклад, розширення BMP позначає BMP-файл, підтримуваний у системах Windows і OS/2 (BMP - скорочення від bitmap, тобто бітовий, растровий); TIF - скорочення від TIFF чи Tagged Image File Format. Це тільки два представники великого сімейства форматів, використовуваних на персональних комп'ютерах.
Кожен з цих форматів по-різному зберігає графічну інформацію, і кожен з них розроблявся для конкретних цілей. Формат GIF (Graphics Interchange File - файл графічного обміну), наприклад, був створений, щоб вміщати якнайбільше графічної інформації в обмеженому обсязі для прискорення одержання файлів користувачами мережі CompuServe. Формат PCX спочатку був створений для збереження чорно-білих графічних файлів в ранніх версіях програми PC Paintbrush для IBM PC. Зараз формат PCX застосовується і для кольорових графічних файлів.
Растровий графічний файл містить інформацію двох видів: графічну і неграфічну. У графічних даних вказуються кольори пікселів, неграфічні дані містять інформацію, необхідну для відновлення зображення, наприклад, його висоту і ширину, а також службову, наприклад, номер версії чи відомості про авторські права. Все залежить від формату і від того, хто (чи який програмний пакет) створив цей файл.
У растрових файлах використовується один із двох методів збереження даних про пікселі. У повноколірних зображеннях піксель може приймати будь-яке з більш ніж 16 мільйонів значень і колір пікселя зберігається як 24-розрядне значення - по 8 бітів на червону, зелену і синю компоненти кольору. Якщо зображення містить 1 мільйон пікселів, то розмір файлу дорівнює 3 мільйони байтів плюс довжина неграфічних даних. Якщо ж зображення обмежене 256 кольорами, то інформація про кольори кодується з використанням палітри. Замість того, щоб зберігати повністю значення кольору для кожного пікселя, інформація про пікселі вказує на номер кольору у палітрі, а вона містить коди кольорів. Зі зменшенням кількості бітів, необхідних для представлення кольору пікселя, зменшується розмір файлу.
Як приклад, візьмемо зображення з мільйона пікселів, що містить 256 різних кольорів. Кодування кольору кожного пікселя 24-бітним значенням приводить до надмірності, тому що деякі (а можливо й всі) з 256-ти кольорів повторюються неодноразово. Для зберігання кодів кольорів, які зустрічаються в даному 256-колірному малюнку, виділяється у файлі 768 байтів під кольорову палітру: 256 полів по 24 біти, кожне поле містить один із кольорів, що зустрічаються в зображенні. Тоді кольори пікселів кодуються 8 бітами, тобто цілими числами в діапазоні від 0 до 255, які вказують на номер кольору в палітрі. Тепер для графічної частини файлу досить 1000768 байтів, проти колишніх 3000000 байтів, що вимагаються для збереження цього зображення без використання палітри. І навіть з врахуванням додаткових байтів з неграфічної частини файлу, ми все-таки одержуємо зменшення розміру файлу майже втричі.
У більшості форматів графічних файлів пікселі розташовуються по рядках. Якщо розміри зображення 1000 на 1000 пікселів, і кожен піксель представляється 8-ма бітами, то перші 1000 байтів графічної частини файлу містять кольори пікселів з верхнього рядка зображення (зліва направо), наступні 1000 байтів містять кольори пікселів другого рядка і так далі. Однак у деяких форматах використовується інший порядок рядків. Наприклад, BMP-файли починаються з нижнього рядка і закінчуються верхнім рядком зображення.
У кожному форматі графічні і неграфічні дані структуруються по-своєму. Уникаючи узагальнень, розглянемо ближче один з форматів – BMP-формат, що широко використовується в системах Windows і OS/2. Зокрема, ми розглянемо BMP-файл, що описує 256-кольорове зображення розміром 1000 на 1000 пікселів. (Формат BMP-файлу дещо відрізняється в залежності від того, скільки кольорів містить зображення - 2, 16, 256 чи 16,7 млн. Формати BMP у Windows і OS/2 також небагато відрізняються.) Опис цього файлу буде відповідати варіанту BMP для Windows. Файл складається з чотирьох основних частин: 14-байтного заголовка файлу, 40-байтного інформаційного заголовка, 1024-байтної кольорової таблиці і мільйона байтів для значень пікселів. (Під таблицю кольорів виділяється 1024 байти, а не 768, оскільки в кожне 24-бітове поле таблиці додається ще один, невикористовуваний байт.)
Перші 14 байтів BMP-файлу утворюють його заголовок. Заголовок файлу містить три значення: букви BM, що говорять про те, що графічний файл має BMP формат, число, що відповідає розміру файла і число, що вказує на зміщення, з якого починаються растрові дані. Ще два поля в заголовку файла зарезервовані для майбутнього використання і містять нулі.
Неграфічні дані зберігаються в інформаційному заголовку. Поля в інформаційному заголовку вказують його розмір (40 байтів у BMP-файлах для Windows), висоту і ширину зображення в пікселях і кількість бітів на піксель.
Таблиця кольорів (палітра) містить 256 полів по 4 байти. Перший байт у кожному полі відповідає синій компоненті кольору, другий зеленій і третій - червоній. Четвертий байт не використовується і встановлюється в 0. Якщо перші три байти в таблиці кольорів, наприклад, дорівнюють 0, 192 і 192, це означає, що нульовий номер відповідає жовтому кольору середньої інтенсивності (суміш зеленого і червоного). У таблиці кольорів визначаються всі кольори, що використовуються в зображенні.
Наступна частина файлу містить номери кольорів для всіх пікселів зображення. Наприклад, зображення складається з 1 мільйона пікселів, кожен піксель вимагає 8 бітів - одного байта кольорової інформації, ця частина файлу займає 1 мільйон байтів. Послідовність байтів відповідає порядку пікселів у зображенні зліва направо, починаючи з нижнього рядка зображення. Значенням кожного байта є номер кольору в таблиці кольорів.
Виведення на екран зображення, що зберігається в BMP-файлі, починається з читання заголовка файлу та інформаційного заголовка. Програма, таким чином, довідається про розміри зображення і кількість кольорів.
Потім програма читає таблицю кольорів. Якщо комп'ютер виводить 256 кольорів максимум, то програма заповнює кольорову палітру значеннями з таблиці кольорів . Так забезпечується правильна передача кольорів. Якщо комп'ютер працює у відеорежимі з 16, 24 чи 32 бітами на піксель, то кольорову палітру заповнювати не потрібно.
І, нарешті, зчитуються растрові дані. Як тільки рядок зі значеннями кодів пікселів прочитаний із файла, він передається у відеобуфер для виведення точок зображення. У таких графічних системах, як Windows, програма пересилає значення кольорів не безпосередньо у відеобуфер, а в модуль GDI32 (Graphic Device Interface), і вже звідти заноситься у відеобуфер.

Стискання зображень
Основний недолік растрових файлів - дуже великі розміри. Якщо зневажити заголовками файлу й іншими неграфічними даними, його розмір пропорційний кількості пікселів у зображенні і кількості бітів, необхідних для представлення кожного пікселя. Повнокольорове зображення розміром 1024х768 пікселів займає більше двох мегабайтів пам'яті, а одна секунда відеофільму телевізійної якості в растровому вигляді з'їдає біля тридцяти мегабайтів. Тому жорсткий диск при поганій організації роботи заповнюється дуже швидко. Оптичні компакт-диски, які мають обсяг 700-800 мегабайтів, теж нераціонально використовувати для зберігання зображень в розгорнутому вигляді.
Використовуючи алгоритми стискання зображень, можна різко зменшити розмір графічних файлів. Для стискання графічної інформації використовуються математичні прийоми, що зменшують надлишковість інформації, яка представлена в графічному вигляді. Ступінь стискання залежить від вибору методу і надлишковості вмісту графічного файла і для примітивних зображень може досягати сотень і тисяч разів, а для складних фотозображень приблизно дорівнює від 3 до 10 разів. Існують методи, що стискають ще сильніше, але з деякою втратою якості - при відновленні зображення втрачається певна частина інформації про кольори. В результаті розпаковане зображення може стати дещо розмитим чи знебарвленим.
Алгоритми стискання растрової інформації поділяються на дві великі групи: стискання із втратами і стискання без втрат. Методи стискання без втрат дають більш низький коефіцієнт стискання, але зберігають точне значення кольорів пікселів початкового зображення. Методи з втратами дають більш високі коефіцієнти стискання, але не дозволяють відтворювати первісне зображення з точністю до пікселя. Для більшості файлів, що містять текстову чи математичну інформацію, дуже важливо зберегти всю інформацію, бо втрата хоча б одного біта може змінити зміст всього файлу. Зовсім інша справа з растровими даними. Людське око не сприймає всі тонкі відтінки кольорів в звичайному растровому зображенні. Тому деякі деталі можуть бути опущені без помітного порушення інформаційного змісту малюнка.
Розповсюджені алгоритми стискання зображень без втрат: RLE, LZW, алгоритм Хафмана, JBIG. Алгоритми архівації з втратами: JPEG, фрактальний та хвильовий.

Алгоритм архівації без втрат RLE
Існує два варіанти алгоритму. Спочатку розглянемо перший варіант.
Даний алгоритм надзвичайно простий в реалізації. Групове кодування (від англійського Run Length Encoding (RLE)) - найстаріший і найпростіший алгоритм архівації графіки. Зображення в ньому витягається в ланцюжок байтів по рядках растра. Саме стискання у RLE відбувається за рахунок того, що у зображенні зустрічаються ланцюжки однакових байтів. Заміна їх на пари <лічильник повторень, значення> зменшує надмірність даних.
Ознакою байта-лічильника є одиниці в двох верхніх бітах. Решта 6 бітів використовуються для лічильника, що може набувати значення від 1 до 64. Рядок з 64 повторюваних байтів перетворюється в два байти, тобто стискається в 32 рази.
Алгоритм розрахований на ділову графіку — зображення з великими областями повторюваного кольору. Можлива ситуація, коли розміри файла не зменшуються, а збільшуються.
Даний алгоритм реалізований у форматі PCX.
Тепер розглянемо другий варіант алгоритму. Другий варіант цього алгоритму має більший максимальний коефіцієнт стискання. Ознакою повтору в даному алгоритмі є одиниця в старшому розряді відповідного байта.
В найкращому випадку цей алгоритм може стиснути файл у 64 рази (а не в 32 рази, як у попередньому варіанті), в найгіршому збільшує на 1/128. Середні значення ступеня компресії обох варіантів алгоритму приблизно рівні.
Схожа схема компресії використана у форматах TIFF і TGA.

Алгоритм архівації без втрат LZW
Назва алгоритму пов’язана із прізвищами авторів - Lempel, Ziv і Welch. Стискання у ньому здійснюється за рахунок повторень ланцюжків байтів.
Процес стискання виглядає досить просто. Послідовно зчитуються символи вхідного потоку і перевіряться, чи є в створеній таблиці рядків такий самий рядок. Якщо рядок є, то ми зчитуємо наступний символ, а якщо рядка немає, то ми заносимо в потік код для попередньо знайденого рядка, заносимо рядок у таблицю і починаємо пошук спочатку.
На практиці для зберігання таблиці використовується хеш-таблиця. Таблиця складається з 8192 (213) елементів. Кожен елемент містить <код попереднього підрядка; доданий символ; код цього рядка>. Ключ для пошуку довжиною 20 бітів формується з використанням двох перших елементів, збережених у таблиці як одне число (key). Молодші 12 бітів цього числа відведені для коду, а наступні 8 бітів для значення символу.
Як хеш-функція використовується: Index(key)=((key >> 12) XOR key) & 8191;
Де >> - побітовий зсув вправо (key >> 12 - ми одержуємо значення символу), XOR - побітова логічна операція виключного АБО, & - логічне побітове І.
Таким чином, за декілька порівнянь знаходиться одержуємо шуканий код чи повідомлення, що такого коду в таблиці немає.
Найкращий коефіцієнт стискання буде для ланцюжка одинакових байтів великої довжини (наприклад, для 8-бітного зображення, всі точки якого мають, для визначеності, колір 0). При цьому в 258 рядок таблиці ми запишемо рядок “0, 0”, у 259 — “0, 0, 0”, ... у 4095 — рядок з 3809 (=4095-256) нулів. При цьому в потік потрапить 3810 кодів, включаючи код очищення. Отже, порахувавши суму арифметичної прогресії від 1 до 3809 (тобто довжину стиснутого ланцюжка) і розділивши її на 3810*12/8 (в потік записуються 12-бітні коди), ми одержимо значення можливого найкращого коефіцієнта компресії для цього методу.
Найгірший коефіцієнт буде для випадку, коли ми жодного разу не зустрінемо підрядок, що вже є в таблиці (в ній не повинно зустрітися жодної однакової пари символів).
LZW реалізований у форматах GIF і TIFF.

Алгоритм архівації без втрат Хафмана
Це класичний алгоритм стискання, відомий з 60-х років. Використовує тільки частоту появи одинакових байтів у зображенні. Зіставляє символам вхідного потоку з більшою частотою появи коротші ланцюжки бітів. І, навпаки, символи, що зустрічаються рідше, кодуються ланцюжками більшої довжини. Для статистичного аналізу потрібно двічі переглядати растрове зображення.
На практиці використовуються різновиди алгоритму. Так, у деяких випадках використовується постійна таблиця, а в деяких таблиця будується адаптивно в процесі архівації/розархівації. Ці прийоми не вимагають двох переглядів і необхідності збереження таблиці разом із зображенням. Кодування з фіксованою таблицею застосовується як останній етап архівації в JPEG і в деяких інших алгоритмах.

Алгоритм архівації без втрат JBIG
Алгоритм розроблений групою експертів ISO (Joint Bi-level Experts Group) спеціально для стискання контрастних однобітних чорно-білих зображень. Наприклад, факсів чи відсканованих документів. В принципі, може застосовуватися і до 2-х, і до 4-х бітових малюнків. При цьому алгоритм розбиває їх на окремі бітові площини. JBIG дозволяє керувати такими параметрами, як порядок розбивки зображення на бітові площини, ширина смуг у зображенні, рівні маштабування. Остання можливість дозволяє легко орієнтуватися в базі великих за розмірами зображень, переглядаючи спочатку їх зменшені копії. Змінюючи ці параметри, можна використовувати описаний вище ефект “огрубленного зображення” при одержанні зображення по мережі чи по будь-якому іншому каналі, пропускна здатність якого мала в порівнянні з можливостями процесора. Розпаковуватися зображення на екрані буде поступово, ніби повільно “проявляючись”. При цьому людина починає аналізувати зображення задовго до кінця процесу розархівації.
Алгоритм побудований на базі Q-кодувальника, патентом на який володіє IBM. Q-кодер так само, як і алгоритм Хафмана, використовує для частіше повторюваних символів коротші ланцюжки, а для рідше повторюваних - довші. Однак, на відміну від попереднього, в алгоритмі кодуються не окремі байти, а ланцюжки символів.

Алгоритм архівації із втратами JPEG
JPEG - досить новий і потужний алгоритм. Практично він є стандартом де-факто для фотографічних зображень. Алгоритм оперує областями 8х8 пікселів, на яких яскравість і колір змінюються порівняно плавно. Внаслідок цього, при розкладанні матриці такої області в подвійний ряд за косинусами значимими виявляються тільки перші коефіцієнти. Таким чином, стискання у JPEG здійснюється за рахунок плавної зміни кольорів у зображенні.
Алгоритм розроблений групою експертів в області фотографії спеціально для стискання 24-бітних зображень. JPEG - Joint Photographic Expert Group - підрозділ у рамках ISO - Міжнародної організації по стандартизації. Назва алгоритму читається ['jei'peg]. Алгоритм заснований на дискретному косинусоїдальному перетворенні (надалі ДКП), яке застосовується до матриці зображення для одержання деякої нової матриці коефіцієнтів. Для відтворення початкового зображення застосовується обернене перетворення.
ДКП розкладає зображення за амплітудами основних частот. В процесі перетворення обчислюється матриця, в якій багато коефіцієнтів приблизно дорівнюють нулю. Крім того, людська система сприйняття кольору слабо розпізнає певні частоти. Тому можна апроксимувати деякі коефіцієнти більш грубо без помітної втрати якості зображення.
Для цього використовується квантування коефіцієнтів (quantization). В найпростішому випадку - це арифметичний побітовий зсув вправо. При цьому перетворенні губиться частина інформації, але можуть досягатися великі коефіцієнти стискання.
Істотними позитивними сторонами алгоритму є те, що:
1) Задається ступінь стискання.
2) Вихідне кольорове зображення може мати 24 біти на піксель.
Негативними сторонами алгоритму є те, що:
1) При підвищенні ступеня стискання зображення розпадається на окремі квадрати (8x8). Це позв'язано з великими втратами в низьких частотах при квантуванні, і відновити вихідні дані стає неможливо.
2) Проявляється ефект Гібса - ореоли по границях різких переходів кольорів.
Стандартизований JPEG відносно недавно - у 1991 році. Але вже тоді існували алгоритми, які стискали сильніше при менших втратах якості, але вимагали набагато більше обчислень. Дії авторів стандарту були обмежені обчислювальними потужностями тогочасної техніки . На персональному комп'ютері алгоритм повинен був із зображенням середньої складності працювати менше хвилини, а його апаратна реалізація - відносно простою і дешевою. Алгоритм повинен був бути симетричним (час стискання приблизно дорівнює часу розгортання).
Стала можливою поява цифрових фотоапаратів - пристроїв невеликого розміру, що знімають 24-бітові фотографії на 10-200 Мб флеш-карту. Потім ця карта вставляється в роз’єм на комп’ютері і зображення зчитується, редагується і друкується на фотопринтері.
Неприємною властивістю JPEG є також те, що горизонтальні і вертикальні смуги на дисплеї не помітні, але можуть проявитися на друкованих копіях у вигляді муарового візерунка. Він виникає при накладанні похилого растра принтера на горизонтальні і вертикальні смуги зображення. Через це JPEG не рекомендується використовувати в поліграфії. Однак при архівації зображень, призначених для перегляду людиною, він на даний момент незамінний.
Кілька слів необхідно сказати про модифікації цього алгоритму. Хоча JPEG і є стандартом ISO, формат його файлів не був зафіксований. Користуючись цим, виробники використовують свої, несумісні між собою формати, і, отже, можуть змінювати алгоритм. Так, внутрішні таблиці алгоритму, рекомендовані ISO, заміняються ними на свої власні. Крім того, легка плутанина присутня при заданні ступеня втрат. Наприклад, при тестуванні з'ясовується, що “відмінна” якість, “100%” і “10 балів” дають істотно різні результати. При цьому, до речі, “100%” якості не означає стискання без втрат. Зустрічаються також варіанти JPEG, які використовують тільки окремі програми.
Як стандарт ISO, JPEG широко використовується для обміну зображеннями в комп'ютерних мережах та Інтернеті. Підтримується алгоритм JPEG у форматах Quick Time, PostScript Level 2, Tiff 6.0 і на даний момент займає чільне місце в системах мультимедіа.

Фрактальний алгоритм архівації із втратами
Фрактальна архівація заснована на тому, що зображення представляється в більш компактній формі за допомогою коефіцієнтів системи ітерованих функцій (Iterated Function System - надалі IFS). IFS являє собою набір тривимірних афінних перетворень, які переводять одне зображення в інше. Перетворенню піддаються точки в тривимірному просторі (х_координата, у_координата, яскравість).
Найбільш наочно цей процес продемонстрував Барнслі у своїй книзі “Fractal Image Compression”. Там введене поняття Фотокопіювальної Машини, що складається з екрана, на якому зображений початковий малюнок, і системи лінз, що проектують зображення на інший екран.
• Лінзи можуть проектувати частину зображення довільної форми в будь-яке інше місце нового зображення.
• Області, у які проектуються зображення, не перетинаються.
• Лінза може змінювати яскравість і зменшувати контрастність.
• Лінза може дзеркально відбивати і повертати свій фрагмент зображення.
• Лінза повинна зменшувати (маштабувати) свій фрагмент зображення.
Розставляючи лінзи і змінюючи їх характеристики, ми можемо керувати одержуваним зображенням. Одна ітерація роботи Машини полягає в тому, що з вихідного зображення за допомогою проектування будується нове, після чого нове береться в якості вихідного. Стверджується, що в процесі ітерацій ми одержимо зображення, яке перестане змінюватися. Воно буде залежати тільки від розташування і характеристик лінз і не буде залежати від вихідної картинки. Це зображення називається “нерухомою точкою” чи атрактором даної IFS. Відповідна теорія гарантує наявність рівно однієї нерухомої точки для кожної IFS.
Кожне перетворення кодується буквально ліченими байтами, у той час як зображення, побудовані з їх допомогою, можуть займати декілька мегабайтів.
З вищесказаного стає зрозуміло, як працює архіватор, і чому йому потрібно так багато часу. Фактично, фрактальна компресія - це пошук самоподібних областей у зображенні і визначення для них параметрів афінних перетворень.
У нагіршому випадку, якщо не буде застосовуватися оптимізація алгоритму, потрібно перебрати і порівняти всі можливі фрагменти зображення різного розміру. Навіть для невеликих зображень з врахуванням дискретності ми одержимо астрономічне число варіантів, які потрібно перебрати. Причому навіть різке звуження класів перетворень, наприклад, за рахунок маштабування тільки у визначену кількість разів, не дає помітного виграшу в часі. Крім того, при цьому втрачається якість зображення. Переважна більшість досліджень в області фрактальної компресії зараз спрямовані на зменшення часу архівації, необхідного для одержання якісного зображення.

Хвильовий алгоритм архівації із втратами
Англійська назва рекурсивного стискання – wavelet - перекладається як хвильове стискання чи як стискання із використанням сплесків. Цей вид архівації відомий досить давно і побудований на ідеї використання когерентності областей. Орієнтований алгоритм на кольорові і чорно-білі зображення з плавними переходами. Ідеальний для зображень типу рентгенівських знімків. Коефіцієнт стискання задається і лежить в межах 5 - 100 разів. При спробі задати більший коефіцієнт, на різких границях, що проходять по діагоналі, проявляється “ступінчастий ефект” - сходинки різної яскравості, розміром у декілька пікселів.
Ідея алгоритму полягає в тому, що у файлі зберігається різниця між середніми значеннями сусідніх блоків у зображенні, яка набуває невеликих значень, близьких до 0.
До достоїнств цього алгоритму можна віднести те, що він дозволяє реалізувати можливість поступового “проявлення” зображення при передачі по мережі чи каналах зв’язку. На початку зображення фактично зберігається його зменшена копія, що дозволяє швидко переглядати зменшені варіанти зображень.
На відміну від JPEG і фрактального алгоритму даний метод не оперує блоками тільки одного розміру, наприклад, 8х8 пікселів. Точніше, ми оперуємо блоками 2х2, 4х4, 8х8 і т.д. Однак внаслідок того, що коефіцієнти для цих блоків зберігаються незалежно, не відбувається дроблення зображення на “мозаїчні” квадрати.

 

 

Список літератури
1. Ньюмен, Спрулл, Основы интерактивной машинной графики, М. Мир, 1976.
2. Энджел Й. Практическое введение в машинную графику, Радио и Связь, 1984.
3. А. Вэн-Дэм, Дж. Фоли, Основы интерактивной машинной графики, т.1-2, М. Мир, 1985.
4. Е.В. Шикин, А.В.Боресков, Компьютерная графика. Динамика, реалистические ихображения, М., Диалог-МИФИ, 1995, 1997.
5. Л. Аммерал, Машинная графика на языке С, в 4-х томах, изд-во Сол. Систем, 1992.
6. Компьютер обретает разум. Пер. с англ. Под ред. В.Л.Стефанюка, М. Мир, 1990.
7. Роджерс, алгоритмические основы машинной графики. М. Мир, 1989.
8. Грайс, Графические средства персональных компьютеров, М., Мир, 1980.
9. Роджерс, Адамс, Математические основы машинной графики, М. Машиностроение, 1985.
10. Гилой, Интерактивная машинная графика, М., Мир, 1981.
11. Ф. Препарата, М. Шеймос, Вычислительная геометрия: Введение, М. Мир, 1989.
12. А.Фокс, М. Пратт, Вычислительная геометрия, М., Мир, 1982.
13. А.Б.Боресков, Е.В.Шикин, Г.Е.Шикина, Компьютерная графика: первое знакомство, Под ред. Е.В.Шикина, М., Финансы и статистика, 1996.
14. А.В.Фролов, Г.В.Фролов, Графический интерфейс GDI в MS WINDOWS, Москва, Изд-во Диалог-МИФИ, 1994.
15. Майкл Ласло, Вычислительная геометрия и компьютерная графика на С++, Москва, Бином, 1997.
16. Ю.Тихомиров, Программирование трехмерной графики, С.-Пб.: БХВ Санкт-Петербург,1999.
17. А.Хонич, Как самому создать трехмерную игру. М.:МИКРОАРТ, 1996.
18. М.Маров, 3D Studio MAX 2.5: справочник – СПб: «Питер», 1999. – 672 с.
19. А.Ла Мот, Д.Ратклифф и др. Секреты программирования игр/ Перев с англ. – СПб: Питер, 1995. – 720 с.
20. Н. Томпсон, Секреты программирования трехмерной графики для Windows 95. Перев с англ. – СПб: Питер, 1997. – 352 с.