Software renderer - 1: матчастину

Програмний рендерінг (software rendering) — це процес побудови зображення без допомоги GPU. Цей процес може йти в одному з двох режимів: у реальному часі (обчислення великої кількості кадрів в секунду — необхідно для інтерактивних додатків, наприклад, ігор) і «оффлайн» режимі (при якому час, який може бути витрачений на обчислення одного кадру, не обмежена настільки строго — обчислення можуть тривати годинник або навіть дні). Я буду розглядати тільки режим візуалізації в реальному часі.

У цього підходу існують як недоліки так і переваги. Очевидним недоліком є продуктивність — CPU не в змозі конкурувати з сучасними відеокартами в цій області. До переваг слід віднести незалежність від відеокарти — саме тому він використовується як заміна апаратного рендеринга у випадках, коли відеокарта не підтримує ту або іншу можливість (так званий software fallback). Існують і проекти, мета яких — повністю замінити апаратний рендеринг програмним, наприклад, WARP, що входить до складу Direct3D 11.

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

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

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

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

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

Вектора

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



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

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

Щоб уникнути плутанини, в межах статті ми не будемо більше розуміти під словом «вектор» абстрактний набір чисел, а будемо так називати зміщення.

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



У скалярного твору є дві важливі геометричні інтерпретації.

  1. Вимірювання кута між векторами.
    Розглянемо наступний трикутник, отриманий з трьох векторів:



    Записавши для нього теорему косинусів і скоротивши вираз, прийдемо до запису:



    Оскільки довжина ненульового вектора за визначенням більше 0, то косинус кута визначає знак скалярного добутку і його рівність нулю. Отримуємо (вважаючи, що кут від 0 до 360 градусів):



  2. Скалярний добуток обчислює довжину проекції вектора на вектор.



    З визначення косинуса кута отримуємо:



    Ми вже знаємо з попереднього пункту, що:



    Висловивши з другого виразу косинус кута, підставивши в перше і домножив на ||w||, одержуємо результат:



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

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



    Ми надалі скористаємося цим при побудові трансформації в систему координат камери.

Системи координат

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

Уявімо, що у нас виникла необхідність у візуалізації сцени з двома моделями, наприклад:



Які системи координат природним чином випливають з такої постановки? Перша — це система координат самої сцени (яка зображена на рисунку). Це система координат, що описує світ, який ми збираємося малювати — саме тому вона і називається «світової» (на картинках буде позначена словом «world»). Вона «пов'язує» всі об'єкти сцени разом. Наприклад, координати центра об'єкта A система координат (1, 1), а координати центра об'єкта B (-1, -1).

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

Для простоти будемо вважати, що модель описується просто списком точок («вершин»), з яких вона складається. Наприклад, модель B складається з трьох точок, які приходять нам в наступному форматі:

v0 = (x0, y0)
v1 = (x1, y1)
v2 = (x2, y2)

На перший погляд, було б здорово, якби вони вже були описані в потрібній нам «світової» системі! Уявляєте, ви додаєте модель на сцену, а вона вже знаходиться там, де нам і потрібно. Для моделі B це могло б виглядати ось так:

v0 = (-1.5, -1.5)
v1 = (-1.0, -0.5)
v2 = (-0.5, -1.5)

Але використовувати такий підхід не вийде. На те є поважна причина: це позбавляє можливості використовувати одну і ту ж модель заново в різних сценах. Уявіть, що вам дали модель B, яка була змодельована так, що при додаванні її на сцену вона виявляється в потрібному нам місці, як у прикладі вище. Потім, раптово, вимога змінилося — ми хочемо її зрушити зовсім на іншу позицію. Виходить, людині, яка створила цю модель, доведеться рухати її самостійно і потім знову віддавати вам. Звичайно, це — повний абсурд. Ще більш сильний аргумент це те, що у випадку з інтерактивними додатками, модель може рухатися, повертатися, анимироваться на сцені — що ж, художнику робити модель у всіх можливих положеннях? Це звучить ще більш нерозумно.

Рішення цієї проблеми — «локальна система координат моделі. Ми моделюємо об'єкт таким чином, щоб його центр (або те, що можна умовно за такої прийняти) був розташований в початку координат. Потім ми програмно орієнтуємо (переміщуємо, повертаємо тощо) локальну систему координат об'єкта у потрібне нам місце у світовій системі. Повертаючись до сцени вище, об'єкт A (одиничний квадрат, повернутий на 45 градусів за годинниковою стрілкою) може бути змодельований наступним чином:



Опис моделі в цьому випадку буде виглядати наступним чином:

v0 = (-0.5, 0.5)
v1 = (0.5, 0.5)
v2 = (0.5, -0.5)
v3 = (-0.5, -0.5)

І, відповідно, положення в сцені двох систем координат — світовий та локальної об'єкта A:



