Назад в раздел
demo.design 3D programming FAQ.
|
eManual.ru - электронная документация
Секция 1 из 6 - Предыдущая - Следующая
Все секции
- 1
- 2
- 3
- 4
- 5
- 6
demo.design 3D programming FAQ, release 2
-----------------------------------------
-------------------------------------------------------------------------------
Этот файл может быть использован исключительно в НЕКОММЕРЧЕСКИХ целях.
-------------------------------------------------------------------------------
Содержание
----------
1. Введение
1.1. Предположения и соглашения
2. Основы 3D графики
2.1. Задание объектов и сцен
2.2. Проецирование
2.3. Матричные преобразования
2.4. Рисование одноцветного треугольника
2.5. Работа с произвольной камерой
3. Удаление невидимых частей
3.1. Отброс нелицевых граней
3.2. Алгоритм художника
3.3. Z-буфер
3.4. Порталы
3.5. Z-отсечение
3.6. Отсечение
3.6.1. Отсечение при растеризации
3.6.2. Алгоритм Сазерленда-Ходжмана
3.6.3. 3D-отсечение
4. Текстурирование
4.1. Точное
4.2. Аффинное
4.3. Перспективно-корректное
4.4. Параболическое
4.5. Билинейная фильтрация текстур
4.6. Мипмэппинг
5. Освещение
5.1. Модель освещения
5.2. Расчет нормали к объекту
5.3. Освещение по Ламберту
5.4. Освещение по Гуро
5.5. Освещение по Фонгу
5.6. Как совместить текстуру и освещение
5.6.1. 256-цветные режимы
5.6.2. 24/32-битные режимы
5.6.3. 15/16-битные режимы
6. Оптимизация
6.1. Приемы оптимизации для процессоров Intel Pentium
6.1.1. Спаривание целочисленных команд
6.1.2. Кэш-память
6.1.3. Разные трюки
6.2. Примеры внутренних циклов текстурирования
6.3. Использование инструкций MMX
6.4. Тайловые текстуры
7. Разное
7.1. Субпиксельная точность
7.2. Субтексельная точность
7.3. Поворот 3D вектора за шесть умножений
7.4. Алгоритм "бегущих кубиков" для полигонизации изоповерхностей
7.5. Формат 3DS-файла
7.6. Сплайны Кочанека-Бартельса
7.7. Кватернионы
7.8. Обратная трассировка лучей
-------------------------------------------------------------------------------
Если вы хотите дополнить FAQ, что-либо предложить или что-то увидеть в
очередном release - пишите:
Andrew Aksyonoff, 2:5036/5.47@fidonet
e-mail: shodan@chat.ru
-------------------------------------------------------------------------------
Последняя версия FAQ распространяется следующими методами:
- выкладывается на http://www.enlight.ru/faq3d
- с некоторой задержкой постится в demo.design.uue
- с некоторой задержкой кладется на мой FAQserver (Subj: dd3dfaq) и
с еще большей кладется на некоторые другие FAQserver'ы, их владельцы,
надеюсь, сами сделают объявления об этом в соответствующих эхах
Правила пользования FAQserver'ом стандартны. Если нужна помощь, то просто
напишите ему вот такое письмо:
From: you, 2:1234/56.78
To: FAQserver, 2:5036/5.47
Subj: %HELP
FAQserver, пожалуйста, используйте только в том случае, если не можете
достать FAQ никаким другим образом (нету никакой возможности доступа к
Сети, demo.design.uue в город не ходит, etc). Лимит дневной посылки на
данный момент равен 250k. Впрочем, все находится под ручным контролем и
лимит периодически превышается.
Анонсы я буду постить в demo.design, ru.algorithms и ru.game.design.
Форварды анонсов, ссылки на сайт и вообще любое распространение лишь
приветствуется.
Особое спасибо Oleg Lubarsky (drlove@impuls.zhitomir.ua) за бессменный
бета-тестинг и Andrey Samoilov (asy@sense.simbirsk.su) за дизайн сайта
и HTML-версию FAQ.
-------------------------------------------------------------------------------
1. Введение
===========
1.1. Предположения и соглашения
-------------------------------
Предполагается, что читатель имеет какие-то основные сведения о компьютерной
графике. Предполагается, что объект, состоящий из треугольных граней с
наложенными на них текстурами, есть достаточно реалистичная и относительно
простая модель. Также предполагается, что этот самый читатель способен
воспринимать тот менторский тон, в котором, видимо, будет выдержана большая
часть этого FAQ.
Рекомендуется наличие у читателя неких базовых познаний в стереометрии
и линейной алгебре, а также программировании. Например, довольно сильно
рекомендуется умение нарисовать одноцветный 2D треугольник.
Соглашения - следующие. Система 3D координат используется такая:
y
| z
| /
| /
-------O-------x
/ |
* |
/ |
Здесь буквами x, y, z обозначены положительные направления осей Ox, Oy и Oz
соответственно. Также предполагается, что камера неподвижна и находится в
точке (*) с координатами (0,0,-dist), ось зрения камеры направлена по оси Oz,
а именно в точку (0,0,0) (т.е. camera target = (0,0,0)), ось Ox с точки
зрения камеры направлена слева направо, ось Oy - снизу вверх, ось Oz - вглубь
экрана. Размер экрана - xSize на ySize пикселов.
Проецирование на плоскость экрана в этом случае будет осуществляться по
формулам
sx = xSize/2+x*dist/(z+dist),
sy = ySize/2-y*dist/(z+dist).
Здесь и далее используются обозначения
sx, sy - координаты проекции точки на экране,
x, y, z - 3D координаты точки,
dist - расстояние от камеры (она находится в точке (0,0,-dist)) до начала
координат,
u, v - координаты в текстуре (u - по горизонтали, v - по вертикали).
2. Основы 3D графики
====================
2.1. Задание объектов и сцен
----------------------------
Покажем здесь достаточно распространенную схему задания 3D объектов и сцен.
Подобная схема, кстати, используется, в 3D Studio.
Каждая сцена представляет собой следующее:
- набор объектов
- набор источников света
- набор текстур
- набор камер (хотя обычно используется одна)
Каждый объект задается следующим:
- набор вершин
* вершина определяется своими 3D координатами и соответствующими ей
координатами в текстуре
- набор граней
* грань определяется тремя вершинами и текстурой (вообще говоря, не
текстурой, а материалом: кроме текстуры могут быть заданы, например,
коэффициенты рассеивания и отражения света)
- поведение объекта
* то есть, расположение (то есть смещение, ось поворота, угол поворота,
коэффициент масштабирования, и т.д.) в зависимости от номера кадра;
обычно задается в нескольких ключевых точках и интерполируется между
ними с помощью сплайнов
Каждый источник света задается следующим:
- положение
- ориентация (точка, в которую направлен этот источник, target)
- тип (фоновый/направленный/ненаправленный)
- цвет (обычно RGB)
Каждая текстура представляет собой прямоугольную 2D картинку, часто
бывает фиксированных размеров (например, 64x64, 128x128, 256x256).
Каждая камера задается следующим:
- положение (location)
- направление (точнее, точкой, в которую направлена эта камера; target)
- угол зрения (FOV)
- угол поворота относительно своей оси (roll)
2.2. Проецирование
------------------
Мы будем использовать только обычное перспективное проецирование на плоскость
зрения "стандартной" камеры, определенной в пункте 1.1 (там же написаны и
формулы проецирования). Случай произвольной камеры будет приводиться к
случаю стандартной камеры.
2.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.
y * A' - результат
| - поворота
| -
| -
| - * A - исходная
| - --- точка
| - ---
| - ---
| ---
----O-----------------------x
|
|
Пусть 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).
2.4. Рисование одноцветного треугольника
----------------------------------------
Без понимания того, как рисовать залитый одним цветом треугольник, дальше
лезть в 3D графику явно не стоит. Поэтому вот объяснение.
Возьмем любой треугольник. Его изображение на экране - набор горизонтальных
отрезков, причем из-за того, что треугольник - фигура выпуклая, каждой
строке экрана соответствует не более одного отрезка. Поэтому достаточно
пройтись по всем строкам экрана, с которыми пересекается треугольник (то
есть, от минимального до максимального значения y для вершин треугольника),
и нарисовать соответствующие горизонтальные отрезки.
----------------------------
| A |
| **** |
| ******* |
| ********** |
| B************ |
| *********** |
| ********* |
|-----------@@@@@@@--------|
| ***** |
| *** |
| C |
----------------------------
Отсортируем вершины так, чтобы вершина 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);
}
// ...
Вот и все. Ну, горизонтальную линию, надеюсь, нарисовать сумеют все желающие.
2.5. Работа с произвольной камерой
----------------------------------
Рассмотрим любую камеру как точку - центр проецирования и экран - плоский
прямоугольник в 3D пространстве, на плоскость которого идет проецирование.
Наша стандартная камера, например, задается точкой (0,0,-dist) и экраном с
вершинами (-xSize/2,ySize/2), ..., (xSize/2,-ySize/2). Можно задать эту
систему тремя векторами, задающими с точки зрения камеры направления вперед,
вправо и вверх; вектор "вперед" соединяет центр проецирования и центр экрана,
вектор "вправо" соединяет центр экрана и правую его границу, вектор "вверх",
соответственно, центр экрана и верхнюю его границу. Обозначим эти вектора
как p, q и r соответственно, а центр проецирования за s. Вот пример для
стандартной камеры.
y
| z
| /
=====^=======+
@ / + <--------- экран
@ <-----+----------- r, "вверх"
@ / +
------------------O@@@@@@@>-------x
@ | ^-+----------- q, "вправо"
@ <---------+----------- p, "вперед"
@ | +
@ ===========+
* |
/ |
|
|
Здесь (для стандартной камеры; обозначим ее вектора как 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 очевиден.
3. Удаление невидимых частей
============================
3.1. Отброс нелицевых граней
----------------------------
Пусть у нас есть объект, внутри которого камера заведомо не окажется. Обычно
такие объекты составляют большую часть или всю сцену. Тогда для каждой грани
мы можем увидеть только одну ее сторону - лицевую. Грань - плоскость, она
делит все 3D пространство на два полупространства. Так вот, лицевую сторону
видно только из одного полупространства, из того, в которое "смотрит" нормаль
к этой грани, направленная *из* объекта. Проверив, в какое полупространство
попадает камера, можно сразу определить, является ли грань лицевой (то есть,
может ли камера увидеть лицевую сторону этой грани) и надо ли ее рисовать.
Пусть грань имеет вершины v1, v2, v3 и нормаль (nx,ny,nz). Тогда уравнение
плоскости, в которой она лежит, будет иметь вид
nx*x+ny*y+nz*z+d = 0.
d находим из того факта, что v1 в плоскости лежит:
nx*v1.x+ny*v1.y+nz*v1.z+d = 0,
d = -(nx*v1.x+ny*v1.y+nz*v1.z).
Функция nx*x+ny*y+nz*z+d принимает положительные значения по одну сторону от
плоскости, отрицательные по другую и равна нулю на самой плоскости. Точка
(v1.x+nx,v1.y+ny,v1.z+nz) лежит, очевидно, в том полупространстве, откуда
грань видно. Значение функции (назовем ее функцией видимости) в этой точке
равно
nx*(v1.x+nx)+ny*(v1.y+ny)+nz*(v1.z+nz)+d =
nx*(v1.x+nx)+ny*(v1.y+ny)+nz*(v1.z+nz)-(nx*v1.x+ny*v1.y+nz*v1.z) =
nx*nx+ny*ny+nz*nz > 0.
Таким образом, если значение функции в какой-то точке больше нуля, то грань
из этой точки потенциально видна. Нас интересует видимость грани из нашей
камеры, а камера у нас зафиксирована в точке (0,0,-dist). Таким образом,
получаем, что грани, для которых
-nz*dist-(nx*v1.x+ny*v1.y+nz*v1.z) < 0,
или, что равносильно,
nz*dist+nx*v1.x+ny*v1.y+nz*v1.z > 0,
заведомо не видны и время на их обработку и отрисовку тратить не стоит.
Отдельный вопрос - как считать нормали к граням. Точнее, как выбрать одну
из двух нормалей, которая будет смотреть из объекта. Обычно эта проблема
решается еще на этапе построения 3D моделей - например, пакет 3D Studio
записывает вершины граней в порядке A-B-C так, чтобы векторное произведение
BA*CA и было нормалью. Еще один способ - выбрать внутренную точку для объекта
(либо вручную, либо взять его центр тяжести, либо еще как-нибудь - методов
может быть придумано сколько угодно) и использовать ее: если для этой точки
функция видимости положительна, то есть грань якобы видна, то надо поменять
знак nx, ny и nz.
Осталось отметить, что для выпуклых объектов этот метод полностью решает
задачу об удалении невидимых частей. Для невыпуклых же он позволяет быстро и
просто сократить число граней, подлежащих дальнейшей проверке на видимость и
собственно отрисовке.
3.2. Алгоритм художника
-----------------------
Пусть имеется некий набор граней (т.е. сцена), который требуется нарисовать.
Отсортируем грани по удаленности от камеры и отрисуем все грани, начиная с
самых удаленных. Довольно распространенная характеристика удаленности для
грани ABC - это среднее значение z, mid_z = (A.z+B.z+C.z)/3. Вот и весь
алгоритм. Просто, и обычно достаточно быстро.
Существует, правда, несколько проблем.
Во-первых, при некотором расположении граней этот алгоритм вообще не может
дать правильного результата - в каком порядке грани не рисуй, получится
неправильно. Вот стандартный пример.
+----+ +----+
| | | |
+---| |--------------
| | | |
+---| |--------------
| | | |
| | | |
+-------------| |---+
| | | |
+-------------| |---+
| | | |
+----+ +----+
Во-вторых, при некотором расположении граней и использовании среднего значения
z как характеристики удаленности алгоритм тоже дает неправильный результат.
Пример чуть ниже. В этом случае горизонтальную грань надо отрисовывать второй,
но по среднему значению z она лежит дальше и таким образом получается, что ее
надо отрисовывать первой. Возможные пути решения этой проблемы - какие-то
изменения характеристики удаленности, либо моделирование, не вызывающее таких
ситуаций.
y
| |
| | <- грань #1 (параллельна Oxy)
| |
| --------------------------------------
| ^^^ грань #2 (параллельна Oxz)
|
|
|
|
--*------O-------------------------------------------------z
^-- камера
И наконец, при использовании этого алгоритма отрисовываются вообще все грани
сцены, и при большом количестве загораживающих друг друга граней мы будем
тратить большую часть времени на отрисовку невидимых в конечном итоге
частей. То есть совершенно впустую. В таком случае целесообразно использовать
какие-то другие методы (например BSP и PVS, порталы, и т.д).
3.3. Z-буфер
------------
Заведем буфер (собственно z-буфер) размером с экран, и забьем его каким-то
большим числом, настолько большим, что координаты z для точек сцены заведомо
меньше. Например, если z - fixedpoint 16:16, то можно использовать максимально
возможное значение, то есть 0x7FFFFFFF. Для каждой рисуемой точки считаем
Секция 1 из 6 - Предыдущая - Следующая
|
|
 |
|
