View Single Post
Old 19th December 2009, 20:31   #24  |  Link
StainlessS
HeartlessS Usurer
 
StainlessS's Avatar
 
Join Date: Dec 2009
Location: Over the rainbow
Posts: 10,980
@ Gavino,

I shall edit the GScipt(""" stuff to outside the function, thought it was purely compile time.

After getting it working recursively, I did spend about 10 mins converting using while loop, but
thought, 'sod it, why bother'. It can be more difficult than recursive, the iterative Euclid() thing
runs quite a lot quicker than rercursive, and in Knuth, (maybe Fundamental Algorithms) he
does a fairly longer iterative version that is quite a bit faster than that. If it could be converted
to iterative, it would not be too difficult a job to make it run without GScript (Eval), but would
not want to even try doing it that way without something that already worked.

I have not really done any coding [other than my new filter Exblend() as posted on doom Dec 2nd],
for about 14 years. Did quite a bit of graphics type stuff, quick drawing of lines, circles, ellipse,
torus etc, using something called DDA. Cannot for the life of me remember what its called [DDA],
nor anything about how it works. Was thinking that maybe I could use it [DDA] in doing a direct
conversion from 23.976 to 25 FPS (instead of a 24FPS interim conversion).
Could you please take a quick look at the below comments from a function I wrote about 16 or 17
years ago, I cant make head nor tail of it and dont even know what to look for on the net,
looked DDA up on Wikipedia, got something completely unrelated.

See Below:-


Code:
void wrcircle0(int xc,int yc,int r,int pen)
{
/*                  circle
  Single pixel render version (ie wrpixel()).
  Draw a lovely round circle on a 1:1 aspect ratio device using a DDA.
  Uses equation of circle:-
    x*x + y*y <= r*r  
      where pixel is exactly on circumference of circle when the
      equation balances exactly.
  We wish for rounding to the nearest pixel using the distance from the
  origin to the circumference ie
    sqrt(x*x + y*y) <= r + 0.5
    The above in effect calculates the distance from the centre of the
  origin to the centre of the target pixel (ie the coords themselves are
  NOT rounded, simply the distance from centre to centre) and it is the
  radius that is rounded rather than the x,y coords.
  We need the pixel that provides the greatest distance from the 
      origin while maintaining the above relationship.
  We want to re-write in the form of the first equation so
    x*x + y*y <= (r + 1/2)*(r + 1/2)
  Expanding the right hand side we get
    x*x + y*y <= r*r + r + 1/4
  As (x*x + y*y) never produces a fractional result, we can drop the 1/4
  from the equation without affect.
  Rewriting:-     
    x*x + y*y - r*r - r <= 0
      where ((r*r) - r) is constant and (x*x) and (y*y) vary
      and can be calculated easily without multiplication as we step
      through the x,y coordinates.
  Where 
    n           -1    0   1   2   3   4 
    (n*n)         -1    0   1   4   9   16  
    (n*n)-((n-1)*(n-1))     -1    1   3   5   7   
    diffstep            2   2   2   2

  The difference (n*n) - ((n-1)*(n-1)) cancels to:-
    2n - 1 and varies by diffstep (2) when stepping through x,y coords.
  The threshhold at x,y of (0,r) is calculated as
    (0*0) + (r*r) - (r*r) - r which cancels to  (-r).
    We step coords clockwise from  top centre (0,r) to (r,0). We check
  first that x+1,y is ok to print and if so we move RIGHT (From our
  rotation and the perfect aspect ratio, the pixel to the right of current
  is ALWAYS further away and always furthest possible if plottable), if
  this fails then we KNOW we have to check 1 DOWN and RIGHT of current as
  this is always next possible longest radius, if plottable we move DOWN
  and RIGHT, otherwise we KNOW that 1 down from current is always closer
  than current so we do not need to check whether its plottable and so we
  move DOWN.
    The above method ensures that plotted points are no more than 1
  pixel from the previous one (counting diagonal as one) and so leaves
  no gaps in the circle.
    To save complications, when plotting 4 quadrants we plot in 2
  parts, the initial top and bottom middle pixels are plotted first
  and it then loops to find the next coords, plots two of those and waits
  until the next loop to do the same coords in the other quadrants.
  This removes the necessity to plot the top, bot, left, and right centre
  pixels as special cases (Otherwise plots same pixels twice).
    Have tested from radius 1 to 1500 and NO pixels overlap any other
  plotted pixels therefore not affecting XOR type operations.
    DONT CHANGE algorithm without good cause.
  Further, To calculate the upper coord of the vertical cord where x==r
  we use:-
    y*y <= (r*r) + r + 1/4 - (x*x)
  As (x == r) and 1/4 will not take any significance we rewrite as:-
    y*y <= r  OR y = (int)sqrt(r);  (Fract part discarded)
  This algorythm does produce the occasional extra pixel at 45 degrees
  which results in a pointy bit instead of a smooth diagonal, however,
  as there are only about 5 instances with a radius less than 10,000 and
  only 4 less than 1000 radius (ie 1, 8, 49, 288). We we could eradicate
  this but do not due to the overhead of detection for such a small
  improvement. [ if((thresh <= 0)&&((x+1)!=y)) step right ELSE step left].
  NOTE, At radius == 1, the aforesaid pointy bit is desired.
*/
long  thresh; /* Needs long (ranges about  +- 2r ) */
long  xd;   /* Needs long (ranges about -1 to 2(r+1) - 1) */
long  yd;   /* Needs long (ranges about -1 to 2r - 1) */
int x,y,terminate,tem;
const   long diffstep = 2L;       /* long to avoid size extension */
  if  (
    (r<=0)        ||
    ((yc-r) > clip[3])  ||
    ((yc+r) < clip[1])  ||
    ((xc-r) > clip[2])  ||
    ((xc+r) < clip[0])
    )return;
  /* Clip thresh, (-ve if fully within clipping area ) */
  if((terminate=clip[1]-yc)<(tem=yc-clip[3]))
    terminate = tem;
  x=0;y=r;    /*  Preset plot at (0,r) and init thresh for (1,r)  */
  yd  = (2L*r - 1L);            /* yd(r) */
  xd  = (2L*0 - 1L + 2L);         /* xd from 0 to 1 */
  thresh  = (-r);             /* thresh(0,r) */
  thresh += xd;             /* thresh(1,r) */
  while((y > 0)&&(y >= terminate))
    {
    wrpixel(xc + x ,yc - y,pen,NULL); /* quad 1 (And starting plot) */
    wrpixel(xc - x ,yc + y,pen,NULL); /* quad 3 (And starting plot) */
    if(thresh <= 0)   /* Can we do (x+1,y), 1 to RIGHT of current */    
      {           /* Yes, step x Right */
      xd  +=  diffstep;   /* xd from x+1 to x+2 */
      thresh  +=  xd;     /* thresh(x+2,y) */
      ++x;          /* This is longest poss radius, DONE */
      }
    else
      {           /* No, stepping y Down */
      thresh  -=  yd;     /* thresh(x+1,y-1) */
      yd  -=  diffstep;   /* yd from y to y-1 */
      if(thresh <= 0)/* Can we do (x+1,y-1), 1 dwn, 1 RGT of current */
        {         /* Yes, stepping both DOWN and RIGHT */
        xd  +=  diffstep; /* xd from x + 1 to x + 2 */
        thresh  +=  xd;   /* thresh(x+2,y-1) */
        ++x;
        }
      --y;              /* Dont forget to DOWN step y */
      }
    wrpixel(xc - x ,yc - y,pen,NULL); /* quad 2 (And closing plot) */
    wrpixel(xc + x ,yc + y,pen,NULL); /* quad 4 (And closing plot) */
    }
}
Any of that mean anything to you? Beats the hell out of me what it is.

PS, Seem to remember that the DDA thing tends to use
XD, YD and Diffstep, whether in line drawing or any other use.
StainlessS is offline   Reply With Quote