§ Трехмерные координаты

В предыдущей статье я подробно рассказал о том, как найти текстурные координаты на ортогональной проекции в двухмерном пространстве. Сегодня я расскажу о том, как найти их, но уже в трехмерном пространстве. По всей видимости, это работает только для трехмерного измерения, поскольку для каждого пространства необходимы собственные подходы и вычисления, хотя суть всегда остается той же самой.
Для начала, надо рассмотреть следующую иллюстрацию

Здесь показано положение точки камеры в пространстве, а также то, как она смотрит в это пространство. Точка камеры всегда будет в положении (0,0,0) для удобства, но и не только, ибо это не нужно для проекции, все необходимые преобразования, такие как поворот, изменение размера, перенос, будут проходить другим способом. Для алгоритма, находящего точки пересечения на треугольнике, нет необходимости выполнять такие преобразования.
Итак, камера смотрит на некую плоскость, которую еще можно называть проецирующей плоскостью, и расстояние до этой плоскости пусть будет равным dz. В данном случае dz = 1 для удобства, хотя можно взять и другие значения, но сейчас это не имеет смысла. Также можно обратить внимание на то, что есть dx и dy, которые принимают значения от -1 до 1 каждый. Для dx = -1 это значит, что проецирующий луч проходит по левому краю плоскости проекции, для dx = 1 - по правому, точно также как dy = -1 по низу, а dy = 1 по верху. Это тоже не является жестко заданным условием, но вместе с тем, сейчас это все только для удобства.
Это - виртуальный экран, на который будет отображаться треугольник (или другие фигуры, если требуется). Треугольник же задается в пространстве с помощью векторов \vec{AB} , \vec{AC} и точки A , которая будет опорной точкой для этих векторов. На самом же деле, это задается не треугольник, а плоскость, но поскольку треугольник лежит на плоскости, то можно сказать, что и треугольник.
Задача в том, чтобы найти точку пересечения луча, идущего от камеры сквозь проецирующую плоскость (или виртуальный/реальный экран) с плоскостью (и треугольником, на ней лежащим). Для этого надо также параметрически задать уравнение луча. Ясное дело, что вектор луча \vec{OP} = (dx, dy, dz) , где точка P это точка на поверхности проецирующей плоскости.

§ Решение задачи пересечения луча и плоскости

Имеем два параметрически заданных уравнения для плоскости и луча:
M = \vec{OA} + u\vec{AB} + v\vec{AC}
M = t\vec{OP}
Я опустил во втором уравнении стартовую точку, поскольку там она равна 0, как и условились ранее. Поскольку по условию задачи точка M это точка пересечения луча и плоскости, то это значит, что два уравнения нужно приравнять, чтобы получить его решение:
\vec{OA} + u\vec{AB} + v\vec{AC} = t\vec{OP}
И по итогу, раскладывая на координаты x,y,z мы получим следующую систему уравнений:
A_x + u(B_x-A_x) + v(C_x-A_x) = tD_x
A_y + u(B_y-A_y) + v(C_y-A_y) = tD_y
A_z + u(B_z-A_z) + v(C_z-A_z) = tD_z
Я заменю B_i-A_i на ABi, ACi , чтобы упростить чтение уравнения, а также перенесу неизвестные в левую часть уравнения:
uAB_x + vAC_x - tdx = -A_x
uAB_y + vAC_y - tdy = -A_y
uAB_z + vAC_z - tdz = -A_z
Что по итогу наблюдается? Обычная система линейных уравнений с тремя неизвестными. В данном случае u, v это как раз текстурные позиции на плоскости, заданной параметрически (собственно, это и есть параметры), а также t - расстояние до плоскости, которое может служить мерой дальности до найденной точки, но это можно считать и по-другому, с помощью как раз тех самых найденных параметров. Зная параметры, можно рассчитать также и точное местоположение не только точки текстуры, но еще и самой точки, что бывает также очень важно при растеризации и создания, к примеру, шейдерных программ.

§ Вычисление

