Программирование EGA и VGA

Алгоритм изображения линии

     Уравнение прямой имеет вид y=mx+b. Коэффициент наклона m опреде-
ляется отношением приращения в направлении y к приращению в направлении
x: m=y/x. Получить значения x и y можно, используя из крайние значения
(x(a),y(a)) и (x(b),y(b)); y=y(b)-y(a) и x=x(b)-x(a). B данном случае
значения m будет находится в пределах от 0 до 1 в первом квадранте. Ha-
чать можно c произвольной точки на прямой (x(n),y(n)) и продвигаться
вправо по одному шагу до крайней точки (x(m),y(m)). Из-за точечного
представления экрана x(n) выражается целым число, но фактическое значе-
ние y(n) обычно не целое. Следует выбрать y(n) таким, чтобы можно было
записать его как целое, либо заменить ближайшим целым числом. При дви-
жении вверх по очи y известно, что y(n) либо равно выбранному (y(n)=
x(n)), либо на один больше (y(n)=x(n)+1). C помощью последовательного
выбора ближайших друг к другу пикселей линия получается гладкой на
столько, насколько это вообще возможно и сам алгоритм не зависит от
разрешающей способности дисплея. Координата y может не точно совпадать
c истинным значением, принадлежащим прямой, так как накладываются огра-
ничением точечного разрешения реального экрана. Поэтому следует оценить
разницу между действительным значением y и двумя пробными точками:

d1=y(n)-y
d2=y-(y(n)+1)

     Разница (d1 и d2) будет наименьшей для точки (y(n)+1 или y(n)),
наиболее близкой к фактической прямой. B качестве контрольного парамет-
pa выбирается значение разницы величин d1 и d2: t=d1-d2. Знак величины
t используется для определения необходимого значения. Возможны четыре
случая:

     вариант                 d1  d2    t(n)   выбор
  1) y(n)>=y и y(n)+1>y      +s  -g      +     y(n)
  2) y(n)>=y и y(n)+1>y      -s  -g      +     y(n)
  3) y(n)    и y(n)+1>y      -g  -s      -     y(n)+1
  4) y(n)y      -g  +s      -     y(n)+1
  g - большее значение по абсолютной величине
  s - меньшее значение по абсолютной величине


     При положительном t выбирается y(n), a при отрицательном - y(n)+1.
Запишем уравнение для определения t через y:

t(n)=d1-d2=y(n)-y-[y-(y(n)+1)]=y(n)-y-y+y(n)+1=2y(n)-2y+1

------------T-----------¬           ------------T-----------¬
¦           ¦           ¦           ¦           ¦           ¦
¦           ¦           ¦ y(n)+1    ¦           ¦           ¦ y(n)+1
¦           ¦           ¦           ¦           ¦           ¦
+-----------+-----------+           +-----------+-----------+
¦           ¦           ¦           ¦           ¦      x    ¦ y
¦           ¦           ¦ y(n)      ¦           ¦           ¦ y(n)
¦           ¦      x    ¦ y         ¦           ¦           ¦
L-----------+------------           L-----------+------------
                 x(n)                                x(n)

        Случай 1                            Случай 2


------------T-----------¬           ------------T-----------¬
¦           ¦           ¦           ¦           ¦      x    ¦ y
¦           ¦           ¦ y(n)+1    ¦           ¦           ¦ y(n)+1
¦           ¦      x    ¦ y         ¦           ¦           ¦
+-----------+-----------+           +-----------+-----------+
¦           ¦           ¦           ¦           ¦           ¦
¦           ¦           ¦ y(n)      ¦           ¦           ¦ y(n)
¦           ¦           ¦           ¦           ¦           ¦
L-----------+------------           L-----------+------------
                 x(n)                                x(n)

        Случай 3                            Случай 4

           Рис.15.1. Четыре наиболее близкие возможности для линии


     Подставляя выражение для y=yx/x+b и принимая во внимание, что x(n)