Це — один з прикладів, чому наявність кількох систем координат спрощує життя розробникам (і художникам!). Є ще й інша причина — перехід до іншої системи координат може спростити необхідні обчислення.

Опис однієї системи координат відносно іншої
Не існує такого поняття як «абсолютні координати». Опис чого-небудь завжди відбувається відносно якоїсь системи координат. У тому числі і опис іншої системи координат.

Ми можемо побудувати своєрідну ієрархію систем координат в прикладі вище:

— world space
— local space (object A)
— local space (object B)

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

Кожна дочірня система координат може бути описана щодо батьківської за допомогою наступних значень:
  • точка початку координат дочірньої системи щодо батьківської
  • координати базисних векторів дочірньої системи щодо батьківської
Наприклад, у зображенні нижче, початок координат системи 'y' (позначене O') розташоване в точці (1, 1), а координати її базисних векторів i j' дорівнюють (0.7, -0.7) (0.7, 0.7) (що приблизно відповідає осях, повернений на 45 градусів за годинниковою стрілкою).



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



Переклад координат точок з однієї системи в іншу
Координати точки P батьківського системі координат (позначимо Pparent) можуть бути обчислені за допомогою координат цієї точки в дочірній системі (позначимо Pchild) та орієнтації цієї дочірньої системи щодо батьківської (описаній з допомогою початку координат Ochild і базисних векторів i' j') наступним чином:



Знову повернемося до прикладу сцени вище. Ми зорієнтували локальну систему координат об'єкта A щодо світової:



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

Для прикладу візьмемо першу вершину v = (-0.5, 0.5) і обчислимо її координати у світовій системі:



У вірності результату можна переконатися, подивившись на зображення вище.

Матриці

Матриця розмірності m x n — відповідної розмірності таблиця чисел. Якщо кількість стовпців матриці а дорівнює кількості рядків, то матриця називається квадратною. Наприклад, матриця 3 x 3 виглядає наступним чином:



Перемножування матриць
Припустимо, що у нас є дві матриці: M (розмірністю a x b) і N (розмірністю c x d). Вираз R = M · N визначено тільки в тому випадку, якщо кількість стовпців в матриці M дорівнює числу рядків матриці N (тобто b = c). Розмірність отриманої матриці буде дорівнювати a x d (тобто кількість рядків дорівнює кол-ву рядків M а число стовпців — числу стовпців N), а значення, яке перебуває на позиції ij, обчислюється як скалярний добуток i-го рядка M j-ї стовпець N:



Якщо результат множення двох матриць M · N визначено, то це зовсім не означає, що визначено і множення у зворотний бік — N · M (можуть не збігатися кількість рядків і стовпців). У загальному випадку, операція множення матриць так само не коммутативна: M · N ≠ N · M.

Одинична матриця — це матриця, яка не змінює домноженную на неї іншу матрицю (тобто M · I = M) — своєрідний аналог одиниці для звичайних чисел:



Представлення векторів у вигляді матриць
Ми так само можемо вектор представити як матрицю. Є два можливих способи це зробити, які називають «вектор-рядок та вектор-стовпець». Як зрозуміло з назви, вектор-рядок — це вектор, представлений у вигляді матриці з одним рядком, а вектор-стовпець — вектор, представлений у вигляді матриці з одним стовпцем.

Вектор-рядок:



Вектор-стовпець:



Далі ми дуже часто будемо стикатися з операцією множення матриці на вектор (для чого буде обьяснено у наступному розділі), і, забігаючи вперед, матриці з якими ми будемо працювати будуть мати розмірність або 3 x 3 або 4 x 4.

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

  • Множення вектора на матрицю зліва:



  • Множення вектора на матрицю «справа»:

Як видно, ми отримуємо різний результат у кожному з випадків. Це може призвести до випадкових помилок, якщо API дозволяє помножити вектор на матрицю з обох сторін, оскільки, як ми побачимо надалі, матриця трансформації увазі що вектор буде помножений на неї одним з двох способів. Так що, на мою думку, в API краще дотримуватися тільки одного з двох варіантів. В рамках цих статей я буду використовувати перший варіант — тобто вектор множиться на матрицю зліва. Якщо ви вирішили використовувати інший порядок, то, для того щоб отримати коректні результати, вам потрібно буде перенести всі матриці, які в подальшому зустрінуться у цій статті, а слово «рядок» замінити на «стовпець». Це так само впливає на порядок множення матриць при наявності декількох трансформацій (детальніше буде розглянуто далі).

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

Ще одне вкрай важливе властивість операції множення матриць, яке нам надалі згодиться — дистрибутивность щодо складання:



Геометрична інтерпретація
Як ми побачили в попередньому розділі — матриця певним чином трансформує домноженный на неї вектор.

Ще раз згадаємо, що будь-який вектор може бути представлений як лінійна комбінація базисних векторів:





Помножимо це вираз на матрицю:



Використовуючи дистрибутивность щодо складання, отримаємо:



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



Між цими двома виразами є дві відмінності — в першому виразі немає переміщення (Ochild, ми розглянемо пізніше цей момент докладніше, коли будемо говорити про лінійних та афінних трансформаціях), а вектора i, j' k' замінені на iM, jM kM відповідно. Отже, iM, jM kM — є базисні вектори дочірньої системи координат і ми переводимо точку vchild(vx, vy, vy) з цієї дочірньої системи координат в батьківську (vtransformed = vparentM).

Процес трансформації можна зобразити таким чином на прикладі обертання проти годинникової стрілки (xy — початкова, батьківська система координат, 'y' — дочірня, отримана в результаті трансформації):



На всяк випадок, щоб переконатися, що нам зрозумілий сенс кожного з векторів, використовуваних вище, перерахуємо їх заново:
  • vparent — вектор, який ми спочатку множили на матрицю M. Його координати описані щодо батьківської системи координат
  • vchild — вектор, координати якого дорівнюють вектору vparent, але вони описані щодо дочірньої системи координат. Це вектор vparent трансформований тим же чином, що і базисні вектори (оскільки ми використовуємо ті ж координати)
  • vtransformed — той самий вектор, що і vchild але з координатами перерахованими щодо батьківської системи координат. Це підсумковий результат трансформації вектора vparent
Тепер розглянемо, що відбувається при множенні базисних векторів на матрицю M:





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

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



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

Лінійні трансформації

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



Важливе наслідок — лінійна трансформація не може містити переміщення (це так само є причиною, по якій доданок Ochild відсутнє в попередньому розділі), оскільки, згідно з другою формулою, 0 в 0.

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





Приклад:



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



Масштабування
Ми можемо змінити масштаб об'єкта щодо всіх осей застосувавши наступну матрицю:



Осі трансформованої системи координат будуть направлені так само, як і у початкової системи координат, але будуть вимагати в S разів більшої довжини для однієї одиниці виміру:



Приклад:


Масштабування з однаковим коефіцієнтом щодо всіх осей називається рівномірним (uniform). Але ми так само можемо зробити масштабування з різними коефіцієнтами вздовж різних осей (nonuniform):



Shift
Як зрозуміло з назви, ця трансформація виробляє зсув вздовж координатної осі, залишаючи інші осі недоторканими:



Відповідно, матриця зсуву осі y виглядає наступним чином:



Приклад:



Матриця для тривимірного простору будується аналогічним чином. Наприклад, варіант для зсуву осі x:



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

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

Центральна проекція

Наша кінцева мета — зобразити тривимірну сцену на двовимірному екрані. Таким чином, ми повинні тим чи іншим способом спроектувати нашу сцену на площину. Існує дві найбільш часто використовувані типи проекцій — ортографическая і центральна (інша назва — перспективна).

Коли око дивиться на тривимірну сцену, об'єкти, що знаходяться далі від нього, стають меншими в підсумковому зображенні, яке і бачить людина — цей ефект називається перспективою. Ортографическая проекція ігнорує перспективу, що є корисним властивістю при роботі в різних CAD-системах (а так само в 2D іграх). Центральна ж проекція володіє цією властивістю і тому додає значну частку реалістичності. У цій статті ми будемо розглядати тільки її.

На відміну від ортографической проекції лінії в перспективній проекції не паралельні один одному, а перетинаються в точці, званої центром проекції. Центром проекції виступає «око», яким ми дивимося на сцену — віртуальна камера:



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



Розглянемо найпростіший приклад: камера розташована в початку координат, а площину проекції знаходиться на відстані d від камери. Нам відомі координати точки, яку ми хочемо спроектувати: (x, y, z). Знайдемо координату xp проекції цієї точки на площину:



На цій картинці видно два подібних трикутника — CDP CBA (по трьом кутам):



Відповідно, відносини між сторонами зберігаються:



Отримуємо результат для x-координати:



І, аналогічно, для y-координати:



Пізніше, нам необхідно буде використовувати цю трансформацію для формування спроецированного зображення. І тут виникає проблема — ми не можемо уявити поділ на z-координату в тривимірному просторі за допомогою матриці. Рішенням цієї проблеми, так само як і у випадку з матрицею переміщення, є однорідні (homogeneous) координати.

Проективна геометрія і однорідні координати

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

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

Визначимо промінь у просторі R3 наступним чином: промінь — це безліч векторів виду kv (k — скаляр, v — ненульовий вектор, елемент простору R3). Тобто вектор v задає напрям променя:



Тепер ми можемо перейти до визначення проективного простору. Проективна площину (тобто проективне простір з розмірністю дорівнює двом) P2, асоційована з простором R3, це безліч променів R3. Таким чином, «точка» P2 — це промінь R3.

Відповідно, два вектора R3 задають один і той же елемент в P2, якщо один з них може бути отриманий домножением другого на який-небудь скаляр (оскільки в цьому випадку вони лежать на одному промені):



Приміром, вектора (1, 1, 1) і (5, 5, 5) представляють один і той же промінь, а отже є однією і тією ж «точкою» в проективної площині.

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

Надалі ми будемо використовувати однорідні координати для подання афінних (містять переміщення) трансформацій і проектування. Але до цього потрібно вирішити ще одне питання: яким чином представити у вигляді однорідних координат вже дані нам вершини моделі? Оскільки «доповнення» до однорідних координат відбувається за рахунок додавання третьої координати w, питання зводиться до того, яке значення w нам необхідно використовувати. Відповідь на це питання — будь-яке не дорівнює нулю. Різниця у використанні різних значень w полягає в зручності роботи з ними.



І, як буде зрозуміло далі (і що почасти зрозуміло інтуїтивно), найзручнішим значенням w є одиниця. Переваги цього вибору такі:
  • Це дозволяє в більш природному вигляді представити переміщення у вигляді матриці (буде показано далі)
  • Після деяких трансформацій (включаючи перспективну проекцію) значення w буде довільним, і нам потрібно буде повернутися на обрану нами спочатку площину (тобто повернути спочатку вибране значення w):



    Якщо ця площина w = 1, нам досить буде поділити всі координати на w — в результаті, ми отримаємо одиницю в w координаті
Таким чином, ми вибираємо значення w = 1, а значить наші вхідні дані в однорідних координатах тепер будуть виглядати наступним чином (зрозуміло, одиниця вже буде додана нами, а не буде знаходитися в самому описі моделі):

v0 = (x0, y0, 1)
v1 = (x1, y1, 1)
v2 = (x2, y2, 1)

Тепер потрібно розглянути особливий випадок при роботі з w-координатою. А саме — її рівність нулю. Вище ми говорили, що ми можемо вибрати будь-яке значення w, не рівне нулю, для розширення до однорідних координат. Ми не може взяти w = 0, зокрема, тому, що це не дозволить переміщати цю точку (оскільки, як ми побачимо далі, переміщення відбувається саме за рахунок значення w координаті). Так само, якщо біля точки координата w — нульова, ми можемо розглядати її як точку «до нескінченності», оскільки при спробі повернутися на площину w = 1 ми отримаємо ділення на нуль:



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

У зв'язку з цим, часто пишуть, що при w = 1 ми описуємо точку, а при w = 0 — вектор.

Як я вже писав, ми використовували приклад двомірних проективних проективних просторів, але дійсно будемо використовувати тривимірні проективні простору, а значить кожна точка буде описуватися 4-ма координатами: (x, y, z, w).

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



Ми так само можемо використовувати 4 х 4 матриці для опису афінних трансформацій, використовуючи однорідні координати:



Розглянемо результат множення вектора, представленого у вигляді однорідних координат, та множення на 4 x 4 матрицю:





Як видно, на відміну від трансформації, представленої у вигляді 3 x 3 матриця, полягає в наявності 4-ї координати, а так само нових складових в кожній з координат виду vw · m3i. Використовуючи це, і маючи на увазі w = 1, ми можемо уявити переміщення наступним чином:



Тут можна переконатися в правильності вибору w = 1. Для подання зміщення dx ми використовуємо доданок виду w · dx / w. Відповідно, останній рядок матриці виглядає як (dx/w, dy/w, dz/w, 1). У разі w = 1 ми можемо просто опустити знаменник.

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

Опис віртуальної камери

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

Параметри камери ставлять усічену піраміду огляду (view frustum), яка визначає, яка частина сцени потрапить в підсумкове зображення:



Розглянемо їх по черзі:

  • Розташування та орієнтація камери в просторі. Положення, очевидно, просто точка. Описати орієнтацію можна різними способами. Я буду використовувати так звану «UVN» систему, тобто орієнтація камери описується положенням пов'язаної з нею системою координат. Зазвичай, осі в ній називаються u, v n (тому і така назва), але я буду використовувати right, up forward — з цих назв простіше зрозуміти, чому відповідає кожна вісь. Ми будемо використовувати лівобічну систему координат.



    При створенні об'єкта камери в API можна описувати всі три осі — але це дуже незручно для користувача. Найчастіше, користувач знає, в якому напрямку повинна дивитися камера, а так само приблизну орієнтацію вектора up (будемо називати цей вектор up'). Використовуючи ці два значення ми може побудувати правильну систему координат для камери за наступним алгоритмом:

    • Обчислюємо вектор right використовуючи вектора forward up' за допомогою векторного добутку:
    • Тепер обчислюємо коректний up, використовуючи right forward:
    Тобто, вектор up' разом forward задають площину, в якій повинен бути розташований цей вектор up. Якщо у вас є досвід використання OpenGL, то саме за таким алгоритмом працює відома функція gluLookAt.

    Важливо не забути нормалізувати отримані в результаті вектора — нам потрібна ортонормована система координат, оскільки її зручніше використовувати у подальшому

  • z-координати ближньої і дальньої площин відсікання (near/far clipping plane) в системі координат камери

  • Кути огляду камери. Вони задають розміри усіченої піраміди огляду:



    Оскільки сцена надалі буде спроецирована на площину проекції, то зображення на цій площині надалі буде відображено на екрані комп'ютера. Тому важливо, щоб співвідношення сторін у цій площині і вікна (або його частини), у якому буде показано зображення, збігалися. Цього можна досягти, надавши користувачу API можливість задавати тільки один кут огляду, а другий обчислювати в відповідності із співвідношенням сторін вікна. Наприклад, знаючи горизонтальний кут огляду, ми можемо обчислити вертикальний наступним чином:



    Коли ми обговорювали центральну проекцію, ми бачили, що чим далі знаходиться площину проекції від камери, тим більше розмір отриманого зображення — ми позначали відстань від камери (вважаючи, що вона розташована в початку координат) вздовж осі z до площини проекції змінної d. Відповідно слід вирішити питання, яке значення d нам необхідно вибрати. Насправді, будь-яке ненульове. Незважаючи на те, що розмір зображення збільшується при збільшенні d, пропорційно збільшується і та частина площини проекції, яка перетинається з пірамідою огляду, залишаючи одним і тим же масштаб зображення щодо розмірів цієї частини площини. Надалі ми будемо використовувати d = 1 для зручності.

    Приклад в 2D:



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


