1. Задание объектов и сцен

Покажем здесь достаточно распространенную схему задания 3D объектов и сцен.
Подобная схема, кстати, используется, в 3D Studio.
Каждая сцена представляет собой следующее:
- набор объектов
- набор источников света
- набор текстур
- набор камер (хотя обычно используется одна)

Каждый объект задается следующим:
- набор вершин
* вершина определяется своими 3D координатами и соответствующими ей координатами в текстуре
- набор граней
* грань определяется тремя вершинами и текстурой (вообще говоря, не текстурой, а материалом: кроме текстуры могут быть заданы, например, коэффициенты рассеивания и отражения света)
- поведение объекта
* то есть, расположение (то есть смещение, ось поворота, угол поворота, коэффициент масштабирования, и т.д.) в зависимости от номера кадра; обычно задается в нескольких ключевых точках и интерполируется между ними с помощью сплайнов

Каждый источник света задается следующим:
- положение
- ориентация (точка, в которую направлен этот источник, target)
- тип (фоновый/направленный/ненаправленный)
- цвет (обычно RGB)

Каждая текстура представляет собой прямоугольную 2D картинку, часто бывает фиксированных размеров (например, 64x64, 128x128, 256x256).

Каждая камера задается следующим:
- положение (location)
- направление (точнее, точкой, в которую направлена эта камера; target)
- угол зрения (FOV)
- угол поворота относительно своей оси (roll)

2. Проецирование

Мы будем использовать только обычное перспективное проецирование на плоскость зрения "стандартной" камеры, определенной в пункте 1.1 (там же написаны и формулы проецирования). Случай произвольной камеры будет приводиться к случаю стандартной камеры.

3. Матричные преобразования

Вообще говоря, лучше всего немного почитать любую книжку по линейной алгебре. Здесь будет только краткий рассказ о 3D преобразованиях, о том, как их делать с помощью матриц, и о том, что же такое матрицы и как с ними работать.
Введем несколько терминов. n-мерный вектор, он же вектор размерности n, он же вектор размера n: упорядоченный набор n действительных чисел. Вообще говоря, практически то же самое, что и обычный 1D-массив. Матрица размера m на n (будет обозначаться как m*n, mxn): таблица размера m на n, в каждой клетке которой - действительное число. Это уже 2D-массив. Всего лишь. Вот пример матрицы 3x3:

[ 15 y*z 0.6 ]
[ 7 -3 91 ]
[ sin(x) 0.123 exp(t) ]

Займемся определением операций над векторами и матрицами. Вектор будем записывать в столбик и рассматривать его как матрицу размера n*1.
Операция скалярного произведения векторов: определена для двух векторов одинаковых размеров. Результат есть число, равное сумме произведений соответствующих элементов векторов. Пример:

[ 1 ] [ 4 ]
[ 2 ] * [ 5 ] = 1*4 + 2*5 + 3*6 = 32
[ 3 ] [ 6 ]
Операция векторного произведения: определена для (n-1) вектора одинакового размера n. Результат - вектор, причем, что интересно, перпендикулярный всем множителям. Результат меняется от перестановки мест множителей!!! Формально определяется как определитель матрицы, первая строка которой есть все базисные вектора, а все последующие - соответствующие координаты всех множителей. Поскольку нам она будет требоваться только для 3D пространства, мы определим векторное произведение двух 3D векторов явно:

[ Ax ] [ Bx ] | i j k | [ Ay*Bz-Az*By ]
AxB = [ Ay ] x [ By ] = | Ax Ay Az | = [ Az*Bx-Ax*Bz ]
[ Az ] [ Bz ] | Bx By Bz | [ Ax*By-Ay*Bx ]

Операция сложения двух матриц: определена для матриц одинаковых размеров. Каждый элемент суммы (то есть, каждое число в таблице) равняется сумме соответствующих элементов слагаемых-матриц. Пример:

[ 1 x 500 ] [ 8 a 3 ] [ 9 a+x 503 ]
[ 2 y 600 ] + [ 9 b 2 ] = [ 11 b+y 602 ]
[ 3 z 700 ] [ 10 c 1 ] [ 13 c+z 701 ]

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

