16. Алгоритм вывода окружности

Для вывода контура круга можно использовать соотношение между координатами X и Y для точек окружности X²+Y²=R² и построить алгоритм прямого вычисления координат. Однако в этом случае необходимо вычислять квадратный корень (как элемент бесконечной последовательности приближений).

Приведем запись инкрементного алгоритма Брезенхэма:

r2:=radius*radius;

dst:=4*r2;

dxt:=radius/1.414213562373;

t:=0;

s:=-4*r2*radius;

e:=(-s/2)-3*r2;

ca:=-6*r2;

cd:=-10*r2;

x:=0; y:=radius;

Закрасить пиксел (xc,yc+radius);

Закрасить пиксел (xc,yc-radius);

Закрасить пиксел (xc+radius,yc);

Для indx от 1 до dxt с шагом 1:

x:=x+1;

Если e>=0 то e:=e+t+ca иначе y:=y-1, e:=e+t-s+cd, s:=s+dst; t:=t-dst;

Закрасить пиксел (xc+x,yc+y);

Закрасить пиксел (xc+y,yc+x);

Закрасить пиксел (xc+y,yc-x);

В этом алгоритме используется симметрия круга - в основном цикле вычисляются координаты точек окружности только для одного октанта и сразу рисуются восемь симметрично расположенных пикселов. Алгоритм вывода эллипса Инкрементный алгоритм для эллипса подобен алгоритму для круга, но несколько сложнее его:

a:=|enx-xc|; b:=|eny-yc|;

a2:=a*a; b2:=b*b;

dds:=4*a2; ddt:=4*b2; dxt:=a2/sqrt(a2+b2);

t:=0;

s:=-4*a2*b;

e:=(-s/2)-2*b2-a2;

ca:=-6*b2;

cd:=ca-4*a2;

x:=xc; y:=yc+b;

Закрасить пиксел (x, y);

Закрасить пиксел (x, 2*yc-y);

Закрасить пиксел (2*xc-x, 2*yc-y);

Закрасить пиксел (2*xc-x, y);

Для indx от 1 до dxt с шагом 1:

x:=x+1;

Если e>=0 то e:=e+t+ca иначе y:=y-1, e:=e+t-s+cd,

s:=s+dds; t:=t-ddt;

Закрасить пиксел (x, y);

Закрасить пиксел (x, 2*yc-y);

Закрасить пиксел (2*xc-x, 2*yc-y);

Закрасить пиксел (2*xc-x, y);

dxt:=|y-yc|;

e:=e-(t/2+s/2+b2+a2);

ca:=-6*a2;

cd:=ca-4*b2;

Для indx от 1 до dxt с шагом 1:

y:=y-1;

Если e<=0 то e:=e-s+ca иначе x:=x+1, e:=e-s+t+cd,

t:=t-ddt; s:=s+dds;

Закрасить пиксел (x, y);

Закрасить пиксел (x, 2*yc-y);

Закрасить пиксел (2*xc-x, 2*yc-y);

Закрасить пиксел (2*xc-x, y).

В этом алгоритме использована симметрия эллипса по квадрантам. Алгоритм состоит из двух циклов. Сначала для x от 0 до dxt, где а потом цикл до точкиx=a, y=0.

17. Удаление невидимых линий и поверхностей

Алгоритм Робертса

В объектном пространстве первый этап – удаление граней, ребер закрываемых самим телом.Второй этап – проверка видимых ребер на закрытие другими телами.Вычислительная трудоемкостьn²(количество объектов в сцепе).Условие алгоритма– все тела выпуклые.p= [abcd] - плоскость

a

b

ax + by + cz + d = 0 [ x y z₁ ] c = 0 или [ x y z₁ ] [ p ]^T = 0

d

a₁ . . . a_n

b₁ b_n

V = c₁ c_n матрица тела [ S ] = [ x y z₁ ]

d₁ d_n

>

[s] [p]^T= 0 по какую сторону от плоскости

<

В алгоритме Робертсапредполагается, что точки внутри дают > 0.

Чтобы этого добиться нужны коррективные уравнения.

АЛГОРИТМ ВАРНОКА (удаление невидимых поверхностей)

Рассматривается сцена, состоящая из многоугольников (полигонов). Требуется определить только видимые части полигонов. По взаимному положению полигонов и окна (экрана) можно выделить следующие типы полигонов:

a) внешний б) внутренний в) пересекающий г) охватывающий