Ми можемо рухати і повертати камеру, змінюючи положення та орієнтацію її системи координат. Приклад коду:
Прихований текст
void camera::move_right(float distance)
{
m_position += m_right * distance;
}

void camera::move_left(const float distance)
{
move_right(-distance);
}

void camera::move_up(const float distance)
{
m_position += m_up * distance;
}

void camera::move_down(const float distance)
{
move_up(-distance);
}

void camera::move_forward(const float distance)
{
m_position += m_forward * distance;
}

void camera::move_backward(const float distance)
{
move_forward(-distance);
}

void camera::yaw(const float radians)
{
matrix3x3 const rotation{matrix3x3::rotation_around_y_axis(radians)};
m_forward = m_forward * rotation;
m_right = m_right * rotation;
m_up = m_up * rotation;
}

void camera::pitch(const float radians)
{
matrix3x3 const rotation{matrix3x3::rotation_around_x_axis(radians)};
m_forward = m_forward * rotation;
m_right = m_right * rotation;
m_up = m_up * rotation;
}


Графічний конвеєр

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

Вхідні параметрів конвеєра:
  • Об'єкт і його орієнтація у світовій системі координат
  • Камера, чиї параметри ми будемо використовувати при складанні зображення
1. Перехід у світову систему координат
На цій стадії ми трансформуємо вершини об'єкта з локальної системи координат у світову.