Чтобы решить СЛАУ, можно воспользоваться разными методами, но здесь лучше всего подойдет именно метод Крамера, который очень распространен для такого рода решения. К тому же любой другой метод будет сложнее для понимания, вычисления, и приведет к тому же самому результату.
Надо найти определить матрицы по методу нахождения определителей (см. Википедию).
\Delta = \begin{vmatrix}AB_x & AC_x & -dx \\\ AB_y & AC_y & -dy \\\ AB_z & AC_z & -dz \end{vmatrix} = dx(AB_zAC_y - AB_yAC_z) + dy(AB_xAC_z - AB_zAC_x) + dz(AB_yAC_x - AB_xAC_y)
Замечу, что dz тут будет константой и вообще по условию dz = 1.
По методу Крамера, чтобы вычислить u,v,t потребуется найти еще 3 определителя
u = \frac{1}{\Delta} \begin{vmatrix}-A_x & AC_x & -dx \\\ -A_y & AC_y & -dy \\\ -A_z & AC_z & -dz \end{vmatrix} = \frac{dx(A_yAC_z - A_zAC_y) + dy(A_zAC_x - A_xAC_z) + dz(A_xAC_y - A_yAC_x)}{\Delta}
v = \frac{1}{\Delta} \begin{vmatrix}AB_x & -A_x & -dx \\\ AB_y & -A_y & -dy \\\ AB_z & -A_z & -dz \end{vmatrix} = \frac{dx(A_zAB_y - A_yAB_z) + dy(A_xAB_z - A_zAB_x) + dz(A_yAB_x - A_xAB_y)}{\Delta}
t = \frac{1}{\Delta} \begin{vmatrix}AB_x & AC_x & -A_x \\\ AB_y & ACy & -A_y \\\ AB_z & ACz & -A_z \end{vmatrix} = \frac{A_x(AC_yAB_z - AB_yAC_z) + A_y(AB_xAC_z - AC_xAB_z) + A_z(AC_xAB_y - AB_xAC_y)}{\Delta}
Все очень просто! Теперь остается лишь только начать вычислять. Для оптимизации расчетов можно сказать следующее: меняются только dx, dy, все же остальные константы можно вычислять один раз для треугольника. Так работают видеокарты, которые не считают все подряд, а перед рендерингом высчитывают константы и работают только с ними.
Замечу еще кое-что. Чтобы рассчитать z на поверхности плоскости, который пересек луч, необходимо домножить dz на t , поскольку t здесь выступает лишь как множитель для dz . Расчет параметра t годится для задач по рейтрейсингу, для установления ближайшей точки пересечения с плоскостью.

§ Программная реализация

Сейчас я приведу программный код, который будет являться справочным материалом.
// Сначала, получаем разности
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 = (a.y*ACz - a.z*ACy),
        A2 = (a.z*ACx - a.x*ACz),
        A3 = (a.x*ACy - a.y*ACx),
        // ---
        B1 = (a.z*ABy - a.y*ABz),
        B2 = (a.x*ABz - a.z*ABx),
        B3 = (a.y*ABx - a.x*ABy),
        // ---
        C1 = (ABz*ACy - ABy*ACz),
        C2 = (ABx*ACz - ABz*ACx),
        C3 = (ABy*ACx - ABx*ACy),
        // ---
        D1 = (ACy*ABz - ABy*ACz),
        D2 = (ABx*ACz - ACx*ABz),
        D3 = (ACx*ABy - ABx*ACy);

float   u = dx*A1 + dy*A2 + dz*A3;
float   v = dx*B1 + dy*B2 + dz*B3;
float   D = dx*C1 + dy*C2 + dz*C3;
float   t = a.x*D1 + a.y*D2 + a.z*D3;

if (D != 0) {

    u /= D;
    v /= D;
    t /= D;
    x  = t*dx;
    y  = t*dy;
    z  = t*dz;

} else {
    u = v = t = 0;
}

§ Уравнение плоскости

Из полученного уравнения есть важный вывод, это уравнение плоскости:
D1*x + D2*y + D3*z + t = 0
Поэтому, из этих данных легко получить нормаль (D1, D2, D3). Возможно, плоскость повернута с другой стороны (левосторонняя или правосторонняя).
Также есть старый материал по этой теме.

§ QBasic 4.5

Пример реализации на языке программирования BASIC
SCREEN 13

' Координаты треугольника
Ax = -5: Ay =  5: Az = 15
Bx =  5: By =  5: Bz = 6
Cx = -5: Cy = -5: Cz = 6

' Предварительный расчет
ABx = Bx - Ax: ACx = Cx - Ax
ABy = By - Ay: ACy = Cy - Ay
ABz = Bz - Az: ACz = Cz - Az

A1 = ( Ay * ACz -  Az * ACy): A2 = ( Az * ACx -  Ax * ACz): A3 = ( Ax * ACy -  Ay * ACx)
B1 = ( Az * ABy -  Ay * ABz): B2 = ( Ax * ABz -  Az * ABx): B3 = ( Ay * ABx -  Ax * ABy)
C1 = (ABz * ACy - ABy * ACz): C2 = (ABx * ACz - ABz * ACx): C3 = (ABy * ACx - ABx * ACy)

' Растеризация
FOR y = 0 TO 200
FOR x = 0 TO 320

  ' Проекционный луч
  dx = x - 160
  dy = 100 - y
  dz = 100

  ' Расчет координат
  u = dx*A1 + dy*A2 + dz*A3
  v = dx*B1 + dy*B2 + dz*B3
  D = dx*C1 + dy*C2 + dz*C3

  ' Плоскость не должна быть параллельна лучу проекции
  IF D <> 0 THEN

    u = u / D
    v = v / D
    c = (15 * u XOR 15 * v) + 16
    IF u >= 0 AND v >= 0 AND u + v <= 1 THEN PSET (x, y), c

  END IF

NEXT
NEXT
Что в итоге получается

17 мая, 2020
© 2007-2022 Все лоскуты недурственно упакованы