Короткий курс копьютерной графіки, пишемо спрощений OpenGL своїми руками, стаття 1 з 6

Постановка завдання
Мета цього циклу статей — показати, як працює OpenGL, написавши його (сильно спрощений!) клон самостійно. На подив часто стикаюся з людьми, які не можуть подолати початковий бар'єр навчання OpenGL/DirectX. Таким чином, я підготував короткий цикл з шести лекцій, після якого мої студенти видають непогані рендери.

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



Я постараюся не перевалити за 500 рядків в кінцевому коді. Моїм студентам потрібно від 10 до 20 годин програмування, щоб почати видавати подібні рендери. На вхід отримуємо текстовий файл з полігональної сіткою + картинки з текстурами, на вихід отрендеренную модель. Ніякого графічного інтерфейсу, що запускається програма просто генерує файл з картинкою.

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

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

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

Весь код доступний на гітхабі, тут знаходиться початковий код, який я даю своїм студентам.

#include "tgaimage.h"

const TGAColor white = TGAColor(255, 255, 255, 255);
const TGAColor red = TGAColor(255, 0, 0, 255);

int main(int argc, char** argv) {
TGAImage image(100, 100, TGAImage::RGB);
image.set(52, 41, red);
image.flip_vertically(); // i want to have the origin at the left bottom corner of the image
image.write_tga_file("output.tga");
return 0;
}

output.tga повинен виглядати приблизно так:



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

Як виглядає найпростіший код, який малює відрізок між двома точками (x0, y0) і (x1, y1)?
Мабуть, якось так:

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
for (float t=0.; t<1.; t+=.01) {
int x = x0*(1.-t) + x1*t;
int y = y0*(1.-t) + y1*t;
image.set(x, y, color);
}
}



Снапшот коду доступний на гітхабі.




Проблема цього коду (крім ефективності) це вибір константи, яку я взяв рівною .01.
Якщо раптом ми візьмемо її рівною .1, то наш відрізок буде виглядати ось так:



Ми легко можемо знайти потрібний крок: це просто кількість пікселів, які потрібно намалювати.
Найпростіший (з помилками!) код виглядає приблизно так:

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
for (int x=x0; x<=x1; x++) {
float t = (x-x0)/(float)(x1-x0);
int y = y0*(1.-t) + y1*t;
image.set(x, y, color);
}
}

Обережно: наипервейший джерело помилок в такому коді моїх студентів — це цілочисельне ділення типу (x-x0)/(x1-x0).

Далі, якщо ми спробуємо цим кодом намалювати ось такі лінії:

line(13, 20, 80, 40, image, white);
line(20, 13, 40, 80, image, red);
line(80, 40, 13, 20, image, red);



То з'ясується, що одна лінія хороша, друга з дірками, а третій зовсім немає.




Дірки в одному з сегментів з-за того, що його висота більше ширини.
Мої студенти часто мені пропонують такий фікс: if (dx>dy) {for (int x)} else {for (int y)}.
Ну ялинки!

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
bool steep = false;
if (std::abs(x0-x1)<std::abs(y0-y1)) { // if the line is steep, we the image transpose
std::swap(x0, y0);
std::swap(x1, y1);
steep = true;
}
if (x0>x1) { // make it left-to-right
std::swap(x0, x1);
std::swap(y0, y1);
}

for (int x=x0; x<=x1; x++) {
float t = (x-x0)/(float)(x1-x0);
int y = y0*(1.-t) + y1*t;
if (steep) {
image.set(y, x, color); // if transposed, de-transpose
} else {
image.set(x, y, color);
}
}
}






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

Отже, попередній код прекрасно працює, але він може бути оптимізовано.

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

Для тестів я малюю 1000000 разів 3 відрізки, які ми малювали перед цим. Мій процесор: is Intel® Core(TM) i5-3450 CPU @ 3.10 GHz.
Цей код для кожного пікселя викликає конструктор копіювання TGAColor.
А це 1000000 * 3 відрізка * приблизно 50 пикслей на відрізок. Чимало викликів.
Де почнемо оптимізацію?
Профайлер нам скаже.

Я откомпилировал код з ключами g++ -ggdb-g3-pg-O0; потім запустив gprof:

% cumulative self self total
time seconds seconds calls ms/call ms/call name
69.16 2.95 2.95 3000000 0.00 0.00 line(int, int, int, int, TGAImage&, TGAColor)
19.46 3.78 0.83 204000000 0.00 0.00 TGAImage::set(int, int, TGAColor)
8.91 4.16 0.38 207000000 0.00 0.00 TGAColor::TGAColor(TGAColor const&)
1.64 4.23 0.07 2 35.04 35.04 TGAColor::TGAColor(unsigned char, unsigned char, unsigned char, unsigned char)
0.94 4.27 0.04 TGAImage::get(int, int)

