Во всех графических режимах видеопамять (ВП) организована как образ (подобие) растра экрана видеомонитора (ВМ). Это означает, что каждому пикселю графического экрана поставлена в соответствие некоторая ячейка ВП. Каждая ячейка хранит значения атрибута пикселя – информацию о яркости и цвете.
В растровой графике любой графический примитив (отрезок прямой, дуга окружности, любая аналитическая кривая, частично или целиком, в дальнейшем их будем называть векторами) моделируется на экране как последовательность точек в узлах сетки растра. При этом для каждой точки устанавливается адрес соответствующей ячейки ВП и туда записывается атрибут точки вектора. Таким образом, задача формирования видеокода вектора складывается из задачи нахождения точек в узлах сетки растра (моделирующих заданный вектор), вычислении соответствующих адресов ячеек ВП и записи по этим адресам атрибутов точек вектора.
Существует несколько способов построения растровых изображений векторов. Наиболее распространенный из них алгоритм Брозенхейма. Рассмотрим упрощенную модификацию такого алгоритма, который известен как метод оценочной функции.
Воспроизведение отрезка прямой линии. Поскольку точки растра формируются последовательно, то шаг в очередную точку можно рассматривать как движение по узлам сетки растра, а движущуюся точку будем называть изображающей точкой (ИТ). В дальнейшем будем изучать движение ИТ в xoy с шагом 1. Рассмотрим случай, когда отрезок задан в первой четверти (рис.1).
Уравнение прямой, на которой лежит заданный отрезок(A,B), имеет вид:
Ay – Bx=0.
Введем оценочную функцию таким образом: F(x, y)=Ay – Bx.
Оценочная функция обладает такими очевидными свойствами:
F(x, y) = 0, если точка (x, y) лежит на прямой;
F(x, y) > 0, если точка (x, y) выше прямой;
F(x, y)< 0, если точка (x, y) ниже прямой.
Движение ИТ должно сводиться к последовательному прохождению через узлы сетки, начиная с x=0, y=0, так, чтобы по возможности меньше отклоняться от заданной прямой и на определенном шаге движения попасть в точности в положение x=A, y=B. Такая задача получила в технических приложениях известность как задача интерполяции, а один шаг движения при этом реализуется одним циклом интерполяции. Решается эта задача использованием свойств F(x, y), из которых следует, что если в результате предыдущего шага ИТ оказалась в точке (x, y) то решение о следующем шаге следует принимать по правилам:
если F(x, y) < 0, то y:=y+1, делается шаг +1 по y;
если F(x, y) > 0, то x:=x+1, делается шаг +1 по x;
если F(x, y) = 0, то x:=x+1 при A³B; и y:=y+1 при A<B.
Движение начинается с начальными условиями x=0, y=0, F(x, y) =0 и заканчивается при x=A, y=B . После выполнения A+B циклов интерполяции ИТ окажется в точке (A,B).
Изложенный алгоритм предполагает вычисление F(x, y)в каждом цикле интерполяции. Эти вычисления могут выполняться следующим образом:
после шага равного +1 по координате X:
F(x+1, y)=Ay – B(x+1) = Ay – Bx – B = F(x, y) – B;
после шага равного +1 по координате Y:
F(x, y+1)= A(y + 1) – Bx = Ay + A – Bx = F(x, y)+A.
Воспроизведение дуги окружности. Рассмотрим случай, представленный на рис. 2, когда дуга окружности в 1-й четверти, движение осуществляется против часовой стрелки от (xH, yH) до (xK, yK).
F(x, y) = 0, если точка (x, y) лежит на окружности;
F(x, y) > 0, если точка (x, y) вне окружности;
F(x, y)< 0, если точка (x, y) внутри окружности.
Правила принятия решения об очередном шаге (для случая движения против часовой стрелки по дуге, заданной в первой четверти):
если F(x, y) < 0, то y:=y + 1, делается шаг +1 по y;
если F(x, y) > 0, то x:=x – 1, делается шаг –1 по x;
если F(x, y) = 0, то x:=x – 1 при x £ y и y:=y + 1 при x > y.
Движение начинается с начальными условиями x=xH, y=yH, F(x,y)=0 и заканчивается при x=xK, y=yK . Оценочная функция вычисляется в каждом цикле интерполяции по формулам:
F(x,y+1) = x2+(y+1)2 – R2 = F(x,y) +2y+1;
F(x–1,y) = F(x,y) – 2x+1.
Изложенный метод прост в реализации и позволяет обойтись только целочисленной арифметикой. Недостаток – необходимость в большом количестве модификаций алгоритма даже при воспроизведении одного вектора, но c разными начальными условиями.
Другой метод – метод цифровых дифференциальных анализаторов (ЦДА), основан на численном решении дифференциального уравнения движения точки по заданной кривой. Модель движения ИТ примем такой, как это показано на рис.3.
Описание движения ИТ по заданной кривой будет иметь вид:
xi+1 = xi+Dxi,
yi+1 = yi+Dyi,
i=1,2, ...,
x0=xн, y0=yн.
Один цикл движения назовем циклом интерполяции. На Dxi и Dyi наложим такое условие – за один цикл интерполяции результирующее движение должно быть: Dli £ 1. При выполнении данного условия теоретический шаг движения никогда не превысит единицы по каждой координате (следовательно, ни при каком цикле интерполяции не произойдет «перепрыгивания» через очередную точку растра).
Введем переменные Xi, Yi – это ближайшие целые значения координат точного положения движущейся точки после очередного цикла интерполяции, т.е. это координаты точек растра.
С учетом изложенного, модель движения по узлам сетки с единичными шагами будет иметь вид:
xi+1 = xi +Dxi,
Xi+1 = (int) xi+1,
yi+1 = yi +Dyi,
Yi+1 = (int) yi+1,
, при i=1,2, ..., x0=xн, y0=yн.
Операцию (int) yi+1 будем понимать как взятие ближайшего целого от yi+1.
Если реализуется указанная модель движения и циклы интерполяции выполняются с интервалом Dt = 1/F, то скорость движения ИТ по кривой будет v = 1/Dt =F, где F – частота выполнения циклов интерполяции.
Пусть кривая задана уравнением в неявной форме F(x,y)=0,а v есть скорость движения ИТ по этой кривой. Если F(x,y)=0, то и
.
Очевидно, что
, или , ,
где , , обращают в нуль левую часть уравнения при всех (x,y), удовлетворяющих F(x,y)=0. Следовательно получены дифференциальные уравнения движения по кривой F(x,y)=0, а k – произвольный коэффициент, задающий направление и скорость движения.
При малых Dt возможен переход к конечным разностям
и .
Тогда , . Для выбора Dt примем, что , т.е.
, , .
Приведем возможную реализацию этого метода на примере окружности. Уравнение окружности в форме F(x,y)=0 имеет вид:
F(x,y) = x2 + y2 – R2.
При этом , , . Тогда
Изложенный алгоритм обеспечивает воспроизведение участка кривой длинной Dli = 1 за один цикл интерполяции. При частоте интерполяции F вектор строится со скоростью v = F ед./сек. Изменяя F, можно управлять скоростью построения вектора. Для этого положим , что соответствует и . Выберем , где m – наименьшее целое, для которого выполняется , т.е. . Тогда , . В этом случае, простота вычислений внутри цикла интерполяции делает этот алгоритм более эффективным.
– за один цикл интерполяции результирующее движение должно быть: Dli £ 1. При выполнении данного условия теоретический шаг движения никогда не превысит единицы по каждой координате (следовательно, ни при каком цикле интерполяции не произойдет «перепрыгивания» через очередную точку растра).
и
.
, 
или 
, 
,
, 
, обращают в нуль левую часть уравнения при всех (x,y), удовлетворяющих F(x,y)=0. Следовательно получены дифференциальные уравнения движения по кривой F(x,y)=0, а k – произвольный коэффициент, задающий направление и скорость движения.
и 
.
, 
. Для выбора Dt примем, что 
, т.е.
, 
, 
.
, 
, 
. Тогда
и 
. Выберем 
, где m – наименьшее целое, для которого выполняется 
, т.е. 
. Тогда 
, 
. В этом случае, простота вычислений внутри цикла интерполяции делает этот алгоритм более эффективным.