. 방법 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 );
}
