Секция 2 из 6 - Предыдущая - Следующая
Все секции
- 1
- 2
- 3
- 4
- 5
- 6
значение z; если оно больше, чем значение в z-буфере (точка закрыта какой-то
другой точкой), или меньше, чем -dist (точка находится за камерой), то
переходим к следующей точке. Если меньше, то рисуем точку на экране (или в
видеобуфере), а в z-буфер записываем текущее значение z. Вот кусок кода для
лучшего понимания:
// ...
if (z > -dist && z < zbuffer[screenX][screenY]) {
screen[screenX][screenY] = color;
zbuffer[screenX][screenY] = z;
}
// ...
Имеет смысл считать значения не z, а z1 = 1/(z+dist), так как эта величина
изменяется по грани линейно, и линейная интерполяция дает точные результаты
(более подробно это описано в 4.3). Тогда условия чуть изменяются - точка
загорожена другой, если значение z1 *меньше* значения в z-буфере; и точка
находится за камерой, если z1 < 0. Буфер инициализируем нулями. Тогда
не нежна проверка на положительность z1 - точка попадает в z-буфер и на
экран, только если z1 больше текущего значения, и поэтому точки, для которых
z1 < 0 в буфер и без проверки никогда не попадут. Код тоже чуть изменится:
// ...
if (z1 > zbuffer[screenX][screenY]) {
screen[screenX][screenY] = color;
zbuffer[screenX][screenY] = z1;
}
// ...
Вот и все. Осталось упомянуть, что этот метод иногда называют w-буфером,
подчеркивая разницу между хранением z и какой-то обратной величины, w.
Это самый простой метод удаления невидимых частей, причем всегда дающий
полностью правильные результаты. Единственная проблема - скорость, z-буфер,
как самый простой, является и самым медленным методом.
3.4. Порталы
------------
Этот метод предназначен для т.н. indoor environments - в буквальном переводе
"комнатная среда"; это как бы внутренность какого-то здания. В качестве
примера могут служить Doom, Quake.
В этом случае сцена составляется из комнат. Комнаты связаны друг с другом
какими-то проходами - дверями, окнами, чем угодно. На каждый такой проход
вешается обычный полигон, называемый порталом. Для отрисовки сцены достаточно
нарисовать текущую комнату вместе с тем, что из нее видно. Но то, что из нее
видно, может быть видно *только* через порталы.
Таким образом, для отрисовки всей сцены мы просто берем и рисуем текущую
комнату, используя любые методы удаления невидимых частей (например, алгоритм
художника и отброс нелицевых граней). А если в процессе отрисовки нам
встречается полигон, помеченный как портал, то мы рисуем комнату, которую
видно через этот портал, причем отсекаем ее уже по проекции этого портала.
Как обычно, кусок кода для уяснения:
// ...
void drawRoom(int roomID, polygon *clipArea) {
int i;
for (i = 0; i < rooms[roomID].numFaces; i++)
drawFace(&rooms[roomID].face[i], clipArea);
}
void drawFace(polygon *face, polygon *clipArea) {
polygon *newClipArea;
if (face->isPortal) {
if (isVisible(face, clipArea) {
newClipArea = clipPolygon(face, clipArea);
drawRoom(face->destinationRoom, newClipArea);
}
} else drawClippedPolygon(face, clipArea);
}
// ...
drawRoom(currentRoom, fullScreen);
// ...
Здесь функция isVisible(face, clipArea) возвращает false, если грань face и
область отсечения clipArea не пересекаются; функция clipPolygon возвращает
пересечение полигонов face и clipArea (то есть отсекает face в clipArea и
наоборот); fullScreen - полигон размером с экран (или любую нужную область
отрисовки).
В природе есть Alpha 2 - готовый engine, использующий порталы и написанный на
TMT Pascal, причем, что приятно, доступный в исходниках. Скачать его когда-то
было можно с http://www.geocities.com/CapeCanaveral/5402. Есть, впрочем,
надежда, что найти этот engine особых проблем не составит.
Осталось упомянуть, что несмотря на то, что в изложенной форме метод и требует
возможности отрисовки произвольной грани, отсеченной в произвольную грань,
можно обойтись и отсечением по bounding box проекции портала.
3.5. Z-отсечение
----------------
Необходимость в этой процедуре возникает, когда, в конце концов, оказывается,
что надо нарисовать грань, у которой часть вершин лежит перед камерой, а
часть - за камерой. То есть грань, пересекающуюся с экраном. Сама по себе
она правильно не нарисуется.
Поскольку камера видит только то, что перед ней находится, все те точки, для
которых z < -dist, рисовать не надо. То есть, каждую грань надо обрезать
плоскостью z = -dist. Принципиально различных случаев расположения грани
относительно этой плоскости может быть всего четыре; когда перед камерой
находятся соответственно 0, 1, 2 или 3 вершины. Первый и последний случаи
тривиальны - если перед камерой находится 0 вершин, то грань просто не видна
и рисовать ее не надо; если 3 вершины, то грань видна целиком и полностью и
ее достаточно просто взять и нарисовать. Рассмотрим оставшиеся два случая.
Случай первый, когда перед камерой находится только одна вершина:
|
|
A |
/ \|
B D
\ |\
\ | \
E \
| \ \
| \\
| C
|
--------|-------------------------> z
|
| z = -dist
|
В этом случае перед камерой находится только треугольник CDE. Его и надо
будет нарисовать вместо грани.
Случай второй, когда перед камерой находятся две вершины:
|
|
| A
|/ \
D B
/| /
/ | /
/ E
/ / |
// |
C |
|
--------|-------------------------> z
|
| z = -dist
|
Здесь уже надо будет нарисовать трапецию DABE; она разбивается на два
треугольника, DAB и DBE. Их и рисуем вместо грани.
Координаты и текстурные координаты для точек D, E считаются совсем просто:
с одной стороны, D лежит на AC, с другой стороны, D.z = -dist. Для точки D
как лежащей на AC любая величина t (вместо t подставляем x/y/u/v) считается
следующим образом:
D.t = A.t + (C.t - A.t) * (D.z - A.z) / (C.z - A.z) =
= A.t + (C.t - A.t) * (-dist - A.z) / (C.z - A.z)
Все это сводится в следующий алгоритм отрисовки грани:
- выясняем, сколько вершин лежит перед камерой; то есть - какой из
случаев мы имеем;
- ставим точки A, B, C в соответствие с вершинами (то есть, если
вершина v0 находится перед камерой, а вершины v1, v2 - нет, то
имеем первый случай, где C = v0, A = v1, B = v2);
- считаем, если нужно, координаты D, E;
- рисуем (или добавляем в список отрисовки) полученные треугольники.
Осталось только добавить, что обрезание на самом деле надо проводить не
плокостью z = -dist, а плоскостью z = -dist + smallvalue, smallvalue > 0,
чтобы избежать проблем при проецировании.
3.6. Отсечение
--------------
В процессе отрисовки граней мы почти сразу столкнемся со следующей неприятной
ситуацией: проекция грани лежит в плоскости экрана, но она вовсе не обязана
точно попадать в прямоугольник-экран. Поэтому эту самую проекцию желательно
корректно обрезать по границе экрана (можно, конечно, выводить все на экран
через свою функцию putpixel() и проверять в ней x, y на попадание в экран,
но это извращение и вдобавок очень медленно). Операцией обрезания как раз и
занимаются разные алгоритмы отсечения (clipping).
3.6.1. Отсечение при растеризации
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Это, пожалуй, самый простой, довольно быстрый и наиболее часто используемый
метод отсечения. Идея, как обычно, проста. При растеризации треугольника мы
в конечном итоге рисуем набор горизонтальных отрезков. Так и будем обрезать
по границам экрана именно отрезки. Пусть мы рисуем отрезок от start_x до
end_x по строке с y = current_sy. Возможны следующие случаи:
- (current_sy < 0), или (current_sy >= YSIZE), или (start_x >= XSIZE),
или (end_x <= 0). Тогда отрезок вообще не виден и мы его не рисуем.
Причем если (current_sy >= YSIZE), то отрисовку грани прекращаем.
- (start_x < 0). В этом случае нам надо пропустить первые (-start_x)
пикселов, так что сдвигаем все интерполируемые по отрезку величины
на (-start_x) пикселов и делаем start_x равным нулю. Например, для
аффинного текстурирования надо сдвинуть u и v:
u += (-start_x) * du;
v += (-start_x) * dv;
start_x = 0;
- (end_x >= XSIZE). Здесь совсем просто. Так как интерполируем мы, начиная
с начала отрезка, достаточно просто сделать end_x = XSIZE - 1.
Таким образом, все отсечение делается несколькими строками кода:
// ...
if (current_sy >= YSIZE) return;
if ((current_sy < 0) || (start_x >= XSIZE) || (end_x <= 0)) break;
if (start_x < 0) {
u -= start_x * du; // пример для аффиного текстурирования
v -= start_x * dv;
}
if (end_x >= XSIZE) end_x = XSIZE - 1;
// ...
Самое приятное заключается в том, что два умножения, которые получаются в
случае (start_x < 0), можно легко совместить с теми двумя, что нужны для
субтексельной точности (см.п.7.2). А несколько сравнений и присваивание на
одну линию делаются достаточно быстро. Получаем отсечение, практически не
замедляющее скорость работы.
3.6.2. Алгоритм Сазерленда-Ходжмана
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Этот алгоритм (Sutherland-Hodgman algorithm) предназначен, на самом деле,
для отсечения произвольного полигона (даже не обязательно выпуклого, хотя
использовать невыпуклые полигоны довольно, на мой взгляд, нерационально)
в полуплоскость, или, для 3D случая, в полупространство; другими словами,
отсечения полигона прямой или плоскостью. Применяя алгоритм несколько раз,
получаем методы отсечения в выпуклый полигон (например, прямоугольник,
которым является экран) или выпуклый объем (например, ту часть пространства,
которую видно из камеры).
Итак, пусть у нас есть полигон с N вершинами, заданными в каком-то порядке,
то есть, по часовой стрелке или против; в каком именно, алгоритму все равно.
Занумеруем их от 0 до N-1. Теперь последовательно обходим все ребра полигона:
ребро от вершины 0 до вершины 1, от 1 до 2, ..., от N-2 до N-1, от N-1 до 0.
Вершины, являющиеся началом и концом ребра, могут лежать в области отсечения,
(область отсечения - либо полуплоскость для 2D случая, либо полупространство
для 3D случая) могут и не лежать; возможны следующие случаи:
- начало лежит в области отсечения, конец - тоже. Тогда просто добавляем
начало к вершинам полигона-результата.
- начало лежит в области отсечения, конец не лежит. В этом случае считаем
точку пересечения ребра и границы области отсечения, добавляем в список
вершин результата начало ребра и вслед за ним точку пересечения.
- начало не лежит в области отсечения, конец лежит. Тоже считаем точку
пересечения, и добавляем только ее.
- начало не лежит в области отсечения, конец тоже. Переходим к следующему
ребру, никак не изменяя результат.
Рассмотрим простенький пример работы алгоритма в 2D случае, а именно отсечем
2D треугольник прямой. Она делит плоскость на две полуплоскости, две области,
нужную и ненужную.
|
отсекаемая | нужная
область | 1 область
| /..\
| /.....\
A........\
/ |.........\
/ |..........\
0-----B-----------2
|
|
- шаг 1, ребро 0-1: вершина 0 не лежит в нужной области, вершина 1 лежит.
Ищем точку пересечения, находим точку A, добавляем ее в список вершин
результата. Теперь этот список состоит из одной вершины A.
- шаг 2, ребро 1-2: обе вершины лежат в области, добавляем вершину 1.
Результат теперь являет собой список A, 1.
- шаг 3, ребро 2-0: 2 лежит в области, 0 не лежит. Добавляем вершину 2 и
точку пересечения B. После последнего шага, таким образом, получили
корректный результат отсечения - полигон с вершинами A, 1, 2, B.
В случае, когда надо сделать отсечение в экран, последовательно применяем
алгоритм, отсекая полигон прямыми sx=0, sx=XSIZE, sy=0, sy=YSIZE. Из-за
такого простого вида уравнений прямых соответственно упрощается код для
выяснения принадлежности вершины нужной области и поиска точки пересечния.
Вот, например, кусок кода для отсечения полигона прямой sx=0 (оставляющий
область sx > 0).
// dst - массив для сохранения вершин результата
// src - массив вершин исходного полигона
// n - число вершин исходного полигона
// функция возвращает число вершин результата
int clipLeft(vertex *dst, vertex *src, int n) {
int i, r;
vertex p1, p2;
float k;
r = 0;
for (i = 0; i < n; i++) {
p1 = src[i];
p2 = src[(i + 1) % n];
if (p1.sx >= 0) { // если начало лежит в области
if (p2.sx >= 0) { // если конец лежит в области
dst[r++] = p1; // добавляем начало
} else { // если конец не лежит в области
dst[r++] = p1; // добавляем начало
k = -p1.sx / (p2.sx - p1.sx); // добавляем точку пересечения
dst[r].sx = 0;
dst[r].sy = p1.sy + k * (p2.sy - p1.sy);
dst[r].u = p1.u + k * (p2.u - p1.u);
dst[r].v = p1.v + k * (p2.v - p1.v);
r++;
}
} else { // если начало не лежит в области
if (p2.sx >= 0) { // если конец лежит в области
k = -p1.sx / (p2.sx - p1.sx); // добавляем точку пересечения
dst[r].sx = 0;
dst[r].sy = p1.sy + k * (p2.sy - p1.sy);
dst[r].u = p1.u + k * (p2.u - p1.u);
dst[r].v = p1.v + k * (p2.v - p1.v);
r++;
}
}
}
return r;
}
Видно, что можно чуточку перемешать код обработки разных случаев, изменить
порядок действий алгоритма и тем самым подсократить исходник, да и сделать
алгоритм проще и понятнее:
// dst - массив для сохранения вершин результата
// src - массив вершин исходного полигона
// n - число вершин исходного полигона
// функция возвращает число вершин результата
int clipLeft(vertex *dst, vertex *src, int n) {
int i, r;
vertex p1, p2;
float k;
r = 0;
for (i = 0; i < n; i++) {
p1 = src[i];
p2 = src[(i + 1) % n];
if (p1.sx >= 0) { // если начало лежит в области
dst[r++] = p1; // добавляем начало
}
if (((p1.sx > 0) && (p2.sx < 0)) || // если ребро пересекает границу
((p2.sx >= 0) && (p1.sx < 0))) // добавляем точку пересечения
{
k = -p1.sx / (p2.sx - p1.sx);
dst[r].sx = 0;
dst[r].sy = p1.sy + k * (p2.sy - p1.sy);
dst[r].u = p1.u + k * (p2.u - p1.u);
dst[r].v = p1.v + k * (p2.v - p1.v);
r++;
}
}
return r;
}
Написав аналогичные куски кода для остальных трех сторон экрана, получим
функцию отсечения в экран по алгоритму Сазерленда-Ходжмана.
3.6.3. 3D-отсечение
~~~~~~~~~~~~~~~~~~~
В пунктах 3.6.1 и 3.6.2 делался упор на 2D-отсечение, т.е. отсечение экраном
уже спроецированного полигона. Еще один метод - это 3D-отсечение, когда все
полигоны отсекаются областью зрения камеры. В этом случае после проецирования
полигон заведомо попадает в экран и дальнейшее отсечение уже не требуется.
Кстати, z-отсечение при 3D-отсечение делается почти автоматически, очень
хорошо вписываясь в общую схему, при использовании же 2D-отсечения придется
делать еще и его.
Рассмотрим стандартную камеру. Ее область зрения задается "пирамидой",
ограниченной пятью плоскостями со следующими уравнениями (откуда взялось
smallvalue и что это такое, написано в п.3.5):
z = -dist + smallvalue
y = (z + dist) * ySize / (2 * dist)
y = -(z + dist) * ySize / (2 * dist)
x = (z + dist) * xSize / (2 * dist)
x = -(z + dist) * xSize / (2 * dist)
Вот рисунок (вид сбоку), на котором видно первые три из этих плоскостей.
y
| ===
| | ===
| ===
| ===|
| === |
=|= |
----*==-|-------O-----------z
=|= |
| === |
| ===|
| ===
| | ===
| ===
|
Отсекаем полигон каждой из этих плоскостей по тому же самому алгоритму
Сазерленда-Ходжмана, получаем 3D-отсечение.
Теперь выясним, как это самое отсечение сделать относительно универсально
(а не только для стандартной камеры), быстро и просто. Зададим наши пять
плоскостей не в форме какого-то уравнения, а в форме
plane = [o, n],
где o - какая-то точка, принадлежащая плоскости; n - нормаль, смотрящая в
то полупространство, которое мы хотим оставить. Например, для стандартной
камеры в этом случае плоскости запишутся так:
n = (0, 0, 1), o = (0, 0, -dist + smallvalue)
n = (0, -dist, ySize/2), o = (0, 0, -dist)
n = (0, dist, ySize/2), o = (0, 0, -dist)
n = (-dist, 0, xSize/2), o = (0, 0, -dist)
n = ( dist, 0, xSize/2), o = (0, 0, -dist)
При такой форме задания плоскости критерий принадлежности произвольной точки
p нужному нам полупространству выглядит очень просто:
(p - o) * n >= 0.
Не менее просто выглядит и процедура поиска пересечения отрезка от точки p1
до точки p2 с плоскостью. Для любой точки p внутри отрезка имеем
p = p1 + k * (p2 - p1), 0 <= k <= 1,
но так как p лежит в плоскости, p * n = 0; отсюда имеем
(p1 * n) + (k * (p2 - p1) * n) = 0,
k = -((p2 - p1) * n) / (p1 * n) =
= (p1 * n - p2 * n) / (p1 * n) =
= 1 - (p2 * n) / (p1 * n).
и моментально находим точку пересечения. Все 3D-отсечение, таким образом,
сводится к последовательному применению одной универсальной процедуры
отсечения плоскостью. Кроме того, видно, что можно посчитать матрицу перевода
стандартной камеры в произвольную, применить ее к выписанным точкам o и
нормалям n для плоскостей, задающих "стандартную" область зрения (к нормалям,
естественно, надо применить только "поворотную" часть матрицы) и получить,
таким образом, уравнения плоскостей уже для *любой* камеры. Тогда 3D-отсечение
можно сделать вообще до всяческих преобразований сцены, минимизировав, таким
образом, количество поворотов и проецирований вершин - не попавшие в область
зрения вершины поворачивать и проецировать, очевидно, не надо. Проецирования
невидимых вершин, впрочем, можно избежать и другим образом: сделав поворот
сцены, а потом 3D-отсечение "стандартной" областью зрения камеры.
Рассмотрим это более подробно. Пусть у нас есть какая-то камера; пусть есть
матрица, которая переводит стандартную камеру в эту камеру. Она как бы состоит
из двух частей: матрицы T (обозначения здесь использутся те же самые, что в
п.2.5) и матрицы параллельного переноса, совмещающей Ss и s (обозначим ее
буквой M). Причем сначала применяется матрица M, потом матрица T. Так вот,
для перевода какой-то плоскости-ограничителя области зрения стандартной
камеры, заданной в форме plane = [o,n], надо всего лишь сделать пару
матричных умножений (поскольку M - матрица переноса, и ее применение на деле
сводится к трем сложениям, матричных умножений будет ровно два):
new_o = T * M * std_o
new_n = T * std_n
Что лучше и быстрее, как обычно, не ясно. При отсечении до преобразований
тест на попадание точки в область зрения стоит от 3 до 15 умножений
(относительно дешевые операции типа сложений не считаем), плюс 11 умножений
и 2 деления на поворот и проецирование после отсечения, зато поворачиваются
и проецируются только видимые точки. При отсечении после преобразований
тест стоит 8 умножений (так как в координатах нормалей шесть нулей и одна
единица), зато для всех точек придется сделать 9 умножений для поворота;
проецироваться же по-прежнему будут только видимые точки. Так что наиболее
подходящий метод выбирайте сами.
В завершение осталось только привести процедуру для отсечения полигона
произвольной плоскостью:
// вычитание векторов
float vecsub(vertex *result, vertex a, vertex b) {
result->x = a.x - b.x;
result->y = a.y - b.y;
result->z = a.z - b.z;
}
// скалярное умножение векторов
float vecmul(vertex a, vertex b) {
return a.x * b.x + a.y * b.y + a.z * c.z;
}
// dst - массив для сохранения вершин результата
// src - массив вершин исходного полигона
// num - число вершин исходного полигона
// n - нормаль к плоскости
// o - точка, лежащая в плоскости
// функция возвращает число вершин результата
int clipPlane(vertex *dst, vertex *src, int num, vertex n, vertex o) {
int i, r;
vertex p1, p2, tmp;
float t1, t2;
float k;
r = 0;
for (i = 0; i < num; i++) {
p1 = src[i];
p2 = src[(i + 1) % num];
vecsub(&tmp, p1, o); t1 = vecmul(tmp, n);
vecsub(&tmp, p2, o); t2 = vecmul(tmp, n);
if (t1 >= 0) { // если начало лежит в области
dst[r++] = p1; // добавляем начало
}
if (((t1 > 0) && (t2 < 0)) || // если ребро пересекает границу
((t2 >= 0) && (t1 < 0))) // добавляем точку пересечения
{
k = 1 - vecmul(p1, n) / vecmul(p2, n);
dst[r].x = p1.x + k * (p2.x - p1.x);
dst[r].y = p1.y + k * (p2.y - p1.y);
dst[r].z = p1.z + k * (p2.z - p1.z);
dst[r].u = p1.u + k * (p2.u - p1.u);
dst[r].v = p1.v + k * (p2.v - p1.v);
r++;
}
}
return r;
}
4. Текстурирование
==================
4.1. Точное
-----------
Задача текстурирования формулируется таким образом: есть грань - согласно
предположениям, треугольная - с наложенной на нее текстурой. То есть каждая
точка грани окрашена цветом соответствующей ей точки в текстуре. Текстура
накладывается линейным образом. Есть точка экрана с координатами на экране
(sx,sy), принадлежащая проекции грани. Требуется найти ее цвет, то есть
цвет соответствующей этой точке экрана точки текстуры. А для этого надо
найти координаты текстуры для этой точки - точнее, для той точки, проекцией
которой на экран является наша (sx,sy).
Пусть вершины грани есть точки A(Ax,Ay,Az), B(Bx,By,Bz) и C(Cx,Cy,Cz), а
соответствующие им точки текстуры - (Au,Av), (Bu,Bv) и (Cu,Cv). Найдем
координаты текстуры для точки, проекцией которой является (sx,sy).
Для точек (x,y,z), проекцией которых является (sx,sy) имеем:
sx = xSize/2+x*dist/(z+dist),
sy = ySize/2-y*dist/(z+dist).
Для упрощения формул будем использовать обозначения
i = sx-XSize/2,
j = YSize/2-sy,
Z = z+dist.
Тогда эти формулы примут вид
i = x*dist/Z,
j = y*dist/Z,
или, что равносильно:
i*Z = x*dist,
j*Z = y*dist.
Рассмотрим точку D, принадлежащую грани. Для нее D = A+a*(B-A)+b*(C-A), так
как она лежит в грани. D однозначно задается парой (a,b). Для нее координаты
текстуры (из того, что текстура накладывается линейно) будут такие:
Du = Au+a*(Bu-Au)+b*(Cu-Au),
Dv = Av+a*(Bv-Av)+b*(Cv-Av).
Пусть проекция D на экран как раз и имеет координаты (sx,sy), тогда для нее
выполнены написанные выше соотношения:
i*DZ = Dx*dist,
j*DZ = Dy*dist.
Подставим сюда координаты D, выраженные через координаты A, B и неизвестные
коэффициенты a, b:
i*(Az+a*(Bz-Az)+b*(Cz-Az)+dist) = dist*(Ax+a*(Bx-Ax)+b*(Cx-Ax)),
j*(Az+a*(Bz-Az)+b*(Cz-Az)+dist) = dist*(Ay+a*(By-Ay)+b*(Cy-Ay)),
т.к. мы договорились, что AZ = Az+dist, и, кстати, поэтому BZ-AZ = Bz-Az,
это можно чуть укоротить:
i*(AZ+a*(BZ-AZ)+b*(CZ-AZ)) = dist*(Ax+a*(Bx-Ax)+b*(Cx-Ax)),
j*(AZ+a*(BZ-AZ)+b*(CZ-AZ)) = dist*(Ay+a*(By-Ay)+b*(Cy-Ay)).
Выделим a и b:
a*(i*(BZ-AZ)-dist*(Bx-Ax))+b*(i*(CZ-AZ)-dist*(Cx-Ax)) = dist*Ax-i*AZ,
a*(j*(BZ-AZ)-dist*(By-Ay))+b*(j*(CZ-AZ)-dist*(Cy-Ay)) = dist*Ay-j*AZ.
Получили систему двух линейных уравнений, из которой можно найти a и b, а
по ним немедленно вычисляются u и v. Введем вектор M = BA (Mx = Bx-Ax и т.д.)
и вектор N = CA, обозначим d = dist (все это для краткости записи). Тогда
эти два уравнения перепишутся в виде:
a*(i*Mz-d*Mx)+b*(i*Nz-d*Nx) = d*Ax-i*AZ,
a*(j*Mz-d*My)+b*(j*Nz-d*Ny) = d*Ay-j*AZ,
и решая систему (например, по формулам Крамера) получаем:
(dAx-iAZ)(jNz-dNy)-(dAy-jAZ)(iNz-dNx)
a = ------------------------------------- =
(iMz-dMx)(jNz-dNy)-(iNz-dNx)(jMz-dMy)
djAxNz-ddAxNy-ijAZNz+idAZNy-diAyNz+ddAyNx+ijNzAZ-djAZNx
= ------------------------------------------------------- =
ijMzNz-idMzNy-djMxNz+ddMxNy-ijMzNz+idNzMy+djNxMz-ddNxMy
dj(AxNz-AZNx)+dd(AyNx-AxNy)+id(AZNy-AyNz)
= ----------------------------------------- =
id(MyNz-MzNy)+dj(NxMz-MxNz)+dd(MxNy-NxMy)
i(AZNy-AyNz)+j(AxNz-AZNx)+d(AyNx-AxNy)
= --------------------------------------
i(MyNz-MzNy)+j(NxMz-MxNz)+d(MxNy-NxMy)
аналогично получаем
i(AZMy-AyMz)+j(AxMz-AZMx)+d(AyMx-AxMy)
b = --------------------------------------
i(MyNz-MzNy)+j(NxMz-MxNz)+d(MxNy-NxMy)
Знаки умножения здесь везде опущены, иначе читать это все совсем невозможно.
Осталось немного, подставить Mx = Bx-Ax и так далее, а потом подставить эти
a и b в формулы для Du и Dv. В процессе подстановок что-то сократится,
что-то упростится, но формулы для Du и Dv все равно получатся длиной в
несколько строк.
Но из этих формул видно кое-что интересное. А именно, то, что
u = (C1*sx+C2*sy+C3) / (C4*sx+C5*sy+C6),
v = (C7*sx+C8*sy+C9) / (C4*sx+C5*sy+C6),
причем C1, ..., C9 - просто какие-то коэффициенты, зависящие от грани. То
есть, можно посчитать эти коэффициенты один раз на грань, а потом считать
u, v по написанным пару строк выше формулам. Но все равно получается как
минимум одно деление на точку. Это слишком медленно. Поэтому все методы
текстурирования на самом деле используют приближенные вычисления, хотя и
именно по этим формулам.
Стоит отметить тот факт, что на самом деле здесь грань не обязательно
должна быть треугольной - можно взять любые три вершины многоугольной грани.
То же самое справедливо и для остальных описанных методов текстурирования.
4.2. Аффинное
-------------
Этот метод текстурирования основан на приближении u, v линейными функциями.
Итак, пусть u - линейная функция, u = k1*sx+k2*sy+k3. Можно посчитать k1,
k2, k3 исходя из того, что хотя бы в вершинах грани u должно совпадать с
точным значением - это даст нам три уравнения, из которых быстро и просто
находятся эти коэффициенты, и потом считать u по этой формуле. Но это все
равно медленно - два умножения на пиксел.
Будем рисовать грань по строкам - это общепринято, довольно просто, и не
доводит до умопомешательства кэш-память процессора. Вершины грани заранее
отсортируем по sy (например, A.sy <= B.sy <= C.sy). Для каждой строки можно
посчитать начальное значение x, u (так же, как и для x, ведь u по любой прямой
меняется тоже линейно), а также длину этой строки.
A
/ \
/ \
*--------*
/ B
/ /
/ /
/ /
/ /
/ /
//
C
В нарисованном случае, например,
x_start = A.sx+(current_sy-A.sy)*(C.sx-A.sx)/(C.sy-A.sy),
u_start = A.u+(current_sy-A.sy)*(C.u-A.u)/(C.sy-A.sy),
x_end = A.sx+(current_sy-B.sy)*(B.sx-A.sx)/(B.sy-A.sy),
length = x_end - x_start.
Какие вершины использовать в этих формулах - это уже проблемы рисования
треугольника, а не текстурирования. Лично я просто храню x_start, x_end,
u_start, на каждом переходе вниз на строчку прибавляю к
delta_x_start = (C.sx-A.sx)/(C.sy-A.sy),
и аналогично высчитываемые приращения для x_end, u_start. Вот только надо
аккуратно следить за тем, какая сторона правая, какая - левая, и на каком мы
сейчас промежутке находимся - то ли AB, то ли BC, и соответственно изменять
приращения. Впрочем, все это - уже обыкновенное рисование треугольника. В
примерах просто сделано решение "в лоб" - проверяем, какой участок - AB или
BC - пересекает текущая строка, считаем x/u/v на обоих концах, считаем длину
строки и берем соответствующие левому концу (то есть меньшему x) значения u
и v.
Так вот. Посчитали начало строки, длину строки, u в начале строки. Осталось
заметить, что раз уж u = k1*sx+k2*sy+k3, то при переходе к следующему пикселу
строки у нас u изменяется на k1 (так же известный как du/dsx). Это число и
надо как-то посчитать. Например, так:
A
/ \
/ \ x_start = A.sx+(B.sy-A.sy)*(C.sx-A.sx)/(C.sy-A.sy),
/ \ x_end = B.sx,
*-----------B u_start = A.u+(B.sy-A.sy)*(C.u-A.u)/(C.sy-A.sy),
/ / u_end = B.u,
/ / du_dsx = (u_start-u_end)/(x_start-x_end).
/ /
/ /
/ /
//
C
du/dsx - просто число, оно не меняется на всем треугольнике, поэтому просто
считаем его там, где удобно, и берем посчитанное значение.
v (из тех же соображений) считается абсолютно точно так же, надо только во
всех приведенных формулах u заменить на v, и все.
Теперь осталось только взять и нарисовать эту строку:
// ...
u = u_start;
v = v_start;
for (current_sx = x_start; current_sx <= x_end; current_sx++) {
putpixel(current_sx, current_sy, texture[(int)v][(int)u]);
u += du_dsx;
v += dv_dsx;
}
// ...
Пройдясь по всем строкам грани - т.е. пробежавшись current_sy по значениям
от A.sy до C.sy (вершины отсортированы!), получим текстурированную грань.
Voila!
4.3. Перспективно-корректное
----------------------------
Этот метод основан на приближении u, v кусочно-линейными функциями. Кратко
говоря, при рисовании каждая строка разбивается на куски (обычно несколько
кусков длиной 8/16/32 пикселов и один оставшийся произвольной длины), в
начале и конце каждого куска считаются точные значения u, v, а на куске
они интерполируется линейно.
Точные значения u и v, в принципе, можно считать по формулам из 4.1, но
обычно используют более простой путь. Он основан на том факте, что значения
1/Z, u/Z и v/Z зависят от sx, sy ЛИНЕЙНО. Доказательство этого факта пока
опущено. Таким образом, достаточно для каждой вершины посчитать 1/Z, u/Z,
v/Z и линейно их интерполировать - точно так же, как интерполируются u и v
в 4.2. Причем, так как эти значения зависят от sx, sy строго линейно, то
интерполяция дает не сильно приближенные результаты, а абсолютно точные!
Сами же точные значения u, v считаются как
u = (u/Z) / (1/Z),
v = (v/Z) / (1/Z).
Дальше все становится совсем просто. При рисовании треугольника, на ребрах
интерполируем не u и v, как в 4.2, а 1/Z, u/Z, v/Z. Кроме того, заранее
считаем d(u/Z)/dsx, d(v/Z)/dsx, d(1/Z)/dsx (то есть, изменений этих самых
u/Z, v/Z, 1/Z соотвествующих шагу по dsx на 1) так, как считали du/dsx - это
будет нужно для быстрого вычисления точных значений u, v. Каждую линию рисуем
кусками по 8/16/32 пикселов (на самом деле, кусками любой длины; просто если
длина - степень двойки, то при вычислении du/dx и dv/dx для текущего куска
можно деление на длину куска заменить сдвигом вправо) и, если надо, рисуем
оставшийся хвостик. Для расчета точных значений u, v в конце каждого куска
пользуемся посчитанными (ага!) значениями d(u/Z)/dsx, d(v/Z)/dsx, d(1/Z)/dsx;
раз значения u/Z, v/Z, 1/Z в начале куска известны, меняются они линейно и
длина куска известна (либо 16 пикселов, либо длина остатка), то в конце
куска они считаются все это до боли просто:
uZ_b = uZ_a + length * duZ_dsx; // расчет u/Z, v/Z, 1/Z в конце куска
vZ_b = vZ_a + length * dvZ_dsx;
Z1_b = Z1_a + length * dZ1_dsx;
Все вместе выглядеть это будет примерно так:
// ...
current_sx = x_start;
Секция 2 из 6 - Предыдущая - Следующая
© faqs.org.ru
