3.Circles |
Finding Pixels that lie on a Circlex2 + y2 = r2 for y in [ 0, n ] for x in [ 0, n ] if x2 + y2 - r2 = 0 setPixel ( x, y ) |
Finding Pixels that nearly lie on a Circlex2 + y2 = r2 for y in [ 0, n ] for x in [ 0, n ] if | x2 + y2 - r2 | <= [delta] setPixel ( x, y ) |
A quarter circle generated with unit steps in x, and with y calculated and then rounded.Unique values of y for each x produce gaps |
Finding the Pixels on a Circle - Polar Parametricx2 + y2 = r2 |
Finding the Pixels on a Circle - Polar Parametricx2 + y2 = r2 for [theta] in [ 0, 2[pi] ] x = r cos[theta] y = r sin[theta] setPixel ( x, y ) |
Symmetry of a CircleCalculation of a circle point (x,y) in one octant yields the circle points shown for other seven octants |
Midpoint Algorithm for CircleMidpoint between candidate pixels at sampling position xk+1 along a circular path |
Midpoint Algorithm for CircleThe pixel grid for the midpoint circle algorithm showing M and the pixels E and SE to choose between |
Midpoint Circle AlgorithmImplicit Equationf(x,y) = x2 + y2 - R2 f(x,y) > 0 => point outside circle f(x,y) < 0 => point inside circle |
Midpoint Circle AlgorithmImplicit Equationf(x,y) = x2 + y2 - R2 f(x,y) > 0 => point outside circle f(x,y) < 0 => point inside circleMidpoint Criteria f(M) = f(xp+1, yp - 1/2) = (xp + 1)2 + (yp - 1/2)2 - R2 d >= 0 choose SE next M: +1 in x, -1 in y d < 0 choose E next M: +1 in x |
Midpoint Circle AlgorithmImplicit Equationf(x,y) = x2 + y2 - R2 f(x,y) > 0 => point outside circle f(x,y) < 0 => point inside circleMidpoint Criteria f(n) = f(xp+1, yp - 1/2) = (xp + 1)2 + (yp - 1/2)2 - R2 d >= 0 choose SE next n: +1 in x, -1 in y d < 0 choose E next n: +1 in xBook keeping deltaE = dnew - dold = f(xp + 2, yp - 1/2) - f(xp+1, yp - 1/2) = 2xp + 3 deltaSE = f(xp + 2, yp - 3/2) - f(xp+1, yp - 1/2) = 2xp - 2yp + 5 dstart = f(x0 + 1, y0 - 1/2) = f(1, R - 1/2) = 5/4 - R |
Midpoint Circle Algorithmvoid MidpointCircle ( int radius, int value ) { int x, y; float d; x = 0; y = radius; d = 5.0 / 4 - radius; CirclePoints ( x, y, value ); while ( y > x ) { if ( d < 0 ) { d += x * 2.0 + 3; x ++; } else { d += (x - y) * 2.0 + 5; x ++; y --; } CirclePoints ( x, y, value ); } } |
Midpoint Circle Algorithmvoid MidpointCircle ( int radius, int value ) { int x, y; int d; x = 0; y = radius; d = 1 - radius; CirclePoints ( x, y, value ); while ( y > x ) { if ( d < 0 ) { d += x * 2 + 3; x ++; } else { d += (x - y) * 2 + 5; x ++; y --; } CirclePoints ( x, y, value ); } } |
Midpoint Circle Algorithmvoid CirclePoints (float x, float y, int value) { WritePixel ( x, y, value ); WritePixel ( y, x, value ); WritePixel ( y, -x, value ); WritePixel ( x, -y, value ); WritePixel ( -x, -y, value ); WritePixel ( -y, -x, value ); WritePixel ( -y, x, value ); WritePixel ( -x, y, value ); } |
Midpoint Circle Algorithm |
Midpoint Circle Algorithmx = 0, y = r, p = 1 - r plotPoint ( x + xc, y + yc ) while x < y { if p < 0 { x = x + 1 p = p + 2x + 3 } else { x = x + 1 y = y - 1 p = p + 2( x - y ) + 5 } plotPoint ( x + xc, y + yc ) } |
Midpoint Circle Algorithm
x = 0, y = r, p = 1 - r plotPoint ( x + xc, y + yc ) while x < y { if p < 0 { x = x + 1 p = p + 2x + 3 } else { x = x + 1 y = y - 1 p = p + 2( x - y ) + 5 } plotPoint ( x + xc, y + yc ) } |
Midpoint Circle Algorithm
x = 0, y = r, p = 1 - r plotPoint ( x + xc, y + yc ) while x < y { if p < 0 { x = x + 1 p = p + 2x + 3 } else { x = x + 1 y = y - 1 p = p + 2( x - y ) + 5 } plotPoint ( x + xc, y + yc ) } |
Midpoint Circle Algorithm
x = 0, y = r, p = 1 - r plotPoint ( x + xc, y + yc ) while x < y { if p < 0 { x = x + 1 p = p + 2x + 3 } else { x = x + 1 y = y - 1 p = p + 2( x - y ) + 5 } plotPoint ( x + xc, y + yc ) } |
Midpoint Circle Algorithm
x = 0, y = r, p = 1 - r plotPoint ( x + xc, y + yc ) while x < y { if p < 0 { x = x + 1 p = p + 2x + 3 } else { x = x + 1 y = y - 1 p = p + 2( x - y ) + 5 } plotPoint ( x + xc, y + yc ) } |
Midpoint Circle Algorithm
x = 0, y = r, p = 1 - r plotPoint ( x + xc, y + yc ) while x < y { if p < 0 { x = x + 1 p = p + 2x + 3 } else { x = x + 1 y = y - 1 p = p + 2( x - y ) + 5 } plotPoint ( x + xc, y + yc ) } |
Midpoint Circle Algorithm
x = 0, y = r, p = 1 - r plotPoint ( x + xc, y + yc ) while x < y { if p < 0 { x = x + 1 p = p + 2x + 3 } else { x = x + 1 y = y - 1 p = p + 2( x - y ) + 5 } plotPoint ( x + xc, y + yc ) } |
Midpoint Circle Algorithm
x = 0, y = r, p = 1 - r plotPoint ( x + xc, y + yc ) while x < y { if p < 0 { x = x + 1 p = p + 2x + 3 } else { x = x + 1 y = y - 1 p = p + 2( x - y ) + 5 } plotPoint ( x + xc, y + yc ) } |
Midpoint Circle: Second Order DifferencesKey idea: Just as we calculate x and y incrementally, we can also calculate deltaE and deltaSE incrementally |
Midpoint Circle: Second Order DifferencesKey idea: Just as we calculate x and y incrementally, we can also calculate deltaE and deltaSE incrementally caseE: deltaEold = 2xp + 3 deltaEnew = 2xp + 5 deltaDeltaE = 2 deltaDeltaSE = ( 2(xp - 1) - 2yp + 5 ) - ( 2xp - 2yp + 5 ) = 2 |
Midpoint Circle: Second Order DifferencesKey idea: Just as we calculate x and y incrementally, we can also calculate deltaE and deltaSE incrementally caseE: deltaEold = 2xp + 3 deltaEnew = 2xp + 5 deltaDeltaE = 2 deltaDeltaSE = ( 2(xp - 1) - 2yp + 5 ) - ( 2xp - 2yp + 5 ) = 2 caseSE: deltaDeltaE = (2xp + 5) - (2xp + 3) = 2 deltaDeltaSE = ( 2(xp + 1) - 2(yp - 1) + 5 ) - ( 2xp - 2yp - 5 ) = 4 |
Midpoint Circle: Second Order DifferencesKey idea: Just as we calculate x and y incrementally, we can also calculate deltaE and deltaSE incrementally caseE: deltaEold = 2xp + 3 deltaEnew = 2xp + 5 deltaDeltaE = 2 deltaDeltaSE = ( 2(xp - 1) - 2yp + 5 ) - ( 2xp - 2yp + 5 ) = 2 caseSE: deltaDeltaE = (2xp + 5) - (2xp + 3) = 2 deltaDeltaSE = ( 2(xp + 1) - 2(yp - 1) + 5 ) - ( 2xp - 2yp - 5 ) = 4 Starting out: deltaEstart = 2 * 0 + 3 = 3 deltaSEstart = 2 * 0 - 2 * R + 5 = 5 - 2R |
void MidpointCircle ( int radius, int value ) { int x, y, d, deltaE, deltaSE; x = 0; y = radius; d = 1 - radius; deltaE = 3; deltaSE = 5 - radius * 2; CirclePoints ( x, y, value ); while ( y > x ) { if ( d < 0 ) { /* Select E */ d += deltaE; deltaE += 2; deltaSE += 2; x ++; } else { /* Select SE */ d += deltaSE; deltaE += 2; deltaSE += 4; x ++; y ++; } CirclePoints ( x, y, value ); } } |
Made by dynaPage 0.2 |