DEMO.DESIGN
 Frequently Asked Questions		  
оглавление | demo party в ex-СССР | infused bytes e-mag | новости от ib/news | другие проекты | письмо | win koi lat 
следующий фpагмент (2)
- Demo/intro making and discussion (2:5030/84) ------------------ DEMO.DESIGN -
 Msg  : 1887 of 1887
 From : Andrew Usachov                      2:5100/87       31 Jul 98  18:38:46
 To   : All                                                 01 Aug 98  00:08:17
 Subj : Алгоpитмики:
-------------------------------------------------------------------------------
г=[¦]========================[ Hello All! ]=======----------------

    Знаю, что к демкам это почти не имеет отношения, однако об этом говоpится в
FAQ... Вашему вниманию пpедлагаются :-) пpоцедуpа, pисующая окpужность и не
использующая умножений и типов данных длиннее WORD, и пpоцедуpа, pисующая
эллипс, и выполняющая 4 умножения на эллипс. Может, занести в FAQ в качестве
пpимеpа?

- - - 8< - - - - - 8< - - [ begin of Circle.Pas ] - - 8< - - - - - 8< - - -
{ (с) 1997,1998 Andrew Usachov, 2:5100/87@fidonet

    Как это pаботает?
    Фоpмула окpужности вокpуг начала кооpдинат r1^2=x1^2+y1^2=r0^2. Достаточно
наpисовать одну дугу от напpавления "на 12 часов" до напpавления "на 1 час 30
минут" :-) , а остальные 7 дуг получить отpажениями. Рисуем точку "на 12
часов".
Расстояние от нее до начала кооpдинат (вpеменный pадиус) pавно pадиусу
окpужности. Пpодвигаем точку на пискель пpавее. Вpеменный pадиус может стать
больше pадиуса окpужности (точка вышла из окpужности), в таком случае опускаем
точку на пискель вниз. Для pассматpиваемой дуги это гаpантиpует, что вpеменный
pадиус обязательно опять станет меньше pадиуса окpужности (точка веpнется в
окpужность). Можно pисовать следующую точку. Так мы их pисуем, пока напpавление
из центpа окpужности на последнюю точку не станет больше, чем "на 1 час 30
мин",
т.е. y1<x1.
    От умножений избавляемся следующим обpазом. В цикле для пpовеpки выхода
точки из окpужности сpавниваем не r1 с r0 и не r1^2 с r0^2, а r0^2-r1^2 с 0.
Выpажение r0^2-r1^0 уменьшается на 2*x1+1 пpи пеpемешении точки на пиксель
впpаво и увеличивается на 2*y1+1 пpи пеpемещении точки на пиксель вниз. В
случае
эллипса уpавнение будет r1^2=(x1/Rx)^2+(y1/Ry)^2=1. Пеpеходим к целым числам:
x1^2*Ry^2+y1^2*Rx^2=Rx^2*Ry^2. Пpи пеpедвижении точки впpаво выpажение
Rx^2*Ry^2-x1^2*Ry^2+y1^2*Rx^2, котоpое нам надо сpавнивать с нулем для пpовеpки
необходимости опустить точку на пиксель вниз, уменьшается на величину
(2*x1+1)*Ry^2=2*x1*Ry^2+Ry^2, где пеpвое слагаемое в свою очеpедь с каждым
пеpемещением впpаво уменьшается на константу 2*Ry^2, а втоpое - константа.
    Эллипс стpоится из четыpех симметpичных "веpтикальных" и четыpех
симметpичных "гоpизонтальных" дуг. Рисование одной "гоpизонтальной" дуги
пpоисходит от самой веpхней точки эллипса до тех поp, пока пеpемещение вышедшей
из эллипса текущей pисуемой точки на пиксель вниз не пеpестанет возвpащать эту
точку обpатно в эллипс.
}

Var Screen: Array[0..199,0..319] of Byte absolute $a000:$0000;

Procedure Circle(x0,y0,r0,c0: Integer);
Var x1,y1,r02_r2 : Integer;
begin
 x1:=0;
 y1:=r0;
 r02_r2:=r0+r0+1; { Hа любителя: здесь можно написать ":=0"}
 repeat
  Screen[y0+y1,x0+x1]:=c0;
  Screen[y0+y1,x0-x1]:=c0;
  Screen[y0-y1,x0+x1]:=c0;
  Screen[y0-y1,x0-x1]:=c0;
  Screen[y0+x1,x0+y1]:=c0;
  Screen[y0+x1,x0-y1]:=c0;
  Screen[y0-x1,x0+y1]:=c0;
  Screen[y0-x1,x0-y1]:=c0;
  Dec(r02_r2,x1+x1+1);
  Inc(x1);
  if r02_r2<=0 then {...тогда здесь нужно написать "<0"}
    begin
     Dec(y1);
     Inc(r02_r2,y1+y1+1);
    end;
 until x1>y1;
end;

Procedure FillCircle(x0,y0,r0,c0: Integer);
Var x1,y1,r02_r2,x,y : Integer;
begin
 x1:=0;
 y1:=r0;
 r02_r2:=r0+r0+1;
 repeat
  For x:=x0-x1 to x0+x1 do
   begin
    Screen[y0+y1,x]:=c0;
    Screen[y0-y1,x]:=c0;
   end;
  For x:=x0-y1 to x0+y1 do
    begin
     Screen[y0+x1,x]:=c0;
     Screen[y0-x1,x]:=c0;
    end;
  Dec(r02_r2,x1+x1+1);
  Inc(x1);
  if r02_r2<=0 then
    begin
     Dec(y1);
     Inc(r02_r2,y1+y1+1);
    end;
 until x1>y1;
end;

