Это, пожалуй, самый простой, довольно быстрый и наиболее часто используемый метод отсечения. Идея, как обычно, проста. При растеризации треугольника мы в конечном итоге рисуем набор горизонтальных отрезков. Так и будем обрезать по границам экрана именно отрезки. Пусть мы рисуем отрезок от 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). А несколько сравнений и присваивание на одну линию делаются достаточно быстро. Получаем отсечение, практически незамедляющее скорость работы.
33. Алгоритм Сазерленда-Ходжмана, 3d отсечение
Этот алгоритм (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.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;
}
34. Точное текстурирование
Задача текстурирования формулируется таким образом: есть грань – согласно предположениям, треугольная - с наложенной на нее текстурой. То есть каждая точка грани окрашена цветом соответствующей ей точки в текстуре. Текстура накладывается линейным образом. Есть точка экрана с координатами на экране (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 по написанным пару строк выше формулам. Но все равно получается как минимум одно деление на точку. Это слишком медленно. Поэтому все методы текстурирования на самом деле используют приближенные вычисления, хотя и именно по этим формулам.
Стоит отметить тот факт, что на самом деле здесь грань не обязательно должна быть треугольной - можно взять любые три вершины многоугольной грани. То же самое справедливо и для остальных описанных методов текстурирования.
35. Аффинное текстурирование
Этот метод текстурирования основан на приближении 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!
36. Перспективно-корректное текстурирование, Мипмэппинг
Этот метод основан на приближении 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;
length = x_end - x_start;
// расчет u/Z, v/Z, 1/Z, u, v в начале самого первого куска
uZ_a = uZ_start;
vZ_a = vZ_start;
Z1_a = Z1_start; // это 1/Z
u_a = uZ_a / Z1_a;
v_a = vZ_a / Z1_a;
// рисуем куски по 16 пикселов
while (length >= 16) {
uZ_b = uZ_a + 16 * duZ_dsx; // расчет u/Z, v/Z, 1/Z, u, v в конце куска
vZ_b = vZ_a + 16 * dvZ_dsx;
Z1_b = Z1_a + 16 * dZ1_dsx;
u_b = uZ_b / Z1_b;
v_b = vZ_b / Z1_b;
u = u_a; // начинаем текстурирование с начала куска
v = v_a;
du = (u_b - u_a) / 16; // можно сделать >> 4, используя fixedpoint
dv = (v_b - v_a) / 16; // можно сделать >> 4, используя fixedpoint
// рисуем 16 пикселов старым добрым "аффинным" методом
len = 16;
while (len--) {
putpixel(current_sx, current_sy, texture[(int)v][(int)u]);
u += du;
v += dv;
current_sx++;
}
length -= 16;
// конец куска становится началом следующего куска
uZ_a = uZ_b;
vZ_a = vZ_b;
Z1_a = Z1_b;
u_a = u_b;
v_a = v_b;
}
// дорисовываем "хвост" линии, если он непуст
if (length!= 0) {
uZ_b = uZ_a + length * duZ_dsx;
vZ_b = vZ_a + length * dvZ_dsx;
Z1_b = Z1_a + length * dZ1_dsx;
u_b = uZ_b / Z1_b;
v_b = vZ_b / Z1_b;
u = u_a; // начинаем текстурирование с начала куска
v = v_a;
du = (u_b - u_a) / length;
dv = (v_b - v_a) / length;
// рисуем остаток пикселов старым добрым "аффинным" методом
while (length--) {
putpixel(current_sx, current_sy, texture[v][u]);
u += du;
v += dv;
current_sx++;
}
}
//...
Как и в 4.2, пройдемся подобным куском кода по всем строкам грани, не забыв вместо "//..." вставить интерполяцию всяких там [u/v/1]Z_start, содранную с интерполяции u_start.. и - о чудо, текстурированная с учетом перспективы грань!
Осталось сказать еще пару слов о кое-какой оптимизации.
Во-первых, два деления при расчете u и v в цикле прорисовки можно (и нужно) заменить на одно - посчитать tmp = 1/Z, дальше u = uZ * tmp, v = vZ * tmp.
Во-вторых, немного поменяв местами блоки расчета очередной пары точных значений u и v и прорисовки очередного куска линии, можно добиться того, что это самое одно деление, нужное для расчета u и v для *следующего* куска будет находиться сразу перед прорисовкой *текущего* куска. А в этом случае деление может исполняться в сопроцессоре одновременно с отрисовкой куска линии в процессоре. То есть единственная медленная операция будет считаться на полную халяву! Получим перспективно-корректное текстурирование, которое (теоретически) будет работать ненамного медленнее аффинного.
В-третьих, деление на length при дорисовке хвостика длиной от 1 до 15 пикселов можно заменить на умножение на 1/length, заранее посчитав табличку для значений 1/length.
И наконец, мелкие треугольники можно текстурировать аффинным методом, а большие - методом с коррекцией. Размер треугольника можно определять хотя бы по длине самой длинной горизонтальной линии:
x_start = A.sx+(B.sy-A.sy)*(C.sx-A.sx)/(C.sy-A.sy),
x_end = B.sx,
longest_length = x_end - x_start,
все равно мы ее считаем для расчета du_dsx или duZ_dsx и иже с ними.
Мипмэппинг
Если полигон относительно сильно удален или повернут, так, что соседним пикселам на экране соотвествуют сильно разнесенные точки текстуры, то возникают всякие неприятные артефакты - можно считать, что потому, что при текстурировании мы выбираем лишь какую-то одну точку текстуры, а реально в экранный пиксел будет проецироваться несколько текселов (точек текстуры).Вообще идеальным методом было бы следующее: провести до пересечения с гранью 3D-пирамиду с вершиной в камере и основанием-пикселом, выбрать все точки текстуры, попадающие в наш пиксел, и усреднить значения их цветов. Вот только вычислительные затраты на одну точку в этом случае окажутся просто фантастическими.
Поэтому для удаления артефактов используется значительно более простая вещь, а именно мипмэппинг. Идея, как обычно, проста. Для каждой текстуры заранее создается несколько ее копий уменьшенного размера (1/2, 1/4, и так далее), а далее при текстурировании используется либо сама текстура, либо подходящая уменьшенная копия. Памяти при этом расходуется на 25-33% больше, чем без мипмэппинга, но зато, вроде бы, увеличивается качество изображения.
Как создать уменьшенную в два раза копию текстуры? Здесь мы опишем три метода, два из них очевидны, третий позаимствован у Crystal Space. Методы расположены в порядке уменьшения скорости и увеличения качества уменьшенной текстуры.
Метод 1. Выкинуть все пикселы текстуры с нечетными координатами. Самый простой, самый быстрый, но дает не очень хорошо выглядящие результаты.
Метод 2. Оставить точки с четными координатами, в каждой точке усреднить значения цвета в этой точке и ее трех соседях (справа, снизу и справа-снизу).
Метод 3. Оставить точки с четными координатами, использовав в каждой точке фильтр, заданный вот такой матрицей:
[ 1 2 1 ]
1/16 * [ 2 4 2 ]
[ 1 2 1 ]
В виде формул для каждой из компонент цвета точки уменьшенной в два раза копии текстуры эти методы запишутся, соответственно, так:
mip1[x][y] = tex[2*x][2*y]; // метод 1
mip2[x][y] = (// метод 2
tex[2*x ][2*y ] +
tex[2*x+1][2*y ] +
tex[2*x ][2*y+1] +
tex[2*x+1][2*y+1]) / 4;
mip3[x][y] = (// метод 3
1 * tex[2*x-1][2*y-1] +
2 * tex[2*x ][2*y-1] +
1 * tex[2*x+1][2*y-1] +
2 * tex[2*x-1][2*y ] +
4 * tex[2*x ][2*y ] +
2 * tex[2*x+1][2*y ] +
1 * tex[2*x-1][2*y+1] +
2 * tex[2*x ][2*y+1] +
1 * tex[2*x+1][2*y+1]) / 16;
Последовательно применяя любой из описанных методов, мы можем построить набор уменьшенных текстур. Остается выяснить, какую именно из них надо выбрать при текстурировании. Здесь опять будет описано два достаточно простых метода; а вообще, конечно, их можно придумать значительно больше.
Метод 1: полигональный мипмэппинг. В этом случае мы считаем площадь полигона на экране в пикселах и его же площадь в текстуре в текселах (последнюю обычно можно посчитать заранее), определяем по ним примерное количество пикселов, соотвествующих одному пикселу и выбираем нужный уровень уменьшения текстуры по следующей формуле:
miplevel = floor(log2(screenArea / textureArea) / 2);
здесь
screenArea - площадь грани на экране (в пикселах)
textureArea - площадь грани в текстуре (в текселах)
log2() - функция двоичного логарифма (для Watcom C стандартная)
miplevel - уровень уменьшения; выбираемая текстура должна быть сжата
по обеим осям в (2^miplevel) раз
Поскольку бесконечное количество уменьшенных копий текстуры никто хранить не будет, да и увеличенные текстуры тоже обычно не хранят, а miplevel может получится любым действительным числом, надо, конечно, поставить заглушку:
miplevel = floor(log2(screenArea / textureArea) / 2);
if (miplevel < 0) miplevel = 0;
if (miplevel > MAXMIPLEVEL) miplevel = MAXMIPLEVEL;
screenArea и textureArea проще всего, по-моему, посчитать по формуле Герона для площади треугольника:
// a, b, c - стороны треугольника; p - периметр
a = sqrt((v2.sx-v1.sx)*(v2.sx-v1.sx) + (v2.sy-v1.sy)*(v2.sy-v1.sy));
b = sqrt((v3.sx-v1.sx)*(v3.sx-v1.sx) + (v3.sy-v1.sy)*(v3.sy-v1.sy));
c = sqrt((v3.sx-v2.sx)*(v3.sx-v2.sx) + (v3.sy-v2.sy)*(v3.sy-v2.sy));
p = (a + b + c);
screenArea = sqrt(p * (p-a) * (p-b) * (p-c));
a = sqrt((v2.u-v1.u)*(v2.u-v1.u) + (v2.v-v1.v)*(v2.v-v1.v));
b = sqrt((v3.u-v1.u)*(v3.u-v1.u) + (v3.v-v1.v)*(v3.v-v1.v));
c = sqrt((v3.u-v2.u)*(v3.u-v2.u) + (v3.v-v2.v)*(v3.v-v2.v));
p = (a + b + c);
textureArea = sqrt(p * (p-a) * (p-b) * (p-c));
Этот метод практически не требует вычислительных затрат, так как все операции проделываются один раз на грань. С другой стороны, здесь использутся один и тот же уровень уменьшения (он же уровень детализации, LOD, level of detail) для всего полигона, а разным пикселам может соответствовать разное количество текселов. Есть и более неприятное следствие - уровни уменьшения для двух соседних полигонов меняются скачком, а это не очень хорошо выглядит.
Метод 2: попиксельный мипмэппинг. В этом случае нужный уровень уменьшения считается для каждого пиксела и выбирается на основе максимального шага в текстуре из соответствующих переходу к соседнему пикселу:
textureStep = max(
sqrt(dudx * dudx + dvdx * dvdx),
sqrt(dudy * dudy + dvdy * dvdy));
miplevel = floor(log2(textureStep));
Подобную операцию для каждого пиксела проводить, конечно, накладно. Но при аффинном текстурировании dudx, dvdx, dudy и dvdy постоянны для всех пикселов, так что попиксельный мэппинг становится полигонным, только с другой методикой расчета уровня уменьшения. Для перспективно-корректного же текстурирования dudx, dvdx, dudy и dvdy постоянны для всех пикселов одного кусочка (span'а), так что уровень уменьшения считается раз в несколько пикселов.
Впрочем, даже раз в несколько пикселов подобное (два корня и один логарифм) считать будет достаточно медленно. Поэтому займемся небольшой оптимизацией: во-первых, для скорости можно сделать упрощение и считать, что
textureStep = sqrt(dudx * dudx + dvdx * dvdx);
Далее, заметим, что log2(sqrt(x)) = log2(x) / 2, откуда
miplevel = floor(log2(dudx * dudx + dvdx * dvdx) / 2);
Осталась, практически, одна трудоемкая операция - взятие логарифма. Но и ее можно убрать. Дело в том, что числа с плавающей запятой (float'ы) как раз и хранятся в логарифмической форме, и floor(log2(x)) можно посчитать вот так:
float x;
int floor_log2_x;
x = 123456;
floor_log2_x = ((*((int*)&x)) - (127 << 23)) >> 23; // чистый C
floor_log2_x = (((int&)x) - (127 << 23)) >> 23; // C++
Соответственно, floor(log2(sqrt(x))) = floor(log2(x) / 2) считаем как
miplevel = ((*((int*)&x)) - (127 << 23)) >> 24; // чистый C
miplevel = (((int&)x) - (127 << 23)) >> 24; // C++
Естественно, что этот трюк можно применить и в случае полигонного мипмэпинга для полного устранения всяческих медленых операций типа sqrt(), log2(). Вот, в общем-то, и все.
37. Параболическое текстурирование, Билинейная фильтрация текстур
Этот метод основан на приближении u, v квадратичными функциями - параболами, то есть. Для каждой строки строится приближающие u, v квадратичные функции, дальше с их помощью они интерполируются по строке. Для этого нам понадобятся точные значения u, v в трех точках - начале, середине и конце строки. Их считаем точно так же, как в 4.3.
Итак, пусть у нас есть точные значения u в начале, середине и конце строки, то есть на расстоянии 0, length/2 и length пикселов от начала этой строки, обозначим их как ua, ub, и uc соответственно. Мы пытаемся приблизить u квадратичной функцией, то есть полагаем, что
u = A*x*x + B*x + C,
где x - расстояние от текущей точки до начала строки. Тогда, подставив в формулу ua, ub, uc и соответствующие им x, получаем:
ua = C,
ub = A*(length*length)/4 + B*length/2 + C,
uc = A*(length*length) + B*length + C.
Т.о. C = ua, а для A и B имеем систему уравнений:
A*(length*length)/4 + B*length/2 = ub - ua,
A*(length*length) + B*length = uc - ua.
Умножим первое уравнение на четыре, вычтем из него второе:
4*A*(length*length)/4 + 4*B*length/2 -
A*(length*length - B*length = 4*(ub - ua) - (uc - ua),
B*length = 4*(ub - ua) - (uc - ua),
B = (4*(ub - ua) - (uc - ua)) / length.
Умножим первое уравнение на два, вычтем его из второго:
A*(length*length) + B*length -
2*A*(length*length)/4 - 2*B*length/2 = (uc - ua) - 2*(ub - ua),
A*(length*length)/2 = (uc - ua) - 2*(ub - ua),
A = (2*(uc - ua) - 4*(ub - ua)) / (length*length).
Получили формулы для A, B, C. Найдем теперь du и ddu. Для текущей точки x имеем:
du(x) = u(x+1) - u(x),
du = (A*(x+1)*(x+1)+B*(x+1)+C) - (A*x*x+B*x+C) =
= A*(2*x+1) + B,
ddu(x) = du(x+1) - du(x),
ddu = (A*(2*(x+1)+1)+B) - (A*(2*x+1)+B) = 2*A.
Т.о., начальные значения u, du, ddu будут равны
u = C,
du = A + B,
ddu = 2*A.
А по известным начальным значениям u, du, ddu последовательно вычисляем значения u в любой точке:
u(0), du(0), ddu - известны
u(1) = u(0) + du(0), du(1) = du(0) + ddu
u(2) = u(1) + du(1), du(2) = du(1) + ddu
u(3) = u(2) + du(2), du(3) = du(2) + ddu
...
Для v все делается полностью аналогично.
Таким образом, рисование строки будет выглядеть примерно так:
//...
// считаем u, v для начала, середины и конца строки
ua = uz_start / z1_start;
va = vz_start / z1_start;
ub = (uz_start + uz_end) / (z1_start + z1_end);
vb = (vz_start + vz_end) / (z1_start + z1_end);
uc = uz_end / z1_end;
vc = vz_end / z1_end;
// считаем начальное du и ddu
pa = 2 * ((uc - ua) - 2 * (ub - ua)) / (length * length);
pb = (4 * (ub - ua) - (uc - ua)) / length;
pc = ua;
u = pc;
du = pa + pb;
ddu = 2 * pa;
// считаем начальное dv и ddv
pa = 2 * ((vc - va) - 2 * (vb - va)) / (length * length);
pb = (4 * (vb - va) - (vc - va)) / length;
pc = v_a;
v = pc;
dv = pa + pb;
ddv = 2 * pa;
// рисуем кусок
while (length--) {
putpixel(current_sx, current_sy, texture[v][u]);
u += du;
v += dv;
du += ddu;
dv += ddv;
}
//...
По сравнению с перспективно-корректным текстурированием имеем более медленный внутренний цикл, но меньшее для длинных строк количество делений. Расчет ua, va и иже с ними можно сделать с помощью трех делений, деления на length и (length*length) можно заменить умножениями на 1/length и 1/(length*length), беря эти значения из заранее посчитанной таблички. Т.о., на строку приходится три деления независимо от ее длины. Качество более-менее приемлемое; а для коротких строк можно использовать обычную линейную интерполяцию, точно так же, как и в случае с перспективно-корректным текстурированием. Получаем вполне конкурентоспособный метод текстурирования.
Дата добавления: 2015-11-26; просмотров: 60 | Нарушение авторских прав