Давайте знакомиться, это я.
То есть, модель моей башки, отрендеренная в программе, которую мы сделаем за ближайшие час-два.
В прошлый раз мы нарисовали проволочную сетку трёхмерной модели, в этот раз мы зальём полигоны. Точнее, треугольники, так как OpenGL практически любой полигон триангулирует, поэтому ни к чему разбирать сложный случай. Напоминаю, что этот цикл статей создан для самостоятельного программирования. Время, которое я здесь привожу — это не время чтения моего кода. Это время написания вашего кода с нуля. Мой код здесь только для того, чтобы сравнить ваш (рабочий) код с моим. Я совсем не являюсь хорошим программистом, поэтому ваш код может быть существенно лучше моего. Любая критика приветствуется, любым вопросам рад.
Пожалуйста, если вы следуете этому туториалу и пишете свой код, выкладывайте его на github.com/code.google.com и им подобные и давайте ссылки в комментариях! Это может хорошо помочь как и вам (другие люди могут чего посоветовать), так и будущим читателям.
Рисуем заполненный треугольник.
Итак, тема на сегодня (примерно на два часа для плохо программирующих, но мотивированных студентов): отрисовка двумерных треугольников. В прошлый раз мы разобрали алгоритм Брезенхэма для растеризации отрезка, теперь задача нарисовать заполненный треугольник. Вы будете смеяться, но это нетривиальная задача. Я не знаю почему, но я знаю, что это так. Большинство моих студентов без подсказок проводят над этой задачей существенно больше пары часов. Давайте определимся с методом, а затем будем программировать.
В самом начале давайте рассмотрим вот такой псевдокод:
triangle(vec2 points[3]) {
vec2 bbox[2] = find_bounding_box(points);
for (each pixel in the bounding box) {
if (inside(bbox, pixel)) {
put_pixel(pixel);
}
}
}
Я очень люблю этот метод. Он простой и рабочий. Найти описывающий прямоугольник крайне просто, проверить принадлежность точки двумерному треугольнику (да и любому выпуклому полигону) тоже просто.
Оффтоп: если мне нужно будет написать код, который будет крутиться на, скажем, самолёте, и этот код должен будет проверять принадлежность точки полигону, я никогда не сяду на этот самолёт. Это на удивление сложная проблема, если мы хотим её решить надёжно.
Почему я люблю этот код? Да потому, что, увидев такое, совсем новичок в программировании его воспримет с энтузиазмом, человек, немного знакомый с программированием, только самодовольно хмыкнет, мол, вот идиот писал. А эксперт в программировании компьютерной графики просто пожмёт плечами, мол, ну да, так оно и работает в реальной жизни. Массивно-параллельные вычисления в тысячах маленьких графических процессоров (я говорю про обычные потребительские компьютеры) творят чудеса. Но мы будем писать код под центральный процессор, поэтому этот метод использовать не будем. Да и какая разница, как оно там в кремнии, нашей абстракции вполне хватит для понимания принципа работы.
Окей, начальная заглушка будет выглядеть следующим образом:
void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) {
line(t0, t1, image, color);
line(t1, t2, image, color);
line(t2, t0, image, color);
}
[...]
Vec2i t0[3] = {Vec2i(10, 70), Vec2i(50, 160), Vec2i(70, 80)};
Vec2i t1[3] = {Vec2i(180, 50), Vec2i(150, 1), Vec2i(70, 180)};
Vec2i t2[3] = {Vec2i(180, 150), Vec2i(120, 160), Vec2i(130, 180)};
triangle(t0[0], t0[1], t0[2], image, red);
triangle(t1[0], t1[1], t1[2], image, white);
triangle(t2[0], t2[1], t2[2], image, green);
Как обычно, на гитхабе доступен отпечаток кода. В этом коде всё просто: я даю три треугольника для начальной отладки вашего кода; если внутри функции triangle просто сделать вызов line(), то получим контур треугольника. Как нарисовать заполненный треугольник?
Хороший метод отрисовки треугольника должен обладать следующими свойствами:
- Он должен быть (сюрприз) простым и быстрым
- Он должен быть симметричным: картинка не должна зависеть от порядка вершин, переданных в функцию отрисовки
- Если два треугольника имеют две общие вершины, между ними не должно быть дырок из-за округлений растеризации.
Требований можно добавлять гораздо больше, но мы довольствуемся этими тремя.
Традиционно используется line sweeping (заметание отрезком?):
- Сортируем вершины треугольника по их y-координате
- Растеризуем параллельно левую и правую границы треугольника
- Отрисовываем горзонтальный отрезок между левой и правой точкой границы
Тут мои студенты начинают теряться, кто левый, кто правый, да и вообще, в треугольнике три отрезка…
В этот момент я оставляю своих студентов примерно на час, чтение моего кода куда как менее ценно, нежели сравнение своего (выстраданного!) кода с моим.
[прошёл час]
Как рисую я? Ещё раз, если у вас есть лучший метод, то я его с огромным удовольствием возьму на вооружение. Давайте предположим, что у нас есть три точки треугольника, t0,t1,t2, они отсортированы по возрастанию y-координаты.
Тогда граница А будет между t0 и t2, граница Б будет между t0 и t1, а затем между t1 и t2.
void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) {
// sort the vertices, t0, t1, t2 lower-to-upper (bubblesort yay!)
if (t0.y>t1.y) std::swap(t0, t1);
if (t0.y>t2.y) std::swap(t0, t2);
if (t1.y>t2.y) std::swap(t1, t2);
line(t0, t1, image, green);
line(t1, t2, image, green);
line(t2, t0, image, red);
}
Здесь у нас граница А нарисована красным, а граница Б зелёным.
Граница Б, к сожалению, составная. Давайте отрисуем нижнюю половину треугольника, разрезав его по горизонтали в точке излома границы Б.
void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) {
// sort the vertices, t0, t1, t2 lower-to-upper (bubblesort yay!)
if (t0.y>t1.y) std::swap(t0, t1);
if (t0.y>t2.y) std::swap(t0, t2);
if (t1.y>t2.y) std::swap(t1, t2);
int total_height = t2.y-t0.y;
for (int y=t0.y; y<=t1.y; y++) {
int segment_height = t1.y-t0.y+1;
float alpha = (float)(y-t0.y)/total_height;
float beta = (float)(y-t0.y)/segment_height; // be careful with divisions by zero
Vec2i A = t0 + (t2-t0)*alpha;
Vec2i B = t0 + (t1-t0)*beta;
image.set(A.x, y, red);
image.set(B.x, y, green);
}
}
Заметьте, что в этот раз у меня получились разрывные отрезки. В отличие от прошлого раза (где мы рисовали прямые) я не заморочился поворотом изображения на 90°. Почему? Это оказывается не всем очевидным моментом. Просто если мы соединим горизонтальными линиями соответствующие пары точек, то пробелы пропадут:
Теперь осталось отрисовать вторую половину треугольника. Это можно сделать, добавив второй цикл:
void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) {
// sort the vertices, t0, t1, t2 lower-to-upper (bubblesort yay!)
if (t0.y>t1.y) std::swap(t0, t1);
if (t0.y>t2.y) std::swap(t0, t2);
if (t1.y>t2.y) std::swap(t1, t2);
int total_height = t2.y-t0.y;
for (int y=t0.y; y<=t1.y; y++) {
int segment_height = t1.y-t0.y+1;
float alpha = (float)(y-t0.y)/total_height;
float beta = (float)(y-t0.y)/segment_height; // be careful with divisions by zero
Vec2i A = t0 + (t2-t0)*alpha;
Vec2i B = t0 + (t1-t0)*beta;
if (A.x>B.x) std::swap(A, B);
for (int j=A.x; j<=B.x; j++) {
image.set(j, y, color); // attention, due to int casts t0.y+i != A.y
}
}
for (int y=t1.y; y<=t2.y; y++) {
int segment_height = t2.y-t1.y+1;
float alpha = (float)(y-t0.y)/total_height;
float beta = (float)(y-t1.y)/segment_height; // be careful with divisions by zero
Vec2i A = t0 + (t2-t0)*alpha;
Vec2i B = t1 + (t2-t1)*beta;
if (A.x>B.x) std::swap(A, B);
for (int j=A.x; j<=B.x; j++) {
image.set(j, y, color); // attention, due to int casts t0.y+i != A.y
}
}
}
На этом можно было бы успокоиться, но у меня случается несварение, когда я дважды вижу один и тот же код, да ещё так рядом. Поэтому сделаем его чуть менее читаемым, зато более простым для модификаций.
void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) {
if (t0.y==t1.y && t0.y==t2.y) return; // i dont care about degenerate triangles
// sort the vertices, t0, t1, t2 lower-to-upper (bubblesort yay!)
if (t0.y>t1.y) std::swap(t0, t1);
if (t0.y>t2.y) std::swap(t0, t2);
if (t1.y>t2.y) std::swap(t1, t2);
int total_height = t2.y-t0.y;
for (int i=0; i<total_height; i++) {
bool second_half = i>t1.y-t0.y || t1.y==t0.y;
int segment_height = second_half ? t2.y-t1.y : t1.y-t0.y;
float alpha = (float)i/total_height;
float beta = (float)(i-(second_half ? t1.y-t0.y : 0))/segment_height; // be careful: with above conditions no division by zero here
Vec2i A = t0 + (t2-t0)*alpha;
Vec2i B = second_half ? t1 + (t2-t1)*beta : t0 + (t1-t0)*beta;
if (A.x>B.x) std::swap(A, B);
for (int j=A.x; j<=B.x; j++) {
image.set(j, t0.y+i, color); // attention, due to int casts t0.y+i != A.y
}
}
}
Отпечаток кода для отрисовки 2d треугольников.
Рисуем модель
Мы умеем уже отрисовывать модель с пустыми треугольниками, давайте их зальём случайным цветом, это поможет нам проверить, насколько хорошо мы закодировали заполнение треугольников. Вот код.
for (int i=0; i<model->nfaces(); i++) {
std::vector<int> face = model->face(i);
Vec2i screen_coords[3];
for (int j=0; j<3; j++) {
Vec3f world_coords = model->vert(face[j]);
screen_coords[j] = Vec2i((world_coords.x+1.)*width/2., (world_coords.y+1.)*height/2.);
}
triangle(screen_coords[0], screen_coords[1], screen_coords[2], image, TGAColor(rand()%255, rand()%255, rand()%255, 255));
}
Всё просто: как и раньше, пробегаем по всем треугольникам, превращаем мировые координаты в экранные и рисуем треугольники. Подробное описание разных систем координат в последущих статьях. Должно получиться нечто вроде этого:
Плоская тонировка.
Давайте теперь убирать эти клоунские цвета и освещать нашу модель.
Капитан Очевидность: «При одной и той же итенсивности света полигон освещён максимально ярко, если свет ему перпендикулярен».
Давайте сравним:
Нулевую освещённость мы получим, если полигон параллелен вектору света.
Перефразируем: интенсивность освещённости равна скалярному произведению вектора света и нормали к данному треугольнику.
Нормаль к треугольнику может быть посчитана просто как векторное произведение двух его рёбер.
for (int i=0; i<model->nfaces(); i++) {
std::vector<int> face = model->face(i);
Vec2i screen_coords[3];
Vec3f world_coords[3];
for (int j=0; j<3; j++) {
Vec3f v = model->vert(face[j]);
screen_coords[j] = Vec2i((v.x+1.)*width/2., (v.y+1.)*height/2.);
world_coords[j] = v;
}
Vec3f n = (world_coords[2]-world_coords[0])^(world_coords[1]-world_coords[0]);
n.normalize();
float intensity = n*light_dir;
if (intensity>0) {
triangle(screen_coords[0], screen_coords[1], screen_coords[2], image, TGAColor(intensity*255, intensity*255, intensity*255, 255));
}
}
Но ведь скалярное произведение может быть отрицательным, что это означает? Это означает, что свет падает позади полигона. Если модель хорошая (обычно не наша забота, а 3д моделеров), то мы просто можем этот треугольник не рисовать. Это позволяет быстро убрать часть невидимых треугольников. В англоязычной литературе называется Back-face culling.
Модель моей головы выглядит детальнее? Ну так в ней четверть миллиона треугольников. Ничего, детали мы добавим позже, получив картинку, которую я дал для затравки в первой статье.
Обратите внимание, внутренняя полость рта нарисовалась поверх губ. Ну а что, такое быстрое отсечение невидимых треугольников убирает всё ненужное только для выпуклых моделей. Эти огрехи мы уберём в следующий раз, закодировав z-buffer.
Текущая версия рендерера.
Автор: haqreu