Припустимо, що орієнтація об'єкта у світовій системі координат задається наступними параметрами:
  • В якій точці у світовій системі координат знаходиться об'єкт: (xworld, yworld, zworld)
  • Яким чином об'єкт повернений: (rx, ry, rz)
  • Масштаб об'єкта: (sx, sy, sz)
Назвемо матриці цих трансформацій T, R S відповідно. Для одержання підсумкової матриці, яка буде трансформувати об'єкт у світову систему координат, нам достатньо перемножити їх. Тут важливо зауважити, що порядок перемноження матриць грає роль — це безпосередньо випливає з того факту, що множення матриць некоммутативно.

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



Аналогічне правило застосовується і відносно обертання — воно відбувається відносно початку координат, а значить стан об'єкта зміниться, якщо ми спочатку зробимо переміщення. Та ж логіка працює і для пари трансформацій «поворот — поворот».

Таким чином, коректна послідовність у нашому випадку виглядає наступним чином: масштабування — поворот — зміщення:



2. Перехід в систему координат камери
Перехід в систему координат камери, зокрема, використовується для спрощення подальших обчислень. В цій системі координат камера розташована в початку координат, а її осі — вектора forward, right, up, які ми розглядали в попередньому розділі.

Перехід в систему координат камери складається з двох кроків:
  • Переміщуємо світ таким чином, щоб положення камери збігалося з початком координат
  • Використовуючи обчислені осі right, up, forward, обчислюємо координати вершин об'єкта вздовж цих осей (цей крок можна розглядати як поворот системи координат камери таким чином, щоб вона збігалася з світовою системою координат)
