Генерация отрезков

Лекция №3.

Генерация отрезков

· два алгоритма ЦДА - цифрового дифференциального анализатора (DDA - Digital Differential Analyzer) для генерации векторов - обычный и несимметричный;

· алгоритм Брезенхема для генерации векторов;

· алгоритм Брезенхема для генерации ребер заполненного многоугольника с уменьшением ступенчатости.

Требования к изображению отрезка:

· точное позиционирование концов отрезка;

· отрезки должны выглядеть прямыми;

· яркость вдоль отрезка должна быть постоянной и не зависеть от длины и наклона;

· должны быть поддержаны требуемые атрибуты.


I  =

Ipix  /  Lpix

горизонтальный и

вертикальный отрезки

I  =

Ipix  /  (1.41Lpix)

диагональный отрезок

Методы улучшения аппроксимации:

· объективное улучшение аппроксимации - увеличением разрешения дисплея;

· субъективное улучшение аппроксимации - учет психофизиологических особенностей зрения (уменьшение размеров экрана, размывание резких границ).

Цифровой дифференциальный анализатор

Отрезок описывается уравнением:

dY

dX

=

Py

Px


ЦДА формирует дискретную аппроксимацию решения этого дифференциального уравнения.


Задается N - количество узлов аппроксимации отрезка и за N циклов вычисляются очередные координаты:

X0 =   Xn;     Xi+1 = Xi + Px/N.

Y0 =   Yn;     Yi+1 = Yi + Py/N.

Xi, Yi преобразуются в целочисленные значения.


Недостатки:
· точки могут прописываться дважды,

· нет предпочтительных направлений и отрезки кажутся некрасивыми.


 

Несимметричный ЦДА

По большей координате делается единичный шаг.


Для Px > Py (Px, Py > 0) X-координата увеличиается на 1 Px раз, при этом Y-координата Px раз увеличивается на Py/Px.



Проблема заключается в необходимости деления
(Py/Px) и сложения вещественных чисел.

Алгоритм Брезенхема построения векторов

Алгоритм средней точки. Вещественных операций нет.
Рис. а) и б). Пусть начальная точка (0,0).
Если PY / PX     0.5, то следующая точка (1,0).
Если PY / PX   >   0.5, то следующая точка (1,1).


X0 = Xn;    Y0 = Yn;    X1 = X0 + 1;      E1   =   

DY

DX

  -  

1

2

.

Возможны случаи:

E1 0

E1 > 0

ближайшая точка есть:

X1 = X0 + 1;

X1 = X0 + 1;

Y1 = Y0;

Y1 = Y0 + 1;

E2 = E1 + PY/PX;

E2 = E1 + PY/PX - 1.


Важен только знак E, поэтому домножим E на 2PX:

E1 = 2PY - PX

E1 0:

E2 = E1 + 2PY

E1 > 0:

E2 = E1 + 2(PY - PX)

Модифицированный алгоритм Брезенхема


а) генерация ребер без устранения ступенчатости;
б) точное вычисление интенсивности пикселов;
в) пикселы границы по модифицированному методу Брезенхема.

Построение ребра заполненного моногугольника с устранением ступенчатости.
Яркость пиксела ~ площади пиксела, попавшей внутрь многоугольника.


dy

-

отсекаемая часть пиксела по Y

t

-

тангенс угла наклона отрезка

Исходный алгоритм

Модифицированный

E   =   t  -  1/2

E'   =   E  +  (1-t)

-1/2     E     1/2

0     E'     1

E' - доля площади пиксела внутри многоугольника.


Алгоритм для случая 0      dY      dX:

X= x1;

Y= y1;

Px= x2 - x1;

Py= y2 - y1;

t= I*Py / Px;

E'= I/2;

E'max= I - I*Py / Px;

i= Px;

