Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Статьи / Основы 3D математики: Rendering.

Основы 3D математики: Rendering.

Автор:

Для начала, следует упомянуть, что вся отрисовка (рендеринг) полигона строится на линейной интерполяции.

1. Рендеринг одноцветного треугольника.

Треугольник на экране можно представить как набор горизонтальных отрезков, в силу его выпуклости. Т.к. любой полигон можно разбить на треугольники, обычно так и делается: сначала идет триангуляция полигона, т.е. разбивка его на треугольники, а только затем последовательная их отрисовка.

Нам требуется последовательно отрисовать все эти отрезки, сверху-вниз, последовательно их проходя и отрисовывая; главная проблема, с которой мы можем столкнуться, это как найти координаты точки пересечения стороны треугольника и линии, которую мы рассматриваем.

Исходя из формулы, задающей прямую (x = k*y + b), сравнительно просто получить необходимую нам формулу: x = Ax+(y-Ay)*(Bx-Ax)/(By-Ay), где x, y - координаты точки пересечения скан-линии и стороны треугольника.

Очевидно, что x изменяется линейно, и можно просто найти величину, на сколько изменяется x при увеличении y на единицу для каждого отрезка, что ускорит отрисовку.


Изображение Изображение Изображение

Далее - тривиальное решение задачи: интерполируем y скан-линии от верхней y-координаты треугольника до нижней, узнаем, какие стороны треугольника пересекает на данный момент скан-линия, находим x-координаты для каждой из сторон (левой и правой), и рисуем нужный нам отрезок, одним концом которого будет пересечение скан-линии с одной стороной, а другим - пересечением скан-линии с другой стороной треугольника.

вот кусок кода для пояснения:

typedef struct {                                            // тип вершина
  float x, y;                                               // координаты вершины на плоскости
} vertex;

vertex *a, *b, *c;                                          // вершины треугольника
vertex *d;                                                  // вершина для сортировки по y
int y;                                                      // y-координата скан-линии
float x1, x2, x3;                                           // левая и правая x-координаты отрезка скан-линии, 
                                                            // x3 - переменная для сортировки x1 и x2

void draw_triangle_flat();
 if (a->y > b->y) {d = a; a = b; b = d;}                    // сортировка по y
 if (a->y > c->y) {d = a; a = c; c = d;}
 if (b->y > c->y) {d = b; b = c; c = d;}

 if ((int)a->y == (int)c->y) return;                        // отметаем частный случай, если высота = 0

 for (y = (int)a->y; y <= (int)c->y; y++) {                 // цикл отрисовки грани
  x1 = a->x + (c->x - a->x) * (y - a->y) / (c->y - a->y);   // получаем x-координату самой длинной стороны
  
  if (y >= b->y) {                                          // выясняем, какую сторону проходит скан-линия,
    x2 = b->x + (c->x - b->x) * (y - b->y) / (c->y - b->y); // и вычисляем ее x-координату
   } else {
    x2 = a->x + (b->x - a->x) * (y - a->y) / (b->y - a->y);
  }
 
  if (x1 > x2) {x3 = x1; x1 = x2; x2 = x3;}                 // x1 - слева, x2 - cправа
 
  // отрисовываем отрезок, лежащий на прямой y с концами x1 и x2
  //  .......
 
 }
}

2. Аффинное текстурирование треугольника.

На самом деле, все остается точно таким же, за исключением того, что мы теперь будем изменять не только x-координату, но и координаты в текстуре (принято их обозначать u,v), которые соответствуют координатам на экране. Т.к. данный тип текстурирования называется аффинным, что в переводе ни что иное, как "линейный", очевидно, что и координаты u,v также будут линейно зависеть от изменения y-координаты скан-линии.

Таким образом, все остается на своих местах, меняются только названия переменных :), добавится только то, что координаты u и v будут линейно изменятся не только при увеличении y-координаты, но и в строке, при отрисовке, так что придется нам ввести еще одну переменную: на сколько увеличиваются u и v координаты при увеличении координаты x на 1.

