Алгоритмы растеризации отрезков, окружностей и эллипсов

|x-x0|+|y-y0|=1

max{|x-x0|, |y-y0|}=1

(рис 3.1) Цифровой дифференциальный анализатор.(рис 3.4) Цифровой дифференциальный анализатор// Координаты концов отрезка - (0,0) и (a,b)

e = b/a; // Текущая ордината
delta_e = b/a; // Приращение ординаты

// (x,y) - Координаты текущей точки
x = 0; y = 0;

while( x < a )
{
      plot(x, y);

      if( e > 1/2 )
      {
            // d : диагональное смещение
            x++; y++;

            // т.к. произошло смещение по y на 1 вверх
            e += delta_e - 1;
      }
      else
      {
            // s : горизонтальное смещение
            x++;
            e += delta_e;
      }
}

Алгоритм Брезенхема

Брезенхем [16] модифицировал алгоритм DDA, чтобы он работал в целых числах. Модифицируем алгоритм следующим образом:

уменьшим везде e на $$\frac{1}{2}$$, чтобы сравнивать с 0 ;

домножим e и $$\Delta e$$ на 2a: e0 = 2b - a, $$\Delta e = 2b$$

Приходим к следующему алгоритму:

// Координаты концов отрезка - (0,0) и (a,b)
e = 2b - a;
delta_eS = 2b;
delta_eD = 2b - 2a;

x = 0; y = 0; // (x,y) - Координаты текущей точки

while(x < a)
{
      plot(x, y);

      if(e > 0)
     { // d : диагональное смещение
            x++; y++;
            e += delta_eD;
      }
      else
      { // s : горизонтальное смещение
            x++;
            e += delta_eS;
      }
}

Алгоритм Брезенхема был создан им для вывода отрезков на цифровых инкрементальных графопостроителях, которые могли осуществлять лишь простые единичные сдвиги печатающей головки. Дальнейшая оптимизация может быть произведена, если заметить, что отрезок симметричен относительно прямой, проходящей перпендикулярно ему через его середину; в этом случае можно начинать рисовать сразу с двух концов, что сократит число итераций цикла в алгоритме вдвое.

Алгоритм Кастла-Питвея

Этот алгоритм гораздо менее эффективен с вычислительной точки зрения, чем алгоритм Брезенхема, однако обладает красивой математической структурой. Он основан на идее, схожей с известным алгоритмом Евклида нахождения Наибольшего Общего Делителя двух натуральных чисел [19].

Будем работать со строками, кодирующими последовательность закраски (т.е. состоящими из символов s и d, определенных выше).

Определим две операции над такими строками:

$$\oplus$$ - конкатенация строк, например

$$"ssds" \oplus "sddd " = "ssdssddd "$$

$$\sim$$ - "переворот" строки, например

$$\sim ("ssdds") = "sddss"$$

// Координаты концов отрезка - (0,0) и (a,b)
y = b;
x = a - b;

m1 = "s";
m2 = "d";

while( x \ne y )
{
      if( x > y )
      {
            x = x - y;
            m2 = m1 (+)  ~ m2; 
      }
      else
      {
            y = y - x;
            m1 = m2  (+)  ~ m1; 
      }
}

После завершения работы алгоритма $$m = m_2\oplus \sim m_1$$ задает нужную последовательность сдвигов. Доказательство корректности работы этого алгоритма мы опустим ввиду его громоздкости.

3.3. Изображение отрезка с нецелочисленными координатами концов

Для отрезка с нецелочисленными координатами концов будем строить соответствующую 4-связную линию на растре.

(рис 3.5) Рисование отрезка с нецелочисленными координатами концов.

Существует два подхода.

Округлить координаты концов до целочисленных и воспользоваться алгоритмом для целочисленного случая. Недостаток: может вызывать существенные искажения (особенно в случае отрезков небольшой длины).

Перейдем к нашему каноническому случаю, который теперь характеризуется тем, что отрезок лежит в первом октанте, но координаты $$A(x_A, y_A)$$ в этом случае: $$x_A \in [0, 1), y_A \in [0, 1)$$. Параметризуем наш отрезок стандартным образом:$$(x, y) = A + t \cdot \frac{B-A}{c}, t \in [0, c],$$

где A и B - концевые точки, c > 0 - некий масштабный коэффициент. Сделаем c достаточно большим целым числом, чтобы уменьшить ошибки округления. Тогда рассмотрим

$$\Delta h = \frac{c}{x_B-x_A}$$ - приращение t, при сдвиге на 1 пиксель по x ;

$$\Delta v = \frac{c}{y_B-y_A}$$ - приращение t, при сдвиге на 1 пиксель по y.

Будем сравнивать текущие значения h и v, а затем, в зависимости от этого, делать шаг по x или y и придавать соответствующие приращения h и v. Алгоритм закончится, когда h или v превысит c.

(рис 3.4) Изменение параметров h и v.(рис 3.6) Алгоритм отображения отрезка с нецелочисленными координатами концовx = 0; y = 0; // Канонический случай: начальная точка
// лежит в [0, 1) (+)  [0, 1)

