Развертка с групповой сортировкой

Простейший алгоритм построчного сканирования.


BC	BC	BC
BA	BA	BA
BD	BD	BD
CD	CD	CD
AD	AB	AD


BA	BA	BA
BC	BC	BC
BD	BD	BD
CD	CD	CD
AD	AD	AD

2 формы сортировки

Порядок сортировки начинаемый с у влияет на размер списка активных ребер.

Либо обрабатывается больше информации чем нужно для данной строки.

Проблема борьбы с избыточной информацией решается за счет введения дополнительных данных.

Вначале выполняется групповая сортировка по у всех отрезков изображения.

У – группа

1- пусто

2 -

3 – пусто

4 -

5 – пусто

6 -

7 – пусто

8 – пусто

При групповой сортировке по у образуются области памяти или группы.

При просмотре дисплейного списка заносится информация в группу, соответствующей наибольшей у координате.

х –координата точки пересечения со сканирующей строкой.

- изменение координаты х при переходе одной с другой

- число сканирующих строк пересекаемых данным отрезком.

Алгоритм

Список активных ребер для каждой сканирующей строки формируется добавлением информации из каждой у группы соответствующей сканирующей строке.

Координаты х точек пересечения

сортируется в порядке сканирования, а ребра из списка активных ребер преобразуются в растровую форму.

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