Одна из базовых задач компьютерной графики – нарисовать на экране произвольный закрашенный треугольник:
Сам треугольник задан в векторном виде, то есть у него есть три вершины с координатами: (x0, y0), (x1, y1) и (x2, y2). Между каждой парой координат можно провести линию:
(x0, y0) – (x1, y1)
(x1, y1) – (x2, y2)
(x2, y2) – (x0, y0)
Эти линии задают геометрический контур треугольника. Растеризация – это вывод треугольника на экран в растровом виде, то есть в виде множества закрашенных пикселов.
Где это нужно?
На растеризации треугольников базируется вся 3D-графика. Дело в том, что треугольник – самая простая геометрическая фигура, и обладает удобными свойствами – например, треугольники всегда выпуклые, а их вершины легко сортируются.
Любые другие многоугольники можно растеризовать, разбив их на треугольники, и растеризовав каждый треугольник отдельно.
Почему олдскульная?
В настоящее время практически все компьютеры снабжены видеоускорителями. Поэтому растеризация не представляет проблем. Мы просто передаём в видеоускоритель координаты вершин треугольника, и он сам его рисует (правда, нужно написать ещё шейдер), причём очень быстро, и с различным освещением, и с текстурой и т.д.
Мы вскоре доберемся до видеоуcкорителей и шейдеров. А пока что рассмотрим чисто программный алгоритм растеризации, чтобы:
- понять, как это работает
- работало на любых компьютерах, даже ZX Spectrum и БК-0010
- работало даже на текстовом экране
- получить представление о скорости работы
Я также планирую использовать эту реализацию в генетическом алгоритме, воспроизводящем картинку с помощью треугольников.
Реализация
Писать будем на языке C, так как нужна максимальная скорость. Всё, что необходимо для компиляции программ на C, перечислено в материале Пишем Сапёра на C.
Чтобы растеризовать треугольник, мы в цикле запускаем воображаемую горизонтальную линию, которая перемещается от верха до низа с шагом один пиксел:
На каждом шаге эта линия всегда пересекается с двумя из трёх сторон треугольника (и вот поэтому треугольники удобны!)
Зная две точки пересечения, мы рисуем линию между ними, и вот мы закрасили одну линию в треугольнике! Последовательно смещаясь вниз, вычисляя точки пересечения и рисуя между ними линии, мы закрашиваем весь треугольник.
Общее описание алгоритма:
- Двигать горизонтальную линию сверху вниз
- Для каждой стороны треугольника находить пересечение с этой линией
- Пересекаться будут только какие-то две стороны из трёх, нужно отобрать их
- Между точками пересечения нарисовать линию
Нахождение пересечения произвольной линии с горизонтальной линией описано в материале Пересечение линии с препятствием.
У этого общего описания есть скрытые проблемы.
- Нужно постоянно проверять, какая из сторон треугольника пересекается с линией, а какая нет.
- Из-за целочисленных округлений координат пикселов в некоторых местах происходит неверное определение пересечения и появляются артефакты.
Поэтому сразу оптимизируем процесс. Это будет нудновато и громоздко, но разбивается на элементарные, легко решаемые задачи. Для начала треугольник нужно нормализовать так, чтобы мы знали, какая вершина самая верхняя, а какая самая нижняя. При этом третья вершина автоматически становится средней (спасибо треугольнику!)
Сперва находим самую верхнюю вершину c помощью двух сравнений – её y-координата должна быть меньше двух остальных. Если она оказалась больше, то меняем вершины местами, вместе с координатой x:
Затем из двух оставшихся вершин выбираем среднюю и нижнюю:
И вот у нас нормализованный треугольник. Как я и говорил, это громоздко и нудно, но по факту тут не происходит ничего серьёзного.
Теперь, зная, что y0 это точно верхняя вершина, а y1 это точно средняя вершина, мы точно знаем, какие две стороны треугольника будут пересекаться с горизонтальной линией вплоть до координаты y1. Это стороны (y0 - y1) и (y0 - y2).
Двигая горизонтальную линию (переменная top_y) от y0 до y1, вычисляем пересечения и рисуем первую половину треугольника:
Затем двигаем линию от y1 до y2, и на этот раз в пересечениях участвует третья сторона треугольника (y1 - y2), в то время как первая (y0 - y2) продолжает использоваться дальше (это гарантируется треугольником):
Рисуем вторую часть, и треугольник готов:
Я сделал вывод случайных треугольников на экран, и вот как это выглядит:
Теперь попробуем оценить скорость рисования.
На моём ноутбуке (он еле-еле тянет игру Cyberpunk 2077 на самых низких настройках) 100 000 (сто тысяч) треугольников рисуется за примерно 42 секунды. Это 2380 треугольников в секунду. Если игра, допустим, работает на частоте 60 кадров в секунду, то в одном кадре можно отрисовать только около 40 треугольников. Это чудовищно мало.
Но если посмотреть, что отбирает больше всего времени, то это будет вызов функции SDL_UpdateWindowSurface(). Данная функция отображает на экране то, что было нарисовано в буфере видеопамяти.
Сейчас она вызывается после рисования каждого треугольника. Если её не вызывать, то треугольники будут по-прежнему рисоваться, только мы их не увидим. Без вызова этой функции время работы программы сокращается до 2.5 секунды. Получаем 40 000 треугольников в секунду, или 667 треугольников в кадр. Это более реалистичный вариант, так как в каждом кадре игра сначала рисует все необходимые треугольники и затем только один раз вызывает SDL_UpdateWindowSurface().
Теперь посмотрим, сколько времени занимает собственно рисование треугольника. Оставим все вычисления, но не будем рисовать, то есть не будем вызывать метод SDL_FillRect(). Время сокращается до 0.3 секунды. Это 333 333 треугольников в секунду, или 5 555 треугольников в кадр.
Как видим, основной проблемой являются не вычисления, а вызовы SDL_UpdateWindowSurface() и SDL_FillRect(). Надо подумать над тем, как исправить ситуацию.
Но как бы то ни было, 5 555 треугольников всё равно довольно мало. Игры оперируют сотнями тысяч треугольников на ускорителях. Поэтому в следующий раз сделаю OpenGL-вариант и сравним.
А данная реализация вполне подойдёт, чтобы начать делать генетический алгоритм на треугольниках, так как там всего лишь десятки, а не тысячи треугольников, и с ними производятся операции подсчёта рейтинга и т.п., то есть их мало просто нарисовать, но нужно ещё и с ними работать руками, а программная реализация для этого как раз подходит.
Скриншот, который может претендовать на современное искусство:
Полный код программы на GitHub
Читайте дальше: Альфа-канал вручную
