При переходе к следующей строке развертки в процессе закрашивания помимо инкрементального перемещения по ребру могут произойти еще кое-какие вещи.
1. Новая строка развертки может теперь лежать ниже (или выше) ребра, представленного в списке АЕЬ. С целью упрощения проверки такой ситуации в АЕЬ хранится ордината у верхней концевой точки каждого ребра. Если новое значение у превышает это верхнее предельное значение, то данное ребро удаляется из списка АЕЬ.
Средства для растровой графики
2. Когда ордината у становится равной значению ординаты нижней концевой точки некоторых ребер полигона, появляется одно или несколько новых ребер. Записи для таких ребер добавляются в список AEL в форме ссылки на отдельную таблицу, которую мы рассмотрим позднее.
3. Для непростых полигонов порядок абсцисс пересечений с ребрами может измениться на обратный в случае, когда пересекаются два его ребра. Если это происходит, то список пересечений должен быть отсортирован заново.
После закрашивания серий текущей строки развертки значение у увеличивается, абсциссы пересечений обновляются, некоторые ребра удаляются из списка AEL, а другие ребра добавляются в него; и при необходимости осуществляется пересортировка абсцисс пересечения. Закрашивание серий новой строки развертки проводится аналогично.
Таблица ребер
Для того чтобы определить, какие ребра следует добавить при переходе к следующей строке развертки, мы могли бы проверить каждую вершину полигона Р, чтобы узнать, какие ребра появятся после приращения у, однако этот метод является неэффективным. Вместо этого информация о каждом ребре полигона Рсобирается заранее и предусмотрительно помещается в специальную таблицу ребер (edge table - ЕТ). ЕТ обеспечивает быстрый доступ к информации, необходимой для обновления списка AEL.
Таблица ЕТ оформлена в виде массива списков edgetable[], по одному списку для каждой строки развертки. Фрагмент таблицы ЕТ для полигона Q с рис. 10.33 показан на рис. 10.36. Эта часть ЕТ формируется при начальном обходе полигона, который производится для устранения горизонтальных ребер и сокращения других.