Procedure Ellipse(x0,y0,Rx,Ry,c0: Integer);
Var x1,y1,Rx2,Ry2,x1Ry2,y1Rx2,Rx2Ry2_x12Ry2_y12Rx2: LongInt;
begin
 Rx2:=Sqr(Rx+1);
 Ry2:=Sqr(Ry+1);

 x1:=0;
 y1:=Ry;
 x1Ry2:=0;
 y1Rx2:=y1*Rx2;
 Rx2Ry2_x12Ry2_y12Rx2:=y1Rx2+y1Rx2+Rx2;
 repeat
  Screen[y0+y1,x0+x1]:=c0;
  Screen[y0+y1,x0-x1]:=c0;
  Screen[y0-y1,x0+x1]:=c0;
  Screen[y0-y1,x0-x1]:=c0;
  Dec(Rx2Ry2_x12Ry2_y12Rx2,x1Ry2+x1Ry2+Ry2);
  Inc(x1);
  Inc(x1Ry2,Ry2);
  if Rx2Ry2_x12Ry2_y12Rx2<0 then begin
                                  Dec(y1);
                                  Dec(y1Rx2,Rx2);
                                  Inc(Rx2Ry2_x12Ry2_y12Rx2,y1Rx2+y1Rx2+Rx2);
                                 end
                            else Continue;
  until Rx2Ry2_x12Ry2_y12Rx2<0;

 x1:=Rx;
 y1:=0;
 x1Ry2:=x1*Ry2;
 y1Rx2:=0;
 Rx2Ry2_x12Ry2_y12Rx2:=x1Ry2+x1Ry2+Ry2;
 repeat
  Screen[y0+y1,x0+x1]:=c0;
  Screen[y0+y1,x0-x1]:=c0;
  Screen[y0-y1,x0+x1]:=c0;
  Screen[y0-y1,x0-x1]:=c0;
  Dec(Rx2Ry2_x12Ry2_y12Rx2,y1Rx2+y1Rx2+Rx2);
  Inc(y1);
  Inc(y1Rx2,Rx2);
  if Rx2Ry2_x12Ry2_y12Rx2<0 then begin
                                  Dec(x1);
                                  Dec(x1Ry2,Ry2);
                                  Inc(Rx2Ry2_x12Ry2_y12Rx2,x1Ry2+x1Ry2+Ry2);
                                 end
                            else Continue;
  until Rx2Ry2_x12Ry2_y12Rx2<0;
end;

BEGIN
 asm
  mov ax, $13
  int $10
 end;

 Repeat
   Circle(50+Random(219),50+Random(99),10+Random(40),9+Random(7));
{  Ellipse(50+Random(219),50+Random(99),Random(50),Random(50),9+Random(7));}
 Until Port[$60]=1;

 asm
  mov ax, $03
  int $10
 end;
END.
- - - 8< - - - - - 8< - - [  end of Circle.Pas  ] - - 8< - - - - - 8< - - -


следующий фpагмент (3)|пpедыдущий фpагмент (1)


- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS -
 Msg  : 15 of 34                                                                
 From : andrewfg@ed.ac.uk                   2:5030/144.99   14 Apr 94  09:52:12 
 To   : All                                                 17 Apr 94  01:45:08 
 Subj : Ellipse drawing                                                         
--------------------------------------------------------------------------------

I posted this before, but I don't know if it got through.
Anyway, it's my implementation  of the Foley and van Dam ellipse drawer.

A.

--
Andrew Fitzgibbon (Research Associate),                     andrewfg@ed.ac.uk
Artificial Intelligence, Edinburgh University.               +44 031 650 4504
       "If it ain't broke, don't fix it" - traditional (c1950)
          "A stitch in time saves nine." - traditional (c1590)


-----------------------------------------------------------------------------
//
// CONIC  2D Bresenham-like conic drawer.
//  CONIC(Sx,Sy, Ex,Ey, A,B,C,D,E,F) draws the conic specified
//  by A x^2 + B x y + C y^2 + D x + E y + F = 0, between the
//  start point (Sx, Sy) and endpoint (Ex,Ey).

// Author: Andrew W. Fitzgibbon (andrewfg@ed.ac.uk),
//       Machine Vision Unit,
//         Dept. of Artificial Intelligence,
//    Edinburgh University,
//
// Date: 31-Mar-94

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#include "image.hxx"

static int DIAGx[] = {999, 1,  1, -1, -1, -1, -1,  1,  1};
static int DIAGy[] = {999, 1,  1,  1,  1, -1, -1, -1, -1};
static int SIDEx[] = {999, 1,  0,  0, -1, -1,  0,  0,  1};
static int SIDEy[] = {999, 0,  1,  1,  0,  0, -1, -1,  0};
//atic int BSIGNS[] = {99, 1,  1, -1, -1,  1,  1, -1, -1};

int   debugging = 0;

void ConicPlotter::plot(int x, int y)
{
  printf("ConicPlotter::plot(%d, %d)\n", x, y);
}

inline int odd(int n)
{
  return n&1;
}

inline int abs(int a)
{
  if (a > 0)
    return a;
  else
    return -a;
}

int getoctant(int gx, int gy)
{
  // Use gradient to identify octant.
  int upper = abs(gx)>abs(gy);
  if (gx>=0)          // Right-pointing
    if (gy>=0)        //    Up
      return 4 - upper;
    else          //    Down
      return 1 + upper;
  else            // Left
    if (gy>0)         //    Up
      return 5 + upper;
    else          //    Down
      return 8 - upper;
}

