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

В алгоритмах, относящихся к группе методов «затравочного заполнения», один пиксель внутри закрашиваемого контура – затравка – должен быть заранее известен. Начиная с этого пикселя, алгоритмы находят и закрашивают все другие пиксели области, ограниченной контуром, до обнаружения границ. В процессе работы в качестве новой затравки назначаются, по тем или иным соображениям, другие пиксели области.

Гранично-определенная область характеризуется тем, что все пиксели на ее границе имеют определенный цвет, причем ни один пиксель самой области не может иметь этот цвет. Четырехсвязной называется область, которую можно заполнить, переходя от пикселя к пикселю в четырех направлениях: влево, вправо, вверх и вниз.

Работу построчного алгоритма заполнения с затравкой для гранично-определенной четырехсвязной области схематично можно описать так:

• поместить координаты адресуемой точки затравочного пикселя в стек;

• пока стек не пуст:

  • извлечь данные о пикселе из стека; если ему уже присвоено требуемое значение цвета – проигнорировать, если нет, тогда:

  • присвоить пикселю требуемое значение цвета;

  • заполнить интервал с текущим пикселем вправо и влево от него вдоль сканирующей строки до обнаружения границ;

  • переменным х_лев и х_пр присвоить значения горизонтальных координат адресуемых точек соответственно крайнего левого и крайнего правого пикселей интервала;

  • в диапазоне х_лев  х  х_пр проверить строки, расположение непосредственно над и под текущей строкой; если в них есть еще не заполненные интервалы (т.е. не все пиксели граничные или уже заполненные), то в указанном диапазоне данные о крайнем правом пикселе на каждом интервале поместить в стек.

Рис.4 иллюстрирует последовательность действий при работе такого алгоритма по заполнению конкретной гранично-определенной четырехсвязной области. В качестве исходной затравки используется пиксель с координатами адресуемой точки (3, 5). На рисунке обозначены также уровни стека, на которые помещаются данные о соответствующих пикселях.

Ниже представлена запись рассматриваемого алгоритма на псевдокоде (см. приложение 1). В ней переменные Треб_знач и Гран_знач идентифицируют цвета заполняемой области и ее границы соответственно.

Затравка (x, y) выдает затравочный пиксель

Инициализируем стек

Push Затравка (x, y)

while (стек не пуст)

Извлечение пикселя из стека

Pop Пиксель (x, y)

if Пиксель (x, y) < > Треб_знач then

Пиксель (x, y) = Треб_знач

Сохранение x-координаты затравочного пикселя

Врем_x = x

Заполнение интервала справа от затравки

x = x + 1

while Пиксель (x, y) < > Гран_знач

Пиксель (x, y) = Треб_знач

x = x + 1

end while

Сохранение крайнего справа пикселя

х_пр = x – 1

Восстановление x-координаты затравки

x = Врем_x

Заполнение интервала слева от затравки

x = x – 1

while Пиксель (x, y) < > Гран_знач

Пиксель (x, y) = Треб_знач

x = x – 1

end while

Сохранение крайнего слева пикселя

х_лев = x + 1

Проверка строки выше на наличие незаполненных интервалов в диапазоне х_лев  х  х_пр

x = х_лев

y = y + 1

while x  х_пр

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

Флаг = 0

while (Пиксель (x, y) < > Гран_знач and

Пиксель (x, y) < > Треб_знач and x < х_пр)

if Флаг = 0 then Флаг = 1

x = x + 1

end while

if Флаг = 1 then

if (x = х_пр and Пиксель (x, y) < > Гран_знач and

Пиксель (x, y) < > Треб_знач) then

Push Пиксель (x, y)

else

Push Пиксель (x – 1, y)

end if

Флаг = 0

end if

Продолжение проверки, если диапазон был прерван

х_вход = x

while ((Пиксель (x, y) = Гран_знач or

Пиксель (x, y) = Треб_знач) and x < х_пр)

x = x + 1

end while

Проверка увеличения x-координаты

if x = х_вход then x = x + 1

end while

Проверка строки ниже на наличие незаполненных интервалов – отличается от проверки строки выше только тем, что вместо оператора y = y + 1 подставляется оператор y = y – 1