PutPixel(X, Y, t/2); /* Первая точка вектора */
while (i = i - 1 0) {
if (E' E'max) {
X= X + 1; Y= Y + 1; E' = E'- E'max;
} else X= X + 1;
E' = E'+ t;
PutPixel(X, Y, E'); /* Очередная точка */
}

Улучшение качества аппроксимации примитивов

· увеличение разрешения устройства вывода;
· уменьшение размеров устройства вывода;
· усреднение с понижением разрешения:

Iij = (k = 1ml = 1m   MklVk+(i-1)m, l+(j-1)m) / S,

i = 1, 2, 3 ;     j = 1, 2, 3

· "размывание" границ без понижения разрешения:

Iij = (k = 1ml = 1m   MklVk+i-i0-1, l+j-j0-1) / S,

m    нечетно,    i0 = j0 = (m-1)/2;

i = i0+1, i0+2, ;       j = j0+1, j0+2,


S = k = 1ml = 1m  Mkl



 

Подчеркивание границ

Для подчеркивания границ используется высокочастотная фильтрация исходного изображения с помощью масок вида:


Вычислительная процедура аналогична рассмотренной выше.

Генерация окружности

Координатное представление

X2 + Y2 = R2

Y =

  ______
R2 - X2
 

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

X = R cosf

Y = R sinf

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

X2 + Y2 = R2
min  Ei(Pi) = (Xi2 + Yi2) - R2


 
Pi(Xi, Yi) - очередной пиксел

Достаточно сгенерировать точки для 1/8 окружности


При генерации окружности по часовой стрелке после занесения пиксела (Xi, Yi) следующий пиксел может быть Pg, Pd или Pv


Для выбора возможного пиксела вычислим:

|Dg|

=

| (X+1)2

+

Y2

-

R2 |

|Dd|

=

| (X+1)2

+

(Y-1)2

-

R2 |

|Dv|

=

| X2

+

(Y-1)2

-

R2 |


В качестве очередного пиксела выберем тот, для которого |D| минимально


Dd < 0

-

диагональный  пиксел  внутри

(1-3)

Dd > 0

-

диагональный  пиксел  вне

(5-7)

Dd = 0

-

диагональный  пиксел  на

(4)


 

Случай Dd < 0

Выбор между возможными следующими пикселами Pg или Pd определяется разностью:

di

=

|Dg| - |Dd| =

|(X+1)2 + Y2 - R2| -

|(X+1)2 + (Y-1)2 - R2|.



0

-

выбор

Pg

>

0

-

выбор

Pd

Вычисление di. Варианты 2 и 3:


 
Так как Pg или вне или на
окружности, а Pd внутри, то
Dg 0;        Dd < 0.


Таким образом:
di = (X+1)2 + Y2 - R2 + (X+1)2 + (Y-1)2 - R2.
di = 2 ·[(X+1)2 + (Y-1)2 - R2] + 2·Y - 1.
di = 2 ·(Dd + Y) - 1

Вариант 1

Очевидно должен быть выбран пиксел Pg.
Dg < 0, Dd < 0 и |Dg| < |Dd| di < 0, т.е. по критерию di < 0 как и ранее д.б. выбран Pg, что верно.


 

Случай Dd > 0

Выбор между возможными следующими пикселами Pd или Pv определяется разностью:

si

=

|Dd| - |Dv| =

|(X+1)2 + (Y-1)2 - R2| -

|X2 + (Y-1)2 - R2|



0

-

выбор

Pd

>

0

-

выбор

Pv

Вычисление si. Варианты 5 и 6:


 
Так как Pd вне, а Pv или
внутри или на окружности, то
Dd > 0;        Dv 0.


Таким образом:
si = (X+1)2 + (Y-1)2 - R2 + X2 + (Y-1)2 - R2;
si = 2 ·[(X+1)2 + (Y-1)2 - R2] - 2·X - 1;
si = 2 ·(Dd - X) - 1.

Вариант 7

Очевидно должен быть выбран пиксел Pv.
Dd > 0, Dv > 0 и |Dd| > |Dv| si > 0, т.е. по критерию si > 0 как и ранее д.б. выбран Pv, что верно.

Случай Dd = 0


di:  

Dg > 0;    Dd = 0;    
по критерию di > 0 выбираем Pv

si:  

Dd = 0;    Dv < 0;    
по критерию si 0 выбираем Pv

Итак:

Dd < 0:

di 0 - выбор горизонтального пиксела Pg

di > 0 - выбор диагонального пиксела Pd

Dd > 0:

si 0 - выбор диагонального пиксела Pd

si > 0 - выбор вертикального пиксела Pv

Dd = 0:

выбор диагонального пиксела Pd.

Рекуррентные соотношения для вычисления Ddi+1

  1. Для горизонтального шага к Xi+1, Yi
    Xi+1 = Xi + 1;     Yi+1 = Yi;
    Ddi+1 = (Xi+1+1)2 + (Yi+1-1)2 - R2 =
    (Xi+1)2 + (Yi-1)2 - R2 + 2·Xi+1 + 1 =
    Ddi + 2·Xi+1 + 1;
  2. Для диагонального шага к Xi+1, Yi-1
    Xi+1 = Xi + 1;    Yi+1 = Yi - 1;
    Ddi+1 = Ddi + 2 ·Xi+1 - 2 ·Yi+1 + 2;
  3. Для вертикального шага к Xi, Yi-1 Xi+1 = Xi;    Yi+1 = Yi - 1;
    Ddi+1 = Ddi - 2 ·Yi+1 + 1;
  4. Начальная инициализация
    X = 0;    Y = R;
    Dd = (X+1)2 + (Y-1)2 - R2 = 1 + (R-1)2 - R2 = 2*(1 - R)

Генерация отрезков