Операция умножения двух матриц: определена для двух матриц таких размеров a*b и c*d, что b = c. Например, если b = c, но a != d, то при перестановке множителей операция будет вообще не определена. Результатом умножения матрицы A размером a*b на матрицу B размером b*d будет матрица C размером a*d, в которой элемент, стоящий в строке i и столбце j, равен произведению строки i матрицы A на столбец j матрицы B. Произведение строки на столбец определяется как сумма произведений соответствующих элементов строки и столбца. Чтобы было хоть чуть-чуть понятно, пример умножения строки на столбец (они должны быть равной длины, кстати; поэтому и такие ограничения на размеры матриц):

[ 4 ]
[ 1 2 3 ] * [ 5 ] = 1*4 + 2*5 + 3*6 = 32
[ 6 ]

А чтобы перемножить две матрицы, надо эту операцию проделать для каждого элемента. Вот пример:

[ 1 2 3 ] [ 0 3 ] [ 1*0+2*1+3*2 1*3+2*4+3*5 ]
[ 4 5 6 ] * [ 1 4 ] = [ 4*0+5*1+6*2 4*3+5*4+6*5 ] = ...
[ 7 8 9 ] [ 2 5 ] [ 7*0+8*1+9*2 7*3+8*4+9*5 ]

Умножение и сложение матриц обладают почти тем же набором свойств, что и обычные числа, хотя некоторые привычные свойства не выполняются (например, A*B != B*A); нам на самом деле понадобится знать, что произведение вида A*B*C*D*... не зависит от того, как расставить скобки. Или, если угодно, что

A*(B*C) = (A*B)*C.

Теперь забудем об этом на некоторое время и перейдем к преобразованиям. Любое движение (то есть преобразование пространства, сохраняющее расстояние между точками) в трехмерном пространстве, согласно теореме Шаля, может быть представлено в виде суперпозиции поворота и параллельного переноса, то есть последовательного выполнения поворота и параллельного переноса. Именно поэтому основная часть информация о поведении объекта - это его смещение, ось поворота и угол поворота. И именно поэтому нам достаточно знать, как сделать два преобразования - перенос и поворот.

Перенос точки (кстати, точки будут также рассматриваться как вектора с началом в начале координат и концом в собственно точке) с координатами (x,y,z) на вектор (dx,dy,dz) делается простым сложением всех координат. То есть результат - это (x+dx,y+dy,z+dz). Как бы сложили вектор-точку и вектор-перенос.

Поворот - занятие уже более интересное. Но тоже простое. Рассмотрим для примера поворот точки (x,y,z) относительно оси z. В этом случае z не меняется вообще, а (x,y) меняются так же, как и при 2D повороте относительно начала координат.

Посмотрим, какие будут координаты у точки A' - результата поворота A(x,y) на угол alpha.

Пусть r = sqrt(x*x+y*y). Пусть угол AOx равен phi, тогда из рисунка видно, что cos(phi) = x/r, sin(phi) = y/r. Угол A'OA равен по условию alpha. Отсюда

x' = r*cos(alpha+phi) = r*(cos(alpha)*cos(phi)-sin(alpha)*sin(phi)) =
= (r*cos(phi))*cos(alpha)-(r*sin(phi))*sin(alpha) =
= x*cos(alpha)-y*sin(alpha)
y' = r*sin(alpha+phi) = r*(cos(alpha)*sin(phi)+sin(alpha)*cos(phi)) =
= (r*cos(phi))*sin(alpha)+(r*sin(phi))*cos(alpha) =
= x*sin(alpha)+y*cos(alpha)

Для трехмерного случая, таким образом

x' = x*cos(alpha)-y*sin(alpha)
y' = x*sin(alpha)+y*cos(alpha)
z' = z

Аналогичные формулы получатся и для других осей поворота (то есть Ox, Oy). Поворот относительно произвольной оси, проходящей через начало координат, можно сделать с помощью этих поворотов - сделать поворот относительно Ox так, чтобы ось поворота стала перпендикулярна Oy, затем поворот относительно Oy так, чтобы ось поворота совпала с Oz, сделать собственно поворот, а затем обратные повороты относительно Oy и Ox. Можно даже вывести формулы для такого поворота и убедиться в том, что они очень громоздкие.

Вспомним о матрицах и векторах и внимательно посмотрим на выведенные формулы для поворота. Можно заметить, что

