Фантазии о Вселенной и мой личный сайт
Алгоритм точного текстурирования

Алгоритм точного текстурирования


Точка на параллепипеде

Это любимая тема, текстурирование. И сейчас про нее и будет идти разговор. Но для начала, надо вспомнить некоторые азы аналитической геометрии. Ибо без этого никак просто и никуда, однако, она не такая и сложная, если подумать.

Точка в 2-х мерном пространстве
Рисунок 1. Точка в 2-х мерном пространстве

Вот возьмем очень простой пример, чтобы положить точку в 2-х мерном пространстве, нам потребуется отсчитать некоторую длину \( u \) по оси \( OA \), зафиксировать там точку, и отсчитать некоторую длину \( v \) по оси \( OB \). Точка будет как раз там. С математической точки зрения это будет выглядеть так:

$$ x = O_x + u(A_x - O_x) \\ y = O_y + v(B_y - O_y) $$

То есть, если мы возьмем, например \(u = 1\), \(v = 1\), то получится вот что:

$$ x = O_x + 1(A_x - O_x) = O_x + A_x - O_x = A_x \\ y = O_y + 1(B_y - O_y) = O_y + B_y - O_y = B_y $$

А теперь рассмотрим другой случай. С параллелепипедом.

Точка на параллелепипеде
Рисунок 2. Точка на параллелепипеде

На этом рисунке видно, что сначала мы откладываем на прямой \(OA\) некоторый отрезок длиной \(u\), и на прямой \(OB\) отрезок длиной \(v\), после чего делаем их пересечение, но на самом деле, это сложение. Вот так получаем точку \(C\) на отрезке \(OC\)

$$ C_x = O_x + u(A_x - O_x) \\ C_y = O_y + u(A_y - O_y) \\ C_z = O_z + u(A_z - O_z) $$

И также делается для отрезка \(OD\) для получения точки \(D\):

$$ D_x = O_x + v(B_x - O_x) \\ D_y = O_y + v(B_y - O_y) \\ D_z = O_z + v(B_z - O_z) $$

Как видно, я сразу сделал все в трехмерных координатах, чтобы проиллюстрировать, что не имеет значения размерность. Но, чтобы получить точку \(E\), или, точнее сказать, вектор \(OE\), необходимо сначала проложить вектор \(OD\), и к нему добавить вектор \(OC\) (или наоборот, не имеет значения). Соответственно, базисом будет точка \(O\).

$$ E_x = O_x + u(A_x - O_x) + v(B_x - O_x) \\ E_y = O_y + u(A_y - O_y) + v(B_y - O_y) \\ E_z = O_z + u(A_z - O_z) + v(B_z - O_z) $$

В векторной форме будет вот так (приблизительно говоря)

$$ E = O + u\overrightarrow{OA} + v\overrightarrow{OB} $$

Итог. Таким образом, мы параметрически задали плоскость в пространстве. То есть, чтобы описать любую плоскость в пространстве, для этого нам потребуется пара \((u,v)\), и 3 точки, а точнее даже говоря, 2 вектора.

Пересечение прямой и плоскости

Пришло время рассказать о том, как найти пересечение прямой и плоскости. Это важно, поскольку мы должны найти параметры \((u,v)\), которые и будут координатами текстуры. Условимся в том, что \(0 \le u \le 1\) и \(0 \le v \le 1\). То есть позиция текстуры не будет выпадать за пределы от 0 до 1. Что и правильно на первых порах. Так-то она часто как раз превышает эти пределы, чтобы текстуру "размножить" на один треугольник можно было.

Каким образом найти пересечение прямой и плоскости, которые заданы параметрически? Оба заданы? Нужно их приравнять друг к другу. То есть, чтобы сделать, чтобы точка лежала на плоскости, надо, что точка эта была равна уравнению этой плоскости. Допустим, у нас есть параметрически заданная прямая \(ML\). Мы приравняем каждый ее компонент к уравнению плоскости, заданную векторами \(\overrightarrow{AB}\) и \(\overrightarrow{AC}\).

$$ C_x = M_x + t(L_x - M_x) = A_x + u(B_x - A_x) + v(C_x - A_x) \\ C_y = M_y + t(L_y - M_y) = A_y + u(B_y - A_y) + v(C_y - A_y) \\ C_z = M_z + t(L_z - M_z) = A_z + u(B_z - A_z) + v(C_z - A_z) $$

Теперь задача в том, чтобы найти \((u,v)\). Точкой пересечения будет точка \(C\). Она пока не нужна, нам нужны только 2 параметра, которые будут пересекаться (если еще будут), могут и не пересечься, если линия лежит параллельно плоскости, в таком случае хоть какие взять параметры, они не сойдутся.

