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


Алгоритмы заполнения областей и формирования карт заполнения

Данная работа ориентирована, в первую очередь, на двумерную графику, представляющую собой в основном сложившуюся совокупность концепций и методов, зафиксированную в графических стандартах. Одно из основных понятий, содержащихся в этих стандартах, - "примитив вывода". Предлагаемый в статье новый примитив вывода КАРТА ЗАПОЛНЕНИЯ есть обобщение известного примитива ОБ-' ЛАСТЬ ЗАПОЛНЕНИЯ.
Известны два наиболее общих задания плоских областей: а) границей и внутренней точкой; б) только границей. Алгоритмы, ориентированные на первый способ, обеспечивают итерационную процедуру поиска всех внутренних точек области. При этом внутренней точкой области считается любая точка на плоскости, которую можно соединить с исходной внутренней точкой линией, не пересекающей границы области. Такие алгоритмы допускают использование произвольных типов элементов контура границы, в том числе отрезки прямых, дуги окружностей и другие кривые, и произвольный порядок их следования. Но эти алгоритмы не согласуются со стандартами машинной графики, так как могут допускать искажение результата заполнения после аффинных преобразований.
При втором способе задания области используются так называемые алгоритмы парного выбора, основанные на процедурах сканирования. Эти алгоритмы отличаются большим разнообразием, однако могут иметь существенные ограничения. Так, например, алгоритмы, позволяющие исиользовать дуги окружностей в качестве элементов границ, не допускают произвольного порядка этих элементов при задании области. С другой стороны, алгоритмы, безразличные к порядку следования элементов границ, не обеспечивают работу с дугами.
 
Алгоритмы парного выбора основаны на правиле парного выбора, по которому определяется принадлежность некоторой тестируемом точки внутренней части области. В стандартах сформулировано следующее правило парного выбора: Из заданной (тестируемой) точки проводится тестирующий луч, идущий в бесконечность. Если число пересечений между этим лучом и границей области нечетное (индекс пересечений нечетный), то данная точка лежит внутри области. Если число пересечений четное (индекс пересечений четный), то точка лежит вне области. Если тестирующий луч проходит по касательной к границе области, то число пересечений не изменяется.
Приведенное выше правило парного выбора можно сформулиро вать и таким образом:
При вычислении индекса пересечения тестирующего луча с границей области учитывается число участков границ, имеющих общие точки с этим лучом и лежащих (строго) по одну сторону от него.
Под словом "строго" понимается то, что при вычислении индекса пересечения не учитываются участки границ, лежащие на тестирующем луче.
Для области тестируемой точки и тестирующего луча, индекс пересечения к можно посчитать по правилу парного выбора двумя способами. При этом в обоих случаях индекс к будет нечетным. Это означает, что тестируемая точка лежит внутри области.
 
Рассмотрим алгоритм парного выбора, инвариантный порядку следования и типам элементов границ. Этот алгоритм обеспечивает заполнение областей с точностью до пикселов границы. Он состоит из двух этапов:
1)    формирование переключателей аппарата заполнения в процессе интерполяции границы области;
2)    сканирование пространства отображения, при котором для каждой сканирующей линии в качестве внутренних точек области выбираются точки, заключенные между последовательными несмежными парами переключателей аппарата заполнения.
Заметим, что при отображении отрезков прямых, дуг окружностей и других кривых две точки (текущая и предыдущая) растрового представления элемента контура границы образуют, в общем случае,
четыре варианта ориентации с двумя возможными направлениями в каждом варианте, соответствующими восьми направлениям при интерполяции . Переход от предыдущей точки к текущей называется шагом интерполяции. Шаги интерполяции могут рассматриваться как элементарные участки границы, к которым можно применить модифицированное правило парного выбора.
 
