[CG Algorhtim]Midpoint circle algorithm

. 방법 1 : 원의 방정식에서 x값을 증가시키면서 y를 구하자.
  . 문제점
  . x가 원의 가장 왼쪽, 오른쪽 근처에서 원 위의 점들이 듬성듬성 찍힌다.
  . sqrt() 함수를 써야 한다. (느리다.)
  . y = yc +-sqrt(r^2-(x-xc)^2)

. 방법 2 : Polar coordinate를 이용하자.
  . 듬성듬성찍히는 문제를 해결
  . sin(), cos() 함수를 써야 한다. (느리다.) 
  . x = xc + rcos(theta)
  . y = yc + rsin(theta)

. 방법 3
  . 8-way symmetry를 이용하자.(x축 대칭, y축 대칭, y=x 대칭)
  2 x 2 x 2 = 8, 1/8, 45도만 계산하면 된다.
  . 북~북서쪽의 45도를 계산하자.(듬성듬성하지 않게)
  . Midpoint line algorithm을 응용하자.

void 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 = d + x * 2.0 + 3;
  ++x;
     }
     else {
        d = d + (x - y) * 2.0 + 5;
  ++x;
  --y;
     }
     CirclePoints ( x, y, value );
  }
}

. 방법 4
  . floating point 연산을 없애자

void 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 = d + x * 2 + 3;
  ++x;
     }
     else {
        d += (x - y) * 2 + 5;
  ++x;
  --y;
     }
     CirclePoints ( x, y, value );
  }
}

. 방법 5
  . loop 내의 곱셈을 없애자.
  . Second Order Differences
  . Key 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 );
  }
}

참고)
http://www.cs.umbc.edu/~rheingan/435/pages/res/gen-3.Circles-single-page-0.html

Midpoint Circle Algorithm
Implicit Equation
  f(x,y) = x^2 + y^2 - R^2
     f(x,y) > 0  =>  point outside circle
     f(x,y) < 0  =>  point inside circle

Midpoint Criteria
  f(M) = f(xp+1, yp - 1/2)
       = (xp + 1)^2 + (yp - 1/2)^2 - R^2

  d >= 0 choose SE
       next M: +1 in x, -1 in y

  d <  0 choose E
       next M: +1 in x

Book 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

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