int conic(int xs, int ys, int xe, int ye,
    int A, int B, int C, int D, int E, int F,
    ConicPlotter * plotterdata)
{
  A *= 4;
  B *= 4;
  C *= 4;
  D *= 4;
  E *= 4;
  F *= 4;

  // Translate start point to origin...
  F = A*xs*xs + B*xs*ys + C*ys*ys + D*xs + E*ys + F;
  D = D + 2 * A * xs + B * ys;
  E = E + B * xs + 2 * C * ys;

  // Work out starting octant
  int octant = getoctant(D,E);

  int dxS = SIDEx[octant];
  int dyS = SIDEy[octant];
  int dxD = DIAGx[octant];
  int dyD = DIAGy[octant];

  int d,u,v;
  switch (octant) {
  case 1:
    d = A + B/2 + C/4 + D + E/2 + F;
    u = A + B/2 + D;
    v = u + E;
    break;
  case 2:
    d = A/4 + B/2 + C + D/2 + E + F;
    u = B/2 + C + E;
    v = u + D;
    break;
  case 3:
    d = A/4 - B/2 + C - D/2 + E + F;
    u = -B/2 + C + E;
    v = u - D;
    break;
  case 4:
    d = A - B/2 + C/4 - D + E/2 + F;
    u = A - B/2 - D;
    v = u + E;
    break;
  case 5:
    d = A + B/2 + C/4 - D - E/2 + F;
    u = A + B/2 - D;
    v = u - E;
    break;
  case 6:
    d = A/4 + B/2 + C - D/2 - E + F;
    u = B/2 + C - E;
    v = u - D;
    break;
  case 7:
    d = A/4 - B/2 + C + D/2 - E + F;
    u =  -B/2 + C - E;
    v = u + D;
    break;
  case 8:
    d = A - B/2 + C/4 + D - E/2 + F;
    u = A - B/2 + D;
    v = u - E;
    break;
  default:
    fprintf(stderr,"FUNNY OCTANT\n");
    abort();
  }

  int k1sign = dyS*dyD;
  int k1 = 2 * (A + k1sign * (C - A));
  int Bsign = dxD*dyD;
  int k2 = k1 + Bsign * B;
  int k3 = 2 * (A + C + Bsign * B);

  // Work out gradient at endpoint
  int gxe = xe - xs;
  int gye = ye - ys;
  int gx = 2*A*gxe +   B*gye + D;
  int gy =   B*gxe + 2*C*gye + E;

  int octantcount = getoctant(gx,gy) - octant;
  if (octantcount <= 0)
    octantcount = octantcount + 8;
  fprintf(stderr,"octantcount = %d\n", octantcount);

  int x = xs;
  int y = ys;

  while (octantcount > 0) {
    if (debugging)
      fprintf(stderr,"-- %d -------------------------\n", octant);

    if (odd(octant)) {
      while (2*v <= k2) {
  // Plot this point
  plotterdata->plot(x,y);

  // Are we inside or outside?
  if (d < 0) {        // Inside
    x = x + dxS;
    y = y + dyS;
    u = u + k1;
    v = v + k2;
    d = d + u;
  }
  else {          // outside
    x = x + dxD;
    y = y + dyD;
    u = u + k2;
    v = v + k3;
    d = d + v;
  }
      }

      d = d - u + v/2 - k2/2 + 3*k3/8;
      // error (^) in Foley and van Dam p 959, "2nd ed, revised 5th printing"
      u = -u + v - k2/2 + k3/2;
      v = v - k2 + k3/2;
      k1 = k1 - 2*k2 + k3;
      k2 = k3 - k2;
      int tmp = dxS; dxS = -dyS; dyS = tmp;
    }
    else {        // Octant is even
      while (2*u < k2) {
  // Plot this point
  plotterdata->plot(x,y);

  // Are we inside or outside?
  if (d > 0) {        // Outside
    x = x + dxS;
    y = y + dyS;
    u = u + k1;
    v = v + k2;
    d = d + u;
  }
  else {          // Inside
    x = x + dxD;
    y = y + dyD;
    u = u + k2;
    v = v + k3;
    d = d + v;
  }
      }
      int tmpdk = k1 - k2;
      d = d + u - v + tmpdk;
      v = 2*u - v + tmpdk;
      u = u + tmpdk;
      k3 = k3 + 4*tmpdk;
      k2 = k1 + tmpdk;

      int tmp = dxD; dxD = -dyD; dyD = tmp;
    }

    octant = (octant&7)+1;
    octantcount--;
  }

  // Draw final octant until we reach the endpoint
  if (debugging)
    fprintf(stderr,"-- %d (final) -----------------\n", octant);

  if (odd(octant)) {
    while (2*v <= k2 && x != xe && y != ye) {
      // Plot this point
      plotterdata->plot(x,y);

      // Are we inside or outside?
      if (d < 0) {        // Inside
  x = x + dxS;
  y = y + dyS;
  u = u + k1;
  v = v + k2;
  d = d + u;
      }
      else {          // outside
  x = x + dxD;
  y = y + dyD;
  u = u + k2;
  v = v + k3;
  d = d + v;
      }
    }
  }
  else {       // Octant is even
    while ((2*u < k2) && (x != xe) && (y != ye)) {
      // Plot this point
      plotterdata->plot(x,y);

      // Are we inside or outside?
      if (d > 0) {        // Outside
  x = x + dxS;
  y = y + dyS;
  u = u + k1;
  v = v + k2;
  d = d + u;
      }
      else {          // Inside
  x = x + dxD;
  y = y + dyD;
  u = u + k2;
  v = v + k3;
  d = d + v;
      }
    }
  }

  return 1;
}


следующий фpагмент (4)|пpедыдущий фpагмент (2)

- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS -
 Msg  : 115 of 144                                                              
 From : sabre@teleport.com                  2:5030/315      18 Jan 96  23:40:36 
 To   : All                                                 20 Jan 96  05:15:20 
 Subj : Re: Bresenham algorithm for an ellipse ?                                
--------------------------------------------------------------------------------
X-RealName: Chris Lattner

: I am looking an algorithm for drawing an ellipse .
: The input shall be the midpoint and the two axes .

Here is one implementation in C of the algorithm...

Remark : Only one quarter of the ellipse is computated, the rest
         is set by symmetry.

         a  and  b  are the half-axes (I hope this is the right
         word for it) of the ellipse in  x- and y-direction.
         If you like a circle set  a=b=radius  .

--------------------------------- cut ---------------------------------
void symmetry(x,y)
int x,y;
{
 PUT_PIXEL(+x,+y);  // This would obviously be inlined!
 PUT_PIXEL(-x,+y);  // and offset by a constant amount
 PUT_PIXEL(-x,-y);
 PUT_PIXEL(+x,-y);
}

void bresenham_ellipse(a,b)
int a,b;
{
 int x,y,a2,b2, S, T;

 a2 = a*a;
 b2 = b*b;
 x = 0;
 y = b;
 S = a2*(1-2*b) + 2*b2;
 T = b2 - 2*a2*(2*b-1);
 symmetry(x,y);
 do
   {
    if (S<0)
       {
        S += 2*b2*(2*x+3);
        T += 4*b2*(x+1);
        x++;
       }
      else if (T<0)
          {
           S += 2*b2*(2*x+3) - 4*a2*(y-1);
           T += 4*b2*(x+1) - 2*a2*(2*y-3);
           x++;
           y--;
          }
         else
          {
           S -= 4*a2*(y-1);
           T -= 2*a2*(2*y-3);
           y--;
          }
    symmetry(x,y);
   }
 while (y>0);
}

Have fun!
Chris

следующий фpагмент (5)|пpедыдущий фpагмент (3)