Вычисляется она так:

 x1 = a->x + (c->x - a->x) * (b->y - a->y) / (c->y - a->y);
 u1 = a->u + (c->u - a->u) * (b->y - a->y) / (c->y - a->y);
 v1 = a->v + (c->v - a->v) * (b->y - a->y) / (c->y - a->y);
 x2 = b->x;
 u2 = b->u;
 v2 = b->v;
 du = (u1 - u2) / (x1 - x2);
 dv = (v1 - v2) / (x1 - x2);

На самом деле, можно было вычислить Du/Dx и Dv/Dx и на любой другой линии, но на линии, один конец которой - точка B это сделать проще, т.к. потребуется вычислить координаты 1й точки вместо 2х.

вот кусок кода для пояснения:

typedef struct {                                            // тип вершина
  float x, y;                                               // координаты вершины на плоскости
  float u, v;                                               // координаты в текстуре
} vertex;

vertex *a, *b, *c;                                          // вершины треугольника
vertex *d;                                                  // вершина для сортировки по y
int x, y;                                                   // координаты точки в скан-линии
float u, v;                                                 // текущие координаты в текстуре
float du, dv;                                               // на сколько изменятся координаты в текстуре
                                                            // при изменении x на 1
float u1, v1, u2, v2, u3, v3;                               // координаты в текстуре левой и правой сторон 
                                                            // отрезка, переменные для сортировки
float x1, x2, x3;                                           // левая и правая x-координаты отрезка скан-линии, 
                                                            // x3 - переменная для сортировки x1 и x2

void draw_triangle_affine();
 if (a->y > b->y) {d = a; a = b; b = d;}                    // сортировка по y
 if (a->y > c->y) {d = a; a = c; c = d;}
 if (b->y > c->y) {d = b; b = c; c = d;}

 if ((int)a->y == (int)c->y) return;                        // отметаем частный случай, если высота = 0

 x1 = a->x + (c->x - a->x) * (b->y - a->y) / (c->y - a->y); // получаем du, dv
 u1 = a->u + (c->u - a->u) * (b->y - a->y) / (c->y - a->y);
 v1 = a->v + (c->v - a->v) * (b->y - a->y) / (c->y - a->y);
 x2 = b->x;
 u2 = b->u;
 v2 = b->v;
 du = (u1 - u2) / (x1 - x2);
 dv = (v1 - v2) / (x1 - x2);

 for (y = (int)a->y; y <= (int)c->y; y++) {                 // цикл отрисовки грани
  x1 = a->x + (c->x - a->x) * (y - a->y) / (c->y - a->y);   // получаем x-координату самой длинной стороны
  u1 = a->u + (c->u - a->u) * (y - a->y) / (c->y - a->y);   // получаем u-координату
  v1 = a->v + (c->v - a->v) * (y - a->y) / (c->y - a->y);   // получаем v-координату
  
  if (y >= b->y) {                                          // выясняем, какую сторону проходит скан-линия,
    x2 = b->x + (c->x - b->x) * (y - b->y) / (c->y - b->y); // и вычисляем ее x-координату
    u2 = b->u + (c->u - b->u) * (y - b->y) / (c->y - b->y); //                u-координату
    v2 = b->v + (c->v - b->v) * (y - b->y) / (c->y - b->y); //                v-координату
   } else {
    x2 = a->x + (b->x - a->x) * (y - a->y) / (b->y - a->y);
    u2 = a->u + (b->u - a->u) * (y - a->y) / (b->y - a->y);
    v2 = a->v + (b->v - a->v) * (y - a->y) / (b->y - a->y);
  }
 
  if (x1 > x2) {                                            // x1 - слева, x2 - cправа
   x3 = x1; x1 = x2; x2 = x3;
   u3 = u1; u1 = u2; u2 = u3;
   v3 = v1; v1 = v2; v2 = v3;
  }
 
  u = u1;
  v = v1;
  
  // отрисовываем отрезок, лежащий на прямой y с концами x1 и x2
  for (x = (int)x1; x <= (int)x2; x++) {
    // рисуем пиксель, с координатами x,y, цвет которого соответствует цвету пикселя 
    // в текстуре с координатами u,v
    // ..
    u += du;
    v += dv;
   }
 }
}