end if

end while

Алгоритм двумерного отсечения Сазерленда-Коэна

Д анный алгоритм реализует отсечение отрезков координатно-ориентированным прямоугольником, границы которого: левая, правая, нижняя и верхняя – задаются координатами соответственно x_л , x_п , y_н и y_в (рис.5). В алгоритме используются четырехразрядные (битовые) коды, определяющие расположение концов отрезков относительно границ отсекающего окна. При формировании кода конца отрезка с координатами (x, y) в первый (крайний правый) бит заносится 1, если x < x_л , во второй – если x > x_п , в третий – если y < y_н , в четвертый – если y > y_в . В остальных случаях в соответствующие биты заносится 0. Таким образом, вся координатная плоскость разбивается на девять областей, в каждой из которых концу отрезка присваивается уникальный код (см. рис.5). При внутреннем отсечении признаком полной видимости отрезка являются нулевые коды обоих его концов (как для отрезка ab на рис.5). Признак безусловной невидимости отрезка – отличное от нуля побитовое логическое произведение концевых кодов (так, у отрезка cd, расположенного целиком левее отсекающего окна, с кодами концов 0101 и 0001 такое произведение будет равно 0001). Вместе с тем, при полностью нулевом побитовом логическом произведении концевых кодов отрезок может оказаться частично видимым (как отрезки ef и gh) или полностью невидимым (как отрезок ij). Для подобных отрезков при выявлении их возможных видимых частей используются результаты определения точек пересечения бесконечной прямой линии, проведенной через отрезок, с бесконечными прямыми линиями, проведенными через ребра отсекающего окна.

Для отрезка с началом в точке P₁ (x₁ , y₁) и концом в точке P₂ (x₂ , y₂), если он не вертикален ( ), такие точки пересечения на прямых, проведенных через левое и правое ребра, будут иметь координаты соответственно:

x = x_л , ; x = x_п , .

Если отрезок не горизонтален ( ), координаты аналогичных точек пересечения на прямых, проведенных через нижнее и верхнее ребра, будут равны соответственно:

, y = y_н ; , y = y_в .

Последовательность действий в алгоритме двумерного внутреннего отсечения Сазерленда-Коэна следующая. С использованием кодов концов отрезок проверяется на полную видимость и безусловную невидимость. Если проверка не дает очевидного результата, поочередно работают четыре отсекателя в виде бесконечных прямых, проходящих соответственно через левое, правое, нижнее и верхнее ребра отсекающего окна. В каждом случае проверяется, не лежит ли отрезок полностью в той же стороне от отсекающей прямой, что и само окно (очевидно, например, что если в первом бите кодов концов отрезка содержится 0, отрезок полностью лежит правее левой отсекающей прямой). Если это так, переходят к следующей отсекающей прямой. В противном случае проверяют, не лежит ли начало отрезка в той же стороне, что и окно. Если это подтверждается, начало и конец отрезка меняются местами. Начало отрезка в любом случае оказывается по отношению к отсекающей прямой в стороне, противоположной той, где находится окно. После определения точки пересечения прямой, проведенной через отрезок, с текущей отсекающей прямой начало отрезка переносится в эту точку (удаляется часть отрезка). Полученный новый отрезок вновь проверяется на полную видимость и безусловную невидимость. В зависимости от результата переходят к следующей отсекающей прямой или алгоритм заканчивает работу.

Ниже приведен алгоритм на псевдокоде (см. приложение 1). В нем используются следующие обозначения: Окно – массив 14, содержащий координаты x_л , x_п , y_н , y_в ; P₁ , P₂ , P – начало и конец отрезка с координатами соответственно (x₁ , y₁) и (x₂ , y₂), а также концевая точка, обрабатываемая подпрограммой Конец; Код1, Код2, Код – массивы 14, содержащие коды соответственно начала отрезка, конца отрезка и точки, обрабатываемой подпрограммой Конец; Сумма1, Сумма2, Сумма – суммы всех элементов соответственно массивов Код1, Код2, Код; Лог_произв – сумма побитовых логических произведений кодов концов отрезка; Видимость – признак видимости отрезка, принимающий значения Да, Нет и Возможно в случаях, когда отрезок полностью виден, безусловно невидим и возможно частично видим соответственно; Флаг – индикатор ориентации отрезка, принимающий значения 1 (при вертикальности отрезка) или 0 (в остальных случаях).

