Talk:Midpoint circle algorithm

Untitled

I created this article based on content from the Bresenham's line algorithm article's section Circle variant (this article used to point to that section). That section had been removed, probably because it is was not about the algorithm developed by Bresenham. Lakeworks (talk) 21:06, 12 January 2008 (UTC)

Glitches in the algorithm

The algorithm as given produces undesirable points on the lines $y=\pm x$ for certain (admittedly sparse) radii. The first five such are 4, 11, 134, 373 and 4552. I discovered this myself, but it turns out to be well-known, or at least, well, known. See Sloane's A055979. Curiously, the illustration given in the article uses the bad radius 11, and is not the rasterization produced by the algorithm. (The pixels at $(7,8)$ and $(8,7)$ have been moved to $(7,9)$ and $(9,7)$, which in this case produces a better effect than simply omitting the spurious point.) How real-life graphics programs cope with this, if they use the Bresenham algorithm at all, I do not know. My one experiment has been with KolourPaint, which for a radius of 11 produces something different from both the algorithm and the article's figure.--Jos.Pinkfoot (talk) 00:29, 8 July 2008 (UTC)

If they do use this algorithm, I would guess they just deal with it: it's a natural side effect of the fact that it produces a rasterized approximation of a circle — and at least the points aren't completely off the circle. Considering how far computers have come since the development of this algorithm, all but the most basic graphics applications are probably using anti-aliased drawing algorithms, anyway. ¢R¡p7yc# (talk) 03:24, 24 November 2008 (UTC)

This is not a bug of the algorithm, however that last pixel that occurs with some radius is effectively part of the solution, as it is occurs (when drawing in the first octant) when this last pixel was chosen as the next pixel after the pixel below it, instead of the pixel on the diagonal. Due to the symetries, it produces a set of three pixels forming a right angle: all those pixels correctly respect the distance of plus or minus one half pixel from the theoretical circle, and in fact these three pixels are at equal distance from the circle that passes between them.

This glitch is easy to eliminate, by not drawing the last pixel within the loop, but only outside the loop (exit as soon as y >= x), and testing if the previously drawn pixel (in the first octant) was below. In that case the last pixel does not need to be drawn as the previous pixel drawn within the loop will connect diagonally with the next quadrant.

