- Статья 1: алгоритм Брезенхэма
- Статья 2: растеризация треугольника + отсечение задних граней
- Статья 3: Удаление невидимых поверхностей: z-буфер
Удаление невидимых поверхностей.
Знакомьтесь, это мой друг z-buffer головы абстрактного африканца. Он нам поможет убрать визуальные артефакты отбрасывания задних граней, которые у нас оставались в прошлой статье.
Кстати, не могу не упомянуть, что эта модель, которую я использую в хвост и в гриву, была любезно предоставлена замечательным Vidar Rapp.
Мы её можем использовать исключительно в рамках обучения рендерингу. Это очень качественная модель, с которой я варварски обошёлся, но я обещаю вернуть ей глаза!
В теории можно не отбрасывать невидимые грани, а просто рисовать всё подряд, начав с самых задних, и заканчивая передними.
Это называется алгоритмом художника. К сожалению, он весьма затратен, на каждое изменение положения камеры нужно пересортировывать сцену. А бывают ещё и динамические сцены… Но даже не это основная проблема. Проблема в том, что не всегда это можно сделать.
Перед отрисовкой головы отрисуем что попроще
Давайте представим себе простейшую сцену из трёх треугольников, камера смотрит сверху вниз, мы проецируем наши треугольники на белый экран:
Вот так должен выглядеть рендер этой сцены.
Синяя грань — она за красной или перед? Ни то, ни то. Алгоритм художника здесь ломается. Ну, то есть, можно синюю грань разбить на две, одна часть перед красной, другая за. А та, что перед красной, ещё на две — перед зелёной и за зелёной… Думаю, достаточно ясно, что в сценах с миллионами треугольников это быстро становится непростой задачей. Да, у неё есть решения, например, пользоваться двоичными разбиениями пространства, заодно это помогает и для сортировки при смене положения камеры, но давайте не будем себе усложнять жизнь!
Три измерения — это слишком. Y-buffer!
Давайте потеряем одно из измерений, рассмотрим двумерную сцену, полученную пересечением нашей сцены и жёлтой плоскости разреза:
То есть, наша сцена состоит из трёх отрезков (пересечение жёлтой плоскости и каждого из треугольников), а её рендер — это картинка
той же ширины, что и нормальный рендер, но в один пиксель высотой:
Снимок кода, как обычно, на гитхабе. Поскольку у нас сцена двумерная, то её очень просто нарисовать, это просто три вызова функции line(), которую мы запрограммировали в самый первый раз.
{ // just dumping the 2d scene (yay we have enough dimensions!)
TGAImage scene(width, height, TGAImage::RGB);
// scene "2d mesh"
line(Vec2i(20, 34), Vec2i(744, 400), scene, red);
line(Vec2i(120, 434), Vec2i(444, 400), scene, green);
line(Vec2i(330, 463), Vec2i(594, 200), scene, blue);
// screen line
line(Vec2i(10, 10), Vec2i(790, 10), scene, white);
scene.flip_vertically(); // i want to have the origin at the left bottom corner of the image
scene.write_tga_file("scene.tga");
}
Вот так выглядит наша двумерная сцена, наша задача посмотреть на эти отрезки сверху.
Давайте теперь её рендерить. Напоминаю, рендер — это картинка шириной во всю сцену и высотой в один пиксель. В моём коде я её объявил высотой в 16, но это чтобы не ломать глаза, рассматривая один пиксель на экранах высокого разрешения. Функция rasterize пишет только в первую строчку картинки render.
TGAImage render(width, 16, TGAImage::RGB);
int ybuffer[width];
for (int i=0; i<width; i++) {
ybuffer[i] = std::numeric_limits<int>::min();
}
rasterize(Vec2i(20, 34), Vec2i(744, 400), render, red, ybuffer);
rasterize(Vec2i(120, 434), Vec2i(444, 400), render, green, ybuffer);
rasterize(Vec2i(330, 463), Vec2i(594, 200), render, blue, ybuffer);
Итак, я объявил загадочный массив ybuffer ровно в размер нашего экрана (width, 1). Этот массив инициализирован минус бесконечностью. Затем я передаю в функцию rasterize и картинку render, и этот загадочный массив. Как выглядит сама функция?
void rasterize(Vec2i p0, Vec2i p1, TGAImage &image, TGAColor color, int ybuffer[]) {
if (p0.x>p1.x) {
std::swap(p0, p1);
}
for (int x=p0.x; x<=p1.x; x++) {
float t = (x-p0.x)/(float)(p1.x-p0.x);
int y = p0.y*(1.-t) + p1.y*t;
if (ybuffer[x]<y) {
ybuffer[x] = y;
image.set(x, 0, color);
}
}
}
Очень-очень просто: я прохожу по всем x-координатам между p0.x и p1.x и вычисляю соответствующую y-координату нашей линии.
Затем я проверяю, что у нас в массиве ybuffer по этой координате x. Если текущий пиксель ближе к камере, нежели то, что там сохранено,
то я и его рисую в картинке, и ставлю новую y-координату в игрек-буфере.
Давайте разбираться поэтапно: после вызова растеризатора для первой (красной) линии вот что мы имеем в памяти:
содержимое экрана:
содержимое y-буфера:
Здесь мерзким фиолетовым цветом отмечена минус бесконечность, это те места, где ни одного пикселя ещё нарисовано не было.
Всё остальное градациями серого, т.к. ybuffer это не цвет, а глубина данного пикселя. Чем белее, тем ближе к камере был данный нарисованный на экране пиксель.
Дальше мы рисуем зелёную линию, вот память после вызова её растеризатора:
содержимое экрана:
содержимое y-буфера:
Ну и напоследок синюю:
содержимое экрана:
содержимое y-буфера:
Поздравляю вас, мы нарисовали нашу двумерную сцену! Ещё раз полюбуемся на финальный рендер:
Три измерения — это в самый раз. Z-buffer!
Снимок кода на гитхабе.
Внимание: в этой статье я использую ту же самую версию растеризатора треугольника, что и в предыдущей. Улучшенная версия растеризатора (проход всех пикселей описывающего прямоугольника) будет вскорости любезно предоставлена и описана в отдельной статье уважаемым gbg! Stay tuned.
Поскольку у нас экран теперь двумерный, то z-буфер тоже должен быть двумерным:
int *zbuffer = new int[width*height];
Я упаковал двумерный массив в одномерный, конвертировать можно как обычно:
из двух координат в одну:
int idx = x + y*width;
Обратно:
int x = idx % width; int y = idx / width;
Затем в коде я прохожу по всем треугольникам и делаю вызов растеризатора, передавая ему и картинку, и z-буфер.
triangle(screen_coords[0], screen_coords[1], screen_coords[2], image, TGAColor(intensity*255, intensity*255, intensity*255, 255), zbuffer);
[...]
void triangle(Vec3i t0, Vec3i t1, Vec3i t2, TGAImage &image, TGAColor color, int *zbuffer) {
if (t0.y==t1.y && t0.y==t2.y) return; // i dont care about degenerate triangles
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
Vec3i A = t0 + (t2-t0)*alpha;
Vec3i 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++) {
float phi = B.x==A.x ? 1. : (float)(j-A.x)/(float)(B.x-A.x);
Vec3i P = A + (B-A)*phi;
P.x = j; P.y = t0.y+i; // a hack to fill holes (due to int cast precision problems)
int idx = j+(t0.y+i)*width;
if (zbuffer[idx]<P.z) {
zbuffer[idx] = P.z;
image.set(P.x, P.y, color); // attention, due to int casts t0.y+i != A.y
}
}
}
}
Это просто ужасно, насколько код похож на растеризатор из прошлой статьи. Что изменилось? (Используйте vimdiff и посмотрите :) )
Vec2 был заменён на Vec3 в вызове функции и сделана проверка if (zbuffer[idx]<P.z);
Всё! Вот наш настоящий рендер без огрехов отсечения невидимых поверхностей:
Обратите внимание, что backface culling в моём коде оставлен:
if (intensity>0) {
triangle(screen_coords[0], screen_coords[1], screen_coords[2], image, TGAColor(intensity*255, intensity*255, intensity*255, 255), zbuffer);
}
Он не является необходимым для получения этой картинки, это только ускорение вычислений.
Стоп, мы только что интерполировали z-координату. А можно добавить ещё чего в нагрузку?
Текстуры! Это будет домашняя работа.
В .obj файле есть строчки vt u v, они задают массив текстурных координат.
Среднее число между слешами в f x/x/x x/x/x x/x/x — это текстурные координаты данной вершины в данном треугольнике. Интерполируете их внутри треугольника, умножаете на ширину-высоту текстурного файла и получаете цвет пикселя из файла текстуры.
Диффузную текстуру брать здесь.
Вот пример того, что должно получиться. Вращать голову не обязательно :)
Автор: haqreu