Инициализация переменных

for i = 1 to 4

Код1 ( i ) = 0

Код2 ( i ) = 0

next i

Флаг = 0

Проверка вертикальности отрезка

if x₂ – x₁ = 0 then

Флаг = 1

else

Вычисление тангенса угла наклона

end if

Для каждой отсекающей прямой

for i = 1 to 4

call Коэн (P₁ , P₂ , Окно; Видимость, Код1, Код2)

if Видимость = Да then 2

if Видимость = Нет then 3

Проверка положения отрезка относительно отсекающей прямой

if Код1 ( i ) = Код2 ( i ) then 1

Если P₁ в той же стороне, что и окно, P₁ и P₂ поменять местами

if Код1 ( i ) = 0 then

Врем = P₁

P₁ = P₂

P₂ = Врем

end if

Поиск точки пересечения; перенос в нее точки P₁

if i  2 then

y₁ = m*(Окно ( i ) – x₁ ) + y₁

x₁ = Окно ( i )

else

if Флаг < > 1 then

x₁ = 1/m*(Окно ( i ) – y₁ ) + x₁

end if

y₁ = Окно ( i )

end if

1 next i

2 Draw P₁ P₂

3 finish

Подпрограмма анализа видимости отрезка

subroutine Коэн (P₁ , P₂ , Окно; Видимость, Код1, Код2)

call Конец (P₁ , Окно; Код1, Сумма1)

call Конец (P₂ , Окно; Код2, Сумма2)

Видимость = Возможно

Проверка полной видимости отрезка

if Сумма1 = 0 and Сумма2 = 0 then

Видимость = Да

else

Проверка безусловной невидимости отрезка

call Лог_произв (Код1, Код2; Лог_произв)

if Лог_произв < > 0 then Видимость = Нет

end if

return

Подпрограмма вычисления кодов концевой точки

subroutine Конец (P, Окно; Код, Сумма)

if x < Окно ( 1 ) then Код ( 1 ) = 1 else Код ( 1 ) = 0

if x > Окно ( 2 ) then Код ( 2 ) = 1 else Код ( 2 ) = 0

if y < Окно ( 3 ) then Код ( 3 ) = 1 else Код ( 3 ) = 0

if y > Окно ( 4 ) then Код ( 4 ) = 1 else Код ( 4 ) = 0

Сумма = 0

for i = 1 to 4

Сумма = Сумма + Код ( i )

next i

return

Подпрограмма вычисления логического произведения

subroutine Лог_произв (Код1, Код2; Лог_произв)

Лог_произв = 0

for i = 1 to 4

Лог_произв = Лог_произв + Integer ((Код1( i ) + Код2( i ))/2)

next i

Алгоритм плавающего горизонта

Д анный алгоритм относится к группе алгоритмов, реализующих удаление невидимых линий и поверхностей. Чаще всего он используется для визуализации трехмерных поверхностей, описываемых функциями вида F (x, y, z) = 0. Главная идея заключается в сведении трехмерной задачи к двумерной: поверхность сечется параллельными и равноотстоящими друг от друга плоскостями, и на экран выводятся линии пересечения (рис.9). Так, например, при задании секущих плоскостей постоянными значениями z поверхность представляется совокупностью кривых, которые описываются функциями y = f (x, z) при z = const, т.е. y = f (x). Плоскости z = const сортируют по степени их удаленности от точки наблюдения. Затем поочередно для каждой плоскости, начиная с ближней, строится лежащая на ней кривая. При этом для каждого из значений х, задаваемых в пространстве изображения (в координатной плоскости экрана) с шагом, равным расстоянию между пикселями (т.е. единице), определяется значение у. Если на текущей кривой при конкретном значении х соответствующее значение у больше или, наоборот, меньше, чем значения y для всех предыдущих кривых при том же значении х, то текущая кривая полагается видимой в данной точке; в противном случае она считается невидимой (на рис.9 невидимые участки кривых показаны пунктиром).

