Выделение первого или второго, четвертого или пятого или третьего слагаемого.
if Δi < 0 then 2
if Δi > 0 then 3
if Δi = 0 then 20
δ = 2 * Δi + 2 * y1 – 1
if δ ≤ 0 then 10
if δ > 0 then 20
определить 4 или 5
δ = 2 * Δi + 2 * x1 – 1
if δ ≤ 0 then 10
if δ > 0 then 20
Выполение шагов:
10 xi = xi + 1
Δi = Δi + 2 * xi + 1
goto 1
20 xi = xi + 1
yi = yi – 1
Δi = Δi + 2 * xi – 2 * yi + 2
goto 1
30 yi = yi – 1
Δi = Δi – 2 * yi + 1
goto 1
80 finish
При развертке в реальном времени производится смена произвольного представления атрибутов четырьмя геометрическими характеристиками, которые определяют визуальный цвет, оттенок и интенсивность.
Кроме того, координаты x, y, углы наклона и текст относятся к геометрическим характеристикам и последовательны и упорядочены по координате y.
Во время воспроизведения каждого кадра процессор сканирует эту информацию и вычисляет интенсивность каждого пикселя на экране. Требования на память обычно ограничиваются необходимостью хранить дисплейный список и одну сканирующую строку.
Поскольку информация о сцене (об изображении) хранится в произвольно организованном дисплейном списке, то добавление или удаление информации из списка осуществляется легко, однако сложность выводимого изображения ограничивается скоростью дисплейного процесса.
Обычно это означает, что ограничивается число отрезков или многогранников в картине, количество пересечений со сканирующей строкой или число цветов или полутонов серого.
Для пересечения каждого отрезка дисплейного списка со сканирующей строкой простейшей реализации метода, всякий раз при изображении строки обрабатывается весь дисплейный список.
При генерации в виде изображения на каждую сканирующую строку, а значит на обработку всего списка приходится всего 36.5 мкс. Это время позволяет использовать данный метод только для рисунков, несложных чертежей, т.к. в общем случае каждый отрезок в сцене пересекает каждую сканирующую строку, то количество начислений может быть сокращено введением списка активных ребер.
Этот список содержит все отрезки изображения, которые пересекают сканирующую строку.
Для организации и управления списка активных ребер можно использовать ряд методов. Например, сначала отрезки изображений сортируются по наибольшей координате y. При этом (в одном из методов) для сортировки используются два перемещающихся указателя. Указатель начала используется для обозначения начала списка активных ребер, а указатель конца – для обозначения конца списка активных ребер.
Поясним работу примером. Пусть дана картинка:
1 2 3
BC←b BC BC
BA BA←b BA
BD←e BD BD←b
CD CD←e CD
AD AD AD←e
Рис. а
1 2 3
BA←b BA←b BA
BC BC BC←b
BD←e BD BD
CD CD←e CD
AD AD AD←e
Рис. б
1 2 3
BD←b BD←b BD←b
BA BA BA
BC←e BC BC
CD CD←e CD
AD AD AD←e
Рис. в
На рисунке представлена сцена с тремя сканирующими характерными строками.
Данный рисунок показан в первых трех столбцах как типичный отсортированный список отрезков фигуры.
Указатель начала в исходном положении устанавливается на начала списка ВС.
Указатель конца устанавливается на последний отрезок в списке, который начинается выше рассмотренной сканирующей строки.
При сканировании изображение необходимо корректировать. Список активных рёбер, при этом указатель конца переходит вниз чтобы получить в список новый отрезок, начинающийся на текущей сканированной строке или выше.
Порядок сортировки отрезков, начинающихся с одной и той же координаты, влияет на размер списка активных ребер. При этом возникает ситуация, что некоторые ребра (отрезки) никогда не покидают список. В результате, может обрабатываться больше информации, чем необходимо.
Эту проблему можно устранить путем введения дополнительной структуры данных, при этом можно упростить вычисление пересечения каждого отрезка со сканирующей строкой.
Сначала выполняется групповая сортировка по оси Y всех отрезков изображения. При этой сортировке создаются области памяти или группы для каждой сканирующей строки. Например, если применяется 512 сканирующих строк, то используется 512 групп.
При просмотре отрезка в дисплейном списке информация о каждой сканирующей строке помещается в группу, соответствующую наибольшей величине координаты Y для отрезка.
Для простого черно-белого контурного изображения необходимо записывать только координату X точки пересечения с групповой сканирующей строкой.
∆X – изменение координаты X при переходе от одной сканирующей строки к другой.
∆Y – число сканирующих строк, пересекаемых отрезком.
Для простых изображений большинство из Y-групп будет пусто. Список активных ребер для текущей сканирующей строки формируется добавлением информации из Y-группы, соответствующей этой строке.
Координаты X для точек пересечения сортируются в порядке сканирования и ребра из списка активных ребер преобразуются в растровую форму.
После этого для каждого отрезка из списка активных ребер величину ∆Y уменьшают на 1.
Если ∆Y < 0, то отрезок исключается из списка.
Для каждого отрезка координата X точки пересечения для новой сканирующей строки получается прибавлением ∆X.
Этот процесс повторяется для всех сканирующих строк.
Если используется фиксированный размер ∆-групп, то для пересечения с каждой сканирующей строкой выделяется фиксированное количество памяти.
Таким образом, максимальное число пересечений с каждой сканирующей строкой предопределено заранее и, следовательно, сложность изображения ограничена.
Одним из методов, позволяющих преодолеть это ограничение может служить использование в качестве структуры данных последовательное индексирование списков.
В этом случае каждая Y-группа содержит только указатель на расположение в структуре данных информации.
Таким образом, структура представляет собой последовательно-индексированный список и данные.
Метод определения пересечения отрезков со сканирующими строками дает хорошие результаты для вертикальных и почти вертикальных отрезков, однако, для горизонтальных отрезков точек пересечения будет вычислено очень мало, что приведет к некачественному изображению отрезка.
Для решения этой задачи предлагают определять пересечение на двух последовательных сканирующих строках и активировать пиксели между точками пересечения, при этом для горизонтальных отрезков использовать только концевые точки.
Т.к. все изображения обрабатываются для каждого видеокадра, развертка в реальном времени применима для высокоинтерактивной графики.
При использовании групповой сортировки по Y отрезки могут быть добавлены или удалены из дисплейного списка простым добавлением или удалением их из Y-группы и связанной с ними структуры данных. Для удобства добавления и удаления отрезков используется структура данных в виде связного списка. При этом приходится иметь элементы в данной структуре, определяющие конец строки, группы данных. В результате добавления информация об отрезке добавляется к концу списка данных. Если отрезок удаляется из фигуры, список модифицируется.