/* Приращения t, соответствующие смещениям от начальной
точки до границ первого пикселя. */

h = delta_h * (1 - xA); // delta_h0
v = delta_v * (1 - yA); // delta_v0

while( (h < c) AND (v < c) )
{
       plot(x, y);
   
       if( h < v )
       {
            // Сдвиг по горизонтали
            x++; h += delta_h;
       }
       else if( h > v )
      {
            // Сдвиг по вертикали
            y++; v += delta_v;
       }
       else
      {
            // h = v : Вырожденный случай (см. рис. 3.5)
            // рисуем произвольный из двух возможных пикселей,
            // например, верхний:
            plot(x,y+1);
            x++; y++;
            h += delta_h; v += delta_v;      
      }
}

Замечание. Приведенный выше алгоритм легко обобщается на n -мерный случай.

3.4. Изображение окружностей

Для начала перейдем к канонической системе координат, в которой центр окружности совпадает с началом координат. Тогда можно заметить, что в силу симметрии окружности относительно прямых, разделяющих октанты, достаточно построить растровое представление в одном октанте, а затем с помощью симметрий получить изображения в других октантах (см. рис. 3.7). Будем пользоваться заданием окружности в виде неявной функции: x2 + y2 - R2 = 0.

(рис 3.7) Симметрии при изображении окружности.

Пусть f(x, y) = x2 + y2 - R2. Будем рисовать часть окружности в 4 -м октанте, начиная с точки (-R, 0) (см. рис. 3.7, показано стрелкой).

Пусть $$R \in \mathbb{N}$$, тогда $$f(x, y) \in \mathbb{Z} \text{ для } x \in \mathbb{Z}, y \in \mathbb{Z}$$. Пусть функция plot8(x, y) отображает на растре все 8 точек, полученных из (x, y) с помощью симметрий.

Алгоритм Брезенхема

Будем рассуждать подобно алгоритму Брезенхема для отрезков (с соответствующими поправками на 4 -й октант) [17]. Из двух возможных пикселов в 4 -м октанте (соответствующих вертикальному и диагональному смещениям, которые обозначаются аналогично прежним s и d, см. рис. 3.10) будем выбирать тот, расстояние от окружности до которого меньше.

(рис 3.8) Расстояния до окружности.

Для того чтобы выбрать один из двух возможных пикселей, будем сравнивать расстояния от них до окружности: где расстояние меньше - тот пиксел и будет искомым. В примере на рис. 3.8 сравниваются расстояния от точек S(xs, ys) и D(xd, yd) до окружности с радиусом R. Из евклидовой метрики получаем:

$$\Delta R_s = \sqrt{x_s^2 + y_s^2} - R; \\ \Delta R_d = R -\sqrt{x_d^2 + y_d^2}.$$

Но вычисление квадратного корня - вычислительно трудоемкая операция, поэтому при достаточно больших R мы будем заменять сравнение расстояний сравнением приближенных значений их квадратов (см. рис. 3.9):

$$(\Delta R_s)^2-(\Delta R_d)^2 = x_s^2 + y_s^2 - 2R\sqrt{x_s^2 + y_s^2}+R^2 - x_d^2 - y_d^2 + \\+ 2R\sqrt{x_d^2 + y_d^2} - R^2.$$ (рис 3.9) Приближенное сравнение расстояний.

Уменьшим два слагаемых на приблизительно одинаковые величины:

$$- 2R\sqrt{x_s^2 + y_s^2}$$ заменим на $$-2R \cdot R$$,

$$+ 2R\sqrt{x_d^2 + y_d^2}$$ заменим на $$+2\sqrt{x_d^2 + y_d^2} \cdot \sqrt{x_d^2 + y_d^2}$$

получим

$$(\Delta R_s)^2-(\Delta R_d)^2 \approx x_s^2 + y_s^2 - 2R \cdot R + R^2 - \\ - x_d^2 - y_d^2 + 2\sqrt{x_d^2 + y_d^2} \cdot \sqrt{x_d^2 + y_d^2} - R^2 = \\ = x_s^2 + y_s^2 + x_d^2 + y_d^2 - 2R^2.$$

Таким образом, приближенно

D ближе к окружности, чем S $$\Leftrightarrow$$$$x_s^2 + y_s^2 + x_d^2 + y_d^2 - 2R^2 > 0;$$

S ближе к окружности, чем D $$\Leftrightarrow$$$$x_s^2 + y_s^2 + x_d^2 + y_d^2 - 2R^2 < 0.$$

(рис 3.10) Алгоритм Брезенхема для окружности.

Пусть (x, y) - текущий пиксель. Обозначим

$$F_s = f(x, y + 1) = x^2 + {(y + 1)}^2 - R^2 > 0, \\ F_d = f(x + 1, y + 1) = {(x + 1)}^2 + {(y + 1)}^2 - R^2 < 0, \\ F = F_s + F_d;$$