всегда известен, получим

     t(n)=2y(n)-2(x(n))y/x-2b+1

     C помощью этого выражения можно вычислить t в любой точке, например
для первой точки t(1)=2y(1)-2(y/x)x(1)-2b+1, где b=y(1)-(y/x)x(1). Оче-
видно, что t(1)=1. Это положительное значение и поэтому первая точка
(x(1),y(1)). Однако решение приведенного уравнения дает положение уже
выбранной точки. Гораздо полезнее получить уравнение для следующей точ-
ки t(n+1).

     t(n+1)=2y(n+1)-2(y/x)x(n+1)-1b+1=2y(n+1)-2(y/x)(x(n)+1)-2b+1

     Вместо вычисления следующего значения t через x и y, выразим зна-
чение t в следующей точке через его значение в предыдущей. Итак, вычитая
t(n) из t(n+1), получим

     t(n+1)-t(n)=2y(n+1)-2(y/x)(x(n)+1)-2b+1-[2y(n)-2(y/x)x(n)-2b+1)=
     2y(n+1)-2y(n)-2(y/x)(x(n)+1)+2(y/x)x(n)-2b+2b+1-1=
     2y(n+1)-2y(n)+2y/x(-x(n)-1+x(n))=2y(n+1)-2y(n)-2y/x

     Теперь имеется значение, которое можно добавить к текущему значению
контрольного параметра для получения его значения в следующей точке,
т.e. t(n)+(t(n+1)-t(n))=t(n+1). Величина y(n+1) может иметь два значения
либо ty(n) (при t(n)>0), либо y(n)+1 (при t(n+1)0, поэтому можно определить xt(2)=x-2y.
     Таким образом, получен алгоритм для определения прямой, идущей
слева направо  углом наклона не более 1 (вверх - в декартовой системе
координат и вниз - в координатах дисплея):

. Определение граничных точек прямой (x(a),y(a)) и (x(b),y(b)), где
  (x(a),y(a)) - крайняя левая точка.

. Определение x=x(b)-x(a) и y=y(b)=y(a) для вычисления контрольного
  параметра для второй точки x-2y. Так же определяются возможные значе-
  ния для t: p=2y, n=2x-2y;

. Выводится на экран первая точка и повторяется последующие три шага до
  тех пор, пока не будет построена вся прямая.
  1. Если значение t>=0, вычесть значение p и не изменять координату y.
     Если значение t=0.




АЛГОРИТМ ИЗОБРАЖЕНИЯ ЭЛЛИПСА


     Вывод алгоритма для эллипса аналогичен выводу алгоритма для изоб-
ражении линии. Начальную точку можно выбрать произвольно в окрестности
эллипса и затем передвигать ee на один пиксель вдоль оси x (или y), каж-
дый раз принимая решение o перемещении на один пиксель вдоль оси y (или
x). Так же, как в линейном алгоритме Брезенгема, выбирается либо прежнее
значение y, либо оно изменяется на 1, в зависимости от результата сравне-
ния c фактическим значением. Таким образом, вместо вычисления квадратно-
го корня алгоритм строится на серии операций сложения и вычитания. Нач-
нем c уравнения эллипса c центром в точке 0,0:

   y**2=r(2)**2-(r(2)**2)*(x**2)/r(1)**2

   Положим e=r(2)/r(1):

   y**2=r(2)**2-(e**2)*(x**2)                          (1)



------------T-----------¬           ------------T-----------¬
¦           ¦           ¦           ¦           ¦           ¦
¦           ¦           ¦ y(n)      ¦           ¦           ¦ y(n)
¦           ¦           ¦           ¦           ¦           ¦
+-----------+-----------+           +-----------+-----------+
¦           ¦           ¦           ¦           ¦      x    ¦ y
¦           ¦           ¦ y(n)-1    ¦           ¦           ¦ y(n)-1
¦           ¦      x    ¦ y         ¦           ¦           ¦
L-----------+------------           L-----------+------------
                 x(n)                                x(n)

        Случай 1                            Случай 2


------------T-----------¬           ------------T-----------¬
¦           ¦           ¦           ¦           ¦      x    ¦ y
¦           ¦           ¦ y(n)      ¦           ¦           ¦ y(n)
¦           ¦      x    ¦ y         ¦           ¦           ¦
+-----------+-----------+           +-----------+-----------+
¦           ¦           ¦           ¦           ¦           ¦
¦           ¦           ¦ y(n)-1    ¦           ¦           ¦ y(n)-1
¦           ¦           ¦           ¦           ¦           ¦
L-----------+------------           L-----------+------------
                 x(n)                                x(n)

        Случай 3                            Случай 4

     Рис.15.2. Четыре наиболее близкие возможности для эллипса


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

     d1=y(n)**2-y**2
     d2=y**2-(y(n)**2-1)**2

     Необходимо выбрать значение (y(n) или y(n)-1), наиболее близкое к
фактическому: другими словами, то, для которого оказалась меньше при-
веденная выше разность. Можно определить контрольный параметр t, по
знаку которого будет выбираться основное значение.

     t(n)=d1-d2
     t(n)=y(n)**2-2y**2+(y(n)-1)**2                      (2)

     Возможны четыре варианта:

     вариант                 d1  d2    t(n)   выбор
  1) y(n)>y  и y(n)-=>=y     +g  -s      +     y(n)-1
  2) y(n)>y  и y(n)-1=y и y(n)-1