10% робочого часу — це копіювання кольору.
Але ще 70% проводяться у виклику line()! Тут і будемо оптимізувати.




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

Код доступний тут.

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
bool steep = false;
if (std::abs(x0-x1)<std::abs(y0-y1)) {
std::swap(x0, y0);
std::swap(x1, y1);
steep = true;
}
if (x0>x1){
std::swap(x0, x1);
std::swap(y0, y1);
}
int dx = x1-x0;
int dy = y1-y0;
float derror = std::abs(dy/float(dx));
float error = 0;
int y = y0;
for (int x=x0; x<=x1; x++) {
if (steep) {
image.set(y, x, color);
} else {
image.set(x, y, color);
}
error += derror;

if (error>.5) {
y += (y1>y0?1:-1);
error -= 1.;
}
}
}

% cumulative self self total
time seconds seconds calls ms/call ms/call name
38.79 0.93 0.93 3000000 0.00 0.00 line(int, int, int, int, TGAImage&, TGAColor)
37.54 1.83 0.90 204000000 0.00 0.00 TGAImage::set(int, int, TGAColor)
19.60 2.30 0.47 204000000 0.00 0.00 TGAColor::TGAColor(int, int)
2.09 2.35 0.05 2 25.03 25.03 TGAColor::TGAColor(unsigned char, unsigned char, unsigned char, unsigned char)
1.25 2.38 0.03 TGAImage::get(int, int)




А навіщо нам потрібні плаваючі точки? Єдина причина — це одне ділення на dx і порівняння з .5 в тілі циклу.
Ми можемо позбутися плаваючою точки, замінивши змінну error інший, назвемо її error2, вона дорівнює error*dx*2.
Ось еквівалентний код:

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
bool steep = false;
if (std::abs(x0-x1)<std::abs(y0-y1)) {
std::swap(x0, y0);
std::swap(x1, y1);
steep = true;
}
if (x0>x1) {
std::swap(x0, x1);
std::swap(y0, y1);
}
int dx = x1-x0;
int dy = y1-y0;
int derror2 = std::abs(dy)*2;
int error2 = 0;
int y = y0;
for (int x=x0; x<=x1; x++) {
if (steep) {
image.set(y, x, color);
} else {
image.set(x, y, color);
}
error2 += derror2;

if (error2 > dx) {
y += (y1>y0?1:-1);
error2 -= dx*2;
}
}
}

% cumulative self self total
time seconds seconds calls ms/call ms/call name
42.77 0.91 0.91 204000000 0.00 0.00 TGAImage::set(int, int, TGAColor)
30.08 1.55 0.64 3000000 0.00 0.00 line(int, int, int, int, TGAImage&, TGAColor)
21.62 2.01 0.46 204000000 0.00 0.00 TGAColor::TGAColor(int, int)
1.88 2.05 0.04 2 20.02 20.02 TGAColor::TGAColor(unsigned char, unsigned char, unsigned char, unsigned char)

Інша розмова, тепер достатньо прибрати непотрібні копії при виклику функції, передвая колір по посиланню (чи просто включивши прапор компіляції-O3) і все готово. Жодного множення, ні єдиного ділення в коді.
Час роботи знизилося з 2.95 секунди до 0.64.

Дротяний рендер.
Тепер все готово для створення дротяного рендера. Знімок коду і тестова модель тут.

Я використовував wavefront obj формат файлу для зберігання моделі. Все, що нам потрібно для рендера, це прочитати з файлу масив вершин виду

v 0.608654 -0.568839 -0.416318
[...]
це координати x,y,z, одна вершина на рядок файлу

і граней
f 1193/1240/1193 1180/1227/1180 1179/1226/1179
[...]

Тут нас цікавлять перше число після кожного пробілу, це номер вершини в масиві, який ми прочитали раніше. Таким чином ця строчка каже, що вершини 1193, і 1179 1180 утворюють трикутник.

Файл model.cpp містить простий парсер.

Пишемо такий цикл в наш main.cpp і вуаля, наш дротяний рендер готовий.

for (int i=0; i<model->nfaces(); i++) {
std::vector < int> face = model->face(i);
for (int j=0; j < 3; j++) {
Vec3f v0 = model->vert(face[j]);
Vec3f v1 = model->vert(face[(j+1)%3]);
int x0 = (v0.x+1.)*width/2.;
int y0 = (v0.y+1.)*height/2.;
int x1 = (v1.x+1.)*width/2.;
int y1 = (v1.y+1.)*height/2.;
line(x0, y0, x1, y1, image, white);
}
}



Наступного разу будемо малювати 2D трикутники і попдравлять наш рендер.

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

0 коментарів

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