Lately I have been thinking about a way to draw a circle without the use of the sine and/or cosine and I thought of a way which I am not sure is the best way to do this.

Let?s say we are given the center point of the circle and its radius. We can now create a loop which iterates from Center.x-Radius to Center.x+Radius or maybe even downwards from Center.x+Radius to Center.x-Radius. Now we have one point on the radius which is the center of the circle and one point which we have the X to, which is located on the circumference. We can then calculate the Y position of this point using the distance formula as in:

Radius = Sqrt ((P1.x - P2.x) ^2 + (P1.y - P2.y) ^2)

We have the radius and the x, y position of the first point and also the x position of the second point, therefore, we are only left to find the y position of the second point. The final x and y position of the second point would be a point on the circumference, wouldn?t it be?
Posted on 2006-12-29 23:06:00 by XCHG
Yes you can calculate circles this way, but be aware that you're still using trigonometry - you're merely expressing the trigonometric equations in a different way.

SOH CAH TOA
Posted on 2006-12-29 23:37:46 by Homer
Its still a nice way of showing that numbers are just dimensionless ratios no matter how complex we think equations are.

e.g
cos(x) = 1- (x^2/2!) + (x^4/4!) ......

just the sum of ratios

Nicely done XCHG
Posted on 2006-12-30 16:15:04 by IIwastitan
XCHG,

    Wouldn't it be more concise to assume a radius of 1.  Then define the x-range from -1 to +1 and step it in say 200 steps, so that you need to compute the corresponding y-value of x from -1,-.99,-.98,-97,...,0,.01,.02,.03,...,.97,.98,.99,1 .  Then the y-values can be calculated simply by Pythagoras's theorem, which is plus or minus SQRT(1-X^2) for each x-value.  If the radius is greater than 1, the x and y values can easily be scaled up.  Ratch
Posted on 2006-12-30 21:54:33 by Ratch
IIwastitan,

...  sin(x) = 1- (x^2/2!) + (x^4/4!) ......  ...


    The formula you gave is for the cos, not the sin.  Ratch
Posted on 2006-12-30 21:58:41 by Ratch
IIwastitan,

Isn't that like a very twisted interpretation of taylor's expansion?
Posted on 2006-12-30 22:23:33 by roticv
Look up Bresenham's Circle Algorithm.  It's very simple and doesn't need anything more than bit shifting and addition/subtraction, so it's highly regarded as the fastest circle drawing algorithm.  The more general version of the algorithm also applies to arbitrary curves, and the line-specific version is very fast.

I hope this helps.  :)
Posted on 2006-12-30 22:49:32 by hackulous
Just to ditto Bresenham's algo.  It is the most often used method.
Posted on 2006-12-31 23:04:42 by drhowarddrfine
Ratch,

I believe that the Pythagorean Theorem states that in the right triangle, the length of the hypotenuse squared is equal to the sum of the squares of the other two sides. Therefore, if I have the x position which is put in iteration for example from -1 to +1 in a unit circle and I also have centre point I don?t think that I would be merely able to calculate the y position using that formula.

In that case, I will first have to find the line formula for the side of the right triangle with one point at the center and one at the x position in the iteration which is pretty easy with a fixed slope for infinite points on the vertical line. After that I have to find where the hypotenuse and the other side of the triangle intersect which would be a point on the circumference. Or maybe I?m wrong?!



hackulous,

I hadn?t heard about this algorithm but I sure will search for it in Google and see what comes up. Thank you.



drhowarddrfine,

I?ll look for that too, thanks.

Posted on 2007-01-01 02:10:55 by XCHG

i have seen an algo that claims to be faster than bresenham, although  based on it.

its called frith 's algo.

it was hidden in a pile of demoscene resources and now its not online anymore. i had that  on a harddrive... tha crashed some time ago. lesson: donttrust the internet! grab what you can when you can. make backups! i found it again somewhere, but without some comments. they said there was an asm version with a big speed increase. there was also an asm line drawing based on ADC and i think it was 1 instruction/pixel.
the academic algos that everyone quotes are not necessarly the best ever crafted.

demomakers rule!

http://www.java-tutor.com/aufgaben/j/insel/additives/base/fcircle.txt

and yeah, i know its based on setpixel. i guess its up to you to make an vram-address- based algo out of this and/ of to convert to  assembly... :)

