Предыдущая часть: Олдскульная растеризация треугольников
В предыдущей части мы рассмотрели алгорим для вывода на экран треугольника (в рамках подготовки к реализации графического генетического алгоритма).
Я нашёл другую программу, которая использует в качестве генов не только треугольники, но и многоугольники (для краткости буду называть их полигонами).
Исходный код этой программы на С++ (автор Gabriele Greco), а также исполняемый файл, находятся здесь:
http://www.ggsoft.org/archives/genetic_test.zip
Она позволяет добиться существенно лучших результатов при меньшем количестве полигонов, что в свою очередь ускоряет работу генетического алгоритма.
Поэтому я задался целью тоже сделать растеризацию полигонов. Я посмотрел в исходный код и примерно понял, как это работает, но копировать код не стал, чтобы разобраться самому.
Сейчас я расскажу общий принцип, как происходит растеризация полигона. Во-первых, сложность состоит в том, что треугольник всегда выпуклый, а многоугольник может быть и невыпуклым, и даже само-пересекающимся, например:
Принцип работы остаётся примерно такой же, как с треугольником, но добавляются лишние условия.
Для начала мы должны выяснить минимальную и максимальную y-координаты полигона (min_y и max_y).
Затем в цикле пускаем сканирующую линию по координате y от min_y до max_y:
Так же как и с треугольником, мы проверяем, какие грани полигона пересекаются со сканирующей линией. Но если в треугольнике этих пересекающих граней может быть только две, в полигоне их может быть сколько угодно. Поэтому на каждом шаге сканирующей линии все грани перебираются в цикле, и для каждой из них считается x-координата пересечения. В данном примере мы насчитали 4 координаты (x0, x1, x2, x3):
У этих точек есть интересное свойство: первая из них это точка входа в полигон, вторая это точка выхода, затем снова точка входа и выхода... То есть если объединять их попарно, то мы получим отрезки, которые надо нарисовать:
Из-за произвольности формы полигона таких отрезков на одной линии может получиться много. Поэтому делается буфер, в который мы добавляем найденные координаты пересечения по мере перебора граней полигона.
Когда все грани перебраны, мы получаем буфер, наполненный какими-то координатами пересечения. Их нужно отсортировать так, чтобы они располагались в порядке возрастания. В оригинальной программе это делалось функцией qsort(), но я сделал сортировку пузырьком прямо при добавлении элемента в буфер. Так что буфер всегда отсортирован.
Затем мы берем из буфера пару координат и рисуем горизонтальную линию между ними, затем ещё пару и т.д., пока буфер не закончится.
Потом мы переходим к следущей сканирующей линии и повторяем всё снова.
Вот собственно и всё, что требуется для растеризации полигона. Но встречаются граничные случаи, где алгоритм сбивается. Это когда концы граней точно совпадают с координатой сканирующей линии:
Здесь мы видим, как две грани сходятся в одной точке, и несмотря на то, что точка визуально одна, в буфер добавляются две – по одной от каждой грани. В данном случае это правильно: две одинаковые точки в буфере создают отрезок нулевой длины и выводятся как одна точка, что и требуется. Вторые две за ними также выводятся правильно. Но теперь посмотрим на другой вариант:
Здесь в первой точке тоже сходятся две грани, и порождают две одинаковых координаты пересечения. Как мы помним, первая координата это вход в полигон, а вторая – выход. Следовательно, после вывода нулевого отрезка из этих двух координат мы попадём в состояние "вне полигона". Но как можно видеть, мы всё ещё внутри полигона до следущей точки. То есть, состояние "вне полигона" определяется неправильно.
Чтобы этого не произошло, в углах, где соединяются две грани, нужно порождать не две точки пересечения, а одну. Но тогда перестанет работать предыдущий рассмотренный случай с отдельно стоящей острой вершиной.
На самом деле для каждого случая требуется своя проверка. Нужно взять две грани, которые сходятся в рассматриваемой точке, и проверить их взаимное расположение:
Если обе этих грани расположены с одной стороны от сканирующей линии (то есть их вторые концы или оба больше, или оба меньше y), то это угол, для которого нужно добавить две точки пересечения.
Если же эти грани расположены с разных сторон от сканирующей линии (один конец больше, а другой меньше y), то это угол, для которого нужно добавить только одну точку пересечения.
Самое удивительное, что этот алгоритм работает с такой же скоростью, что и алгоритм треугольников. Замеры на рисование 100000 полигонов не показали никаких существенных отличий. Так что от отдельного рисования треугольников можно и отказаться, ведь достаточно сделать полигон с тремя гранями.
Мне, однако, не нравится, что на каждом шаге сканирующей линии происходит перебор всех граней полигона. Если высота экрана 480 пикселов, и полигон занимает всю эту высоту, то для пятиугольника получим перебор из 2400 шагов.
У меня есть идея, как это упростить, и возможно даже ускорить. Об этом напишу в следующем выпуске.
Полный код программы на GitHub
