Ищем быстрый алгоритм рендеринга полигонов

Question

Я работаю с микрочипом dsPIC33FJ128GP802.Это небольшой микроконтроллер на основе DSP, и он не имеет большой мощности (40 миллионов инструкций в секунду).Я ищу способ визуализации выпуклого (то есть простого) многоугольника.Я имею дело только с 2D-фигурами, целочисленной математикой и заданными или прозрачными пикселями (т.е. 1 бит на пиксель). У меня уже есть процедуры для рисования быстрых горизонтальных и вертикальных линий (запись до 16 пикселей за 88 циклов), поэтому я бы хотелиспользовать алгоритм сканирования.

Однако все алгоритмы, которые я нашел, похоже, зависят от деления (которое занимает 18 циклов на этом процессоре) и математики с плавающей запятой (которая эмулируется в программном обеспечении и поэтому очень медленная; она также занимает много времени)ROM), или предположим, что у меня большой объем памяти.У меня осталось только 2K, ~ 14K используется для графической памяти моего 16K.Так кто-нибудь знает какие-либо хорошие встроенные машинные алгоритмы, на которые они могут указать мне простой реализацией C или псевдокода, которые я могу реализовать в сборке?Предпочтительно в сети, я не живу рядом с хорошими книжными магазинами со многими книгами по программированию.

Спасибо.:)

РЕДАКТИРОВАТЬ: Уточнение, это алгоритм заполнения полигонов, который я ищу.Я могу реализовать алгоритм контура многоугольника, используя алгоритм рисования линий Брезенхэма (как предполагает Марк Б.)

РЕДАКТИРОВАТЬ # 2: Я хотел, чтобы все знали, что я получил базовый алгоритм в Python.Вот ссылка на код.Открытый код домена.

http://dl.dropbox.com/u/1134084/bresenham_demos.py

Answer 1

Как насчет алгоритма Брезенхема Line?После некоторой настройки, это чистая целочисленная математика, и ее можно адаптировать для рисования многоугольника простой итерацией начальных точек по краям многоугольника.

комментарии:

Я попытаюсь нарисовать этов ASCII, но это, вероятно, будет выглядеть грубо.Брезенхэма можно использовать для рисования заполненного многоугольника, выбирая начальный край и итеративно перемещая линию брезенхама по холсту параллельно этой точке.

Допустим, у вас есть несколько таких точек:

*(1)
                      *(3)

    *(2)         
                 *(4)

Они пронумерованы в порядке сортировки слева-справа, поэтому вы выбираете крайнюю левую начальную точку (1) и решаете, хотите ли вы идти вертикально (начало 1,2) или горизонтально (1,3).Это, вероятно, будет зависеть от того, как ваш DSP будет отображаться, но давайте вернемся к вертикали.

Итак ... Вы используете линию 1-2 в качестве начальной строки bresenham.Вы вычисляете начальные точки линий заполнения, используя строки 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, а косые черты - это линии заливки.

Конечно, это работает, только если точки правильно отсортированы, и у вас выпуклый многоугольник.Если он вогнутый, вам следует быть очень осторожным, чтобы не допустить пересечения линий заливки через границу, или выполнить некоторую предварительную обработку и разделить исходный полигон на два или более выпуклых.

Answer 2

Возможно, вы захотите посмотреть статьи Майкла Абраша о докторе Доббсе о заполнении / растре полигонов / и т. Он использует математику с фиксированной точкой

Answer 3

Томас, если у вас есть алгоритм рисования линий Брезенхэма, используйте его в качестве основы для дальнейшего улучшения: разделите свой полигон на подполигоны с горизонтальной линией разреза через каждую вершину.Затем начните прослеживать 2 левые и правые стороны каждой из этих подполисов, используя Брезенхем.Таким образом, у вас есть 2 конечные точки каждой линии сканирования в вашем многоугольнике.

Answer 4

Я бы начал с преобразования полигона в набор треугольников и их рендеринга, потому что треугольники легко визуализировать с помощью линий сканирования. Хотя и здесь есть некоторые детали.

По сути, подпроцедуре draw-triangle будет дан необработанный треугольник, и она будет продолжена:

1. Отклонить вырожденные треугольники (где две из трех вершин перекрываются).
2. Сортировка вершин по Y (поскольку существует только три, вы можете жестко закодировать логику сортировки).
3. Теперь, в этот момент вы должны знать, что будет три вида треугольников: один с плоским верхом, другой с плоским дном и «общие» треугольники. Вы хотите обработать общий треугольник, по существу разделив его на один из плоских типов. Это потому, что вы не хотите, чтобы if проверял каждую линию сканирования, чтобы определить, изменился ли наклон.
4. Чтобы отобразить плоский треугольник, вы должны запустить два алгоритма Брезенхэма параллельно для итерации пикселей, составляющих края, и использовать точки, которые они вам дают, в качестве конечных точек каждой горизонтальной линии сканирования.

Answer 5

Может быть проще разбить проблему на две части. Сначала найдите / напишите алгоритм, который рисует и заполняет треугольник. Во-вторых, напишите алгоритм, который разбивает произвольный многоугольник на треугольники (используя разные комбинации вершин).

Чтобы нарисовать / заполнить треугольник, используйте Алгоритм линии Брезенхэма, чтобы одновременно нарисовать линию между точками 0 и 1 и между 1 и 2. Для каждой входной точки x нарисуйте пиксель, если он равен или находится между ними. y точек, сгенерированных двумя линиями. Когда вы достигнете одной конечной точки, продолжайте, используя незаконченную сторону и сторону, которая еще не использовалась.

Edit: Чтобы разбить выпуклый многоугольник на треугольники, расположите точки по порядку и назовите их P1, P2, ... PN. Пусть P1 будет вашей «корневой» точкой, и строите треугольники, используя эту точку и комбинации соседних точек. Например, пятиугольник даст три треугольника P1-P2-P3, P1-P3-P4 и P1-P4-P5. В общем случае выпуклый многоугольник с N сторонами будет разложен на N-2 треугольников.