Drawing a smooth circle as described by Xaolin Wu

Question

I use the command "Quick Smoothing the Environment Generator" described by Xiaolin Wu in his article "Effective Smoothing Technique" from Siggraph'91.

This is the code I wrote using Python 3 and PySDL2:

def draw_antialiased_circle(renderer, position, radius): def _draw_point(renderer, offset, x, y): sdl2.SDL_RenderDrawPoint(renderer, offset.x - x, offset.y + y) sdl2.SDL_RenderDrawPoint(renderer, offset.x + x, offset.y + y) sdl2.SDL_RenderDrawPoint(renderer, offset.x - x, offset.y - y) sdl2.SDL_RenderDrawPoint(renderer, offset.x + x, offset.y - y) i = 0 j = radius d = 0 T = 0 sdl2.SDL_SetRenderDrawColor(renderer, 255, 255, 255, sdl2.SDL_ALPHA_OPAQUE) _draw_point(renderer, position, i, j) while i < j + 1: i += 1 s = math.sqrt(max(radius * radius - i * i, 0.0)) d = math.floor(sdl2.SDL_ALPHA_OPAQUE * (math.ceil(s) - s) + 0.5) if d < T: j -= 1 T = d if d > 0: alpha = d sdl2.SDL_SetRenderDrawColor(renderer, 255, 255, 255, alpha) _draw_point(renderer, position, i, j) if i != j: _draw_point(renderer, position, j, i) if (sdl2.SDL_ALPHA_OPAQUE - d) > 0: alpha = sdl2.SDL_ALPHA_OPAQUE - d sdl2.SDL_SetRenderDrawColor(renderer, 255, 255, 255, alpha) _draw_point(renderer, position, i, j + 1) if i != j + 1: _draw_point(renderer, position, j + 1, i) 

This is a naive implementation of what I think is described in his article, except that I assigned a value of radius j instead of i , because either I misunderstand or there is an error in his article. In fact, it initializes i value of radius j from 0 , and then determines the condition of the cycle i <= j , which can be true only when the radius is 0 . This change led me to make some other minor changes to what is described, and also change if d > T to if d < T simply because otherwise it looked broken.

This implementation works mostly well, except at the beginning and at the end of each octant, where some glitches appear.

The circle above has a radius of 1. As you can see at the beginning of each octantant (for example, in the (0, 1) area), the pixels drawn inside the loop do not align with the first pixel, which is equal before the start of the loop. Also, something terribly mistakenly approaches the end of each octantant (for example, in the area (sqrt(2) / 2, sqrt(2) / 2) ). I managed to remove this last problem by changing the condition if d < T to if d <= T , but the same problem appears at the beginning of each octantant.

Question 1 : What am I doing wrong?

Question 2 : If I wanted the input position and radius to be floating points?

Answer 1

Let me deconstruct your implementation to see what mistakes you made:

 def draw_antialiased_circle(renderer, position, radius): 

First question, what does radius mean? It is impossible to draw a circle, you can draw a ring (ring / donut), because if you do not have thickness, you cannot see it. Therefore, the radius is ambiguous, is it the inner radius, the radius of the midpoint, or the outer radius? If you do not specify a variable name, this will be confusing. Perhaps we can find out.

 def _draw_point(renderer, offset, x, y): sdl2.SDL_RenderDrawPoint(renderer, offset.x - x, offset.y + y) sdl2.SDL_RenderDrawPoint(renderer, offset.x + x, offset.y + y) sdl2.SDL_RenderDrawPoint(renderer, offset.x - x, offset.y - y) sdl2.SDL_RenderDrawPoint(renderer, offset.x + x, offset.y - y) 

OK, we are going to make four places at once, since the circle is symmetrical. Why not 8 places at once?

 i = 0 j = radius d = 0 T = 0 

OK, initialize i to 0 and j radius, these should be the x and y coordinates. What is d and T ? Descriptive variable names are not supported. This is normal when copying scientists' algorithms to make them understandable with longer variable names that you know!

 sdl2.SDL_SetRenderDrawColor(renderer, 255, 255, 255, sdl2.SDL_ALPHA_OPAQUE) _draw_point(renderer, position, i, j) 

BUT? Are we drawing a special case? Why are we doing this? Not sure. What does it mean? This means filling the square in (0, radius) full opacity. So, now we know what radius , this is the outer radius of the ring, and the width of the ring is apparently one pixel. Or at least what this special case tells us ... let's see if this is preserved in the general code.

 while i < j + 1: 

We are going to go in cycles until we reach a point on the circle, where i > j , and then stop. That is, we draw an octant.

  i += 1 

So, we have already drawn all the pixels that we care about, in position i = 0 , we will move to the next.

  s = math.sqrt(max(radius * radius - i * i, 0.0)) 

those. s is a floating point number that is the y-component of the octant at point i along the x axis. That is, the height above the x axis. For some reason we have max , maybe we are worried about very small circles ... but this does not tell us if the point is on the outer / inner radius.

  d = math.floor(sdl2.SDL_ALPHA_OPAQUE * (math.ceil(s) - s) + 0.5) 

Breaking it, (math.ceil(s) - s) gives us a number from 0 to 1.0, which. This number will increase as s decreases, as i increases, and then, as soon as it reaches 1.0, it will reset to 0.0, therefore, in a sawtooth pattern.

sdl2.SDL_ALPHA_OPAQUE * (math.ceil(s) - s) We use a sawtooth input to create an opacity level, i.e. to smooth the circle. Put a constant addition of 0.5. floor() assumes that we are only interested in integer values ​​- probably the API accepts only integer values. All this shows that d ends as an integer level between 0 and SDL_ALPHA_OPAQUE , which starts from the beginning with 0, then gradually increases with i , and then when ceil(s) - s moves from 1 to 0, it falls back again.