Процесс интерполяции (организованный, например, по алгоритму Брезенхэма [5! при формировании отрезков прямых или по алгоритму Питвея [6] при формировании дуг кривых второго порядка) на каждом шаге интерполяции порождает значения элементарных приращений dx и dy по осям координат. Каждое элементарное приращение может принимать значения -1, 0 или +1, но оба они не могут быть равны нулю одновременно.
Если в алгоритме на втором этапе работы используются горизонтальные сканирующие линии, то на первом этапе на каждом шаге интерполяции в качестве переключателей аппарата заполнения могут фиксироваться либо "нижние" , либо "верхние"  точки. При вертикальных сканирующих линиях могут использоваться либо "правые" , либо "левые" точки. Многократное фиксирование одной точки, например при перегибах или самопересечениях контура границы, сводится к обеспечению индекса пересечения, взятому по модулю.
На первом этапе работы алгоритма фиксируются переключатели аппарата заполнения в однослойной карте битов R путем инвертирования значений соответствующих битов по правилу парного выбора (см. рис. 3, г), рассчитанного на вертикальные сканирующие линии. Для горизонтальных сканирующих линий достаточно на каждом шаге интерполяции анализировать значение приращения dy, а не dx.
 
На втором этапе алгоритма  заполнение текущей строки растра R(Y) обеспечивается путем ее сложения по правилу поразрядной суммы по модулю 2 со строкой R(Y-l).
 
Рассмотрим принцип работы обсуждаемого алгоритма на приме- ; заполнения треугольной области ABC. При формировали границы АВ  на первом шаге интерполяции (от 1чки (1.1) к точке (2.2)) будет зафиксирована (в соответствии с пра- июм (2)) в качестве переключателя аппарата заполнения точка (1.1), на втором шаге (от точки (2.2) к точке (3.3)) - точка (2.2) и т. д., на последнем шаге (от точки (5.5) к точке (6.6)) - точка (5.5).
При формировании границы ВС будут выполнены только вертикальные шаги интерполяции, не влияющие на процесс формирования переключателей аппарата заполнения .
При формировании границы СА на первом шаге интерполяции (от точки (6.1) к точке (5.1)) в качестве переключателя аппарата заполнения будет зафиксирована точка (5.1), на втором - точка (4.1) и т. д., на последнем шаге - точка (1.1). Но поскольку точка (1.1) уже была зафиксирована при формировании границы АВ, то повторное фиксирование "сотрет" переключатель заполнения .
После процедуры заполнения (в соответствии со вторым этапом алгоритма) будет получено результирующее изображение.
 
Рассмотренный алгоритм может быть обобщен на случай, когда требуется отобразить семейство смежных и изолированных областей одного приоритета. Назовем такое семейство областей КАРТОЙ ЗАПОЛНЕНИЯ. КАРТА ЗАПОЛНЕНИЯ позволяет задавать множество областей, которые могут иметь прямолинейные или криволинейные границы. Каждый элемент контура границы сопровождается информацией о видах заполнения соответствующих областей. Под видом заполнения здесь понимается совокупность типа заполнения, например "сплошное", "штрихованное" и так далее, и конкретного цвета, конкретной штриховки и т. д. При задании КАРТЫ ЗАПОЛНЕНИЯ используются два типа границ: абсолютные и относительные. Каждой абсолютной границе ставится в соответствие вид заполнения отдельной области, а каждой относительной границе - вид заполнения двух смежных областей
Остановимся далее на КАРТАХ ЗАПОЛНЕНИЯ, состоящих из сплошных областей. Каждая область заполняется своим цветом, определяющим вид заполнения. Абсолютные границы связываются со значениями индексов цветом отдельных областей, а каждая относительная граница - со значением, равным поразрядной сумме (по модулю 2) индексов цветов двух смежных областей, разделенных этой границей.
Для таких КАРТ ЗАПОЛНЕНИЯ можно сформулировать следующее модифицированное правило парного выбора: При определении вида заполнения конкретной области проводится тестирующий луч из бесконечности в точку, принадлежащую этой области. Далее учитываются только индексы цветов участков границ, имеющих общие точки с этим лучом и лежащих (строго) по одну сторону от него.
Вид заполнения области вычисляется по следующей формуле:
Т - R1 xor R2 хог ... хог Ri,    (3)
где Rl, R2, ... , Ri - значения индексов цвета, связанные с участками границ, учтенными при тестировании.
 
Например, вид заполнения области, включающей в себя точку , при рассмотрении участков границ, расположенных "сверху" ' тестирующего луча, будет вычисляться по формуле
Т - С хог (С хог А) - А,    (4)
три рассмотрении участков границ, расположенных, "снизу" от тес- рующего луча, - по формуле
Т - С хог (С хог В) хог (В хог А) - А.    (5)
Ниже приведен текст модуля FMapCGA, написанный на языке rbo Pascal (версия 5.0) и рассчитанный на формирование однопри- нетной информации в виде КАРТЫ ЗАПОЛНЕНИЯ. Модуль обес- твает работу с графическим адаптером CGA.
FMapCGA; face
procedure Begin_FiIl_Map;
procedure Drav^Boundary (xl,yl,x2,y2.color : integer); procedure End_Fi]l_Map;
:mentation
ScreenSize - 320*200 div 8 - I; {размер видеобуфера CGA в словах - 1} OfsOddLines - 4096; {смещение в видеобуфере CGA нечетных строк растра}
LintSize ■ 40; {размер строки растра видеобуфера CGA в словах} MaxLine * 199; {число строк растра в видеобуфере CGA - 1} var
R    : array [0..MaxLine, O.XineStze} of word;
Screen    ; array iO..ScreenSizej of word Absolute
ScreenSeg:0000; procedure Begin_Fill_Map;
{Обеспечивает инициализацию массива R, предназначенного для записи переключателей аппарата заполнения.} var
у    : integer,
i    : byte;
begin
for у О то MaxUne do    1
for i :»0 to LineSize do
R [y, i] 0;
end; { Begin_Fil1_Map }
procedure Draw_Boundary (xl,yi,x2,y2,color : initeger);
{Интерполирует отрезок прямой lxl,yl; x2,y2J, соответствующий границе карты. Параметр color должен соответствовать значению цвета отдельной области для абсолютных границ или поразрядной сумме по модулю 2 значений цветов двух смежных областей для относительных границ.}
var
х, у, dx, dy, direct, xstep. ystep : integer; procedure put_R (x, у : integer);
{Записывает переключатель заполнения, заданный переменной color, в элемент массива R, который соответствует координатам х и у.} var
i    : byte;
PixelColor : word; begin { put_R } i ; x div &;
PixelColor Swap (color shl (l4-(x and 7) * 2)); R ty, i] R [y, i] xor PixelColor ; end; { put_R }
begin { Draw_Boundary } x xl; xstep := 5; У yU ystep 1; if xl » x2 then begin
ж x2; у;» y2; x2 :«= xl; y2 yl;
end;
if у * y2 then ystep г" -1 dx (x2-x); dy abs (y2-y); if dx - 0
then direct -1 else direct 0; while not ((x * x2) and <y • y2)) do begin
if direct « 0 then begin
у у + ystep; direct := direct + dx;
end
else
begin
put_R (x, y): x x + xstep; direct direct - by;
end;
end;
end; { Draw_Boundary } procedure End_FiII_Map;
{Заполняет области, входящие в состав карты, путем сканирования массива R. Результат сканирования пересылается в видеобуфер дисплея.}
var
У, i    '. byte;
bedin {End_Filt_Map)
for у 0 to MaxLine - I do for i 0 to LineSize do
R [y + i, i] R [y, il xor R [у + I, il; for у 0 to MaxLine - 1 do
move (R [y, 0], Screen [(y div 2) » LineSize + byte(oddly)) * OfsOdd Lines],
LineSize * 2);
end; j End_Fm_Map)
END. {unit FMapCGA)
Пример использования процедур BeginFillMap, Draw Boundary и End_Fill_Map модуля FMapCGA приведен ниже в программе FILL_MAP. Эта программа служит для формирования изображения карты, представленной на рис. 7.
program FILL_MAP;
uses
Graph. FMapCGA;
const
Color! - [; Color2 - 2; Color3 - 3;
var
grDriver, grmode,
errorCode : integer;
BEGIN    { Mam )
grDriver :- CGAC2;
InitGraph (grDriver, grMode, 'c:\turbo5'); Bcgin_Fsll_Map;
Draw_Boundary <120 , 0, 240. 199, Colorl): Draw_Boundary <240, 199, 0, 199, Color2); Draw_Boundary ( 0. 199, 120 , 0, Color}); Draw_Boundary <120, 0, !20. 125. Colorl xoi Color3); Draw_Boundary (120, 125, 240, 199, Colorl xor Color2>: Draw_Boundary (120, 125, 0, 199, Color2 xor ColorJ); End_Fill_Map;
END. { Main )
В заключение остановимся на српоставлении примитива КАРТА ЗАПОЛНЕНИЯ с другими примитивами вывода, используемыми в существующих графических стандартах. КАРТУ ЗАПОЛНЕНИЯ прежде всего можно рассматривать как обобщение примитива ОБЛАСТЬ ЗАПОЛНЕНИЯ. При этом предлагается следующая "логика" обобщения. В стандарте GKS [1] область заполнения задается односвязной границей (см. рис. 8, а и 9, о), в проекте стандарта CGA [2] допускается использование нескольких односвязных границ при задании областей, имеющих полости или состоящих из нескольких изолированных подобластей. При этом отдельные элементы контура границы могут отображаться независимо от внутренней части области (см. рис. 8, б и 9, б). Если допустить возможность использования как абсолютных, так и относительных границ при задании плоских одноприоритетных
 


Обсудить вопрос в студенческом форуме

 

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