 |
Рисование простых графичиских объектов.
Рисование окружности.
Алгоритмы взяты из прекрасной книги
П.В.Вельтмандер "Машинная графика"
Во многих областях приложений, таких как, например, системы автоматизированного проектирования машиностроительного направления, естественными графическими примитивами, кроме отрезков прямых и строк текстов, являются и конические сечения, т.е. окружности, эллипсы, параболы и гиперболы. Наиболее употребительным примитивом, естественно, является окружность. Один из наиболее простых и эффективных алгоритмов генерации окружности разработан Брезенхемом.
1 Алгоритм Брезенхема
Для простоты и без ограничения общности рассмотрим генерацию 1/8 окружности, центр которой лежит в начале координат. Остальные части окружности могут быть получены последовательными отражениями (использованием симметрии точек на окружности относительно центра и осей координат).
Окружность с центром в начале координат описывается уравнением:
|
Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пиксела точку растра Pi(Xi, Yi), ближайшую к истинной окружности, так чтобы ошибка:
|
была минимальной. Причем, как и в алгоритме Брезенхема для генерации отрезков, выбор ближайшей точки выполняется с помощью анализа значений управляющих переменных, для вычисления которых не требуется вещественной арифметики. Для выбора очередной точки достаточно проанализировать знаки.
Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R.
Проанализируем возможные варианты занесения i+1-й точки, после занесения i-й.
При генерации окружности по часовой стрелке после занесения точки (Xi, Yi) следующая точка может быть (см. рис. 0.1а) либо Pg = (Xi+1, Yi) - перемещение по горизонтали, либо Pd = (Xi+1, Yi-1) - перемещение по диагонали, либо Pv = (Xi, Yi-1) - перемещение по вертикали.
Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра окружности до точки и окружности:
| ||||||||||||||||||||||||||||||||||||||||||
Выбирается и заносится та точка, для которой это значение минимально.
Выбор способа расчета определяется по значению Dd. Если Dd < 0, то диагональная точка внутри окружности. Это варианты 1-3 (см. рис. 0.1б). Если Dd > 0, то диагональная точка вне окружности. Это варианты 5-7. И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности. Это вариант 4. Рассмотрим случаи различных значений Dd в только что приведенной последовательности.
Случай Dd < 0
Здесь в качестве следующего пиксела могут быть выбраны или горизонтальный - Pg или диагональный - Pd.
Для определения того, какой пиксел выбрать Pg или Pd составим разность:
| |||||||||||||
И будем выбирать точку Pg при di Ј 0, в противном случае выберем Pd.
Рассмотрим вычисление di для разных вариантов.
Для вариантов 2 и 3:
Dg і 0 и Dd < 0, так как горизонтальный пиксел либо вне, либо на окружности, а диагональный внутри.
|
Добавив и вычтя (Y-1)2 получим:
|
В квадратных скобках стоит Dd, так что
|
Для варианта 1:
Ясно, что должен быть выбран горизонтальный пиксел Pg. Проверка компонент di показывает, что Dg < 0 и Dd < 0, причем di < 0, так как диагональная точка больше удалена от окружности, т.е. по критерию di < 0 как и в предыдущих случаях следует выбрать горизонтальный пиксел Pg, что верно.
Случай Dd > 0
Здесь в качестве следующего пиксела могут быть выбраны или диагональный - Pd или вертикальный Pv.
Для определения того, какую пиксел выбрать Pd или Pv составим разность:
| |||||||||||||
Если si Ј 0, то расстояние до вертикальной точки больше и надо выбирать диагональный пиксел Pd, если же si > 0, то выбираем вертикальный пиксел Pv.
Рассмотрим вычисление si для разных вариантов.
Для вариантов 5 и 6:
Dd > 0 и Dv Ј 0, так как диагональный пиксел вне, а вертикальный либо вне либо на окружности.
|
Добавив и вычтя (X+1)2 получим:
|
В квадратных скобках стоит Dd, так что
|
Для варианта 7:
Ясно, что должен быть выбран вертикальный пиксел Pv. Проверка компонент si показывает, что Dd > 0 и Dv > 0, причем si > 0, так как диагональная точка больше удалена от окружности, т.е. по критерию si > 0 как и в предыдущих случаях следует выбрать вертикальный пиксел Pv, что соответствует выбору для вариантов 5 и 6.
Случай Dd = 0
Для компонент di имеем: Dg > 0 и Dd = 0, следовательно по критерию di > 0 выбираем диагональный пиксел.
С другой стороны, для компонент si имеем: Dd = 0 и Dv < 0, так что по критерию si Ј 0 также выбираем диагональный пиксел.
Итак:
Dd < 0
di Ј 0 - выбор горизонтального пиксела Pg
di > 0 - выбор диагонального пиксела Pd
Dd > 0
si Ј 0 - выбор диагонального пиксела Pd
si > 0 - выбор вертикального пиксела Pv
Dd = 0
выбор диагонального пиксела Pd.
Выведем рекуррентные соотношения для вычисления Dd для (i+1)-го шага,
после выполнения i-го.
1. Для горизонтального шага к Xi+1, Yi
Xi+1 = Xi + 1
Yi+1 = Yi
Ddi+1 = (Xi+1+1)2 + (Yi+1-1)2 - R2 =
Xi+12 + 2·Xi+1 + 1 + (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
В Приложении 5 приведена подпрограмма V_circle, реализующая описанный выше алгоритм и строящая дугу окружности в первой четверти. Начальная инициализация должна быть:
X= 0
Y= R
Dd = (X+1)2 + (Y-1)2 - R2 = 1 + (R-1)2 - R2 = 2*(1 - R)
Пикселы в остальных четвертях можно получить отражением. Кроме того достаточно сформировать дугу только во втором октанте, а остальные пикселы сформировать из соображений симметрии, например, с помощью подпрограммы Pixel_circle, приведенной в Приложении и заносящей симметричные пикселы по часовой стрелке от исходного.
В Приложении приведены подпрограмма V_BRcirc, реализующая описанный выше алгоритм и строящая дугу окружности во втором октанте с последующим симметричным занесением пикселов. Эта процедура может строить и 1/4 окружности. Подробнее см. текст Приложения. Там же приведена более короткая подпрограмма, строящая 1/8 окружности методом Мичнера [], (том 1, стр. 152). Остальная часть окружности строится симметрично.
0.15 Приложение 4. Процедуры генерации окружности
В данном приложении помещены процедуры генерации окружностей по алгоритму Брезенхема и Мичнера, а также программа T_Circle для тестирования данных процедур.
/*--------------------------------------------------- V_Circle
* Подпрограммы для генерации окружности
* Pixel_circle - занесение пикселов с учетом симметрии
* V_BRcirc - генерирует окружность по алгоритму
* Брезенхема.
* V_MIcirc - генерирует окружность по алгоритму
* Мичнера.
*/
#include <graphics.h>
/*----------------------------------------------- Pixel_circle
* Заносит пикселы окружности по часовой стрелке
*/
static void Pixel_circle (xc, yc, x, y, pixel)
int xc, yc, x, y, pixel;
{
putpixel(xc+x, yc+y, pixel);
putpixel(xc+y, yc+x, pixel);
putpixel(xc+y, yc-x, pixel);
putpixel(xc+x, yc-y, pixel);
putpixel(xc-x, yc-y, pixel);
putpixel(xc-y, yc-x, pixel);
putpixel(xc-y, yc+x, pixel);
putpixel(xc-x, yc+y, pixel);
} /* Pixel_circle */
/*--------------------------------------------------- V_BRcirc
* Генерирует 1/8 окружности по алгоритму Брезенхема
*
* Процедура может строить 1/4 окружности.
* Для этого надо цикл while заменить на for (;;)
* и после Pixel_circle проверять достижение конца по условию
* if (y <= end) break;
* Где end устанавливается равным 0
* В этом случае не нужен и последний оператор
* if (x == y) Pixel_circle (xc, yc, x, y, pixel);
* Генерацию 1/8 можно обеспечить задав end = r / sqrt (2)
*/
void V_BRcirc (xc, yc, r, pixel)
int xc, yc, r, pixel;
{ int x, y, z, Dd;
x= 0; y= r; Dd= 2*(1-r);
while (x < y) {
Pixel_circle (xc, yc, x, y, pixel);
if (!Dd) goto Pd;
z= 2*Dd - 1;
if (Dd > 0) {
if (z + 2*x <= 0) goto Pd; else goto Pv;
}
if (z + 2*y > 0) goto Pd;
Pg: ++x; Dd= Dd + 2*x + 1; continue; /* Горизонт */
Pd: ++x; --y; Dd= Dd + 2*(x-y+1); continue; /* Диагонал */
Pv: --y; Dd= Dd - 2*y + 1; /* Вертикал */
}
if (x == y) Pixel_circle (xc, yc, x, y, pixel);
} /* V_BRcirc */
/*--------------------------------------------------- V_MIcirc
* Генерирует 1/8 окружности по алгоритму Мичнера
*/
void V_MIcirc (xc, yc, r, pixel)
int xc, yc, r, pixel;
{ int x, y, d;
x= 0; y= r; d= 3 - 2*r;
while (x < y) {
Pixel_circle (xc, yc, x, y, pixel);
if (d < 0) d= d + 4*x + 6; else {
d= d + 4*(x-y) + 10; --y;
}
++x;
}
if (x == y) Pixel_circle (xc, yc, x, y, pixel);
} /* V_MIcirc */
/*=============================================== T_CIRCLE.C
*
* ТЕСТ ГЕНЕРАЦИИ ОКРУЖНОСТЕЙ
*
* Запрашивает ввод четырех чисел - координат центра,
* радиуса и цвета построения: Xc Yc R Pix
*
* Затем строит заданную окружность по алгоритму Брезенхема
* и концентрично с ней с радиусом, уменьшенным на 2, и
* номером цвета, уменьшенным на 1, выдает окружность по
* алгоритму Мичнера.
*
* При вводе Xc < 0 программа прекращает работу
*/
#include <graphics.h>
#include <stdio.h>
#include "V_CIRCLE.C"
/*-------------------------------------------- MAIN T_CIRCLE.C
*/
void main (void)
{
int ii, Xc=300, Yc=240, R=238, Pix=14;
int gdriver = DETECT, gmode;
initgraph(&gdriver, &gmode, "c:\tc\bgi");
if ((ii= graphresult()) != grOk) {
printf ("Err=%d\n", ii); goto all;
}
setbkcolor(0);
cleardevice();
for (;;) {
gotoxy (1,1);
printf(" \r");
printf("Xc, Yc, R, Pix= (%d %d %d %d) ? ", Xc,Yc,R,Pix);
scanf ("%d%d%d%d", &Xc, &Yc, &R, &Pix);
if (Xc < 0) break;
V_BRcirc (Xc, Yc, R, Pix);
V_MIcirc (Xc, Yc, R-2, Pix-1);
}
all:
closegraph();
}
Исходники этого алгоритма, взятые из других источников.
void Circle(int x, int y, int r,unsigned char color)
{
int x1,y1,yk = 0;
int sigma,delta,f;
x1 = 0;
y1 = r;
delta = 2*(1-r);
do
{
PutPixel(x+x1,y+y1,color);
PutPixel(x-x1,y+y1,color);
PutPixel(x+x1,y-y1,color);
PutPixel(x-x1,y-y1,color);
f = 0;
if (y1 < yk)
break;
if (delta < 0)
{
sigma = 2*(delta+y1)-1;
if (sigma <= 0)
{
x1++;
delta += 2*x1+1;
f = 1;
}
}
else
if (delta > 0)
{
sigma = 2*(delta-x1)-1;
if (sigma > 0)
{
y1--;
delta += 1-2*y1;
f = 1;
}
}
if (!f)
{
x1++;
y1--;
delta += 2*(x1-y1-1);
}
}
while(1);
}
На Паскале:
Procedure Circle(x,y,rr:integer); var xi,yi,r,di,lim,s,ss:integer; label 1,2,3,4,10,20,30; Begin r:=rr; xi:=0; yi:=r; di:=2*(1-r); lim:=0; 1: SetPixel(xi+x,yi+y); SetPixel(xi+x,-yi+y); SetPixel(-xi+x,yi+y); SetPixel(-xi+x,-yi+y); if yi0then goto 3; if di=0 then goto 20; 2: s:=2*di+2*yi-1; if s<=0then goto 10; if s>0then goto 20; 3: s:=2*di+2*xi-1; if s<=0then goto 20; if s>0then goto 30; 10:xi:=xi+1; di:=di+2*xi+1; goto 1; 20:xi:=xi+1; yi:=yi-1; di:=di+2*xi-2*yi+2; goto 1; 30:yi:=yi-1; di:=di-2*yi+1; goto 1; 4: end;
Вверх по странице, к оглавлению и навигации.