bye.
Posted on 2007-01-01 06:05:41 by HeLLoWorld
lesson: donttrust the internet! grab what you can when you can. make backups!
1000% agree!
Posted on 2007-01-01 09:28:20 by drhowarddrfine
From working at D-Wave Systems on quantum-computer-related stuff, I'm well aware that theoretical ideas quite often don't work nearly as well in practice.  However, an algorithm is not its implementation.  You can make implementations of Bresenham's algorithms that are much faster than coding them "straight up", but it's just a good implementation of the same algorithm.  That said, Frith's algorithm does appear not to be Bresenham's circle algorithm, but it is in the general class of Bresenham curve-drawing algorithms because it uses a balance variable that causes one action when below zero and another when above zero.  From the looks of it, it might or might not be much faster than Bresenham's circle algorithm once both are optimized.  Also, one instruction per pixel is impossible unless you've got a horizontal line and do it with "rep movsd", because to have a loop that draws a line, you need at least two instructions to update x and y, one instruction to set the pixel value, and one instruction to jump back.

On a semi-related note, the code in fcircle.txt does use dangerous syntax for C/Java that may produce different execution from different compilers, namely using a prefix/postfix ++/-- operator on a variable that is used elsewhere in the line.  Some compilers have the ++/-- executed in left-to-right order, some in right-to-left order, and some leave them until after everything else on the line has been evaluated, so I'm not sure which his code is assuming.  In Java I think it's standardized to left-to-right, and both VC++ and GCC do something different.  Try out "a += a++ + ++a + a;" or something else crazy like that to see the differences.

Edit: Sorry, my statement of "highly regarded as the fastest" is a gross generalization and shouldn't be given a lot of weight.  It's just that it's hundreds of times faster than trying to use stuff with square roots or trigonometry.
Posted on 2007-01-01 11:45:41 by hackulous

From working at D-Wave Systems on quantum-computer-related stuff,


man, is that cool or what :)


However, an algorithm is not its implementation.  You can make implementations of Bresenham's algorithms that are much faster than coding them "straight up", but it's just a good implementation of the same algorithm


mmy views quite differ.i see noabsolute differencebetween algo and implementation, no clear line. you could write an algo in C.youcould write an implementation in C. its just you further refine the code,thinking at how the machine will execute it.to my eyes,if you switch from setpixel-based to vram-based, youve just changed your algo, or at least refined.. because then vith vram you can do things you couldnt otherwise.


That said, Frith's algorithm does appear not to be Bresenham's circle algorithm

i seem to recall the original file said the algo had been designed while trrying to improve on bresenham. yes that  doesnt mean its based onto it.


lso, one instruction per pixel is impossible unless you've got a horizontal line and do it with "rep movsd", because to have a loop that draws a line, you need at least two instructions to update x and y, one instruction to set the pixel value, and one instruction to jump back.


i suppose youre perfectly right and  im  wrong.:)
it must have  been  3 or 4 ops.


On a semi-related note, the code in fcircle.txt does use dangerous syntax for C/Java that may produce different execution from different compilers, namely using a prefix/postfix ++/-- operator on a variable that is used elsewhere in the line.  Some compilers have the ++/-- executed in left-to-right order, some in right-to-left order, and some leave them until after everything else on the line has been evaluated, so I'm not sure which his code is assuming.  In Java I think it's standardized to left-to-right, and both VC++ and GCC do something different.  Try out "a += a++ + ++a + a;" or something else crazy like that to see the differences.


i also think thistype of coding quite sucks, its confusing for me. if on  top  of that its ambiguous even to compiler as you say, its not kewl at all. but sems experienced coders liked it back in the days.
btw in the src it seems "&"  means "&&" and ";=" means "!="

Edit: Sorry, my statement of "highly regarded as the fastest" is a gross generalization and shouldn't be given a lot of weight.  It's just that it's hundreds of times faster than trying to use stuff with square roots or trigonometry.


yes, ofcourse. no problem!

btw  my keyboardsucks bigtime. :)

Posted on 2007-01-01 14:08:08 by HeLLoWorld
btw in the src it seems "&"  means "&&" and ";=" means "!="


no... gt and lt dont look like variables...  maybe greater  than and  lessthan?

dont understand  thecode anyhow :)
strange
Posted on 2007-01-01 14:18:22 by HeLLoWorld

btw in the src it seems "&"  means "&&" and ";=" means "!="

no... gt and lt dont look like variables...  maybe greater  than and  lessthan?


It's escaped for HTML or something, because &lt; and &gt; are standard HTML/XML entities.  "&lt;" is "<" and "&gt;" is ">".  So, it actually reads:
void FCircle(int x, int y, int radius, uchar color)
{
  int balance, xoff, yoff;

  xoff = 0;
  yoff = radius;
  balance = -radius;

  do {
    SetPixel(x+xoff, y+yoff, color);
    SetPixel(x-xoff, y+yoff, color);
    SetPixel(x-xoff, y-yoff, color);
    SetPixel(x+xoff, y-yoff, color);
    SetPixel(x+yoff, y+xoff, color);
    SetPixel(x-yoff, y+xoff, color);
    SetPixel(x-yoff, y-xoff, color);
    SetPixel(x+yoff, y-xoff, color);

    if ((balance += xoff++ + xoff) >= 0)
      balance -= --yoff + yoff;

  } while (xoff <= yoff);
}