3. Перспективно-корректное текстурирование.

Для перспективного проецирования аффинное (линейное) текстурирование, грубо говоря, совсем не подходит, так как линейно изменяться u и v не будут. Линейно мы будем интерполировать в данном случае величины u/z, v/z и 1/z, а непосредственно текстурирование мы будем проводить небольшими отрезками (спанами - span), вычисляя на начале и конце спана точные величины u и v, только затем интерполируя их. Спаны обычно бывают размеров в 8, 16, 32 пикселя (к чему бы это? :)).

Вместо вычисления Du/Dx и Dv/Dx мы будем вычислять D(u/z)/Dx, D(v/z)/Dx и D(1/z)/Dx.

теперь - кусок кода:

typedef struct {                                            // тип вершина
  float sx, sy, sz;                                         // координаты вершины в пространстве
  float uz, vz, wz;                                         // u/z, v/z, 1/z
  float x, y;                                               // координаты вершины на плоскости
  float u, v;                                               // координаты в текстуре
} vertex;

vertex *a, *b, *c;                                          // вершины треугольника
vertex *d;                                                  // вершина для сортировки по y
int x, y;                                                   // координаты точки в скан-линии
int length, len;                                            // длина отрезка, оставшаяся длина спана
float u, v;                                                 // текущие координаты в текстуре
float du, dv;                                               // на сколько изменятся координаты в текстуре
                                                            // при изменении x на 1
float duz, dvz, dwz;                                        // дельты интерполируемых величин
float wz1, uz1, vz1, wz2, uz2, vz2, uz3, vz3, wz3;          // интерполируемые величины, переменные 
                                                            // для сортировки
float uz_a, vz_a, wz_a, uz_b, vz_b, wz_b;                   // переменные для начала и конца спана
float u_a, v_a, u_b, v_b;                                   // координаты в текстуре левой и правой сторон 
                                                            // спана
float x1, x2, x3;                                           // левая и правая x-координаты отрезка скан-линии
                                                            // x3 - переменная для сортировки x1 и x2

