2

Suppose I have a NxN matrix, where each cell is a 1x1 white square.

Suppose I have a position P and a radius R. I want to paint all the cells of the circle of radius R centered in P.

Of course I could do this:

for(int i = P.x - R; i < P.x + R; i++)
    for(int j = P.y - R; j < P.y + R; j++)
        if (distance from P to (i,j) < R)
            Paint(i,j)

But as I will run this code on a shader that will execute every frame, I'd like to know a faster way to find the correct cells instead of asking the distance for each cell, which is slow.

Is there a smarter way?

Daniel
  • 7,357
  • 7
  • 32
  • 84
  • Is this making circle on circumference or filling the cells of the circle? – nice_dev Oct 05 '20 at 17:18
  • filling everything inside the circle. – Daniel Oct 05 '20 at 17:31
  • Ok, so very unlikely to paint a cell without visiting them. – nice_dev Oct 05 '20 at 17:33
  • Yes. I'm looking for a smart way to visit cells, so that I don't need to look at cell that won't be visited. – Daniel Oct 05 '20 at 17:36
  • 2
    You may be looking for You are looking for the [Brezenham's circle algorithm](https://www.gamedev.net/tutorials/programming/graphics/bresenhams-line-and-circle-algorithms-r767/) or [Midpoint circle algorithm](https://en.wikipedia.org/wiki/Midpoint_circle_algorithm). – Victor Sergienko Oct 05 '20 at 20:40
  • https://stackoverflow.com/questions/1201200/fast-algorithm-for-drawing-filled-circles/1201304#1201304 – AakashM Oct 07 '20 at 13:04

1 Answers1

2

You could for each given height of the circle calculate its segment width and fill it out completely.

You'd go from y = P - R to P + R filling all points in the chord (circular segment).

For the length of the chord just use formula (9) from here.

hbejgel
  • 4,674
  • 2
  • 17
  • 27