Перший крок легко можна представити у вигляді матриці переміщення на (-posx, -posy, -posz), pos — положення камери у світовій системі координат:



Для реалізації другого пункту ми скористаємося властивістю скалярного добутку, яке ми розглядали в самому початку — скалярний добуток обчислює довжину проекції вздовж заданої осі. Таким чином, для того щоб перевести точку A в систему координат камери (з урахуванням того, що камера знаходиться в початку координат — ми зробили це в першому пункті), нам достатньо взяти її скалярний твір з векторами right, up, forward. Позначимо точку у світовій системі координат v, а цю ж точку, перекладену в систему координат камери, v', тоді:



Цю операцію можна представити у вигляді матриці:



Комбінуючи ці дві трансформації, ми одержуємо матрицю переходу в систему координат камери:



Схематично цей процес можна зобразити наступним чином:



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



Обидві ці завдання частково вирішує матриця проекції (projection matrix). «Частково» — тому що вона не виробляє саму проекцію, але готує w-координату вершини для цього. З-за цього назву «матриця проекції» звучить не дуже слушно (хоча це досить поширений термін), і я буду надалі називати її матрицею відсікання (clip matrix), оскільки вона так само виробляє відображення усіченої піраміди огляду в однорідне простір відсікання (homogeneous clip space).

