Примечание переводчика:
Эти уроки, от анонимного автора, я, когда раскопал в недрах Интернета на сайте Coding Place, и мне они очень понравились своей простотой. Сейчас конечно, это все устарело, но некоторые самые простые основы 3D в этих уроках рассмотрены понятно и внятно.
Весь код в этих уроках сделан на Borland C++ v3.1 под MsDOS, а основной видеорежим 320x200.
Основы 3D
Для начала, давайте рассмотрим некоторые основы 3D. Сначала, что такое 3D? Хорошо, 3D – это сокращение и значит трехмерность. Теперь, давайте рассмотрим некоторую другую мерность, возможно, это поможет нам понять 3D. Одномерность - только линия, и наше положение на этой линии представлено буквой x. Двумерность - представлена буквами x и y. Это - то, что мы называем координатной системой, x идет слева направо, а y снизу вверх. Это - фактически также наш экран. Теперь, трехмерность представлена x, y и z. Эта новая ось, z, движется от нас вглубь нашей системы координат, это дает нам глубину. Это - то, что мы фактически видим также. Возьмем пример. Закройте один глаз (так как два глаза могут запутать) и возьмите ручку. Отведите эту ручку настолько далеко насколько возможно, и думайте что z теперь равно 100. Далее, перемещайте ручку ближе к вашему глазу, при этом Вы уменьшаете значение z, и когда Вы не можете больше перемещать ручку (около вашего носа), Вы имеете значение z равное единице. Теперь, при значении глубины равным единице, мы имеем фактический размер ручки. Ручка теперь намного больше, чем была прежде, часто больше, чем солнце. Хотя мы знаем, что солнце - фактически тысячи, возможно даже миллионы километров в радиусе, мы видим его как шарик в диаметре не больше, чем 2-3 сантиметра. Это - из-за расстояния между Вами и солнцем, которое составляет 8 световых минут. Теперь, если бы Вы стояли в 1 сантиметре от солнца, Вы видели бы его фактический размер, но сместившись на 1 сантиметра от него, его размер в ваших глазах уже будет равен половине от действительного. Теперь, хотя это не совсем правильно, но принцип соблюден, мы можем найти видимые x и y значения в том месте, где мы видим точку, зная x, y и z координаты. Формулы:
x' = x/z
y' = y/z
Заметим, что мы используем компьютер, и поэтому мы должны прибавить половину размера экрана к результату. Иначе точка 0,0,0 была бы найдена в левом верхнем углу нашего экрана. Следовательно, если мы добавляемся 160 и 100 к нашему значению, мы можем видеть, и отрицательные и положительные значения x/y. Формулы, которые мы должны использовать:
x' = x/z+160
y' = y/z+100
Это основные сведения о 3D.
Примечания переводчика: везде в Coding Place используется разрешения экрана 320x200 и начало координат в середине экрана, при этом ось x идет слева направо, ось y идет снизу вверх, а ось z от экрана вглубь.
Математика с фиксированной запятой
Числа с фиксированной десятичной точкой (ЧФДТ - fixed points) часто используются, чтобы повысить скорость выполнения программ, и при этом сделать код более организованным. Используя ЧФДТ вместо чисел с плавающей запятой, Вы можете добиться лучшей переносимости ваших программ, и Вы можете использовать для вычислений числа длиной 4, 8, 16 или любое другое число бит. Этого нельзя сделать с числами с плавающей запятой, кроме этого любое преобразование чисел с плавающей запятой делается медленно. Поэтому давайте посмотрим, как работать с числами с фиксированной запятой. ЧФДТ – это число, умноженное на другое число. Например, возьмем произвольное число с плавающей запятой - 1554.132473. Теперь, мы хотим поместить это число в 32 разрядную переменную. Мы можем сделать это, умножив это число на 65536. Фактически это означает сдвиг влево на 16 бит, что быстрее, чем умножение, и, следовательно, мы будем использовать сдвиг. Теперь, как это выглядит побитно. Мы выберем другое число на этот раз, пусть это будет единица:
byte 1 byte 2 byte 3 byte 4
00000000 00000000 00000000 00000001 = 1
Теперь, сдвинем влево шестнадцать раз и мы получим число:
byte 1 byte 2 byte 3 byte 4
00000000 00000001 00000000 00000000 = 65536
При таком способе, число один равняется 65536 в ЧФДТ. Следовательно, любое число меньше 65536 будет меньше единицы. Теперь мы имеем два 16.16 разрядных числа. И конечно при этом появляются определенные трудности. Возьмем число 1554.132473, ранее упомянутое. Если мы умножим это число на 65536, то мы получим число 101851625.8. Полученное число не целое и нам надо отсечь 0.8, но насколько это изменит фактическое число? Давайте, разделим полученное число на 65536, чтобы получить вещественное число. Получилось число 1554.132461, которое отличается от первоначального числа на 0.000012. Не так уж и много, потому что мы собираемся использовать ЧФДТ в графике и трудно нарисовать 0.00012 пикселя. Но при наложении текстур такая погрешность может быть и большой, если текстура была бы достаточна большая, так как эта погрешность может вызвать появление одного дополнительного пикселя после вывода 10000 пикселей. Но для такой текстуры нужно огромное разрешение экрана. Возможно, этот недостаток не был бы не таким уж большим, но если Вы используете ЧФДТ для определения столкновений объектов или морфинг, такая погрешность в расчетах могла бы иметь разрушительный эффект, если не устранить эту ошибку. Кроме этого, вас может раздражать то, что вы не можете иметь значения больше чем 65536, так как при выполнении больше 16 сдвигов влево часть битов пропала бы.
Матрицы
Матрицы используются, чтобы упростить код и сделать его быстрее. Например, матрицы отлично используются в коде вращения, который мы рассмотрим ниже. Поэтому давайте рассмотрим основы работы с матрицами. Матрица - это прямоугольная таблица чисел, в которой Вы имеете множество переменных. Рассмотрим несколько матриц, которые мы будем использовать:
[1 0 0 -camerax]
[0 1 0 -cameray]
[0 0 1 -cameraz]
[0 0 0 1 ]
Эта матрица имеет размер 4x4, так как она имеет четыре строки и четыре колонки. Отметим, что матрицы 4x4 и 3x3 наиболее часто встречающиеся матрицы в 3D, но конечно матрицы могут быть любого размера. Теперь рассмотрим, как умножить матрицу на вектор:
[x'] [1 0 0 -camerax] [x]
[y'] = [0 1 0 -cameray] * [y]
[z'] [0 0 1 -cameraz] [z]
[ 1] [0 0 0 1 ] [1]
Слева мы имеем матрицу 4x1, состоящую из переменных x ', y ', z ' и числа 1. Затем в матрице 4x4, имеем четыре строки, стоящие из четырех чисел и переменных. Далее идет матрица 4x1, состоящая из переменных x, y, z и числа 1. Теперь, мы умножаем переменные, находящиеся в первой строке матрицы с каждой соответствующей переменной из последней матрицы, складываем все и присваиваем полученный результат в переменную в первой матрице, которая находится в соответствующей строке. Лучше всего показать это так:
x + y + z + 1
* * * *
[x']=[ 1 0 0 -camerax]
[y']=[ 0 1 0 -cameray]
[z']=[ 0 0 1 -cameraz]
[ 1]=[ 0 0 0 1 ]
Или можно расписать более подробно:
x' = 1 * x + 0 * y + 0 * z + -camerax * 1
y' = 0 * x + 1 * y + 0 * z + -cameray * 1
z' = 0 * x + 0 * y + 1 * z + -cameraz * 1
1' = 0 * x + 0 * y + 0 * z + 1 * 1
Теперь нам поможет небольшое отступление, чтобы двинуться дальше, поэтому давайте посмотрим другой способ для объяснения работы с матрицами. Пусть нам надо вычислить:
x' = 3x + 8y
Или по другому можно написать так:
x' = ax + by
Следовательно, мы можем представить это с помощью умножения двух матриц:
[x]
x' = [a b] * [y]
Теперь, возьмем матрицу 2x2 вместо 2x1.
x' = 3x + 8y
y' = 6x + 2y
x' = [3 8] * [x]
y' = [6 2] [y]
Теперь, мы желаем делать так:
x' = 3x + 8y + 9
y' = 6x + 2y + 2
x' = [3 8 9] [x]
y' = [6 2 2] * [y]
1' = [0 0 1] [1]
Вы видите, что мы берем третью матрицу 3x1 и умножаем ее по-компонентно на первую строку второй матрицы и складываем результаты этих умножений, затем тоже делаем со второй строкой. Это должно быть очень просто для понимания. Теперь, как мы это закодируем? Хорошо, вот пример.
int matrix[3][3];
int x1,y1;
int x2,y2;
main()
{
x1 = 10;
y1 = 20;
matrix[0][0] = 3;
matrix[0][1] = 8;
matrix[0][2] = 9;
matrix[1][0] = 6;
matrix[1][1] = 2;
matrix[1][2] = 2;
matrix[2][0] = 0;
matrix[2][1] = 0;
matrix[2][2] = 1;
x2 = matrix[0][0]*x1+
matrix[0][1]*y1+
matrix[0][2];
y2 = matrix[1][0]*x1+
matrix[1][1]*y1+
matrix[1][2];
}
Вы видите, что не нужно умножать компоненты matrix [0] [2] и matrix [1] [2], поскольку, те значения, на которые надо умножить эти компоненты, равны единице (это конечно справедливо только для вращения). Вот и все, что надо знать, чтобы использовать матрицы. Как умножить матрицы большей размерности, мы пока не думаем, но вот подсказка:
AB=C => Cij = ∑k Aik*Bkj
Вращения
Очень не плохо в нашем 3D мире иметь вращения. Вращения используются при движении камеры и любого другого объекта в любом направлении. Вам необходимо знать, что такое синус и косинус, что понять вращения.
Сначала, рассмотрим 2D вращения. Мы хотим вращать точку с координатами x и относительно точки 0,0. Поворот относительно начала координат делается по формулам:
newx = x*cos(theta) - y*sin(theta)
newy = y*cos(theta) + x*sin(theta)
Где theta - угол, на который надо вращать точку с координатами x и y. Мы видим, что новая координата newx точки равняется x*cos(theta)-y*sun(theta). Можно задать вопрос: почему мы используем значение y для вычисления newx? Но дело в том, что newx не имеет ничего общего с оригинальным значением x, это число произведение x и y. Приведем конкретный пример:
x = 10
y = 0
угол = 45
newx = 10*cos(10) - 0*sin(10)
newy = 0*cos(10) + 10*sin(10)
newx = 9.85
newx = 1.74
Теперь было не плохо получить формулы для вращения точки не относительно начала координат. Для этого надо вычесть значение координат точки вращения из точки x и y. Вот как это выглядит:
newx = (x-startx)*cos(theta) - (y-starty)*sin(theta) + startx
newy = (y-starty)*cos(theta) + (x-startx)*sin(theta) + starty
На пример, мы хотим, чтобы точка (7,0), повернулась на 180 градусов вокруг точки (6,0). Передвинем нашу точку в (1,0). Затем вращаем ее на 180 градусов относительно начала координат, что в результате дает точку (-1,0), далее добавляем точку вращения и получаем результат (5,0). Хороший и правильный результат. Теперь перейдем к 3D сращениям.
Поворот точки в 3D можно выполнить относительно всех
трех осей координат на разные углы, поэтому рассмотрим все три типа поворотов.
Поворот точки вокруг оси абсцисс x по формулам (вращение в плоскости yz):
newx = x
newy = y * cos(theta) – z * sin(theta)
newz = y * sin(theta) + z * cos(theta)
Поворот точки вокруг оси ординат y по формулам (вращение в плоскости xz):
newx = x * cos(theta) + z * sin(theta)
newy = y
newz = - x * sin(theta) + z * cos(theta)
Поворот точки вокруг оси аппликат z по формулам (вращение в плоскости xy):
newx = x * cos(theta) - y * sin(theta)
newy = x * sin(theta) + y * cos(theta)
newz = z
Все три поворота делаются независимо друг от друга, т.е. если надо повернуть вокруг осей Ox и Oy, вначале делается поворот вокруг оси Ox, потом применительно к полученной точки делается поворот вокруг оси Oy.
Также как и в 2D, для выполнения поворота вокруг произвольной точки, надо вначале перенести точку вращения в начало координат, осуществить все необходимые вращения, а потом переместить полученную точку на значения координат точки вращения.
Камеры
Камеры необходимы в 3D мире, чтобы видеть объекты. Они необходимы, если мы хотим двигаться в мире, они необходимы и для многих других вещей также. Мы всегда нуждаемся в камерах, когда делаем 3D программирование. Камеры могут иметь много функций, таких как масштабирование, наведение, области просмотра, т.д. Но мы только нуждаемся в базисных подпрограммах. Для начала нам необходимы матрицы. Если Вы не знаете, как работают матрицы, пожалуйста, посмотрите урок по матрицам. Теперь, о том как использовать камеры. Когда мы включаем камеру в наш код, мы можем делать "путешествие" в 3D мире. Под этим я подразумеваю, что мы можем использовать клавиши курсора, чтобы двигаться вперед и в стороны, смотреть вверх и вниз, и вращаться. Большинство 3D программистов желают это сделать, так как это дает наиболее приличные результаты. На самом деле все это очень просто и сводится к одной матрице, которая должна делать этот трюк. Давайте посмотрим, как можно задать камеру.
Любая камера задается при помощи позиции и углов тангажа (pitch), рысканья (yaw), крена (roll), соответственно это углы поворота вокруг осей x, y, z. Из позиции мы знаем, где камера находится, по углам мы знаем, в каком направлении она смотрит. Главное запомните, что мы должны сделать со всеми вершинами в нашем мире, это перенести их с WCS (мировая система координат) в CCS (система координат камеры). Это выполняется вначале перемещением всех вершин, так чтобы они соответствовали положению камеры. Сдвиг надо сделать с помощью умножения позиции точки на матрицу сдвига 4x4:
[x'] [1 0 0 -camerax] [x]
[y'] = [0 1 0 -cameray] * [y]
[z'] [0 0 1 -cameraz] [z]
[ 1] [0 0 0 1 ] [1]
Теперь мы переместили все вершины из WCC к CCS, но мы нам надо учесть углы вращения. Следовательно, мы делаем три новых матрицы, каждая матрица на свое вращение вокруг оси соответствующей оси.
Вокруг оси x:
[x'] [ 1 0 0 ] [x]
[y'] = [ 0 cos(pitch) -sin(pitch)] * [y]
[z'] [ 0 sin(pitch) cos(pitch)] [z]
Вокруг оси y:
[x'] [cos(yaw) 0 sin(yaw)] [x]
[y'] = [ 0 1 0 ] * [y]
[z'] [-sin(yaw) 0 cos(yaw)] [z]
Вокруг оси z:
[x'] [cos(roll) -sin(roll) 0 ] [x]
[y'] = [sin(roll) cos(roll) 0 ] * [y]
[z'] [ 0 0 1 ] [z]
При вращении на произвольный угол выполняется отдельные вращения вокруг осей координат, но в результате получим одну большую матрицу. Если вычислить ее за ранее, то мы получим следующую матрицу:
[m11 m12 m13]
[m21 m22 m23]
[m31 m32 m33]
где:
m11 = cos(yaw)*cos(roll)
m12 = -cos(yaw)*sin(roll)
m13 = sin(yaw)
m21 = sin(pitch)*sin(yaw)*cos(roll) + sin(roll)*cos(pitch)
m22 = -sin(pitch)*sin(yaw)*sin(roll) + cos(roll)*cos(pitch)
m23 = -sin(pitch)*cos(yaw)
m31 = -cos(pitch)*sin(yaw)*cos(roll) + sin(pitch)*sin(roll)
m32 = cos(pitch)*sin(yaw)*sin(roll) + sin(pitch)*cos(roll)
m33 = cos(yaw)*cos(pitch)
Сортировка
Для правильного вывода полигонов в 3D используется сортировка этих граней по глубине. Ясно, что скорость сортировки сильно влияет на скорость выполнения программы. Мы рассмотрим три метода сортировки, а именно пузырьковую сортировку, быструю и поразрядную сортировку.
Пузырьковая сортировка
Первый алгоритм, который мы рассмотрим - пузырьковая сортировка. Пузырьковая сортировка самый медленный из всех алгоритмов сортировки (поэтому его не следует использовать), но небольшой код этого метода очень трудно забыть. Код выглядит следующим образом:
for (j=0;j<NUM_ELEMENTS-1;j++)
{
for (k=(j+1);k<NUM_ELEMENTS;k++)
{
if (array[j] > array[k])
{
temp = array[j];
array[j] = array[k];
array[k] = temp;
}
}
}
Эта программа сортирует данные в таблице называемой массивом. Эта таблица является и приемной и исходной таблицей. Это не очень удобно, когда необходимо сортировать данные, которые должны храниться в том же самом месте, а не перемещатся (например, грани объекта). (Примечание переводчика: можно поместить указатели, или номера граней в один общий массив и отсортировать его, при этом целостность структур данных граней не будет затронута). Но что эта программа делает? Она начинает с нулевого элемента, и сравнивает его с каждым другим элементом в массиве. Если при этом находится элемент, который имеет меньшее значение, то эти два числа переставляются так, чтобы первый элемент таблицы, в конечном счете, получил самое меньшее значение. Затем берется следующий элемент по номеру, и второй внутренний цикл становится на один проход меньше, и начинается с элемента, на котором кончился предыдущий этап сортировки. Таким образом, программа выполняется фиксированное число раз:
n * n - (1 + 2 + 3 + 4 + 5 .. n)
Быстрая сортировка
Быстрая сортировка также сортирует данные в одной таблице. Быстрая сортировка рекурсивный алгоритм, т.е. функция быстрой сортировки вызывает сама себя. Вначале функция разбивает таблицу на два раздела. В первый раздел помещаются элементы меньшие, чем во втором. Далее для каждого раздела процедура повторяется. При этом число перестановок не больше, чем n * log(n), но в некоторых случаях возможна работа алгоритма со скоростью n2.
Поразрядная сортировка
Возьмем две разные таблицы, одна для промежуточных вычислений и другая исходная, т.е. будем использовать для сортировки дополнительную память. Будем смотреть биты в числе, а не значение числа. Пробегаем каждый элемент, и сортируем их в две таблицы. В исходную таблицу помещаем число, которое имеет сброшенный первый бит (равный нулю). А в промежуточную таблицу помещаем числа, которые имеют установленный первый бит (равный единице). Дальше Вы помещаете числа из промежуточной таблицы сразу за числами в исходную таблицу. Далее делаете тоже для следующего бита и так пока не отсортировали все биты. Этот алгоритм примерно в 300 раз быстрее, чем пузырьковая сортировка, но так как необходимо время для копирования элементов, то он медленнее, чем быстрая сортировка.
Статистика
Результаты на P4-2400:
Bubble sort ... - Ok. 8696 elements pr. second.
Quick sort ... - Ok. 2272727 elements pr. second.
Bit sort ... - Ok. 2127660 elements pr. second.
Heap sort ... - Ok. 2020202 elements pr. second.
Shell sort ... - Ok. 2150538 elements pr. second.
Примечание переводчика:
На сайте не было исходного текста программ для сортировки, я воспроизвел его самостоятельно.
Нормали
Если мы хотим сделать удаление невидимых поверхностей, наложение окружения и освещение, нам нужны нормали. При удалении невидимых поверхностей нормали указывают, куда смотрят поверхности, куда они направлены. При наложении окружения они позволяют получить координаты u и v. При освещении с помощью них можно найти интенсивность света на поверхности. Фактически нормали используются не только в 3D, они также используются и в 2D. И здесь мы расскажем о них.
Нормали - направление, а не точка в пространстве. Очень важно и удобно то, что нормали всегда направлены под углом 90 градусов относительно поверхности, и направлены от поверхности. Теперь посмотрим, как это выглядит в 2D. Если мы имеем линию, которая идет из (x1, y1) в (x2, y2), то нормаль выглядела следующим образом бы:
Трудность в том, что есть две нормали на одну линию или на одну плоскость. Каждая указывает в своем направлении, каждая противоположна другой нормали. Фактически, мы должны выбрать, какая нормаль является нормалью плоскости, т.е. с какой стороны находится лицевая поверхность плоскости.
В 3D мы имеем и грани и вершины. Грани имеют нормаль и вершины имеют нормаль. До вычисления нормалей вершин, надо вычислить нормаль грани. Пусть мы знаем на грани координаты трех вершин. При помощи векторного произведения двух векторов, которые образованы из двух ребер треугольника с общей начальной точкой, можно вычислить нормаль. Вот так:
nx = ((y1-y2)*(z1-z3))-((z1-z2)*(y1-y3));
ny = ((z1-z2)*(x1-x3))-((x1-x2)*(z1-z3));
nz = ((x1-x2)*(y1-y3))-((y1-y2)*(x1-x3));
При этом мы получим точку в 3D пространстве, которая указывает направление нормали. Это направление от начала координат (0,0,0) до точки нормали. Линия, которая могла бы быть сделана из этих точек, является нашим направлением. Значение нормали, которое мы теперь нашли, можно использовать при кодировании, но это не очень удобно. Так как нормаль - это только направление, не важно, где в 3D пространстве точка нормали помещена, и как далеко она от начала координат (0,0,0). Пример - точка нормали (1000,0,0). Эта точка имеет то же самое направление, как и точка нормали (1,0,0). Фактически, при длине нормали равной единице удобнее вычислять углы между нормалями. Но как мы получим нашу длину вектора, чтобы она равнялась единице? Просто мы делим координаты точки на длину вектора:
length = sqrt((nx*nx)+(ny*ny)+(nz*nz));
nx=nx/length;
ny=ny/length;
nz=nz/length;
С нормалями граней все ясно, а как быть с нормалями вершин? Отлично, у нас есть нормаль к грани под углом 90 градусов к плоскости грани. Поэтому, конечно, нормали вершин должны быть такими же. Но можно ли найти перпендикуляр к точке. Такой вектор может быть направлен в любом направлении. Для того чтобы вычислить нормаль к вершине объекта, мы должны знать все грани, которые используют эту вершину, т.е. нам необходимо вычислить вначале все нормали у всех граней объекта. Затем для каждой вершины мы находим все грани, которые используют эту вершину. Если грань использует вершину, то надо прибавить к нормали вершины нормаль этой грани и так далее. Когда все это будет выполнено, надо разделить нормаль вершины на число граней, в которые она входит. В результате нормаль, рассчитана из нормалей, которые перпендикулярны плоскостям граней, и, следовательно, нормаль в результате тоже перпендикуляр. Только учтите, что у грани есть две противоположные нормали, но даже если взять не лицевую, а противоположную ей нормаль, то в этом нет ничего страшного.
Удаление невидимых поверхностей
Удаление невидимых поверхностей объекта нельзя проиллюстрировать на изображении, чтобы пояснить, что это такое. Если грань направлена от нас, то мы ее не видим. Но можно задаться вопросом – почему мы не видим эту грань, которая направлена от нас, ведь у игральной карты мы видим обе стороны?! Да, мы видим ее, но у карты две грани, а не одна. Кроме этого, если карта повернута нам одной гранью, то вторая грань не видна. Если бы мы оказались внутри карты, то мы бы не увидели ни одну из граней. В реальности, конечно, это не так, но если при создании 3D объекта, вы хотите сделать видимыми ОБЕ стороны объекта, то надо сделать больше граней, чтобы показать сплошные стороны. Мяч содержит много граней, чтобы мяч выглядел сплошным.
Отлично, рассмотрим, что надо сначала сделать. Пусть нам надо показать объект в середине экрана, мы проверяем, если z координата нормали положительна, то грань повернута от нас, значит, она невидима, и ее не надо выводить. Если учесть расположение камеры, то надо сделать скалярное умножение между вектором нормали грани и вектором камеры. Пусть вектор камеры равен (0,0,1) и если ваша лицевая нормаль указывает в том же самом направлении (за экран), то грань невидима. Скалярное умножение выглядит следующим образом:
a = x*x + y*y + z*z
a = 0*0 + 0*0 + 1*1
a = 1
a > 0
Если нормаль грани направлена на экран:
a = 0*0 + 0*0 + 1*-1
a = -1
a < 0
Т.е. ее надо нарисовать.
The coding place