Для начала, я все-таки кое-что сокращу. А то писать уж очень много. Сделаю так:

$$ L_i - M_i = \Delta{L_i}, \\ B_i - A_i = \Delta{B_i}, \\ C_i - A_i = \Delta{C_i}, \\ A_i - M_i = \Delta{M_i}, \\ i = x,y,z $$

Теперь я то большое уравнение запишу в другой форме, сокращенно и перенесу сразу, чтобы было на своих местах.

$$ t\Delta{L_x} - u\Delta{B_x} - v\Delta{C_x} = \Delta{M_x} \\ t\Delta{L_y} - u\Delta{B_y} - v\Delta{C_y} = \Delta{M_y} \\ t\Delta{L_z} - u\Delta{B_z} - v\Delta{C_z} = \Delta{M_z} $$

Если присмотреться, то можно заметить, что это система линейных алгебраических уравнений (СЛАУ) с тремя неизвестными. То есть, его можно решить методом Крамера запросто. Либо методом Гаусса, кому как удобнее. Я решаю их методом Крамера всегда. Решать я его не буду сейчас, это легко сделать самому. И не суть еще. Это лишь иллюстрация к дальнейшим формулам.

Жесткая линейная алгебра

Сейчас пойдут формулы. И много. Очень много формул. Поэтому, можно не читать этот раздел. Можно сразу взять какой-нибудь готовый результат, например, нарисовать что-то на OpenGL, не заморачиваясь с формулами.

Сейчас я последовательно выведу формулу, по которой можно подсчитывать \(u, v\), зная лишь точку проекции \(x', y'\), ну и координаты расположенной в пространстве плоскости (треугольника).

Рассмотрим уравнение проекции.

$$ x' = w + \frac{x}{z}*fov \\ y' = h - \frac{y}{z}*fov $$

