logging in or signing up Mid Point Circle Algorithm john1129 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 285 Category: Education License: All Rights Reserved Like it (1) Dislike it (0) Added: January 13, 2011 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Circle Midpoint Algorithm : Circle Midpoint Algorithm draw pixels in this octant (draw others using symmetry) (0,R) (0,-R) (R,0) (-R,0) Implicit function for circle on circle inside outside x+ y+ Choosing the Next Pixel : Choosing the Next Pixel choose E choose SE decision variable d Change of d when E is chosen : Change of d when E is chosen Change of d when SE is chosen : Change of d when SE is chosen Mold (x, y) (x+1, y) E SE (x+1, y+2) (x+2, y+2) Mnew Initial value of d : Initial value of d (0,-R) M0 (1,-R) (1,-R+1) Midpoint Circle Algo : Midpoint Circle Algo x = 0; y = -R; d = 5/4 – R; /* real */ setPixel(x,y); while (y > x) { if (d > 0) { /* E chosen */ d += 2*x + 3; x++; } else { /* SE chosen */ d += 2*(x+y) + 5; x++; y++; } setPixel(x,y); } New Decision Variable : New Decision Variable Our circle algorithm requires arithmetic with real numbers. Let’s create a new decision variable h h=d-1/4 Substitute h+1/4 for d in the code. Note h > -1/4 can be replaced with h > 0 since h will always have an integer value. New Circle Algorithm : New Circle Algorithm x = 0; y = -R; h = 1 – R; setPixel(x,y); while (y > x) { if (h > 0) { /* E chosen */ h += 2*x + 3; x++; } else { /* SE chosen */ h += 2*(x+y) + 5; x++; y++; } setPixel(x,y); } Second-Order Differences : Second-Order Differences Note that d is incremented by a linear expression each time through the loop. We can speed things up a bit by tracking how these linear expressions change. Not a huge improvement since multiplication by 2 is just a left-shift by 1 (e.g. 2*x = x<<1). 2nd Order Difference when E chosen : 2nd Order Difference when E chosen When E chosen, we move from pixel (x,y) to (x+1,y). Slide 11: 2nd Order Difference when SE chosen When SE chosen, we move from pixel (x,y) to (x+1,y+1). New and Improved Circle Algorithm : New and Improved Circle Algorithm x = 0; y = -R; h = 1 – R; dE = 3; dSE = -2*R + 5; setPixel(x,y); while (y > x) { if (h > 0) { /* E chosen */ h += dE; dE += 2; dSE += 2; x++; } else { /* SE chosen */ h += dSE; dE += 2; dSE += 4; X++; y++; } setPixel(x,y); } You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
Mid Point Circle Algorithm john1129 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 285 Category: Education License: All Rights Reserved Like it (1) Dislike it (0) Added: January 13, 2011 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Circle Midpoint Algorithm : Circle Midpoint Algorithm draw pixels in this octant (draw others using symmetry) (0,R) (0,-R) (R,0) (-R,0) Implicit function for circle on circle inside outside x+ y+ Choosing the Next Pixel : Choosing the Next Pixel choose E choose SE decision variable d Change of d when E is chosen : Change of d when E is chosen Change of d when SE is chosen : Change of d when SE is chosen Mold (x, y) (x+1, y) E SE (x+1, y+2) (x+2, y+2) Mnew Initial value of d : Initial value of d (0,-R) M0 (1,-R) (1,-R+1) Midpoint Circle Algo : Midpoint Circle Algo x = 0; y = -R; d = 5/4 – R; /* real */ setPixel(x,y); while (y > x) { if (d > 0) { /* E chosen */ d += 2*x + 3; x++; } else { /* SE chosen */ d += 2*(x+y) + 5; x++; y++; } setPixel(x,y); } New Decision Variable : New Decision Variable Our circle algorithm requires arithmetic with real numbers. Let’s create a new decision variable h h=d-1/4 Substitute h+1/4 for d in the code. Note h > -1/4 can be replaced with h > 0 since h will always have an integer value. New Circle Algorithm : New Circle Algorithm x = 0; y = -R; h = 1 – R; setPixel(x,y); while (y > x) { if (h > 0) { /* E chosen */ h += 2*x + 3; x++; } else { /* SE chosen */ h += 2*(x+y) + 5; x++; y++; } setPixel(x,y); } Second-Order Differences : Second-Order Differences Note that d is incremented by a linear expression each time through the loop. We can speed things up a bit by tracking how these linear expressions change. Not a huge improvement since multiplication by 2 is just a left-shift by 1 (e.g. 2*x = x<<1). 2nd Order Difference when E chosen : 2nd Order Difference when E chosen When E chosen, we move from pixel (x,y) to (x+1,y). Slide 11: 2nd Order Difference when SE chosen When SE chosen, we move from pixel (x,y) to (x+1,y+1). New and Improved Circle Algorithm : New and Improved Circle Algorithm x = 0; y = -R; h = 1 – R; dE = 3; dSE = -2*R + 5; setPixel(x,y); while (y > x) { if (h > 0) { /* E chosen */ h += dE; dE += 2; dSE += 2; x++; } else { /* SE chosen */ h += dSE; dE += 2; dSE += 4; X++; y++; } setPixel(x,y); }