[ x' ] = [ cos(alpha) -sin(alpha) 0 ] [ x ]
[ y' ] = [ sin(alpha) cos(alpha) 0 ] [ y ]
[ z' ] = [ 0 0 1 ] [ z ]

То есть поворот на угол alpha задается одной и той же матрицей, и с помощью этой матрицы (умножая ее на вектор-точку) можно получить координаты повернутой точки. Пока никакого выигрыша не видно - здесь умножение матрицы на вектор требует больше операций, чем расчет x' и y' по формулам.

Удобство матриц для нас заключается как раз в свойстве A*(B*C) = (A*B)*C. Пусть мы делаем несколько поворотов подряд, например, пять (как раз столько, сколько надо для поворота относительно произвольной оси), и пусть они задаюся матрицами A, B, C, D, E (A - матрица самого первого поворота, E - последнего). Тогда для вектора p мы получаем

p' = E*(D*(C*(B*(A*p)))) = E*D*C*B*A*p = (E*D*C*B*A)*p =
= (E*(D*(C*(B*A))))*p = T*p,

где

T = (E*(D*(C*(B*A))))

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

Таким образом, можно задать любой поворот матрицей, и любая комбинация поворотов также будет задаваться матрицей, которую можно довольно легко посчитать. Но есть еще параллельный перенос, есть еще масштабирование. Что делать с ними?

На самом деле, эти преобразования тоже легко записываются в виде матриц. Только вместо матриц 3x3 и 3-мерных векторов используются так называемые однородные 4-мерные координаты и матрицы 4x4. При этом вместо векторов вида
[ x ]
[ y ]
[ z ]

используются вектора вида

[ x ]
[ y ]
[ z ]
[ 1 ]

а вместо произвольных матриц 3x3 используются матрицы 4x4 такого вида:

[ a b c d ]
[ e f g h ]
[ i j k l ]
[ 0 0 0 1 ]

Видно, что если d = h = l = 0, то в результате применения всех операций получается то же самое, что и для матриц 3x3.

Матрица параллельного переноса теперь определяется как

[ 1 0 0 dx ]
[ 0 1 0 dy ]
[ 0 0 1 dz ]
[ 0 0 0 1 ]

Матрицу масштабирования можно определить и для матриц 3x3, и для матриц 4x4:

[ kx 0 0 ] [ kx 0 0 0 ]
[ 0 ky 0 ] или [ 0 ky 0 0 ]
[ 0 0 kz ] [ 0 0 kz 0 ]
[ 0 0 0 1 ]

где kx, ky, kz - коэффициенты масштабирования по соответствующим осям.

Таким образом, получаем следующее. Любое нужное нам преобразование пространства можно задать матрицей 4x4 определенной структуры, разной для разных преобразований. Результат последовательного выполнений нескольких преобразований совпадает с результатом одного преобразования T, которое также задается матрицей 4x4, вычисляемой как произведение матриц всех этих преобразований. Важен порядок умножения, так как A*B != B*A. Результат применения преобразования T к вектору [ x y z ] считается как результат
умножения матрицы T на вектор [ x y z 1 ]. Вот и все.

Осталось только на примере показать, почему A*B != B*A. Пусть A - матрица переноса, B - поворота. Если мы сначала перенесем объект, а потом повернем относительно центра координат (это будет B*A), получим далеко не то, что будет, если сначала объект повернуть, а потом перенести (это уже A*B).

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

Без понимания того, как рисовать залитый одним цветом треугольник, дальше лезть в 3D графику явно не стоит. Поэтому вот объяснение.

Возьмем любой треугольник. Его изображение на экране - набор горизонтальных отрезков, причем из-за того, что треугольник - фигура выпуклая, каждой строке экрана соответствует не более одного отрезка. Поэтому достаточно пройтись по всем строкам экрана, с которыми пересекается треугольник (то есть, от минимального до максимального значения y для вершин треугольника), и нарисовать соответствующие горизонтальные отрезки.

Отсортируем вершины так, чтобы вершина A была верхней, C - нижней, тогда у нас min_y = A.y, max_y = C.y, и нам надо пройтись по всем линиям от min_y до max_y. Рассмотрим какую-то линию sy, A.y <= sy <= C.y. Если sy < B.y, то она пересекает стороны AB и AC; если sy >= B.y - то стороны BC и AC. Мы знаем координаты всех вершин, поэтому мы можем написать уравнения сторон и найти пересечение нужной стороны с прямой y = sy. Получим два конца отрезка. Так как мы не знаем, какой из них левый, а какой правый, сравним их координаты по x и обменяем значения, если надо. Рисуем этот отрезок, повторяем процедуру
для каждой строки - и вуаля, трегуольник нарисован.

Остановимся более подробно на нахождении пересечения прямой y = sy (текущей строки) и стороны треугольника, например AB. Напишем уравнение прямой AB в форме x = k*y+b:

x = A.x+(y-A.y)*(B.x-A.x)/(B.y-A.y)

Подставляем сюда известное для текущей прямой значение y = sy:

x = A.x+(sy-A.y)*(B.x-A.x)/(B.y-A.y)

Вот, в общем-то, и все. Для других сторон пересечение ищется совершенно точно
так же. А вот и пример кода.

// ...
// здесь сортируем вершины (A,B,C)
// ...
for (sy = A.y; sy <= C.y; sy++) {
x1 = A.x + (sy - A.y) * (C.x - A.x) / (C.y - A.y);
if (sy < B.y)
x2 = A.x + (sy - A.y) * (B.x - A.x) / (B.y - A.y);
else
x2 = B.x + (sy - B.y) * (C.x - B.x) / (C.y - B.y);
if (x1 > x2) { tmp = x1; x1 = x2; x2 = tmp; }
drawHorizontalLine(sy, x1, x2);
}
// ...

Надо, правда, защититься от случая, когда B.y = C.y - в этом (и только этом, потому как если C.y = A.y, то треугольник пустой и рисовать его не стоит, или можно рисовать горизонтальную линию; а если B.y = A.y, то sy >= A.y и до деления на B.y - A.y не дойдет) случае произойдет попытка деления на ноль.
Код изменится совсем чуть-чуть:

// ...
// здесь сортируем вершины (A,B,C)
// ...
for (sy = A.y; sy <= C.y; sy++) {
x1 = A.x + (sy - A.y) * (C.x - A.x) / (C.y - A.y);
if (sy < B.y)
x2 = A.x + (sy - A.y) * (B.x - A.x) / (B.y - A.y);
else {
if (C.y == B.y)
x2 = B.x;
else
x2 = B.x + (sy - B.y) * (C.x - B.x) / (C.y - B.y);
}
if (x1 > x2) { tmp = x1; x1 = x2; x2 = tmp; }
drawHorizontalLine(sy, x1, x2);
}
// ...

Вот и все. Ну, горизонтальную линию, надеюсь, нарисовать сумеют все желающие.

5. Работа с произвольной камерой
----------------------------------

Рассмотрим любую камеру как точку - центр проецирования и экран - плоский прямоугольник в 3D пространстве, на плоскость которого идет проецирование. Наша стандартная камера, например, задается точкой (0,0,-dist) и экраном с вершинами (-xSize/2,ySize/2), ..., (xSize/2,-ySize/2). Можно задать эту систему тремя векторами, задающими с точки зрения камеры направления вперед, вправо и вверх; вектор "вперед" соединяет центр проецирования и центр экрана, вектор "вправо" соединяет центр экрана и правую его границу, вектор "вверх", соответственно, центр экрана и верхнюю его границу. Обозначим эти вектора как p, q и r соответственно, а центр проецирования за s. Вот пример для
стандартной камеры.

Здесь (для стандартной камеры; обозначим ее вектора как Sp, Sq, Sr, Ss)

Sp = p = (0,0,dist)
Sq = q = (xSize/2,0,0)
Sr = r = (0,ySize/2,0)
Ss = s = (0,0,-dist)

Любые три взаимно перпендикулярных вектора и точка - центр координат задают в 3D пространстве систему координат. Так что объект мы можем рассматривать в системе обычных координат (x,y,z), в системе координат стандартной камеры (Sp,Sq,Sr) или в системе (p,q,r), соответствующей какой-то произвольной камере. В любом случае, если (a,b,c) - координаты точки в системе координат камеры (точнее, в системе координат с центром в точке s и базисом (p,q,r)), то координаты проекции точки на экране равны

screenX = xSize/2 + xSize/2 * a/c
screenY = ySize/2 - ySize/2 * b/c

В случае стандартной камеры переход от обычной системы координат к системе координат камеры очевиден:

a = x / (xSize/2)
b = y / (ySize/2)
c = (z + dist) / dist

Подставив это в формулы для screenX, screenY, получим как раз те самые формулы
для проекции на стандартную камеру.

Поскольку со стандартной камерой нам достаточно удобно и понятно работать, для произвольной камеры мы должны сделаеть такое преобразование пространства, что как бы совместит произвольную камеру и стандартную камеру. То есть, такое преобразование, что вектора p, q, r перейдут в Sp, Sq, Sr, а точка s в точку Ss.

Посчитаем матрицу для *обратного* преобразования; оно должно переводить Sp,Sq, Sr, Ss в p, q, r, s. Преобразование, переводящее Ss в s (и наоборот) - это обычный паралелльный перенос; остается написать преобразование перевода Sp, Sq, Sr в p, q, r. Пусть у нас есть координаты p, q, r в системе координат (x,y,z):

p = (px,py,pz)
q = (qx,qy,qz)
r = (rx,ry,rz)

Для Sp, Sq, Sr координаты (в этой же системе) известны и равны следующему:

Sp = (0,0,dist)
Sq = (xSize/2,0,0)
Sr = (0,ySize/2,0)

Пусть T - искомая матрица перевода,

[ a b c ]
T = [ d e f ], a..i - какие-то неизвестные.
[ g h i ]

Поскольку T переводит Sp, Sq, Sr в p, q, r; то есть

p = T*Sp
q = T*Sq
r = T*Sr

то, подставляя, например, p и Sp, получаем:

[ px ] [ a b c ] [ 0 ] [ c*dist ]
[ py ] = [ d e f ] [ 0 ] = [ f*dist ], откуда
[ pz ] [ g h i ] [ dist ] [ i*dist ]

c = px/dist
f = py/dist
i = pz/dist.

Аналогично находим все остальные элементы матрицы T:

[ qx*2/xSize rx*2/ySize px/dist ]
T = [ qy*2/xSize ry*2/ySize py/dist ]
[ qz*2/xSize rz*2/ySize pz/dist ]

Но нас интересует обратное к этому преобразование. Оно задается обратной матрицей к T, то есть такой матрицей T1, что

[ 1 0 0 ]
T * T1 = T1 * T = [ 0 1 0 ]
[ 0 0 1 ]

Обратная матрица, вообще говоря, существует далеко не всегда, да и вычисление ее в общем случае - достаточно неприятная задача. Однако в данном случае из-за специального вида матрицы T (конкретнее, из-за того, что T - ортогональная матрица) она не только всегда существует, но и считается очень просто:
[ qx*2/xSize rx*2/ySize px/dist ] [ qx1 rx1 px1 ]
T = [ qy*2/xSize ry*2/ySize py/dist ] = [ qy1 ry1 py1 ]
[ qz*2/xSize rz*2/ySize pz/dist ] [ qz1 rz1 pz1 ]

[ qx1/lq qy1/lq qz1/lq ]
T1 = [ rx1/lr ry1/lr rz1/lr ]
[ px1/lp py1/lp pz1/lp ]

где

lp = px1*px1 + py1*py1 + pz1*pz1
lq = qx1*qx1 + qy1*qy1 + qz1*qz1
lr = rx1*rx1 + ry1*ry1 + rz1*rz1

Сделав сначала параллельный перенос, совмещающий s и Ss, а потом полученное преобразование, как раз и получим преобразование, переводящее произвольную камеру в стандартную.

Теперь надо выяснить, как, собственно посчитать координаты p, q, r через имеющиеся у нас характеристики: положение, направление, угол зрения и угол поворота. 3D Studio (и мы вслед за ней) рассчитывает эти вектора по такому алгоритму:

1. Считаем p = target - location
2. Если p.x == 0 и p.z == 0, то q = (0, 0, 1); иначе q = (p.z, 0, -p.x)
3. Считаем r = crossProduct(p, q) - векторное произведение p на q
4. Считаем lp = length(p) - длина p
5. Приводим r и q к длине 2*lp*tan(FOV/2)

Здесь мы не учитываем поворот камеры вокруг своей оси, его удобнее сделать после перехода к стандартной камере - в этом случае получаем обычный поворот относительно оси z на угол roll.

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

FinalCameraMatrix = RollMatrix * T1 * MoveMatrix

Расчет матриц RollMatrix и MoveMatrix очевиден.

Copyright © Diablo 2005-2006. All rights reserved rmsystem@bk.ru icq 227877666