I think it might be faster with the loop unrolled by octant, so with that in mind, the optimized function might be something like the following (assuming that the compiler does left-to-right evaluation of the prefix/postfix operators).  If done with the single loop, all 8 buffer addresses would need to be calculated instead of just keeping track of one.


FCircle proc x:DWORD,y:DWORD,Radius:DWORD,Colour:DWORD,BufferStart:DWORD,BytesPerRow:DWORD
pusha
xor ebx,ebx
mov ecx,Radius
mov esi,ecx
neg ecx

mov eax,esi
add eax,y
mul BytesPerRow
mov edx,x
lea eax,
add eax,BufferStart

mov edi,Colour

NextPixel0:
mov ,edi

lea ecx,
inc ebx
add eax,4
test ecx,ecx
js NoYAdjust
dec esi
sub eax,BytesPerRow
sub ecx,esi
sub ecx,esi
NoYAdjust:
cmp ebx,esi
jbe NextPixel0


;other 7 octants
...


popa
ret
FCircle endp


Working at D-Wave on co-op was really awesome.  They've got their first big public demo sometime in January, February, or March 2007.  It'll be the world's first demonstration of a quantum computer being used for practical problems, and also the world's first demonstration of a 16-qubit quantum computer.  Check out http://dwave.wordpress.com/ for the latest.  I was even fortunate enough to get to write one of the two applications they'll be demoing (the molecule comparison one).  :D
Posted on 2007-01-01 15:15:29 by hackulous

cant yet  understand what d-wave and co op is about, but itseems tremendous...

we programmers maybe soon will be  outdated when new methods, "hardware " and thinking will show up...
Posted on 2007-01-01 16:02:42 by HeLLoWorld

we programmers maybe soon will be  outdated when new methods, "hardware " and thinking will show up...


Even once quantum computers are eventually able to do a lot, there will still be a lot of thinking for people to do, so don't worry.

As for Frith's algorithm, I went through the derivation, and it is indeed just a simple transformation of Bresenham's Circle Algorithm.  It starts with:


d = 3 - (2*Radius);
x = 0;
y = Radius;
do {
    SetPixels();
    if (d < 0) {
        d += 4*x + 6;
    }
    else {
        d += 4*(x-y) + 10;
        --y;
    }
    ++x;
} while (x<=y)


Then divide all references to d by 2 and then subtract 1.5 from its value:

d = -Radius;
x = 0;
y = Radius;
do {
    SetPixels();
    if (d < -1.5) {
        d += 2*x + 3;
    }
    else {
        d += 2*(x-y) + 5;
        --y;
    }
    ++x;
} while (x<=y)


Then move the 2*x+3 out of the if and subtract that from the 2*(x-y)+10:

d = -Radius;
x = 0;
y = Radius;
do {
    SetPixels();
    d += 2*x + 3;
    if (d-(2*x+3) >= -1.5) {
        d += -2*y + 2;
        --y;
    }
    ++x;
} while (x<=y)


Then subtract 2x+2 from the value of d by adding 2 fewer to it every iteration:

d = -Radius;
x = 0;
y = Radius;
do {
    SetPixels();
    d += 2*x + 1;
    if (d-1 >= -1.5) {
        d += -2*y + 2;
        --y;
    }
    ++x;
} while (x<=y)


Then take into account that d being an integer makes "d-1 >= -1.5" equivalent to "d >= 0", and put the "--y" into the updating of d:

d = -Radius;
x = 0;
y = Radius;
do {
    SetPixels();
    d += 2*x + 1;
    if (d >= 0) {
        d -= 2*(--y);
    }
    ++x;
} while (x<=y)


That's pretty much all, and now I know that he did intend left-to-right evaluation order.  Fun stuff  :)
Posted on 2007-01-01 17:31:38 by hackulous

IIwastitan,

Isn't that like a very twisted interpretation of taylor's expansion?


No its the exponential form of cos(x)

cos(x) = 1 - (x^2/2!) + (x^4/4!)-...  (An even function)
sin(x) = x -(x^3/3!) + (x^5/5!)....      (An odd function)

add both series together but keep all signs positive and you have

e^x = 1 + x+ (x^2/2!) + (x^3/3!).....

So e^ipi + 1 =0
Eulers famous paradox
Posted on 2007-01-03 15:25:09 by IIwastitan