§ Растеризация

Существуют разные способы и методы для того, чтобы вывести треугольник на экран. Я расскажу только вот об одном из них, он достаточно быстрый и даже целочисленный, что может сэкономить процессорное время.
Допустим, треугольник уже спроецирован по точкам на экран, то остается заполнить пространство между этими точками.
Первым делом, необходимо отсортировать точки по вертикали сверху вниз, поскольку далее будет все зависеть именно от порядка. Треугольник ABC, отсортированный по Y, состоит из двух полутреугольников — верхнего и нижнего с общей гранью AC. Грань первого треугольника пролегает по AB, а вторая грань по BC.

§ Сортировка

В JS сортировку трех точек сделать просто:
raster(a, b, c) {
    let p = [a, b, c].sort(function (x, y) { return x.y < y.y ? -1 : 1; });
}

§ Целочисленное приращение

Позиция точек отрезка AC и первого полу-треугольника начинаются в одной точке Ax.
let [Ax,  Adx] = [p[0].x, 0];
let [ACx, ACy] = [p[2].x - p[0].x, p[2].y - p[0].y];
Здесь Ax - это целочисленное значение пикселя, а Adx - это числитель для целочисленного приращения. В данном случае, чтобы получить точку x, требуется использовать формулу:
x = A_x + t\frac{C_x - A_x}{C_y - A_y}
Где t находится от 0 до C_y-A_y включительно. Здесь:
  • ACx = C_x - A_x
  • ACy = C_y - A_y .
Поэтому, чтобы найти новый x, необходимо добавить ACx в числитель, и если числитель превышает знаменатель, то увеличить (уменьшить) Ax, и вычесть из числителя ACx, восстановив равновесие в формуле. Так и работает как одна сторона, так и вторая сторона:
Adx += ACx; Ax += Math.trunc(Adx / ACy); Adx %= ACy;
Bdx += AMx; Bx += Math.trunc(Bdx / AMy); Bdx %= AMy;
Использование функции trunc обязательно, поскольку floor будет направлять не в ту сторону при отрицательном числе.
В случае если разница между самой верхней и самой нижней точкой равняется 0, то по идее, такой треугольник лучше даже не рисовать. С другой стороны, достаточно провести линию. Не уверен, нужно ли это делать, но пока что уберу рисование такого вырожденного в линию треугольника.
if (ACy === 0) return;

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

Рисовка двух полутреугольников описывается очень просто:
for (let i = 0; i < 2; i++) {

    // Боковая сторона
    let [AMx, AMy] = [p[i+1].x - p[i].x, p[i+1].y - p[i].y];
    let [Bx,  Bdx] = [p[i].x, 0];

    ....
}
Для каждого полутреугольника будет взят собственный Bx и Bdx (числитель) и AMx и AMy - разницы \Delta x и \Delta y одного ребра.
Дело осталось за малым — просто нарисовать линии и приращивать их Ax, Bx.
for (let y = p[i].y; y < p[i+1].y + i; y++) {

    // Находится за пределами
    if (y >= this.height) break;

    // Пока что просто линией
    if (y >= 0) this.line(Ax, y, Bx, y, 0xffc000);

    // Сдвиг точек x1,x2. Важно использовать trunc!
    Adx += ACx; Ax += Math.trunc(Adx / ACy); Adx %= ACy;
    Bdx += AMx; Bx += Math.trunc(Bdx / AMy); Bdx %= AMy;
}
В случае, если y находится за верхней границей экрана, то рисовать линию не надо. Если y уходит за нижние границы экрана, то рисовать далее не требуется.
Я бы сказал, что алгоритм далек от идеального, но все же... И вот вышло то, что вышло, а то что не вышло, не вышло по итогу вследствие страшного небытийного Бытия.
18 авг, 2022
© 2007-2022 Тупил лиственный монитор