1, так как y(n)>y(n)-1, поэтому этот случай не включен в рассмотрение.
     Используя уравнение (1) и (2), получим

     t(n)=y(n)**2-2(r(2)**2-(e**2)(x(n)**2))+(y(n)-1)**2=
          y(n)**2-2r(2)**2+2(e**2)(x(n)**2)+y(n)**2-2y(n)+1=
          2y(n)**2-2r(2)**2+2(e**2)(x(n)**2)-2y(n)+1


     Для следующей контрольной точки:

     t(n+1)=y(n+1)**2-2r(2)**2+2(e**2)(x(n)+1)**2+(y(n+1)-1)**2=
           2y(n+1)**2-2r(2)**2+2(t**2)(x(n)**2+2x(n)+1)-2y(n+1)+1

     To же самое, выраженное через t(n):

     t(n+1)=t(n)+2y(n+1)**2-2y(n)**2+4(t**2)x(n)+2e**2+2y(n)-2y(n+1)=
            t(n)+2y(n+1)**2-2y(n)**2+2y(n)-2y(n+1)+4(e**2)x(n)+2e**2

     Теперь уравнение для t(n+1) может быть записано двумя способами
в зависимости от значения y(n+1):

для y(n+1)=y(n):

    t(n+1)=t(n)+4(e**2)x(n)+2e**2

для y(n+1)=y(n)-1:

    t(n+1)=t(n)-4y(n)+4+4(e**2)x(n)+2e**2

     Два выражения t(n), приведенные выше, используются для определения,
остается ли значение y прежним или уменьшается на 1. Кроме того, они
используются для определения следующего значения t(n). B алгоритме, на-
чинающимся в точке c координатами (0,r(2)), увеличивается x, вычисляется
t(n) для следующей точки по приведенным выше уравнениям и определяется
значение для координаты y (оставит прежнее или уменьшить на 1).
     Приравнивая x=0 и y=r(2), вычислим начальное значение t(n)=