$$\Delta F(s) = ( \Delta F \text{ при переходе }s\colon (x, y) \to (x, y + 1) ) = \\ = f(x, y + 2) + f(x + 1, y + 2) - f(x, y + 1)- \\ - f(x + 1, y + 1)\\ = 4y + 6,$$

$$\Delta F(d) = ( \Delta F \text{ при переходе } d\colon (x, y) \to (x + 1, y + 1) ) = \\ = f(x + 1, y + 2) + f(x + 2, y + 2) - f(x, y + 1)- \\ - f(x + 1, y + 1) \\ = 4x + 4y + 10.$$

Тогда из двух возможных смещений d и s выберем.

$$F = F_s + F_d < 0 \Leftrightarrow F_s < -F_d$$, т.е. (x + 1, y + 1) ближе к окружности, чем (x, y + 1):

d: Переходим в (x + 1, y + 1) и придаем соответствующие приращения F, $$\Delta F(s)$$, $$\Delta F(d)$$:

$$F = F +\Delta F(d); \Delta F(s) = \Delta F(s)+4; \Delta F(d) = \Delta F(d)+8.$$

$$F = F_s+F_d < 0 \Leftrightarrow F_s < -F_d$$, т.е. (x, y+1) ближе к окружности, чем (x + 1, y + 1):

s: Переходим в (x, y + 1) и придаем соответствующие приращения F, $$\Delta F(s)$$, $$\Delta F(d)$$:

$$F = F +\Delta F(s); \Delta F(s) = \Delta F(s)+4; \Delta F(d) = \Delta F(d)+4.$$

Если мы начинаем из (-R, 0), то начальные значения будут следующими:

$$F = F_s + F_d = ({(-R)}^2 + 1^2 - R^2) + ({(-R + 1)}^2 + 1^2 - R^2) \\ = 1 + (-2R + 1 + 1) = 3 - 2R, \\ \Delta F(s) = 4 \cdot 0 + 6 = 6, \\ \Delta F(d) = 4 \cdot (-R) + 4 \cdot 0 + 10 = 10 - 4R.$$

Легко видеть, что в алгоритме все величины, связанные с F, кроме F начального, будут кратны 2. Но, если мы поделим все эти величины на 2 (в дальнейшем значения всех величин уже понимаются в этом смысле), то $$F_{нач} = \frac{1}{2}+1-R$$. Так как приращения F могут быть только целочисленными, то $$F = \frac{1}{2} +T$$, где $$T \in \mathbb{Z}$$ ; т.е. если отнять $$\frac{1}{2}$$ от всех значений, то знак F не изменится для всех T, кроме T = 0. Для того чтобы результат сравнения остался прежним, будем считать, что F = 0 теперь соответствует смещению s.

x = -r; y = 0;

F = 1-r;
delta_Fs = 3;
delta_Fd = 5-2*r;

while( x + y < 0 )
{
      plot8( x, y );

      if( F > 0 )
      {
            // d: Диагональное смещение
            F += delta_Fd;
            x++; y++;
            delta_Fs += 2;
            delta_Fd += 4;
      }
      else
      {
            // s: Вертикальное смещение
            F += delta_Fs;
            y++;
            delta_Fs += 2;
            delta_Fd += 2;
      }
}

Размерность вычислений этого алгоритма (т.е. отношение максимальных модулей значений величин, с которыми он оперирует к модулям исходных данных (в данном случае R )) равна 2.

3.5. Изображение эллипсов

Прежде всего отметим, что у эллипса, в отличие от окружности, всего 2 оси симметрии, поэтому по точкам придется строить уже 2 октанта (см. рис. 3.11).

(рис 3.11) Изображение эллипса.

Построение по неявной функции

Будем рассуждать подобно алгоритму Брезенхема для окружностей.

Неявная функция, задающая эллипс, имеет вид

$${{\left( \frac{x}{a} \right)}^2 + {\left( \frac{y}{b} \right)}^2 -1 = 0, a > b}\\ {b^{2x2} + a^{2y2} - a^{2b2} =0}$$

Введем f(x, y) = b2x2 + a2y2 - a2b2.

Аналогично алгоритму для окружности можно сравнивать f для двух возможных вариантов. Подробный вывод оставляем читателю в качестве упражнения.

Построение путем сжатия окружности

Воспользуемся тем, что эллипс с параметрами a, b (пусть a > b ) получается из окружности радиуса a сжатием по оси y в a/b раз. Построим алгоритм, который является некой комбинацией алгоритмов Брезенхема для окружности и для отрезка (см. рис. 3.12).

(рис 3.13) Построение эллипса путем сжатия окружности.(рис 3.12) Смешанная связность.

Начнем из точки (a, 0) на окружности и из точки (0, 0) на отрезке. Будем строить эллипс точно так же, как окружность, но смещать текущую точку по y только в том случае, когда такое смещение происходит в текущем шаге уже для отрезка, т.е. построение отрезка как раз и является реализацией сжатия в a/b раз (точнее, его дискретной аппроксимацией). Этот алгоритм тоже имеет недостаток: возможная смешанная связность полученной линии (см. рис. 3.13).