One minor difficulty is that it requires tracking the position of the previous pixel, in order to detect when it is vertically aligned. But this can offer additional optimizations, by allowing to draw vertical segments instead of individual pixels (notably when drawing a circle in a clipped area, or when computing arbitrary pixel positions within the image: vertical lines are faster to draw than oblique lines and individual random pixels.

If you do that, you will exit the loop when there is possibly a hanging small vertical line which is still not drawn completely and with the last pixel on the 45°direction; this final vertical segment will cover only one or two pixels: if this segment is two pixels, just draw only one. And because of the 8 symetries, the last vertical segment will turn into 4 horizontal and 4 vertical segments, that can intersect and cover the same 4 pixels on the +/- 45° directions if those short segments all have two pixels. By eliminating the second pixel on each segment, you will just draw 8 individual (non-intersecting) pixels instead of horizontal or vertical segments.

Note also that when you exit the loop, the next candidate pixel computed could be outside the quadrant for which it was computed, and in that case you won't draw anything when exiting the loop (this only occurs, in the first octant, when the the pixel outside this quadrant is on a diagonal direction from the last drawn pixel, and you can test it only by testing if (y > x) : if so don't draw the last 8 pixels which are "out of the octant" (if you don't test it, these 8 pixels may either cover the pixels for the next quadrant, or it could be outside of the circle).

verdy_p (talk) 02:39, 7 January 2010 (UTC)

Here is a version of the algorithm, which is easier to understand and also avoids the glitch. It is not optimized using a cumulative variable to compute incrementally the test value, but it uses strictly the definition of circles (it compares the squared distance of the candidate vertical pixel with the square desired radius plus one half, and expression that can be optimized as indicated below, but that you can compute incrementally with an additional "error" variable, if you want to avoid the multiplications, or two variables if you want to reduce the number of additions) :

void circle(int x0, int y0, int r) {
  int u, v; bool diagonal = false;
  for (u = r, v = 0; u > v;) { // start from a know pixel (u,v)=(r,0) on the x axis, compute only the first octant (u > v)
    plot(x0 + u, y0 + v); plot(x0 + v, y0 + u);
    plot(x0 - u, y0 + v); plot(x0 - v, y0 + u);
    plot(x0 + u, y0 - v); plot(x0 + v, y0 - u);
    plot(x0 - u, y0 - v); plot(x0 - v, y0 - u);
    v++; // next pixel is above (in the first octant)
    // if the pixel above is at distance greater than 1/2+r from the origin
    // we could test if (v^2 + u^2 >= (1/2+r)^2), but the following is equivalent with integers: 
    if (diagonal = v*v + u*u - (1 + r)*r > 0)
      u--; // choose the diagonal pixel instead (to the right in the first octant)
  }
  if (u == v && diagonal) { // last pixel if it's on the 45° diagonal
    plot(x0 + u, y0 + u);
    plot(x0 - u, y0 + u);
    plot(x0 + u, y0 - u);
    plot(x0 - u, y0 - u);
  }
}

The Bresenham algorithm just optimizes the multiplications, by not computing them directly, but instead by computing them as a rational that can be updated using the incremental differences (which are also related to the derivative slope, and which can also be computed with only additions of integers. verdy_p (talk) 03:24, 7 January 2010 (UTC)

Note also : an alternative decision can be based on the relative position of the "midpoint" with the exact circle, in which case the midpoint is defined as the middle between the two candidate pixels.

the midpoint above for the next point would be at (u-1/2, v+1), but given that v is already incremented before the test it will just be (u-1/2,v) which is at the squared distance:

( (u-1/2)^2 + vˆ2) - ( rˆ2 )

from the circle whose squared radius is r^2.

In this case, only the sign needs to be tested. This expression can be simplidied by multiplying it by 4 (this does not change the sign which is the only thing tested : it remains negative if the midpoint is within the circle, positive if it is outside it, and null if the midpoint is exactly on the circle):

4 *( ( (u-1/2)^2 + vˆ2) - ( rˆ2 ) ) = 4 * ( uˆ2 - u + 1/4 + v^2 - r^2) = 4*uˆ2 - u + v^2 - rˆ2 + 1

So you can test if (4* (uˆ2 - u + v^2 - rˆ2) + 1 > 0) which is equivalent (for integers only) to if (4* (uˆ2 - u + v^2 - rˆ2) + 1 >= 1) and then can be reduced to

if ((u - 1)*u + v^2 - rˆ2 >= 0) after eliminating the common term from both sides, and after avoiding the multiplication by 4 which does not contribute to the tested sign.

Note how this alternate expression is very similar to the test shown above. It produces some minor differences on rendered circles, only on the positions where two candidates are equally possible (and here also, you can vary the test a bit by deciding what to do in the case where the midpoint is exactly on the circle, something that occurs when this new tested expression is zero...

In conclusion: there are several possible solutions that are equivally valid and respect the constraints, but can be rendered differently. And you still have to treat the last pixel on the 45° direction specially to avoid glitchs (determine if it creates a set of 3 pixels forming a right angle, in order to avoid drawing this last pixel in that case). verdy_p (talk) 04:13, 7 January 2010 (UTC)

The test above just uses a single (u == v) to see if the last pixel is exactly on the 45° direction (and not "after" the computed octant), but you can add another condition for the direction of that pixel since the previously drawn pixel (don't draw it if it's just above the previous pixel: this is the only case where the value stored in the diagonal variable will be used; the stored value of this boolean variable is not used within the loop itself).

One way to avoid storing this extra varaible is to treat the last loop above specially: given that v is incremented at each loop, v+1 (instead of v alone) must remain below u, and you'll have to unwind that last loop before testing the last pixel on the 45° direction (where u==v). verdy_p (talk) 04:13, 7 January 2010 (UTC)

Here is how you can unwind the last loop, before also conditionally drawing the last pixel, this completely eliminates all glitches for the final pixel:

void circle(int x0, int y0, int r) {
    int u, v;
    for (u = r, v = 0; u > v + 1;) {
        plot(x0 + u, y0 + v); plot(x0 + v, y0 + u);
        plot(x0 - u, y0 + v); plot(x0 - v, y0 + u);
        plot(x0 + u, y0 - v); plot(x0 + v, y0 - u);
        plot(x0 - u, y0 - v); plot(x0 - v, y0 - u);
        v++; // above
        if ((u - 1)*u + v*v - r*r >= 0)
            u--; // diagonal
    }
    if (u > v) { // penultimate pixel
        plot(x0 + u, y0 + v); plot(x0 + v, y0 + u);
        plot(x0 - u, y0 + v); plot(x0 - v, y0 + u);
        plot(x0 + u, y0 - v); plot(x0 + v, y0 - u);
        plot(x0 - u, y0 - v); plot(x0 - v, y0 - u);
        v++; // above
        if ((u - 1)*u + v*v - r*r >= 0 &&
            --u == v); // diagonal: can draw last pixel
        else return; // not diagonal: don't draw last pixel
    }
    // draw last pixel where (u == v)
    plot(x0 + u, y0 + u);
    plot(x0 - u, y0 + u);
    plot(x0 + u, y0 - u);
    plot(x0 - u, y0 - u);
}

(the test conditions for candidate pixels is exactly the same as described above (based on the midpoint evaluation with the exact radius, instead of the test of the pixel above with the maximum radius+1/2), except that it occurs on two lines after unwinding the penultimate pixel, and exactly the same incremental evaluation is possible to optimize these tests). verdy_p (talk) 04:53, 7 January 2010 (UTC)

Finally here is how you can optimize the multiplications used above to compute the test function e(u,v), by using incremental variables (note that this test function uses the opposite sign) :

void circle(int x0, int y0, int r) {
    int u, v, e, a, b;
    //e(u  ,v  ) = r*r - u*u + u - v*v 
    //             e(r  ,0  ) = r
    //e(u  ,v+1) = e(u  ,v  ) - 2*v - 1 = e(u  ,v  ) - a(u,v)
    //e(u-1,v+1) = e(u  ,v+1) + 2*u     = e(u  ,v+1) + b(u,v)
    //    
    //a(u  ,v  ) = 2*v + 1        ; b(u  ,v  ) = 2*u
    //             a(r  ,0  ) = 1 ;              b(u  ,v  ) = 2*r
    //a(u  ,v+1) = a(u  ,v  ) + 2 ; b(u  ,v+1) = b(u  ,v  )
    //a(u-1,v+1) = a(u  ,v  )     ; b(u-1,v+1) = b(u  ,v  ) - 2
    for (a = 1, b = (e = u = r) * 2, v = 0; u > v + 1;) {
        plot(x0 + u, y0 + v); plot(x0 + v, y0 + u);
        plot(x0 - u, y0 + v); plot(x0 - v, y0 + u);
        plot(x0 + u, y0 - v); plot(x0 + v, y0 - u);
        plot(x0 - u, y0 - v); plot(x0 - v, y0 - u);
        v++; e -= a; a += 2; // above
        if (e <= 0) {
            u--; e += b; b -= 2; // diagonal
        }
    }
    if (u > v) { // penultimate pixel
        plot(x0 + u, y0 + v); plot(x0 + v, y0 + u);
        plot(x0 - u, y0 + v); plot(x0 - v, y0 + u);
        plot(x0 + u, y0 - v); plot(x0 + v, y0 - u);
        plot(x0 - u, y0 - v); plot(x0 - v, y0 - u);
        v++; // above
        if (e <= 0 &&
            --u == v); // diagonal: can draw last pixel
        else return; // not diagonal: don't draw last pixel
    }
    // draw last pixel where (u == v)
    plot(x0 + u, y0 + u);
    plot(x0 - u, y0 + u);
    plot(x0 + u, y0 - u);
    plot(x0 - u, y0 - u);
}

The source above also decomposes the values added or substracted to the error function e(u,v) using two additional incremental variables (a and b). Note that this is generally not improving the speed, because the cost of using additional registers and updating them will be in fact greater than just updating e with the linear values (a = 2*v+1, and b = 2*u), which just requires just a couple of additions for each. This suggests the following alternate version which may be faster and will require fewer register allocations (and it is similar to the solution exposed in the article for assembly language optimizations):

void circle(int x0, int y0, int r) {
    int u, v, e;
    //e(u  ,v  ) = r*r - u*u + u - v*v 
    //             e(r  ,0  ) = r
    //e(u  ,v+1) = e(u  ,v  ) - 2*v - 1
    //e(u-1,v+1) = e(u  ,v+1) + 2*u
    for (e = u = r, v = 0; u > v + 1;) {
        plot(x0 + u, y0 + v); plot(x0 + v, y0 + u);
        plot(x0 - u, y0 + v); plot(x0 - v, y0 + u);
        plot(x0 + u, y0 - v); plot(x0 + v, y0 - u);
        plot(x0 - u, y0 - v); plot(x0 - v, y0 - u);
        v++; e -= v+v+1; // above
        if (e <= 0) {
            u--; e += u+u; // diagonal
        }
    }
    if (u > v) { // penultimate pixel
        plot(x0 + u, y0 + v); plot(x0 + v, y0 + u);
        plot(x0 - u, y0 + v); plot(x0 - v, y0 + u);
        plot(x0 + u, y0 - v); plot(x0 + v, y0 - u);
        plot(x0 - u, y0 - v); plot(x0 - v, y0 - u);
        v++; // above
        if (e <= 0 &&
            --u == v); // diagonal: can draw last pixel
        else return; // not diagonal: don't draw last pixel
    }
    // draw last pixel where (u == v)
    plot(x0 + u, y0 + u);
    plot(x0 - u, y0 + u);
    plot(x0 + u, y0 - u);
    plot(x0 - u, y0 - u);
}

Another optimisation is possible to avoid plotting the same first pixel (with 4 symetries) two times: instead of testing this case (which occurs with v==0) within the loop, you can also unwind this first loop. Such optimiszation is already shown above for the last pixel of the arc (where u==v) which just plots 4 symetries instead of 8. It will be necessary to do it if you transform this code to an antialiasing version (where all the plotted pixels above will be subsampled to compute a cumulative alpha value that will be used to plot two nearby pixels with distinct alpha values.

To fill a circle, the same code as above can be used, except that you have to draw horizontal lines between pairs of symetric pixels (at the same y coordinate), instead of plotting them individually.

The antialiasing version is not shown here as it would require adding the variables needed for managing the color values in each color plane used. The code above does not really show what color is applied. to make it fully antialiasing, you have to define the level at which pixels are subsampled (this may require subsampling both x and y coordinates by at least 8 (or up to 16), to produce alpha values between 0 (no pixel drawn) and 256 (plain color applied to the target pixel). In reality, the code will be much more complex as you will also have to compute the drawing width, which will be in fact equivalent to filling a ring area between two circles with radius between (r-width/2) and (r+width/2).

Filling rings without filling the full circle and then unfilll the interior will require more complex code to manage the midpoint algorithm along two distinct circles simultaneously.

Many simplified antiliasing implementations do not really produce the correct circles with the desired constant drawing width: you really need to manage two distinct circles with distinct radius to avoid the undesirable visible width variation, so you'll need to work on the code to fill a ring instead of just one circle. verdy_p (talk) 07:39, 7 January 2010 (UTC)

Question about the algorithm

I discovered that the algorithm as given contains the invariant (f == x * x + y * y - radius * radius + 2 * x - y + 1) at the beginning of the loop. It is not clear why the term (2 * x - y + 1) is used. I rewrote the algorithm so that the invariant is just (f == x*x + y*y - radius*radius), and my altered algorithm produces reasonable-looking circles. Perhaps the original algorithm is buggy and is actually creating very slight ellipses, not exact circles? However, I am hesitant to change the algorithm in case there is some good reason for the extra term (2 * x - y + 1). If the algorithm is correct as given, then some explanation is needed to clarify it. —Preceding unsigned comment added by Halberdo (talk • contribs) 18:48, 21 November 2008 (UTC)

No it is not bogous as such : the article just has to explain what is the "midpoint" (because it is part of its name, but is not explained anywhere !).

A true approximation of the algorithm has to carefully design what is this midpoint: if you are in the first octant, the midpoint is may be located between the two candidate next pixels (the pixel just aboive or the diagonal pixel on the upper left).

The algorithm can also be tuned using different constraints: noaminally, the center of pixels should be at a distance not exceeding +/- 0.5 pixels fromthe theoretical circle. This can be tested by comparing the effective distance of the candidate pixels and comparing it with the radius, but there will still remain a question : what happens when the two candidate pixels are at equal distance ?

Generally, the midpoint decision can be simplified by maximizing the x coordinate at each y step, making sure that this position will remain strictly within a circle with the given radius + one half pixel.

Instead of comparing the distance of candidate pixels with this maximum radius, it is much simpler to compare the squared distance of one of the two candidate pixels with the squared maximum radius: generally this is the vertical candidate pixel which is chosen as it is simpler to compute, if we already know the squared distance of the current pixel.

In fact, instead of computing the squared distance of the tested pixel and comparing it with the squared radius, you can just substract this squared radius for both, in order to compare the adjusted squared distance with zero: it is simple to initialize this difference when you start drawing from the pixel on the horizontal axis, because the difference with the desired maximum radius is exactly one half pixel (within the maximum circle which is the one tested), i.e. its squared distance is -1/4 (within the maximum circle). Then to avoid having to compute with quarter units, you can improve the speed using just integers by not testing the difference between the squared distance and the squared maximum radius, but instead four times this quantity: this does not change the complexity for testing the sign.

In that case the first pixel on the horizontal axis will have the test value equal to -1 (it must remain negative : when the test value becomes zero, the tested vertical pixel is exactly on the maximum circle with radius r+1/2 (not on the desired circle with radius r), and the alternate candidate is exactly on the minimum circle with radius r-1/2. The two solutions are possible and are equally acceptable, except in one case: for the last pixel on the 45° diagonal: in that case, when you will connect the two octants, you will see there a sharp right angle (i.e. a spurious pixel). For this reason, it is best in that case to not use the vertical candidate and instead use the diagonal candidate. This just implies keeping the test value strictly negative: this means that when you have the choice between the vertical pixel at distance R+1/2 (exactly on the maximum circle) and the diagonal pixel at distance R-1/2 (exactly on the minimum circle), choose the one on the minimum circle: if the test value is zero, select the diagonal pixel.

In all cases, when going from one current pixel to the next chosen candidate, you have to adjust the test value. As the test value is four times a squared distance, it can be computed only as a quadratic polynomial, but the adjustment will not be quadratic but only linear. This means that you don't even need any multiplciation. Note that for multiplying the test value by 4, you don't need any multiplication.

Notes on accuracy:

• Some algorithms attempt to simplify the initialization, and use a different invariant, but they are WRONG : any adjustment will mean that you don't respect the most exact constraint of keeping the distance exactly within one half pixel (the maximum distance), and what is drawn are the set of pixels which are for example between an acceptable inner radius R and the unacceptable maximum circle at distance R+1... You still get a good approximation of a circle, but you get the wrong approximation of the desired radius !
• Some other simplifications of the agorithm are even worse and can effectively render not perfectly aligned arcs, but draw arcs of circles whose center has been biased, so that when the arcs connect on the 45°direction, they don't have the approximation of the same unitary slope.
• Another incorrect approximation of the radius can bring a case where the curvature is too strong (i.e. the maximum radius is too small): in that case, you'll see a cirle arc starting from the X axis, which will then no longer be able to reach the desired point on the 45°direction, going too far inside the theoretical circle and the best that it will do is to continue it by a straight 45° segment).
• The algorithm shown is in this article is just WRONG : it has the two first defects (so it draws arcs of circles with the wrong approximation of the radius, and the wrong slope on the 45° axis) because it uses the incorrect initializers, and it is the main cause of the visible spurious pixels... It can even draw pxiels that are too far away from the theoretical circle, as far away from the theoretical circle (when computing their distance with the center) as 1 full pixel !!! And it will show some visible angles on the 45° direction, when drawing large enough circles, due to incorrect approximation of the slope (the two tangeants will not corectly match).

To test if your algorithm is correct, assert two things (in a debug version) :

• that the test value which would be computed if the alternate candidate was chosen effectively has a distinct sign. As we choose the test value to be strictly negative for the chosen candidate, the test value should be positive or null for the non-chosen candidate.
• that the final pixel on the 45° direction effectively is at an acceptable distance from the center, not exceeding one half pixel of difference from the theoretical radius.

verdy_p (talk) 01:19, 7 January 2010 (UTC)

Optimization Quesions

The article states ' Only three variables are needed in the main loop to perform the calculation'. However, the two function calls each require four arguments, so there's actually another 8 stack-bound variables inside of the loop. A better way, code wise, might be to use a function-syle Macro, but this would make the snippet harder to read for those not well versed in C. Rsaxvc (talk) 02:20, 15 November 2009 (UTC) do not see thids

That depends on the implementation. I wrote this section based upon circle-drawing code I wrote for a Z80. In this code, all the variables were global, requiring no stack-bound variables for the function call (which could be inlined, if you can afford the space).

The statement "Only three variables" is mainly used to highlight the advantage of this method over the other presented method, which requires 4 in the main loop + whatever you need for the function call. Although you are technically correct (some say this is the best kind of correct ;) ), I think the section makes more intuitive sense in its current form. Otherwise, we would have to add a whole de-rail on the technicalities of function call semantics...

Qarnos (talk) 09:39, 14 May 2010 (UTC)

spheres

there's an algorithm for lines; there's an algorithm for circles. is there an equivalent algorithm for spheres? pauli133 (talk) 21:51, 6 October 2010 (UTC)

Project the sphere to a circle (x, y, r) first, then use the circle algorithm. x and y can be found by projecting the sphere's center, and r can be found by solving a right triangle for the projection, where the right angle corner of the triangle lies on the sphere's surface (i.e. find a ray tangent to the sphere). There are an infinite number of right triangles available; pick one that makes the math easy. -- 70.124.59.176 (talk) 03:28, 29 November 2010 (UTC)

Clarifications

There is currently a note asking for this article to be clarified. Here's some text that might be a little clearer. It should replace the first 3 paragraphs of the "The Algorithm" section:

"The equation for a circle centered at the origin, with a radius r is x^2 + y^2 = r^2. We can use this equation to draw a circle. Furthermore, we can use the fact that a circle is radially symmetric to reduce the amount of work necessary for drawing it. The algorithm presented here will only calculate points in the first octant of the circle and use the symmetry to fill in the rest of its circumference.

Ideally, we'd like the algorithm to work on a pixel-by-pixel basis, so we can increment a counter and traverse the circle, drawing points on its perimeter. The algorithm presented will advance 1 pixel in the Y-direction each iteration through the loop. It will accumulate fractional values in the X-direction, advancing in the X-direction only when those accumulated fractions equal at least 1 pixel in the X-direction." --Dcardani (talk) 23:20, 18 October 2010 (UTC)

A more detailed description of the algorithm can be found at http://www.cs.unc.edu/~mcmillan/comp136/Lecture7/circle.html Alexis59 (talk) 12:57, 14 December 2010 (UTC)

The link helpfully provided by Alexis59, http://www.cs.unc.edu/~mcmillan/comp136/Lecture7/circle.html, is dead as of 2024-02-12. The replacement course as of Fall 2023 may be "Comp 475. 2D Computer Graphics", as described in the currently-most-recent course catalog, but I"m giving up trying to track down the "more detailed description" that Alexis59 saw. )-: DavidHolmes0 (talk) 14:59, 12 February 2024 (UTC)

Total Points Generated

I'm not 100% sure how to phrase this. Maybe someone could help with this. Basically for a radius r, the midpoint circle algorithm generates 4*sqrt(2)*r points. I think this has something to do with the algorithm for generating lines: for a line connecting (x1,y1) -> (x2,y2), max(abs(x2-x1),abs(y2-y1)) points are generated. In the picture of the midpoint circle algorithm, this would be something like (x=r,y=0) -> (x=r*cos(pi/2),y=r*sin(pi/2)). Any suggestions on how to incorporate this? — Preceding unsigned comment added by Drnathanfurious (talk • contribs) 08:46, 3 June 2011 (UTC)

(More precisly, the midpoint circle algorithm draws $4\cdot \mathrm {round} ($√2 $r)$ distinct pixels, or, equivalently, $4\cdot \lfloor$√2 $r+1/2\rfloor$ distinct pixels. The C# implementation of the algorithm given in the article draws $8\cdot \lfloor ($√2$/2)\cdot r+3/4\rfloor +4$ pixels, including duplicates.)--74.104.204.248 (talk) 19:40, 16 February 2015 (UTC)

Bill Atkinson's algorithm

In the book "Steve Jobs", Walt Isaacson describes Bill Atkinson's algorithm for drawing circles quickly on the original Macintosh. This routine eventually became part of the Apple Quickdraw library. The algorithm involves a clever observation about the sum of odd numbers. The algorithm is probably a variant of the midpoint circle algorithm — Preceding unsigned comment added by 66.92.48.217 (talk) 20:14, 22 December 2011 (UTC)

Inaccurate comment in "Optimized" algorithm

This comment appears to be inaccurate:

"The following test may be implemented in assembly language in most machines by testing the carry flag after adding 'y' to the value of 'error' in the previous step, since 'error' nominally has a negative value."

Since 'y' is added twice (once pre-increment and once post-increment), if the carry occurs the first time 'y' is added to 'error', then the carry flag won't be set the second time after incrementing 'y' and adding it to 'error' again. I had to use the sign flag instead of the carry flag (in x86 assembly language).

In general it seems like most machines would only set the carry flag after an addition if the left hand operand was negative prior to the addition and non-negative afterward. Or is this in fact peculiar to x86? Clone53421 (talk) 14:50, 29 July 2013 (UTC)

Flagged dead link

While researching ellipse algorithms, came across this page. Paper by John Kennedy is no longer available at the address uri, flagged it as a dead link. Will update if I find a replacement. Akoi Meexx (talk) 19:18, 17 April 2014 (UTC)

Error in Section "Variant with Integer-Based Arithmetic"

The final step in the derivation substitutes x^2+y^2-r^2 with the previously defined RE(x,y) function. As defined the RE function additionaly takes the abs value of this expression and is therefore not equivalent, which makes the resulting condition simply wrong as stated.

Someone with the patience to futz with markup and editorial politics - please fix. — Preceding unsigned comment added by 5.102.221.219 (talk) 01:49, 7 February 2015 (UTC)

Why is the putpixel(..) block after the update of x and y?

In the C-function in the current version of the article, first the variables are being updated, then the block, drawing the 8 octants follows. Given there is a discussion about the "last pixel" and the fact, that the init values of x and y are on a perfectly fine pixel (error = 0), why not move the putpixel block in front?

   void DrawCircle(int x0, int y0, int radius)
   {
       int x = 0, y = radius;
       int dp = 1 - radius;
       do
       {
           putpixel(x0 + x, y0 + y, 15);     //For the 8 octants
           putpixel(x0 - x, y0 + y, 15);
           putpixel(x0 + x, y0 - y, 15);
           putpixel(x0 - x, y0 - y, 15);
           putpixel(x0 + y, y0 + x, 15);
           putpixel(x0 - y, y0 + x, 15);
           putpixel(x0 + y, y0 - x, 15);
           putpixel(x0 - y, y0 - x, 15);
               
           if (dp < 0)
               dp = dp + 2 * (++x) + 3;
           else
               dp = dp + 2 * (++x) - 2 * (--y) + 5;
       } while (x < y);
   }

I also noticed this, and the circles drawn by the sample code are somewhat diamond-shaped. Following the mathematical description directly above it, I am contributing an implementation that fixes the above issue and also produces a more circular-shaped rasterization. HoldTheDoor (talk) 01:31, 8 June 2016 (UTC)

The remark about minecraft does not make much sense to me, i think it either needs an explanation, or should be removed from this page. I do understand that since minecraft is 'block-y' any pixel related algorithm might be useful in minecraft, but i don't understand why minecraft would be sufficiently special to be mentioned in a very generic algorithm page. itsme (talk) 12:08, 14 July 2016 (UTC)

The closure in the javascript example is priceless

I mean, it'd affect the already-poor performance, make the algorithm about 9000% harder to follow by a beginner, and provide basically no benefit beyond that of a simple "line pitch" constant. Hope the writer doesn't teach IT... — Preceding unsigned comment added by 95.232.30.145 (talk) 02:49, 23 January 2017 (UTC)

Code Example

Most of the contents in this article are only some kind of "proof" saying that the algorithms makes sense. And the actual algorithm is hidden in this proof. To make it clearer what the algorithm does, there should be at least some implementation (e.g. PseudoCode). David Eppstein removed previous code without much of a comment. In its current form the article is extremely unhelpful.

--2A02:8071:699:B700:224B:DCD2:B994:76F5 (talk) 22:18, 3 February 2021 (UTC)

One implementation in pseudocode, ok. Multiple implementations of the same method in multiple real programming languages, not ok. Without published sources for that code they are original research, and with sources they are probably a copyright violation. And compared to pseudocode these implementations are too bogged down with irrelevant programming details to be as helpful to human readers. Wikipedia is not a code repository. There are other sites for that, that do it better. —David Eppstein (talk) 23:33, 3 February 2021 (UTC)

Inaccurate wording on the Generalizations

The text in question reads that:

It is also possible to use the same concept to rasterize a parabola, ellipse, or any other two-dimensional curve.

This statement is slightly confusing on the last part because as-is implies that any 2d curve, regardless of degree, can be derived from Bresenham's original algorithm. As far as I know, considerable arrangements should be made to rasterize curves other than quadratic ones (I don't want to say impossible because I am not sure yet).

So should that text be reworded to say, "...or any other two-dimensional quadratic curve."?

Dv-id.061 (talk) 01:51, 11 July 2021 (UTC)

wrong algorithm?

The algorithm described on this page does not sound like the midpoint circle drawing algorithm, and in fact there is barely any element of "midpoint" in the algorithm!

A good description of what I think is the correct midpoint circle drawing algorithm (in its more general form for ellipses) is given in this paper:

Jerry R. Van Aken: An Efficient Ellipse-Drawing Algorithm. IEEE Computer Graphics and Applications 4(9): 24-35 (1984)

Note that use of the midpoint is an essential part of the method. Krazykat9000 (talk) 10:10, 13 September 2024 (UTC)