Ищу быстрый алгоритм рендеринга многоугольника
Я работаю с Microchip dsPIC33FJ128GP802. Это небольшой микроконтроллер на основе DSP, и у него не так много мощности (40 миллионов инструкций в секунду). Я ищу способ визуализировать выпуклый (т.е. простой) многоугольник. Я имею дело только с 2D-фигурами, целочисленной математикой и установкой или очисткой пикселей (т.е. 1 бит на пиксель). У меня уже есть процедуры для быстрого рисования по горизонтали и вертикальные линии (запись до 16 пикселей за 88 циклов), поэтому я хотел бы использовать алгоритм развертки.
Однако, все алгоритмы, которые я нашел, похоже, зависят от деления (которое занимает 18 циклов на этом процессоре) и математики с плавающей запятой (которая эмулируется в программном обеспечении и поэтому очень медленная; она также занимает много ПЗУ), или предположим, что я иметь большой объем памяти. У меня осталось только 2 КБ, ~ 14 КБ используется для графической памяти моих 16 КБ. Так что, кто-нибудь знает какие-либо хорошие встроенные машинные алгоритмы, на которые они могут указать мне с помощью простой реализации C или псевдокода, которую я могу реализовать в сборке? Желательно в сети, я не живу рядом с хорошими книжными магазинами с большим количеством книг по программированию.
Спасибо. :)
РЕДАКТИРОВАТЬ: Уточнение, это алгоритм заполнения многоугольника, который я ищу. Я могу реализовать алгоритм контура многоугольника, используя алгоритм рисования линий Брезенхэма (как предлагает Марк Б.)
РЕДАКТИРОВАТЬ №2: Я хотел, чтобы все знали, что у меня есть базовый алгоритм на Python. Вот ссылка на код. Код общедоступного домена.
5 ответов
Как насчет линейного алгоритма Брезенхема ? После некоторой настройки это чистая целочисленная математика, и ее можно адаптировать для рисования многоугольника путем простой итерации начальных точек по краям многоугольника.
продолжение комментариев:
Я попытаюсь нарисовать это в ASCII, но, вероятно, это будет выглядеть как примитив. Линию Брезенхэма можно использовать для рисования закрашенного многоугольника, выбирая начальную кромку и итеративно перемещая линию Брезенхэма по холсту параллельно этой точке.
Допустим, у вас есть такие точки:
*(1)
*(3)
*(2)
*(4)
Они пронумерованы в порядке приоритета сортировки слева направо, поэтому вы выбираете крайнюю левую начальную точку (1) и решаете, хотите ли вы двигаться по вертикали (начало 1 , 2) или по горизонтали (1,3). Это, вероятно, будет зависеть от того, как ваш DSP отображает отображение, но давайте вернемся к вертикали.
Итак ... Вы используете линию 1-2 в качестве стартовой линии брезенхема. Вы вычисляете начальные точки линий заполнения, используя строки 1-3 и 2-4 в качестве начальных / конечных точек. Начните вычисление Брезенхэма для каждого и нарисуйте еще один Брезенхэм между этими двумя точками. Что-то вроде:
1.1 -> 2.1, then 1.2 -> 2.2, then 1.3 -> 2.3
и т. Д., Пока вы не дойдете до конца любой из этих строк. В данном случае это произойдет, когда нижняя начальная точка достигнет (4). В этот момент вы начинаете повторять строку 4,3, пока не дойдете до точки 3 с обеими начальными точками, и все будет готово.
*-------
\\\\\\\\ *
\\\\\\\\
*-----\\
------- *
Где черточки - это начальные точки, которые вы рассчитали по 1-3 и 2-4, а косые черты - это линии заливки.
Конечно, это работает, только если точки правильно отсортированы и у вас есть выпуклый многоугольник.Если он вогнутый, вам нужно быть очень осторожным, чтобы не позволить линиям заливки пересекать границу, или выполнить некоторую предварительную обработку и подразделить исходный поли на два или более выпуклых.
Возможно, будет проще разбить проблему на две части. Сначала найдите / напишите алгоритм, который рисует и заполняет треугольник. Во-вторых, напишите алгоритм, который разбивает произвольный многоугольник на треугольники (используя разные комбинации вершин).
Чтобы нарисовать / заполнить треугольник, используйте алгоритм линии Брезенхема, чтобы одновременно провести линию между точками 0 и 1, а также между 1 и 2. Для каждой входной точки x нарисуйте пиксель, если он равен до или между точками y , созданными двумя линиями. Когда вы достигнете одной конечной точки, продолжайте использовать незаконченную сторону и сторону, которая еще не использовалась.
Изменить:
Чтобы разбить выпуклый многоугольник на треугольники, расположите точки по порядку и назовите их P1, P2, ... PN . Пусть P1 будет вашей «корневой» точкой, и строите треугольники, используя эту точку и комбинации соседних точек. Например, пятиугольник даст три треугольника P1-P2-P3 , P1-P3-P4 и P1-P4-P5 . В общем, выпуклый многоугольник с N сторонами разложится на N-2 треугольников.
Вы можете посмотреть статьи Майкла Абраша о докторе Доббсе о заливке / растре полигонов и т. Д. Он использует математику с фиксированной точкой
Томас, если у вас есть алгоритм рисования линий Брезенхэма, используйте его как основу для дальнейшего улучшения: разделите многоугольник на части -полигоны с горизонтальной линией разреза через каждую вершину. Затем начните обводить 2 левые и правые стороны каждого из этих суб-многоугольников, используя Брезенхэм. Th это способ, которым у вас есть 2 конечные точки каждой линии сканирования в вашем многоугольнике.
Я бы начал с преобразования многоугольника в набор треугольников и визуализации их, потому что треугольники легко визуализировать с помощью линий развертки. Хотя всеже есть некоторые подробности.
По сути, подпроцедура рисования-треугольника получит необработанный треугольник и продолжит:
- Отклонить вырожденные треугольники (где две из трех вершин перекрываются).
- Отсортируйте вершины по Y (так как их всего три, вы можете жестко запрограммировать логику сортировки).
- Теперь вы должны знать, что будет три вида треугольников: с плоским верхом, с плоским основанием и «общие» треугольники. Вы хотите обработать общий треугольник, по сути разделив его на по одному плоского типа. Это потому, что вы не хотите, чтобы
ifтестировал каждую строку сканирования, чтобы определить, изменился ли наклон. - Чтобы визуализировать плоский треугольник, вы должны запустить два алгоритма Брезенхэма параллельно для итерации пикселей, составляющих края, и использовать точки, которые они дают вам, в качестве конечных точек каждой горизонтальной линии сканирования.