void draw_triangle_persp();
 a->wz = 1 / a->sz;                                         // подсчитываем 1/z, u/z, v/z для каждой вершины
 a->uz = a->u * a->wz;
 a->vz = a->v * a->wz;
 b->wz = 1 / b->sz;
 b->uz = b->u * b->wz;
 b->vz = b->v * b->wz;
 c->wz = 1 / c->sz;
 c->uz = c->u * c->wz;
 c->vz = c->v * c->wz;

 if (a->y > b->y) {d = a; a = b; b = d;}                    // сортировка по y
 if (a->y > c->y) {d = a; a = c; c = d;}
 if (b->y > c->y) {d = b; b = c; c = d;}

 if ((int)a->y == (int)c->y) return;                        // отметаем частный случай, если высота = 0

 x1 = a->x + (c->x - a->x) * (b->y - a->y) / (c->y - a->y); // получаем x-координату начала отрезка, 
                                                            // duz, dvz, dwz
 wz1 = a->wz + (c->wz - a->wz) * (b->y - a->y) / (c->y - a->y);
 uz1 = a->uz + (c->uz - a->uz) * (b->y - a->y) / (c->y - a->y);
 vz1 = a->vz + (c->vz - a->vz) * (b->y - a->y) / (c->y - a->y);
 x2 = b->x;
 uz2 = b->uz;
 vz2 = b->vz;
 wz2 = b->wz;
 duz = (uz1 - uz2) / (x1 - x2);                             // получаем дельты
 dvz = (vz1 - vz2) / (x1 - x2);
 dwz = (wz1 - wz2) / (x1 - x2);

 for (y = (int)a->y; y <= (int)c->y; y++) {                 // цикл отрисовки грани
  x1 = a->x + (c->x - a->x) * (y - a->y) / (c->y - a->y);   // получаем x-координату самой длинной стороны
  uz1 = a->uz + (c->uz - a->uz) * (y - a->y) / (c->y - a->y);   // получаем uz-координату
  vz1 = a->vz + (c->vz - a->vz) * (y - a->y) / (c->y - a->y);   // получаем vz-координату
  wz1 = a->wz + (c->wz - a->wz) * (y - a->y) / (c->y - a->y);   // получаем wz-координату
  x = x1;
    
  if (y >= b->y) {                                          // выясняем, какую сторону проходит скан-линия,
    x2 = b->x + (c->x - b->x) * (y - b->y) / (c->y - b->y); // и вычисляем ее x-координату
    uz2 = b->uz + (c->uz - b->uz) * (y - b->y) / (c->y - b->y); //            uz-координату
    vz2 = b->vz + (c->vz - b->vz) * (y - b->y) / (c->y - b->y); //            vz-координату
    wz2 = b->wz + (c->wz - b->wz) * (y - b->y) / (c->y - b->y); //            wz-координату
   } else {
    x2 = a->x + (b->x - a->x) * (y - a->y) / (b->y - a->y);
    uz2 = a->uz + (b->uz - a->uz) * (y - a->y) / (b->y - a->y);
    vz2 = a->vz + (b->vz - a->vz) * (y - a->y) / (b->y - a->y);
    wz2 = a->wz + (b->wz - a->wz) * (y - a->y) / (b->y - a->y);
  }
 
  if (x1 > x2) {                                            // x1 - слева, x2 - cправа
   x3 = x1; x1 = x2; x2 = x3;
   uz3 = uz1; uz1 = uz2; uz2 = uz3;
   vz3 = vz1; vz1 = vz2; vz2 = vz3;
   wz3 = wz1; wz1 = wz2; wz2 = wz3;
  }
 
  length = (int)x2 - (int)x1;                               // вычисляем длину всего отрезка
  uz_a = uz1;                                               // подготавливаем переменные для спана и
  vz_a = vz1;                                               // вычисляем u, v на начало спана
  wz_a = wz1;
  u_a = uz_a / wz_a;
  v_a = vz_a / wz_a;

  while (length >= 8) {
   uz_b = uz_a + 8 * duz;                                  // подготавливаем переменные для конца текущего 
   vz_b = vz_a + 8 * dvz;                                  // спана и вычисляем u, v на конец спана
   wz_b = wz_a + 8 * dwz;
   u_b = uz_b / wz_b;
   v_b = vz_b / wz_b;

   u = u_a;
   v = v_a;

   du = (u_b - u_a) / 8;                                   // вычисляем du и dv на спан
   dv = (v_b - v_a) / 8;

   len = 8;
   while (len--) {
     // рисуем текущий пиксель
     // ..
     x++;
     u += du;
     v += dv;
    }
   length -= 8;
   uz_a = uz_b;
   vz_a = vz_b;
   wz_a = wz_b;
   u_a = u_b;
   v_a = v_b;
  }

  if (length != 0) {                                        // дорисовываем оставшиеся пиксели
   uz_b = uz2;
   vz_b = vz2;
   wz_b = wz2;
   u_b = uz_b / wz_b;
   v_b = vz_b / wz_b;
   u = u_a;
   v = v_a;
   du = (u_b - u_a) / length;
   dv = (v_b - v_a) / length;

   while (length--) {
     // рисуем пиксель
     x++;
     u += du;
     v += dv;
    }
  }
 }
}

как пример перспективно-корректного текстурирования также можно посмотреть и этот исходник : 3d.zip, это мой исходник (watcom c++/asm) программного текстурирования из моего первого движка времен примерно 97-го года, когда я только начал разбираться в программировании 3D-графики.

13 июня 2002

#render, #математика

2001—2018 © GameDev.ru — Разработка игр