Секция 5 из 6 - Предыдущая - Следующая
Все секции
- 1
- 2
- 3
- 4
- 5
- 6
TILE_V_MASK 00000111 11000111 10000000 00000000
А окончательная версия цикла выглядит вот так:
// ...
u = make_tile_u(u);
v = make_tile_v(v);
du = make_tile_u(du) | TILE_U_MASK;
dv = make_tile_v(dv) | TILE_V_MASK;
for (current_sx = x_start; current_sx <= x_end; current_sx++) {
putpixel(current_sx, current_sy, texture[unfix(u + v)];
u += du;
v += dv;
u &= (~TILE_U_MASK);
v &= (~TILE_V_MASK);
}
// ...
В переводе на ассемблер, заимствованном из все того же fatmap2.txt, все это
выглядит вот так:
mov eax,tile_u_part
mov ebx,tile_v_part
mov ecx,length
mov esi,texture
mov edi,outputbuffer
lea edi,[edi+ecx-1]
xor ecx,-1
lea ebp,[eax+ebx]
inc ecx
inner:
add eax,tile_du
add ebx,tile_dv
shr ebp,16
and eax,11111111110001110111111111111111b ; (~TILE_U_MASK)
and ebx,11111000001110000111111111111111b ; (~TILE_V_MASK)
inc ecx
mov dl,[esi+ebp]
lea ebp,[eax+ebx]
mov [edi+ecx],dl
jnz inner
Осталось упомянуть про то, что тайлы можно расположить не по горизонтали,
а по вертикали:
Текстура в тайлах:
0, 32, 64, ...
1, 33, 65, ...
2, 34, 66, ...
...
Тогда преобразование для целых частей u, v выглядит следующим образом:
tile_number = ((u >> TILEBITS) << (TEXBITS - TILEBITS)) + (v >> TILEBITS);
tile_u = u & TILEMASK;
tile_v = v & TILEMASK;
texture_offset = (tile_number << (2*TILEBITS)) + (tile_v << TILEBITS) +
tile_u;
Выделяя u, v, получаем:
tile_u_part = ((u >> TILEBITS) << (TEXBITS + TILEBITS) + (u & TILEMASK);
tile_v_part = ((v >> TILEBITS) << TILEBITS) +
((v & TILEMASK) << TILEBITS);
то есть
tile_u_part = ((u >> TILEBITS) << (TEXBITS + TILEBITS) + (u & TILEMASK);
tile_v_part = v << TILEBITS;
Все это делается для единственной цели - скорости. В таком виде перевод u, v
в "тайловые координаты" делается немного проще и быстрее; внутрениий цикл же
остается таким же (ну, константы (~TILE_U_MASK) и (~TILE_V_MASK), конечно,
поменять придется, но это непринципиально). Здесь битовая раскладка выглядит
следующим образом:
tile_u_part UUUUU000 00000uuu 0fffffff ffffffff
tile_v_part 00000VVV VVVVV000 0fffffff ffffffff
tile_du UUUUU111 11111uuu 1fffffff ffffffff
tile_dv 00000VVV VVVVV111 1fffffff ffffffff
TILE_U_MASK 00000111 11111000 10000000 00000000
TILE_V_MASK 00000000 00000111 10000000 00000000
Полные формулы (функции) для перевода из 16:16 fixedpoint в "тайловый" 8:15
fixedpoint приведем именно для этого случая; выглядят они вот так:
int make_tile_u(int u) {
return
((u << 8) & 0xF8000000) +
(u & 0x70000) +
((u >> 1) & 0x7FFF);
}
int make_tile_v(int u) {
return
((v << 3) & 0x7F80000) +
((v >> 1) & 0x7FFF);
}
Для полной комплектности осталось только привести кусочек кода для перевода
обычной текстуры в тайловую форму (для случая текстуры 256x256, тайла 8x8,
"вертикального" расположения тайлов).
void tile_texture(char *dst, char *src) {
int u, v;
for (v = 0; v < 256; v++)
for (u = 0; u < 256; u++)
dst[((u << 8) & 0xF800) + (u & 0x7) + ((v << 3) & 0x7F8)] = *src++;
}
7. Разное
=========
7.1. Субпиксельная точность
---------------------------
Субпиксельная точность означает следующее: только те пикселы, центры которых
лежат внутри данного многоугольника, должны быть нарисованы. На самом деле,
в этом определении можно использовать любую (зафиксированную) точку внутри
пиксела, единственным последствием этого будет сдвиг всего экрана меньше, чем
на 0.5 пиксела.
Необходимость в субпиксельной точности появляется только из-за того, что
дисплеи дискретны, состоят из пикселов. Чем меньше становятся пикселы (то
есть, чем выше разрешение), тем меньше важна эта точность. Однако разницу
можно почувствовать даже на разрешениях порядка 1280x1024, а тем более при
обычных для 3D engine 320x200 или 640x480.
Реализовать субпиксельную точность на редкость просто. Представьте себе, что
мы рисуем грань. Обычно мы начинаем рисовать ее с какого-то нецелого start_y,
так как при преобразованиях (например, проецировании) у нас получаются вовсе
не целые числа. Обычно их просто округляют. В результате типичная процедура
рисования треугольника, которая начинает отрисовку с самой верхней точки A и
идет вниз по строкам, на каждой строке пересчитывая координаты начала и конца
рисуемого отрезка как
sx_start += dx_start;
sx_end += dx_end;
теряет субпиксельную точность из-за этого самого округления, так как sx_start
инициализируется как A.sx, A.sx соотвествует линии y = A.sy, а рисовать мы
начинаем с какого-то округленного значения. Кстати, ни один из примеров к
FAQ'у потерей субпиксельной точности не страдает, так как для каждой строки
sx_start и sx_end заново вычисляются по точной формуле.
Точная формула для расчета sx_start выглядит как
sx_start = A.sx + dx_start * (current_sy - A.sy),
и для самой первой линии мы тоже должны ее честно применить, а не просто
положить sx_start = A.sx. Получаем, что
sx_start = A.sx + dx_start * (ceil(A.sy) - A.sy);
sx_end = A.sx + dx_end * (ceil(A.sy) - A.sy);
Ту же самую операцию надо сделать и со всем остальными переменными, которые
мы будем интерполировать по ребрам (например u, v, интенсивность для Гуро);
и то же самое надо сделать при переходе с ребра на ребро.
// ...
u_start += du_start * (ceil(start_y) - start_y);
u_end += du_end * (ceil(start_y) - start_y);
// ...
Ну и, разумеется, рисовать начинать надо с той строки, которую мы использовали
в формулах. То есть, ceil(start_y).
Вот и все. На скорость работы это не влияет вообще, а грани сразу перестают
мелко и противно дрожать при перемещении, особенно сильно это заметно при
маленьких поворотах (в доли градуса).
7.2. Субтексельная точность
---------------------------
Субтексельная точность сильно смахивает на субпиксельную. Необходимость в ней
появляется из-за следующего факта: рисовать строку мы начинаем с какого-то
нецелого sx, но с целого пиксела. Из-за этого (sx может "гулять" в пределах
одного пиксела почти на единицу!) возникает дрожание текстур примерно на тот
самый пиксел. Устраняется это точно таким же сдвигом, как и в субпиксельной
точности, то есть перед отрисовкой строки корректируются начальные значения
величин, интерполируемых по строке (u, v, освещенность...):
// ...
u_start += du_dsx * (ceil(sx) - sx);
v_start += dv_dsx * (ceil(sx) - sx);
// ...
Это уже немного замедляет работу (на величину порядка 5-10%), но улучшение
качества картинки того стоит. Кроме того, субтексельную точность вполне можно
совместить с 2D-отсечением и получить отсечение, которое не съедает никаких
ресурсов и не замедляет работу. Вообще.
7.3. Поворот 3D вектора за шесть умножений
------------------------------------------
Обычно поворот 3D вектора делают умножением матрицы поворота на этот вектор.
Эта операция требует 9 умножений и 6 сложений. Но с использованием небольшого
precalculation (предварительного расчета) ее можно несколько ускорить.
Пусть нам надо умножить какую-то строку матрицы (a,b,c) на вектор (x,y,z).
Результат должен быть равен
r = a*x+b*y+c*z.
То есть как раз по 3 умножения и 2 сложения на одну строку. Но с другой
стороны,
r = a*x+b*y+c*z = (a*x+b*y+a*b+x*y)+c*z-a*b-x*y =
= (a+y)*(b+x)+c*z-a*b-x*y.
Проще эта формула явно не выглядит. Но дело в том, что x*y - это постоянная
величина, так как x, y - это координаты вершины неповернутого объекта, а они
обычно не меняются. А a*b достаточно посчитать при расчете матрицы поворота,
и это тоже постоянная величина для каждой матрицы. Т.о.
r = (a+y)*(b+x)+c*z-c1-c2.
В результате имеем 2 умножения и 4 сложения на одну строку, то есть те самые
6 умножений и 12 сложений на вектор. Выиграли 3 умножения ценой 6 сложений.
7.4. Алгоритм "бегущих кубиков" для полигонизации изоповерхностей
-----------------------------------------------------------------
Сооветствующий английский термин - marching cubes algorithm; приведен здесь,
так сказать, just to avoid any confusion. Алгоритм предназначен для быстрого
построения полигональной модели изоповерхности трехмерного скалярного поля,
заданного значениями на равномерной сетке. Выражаясь менее академичным и,
надеюсь, более понятным языком, этот алгоритм нужен для быстрого построения
набора треугольных граней, достаточно хорошо приближающего изоповерхность,
то есть такую поверхность, на которой определенная функция равна какой-то
константе - изоуровню. Например, сфера радиуса 1 с центром в нуле - это
изоповерхность функции f=1/(x*x+y*y+z*z) для изоуровня 1. Т.н. "3D капли",
столь любимые ныне, тоже являются изоповерхностью, правда, немного более
сложной функции (да, функция задана в трехмерном пространстве):
n
f = sum c[i]/((x[i]-x)*(x[i]-x)+(y[i]-y)*(y[i]-y)+(z[i]-z)*(z[i]-z)),
i=1
где
n - количество источников поля (капелек);
c[i] - интенсивность каждого источника (радиус капельки);
x[i], y[i], z[i] - координаты каждого источника (центра капельки).
Работает алгоритм следующим образом.
Рассматриваем какой-то параллелипипед, внутри которого заведомо находится
изоповерхность (или та ее часть, которую мы хотим нарисовать). Разбиваем
его сеткой, ну, как бы разрезаем его на несколько меньших параллелипипедов,
и считаем значения функции (поля) в узлах сетки, то есть вершинах этих самых
маленьких параллелипипедов. Для большей ясности можно заменить длинное слово
"параллелипипед" на слово "куб" и представить себе кубик Рубика. Теперь
проходим по всем кубикам (дальше я буду везде использовать слово "кубик",
надоело "параллелипипед" писать). Смотрим на значения функции в вершинах
кубика. Если все они больше (или меньше) изоуровня - значит, кубик находится
целиком над (или под) изоповерхностью, внутри этого кубика поверхности нет и
мы его просто отбрасываем. Если же часть больше, а часть меньше, то некоторые
ребра кубика пересекаются с изоповерхностью. Линейной интерполяцией приближаем
эти точки пересечения и в зависимости от того, какие вершины находятся над
изоповерхностью, а какие под, генерируем несколько треугольных граней. Все
вершины этих граней - это как раз точки пересечения поверхности с ребрами.
Как генерировать грани и пересечения каких ребер с поверхностью считать,
смотрим по таблице, это зависит лишь от того, какие вершины находятся над
поверхностью, а какие - под. Вершин восемь, состояний два - над и под. Это
дает нам 256 возможных расположений, так что таблица не такая уж и большая.
Индекс в таблице тоже генерируется совсем просто: если вершина находится
над поверхностью, устанавливаем соответствующий этой вершине бит индекса,
иначе - сбрасываем.
Вот простенький пример.
4--------3
/ | / |
1--------2 |
| | * |
| 8----|---7
| / | *
5---*----6
Пусть точка 6 находится под поверхностью, остальные - над. Тогда поверхность
проходит через точки (*), приближаем их линейной интерполяцией и проводим
через них треугольную грань. Какие ребра пересекаются с поверхностью, какие
точки пересечния и как соединять - узнаем из таблиц по индексу; в данном
случае индекс равен 11011111b=0DFh (установлены все биты, кроме 6го).
Алгоритм по шагам:
* посчитать значения функции в узлах сетки (вершинах кубиков)
* для каждого кубика:
- посчитать индекс этого кубика в таблице. Каждый бит соответствует
какой-то из вершин, если в ней значение функции больше изоуровня,
то надо установить этот бит, иначе - сбросить
- взять из таблицы по индексу кубика слово, каждый бит в котором
определяет, пересекает ли соответствующее ему (биту) ребро кубика
изоповерхность, или нет. Если да, то посчитать (простая линейная
интерполяция между соответствующими ребру вершинами) координаты
точки пересечения
- взять из таблицы по индексу кубика число генерируемых граней и
собственно тройки номеров ребер, (уже посчитанные) пересечения
которых с изоповерхностью и будут вершинами нужных граней
Неоднократно упоминавшиеся магические таблицы приведены в примерчике, там
же приведен кусок кода, который довольно легко переделть под свой engine.
Пример взят с http://www.mhri.edu.au/~pdb/modelling/polygonise, сам по себе
он компилироваться НЕ будет, но все там написано правильно и никаких ошибок
в таблицах нет (так что ищите ошибку в своем коде).
7.5. Формат 3DS-файла
---------------------
Основная идея вот: файл 3DS состоит из блоков (chunks), каждый из которых
содержит какие-то полезные данные и, возможно, подблоки. Большинство блоков
содержит либо данные, либо подблоки, хотя есть и смешанные блоки. Общий
формат каждого блока такой:
смещение | длина | данные
----------+-----------+-------------------------------------------------
0 | 2 | идентификатор типа блока, chunk_id
2 | 4 | длина блока, chunk_len
4 | chunk_len | данные или подблоки (в зависимости от chunk_id)
В качестве относительно полного описания конкретного содержимого блоков
я бы порекомендовал следующие вещи:
- исходники 3DS reader от MRI/Doomsday, читаются они просто великолепно.
Скачать можно на ftp://ftp.cdrom.com/pub/demos/code/3ds/3dsrdr13.zip;
- 3dsinfo.txt от digisnap.
Здесь я приведу лишь частичное описание, достаточное, впрочем, для того,
чтобы прочитать из 3DS-файла 3D сцену и информацию о ее (сцены) анимации.
Итак, список идентификаторов типов нужных нам для этого блоков:
CHUNK_MAIN = 0x4D4D; // [-] сцена
CHUNK_OBJMESH = 0x3D3D; // [-] всяческие объекты
CHUNK_OBJBLOCK = 0x4000; // [+] объект
CHUNK_TRIMESH = 0x4100; // [-] trimesh-объект
CHUNK_VERTLIST = 0x4110; // [+] список вершин
CHUNK_FACELIST = 0x4120; // [+] список граней
CHUNK_FACEMAT = 0x4130; // [+] материалы граней
CHUNK_MAPLIST = 0x4140; // [+] текстурные координаты
CHUNK_TRMATRIX = 0x4160; // [+] матрица перевода
CHUNK_CAMERA = 0x4700; // [+] объект-камера
CHUNK_MATERIAL = 0xAFFF; // [-] материал
CHUNK_MATNAME = 0xA000; // [+] название материала
CHUNK_TEXTURE = 0xA200; // [-] текстура материала
CHUNK_MAPFILE = 0xA300; // [+] имя файла текстуры
CHUNK_KEYFRAMER = 0xB000; // [-] информация об анимации
CHUNK_TRACKINFO = 0xB002; // [-] поведение объекта
CHUNK_TRACKOBJNAME = 0xB010; // [+] название этого объекта
CHUNK_TRACKPIVOT = 0xB013; // [+] центр вращения объекта
CHUNK_TRACKPOS = 0xB020; // [+] траектория объекта
CHUNK_TRACKROTATE = 0xB021; // [+] траектория вращения объекта
CHUNK_TRACKCAMERA = 0xB003; // [-] поведение камеры
CHUNK_TRACKFOV = 0xB023; // [+] поведение FOV камеры
CHUNK_TRACKROLL = 0xB024; // [+] поведение roll камеры
CHUNK_TRACKCAMTGT = 0xB004; // [-] поведение "цели" камеры
Конкретные данные содержат лишь блоки, отмеченные плюсом, остальные блоки
состоят лишь из подблоков и их нам надо различать лишь потому, что нужные
нам блоки данных - подблоки этих остальных. То есть, скажем, CHUNK_OBJMESH
нам надо знать из-за того, что каждый объект в сцене описывается блоком
CHUNK_OBJBLOCK, который появляется только как подблок CHUNK_OBJMESH, и
просто игнорировать весь CHUNK_OBJMESH из-за этого нельзя. Кроме того, они
задают структуру - например, все данные, что относятся к текущему блоку
CHUNK_OBJBLOCK, относятся к текущему объекту, а подблоки этого блока уже
могут быть разбросаны как угодно.
А теперь - относительно полное описание того, какие данные содержатся в
каждом из блоков. Будут использоваться следующие обозначения:
char[] - ASCIIZ-строка (ASCII-строка, оканчивающаяся нулем)
byte - 8-битное беззнаковое целое число
word - 16-битное беззнаковое целое число
dword - 32-битное целое число
float - 32-битное число с плавающей запятой
vector - float x,z,y
Здесь (в самой последней строчке) опечатки нет! В файле 3DS везде изменен
порядок следования y и z; то есть в файле данных ось y смотрит вглубь экрана,
а ось z - вверх. Несмотря на то, что в самой 3D Studio ось y смотрит как раз
вверх, а z - вдаль.
Блок : CHUNK_VERTLIST
Данные : список вершин текущего объекта
Формат :
word num; // число вершин
vector vertices[num]; // координаты каждой из вершин
Блок : CHUNK_FACELIST
Данные : список граней текущего объекта
Формат :
word num; // число граней
struct { //
word v0; // номер первой вершины грани
word v1; // номер второй вершины грани
word v2; // номер третьей вершины грани
word flags; // флаги грани
} faces[num]; // собственно список граней
Блок : CHUNK_FACEMAT
Данные : название материала и список тех граней объекта, которым назначен
этот материал; таких блоков может быть несколько (грани с разными
материалами в одном объекте), а может вообще не быть, если объекту
материалы вообще не назначены (нетекстурированный объект)
Формат :
char name[]; // название материала
word num; // число граней из этого материала
word face_nums[num]; // список номеров граней из этого материала
Блок : CHUNK_MAPLIST
Данные : текстурные координаты вершин текущего объекта
Формат :
word num; // число вершин
struct { //
float u; // координата текстуры U (по горизонтали)
float v; // координата текстуры V (по вертикали)
} texcoords[num]; // собственно список текстурных координат
Текстурные координаты задаются в диапазоне 0..1. Точка с U=0, V=0 - левый
верхний край текстуры; U=1, V=1 - правый нижний; U=0.5, V=0.5 - центр
текстуры.
Блок : CHUNK_TRMATRIX
Данные : содержит матрицу перевода объекта в некое абстрактное начальное
состояние; в то, что было первоначально смоделировано. Требуется
для корректного отображения анимации: дело в том, что все объекты
в файле хранятся по состоянию на нулевой кадр, а анимация записана
по отношению к "начальным" моделям. Т.е. при отображений нулевого
кадра эта матрица не нужна, а при отображении всего набора кадров
надо будет сначала перевести объекты в "начальное" состояние с
помощью этой самой матрицы перевода и применять все преобразования
(перемещения, повороты, etc) именно к "начальным" объектам.
Формат :
float rotmatrix[3][3]; // матрица поворота
vector offset; // смещение начального объекта
Для перевода объекта в "начальное" состояние надо сначала сдвинуть его
назад, то есть на вектор -offset (НЕ на offset), а потом применить матрицу
поворота rotmatr. Матрица записана построчно. Не забудьте - в ней y и z
тоже везде обменены местами!
Блок : CHUNK_MATNAME
Данные : название материала
Формат :
char[] name; // название материала
Блок : CHUNK_MAPFILE
Данные : имя файла с текстурой
Формат :
char[] filename; // имя файла с текстурой
Блок : CHUNK_TRACKOBJNAME
Данные : название объекта, информация о поведении которого задается в
текущем блоке CHUNK_TRACKINFO
Формат :
char[] name; // название объекта
word flags[2]; // флаги
word parent; // номер объекта-родителя
Поле parent используется для построения иерархической структуры; дерева
объектов. Каждому объекту присваивается его порядковый номер при следовании
в файле, поле parent выставляется в -1, если у данного объекта нет родителя.
Вот пример.
объект | номер | parent
--------+-------+--------
A | 0 | -1
B | 1 | 0 A
C | 2 | 1 +-----------------+----------------+
D | 3 | 2 B K N
E | 4 | 1 +----+----+ + +
F | 5 | 4 C E H L O
G | 6 | 5 + + + + +
H | 7 | 1 D F I M P
I | 8 | 7 + +
J | 9 | 8 G J
K | 10 | 0
L | 11 | 10
M | 12 | 11
N | 13 | 0
O | 14 | 13
P | 15 | 14
Насколько я понял, дерево используется следующим образом: если к какому-то
узлу дерева применяется преобразование, то оно же автоматически применяется
и ко всем узлам, "растущим" из этого. То есть, если объект B в нашем примере
есть рука, а объекты C, D, E, F, G, H, I, J - пальцы, то при повороте руки
пальцы должны повернуться автоматически, вместе с рукой. В результате блок
CHUNK_TRACKROTATE для пальцев может быть пустым, а пальцы будут вращаться
вместе с рукой.
Блок : CHUNK_TRACKPIVOT
Данные : координаты центра вращения объекта
Формат :
vector pivotpoint; // координаты центра вращения
Центр вращения - это как раз та точка "начального" объекта, через которую
надо будет провести ось вращения, задающуюся в блоке CHUNK_TRACKROTATE.
Блок : CHUNK_TRACKPOS
Данные : траектория объекта, заданная ключевыми значениями положения объекта
Формат :
word flags; // флаги
byte unknown[8]; // <неизвестно>
dword num; // число ключевых значений
struct { //
dword frame; // кадр данного ключевого значения
word splineflags; // флаги сплайна
float[] splineinfo; // параметры сплайна (кол-во и тип зависят от
// значения splineflags)
vector pos; // положение объекта
} keys[num]; // собственно ключевые значения
Блок : CHUNK_TRACKROTATE
Данные : траектория вращения объекта, заданная ключевыми значениями вектора
направления оси вращения и угла поворота относительно этой оси
Формат :
word flags; // флаги
byte unknown[8]; // <неизвестно>
dword num; // число ключевых значений
struct { //
dword frame; // кадр данного ключевого значения
word splineflags; // флаги сплайна
float[] splineinfo; // параметры сплайна (кол-во и тип зависят от
// значения splineflags)
float angle; // угол поворота (в радианах)
vector rotaxis; // ось вращения
} keys[num]; // собственно ключевые значения
Только самое первое ключевое значение задает абсолютный поворот. Все
последующие задают "добавочный" поворот, который надо добавить ко всем,
уже сделанным. То есть, во второй ключевой позиции мы последовательно
применяем повороты, заданные первым и вторым ключом, в третьей - первым,
вторым и третьим, и так далее.
Блок : CHUNK_TRACKCAMERA
Данные : траектория камеры, заданная ключевыми значениями положения, угла
зрения, ориентации камеры
Формат :
Состоит из подблоков CHUNK_TRACKOBJNAME, CHUNK_TRACKPOS, CHUNK_TRACKFOV,
CHUNK_TRACKROLL и некоторых других, которые можно безболезненно игнорировать.
Блок : CHUNK_TRACKFOV
Данные : поведение FOV (угла зрения) камеры, заданное ключевыми значениями
Формат :
word flags; // флаги
byte unknown[8]; // <неизвестно>
dword num; // число ключевых значений
struct { //
dword frame; // кадр данного ключевого значения
word splineflags; // флаги сплайна
float[] splineinfo; // параметры сплайна (кол-во и тип зависят от
// значения splineflags)
float FOV; // значение FOV
} keys[num]; // собственно ключевые значения
Блок : CHUNK_TRACKROLL
Данные : поведение roll (угла наклона) камеры, заданное ключевыми значениями
Формат :
word flags; // флаги
byte unknown[8]; // <неизвестно>
dword num; // число ключевых значений
struct { //
dword frame; // кадр данного ключевого значения
word splineflags; // флаги сплайна
float[] splineinfo; // параметры сплайна (кол-во и тип зависят от
// значения splineflags)
float roll; // значение roll
} keys[num]; // собственно ключевые значения
Блок : CHUNK_TRACKCAMTGT
Данные : траектория "цели" камеры (точки, куда камера смотрит), заданная
ключевыми значениями положения
Формат :
Состоит из подблоков CHUNK_TRACKOBJNAME, CHUNK_TRACKPOS и некоторых других,
которые можно безболезненно игнорировать.
Теперь к вопросу о сплайнах и их параметрах. Всего может быть до пяти разных
параметров сплайна, появление каждого из них задается каким-то битом в
поле splineflags:
- установлен бит 0: следует параметр "tension"
- установлен бит 1: следует параметр "continuity"
- установлен бит 2: следует параметр "bias"
- установлен бит 3: следует параметр "ease to"
- установлен бит 4: следует параметр "ease from"
То есть при чтении флагов надо последовательно тестировать каждый бит и,
если он установлен, читать соответствующий параметр; если не установлен,
значит, параметр равен нулю. 3D Studio использует сплайны Кочанека-Бартельса
(Kochanek-Bartels) для интерполяции положения и поворотов, при этом повороты
вдобавок представляются в форме кватернионов, в ней же и интерполируются.
7.6. Сплайны Кочанека-Бартельса
-------------------------------
Пусть у нас имеется набор моментов времени и заданные значения какой-то
функции (например, координат положения объекта) в эти моменты. Для того,
чтобы получить значение функции в какой-то промежуточный момент времени,
между заданными моментами ее придется интерполировать. Самый простой случай,
конечно, линейная интерполяция (точнее говоря, кусочно-линейная), когда
между любыми двумя заданными точками p1, p2 значение интерполируется по
следующей формуле:
f(t) = p1.value + (p2.value - p1.value) * t.
Здесь t - "локальное" время, t=0 в точке p1 и t=1 в точке p2, pi.value -
значение интерполируемой величины в точке pi. Перевод "локального" времени t
в "глобальное" время T и наоборот тривиален:
t = (T - p1.T) / (p2.T - p1.T),
T = p1.T + t * (p2.T - p1.T).
Результат получится такого вида:
value p2
| ---*
| ---- \ * p4
| *--- \ /
| p1 \ /
| * p3
---O-----------------------------T
|
Но в результате такой интерполяции получаются ломаные - негладкие функции.
Визуально это выливается во внезапно дергающиеся, неожиданно меняющие
направление движения объекты и камеру. Негладкость можно математически
описать как разрывность производной функции, получающейся в результате
интерполяции; в точках задания значений у нас производная будет резко
меняться.
Интерполяция сплайнами - такой метод, который дает в результате гладкую
функцию. Достигается это следующим образом: между каждыми двумя точками
функция интерполируется кубической параболой (то есть, полиномом третьей
степени, вида P(x) = a*x^3+b*x^2+c*x+d), причем функция подбирается так,
чтобы на концах отрезка (как раз в точках задания значений) совпадали с
какими-то заранее заданными числами и сами значения функции, и значения
производной. Совпадение самих значений функции требуется для непрерывности
получаемой приближающей функции, а совпадение значений производной - для
непрерывности производной, то есть для "гладкости" приближающей функции.
Таким образом, результат интерполяции у нас получается составленным не из
прямых, как при кусочно-линейной интерполяции, а из "сшитых" кусков разных
кубических парабол. Причем эта кривая получается еще и гладкой, так как мы
"сшиваем" не только сами значения функции, но и значения ее производной.
Пусть на концах отрезка "локального" времени [0,1] заданы значения функции
p1, p2 и значения производной r1, r2. Приближающая функция - кубическая,
то есть
f(t) = a*t^3 + b*t^2 + c*t + d,
f'(t) = 3*a*t^2 + 2*b*t + c,
откуда и получаем:
f(0) = p1,
f(1) = p2,
f'(0) = r1,
f'(1) = r2,
d = p1,
a + b + c + d = p2,
c = r1,
3*a + 2*b + c = r2.
Решив эту систему уравнений, получаем:
a = 2*p1 - 2*p2 + r1 + r2,
b = -3*p1 + 3*p2 - 2*r1 -r2,
c = r1,
d = p1,
отсюда
f(t) = (2*p1 - 2*p2 + r1 + r2) * t^3 + (-3*p1 + 3*p2 - 2*r1 - r2) * t^2 +
r1 * t + p1,
или, что равносильно,
f(t) = p1 * (2*t^3 - 3*t^2 + 1) + r1 * (t^3 - 2*t^2 + t) +
p2 * (-2*t^3 + 3*t^2) + r2 * (t^3 - t^2).
Подставляем сюда значения интерполируемой величины в начале и конце отрезка
(p1 и p2), желаемые значения производных в начале и конце отрезка (r1 и r2),
локальное время для отрезка интерполяции t, и получаем интерполированное
значение функции в любой точке отрезка - кусок кубической параболы, который
проходит через точки (0,p1), (1,p2) и имеет в точках t=0 и t=1 производные
r1 и r2 соответственно.
Осталось выяснить, откуда брать значения производных r1, r2. Они считаются
через заданные (они же ключевые) значения нашей функции в самой точке-ключе,
следующей и предыдущей точке, а также параметры сплайна tension, continuity
и bias в данной точке. Все это (значения функции и набор параметров сплайна
в каком-то наборе точек) задается извне; то есть, например, читается из
3DS-файла.
Введем следующие обозначения. Пусть cur - текущая точка, next - предыдущая,
prev - следующая, r - производная в текушей точке cur, которую мы и должны
как-то посчитать. Пусть
g1 = cur.value - prev.value,
g2 = next.value - cur.value,
g3 = g2 - g1.
Тогда по умолчанию (это когда параметры tension, continuity, bias равны 0)
производная считается как
r = g1 + 0.5 * g3.
Параметры tension, continuity и bias соответственно изменяют вес g3, а также
значения r, g1, g2; с учетом этих параметров формула для производной выглядит
следующим образом:
g1 = (cur.value - prev.value) * (1 + bias),
g2 = (next.value - cur.value) * (1 - bias),
g3 = g2 - g1,
ra = (1 - tension) * (g1 + 0.5 * g3 * (1 + continuity)),
rb = (1 - tension) * (g1 + 0.5 * g3 * (1 - continuity)).
Здесь уже появляются два разных значения производной ra и rb. ra - это то
значение производной, которое используется, когда точка является началом
отрезка сплайн-интерполяции; rb - когда концом. То есть, при интерполяции
между какими-то точками p1, p2 используются значения r1 = p1.ra, r2 = p2.rb.
При continuity = 0 они (ra и rb) равны, при continuity = 1 ra удваивается,
а rb становится равным нулю. Таким образом, параметр continuity контролирует
"изломанность", негладкость сплайна.
Геометрический смысл всех этих параметров нагляднее всего можно показать в
случае, когда value - 2D-вектор. Тогда cur, prev, next - какие-то точки на
плоскости, сплайн - проведенная через них кривая, r - вектор-градиент
кривой в точке cur, он же является касательной (точнее, направляющим вектором
Секция 5 из 6 - Предыдущая - Следующая
© faqs.org.ru