Для хранения максимальных и минимальных значений у при каждом значении х используются два массива чисел: массив верхнего горизонта и массив нижнего горизонта (они отражают текущее состояние «верхнего горизонта» и «нижнего горизонта» соответственно). Очевидно, что по мере обработки кривых значения в первом массиве могут только увеличиваться («верхний горизонт» всплывает), а во втором – только уменьшаться («нижний горизонт» опускается). При использовании таких массивов текущая кривая в какой-либо точке полагается видимой, если при заданном значении x значение у либо больше соответствующего значения в массиве верхнего горизонта, либо меньше аналогичного значения в массиве нижнего горизонта. Если кривая в данной точке видима, значение у заносится в один из массивов на место прежнего элемента.

При аналитическом задании исходной функции расчет кривых с единичной дискретностью изменения х, как правило, не вызывает трудностей. Если же по каким-либо причинам (например, при обработке результатов экспериментальных исследований) шаг задания точек по оси x больше 1, при расчете значений y в промежуточных точках применяется интерполяция (чаще всего линейная) значений y между известными значениями. Полученные таким образом значения y используются затем как при анализе видимости кривых в этих точках, так и при заполнении массивов верхнего и нижнего горизонтов.

Приведем уравнение, соответствующее линейной интерполяции кривой между двумя известными точками с координатами (x_n , y_n) и (x_n+k , y_n+k) (здесь k – шаг задания точек по оси х):

.

П ри изложенном подходе, когда обрабатываемая текущая кривая появляется слева или справа из-под множества ранее обработанных кривых, может появиться некорректность в изображении поверхности – эффект зазубренного ребра (на рис.10 приводящие к искажению фрагменты кривой показаны пунктиром). Избежать такого эффекта можно относительно простым приемом: при обработке каждой текущей кривой (за исключением первой) создаются ложные боковые ребра, соединяющие соответственно крайние левые и крайние правые точки текущей и предыдущей кривых. Ложные ребра на экран не выводятся, но ординаты точек на них при тех дискретных значениях x, при которых ребра определены, участвуют в формировании массивов верхнего и нижнего горизонтов (при тех же условиях, что и сами кривые).

С учетом приведенных соображений формальное описание последовательности действий алгоритма плавающего горизонта можно описать примерно так: поочередно для каждой из равноотстоящих друг от друга плоскостей z = const, начиная с ближней от точки наблюдения:

• определить координаты первой (левой) точки P_n на лежащей в плоскости кривой y = f (x);

• обработать левое боковое ребро: если точка P_n является первой точкой на первой кривой, то запомнить ее в качестве P_n–1 и закончить обработку; в противном случае создать ребро, соединяющее P_n–1 и P_n , занести, если это требуется, ординаты точек ребра в массивы верхнего и нижнего горизонтов и запомнить P_n в качестве P_n–1 ;

• определить координаты остальных точек на кривой y = f (x) при дискретном изменении x с единичным шагом, в том числе последней (правой) точки Q_n ;

• если y = f (x) является первой обрабатываемой кривой, занести значения y всех точек на ней для соответствующих x в массивы верхнего и нижнего горизонтов и закончить обработку, если нет, тогда: сравнить для каждой точки на кривой значение y с имеющимися в массивах верхнего и нижнего горизонтов (для соответствующего значения x); если y точки не меньше, чем в массиве верхнего горизонта, или не больше, чем в массиве нижнего горизонта, или значения в массивах отсутствуют, объявить точку видимой и занести y точки в соответствующий массив (или в оба массива); в противном случае объявить точку невидимой;

• обработать правое боковое ребро: если точка Q_n является последней точкой на первой кривой, то запомнить Q_n в качестве Q_n–1 и закончить обработку; в противном случае создать ребро, соединяющее Q_n–1 и Q_n , занести, если это требуется, ординаты точек ребра в массивы верхнего и нижнего горизонтов и запомнить Q_n в качестве Q_n–1 .