Mid Point Circle Algorithm

Views:
 
Category: Education
     
 

Presentation Description

No description available.

Comments

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); }

authorStream Live Help