§ Теория трехмерного треугольника

Technology 3DNow!. Немного теории, которая гласит следующее.

• Есть параметрическое уравнение линии, которое задается как точка вектора N + t*NM.
• И параметрическое уравнение плоскости, которая задается как сложение двух векторов A + u*AB + v*AC

Необходимо, чтобы линия и плоскость пересеклись, а значит, что они должны стать друг другу равны. Линия задается одним параметром t, а плоскость двумя параметрами (u,v): N + t*NM = A + u*AB + v*AC. Если это непонятно, то статью можно дальше не читать.
Теперь я раскодирую вектора по координатам. Вектора имеют 3 точки в декартовой системе координат (x,y,z).

N.x + t*NM.x = A.x + u*AB.x + v*AC.x
N.y + t*NM.y = A.y + u*AB.y + v*AC.y
N.z + t*NM.z = A.z + u*AB.z + v*AC.z

Здесь к примеру, NM.x = M.x - N.x, AC.x = C.x - A.x и так далее... Как и обычно, потребуется неизвестные (u,v,t) перенести в левую часть уравнений, а известное — в правую, что переписывается следующим образом. И еще сделаю замену (NM.x, NM.y, NM.z) на (dx, dy, dz):

u*AB.x + v*AC.x - t*dx = AN.x
u*AB.y + v*AC.y - t*dy = AN.y
u*AB.z + v*AC.z - t*dz = AN.z

Здесь AN.x = N.x - A.x. Если начальной точки нет, N=0, то остается лишь только -(A.x,A.y,A.z). Надо найти решения уравнения, но из-за того что я уже раньше находил, не буду переписывать вывод формулы.

A =  dx(A.y*AC.z  - A.z*AC.y)  +  dy(A.z*AC.x  - A.x*AC.z)  +  dz(A.x*AC.y  - A.y*AC.x)
B =  dx(A.z*AB.y  - A.y*AB.z)  +  dy(A.x*AB.z  - A.z*AB.x)  +  dz(A.y*AB.x  - A.x*AB.y)
C = A.x(AB.z*AC.y - AB.y*AC.z) + A.y(AB.x*AC.z - AB.z*AC.x) + A.z(AB.y*AC.x - AB.x*AC.y)
D =  dx(AB.z*AC.y - AB.y*AC.z) +  dy(AB.x*AC.z - AB.z*AC.x) +  dz(AB.y*AC.x - AB.x*AC.y)

Вообще прекрасно видно, что коэффициенты вычисления 2x2 матриц совпадают для C и D, так что высчитывать их заново не придется. Теперь, зная все коэффициенты, вычислить (u,v,t) можно легко u = A/D, v=B/D, t=C/D.
Особенность использования t в том, что оно задает параметр линии, а поскольку конечная точка вычисляется как t*(dx,dy,dz) то как можно заметить, при фиксированном dz число t пропорционально глубине. Это означает, что вычислять можно только один раз за кадр коэффициент C, и использовать его для всего треугольника, но, по правде говоря, меняя D, ведь t=C/D, где C-константа для кадра, а вот D меняется в зависимости от рисуемой сейчас в данный момент точки на экране. Так что как бы так не было, а делить число придется. От деления никуда не избавиться.
Вторая особенность заключается в том, что коэффициенты при C или D задают нормаль треугольника, так что это можно еще использовать для расчета освещения, например, или уровня наклона к камере.

§ Вычисления

Можно попробовать сделать предрасчет треугольника перед тем как его рендерить.

A1,A2,A3 = A.y*AC.z  - A.z*AC.y,  A.z*AC.x  - A.x*AC.z,  A.x*AC.y  - A.y*AC.x
B1,B2,B3 = A.z*AB.y  - A.y*AB.z,  A.x*AB.z  - A.z*AB.x,  A.y*AB.x  - A.x*AB.y
C1,C2,C3 = AB.z*AC.y - AB.y*AC.z, AB.x*AC.z - AB.z*AC.x, AB.y*AC.x - AB.x*AC.y

Когда начинается растеризация треугольника, то начинает бросаться луч в различные точки экрана в (dx,dy,dz). Здесь dz всегда фиксированное и по сути означает фокусное расстояние или FOV, для экрана размером 320 на 200 выбирается расстояние вдвое меньшее чем высота, то есть dz=100.
Для dx=-160 до 160, dy = -100 до 100, получается что луч пробегает все точки на экране (их 64000), бросая луч и проверяя точку пересечения с треугольником:

D = (C1*dx + C2*dy + C3*dz)
u = (A1*dx + A2*dy + A3*dz) / D
v = (B1*dx + B2*dy + B3*dz) / D
t = (C1*A.x + C2*A.y + C3*A.z) / D

Ясное дело, что таким методом крайне накладно вычислять треугольник. Каждый раз вычислять u,v,t необязательно, поскольку при инкременте x+1 добавляется к числителю +A1, +B1 (u, v соответственно) и к знаменателю +C1. Достаточно одного лишь сложения, но с делением конечно же, дела обстоят хуже.

§ Рисование

Представим себе, что существуют 3 точки прямо перед камерой, которая смотрит в сторону (0,0,1):

const A = {x: -2, y:  2, z: 3};
const B = {x:  2, y:  2, z: 4};
const C = {x:  1, y: -2, z: 3};

Теперь надо рассчитать разности у векторов AB, AC:

const AB = {x: B.x - A.x, y: B.y - A.y, z: B.z - A.z};
const AC = {x: C.x - A.x, y: C.y - A.y, z: C.z - A.z};

А после этого рассчитать и параметры треугольника.

const A1 = A.y*AC.z  - A.z*AC.y;
const A2 = A.z*AC.x  - A.x*AC.z;
const A3 = A.x*AC.y  - A.y*AC.x;
const B1 = A.z*AB.y  - A.y*AB.z;
const B2 = A.x*AB.z  - A.z*AB.x;
const B3 = A.y*AB.x  - A.x*AB.y;
const C1 = AB.z*AC.y - AB.y*AC.z;
const C2 = AB.x*AC.z - AB.z*AC.x;
const C3 = AB.y*AC.x - AB.x*AC.y;

Как заметить можно, тут используется 18 умножении и 9 вычитаний. С точки зрения вычисления на верилоге, с учетом наличия DSP модулей, это даст 9 тактов при частоте 25 мгц + 1 такт на подсчет разностей. Можно, при наличии большого количества DSP, все за 1 такт подсчитать.
И сам цикл рисования.

let U = A1*x + A2*y + A3*dz;
let V = B1*x + B2*y + B3*dz;
let D = C1*x + C2*y + C3*dz;

for (let dy = y; dy < 100; dy++) {

    let [u, v, d] = [U, V, D];
    for (let dx = x; dx < 160; dx++) {

        u += A1; v += B1; d += C1; // Инкремент X
        if (u >= 0 && v >= 0 && u + v <= d) {
            this.pset(160 + dx, 99 - dy, 0x80FF40);
        }
    }

    U += A2; V += B2; D += C2; // Инкремент Y
}

§ Рисованный треугольник