So what does that matter in the beginning? s almost radius , since i is equal to 1 (provided that the circle does not have a trivial size), so we assume that we have an integral radius (which explicitly assumed the first special random code) ceil(s) - s is 0

  if d < T: j -= 1 d = T 

Here we noticed that d moved from high to low, and we are moving down the screen so that our position j close to where the ring should theoretically be.

But now we understand that the word from the previous equation is wrong. Imagine that in one iteration, d is 100.9. Then at the next iteration it fell, but only to 100.1. Since d and T are equal, since the gender eliminated their difference, we do not reduce j in this case, and this is crucial. I think probably explains the odd curves at the ends of your octant.

 if d < 0: 

Just optimization does not draw if we use alpha value 0

 alpha = d sdl2.SDL_SetRenderDrawColor(renderer, 255, 255, 255, alpha) _draw_point(renderer, position, i, j) 

But the freeze on the first iteration d low, and therefore it refers to the (1, radius) almost completely transparent element. But a special case, to start with drawing a completely opaque element (0, radius) , it is so clear that there will be a graphic glitch. This is what you see.

Performance:

 if i != j: 

Another small optimization in which we will not paint again if we paint in the same place

 _draw_point(renderer, position, j, i) 

And that explains why we only make 4 points in _draw_point() , because here you are doing a different symmetry. This will simplify your code, not.

 if (sdl2.SDL_ALPHA_OPAQUE - d) > 0: 

Another optimization (you should not prematurely optimize your code!):

 alpha = sdl2.SDL_ALPHA_OPAQUE - d sdl2.SDL_SetRenderDrawColor(renderer, 255, 255, 255, alpha) _draw_point(renderer, position, i, j + 1) 

So, at the first iteration, we write above, but with full opacity. This means that this is actually the internal radius that we use, and not the external radius used by the special case error. That is a kind of mistake "one after another."

My implementation (I did not have an installed library, but you can see from the output, checking the boundary conditions, that this makes sense):

 import math def draw_antialiased_circle(outer_radius): def _draw_point(x, y, alpha): # draw the 8 symmetries. print('%d:%d @ %f' % (x, y, alpha)) i = 0 j = outer_radius last_fade_amount = 0 fade_amount = 0 MAX_OPAQUE = 100.0 while i < j: height = math.sqrt(max(outer_radius * outer_radius - i * i, 0)) fade_amount = MAX_OPAQUE * (math.ceil(height) - height) if fade_amount < last_fade_amount: # Opaqueness reset so drop down a row. j -= 1 last_fade_amount = fade_amount # The API needs integers, so convert here now we've checked if # it dropped. fade_amount_i = int(fade_amount) # We're fading out the current j row, and fading in the next one down. _draw_point(i, j, MAX_OPAQUE - fade_amount_i) _draw_point(i, j - 1, fade_amount_i) i += 1 

Finally, would there be gotchas if you want to pass the beginning to a floating point?

Yes it would. The algorithm assumes that the origin is in an integer / integer place and otherwise completely ignores it. As we saw, if you pass an integer outer_radius , the algorithm draws a 100% opaque square at the location (0, outer_radius - 1) . However, if you want to convert to a location (0, 0.5) , you probably want the circle to be smoothly smoothed to 50% opacity in places (0, outer_radius - 1) and (0, outer_radius) , which this algorithm does not give you because he ignores the origin. Therefore, if you want to use this algorithm accurately, you must round off your origin before passing it on, so nothing comes of using float.

Answer 2

I have the following to work on my machine:

 def draw_antialiased_circle(renderer, position, radius, alpha_max=sdl2.SDL_ALPHA_OPAQUE): def _draw_points(i, j): '''Draws 8 points, one on each octant.''' #Square symmetry local_coord = [(i*(-1)**(k%2), j*(-1)**(k//2)) for k in range(4)] #Diagonal symmetry local_coord += [(j_, i_) for i_, j_ in local_coord] for i_, j_ in local_coord: sdl2.SDL_RenderDrawPoint(renderer, position.x + i_, position.y + j_) def set_alpha_color(alpha, r=255, g=255, b=255): '''Sets the render color.''' sdl2.SDL_SetRenderDrawColor(renderer, r, g, b, alpha) i, j, T = radius, 0, 0 #Draw the first 4 points set_alpha_color(alpha_max) _draw_points(i, 0) while i > j: j += 1 d = math.ceil(math.sqrt(radius**2 - j**2)) #Decrement i only if d < T as proved by Xiaolin Wu i -= 1 if d < T else 0 """ Draw 8 points for i and i-1 keeping the total opacity constant and equal to :alpha_max:. """ alpha = int(d/radius * alpha_max) for i_, alpha_ in zip((i, i-1), (alpha, alpha_max - alpha)): set_alpha_color(alpha_) _draw_points(i_, j) #Previous d value goes to T T = d 

The above procedure is a simple implementation of the diagram below.

There is a mistake in this diagram: the lowest test should be D(r,j) < T not D(r,j) > T , which may explain why you are a little confused.

To answer your second question, I doubt that you can pass the float number as the position and radius, since ultimately the C function SDL_RenderDrawPoint expects an int .

You can pass some floats into your Python function, but before using SDL_RenderDrawPoint you have to SDL_RenderDrawPoint them in int . Unfortunately, there is nothing like a half-pixel yet;)