Мы знаем здесь \(x', y'\), потому что задаем точку на экране и хотим вычислить параметры \(u, v\). Перезапишем иначе, я перенесу w, h в левую часть уравнения (и знак поменяю, где \(y'\)):

$$ x = x' - w = \frac{x}{z}*fov \\ y = h - y' = \frac{y}{z}*fov $$

Условимся, что:

$$ x = x' - w \\ y = h - y' \\ fov2 = fov{2} $$

Чтобы потом легче было считать. Теперь я сокращу также и другое:

ABx = B.x – A.x, ACx = C.x – A.x
ABy = B.y – A.y, ACy = C.y – A.y
ABz = B.z – A.z, ACz = C.y – A.z

И это тоже ради того, чтобы сократить и так гору вычислений в будущем. Вспомним параметрически заданное уравнение плоскости:

x = Ax + u*ABx + v*ACx
y = Ay + u*ABy + v*ACy
z = Az + u*ABz + v*ACz

Теперь эти \(x, y, z\) я поставлю в уравнение проекции для x:

$$ x = fov\frac{A_x + u\cdot ABx + v\cdot ACx}{A_z + u\cdot ABz + v\cdot ACz} $$

И для y:

$$ y = fov\frac{A_y + u\cdot ABy + v\cdot ACy}{A_z + u\cdot ABz + v\cdot ACz} $$

Здесь \(x, y\) – это именно координаты проекции, т.е. координаты точки на экране. Домножу левую и правую половину на одно и то же выражение, чтобы получить следующее

x(Az + u*ABz + v*ACz) = fov(Ax + u*ABx + v*ACx)
y(Az + u*ABz + v*ACz) = fov(Ay + u*ABy + v*ACy)

Раскрываем скобки

x*Az + u*x*ABz + v*x*ACz = fov*Ax + u*fov*ABx + v*fov*ACx
y*Az + u*y*ABz + v*y*ACz = fov*Ay + u*fov*ABy + v*fov*ACy

Приведем подобные

u*x*ABz – u*fov*ABx + v*x*ACz – v*fov*ACx = fov*Ax – x*Az
u*y*ABz – u*fov*ABy + v*y*ACz – v*fov*ACy = fov*Ay – y*Az

Сгруппируем:

u(x*ABz – fov*ABx) + v(x*ACz – fov*ACx) = (fov*Ax – x*Az)
u(y*ABz – fov*ABy) + v(y*ACz – fov*ACy) = (fov*Ay – y*Az)

Как теперь видим, можно найти суть. Мы видим СЛАУ, который решается методом Крамера. То есть тут всего лишь 2 неизвестных, остальное все вычислимо. Теперь надо вспомнить метод Крамера и перемножить коэффициенты между собой особым (крест-накрест), образом

D = (x*ABz – fov*ABx)*(y*ACz – fov*ACy) –
    (x*ACz – fov*ACx)*(y*ABz – fov*ABy)

Это и будет детерминант. Он потребуется, чтобы вычислить u, v. Выносим все за скобки и начинаем пересчитывать между собой, сокращая все, что нужно:

+x*y*ABz*ACz – x*fov*ABz*ACy – y*fov*ABx*ACz + fov2*ABx*ACy
-x*y*ABz*ACz + x*fov*ACz*ABy + y*fov*ACx*ABz – fov2*ABy*ACx

И D будет равно:

x*fov* (ABy*ACz – ABz*ACy) +
y*fov* (ABz*ACx – ABx*ACz) +
  fov2*(ABx*ACy – ABy*ACx)

Все! Детерминант подсчитан. Начинаем считать u. Подставим необходимые коэффициенты по методу крамера. Нужно поставить \(b_1, b_2\) на место \(a_{11}, a_{21}\), чтобы найти u:

u(fov*Ax – x*Az) + v(x*ACz – fov*ACx)
u(fov*Ay – y*Az) + v(y*ACz – fov*ACy)

Перемножим крест-накрест \(a_{11}a_{22} - a_{12}a_{21}\):

(fov*Ax – x*Az)*(y*ACz – fov*ACy) –
(x*ACz – fov*ACx)*(fov*Ay – y*Az) =

 fov*y*Ax*ACz – x*y*ACz*Az – fov2*Ax*ACy + fov*x*Az*ACy
-fov*x*Ay*ACz + x*y*ACz*Az + fov2*Ay*ACx – fov*y*Az*ACx

В итоге выходит:

u' =
x*fov* (Az*ACy – Ay*ACz) +
y*fov* (Ax*ACz – Az*ACx) +
  fov2*(Ay*ACx – Ax*ACy)

Аналогичным образом, делается и для v:

u(x*ABz – fov*ABx) + v(fov*Ax – x*Az)
u(y*ABz – fov*ABy) + v(fov*Ay – y*Az)

Перемножение крест-накрест:

(x*ABz – fov*ABx)*(fov*Ay – y*Az) –
(fov*Ax – x*Az)*(y*ABz – fov*ABy) =

(x*ABz*fov*Ay - x*ABz*y*Az - fov*ABx*fov*Ay + fov*ABx*y*Az) -
(fov*Ax*y*ABz - fov*Ax*fov*ABy - x*Az*y*ABz + x*Az*fov*ABy) =

 x*fov*Ay*ABz - x*y*ABz*Az - fov2*Ay*ABx + fov*y*Az*ABx
-y*fov*Ax*ABz + x*y*ABz*Az + fov2*Ax*ABy - fov*x*Az*ABy

Приведя подобные, получаем:

v' =
x*fov* (Ay*ABz - Az*ABy) +
y*fov* (Az*ABx - Ax*ABz) +
  fov2*(Ax*ABy - Ay*ABx)

Все, теперь, чтобы получить \(u\) и \(v\), надо поделить их на дискриминант:

$$ u = \frac{u'}{D}, v = \frac{v'}{D} $$

Программа на С

В заключение разговора, я приведу программу на С, чтобы потом много не искать, а сразу брать готовые результаты отсюда.

// Сначала, получаем разности
float   ABx = b.x - a.x, ACx = c.x - a.x,
        ABy = b.y - a.y, ACy = c.y - a.y,
        ABz = b.z - a.z, ACz = c.z - a.z;

// Рассчитываем коэффициенты
float   A1 =  fov*(a.z*ACy - a.y*ACz),
        A2 =  fov*(a.x*ACz - a.z*ACx),
        A3 = fov2*(a.y*ACx - a.x*ACy),
        // ---
        B1 =  fov*(a.y*ABz - a.z*ABy),
        B2 =  fov*(a.z*ABx - a.x*ABz),
        B3 = fov2*(a.x*ABy - a.y*ABx),
        // ---
        C1 =  fov*(ABy*ACz - ABz*ACy),
        C2 =  fov*(ABz*ACx - ABx*ACz),
        C3 = fov2*(ABx*ACy - ABy*ACx);

float   D = x*C1 + y*C2 + C3;
float   u = x*A1 + y*A2 + A3;
float   v = x*A1 + y*A2 + A3;

if (D != 0) {
    u /= D;
    v /= D;
} else {
    u = v = 0;
}