A few requests for ellipses have prompted me to include this code. It
draws ellipses (including circles, of course) of varying line width
on a SUN bitmap display. (It's part of a paint-type program). I don't
know how this compares to the earlier posting of an ellipse algorithm,
but it's fairly fast.

Enjoy or flame....

=====================================================================

/***********************************************/
/* gred_ellipse.c - draw ellipses		*
/* algorithm from IEEE CG&A Sept 1984 p.24 	*
/***********************************************/
#include <stdio.h>
#include <sunwindow/window_hs.h>

gred_ellipse (cx, cy, radius_x, radius_y, line_width, pw, pattern_pr)
int   			cx, cy;
int   			radius_x, radius_y;
int			line_width;
struct pixwin 		*pw;
struct pixrect 		*pattern_pr;
{
    struct pixrect 	*pr;
    int			inner_radius_x;
    int			inner_radius_y;
    int			outer_radius_x;
    int			outer_radius_y;

/*******************************************************************/
/* Calculate the inner, outer radiuses of the ellipse              */
/*******************************************************************/
    /* if one pixel wide, radiuses are same */
    if (line_width < 2)
    {
	inner_radius_x = outer_radius_x = radius_x;
	inner_radius_y = outer_radius_y = radius_y;
    }
    else
    {
	outer_radius_x = radius_x + (line_width >> 1);
	outer_radius_y = radius_y + (line_width >> 1);
	inner_radius_x = outer_radius_x - line_width + 1;
	inner_radius_y = outer_radius_y - line_width + 1;
    }

/*******************************************************************/
/* Create a pixrect to build the ellipse in.                       */
/*******************************************************************/
    pr = mem_create ((outer_radius_x << 1) + 1, (outer_radius_y << 1) + 1, 1);
    /* now clear it */
    pr_rop (pr,	0, 0, pr -> pr_size.x, pr -> pr_size.y,
		PIX_CLR, (struct pixrect *) 0, 0, 0);

/*******************************************************************/
/* If the inner_radius > 0 then outline the inner edge.            */
/* Then if the outer radius of the ellipse is > than the inner     */
/* radius, call the fill ellipse routine with the outer radius.    */
/*******************************************************************/
    if ((inner_radius_x > 0)
    	    && (inner_radius_y > 0))
        outline_ellipse (pr, outer_radius_x, outer_radius_y, 
		inner_radius_x, inner_radius_y);

    if (line_width >=  2)
	fill_ellipse(pr, outer_radius_x, outer_radius_y, 
		outer_radius_x, outer_radius_y);
    
/*******************************************************************/
/* Now write the ellipse out to the window.                        */
/*******************************************************************/
    inner_radius_x = inner_radius_y = 0;	/* normal source offset */
    if ((cx -= outer_radius_x) < 0)	/* ellipse extends beyond left edge? */
    {
	inner_radius_x = -cx;
	cx = 0;
    }
    if ((cy -= outer_radius_y) < 0)	/* above top edge? */
    {
    	inner_radius_y = -cy;
	cy = 0;
    }

    if (pattern_pr == NULL)
        pw_write (pw, cx, cy, pr->pr_size.x-inner_radius_x, pr->pr_size.y-inner_radius_y,
	    PIX_SRC ^ PIX_DST, pr, inner_radius_x, inner_radius_y);
    else
	pw_stencil (pw, cx, cy, pr -> pr_size.x, pr -> pr_size.y, 
	    PIX_SRC, pr, inner_radius_x, inner_radius_y, pattern_pr, 0, 0);

    pr_destroy (pr);
}


/* draw ellipse incrementally */
static outline_ellipse (pr, center_x, center_y, rx, ry)
struct pixrect *pr;
int    center_x, center_y;
int    rx, ry;
{
	/* intermediate terms to speed up loop */
	long t1 = rx*rx, t2 = t1<<1, t3 = t2<<1;
	long t4 = ry*ry, t5 = t4<<1, t6 = t5<<1;
	long t7 = rx*t5, t8 = t7<<1, t9 = 0L;
	long d1 = t2 - t7 + (t4>>1);	/* error terms */
	long d2 = (t1>>1) - t8 + t5;

	register int x = rx, y = 0;	/* ellipse points */

	while (d2 < 0)			/* til slope = -1 */
	{
		/* draw 4 points using symmetry */
	    	pr_put (pr, center_x + x, center_y + y, 1);
	    	pr_put (pr, center_x + x, center_y - y, 1);
	    	pr_put (pr, center_x - x, center_y + y, 1);
	    	pr_put (pr, center_x - x, center_y - y, 1);

		y++;		/* always move up here */
		t9 += t3;	
		if (d1 < 0)	/* move straight up */
		{
			d1 += t9 + t2;
			d2 += t9;
		}
		else		/* move up and left */
		{
			x--;
			t8 -= t6;
			d1 += t9 + t2 - t8;
			d2 += t9 + t5 - t8;
		}
	}

	do 				/* rest of top right quadrant */
	{
		/* draw 4 points using symmetry */
	    	pr_put (pr, center_x + x, center_y + y, 1);
	    	pr_put (pr, center_x + x, center_y - y, 1);
	    	pr_put (pr, center_x - x, center_y + y, 1);
	    	pr_put (pr, center_x - x, center_y - y, 1);

		x--;		/* always move left here */
		t8 -= t6;	
		if (d2 < 0)	/* move up and left */
		{
			y++;
			t9 += t3;
			d2 += t9 + t5 - t8;
		}
		else		/* move straight left */
			d2 += t5 - t8;
	} while (x>=0);
}


static fill_ellipse (pr, center_x, center_y, rx, ry)
struct pixrect *pr;
int    center_x, center_y;
int    rx, ry;
{
	long t1 = rx*rx, t2 = t1<<1, t3 = t2<<1;
	long t4 = ry*ry, t5 = t4<<1, t6 = t5<<1;
	long t7 = rx*t5, t8 = t7<<1, t9 = 0;
	long d1 = t2 - t7 + (t4>>1);	/* error terms */
	long d2 = (t1>>1) - t8 + t5;
	register int x = rx, y = 0;	/* ellipse points */
        register int t;			/* used in fill operation */
	int wid;			/* width of fill */

	while (d2 < 0)			/* til slope = -1 */
	{
	 	/* fill in leftward to inner ellipse */
	    	for (t=x; (!pr_get(pr, center_x+t, center_y+y)) && t; t--);
		wid = x - t + 1;
		pr_rop (pr, center_x+t, center_y+y, wid, 1,
			PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
		pr_rop (pr, center_x-x, center_y+y, wid, 1,
			PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
		pr_rop (pr, center_x+t, center_y-y, wid, 1,
			PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
		pr_rop (pr, center_x-x, center_y-y, wid, 1,
			PIX_SET | PIX_DONTCLIP, NULL, 0, 0);

		y++;		/* always move up here */
		t9 += t3;	
		if (d1 < 0)	/* move straight up */
		{
			d1 += t9 + t2;
			d2 += t9;
		}
		else		/* move up and left */
		{
			x--;
			t8 -= t6;
			d1 += t9 + t2 - t8;
			d2 += t9 + t5 - t8;
		}
	}

	do 				/* rest of top right quadrant */
	{
		/* fill in downward to inner ellipse */
	    	for (t=y; (!pr_get(pr, center_x+x, center_y+t)) && t; t--);
		wid = y - t + 1;
		pr_rop (pr, center_x+x, center_y+t, 1, wid,
			PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
		pr_rop (pr, center_x+x, center_y-y, 1, wid,
			PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
		pr_rop (pr, center_x-x, center_y+t, 1, wid,
			PIX_SET | PIX_DONTCLIP, NULL, 0, 0);
		pr_rop (pr, center_x-x, center_y-y, 1, wid,
			PIX_SET | PIX_DONTCLIP, NULL, 0, 0);

		x--;		/* always move left here */
		t8 -= t6;	
		if (d2 < 0)	/* move up and left */
		{
			y++;
			t9 += t3;
			d2 += t9 + t5 - t8;
		}
		else		/* move straight left */
		{
			d2 += t5 - t8;
		}
	} while (x>=0);
}

следующий фpагмент (6)|пpедыдущий фpагмент (4)

>I am trying to draw "good" circles on an AT&T 3b1 (aka, UNIX PC).
>The problem is the aspect ratio - it is nowhere near unity.
>I have gone through McIlroy's paper ("Best Approximate Circles on
>Integer Grids") and Foley & Van Dam.  I see two ways to draw the circle:

>(1) Utilize "user coordinates" (in this case a 4096 by 4096 square)
       Bad idea.

>(2) Utilize "device coordinates" (430 by 288, in this case).
        The correct way.

>Am I missing something simple that would make it easy to draw my
>circles ??  Can anyone point me to another reference that adequately
>covers the drawing of a circle on a screen with a non-unity aspect
>ratio (F & VD mention a few, but before I go digging up the articles,
>does anyone know if these are what I should be looking at) ??

It's not really easy to generate good looking circles on a pixel grid.
After trying lots of different things, I have adopted the following
ellipse drawer. It draws ellipses in pixel space; to get circles you
feed it the proper height and width in pixels. This thine works really
well for circles with a radius greater than 4. For smaller circles,
it pays in terms of looking nice to draw each size as a special case.

The enclosed program uses the standard Bresnahan algorithm for the
best approximation of a curve. It is optimized for speed.

There was a good reference to this an article in Dr. Dobbs Journal in 1987,
but for circles only, not ellipses.

I hope that this can help you.

Doug McDonald
Department of Chemistry
University of Illinois


/* Draw an ellipse with width irx and height iry                         */
/* from a routine by Tim Hogan in Dr. Dobb's Journal May '85 p.40        */
/* Improved by calculating increments incrementally, thus removing all   */
/* multiplies from the loops. These multiplies were very bad since they  */
/* were (long)*(long).                                                   */
/* Written Sept. 7, 1987 by J.D. McDonald (public domain)                */

static long     alpha, beta, alpha2, alpha4, beta2, beta4, d;
static long     ddx, ddy, alphadx, betady;
static int      dy, dx;

extern void     e_start(int, int, int ,int);
extern void     e_xd();	
extern void     e_xdyu();
extern void     e_yu(); 

ellipse(x, y, irx, iry, c)
    int             x, y, irx, iry;
    unsigned        c;
{

    beta = (long) irx *(long) irx;
    alpha = (long) iry *(long) iry;

    if (alpha == 0L)
	alpha = 1L;
    if (beta == 0L)
	beta = 1L;

    dy = 0;
    dx = irx;
    alpha2 = alpha << 1;
    alpha4 = alpha2 << 1;
    beta2 = beta << 1;
    beta4 = beta2 << 1;
    alphadx = alpha * dx;
    betady = 0;
    ddx = alpha4 * (1 - dx);
    ddy = beta2 * 3;

    d = alpha2 * ((long) (dx - 1) * dx) + alpha + beta2 * (1 - alpha);
    e_start(x - dx, x + dx, y, c);
          /* e_start draws left and rightmost pixels on vertical centerline */
          /* e_yu draws a pixel in right top quadrant one up from previous  */
          /* e_xd draws a pixel in right top quadrant one left from previous*/
          /* e_xdyu draws a pixel in right top quadrant up and left from    */
          /* previous. e_yu, e_xd, and e_xdyu also draw the corresponding   */
          /* pixels in the other three quadrants.                           */
          /* c is the color                                                 */
    do {
	if (d >= 0) {
	    d += ddx;
	    dx--;
	    alphadx -= alpha;
	    ddx += alpha4;
	    e_xdyu();
	} else
	    e_yu();
	d += ddy;
	dy++;
	betady += beta;
	ddy += beta4;
    } while (alphadx > betady);

    d = beta2 * ((long) dy * (dy + 1)) + alpha2 * ((long) dx * (dx - 2) + 1) 
	+ beta * (1 - alpha2);
    ddx = alpha2 * (3 - (dx << 1));
    ddy = beta4 * (1 + dy);

    do {
	if (d <= 0) {
	    d += ddy;
	    ddy += beta4;
	    dy++;
	    e_xdyu();
	} else
	    e_xd();
	d += ddx;
	ddx += alpha4;
	dx--;
    } while (dx > 0);
}


следующий фpагмент (7)|пpедыдущий фpагмент (5)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS -
 Msg  : 31 of 38                                                                
 From : rmrice@eskimo.com                   2:5030/144.99   29 May 94  23:05:02 
 To   : All                                                 02 Jun 94  03:32:40 
 Subj : (1) HELP: Equation of circle                                            
--------------------------------------------------------------------------------


 -=> In Message-ID: <2sa9sn$3o@tribune.usask.ca>
 -=> James Jonathan Hankinson (Jjh119@herald.usask.ca) wrote on 05-29-94

 Jj> I am looking for an algorithm or C code that performs the
 Jj> following task:

 Jj> Given three points on a plane (x1,y1) (x2, y2) (x3, y3)
 Jj> Return the equation of the circle (center_x, center_y) and radius
 Jj> which passes through all three points.

 Jj> Thanks for any help!
 Jj> James Hankinson

Hi James,

The center of the three point circle will fall on a line which is
sloped perpendicular to, and passes thru the midpoint of, the line
between any two of the given points. The solution is easily found by
finding the intersection of any two such perpendicular lines.

The following snippet will calculate the center_x, center_y and radius
of a circle passing through three given points. I hope it helps you.

The 2D function 'ppp_circle' is also useful for the 3D case, which can
be easily reduced to the problem of three points on a plane. It may also
be used in the solution of the special case of Appolonius's 10th problem
(finding the smallest circle/sphere touching 3 given circles/spheres) in
which the 3 given circles or spheres all have the same radius.

Speaking of Appolonius, I've studied the articles in the Graphics Gems
books (by Jon Rokne in GG-II and by Constantin A. Sevici in GG-III), but
I don't have a clear enough grasp of the algorithms described to actually
code them. Could someone kindly direct me to more detailed descriptions
or existing code for either of those algorithms?

========= cut here ============= cut here ============== cut here ========

/*
** pppcir.c
**
** Contents:  Routine for 3 point circle with supporting routines
**        to calculate v2 line intersection and v2 distance.
**
** The code is self contained except for a call to the standard library
** function 'sqrt'.
**
** If you intend to interface this code with another program note that
** all position and vector parameters of the three functions (ppp_circle,
** line_intersect and v2_dist) are passed as pointers to structures. The
** radius parameter is also a pointer;
**
*/
#include <math.h>

#define false 0
#define true (!false)

typedef struct V2_DIST_VECT
{
  double x;
  double y;
} v2_dist_vect;

typedef v2_dist_vect v2_vect;
typedef v2_dist_vect v2_pos;

/*
** Function v2_dist -- Find the distance between 2 points in 2D space
**
** Inputs:
**    a    pointer to point on first line
**    b    pointer to point on second line
**
** Return value: double
**    calculated distance
*/
static double v2_dist(v2_pos *a, v2_pos *b)
{
  double dx, dy;

  dx = (a->x - b->x);
  dy = (a->y - b->y);
  return (sqrt((dx * dx) + (dy * dy)));
}

/*
** Function line_intersect -- Find the intersection of 2 lines in 2D space
**
** Inputs:
**    p1   pointer to point on first line
**    p2   pointer to point on second line
**    d1   pointer to slope vector of first line
**    d2   pointer to slope vector of second line
**    ip   pointer to storage for intersection position values
**
** Return value: int
**    true *ip contents valid -- intersection found
**    false   *ip contents undefined -- intersection NOT found
**        should only happen when passed two parallel lines
*/
static short line_intersect(v2_pos *p1, v2_pos *p2,
              v2_vect *d1, v2_vect *d2, v2_pos *ip)

{
  double m1, m2;
  int stat = true;

  if(d1->x != 0.0) m1 = d1->y / d1->x;
  if(d2->x != 0.0) m2 = d2->y / d2->x;

  if((d1->x != 0.0) && (d2->x != 0.0)) {
   double temp_x, m, b1, b2;

   m = m1 - m2;
   if (fabs(m) != 0.0){
      b1 = p1->y - m1 * p1->x;
      b2 = p2->y - m2 * p2->x;
      temp_x = (b2 - b1) / m;
      if((m1 == 0.0) || (m2 == 0.0)) {
       ip->x = temp_x;
       ip->y = ((b2 * m1) - (b1 * m2)) / m;
      } else {
       m1 = 1.0 / m1;
       m2 = 1.0 / m2;
       m = (m1 - m2);
       if (m != 0.0) {
          ip->x = temp_x;
          b1 = p1->x -  m1 * p1->y;
          b2 = p2->x -  m2 * p2->y;
          ip->y = (b2 - b1) / m;
       } else stat = false; /* Error: should never happen? */
      }
   } else stat = false; /* Error: parallel non-vertical lines */
  } else if(d1->x != 0.0) {
   ip->x = p2->x;
   m2 = p1->y - (p1->x * m1);
   ip->y =  (m1 * p2->x) + m2;
  } else if(d2->x != 0.0) {
   ip->x = p1->x;
   m1 = p2->y - (p2->x * m2);
   ip->y =  (m2 * p1->x) + m1;
  } else stat = false;     /* Error: parallel vertical lines */
  return stat;
}

/*
** Function ppp_circle -- Find circle passing through 3 given points
**
** Inputs:
**    p1   pointer to first given point
**      p2      pointer to second given point
**      p3      pointer to third given point
**    center  pointer to storage for circle center position values
**    radius  pointer to storage for circle radius value
**
** Return value: int
**    true    *center and *radius values valid -- circle was found
**    false   *center and *radius values undefined -- circle was NOT
**        found should only happen when passed 3 points on a
**        straight line
**
** For the ppp_circle function, if all three points are different the
** results are as expected, but note that . . .
**
**     if p1 and p2 are the same or p1 and p3 are the same the circle
** will be horizontally centered on p1 and pass thru all three points,
**
** and if p2 and p3 are the same then the center is calculated to
** be the midpoint of the line between them and p1.
*/
int ppp_circle(v2_pos *p1, v2_pos *p2, v2_pos *p3,
         v2_pos *center, double *radius)
{
  v2_vect d1, d2;
  v2_pos mp1, mp2;
  int have_center = true;

  /* calculate perpendicular slope vectors */
  d1.y = p2->x - p1->x;
  d2.y = p3->x - p1->x;
  d1.x = p1->y - p2->y;
  d2.x = p1->y - p3->y;

  /* calculate midpoint position values */
  mp1.x = (p1->x + p2->x) * 0.5;
  mp1.y = (p1->y + p2->y) * 0.5;
  mp2.x = (p1->x + p3->x) * 0.5;
  mp2.y = (p1->y + p3->y) * 0.5;

  if ((mp1.x == mp2.x) && (mp1.y == mp2.y)) {
   *center = mp1;
  } else have_center = line_intersect(&mp1, &mp2, &d1, &d2, center);

  if (have_center) *radius = v2_dist(center, p1);
  return (have_center);
}

=========== end of file ===========


следующий фpагмент (8)|пpедыдущий фpагмент (6)

- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS -
 Msg  : 86 of 109                                                               
 From : andres@dpt-info.u-strasbg.fr        2:5030/144.99   21 Jul 94  14:23:10 
 To   : All                                                 25 Jul 94  01:47:28 
 Subj : (1) Re: Best accurate circle drawing algo.                              
--------------------------------------------------------------------------------


Hello, this is a circle algorithm which will be published in
Computer&Graphics end of this year. It has some advantages, and
generalizes Bresenham's algorithm..

For Bresenham's algorithm, just look in Foley-Van Dam or other books (see
FAQ)..

The main idea of this circle is to solve the diophantine equations
x^2 + y^2 E [(R-1/2)^2,(R+1/2)^2[. It's not a completly new idea.
SN.Biswas and BB.Chaudhuri have already spoken about this definition in
"On the generation of discrete circles and their properties" CVGIP 32,
pp. 158-170 (1985), but they have proposed a very inneficient algorithm.
I think other people also thought about this def. but i haven't the
corresponding references.
The reason why this algo can be interesting is that :
- there are no gaps (in kulpa's meaning). A point of Z^2 belongs to one
and only one circle (considering same center and integer radii).
- math. defintion makes easy to define in, out and belonging to this
circle.
- extension to sphere immediate.
There are also problems :
- This def. is very difficult to analyse mathematically (PI is behind)
- extension to non-integer radii and center are not easy if we want to
respect the diophantine defs.
- and some other problems... or works, it depends on view point.

circle (x0,y0,R:integer)
begin algo
x:=0; y:=R; d:=R/2;
isodd:=R and 1;
plot4pixels(x0,y0,R)

while (y>x) do
        if (isodd) then x,y,d,isodd=ODD(x,y,d,R,isodd,x0,y0)
        else            x,y,d,isodd=EVEN(x,y,d,R,isodd,x0,y0)
        endif
        plot8pixels(x0,y0,x,y)  (A)
end while
end algo

WITH the functions :

ODD(x,y,d,R,isodd,x0,y0:integer)
begin function

if (d>x) then d := d-x-1; x:= x+1; isodd:=0;                         (B)

else if (d <= (R-y)) then y := y-1; plot8pixels(x0,y0,x,y);  (C)
     else  y:= y-1;
        (D)
     endif
     d:=d+y-x;
         (E)
     x:=x+1;
endif
return(x,y,d,isodd);
end function

EVEN(x,y,d,R,isodd,x0,y0:integer)
begin function

if (d>x) then d := d-x; x:= x+1; isodd:=1;                             (F)

else if (d <= (R-y)) then y := y-1; plot8pixels(x0,y0,x,y);  (G)
     else  y:= y-1;
        (H)
     endif
     d:=d+y-x;
         (I)
     x:=x+1;
endif
return(x,y,d,isodd);
end function

Let us try this algorithm for a circle with radius 6 :
T stands for True, and F for false.

pos. algo   values           x    y   d   isodd    plots
main        y>x : 6>0 T      0    6   3     0      plot (0,6)
even        d>x : 3>0 T      1    6   3     1                   (F)
main        y>x : 6>1 T      1    6   3     1      plot(1,6)    (A)
odd         d>x : 3>1 T      2    6   1     0                   (B)
main        y>x : 6>2 T      2    6   1     0      plot(2,6)    (A)
even        d>x : 1>2 F      2    6   1     0
even        d<=(R-y): 1<=0 F 3    5   4     0                   (H),(I)
main        y>x : 5>3 T      3    5   4     0      plot(3,5)    (A)
even        d>x : 4>3 T      4    5   1     1                   (F)
main        y>x : 5>4 T      4    5   1     1      plot(4,5)    (A)
odd         d>x : 1>4 F      4    5   1     1
odd         d<=(R-y): 1<=1 T 5    4   1     1      plot(4,4)    (G),(I)
main        y>x : 5>4 F      5    4   1     1      plot(5,4)    (A)

I hope that this exemple will help you.


следующий фpагмент (9)|пpедыдущий фpагмент (7)

******************************************************************************
*Draw circle around Center (d0,d1) with Radius (d2) in Plane (a5).
*Made by Patrick van Logchem (v912152@si.hhs.nl) on 7 June 1993.
******************************************************************************

center:
	dc.w	0,0

	cnop	0,8
	
Circle:
	lea	center(pc),a3
	movem.w	d0/d1,(a3)	; place center in buffer

	move.w	d0,d3
	sub.w	d2,d3		; d3 = -X

	lea	RowTab(pc),a4	; this table contains pre-calculated offsets
				; (with base 0) for every rasterline.
	move.w	d1,d4
	add.w	d4,d4
	move.w	(a4,d4.w),d4

	move.w	d3,d5
	asr.w	#3,d5
	sub.w	d5,d4
	bchg	d3,(a5,d4.w)
	add.w	d5,d4

	add.w	d2,d3
	add.w	d2,d3		; d3 = +X

	move.w	d3,d5
	asr.w	#3,d5
	sub.w	d5,d4
	bchg	d3,(a5,d4.w)

	moveq	#0,d0		; X = 0
	move.w	d2,d1		; Y = R

	move.w	d2,d6
	lsr.w	#1,d6		; D = R>>1
   
	bra.s	skip4

; make sure (with nop's) that cir_lp is on a 8 byte boundary for max speed.

cir_lp:
	cmp.w	d1,d5
	beq.s	skip4		; if(Y != Y_old) /* only plot in new rows */
	plot4	d0,d1		;  set (X,Y),(X,-Y),(-X,-Y),(-X,Y)
skip4:
	plot4	d1,d0		; set (Y,X),(Y,-X),(-Y,-X),(-Y,X)
	move.w	d1,d5		; Y_old = Y
   
	addq.w	#1,d0		; X += 1
	sub.w	d0,d6		; D -= X
	bgt.s	noYdec		; if(D < 0) {
	subq.w	#1,d1		;  Y -= 1
	add.w	d1,d6		;  D += Y }
noYdec:
	cmp.w	d0,d1		; while(X < Y)	/* not finished 1/8 part ?? */
	bgt.w	cir_lp		;  loop

	bne.s	SkipEqu		; if(X == Y)
	plot4	d0,d1		;  set (X,Y),(X,-Y),(-X,-Y),(-X,Y)
SkipEqu:
	rts

******************************************************************************
*Macro to set 4 simetrical pixels around ((middle),(middle+2)).
*\1 = x ,\2 = y (are not touched; d2-d5 are!)

plot4	MACRO
	movem.w	(a3),d2/d3	; get X and Y
	move.w	d3,d4		; and another Y
	add.w	\1,d2		; d2 = +X
	add.w	\2,d3		; d3 = +Y
	sub.w	\2,d4		; d4 = -Y

	add.w	d3,d3		; make offset +Y
	add.w	d4,d4		; make offset -Y
	move.w	(a4,d3.w),d3	; d3=Width/8 * +Y
	move.w	(a4,d4.w),d4	; d4=Width/8 * -Y

	move.w	d2,d5
	asr.w	#3,d5		; d5=X/8
	sub.w	d5,d3
	sub.w	d5,d4
	bchg	d2,(a5,d3.w)	; (+X,+Y)
	bchg	d2,(a5,d4.w)	; (+X,-Y)

*Note: when changing this in to bfchg, speed DEcreases, so 4get it !

	add.w	d5,d3
	add.w	d5,d4

	sub.w	\1,d2
	sub.w	\1,d2		; d2 = -X

	move.w	d2,d5
	asr.w	#3,d5		; d5=X/8
	sub.w	d5,d3
	sub.w	d5,d4
	bchg	d2,(a5,d3.w)	; (-X,+Y)
	bchg	d2,(a5,d4.w)	; (-X,-Y)
	ENDM

******************************************************************************

следующий фpагмент (10)|пpедыдущий фpагмент (8)

- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS -
 Msg  : 101 of 122                                                              
 From : andres@buffnet.net                  2:5030/315      24 Oct 95  19:21:10 
 To   : All                                                 26 Oct 95  05:06:00 
 Subj : Re: Q: Circle Alg with no holes                                         
--------------------------------------------------------------------------------

In article <46j35p$up@mksrv1.dseg.ti.com>, toddl@hsxsrv.dseg.ti.com wrote:

> Is there an algorithm which will produce a circle, such that successive
> integer radius values do not produce holes in the display.
>
> Did I explain that right.  Here is another way.  Using borland graphics
> libraries, the following code:
>   for(r=0;r<400;r++)
>   {
>     circle(x,y,r);
>   }
>
> produces "holes" in which the algorithm did not hit every pixel in the
> raster.
>
> Is there a circle algorithm which leaves no holes, yet is comparable in
> speed to the breshenham circle algorithm?
>

Hi, I published such an algorithm in Computer & Graphics, vol. 18, n¦5,
pp. 695-706, 1994 under the title "Discrete circles, rings and spheres",
E.ANDRES.

Here is the algorithm, you'll find explanaitions in the paper:
I'll write it in a pseudo language, so whatever you program, you should
understand it. If you have any problems, send an e-mail.

BASIC ALGORITHM (xo,yo,R:integer)
{
x=0; y=R; d=R/2;
isodd=R and 1;
plot_4_pixels(xo,yo,R);    /* plots 4 pixels (xo,0),(-xo,0),(0,yo),(0,-yo) */
while (y>x) do
{  if (isodd) then  {x,y,d,isodd = ODD(x,y,d,R,isodd,xo,yo);}
              else  {x,y,d,isodd = EVEN(x,y,d,R,isodd,xo,yo);}
   endif
   plot_8_pixels(xo,yo,x,y);     /* plot 8 pixels (xo+-x,yo+-y),(xo+-y,yo+-x) */
}
}  /* end algorithm */

with

ODD(x,y,d,R,isodd,xo,yo:integer)
{
   if (d>x) then  {d=d-x-1; x=x+1; isodd=0;}
   else { if (d<=(R-y)) then {y=y-1; plot_8_pixels(xo,yo,x,y);}
          else {y=y-1;}
          endif
          d=d+y-x; x=x+1;
        }
   endif
   return(x,y,d,isodd);
}

EVEN(x,y,d,R,isodd,xo,yo:integer)
{
   if (d>x) then  {d=d-x; x=x+1; isodd=1;}
   else { if (d<=(R-y)) then {y=y-1; plot_8_pixels(xo,yo,x,y);}
          else {y=y-1;}
          endif
          d=d+y-x; x=x+1;
        }
   endif
   return(x,y,d,isodd);
}

Be careful there IS a slight difference between ODD and EVEN (line 3 of
these functions).
Send me an e-mail if the algorithm doesn't work fine. They made a couple
of mistakes when they published the article and I haven't my original
notes with me now.

The speed of the algorithm is comparable to McIlroy's algorithm and
slightly slower than Kuzmin's if you consider the number of operations
needed to generate one point. There is nevertheless 10% more points (the
holes) generated than in the other algorithms (improvments of Bresenhams
original algorithm) so the algorithm is 10% slower.

For example:
Bresenham : 2.85
McIlroy :   0.80
Kuzmin :    0.61
This algo:  0.76+10%=0.83

Last thing.. this circle, called arithmetical circle verifies the
following formula : (R-1/2)^2 <= x^2 + y^2 < (R+1/2)^2 <=> R^2-R < x^2+y^2
<= R^2+R. This means that contrary to Bresenham's circle, you can her very
easily verify if a point is in on or outside a circle.

Good luck and send me a e-mail if it works.

Dr. Eric ANDRES


следующий фpагмент (11)|пpедыдущий фpагмент (9)

- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS -
 Msg  : 11 of 15                                                                
 From : OKRA@max.tiac.net                   2:5030/144.99   06 Aug 94  18:08:46 
 To   : All                                                 07 Aug 94  05:00:10 
 Subj : Re: Filled Circles                                                      
--------------------------------------------------------------------------------

WU  DAVID S (wudavid@ecf.toronto.edu) wrote:

: Anyway, if anyone know a good quick, breshman related algorithim,
: please let me know.

  Here's the Bresenham method that I implemented - fiddle with it to get
it to do filled circles.


/*** circle routine for mode 13h - performs no clipping */

void Circle_13(int Ox, int Oy, int radius, int color) {

  int  x,y;                         /* keep track of position on circle */
  int  d;                               /* decision variable */
  int  Xmajor1,Xmajor2,Xmajor3,Xmajor4, /* x-major slice in each quadrant */
       Ymajor1,Ymajor2,Ymajor3,Ymajor4; /* y-major slice in each quadrant */

  d = 3 - (2 * radius);
  x = 0;
  y = radius;
  Xmajor1 = (Oy - radius) * 320 + Ox;
  Xmajor2 = Xmajor1;
  Xmajor3 = (Oy + radius) * 320 + Ox;
  Xmajor4 = Xmajor3;
  Ymajor1 = Oy * 320 + Ox + radius;
  Ymajor2 = Oy * 320 + Ox - radius;
  Ymajor3 = Ymajor2;
  Ymajor4 = Ymajor1;

  for (x=0; x<=y; x++) {
    screen[Xmajor1] = color;            /* draw eight pixels at a time */
    screen[Xmajor2] = color;
    screen[Xmajor3] = color;
    screen[Xmajor4] = color;
    screen[Ymajor1] = color;
    screen[Ymajor2] = color;
    screen[Ymajor3] = color;
    screen[Ymajor4] = color;
    if (d < 0)
      d += (4 * x) + 6;
    else {
      d += 4 * (x - y) + 10;
      y--;
      Xmajor1 += 320;
      Xmajor2 += 320;
      Xmajor3 -= 320;
      Xmajor4 -= 320;
      Ymajor1--;
      Ymajor2++;
      Ymajor3++;
      Ymajor4--;
    }
    Xmajor1++;
    Xmajor2--;
    Xmajor3--;
    Xmajor4++;
    Ymajor1 += 320;
    Ymajor2 += 320;
    Ymajor3 -= 320;
    Ymajor4 -= 320;
  }
}





Всего 10 фpагмент(а/ов) |пpедыдущий фpагмент (10)

Если вы хотите дополнить FAQ - пожалуйста пишите.

design/collection/some content by Frog,
DEMO DESIGN FAQ (C) Realm Of Illusion 1994-2000,
При перепечатке материалов этой страницы пожалуйста ссылайтесь на источник: "DEMO.DESIGN FAQ, http://www.enlight.ru/demo/faq".