![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||
|
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)
The algorithm as given produces undesirable points on the lines 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 and have been moved to and , 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)
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);
}
}
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);
}
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);
}
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);
}
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)
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
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)
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)
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 √2 distinct pixels, or, equivalently, √2 distinct pixels. The C# implementation of the algorithm given in the article draws √2 pixels, including duplicates.)-- 74.104.204.248 ( talk) 19:40, 16 February 2015 (UTC)
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)
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)
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)
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)
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)
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)
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)
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."?
![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||
|
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)
The algorithm as given produces undesirable points on the lines 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 and have been moved to and , 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)
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);
}
}
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);
}
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);
}
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);
}
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)
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
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)
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)
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 √2 distinct pixels, or, equivalently, √2 distinct pixels. The C# implementation of the algorithm given in the article draws √2 pixels, including duplicates.)-- 74.104.204.248 ( talk) 19:40, 16 February 2015 (UTC)
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)
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)
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)
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)
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)
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)
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)
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."?