Предыдущие части: Олдскульная растеризация полигонов, Альфа-канал вручную, Олдскульная растеризация треугольников
В рамках работы над проектом генетического алгоритма я сначала сделал растеризацию треугольника, затем добавил возможность делать полупрозрачные треугольники. После этого заменил треугольники многоточечными полигонами и вроде бы пришёл к состоянию, в котором находятся аналогичные проекты "Генетической Моны Лизы".
Однако меня интересовала идея трёхточечного градиента: что, если каждая вершина треугольника будет иметь свой цвет и свой уровень прозрачности? Можно ли с помощью этого сделать более эффективный генетический алгоритм?
Забегая вперёд, отвечу – да.
Треугольники, имеющие вершины разных цветов, должны закрашиваться плавно меняющимся градиентом. Прозрачность также меняется плавно от вершины к вершине. Выглядит это так:
Как это сделать с многовершинными полигонами, мне пока сложно представить, поэтому я вернулся к простым и надёжным треугольникам.
Итак, костяк кода, который растеризует треугольник, уже есть в предыдущих материалах.
Когда мы рисовали пиксел треугольника с альфа-каналом, сам треугольник имел постоянный цвет и постоянную прозрачность. Эта версия отличается лишь тем, что цвет и прозрачность каждой точки треугольника мы теперь будем вычислять более сложно, потому что они постоянно меняются.
Как обычно, мы находим концы скан-линии, пересекающей треугольник:
Обратим внимание, что начало линии лежит между вершинами v0 и v2, а конец - между вершинами v0 и v1.
Для удобства вычислим разницу координат y между v0 и v2, а также разницу между цветом v0 и v2:
dy = v2.y - v0.y;
color_diff = v2.color - v0.color;
Скан-линия всегда начинает рисоваться от v0.y и движется до v2.y. Когда y-координата линии совпадает с v0.y, её цвет равен
v0.color + 0 * color_diff;
То есть это чистый цвет v0. Когда совпадает с v2.y, цвет равен
v0.color + 1 * color_diff;
То есть это чистый цвет v2. И эти, и все промежуточные знaчения мы получаем через пропорцию:
line.start.color = v0.color + (line.y - v0.y) / dy * color_diff;
Для нужд целочисленной арифметики перепишем выражение по-другому, чтобы сначала было умножение, а потом деление:
line.start.color = v0.color + (line.y - v0.y) * color_diff / dy;
И вот у нас есть цвет начала скан-линии. Теперь точно так же нужно получить цвет конца скан-линии. На этот раз мы будем вычислять разницу в координатах и цветах между v1 и v0:
dy = v1.y - v0.y;
color_diff = v1.color - v0.color;
line.end.color = v0.color + (line.y - v0.y) * color_diff / dy;
Теперь нужно нарисовать линию попиксельно от начала до конца. Так как у нас есть цвет начала линии и цвет конца линии, мы вычисляем промежуточные цвета аналогичным способом. Получим разницу цветов и x-координат между концами линии:
color_diff = line.end.color - line.start.color;
width = line.end.x - line.start.x;
Далее, начиная со старта линии, двигаясь в цикле по x, получаем цвет каждого пиксела опять же через пропорцию:
for (x = 0; x < width; x++) {
color = line.start.color + (x - line.start.x) * color_diff / width;
}
Остаётся только сохранить этот цвет в видеопамяти, смешав его с уже имеющимся там цветом, что было описано в материале про альфа-канал.
Как оптимизировать?
Когда я говорю про цвет, на самом деле речь идёт про четыре компонента: красный, зелёный, синий и прозрачность. Поэтому все вышеприведённые вычисления нужно делать для каждого компонента по отдельности. Это сразу увеличивает объём кода в 4 раза, и приводит к появлению кучи новых переменных, таких как diff_r, diff_g, diff_b, и т.д.
Объём математических операций также значительно возрастает, поэтому первое, что я сделал – постарался, чтобы все вычисления, которые могут быть сделаны заранее, были вынесены из циклов наружу.
Поясню на примере. В цикле повторяется, допустим, вычисление (line.end.color - line.start.color):
for (x = 0; x < width; x++) {
color = line.start.color + (x - line.start.x) * (line.end.color - line.start.color) / width;
}
Я вычисляю это выражение заранее, присваиваю его переменной color_diff, и теперь в цикле нет повторения математической операции:
color_diff = line.end.color - line.start.color;
for (x = 0; x < width; x++) {
color = line.start.color + (x - line.start.x) * color_diff / width;
}
Казалось бы, это победа и можно ожидать некоторого прироста производительности. На самом деле – и я не понимаю почему – код не только не стал быстрее, но даже местами стал показывать худший результат.
Я пытался предвычислить многие операции, но всё это приводило только к появлению новых и новых переменных, а код не ускорялся вообще, или начинал работать медленнее.
Это дико бесит. Я бы посмотрел, что там происходит в ассемблере, но пока нет никакого желания.
Поэтому я наоборот избавился от почти всех предвычисленных переменных и оставил лишние вычисления в цикле. Строчек кода стало чуть меньше, и то уже хорошо. А работает точно так же.
Lookup-таблица прозрачности
Это ещё одна попытка оптимизации, на этот раз вычисления цвета с учётом прозрачности. Эта формула также разбиралась в материале про альфа-канал:
color = (color1 * alpha + color2 * (255 - alpha)) / 255
Здесь есть два умножения и деление. Компоненты color и alpha имеют размер 1 байт, и умножение байта на байт можно представить, натурально, в виде "таблицы умножения": по горизонтали располагаем значения alpha от 0 до 255, по вертикали значения color от 0 до 255, а на пересечениях строк и столбцов – их произведения.
Кроме того, всё это делится на 255, поэтому я сделал таблицу из значений, сразу поделённых на 255 (пожертвовав немного точностью). Размер такой таблицы довольно большой – 64 килобайта, но по современным меркам это ничто.
Теперь вместо умножения и деления готовые значения сразу берутся из таблицы alpha_lut:
color = alpha_lut[(alpha << 8) + color1] + alpha_lut[((255 - alpha) << 8) + color2];
Такие таблицы называются LUT (Look-Up Table), то есть "справочные таблицы".
Но это тоже не помогло :) программа стала работать МЕДЛЕННЕЕ, совершенно явно. Так что я вернулся к старому варианту.
Условия в цикле
Так как я заранее не знаю, слева или справа находится линия v0-v2, концы сканирующей линии могут поменяться местами. Поэтому при рисовании каждой линии (в цикле по координате y) стояло условие: мы слева или справа? В соответствии с ним корректировались концы линии.
Я попытался оптимизировать и это, также просчитав заранее необходимые параметры и назначив ещё кучу переназначаемых переменных. Как бы то ни было, условия из цикла ушли. Но... и это не помогло!!!
Короче говоря, я плюнул и оставил самый первый вариант программы, который мне изначально казался ужасно неоптимизированным. Но лучше его, по факту, ничего не работает. А мне придётся заняться этой загадкой плотнее когда-нибудь.
Исходный код программы на C лежит на github в ветке gradient.