Але про все по порядку. Отже, перше — підготовка до проекції. Для цього ми кладемо z-координату вершини в її w-координату. Сама проекція (тобто поділ на z) буде відбуватися при подальшій нормалізації w-координати — тобто при поверненні в простір w = 1.

Наступне, що повинна зробити ця матриця — це перевести координати вершин об'єкта з простору камери в однорідне простір відсікання (homogeneous clip space). Це простір, координати не відтяті вершин у якому такі, що після застосування проекції (тобто поділу на w-координату, оскільки в ній ми зберегли стару z-координату) координати вершини нормалізуються, тобто задовольняють наступним умовам:



Нерівність для z-координати може відрізнятися для різних API. Наприклад, в OpenGL воно відповідає тому, що вище. В Direct3D ж z-координата відображається в інтервал [0, 1]. Ми будемо використовувати прийнятий в OpenGL інтервал, тобто [-1, 1].
Подібні координати називаються нормализованными координатами пристрою (normalized device coordinates або просто NDC).

Оскільки ми отримуємо NDC-координати поділивши координати на w, вершини в просторі відсікання задовольняють наступним умовам:



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



Отже, даний етап складається з таких кроків:
  • Отримуємо вершини в просторі камери
  • Домножаем на матрицю відсікання — переходимо в простір відсікання
  • Помічаємо відтяті вершини, перевіряючи по нерівностям описаним вище
  • Ділимо координати кожної вершини на її w-координату — переходимо до нормалізованим координатами
Тепер розглянемо, яким чином ми відображаємо координати простору камери в простір відсікання. Згадаємо, що ми вирішили використовувати площину проекції z=1. Для початку нам потрібно знайти функцію, яка відображає координати, що лежать на перетині піраміди огляду і площини проекції в інтервал [-1, 1]. Для цього знайдемо координати точок, що визначають цю частину площини. Ці дві точки мають координати (left, top) (right, bottom). Ми будемо розглядати тільки випадок, коли піраміда огляду симетрична відносно напрямку камери.



Ми можемо їх обчислити, використовуючи кути огляду:



Отримуємо:



Аналогічно для top bottom:



Таким чином, нам потрібно відобразити інтервал [left, right], [bottom, top], [near, far] [-1; 1]. Знайдемо лінійну функцію, яка дає такий результат для left right:



Аналогічно виходить функція для right top:



Вираз для z знаходиться по-іншому. Замість того, щоб розглядати функцію виду az + b ми будемо розглядати функцію a · 1/z + b, тому що надалі, коли ми будемо реалізовувати буфер глибини, нам потрібно буде лінійно інтерполювати величину, зворотну z-координати. Ми не будемо розглядати це питання зараз, і просто приймемо це за дане. Отримаємо:



Таким чином, ми можемо записати, що нормалізовані координати виходять наступним чином координат у просторі камери:



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



Саме за цими формулами ми і проводимо трансформацію в простір відсікання. Ми можемо записати цю трансформацію в матричній формі (додатково згадавши, що в w-координату ми кладемо z):



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



Це відображення (viewport transformation) можна зробити за допомогою простих формул:



Або в матричній формі:



Ми залишимо використання zndc до реалізації буфера глибини.

В результаті у нас є координати вершин на екрані, які ми і використовуємо для відтворення.

