Bresenham's Circle Drawing algorithm

[adam2016]

Hi guys,

so if you read my last post you would know that I'm experimenting with graphics and drawing and interacting with geometric shapes, so drawing a rectangle is simple enough but when it comes to drawing a circle there are two different algorithms that will map the pixels to be drawn to that circle.

I have read the wiki page and followed a couple of pages but all seem to be quite rudimentary, this page details the algorithm the best - https://getsetcg.blogspot.com/2018/10/bresenhams-circle-drawing-derivation.html

It's the best out of a bad bunch,

but could anybody tell me what math is involved here? is it differentiation calculus? is it trig?

there are so many different equations, I can't seem to spot what there form is and why so many are used?

thanks :)

[jonnin]

looks like algebra & geometry combined to me.
its a derivation. you only need the result (which is provided in the C code linked on the site): this is an excessive bunch of junk about how to get from A to B. You just need B, you don't give a rat's rear where it came from when writing the code (you may, intellectually, care, but it has no bearing on the coding).

its like how in calc they spend a week showing you a stupid 2 page formula to deal with the derivative of the division of 2 polynomials. And then you realize that you can invert and multiply in 1/100th the work. The division formula and how they got it is cool and all, but its useless if you just want to get the freaking answer.

I would just iterate something simple myself. This looks like a lot of trouble. Solve some simple form for 0-90 degrees and when you draw mirror to all 4 quadrants per pixel (or line segment, if pixel is a no-go)

[Duthomhas]

The math is basic algebra, using the equation of a circle. You can follow along much easier if you look at the Midpoint Circle Algorithm. What Bresenham did was derive a way to do it using integer arithmetic instead of playing with floats. Back in the day that made a huge difference in observable execution speed.

Bresenham’s graphics algorithms work by keeping track of an error margin. The choice of next pixel [ (x+1, y) or (x+1, y+1) ] is made based on whether that margin would be breached by the next computation. At each step, that error value is adjusted appropriately.

[adam2016]

@jonnin very true , not sure if it's the same but we had to learn how to differentiate from first principles I think it's f'(x) = f(x+h) - f(x) / h rather than just using the power rule which takes a fraction of the time.

@Duthomhas thanks :) I'll have to look into the midpoint circle algorithm, that I will do asap :)

[jonnin]

its much unlike jonnin's circle drawing algorithm. Granted ascii art does not really look too great. 50,50 is the center of the circle. adjust what you add to the double to fit your graphics engine scale. Pixels don't really work in practice: zoom in too far and it gets ugly. Better to draw lines between the points, and less points. But you get the idea, I hope..

There is a cute recursive sphere drawing approach for 3-d to get the triangle faces.

int main()
{
   double p2 = 1.571; //pi/2
   double rad = 20.0;
   bool fakescreen[100][100] = {0};
   int  y, x;
   
   for(double d = 0; d <= p2; d+=0.001)
   {	  
      y = (int)(sin(d)*rad);	  
	  x = (int)(cos(d)*rad);	
	  fakescreen[50+y][50+x] = true;
	  fakescreen[50-y][50+x] = true;
	  fakescreen[50+y][50-x] = true;
	  fakescreen[50-y][50-x] = true;
   }
   for(int i = 0; i < 100; i++)
   {
	 for(int j = 0; j<100; j++)
	 {
	   if(fakescreen[i][j]) cout << '*';
         else cout << ' ';	   
	 }	
	 cout << endl;
   }	 	
}

[poteto]

Not sure if this is a question about math, but the midpoint circle algorithm seems like a perfectly fine way of drawing circles, if not the best way (ignoring hardware rendering, which in that case you would either bake into a texture, or just draw a bunch of lines using the same algorithm, but upscaled).

This is SDL1.2 code (it is a bit intense to convert it to SDL2 for a beginner, especially if you aren't fluent in C), but it should be common sense to translate it to any pixel drawing API.

https://web.archive.org/web/20160326085538/http://content.gpwiki.org/index.php/SDL:Tutorials:Drawing_and_Filling_Circles