Здравствуйте, minorlogic, Вы писали:

MS>>Я пробовал этот метод. Возни с разреженными массивами много, резко возрастают накладные расходы по памяти, а преимущество по времени незначительное (по сравнению с общим массивом клеток и глобальной сортировкой по Y-X). Я так же пробовал модифицированный merge sort. Идея в том, что клетки вдоль ребра уже отсортированы или почти отсортированы, — либо по возрастанию, либо по убыванию — практически готовые куски для merge sort. Но в общем зачете получается выигрыш в 1-3%, и не стоит усилий, а тем более — лишней памяти.

M>А у меня разница в разы была. Скорее всего от того что полигоны были очень сложные и содержали (немного) самопересечения , полигоны были составными (из многихзамкнутых контуров) заполнение even-odd fill.

M>Если интререссно , может топик заведем по методам растеризации полигонов ?


Можно попросить модератора отделить ветку. Я уже внес лепту в модераторство
http://www.rsdn.ru/Forum/Message.aspx?mid=1092306&only=1

Автор: McSeem2
Дата: 26.03.05

Разница в скорости очень сильно зависит от того, что мерять и учитывать
Например, вот на этой картинке http://antigrain.com/demo/graph_test.gif
Получаются следующие относительные времена:

  pipeline    add_path    sort      render     total
    48.831    129.659     72.758    145.989    397.238

Здесь все растеризуется полигонами, включая тонкие линии и это — достаточно жесткий случай для растеризатора по сравнению с полигонами большой площади.
Даже если мы полностью исключим сортировку, получим увеличение производительности на 22%. Но исключить ее нельзя, можно только ускорить, поэтому выигрыш в общем зачете будет процентов 10 максимум (скорее всего, не более 5). Другими словами, данный алгоритм является достаточно хорошо сбалансированным и существенно ускорить его крайне тяжело.

Дело здесь в том, что вычисление клеток со сглаживанием (add_path) занимает существенное время по сравнению с сортировкой — там довольно много работы, в том числе, самое неприятное — целочисленные деления. Если же интерполировать грани Брезенхемом, без сглаживания, эта часть ускорится раз в 10. Render тоже ускорится как минмимум вдвое, поскольку нам не понадобится alpha-blend. И вот тогда сортировка станет критичной. Строго говоря, в этом случае можно обойтись вообще без сортировки, если использовать битовую матрицу. Точнее говоря, нам надо три состояния для правила non-zero fill — "нет клетки", "ребро идет вверх", "ребро идет вниз". Значит по 2 бита на клетку.

Однако, есть и другая задача, гораздо более актуальная. Данный алгоритм со сглаживанием (оригинал — из FreeType by David Turner, который в свою очередь переписан с libArt by Raph Levien) соответствует SVG rendering model. Хотелось бы адаптировать его для Macromedia Flash rendering model. Суть там вот в чем. Полигоны задаются не просто последовательным списком вершин, а произворльным набором ребер (x1,y1,x2,y2). Каждое ребро имеет два аттрибута — цвет закраски слева от ребра и цвет справа. Цвет может иметь флаг "no fill". Таким образом, можно за один проход растеризовать многоцветную сцену — ускорение получается весьма существенным. Ясно, что при такой структуре, входные данные могут быть противоречивыми — например, имеем одно единственное ребро, слева — красно, справа — сине. Непротиворечивость и целостность данных там обеспечивается на более высоком уровне (полигоны должны быть замкнуты, etc).

Казалось бы, больших проблем нет, но если копнуть глубже — их там много. Как вычислять усредненный цвет, если пиксел перекрывается множеством ребер с разными цветами? Как учитывать правило закраски, even-odd, non-zero?
Вот иллюстрации: