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?

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?

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

SOH CAH TOA

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

e.g

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

just the sum of ratios

Nicely done XCHG

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

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

IIwastitan,

The formula you gave is for the cos, not the sin. Ratch

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

The formula you gave is for the cos, not the sin. Ratch

IIwastitan,

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

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

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. :)

I hope this helps. :)

Just to ditto Bresenham's algo. It is the most often used method.

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.

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.

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.

lesson: donttrust the internet! grab what you can when you can. make backups!

1000% agree!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

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.

**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.

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. :)

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

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 < and > are standard HTML/XML entities. "<" is "<" and ">" 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

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...

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 :)

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