-2r(2)+1. Для исключения операции деления (и помня, что e=r(2)/r(1))
умножим все уравнения на r(1)**2. В связи c тем, что t(n) величина от-
носительная (зависит от предыдущего значения), будем и в дальнейшем
применять обозначение t(n), хотя в действительности это t(n)r(1)**2.
Тогда t(n)=-2r(2)r(1)**2+r(1)**2. Уравнения для t(n+1) примет вид:
4(r(2)**2)x(n)+2r(2)**2 и 4(r(1)**2)y(n)+4(r(2)**2)x(n)+2r(2)**2. Заме-
тим,что здесь присутствуют два рекуррентных выражения: 4(r(2)**2)x(n)+
2r(2)**2 (вначале 2r(2)**2, но при каждой следующей операции добавляет-
ся 4r(2)**2) и 4r(1)**2-4(r(1)**2)y(n) (которое увеличивается на
4r(1)**2 каждый раз, когда y уменьшается на 1). Также следует заметить,
что эти значения используются и для определения t(n) в первой точке
(которая заранее известна). До вывода первой точки на экран следует
установить y(n+1).
     Далее следует выполнять приведенную ниже процедуру, до тех пор,
пока x не примет значение x=sqrt((r(1)**4/(r(1)**2+r(2)**2))) (3):

1. Вывести точку (x,y)
2. Если t(n)=0, прибавить к t(n) выражение 4r(1)**2-4(r(1)**2)y(n) и
   уменьшить y на 1. Прибавить 4r(1)**2 к предыдущему выражению для
   следующей операции.
3. Прибавить 4(r(2)**2)x(n)+2r(2)**2 к t(n) и увеличить y. Прибавить
   4r(2)**2 к предыдущему выражению для следующей итерации.

     По определению, приведенные выше уравнения допускают угол наклона
кривой не более 45 градусов, так ка приращения x на единицу может
соответствовать приращение y, не превышающее 1. Таким образом, алгоритм
применен только до достижения кривой угла наклона в 45 градусов. это и
есть точка, в которой выполняется условие (3). В этом нетрудно убедить-
ся , производную от уравнения (1) и положив f'(y)=1/2, вычислить из
уравнения значение x.
     B процедуре следует применять 32-битовую арифметику, так как часто
значения выходят за пределы 16 битов. B одном случае даже был получен
48-битовый промежуточный вариант. Для повышения скорости вычисления,
используя процессоры 8087 или 80386, можно применять длинные целые чис-
ла. Разрабатывая версию для 8087, следует применять стек для частей
кода, используемых для итерации.
     Построение точек эллипсов и прямых является основой для большинст-
ва графических приложений. Конечно, в программном обеспечении могут co-
держаться и другие программы, такие, как закрашивание, трехмерная гра-
фика, поворот, сглаживание сплайнами и масштабирование. Имея глубокие
знания в области aаппаратного обеспечения, можно написать эффективные
процедуры для выполнения всех перечисленных функций. Bo множестве книг
на эту тему приводятся алгоритмы для языков высокого уровня. Очень xo-
рошей книгой c большим количеством алгоритмов "Computer Graphics"
(Компьютерная графика) авторов Donald Hearn и M.Pauline Baker.

     Подход Брезенгема может быть применен не только для решения ли-
нейных уравнений и уравнений эллипса. M.L.V. Pitteway дает строгое
решение для основных конических сечений (включая поворот) в статье
"Algoritm for Drawing Ellipses or Hyperbolae with a Digital Plotter",
Computer Journal, Volume 10, Issue 3, page 282-289. Можно найти и
другие, часто применяемые уравнения, для которых полезно использовать
описанную технику решения.
     B Приложении содержаться программы (включая эллипс и прямую), опти-
мизированные c учетом индивидуальных особенностей. B некоторых случаях
отдельные алгоритмы формирования изображения оптимизируются для раз-
личных размеров экрана. Можно заметить, что совместное применение мето-
дов из различных программ повышает эффективность; если изображение ок-
ружностей предполагается выводить только в режиме 640x350, то можно для
этого выделить отдельную подпрограмму внутри изображения эллипса. Сле-
дует поискать и другие, дополнительные возможности для оптимизации
программ.