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

M>>Сорри за офтоп , чочу поделиться воспоминаниями о том как я писал растеризатор полигонов.
M>>в итоге получил 2 метода.

M>>1. Класический.
M>>сортируем ребра по Y, сканируем линии при каждом попадании на следующую линию ПЕРЕСОРТИРОВЫВАЕМ по X ребра, лучше всего чемто типа пузырька (т.к. сортируем в 99% почти отсортированный или отсортированный список).

MS>Мои давние знакомые из Питера оптимизировали этот алгоритм. Идея в том, что нам надо пересчитывать список активных ребер не во всех точках, а только в точках локальных экстремумов по Y, то есть, /\ или \/. Это дает огромный выигрыш, когда полигон гладкий, но состоит из большого числа точек, типа как области на картах.
MS>Но это работает только для правила even-odd fill. На практике же более актуально non-zero.

Я работал со сложными. кстати тоже для географических карт. Конечно в учет для трасировки берутся только /\ или \/. Это я только бегло описал. Хорошее описание с которого я брал куски была Майкла Абраша статья.

M>>2. трассируем каждое ребро независимо и резульнат трасировки помещаем в 2 мерный разряженный масив.
M>>Затем растиризуем по строкам каждый раз заново сортируя.

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

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

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