Реалізація в коді
Нижче наведено приклад коду, який реалізує конвеєр з описаним вище способом і виробляє відображення в wireframe-режимі (тобто просто поєднуючи вершини лініями). У ньому так само мається на увазі, що об'єкт описаний набором вершин і набором індексів вершин (faces), з яких складаються його полігони:
Прихований текст
void pipeline::draw_mesh(
std::shared_ptr<mesh const> mesh,
vector3 const& position,
vector3 const& rotation,
camera const& camera,
bitmap_painter& painter) const
{
matrix4x4 const local_to_world_transform{
matrix4x4::rotation_around_x_axis(rotation.x) *
matrix4x4::rotation_around_y_axis(rotation.y) *
matrix4x4::rotation_around_z_axis(rotation.z) *
matrix4x4::translation(position.x position.y position.z)};

matrix4x4 const camera_rotation{
camera.get_right().x, camera.get_up().x, camera.get_forward().x, 0.0 f,
camera.get_right().y, camera.get_up().y, camera.get_forward().y, 0.0 f,
camera.get_right().z, camera.get_up().z, camera.get_forward().z, 0.0 f,
0.0 f, 0.0 f, 0.0 f, 1.0 f};
matrix4x4 const camera_translation{
1.0 f, 0.0 f, 0.0 f, 0.0 f,
0.0 f, 1.0 f, 0.0 f, 0.0 f,
0.0 f, 0.0 f, 1.0 f, 0.0 f,
-camera.get_position().x, -camera.get_position().y, -camera.get_position().z, 1.0 f};
matrix4x4 const world_to_camera_transform{camera_translation * camera_rotation};

const float projection_plane_z{1.0 f};
const float near{camera.get_near_plane_z()};
const float far{camera.get_far_plane_z()};
const float right{std::tan(camera.get_horizontal_fov() / 2.0 f) * projection_plane_z};
const float left{-right};
const float top{std::tan(camera.get_vertical_fov() / 2.0 f) * projection_plane_z};
const float bottom{-top};
matrix4x4 const camera_to_clip_transform{
2.0 f * projection_plane_z / (right - left), 0.0 f, 0.0 f, 0.0 f,
0.0 f, 2.0 f * projection_plane_z / (top - bottom), 0.0 f, 0.0 f,
(left + right) / (left - right), (bottom + top) / (bottom - top), (far + near) / (far - near), 1.0 f,
0.0 f, 0.0 f, -2.0 f * near * far / (far - near), 0.0 f};

matrix4x4 const local_to_clip_transform{
local_to_world_transform * world_to_camera_transform * camera_to_clip_transform};

std::vector<vector4> transformed_vertices;
for (vector3 const& v : mesh->get_vertices())
{
vector4 v_transformed{vector4{v.x, v.y, v.z, 1.0 f} * local_to_clip_transform};

if ((v_transformed.x > v_transformed.w) || (v_transformed.x < -v_transformed.w))
{
mark_vector4_as_clipped(v_transformed);
}
else if ((v_transformed.y > v_transformed.w) || (v_transformed.y < -v_transformed.w))
{
mark_vector4_as_clipped(v_transformed);
}
else if ((v_transformed.z > v_transformed.w) || (v_transformed.z < -v_transformed.w))
{
mark_vector4_as_clipped(v_transformed);
}

transformed_vertices.push_back(v_transformed);
}

const float width{static_cast<float>(painter.get_bitmap_width())};
const float height{static_cast<float>(painter.get_bitmap_height())};
matrix4x4 const ndc_to_screen{
width / 2.0 f, 0.0 f, 0.0 f, 0.0 f,
0.0 f, -height / 2.0 f, 0.0 f, 0.0 f,
0.0 f, 0.0 f, 1.0 f, 0.0 f,
width / 2.0 f, height / 2.0 f, 0.0 f, 1.0 f};

for (vector4& v : transformed_vertices)
{
if (is_vector4_marked_as_clipped(v))
{
continue;
}

const float w_reciprocal{1.0 f / v.w};

v.x *= w_reciprocal;
v.y *= w_reciprocal;
v.z *= w_reciprocal;
v.w = 1.0 f;

v = v * ndc_to_screen;
}

for (face const& f : mesh->get_faces())
{
vector4 const& v1{transformed_vertices[f.index1]};
vector4 const& v2{transformed_vertices[f.index2]};
vector4 const& v3{transformed_vertices[f.index3]};

const bool v1_clipped{is_vector4_marked_as_clipped(v1)};
const bool v2_clipped{is_vector4_marked_as_clipped(v2)};
const bool v3_clipped{is_vector4_marked_as_clipped(v3)};

if (!v1_clipped && !v2_clipped)
{
painter.draw_line(
point2d{static_cast<unsigned int>(v1.x), static_cast<unsigned int>(v1.y)},
point2d{static_cast<unsigned int>(v2.x), static_cast<unsigned int>(v2.y)},
color{255, 255, 255});
}

if (!v3_clipped && !v2_clipped)
{
painter.draw_line(
point2d{static_cast<unsigned int>(v2.x), static_cast<unsigned int>(v2.y)},
point2d{static_cast<unsigned int>(v3.x), static_cast<unsigned int>(v3.y)},
color{255, 255, 255});
}

if (!v1_clipped && !v3_clipped)
{
painter.draw_line(
point2d{static_cast<unsigned int>(v3.x), static_cast<unsigned int>(v3.y)},
point2d{static_cast<unsigned int>(v1.x), static_cast<unsigned int>(v1.y)},
color{255, 255, 255});
}
}
}


Приклад використання SDL2 для реалізації

У цьому розділі я коротко розповім, як можна використовувати SDL2 для реалізації відтворення.

Ініціалізація, створення текстури
Перше — це, природно, ініціалізація бібліотеки та створення вікна. Якщо від SDL потрібна тільки графіка, то можна ініціалізувати з прапором SDL_INIT_VIDEO:
Прихований текст
if (SDL_Init(SDL_INIT_VIDEO) < 0)
{
throw std::runtime_error(SDL_GetError());
}

m_window = SDL_CreateWindow(
"lantern",
SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED,
width, height,
SDL_WINDOW_SHOWN);
if (m_window == nullptr)
{
throw std::runtime_error(SDL_GetError());
}

m_renderer = SDL_CreateRenderer(m_window, -1, SDL_RENDERER_ACCELERATED);
if (m_renderer == nullptr)
{
throw std::runtime_error(SDL_GetError());
}


Потім, створюємо структуру, в яку будемо проводити обробку. Я буду використовувати формат ARGB8888, який означає, що на кожен піксель в текстурі буде виділятися 4 байти — три байти на RGB-канали, і один альфа-канал.
Прихований текст
m_target_texture = SDL_CreateTexture(
m_renderer,
SDL_PIXELFORMAT_ARGB8888,
SDL_TEXTUREACCESS_STREAMING,
width, height);
if (m_target_texture == nullptr)
{
throw std::runtime_error(SDL_GetError());
}


Потрібно не забути провести «очищення» SDL і всіх узятих у нього змінних при виході додатки:
Прихований текст
if (m_target_texture != nullptr)
{
SDL_DestroyTexture(m_target_texture);
m_target_texture = nullptr;
}

if (m_renderer != nullptr)
{
SDL_DestroyRenderer(m_renderer);
m_renderer = nullptr;
}

if (m_window != nullptr)
{
SDL_DestroyWindow(m_window);
m_window = nullptr;
}

SDL_Quit();


Відтворення, відображення на екрані
Ми можемо використовувати SDL_UpdateTexture для оновлення текстури, яку ми потім відобразимо на екрані. Ця функція приймає, крім інших, такі параметри:
  • Дані — масив байт, який представляє собою масив пікселів з відповідними значеннями
  • Кількість байт в одному рядку зображення (pitch) — обчислюється як кількість пікселів, помножене на 4 (тому що формат — ARGB8888)
Логічно виділити функціонал малювання в текстуру, представлену масив байт, в окремий клас. Він буде виділяти пам'ять під масив, очищати текстуру, малювати пікселі і лінії. Малювання пікселя може бути зроблено наступним чином (порядок байт розрізняється залежно від SDL_BYTEORDER):
Прихований текст
void bitmap_painter::draw_pixel(point2d const& point, color const& c)
{
unsigned int const pixel_first_byte_index{m_pitch * point.y + point.x * 4};

#if SDL_BYTEORDER == SDL_BIG_ENDIAN
m_data[pixel_first_byte_index + 0] = c.b;
m_data[pixel_first_byte_index + 1] = c.g;
m_data[pixel_first_byte_index + 2] = c.r;
// m_data[pixel_first_byte_index + 3] is alpha, we don't use it for now
#else
// m_data[pixel_first_byte_index + 0] is alpha, we don't use it for now
m_data[pixel_first_byte_index + 1] = c.r;
m_data[pixel_first_byte_index + 2] = c.g;
m_data[pixel_first_byte_index + 3] = c.b;
#endif
}


Малювання ліній можна реалізувати, наприклад, за алгоритмом Брезенхэма.

Після використання SDL_UpdateTexture, необхідно скопіювати текстуру SDL_Renderer і відобразити на екрані за допомогою SDL_RenderPresent. Всі разом:
Прихований текст
SDL_UpdateTexture(m_target_texture, nullptr, m_painter.get_data(), m_painter.get_pitch());
SDL_RenderCopy(m_renderer, m_target_texture, nullptr, nullptr);
SDL_RenderPresent(m_renderer);


На цьому все. Посилання на проект: https://github.com/loreglean/lantern.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.