D-отсечение
В пунктах 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; } Точное Задача текстурирования формулируется таким образом: есть грань – согласно предположениям, треугольная - с наложенной на нее текстурой. То есть каждая точка грани окрашена цветом соответствующей ей точки в текстуре. Текстура накладывается линейным образом. Есть точка экрана с координатами на экране (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 по написанным пару строк выше формулам. Но все равно получается как минимум одно деление на точку. Это слишком медленно. Поэтому все методы текстурирования на самом деле используют приближенные вычисления, хотя и именно по этим формулам.
Стоит отметить тот факт, что на самом деле здесь грань не обязательно должна быть треугольной - можно взять любые три вершины многоугольной грани. То же самое справедливо и для остальных описанных методов текстурирования.
|
