타원도 기본적으로 원 그리기와 동일한 알고리즘을 이용하여 그릴 수 있다. 하지만 원과 달리 좀 더 고려할 부분이 있다. 전체 영역을 $45^\circ$씩 8개 영역으로 나눈 후 한 영역에서만 계산하고 나머지는 대칭성을 이용하는 방법을 타원에는 바로 적용이 어렵다. 원에서 $45^\circ$ 기준선은 접선의 기울기가 $\frac{dy}{dx} = -1$인 점과 원점을 잇는 선분인데 타원에서는 이 관계가 성립하지 않는다. 타원 방정식 $\frac{x^2 }{ a^2} +\frac{ y^2}{b^2} = 1$ 에서 접선의 기울기가 $-1$인 지점은
$$x = \frac{a^2 }{ \sqrt {a^2 + b^2 }} , \quad y = \frac{ b^2 }{ \sqrt {a^2 + b^2 }}$$
로 주어진다. 이 지점까지는 $x$를 독립변수로 잡아야 하고, 나머지 $y = 0$까지는(1 사분면에서) $y$를 독립변수로 잡아야 한다. 나머지 분면은 대칭성을 이용하면 바로 그릴 수 있다.
픽셀 $(x_k , y_k)$에 점이 찍히면 다음은 어느 픽셀에 점을 찍어야 할까? $0\ge \text{기울기}\ge-1$이므로 오른쪽 옆이나 또는 오른쪽 아래 픽셀이 될 것이다. 이를 판별하는 식을 만들기 위해서 다음 식을 고려하자(나눗셈을 피하기 위해서 타원식에 $a^2b^2$을 곱했다):
$$F(x, y) = b^2 x^2 + a^2 y^2 - a^2 b^2$$
$(x_k, y_k )$가 타원 위의 점이면 $F=0$을 만족한다. 다음 점이 찍힐 후보 위치가 $(x_k+1, y_k)$ 또는 $(x_k+1, y_k-1)$이므로 중간 위치(Midpoint)에서 $F$의 부호를 기준으로 판별하도록 하자:
$$d_k = F(x_k+1, y_k-1/2) \\ d_k < 0 \quad \text {이면} \quad (x_k+1, y_k)$$
$$ d_k > 0\quad \text {이면} \quad (x_k+1, y_k-1)$$
이후에 판별식의 업데이트는
$$d_k <0~인 ~경우:\quad d_{k+1} = F(x_k+2, y_k-1/2) = d_{k} + b^2 ( 2 x_{k+1} +1)$$
$$d_k \ge 0 ~인 ~경우: \quad d_{k+1} = F(x_k + 2, y_k -3/2) = d_{k} + b^2 (2x_{k+1} + 1)- 2a^2 y_{k+1}$$
로 주어진다. 시작 픽셀에서 판별식의 값은
$$ x_0 = 0, y_0 = b \quad \Rightarrow\quad d_0 = F(1, b-1/2) = (4 b^2 + a^2 (1 - 4 b)) / 4$$
다음 문제는 $x$가 독립변수로써 얼마나 사용되고, 어느 지점에서 $y$가 독립변수가 되어야 하는가를 알아내는 것이다. 기울기 $dy /dx$ 가 0에서 -1 사이인 지점까지 $x$가 독립변수이므로, 우선 타원식을 미분하면
$$2b^2 x + 2a^2 y \frac{dy}{dx} = 0 $$
$$ \Rightarrow b^2 x = -a^2 y \frac{dy}{dx} = a^2 y \left| \frac{dy}{dx}\right| \le a^2 y, \quad -1 \le \frac{dy}{dx} \le 0 $$
$$ \therefore \quad b^2 x \le a^2 y$$
이 조건이 만족하는 동안 $x$를 독립변수로 사용하여 그리기를 한다.
$y$가 독립변수인 구간으로 넘어가자. 이 경우는 $x_0=a, ~y_0=0$에서 출발하면 위 영역에서 $x_k$와 $y_k$의 역할을 바꾼 방식이 된다. $(x_k, y_k)$에 점이 찍히면 다음 후보는 $(x_k, y_k+1)$ 또는 $(x_k-1, y_k+1)$이다. 중간점이 $(x_k-1/2, y_k+1)$이므로 판별식은
$$ d_k = F(x_k -1/2, y_k +1)$$
로 주어진다. 이 판별식의 업데이트는
$$d_k <0~인 ~경우:\quad d_{k+1} = F(x_k - 1/2, y_k+2) = d_{k} + a^2 ( 2 y_{k+1} +1)$$
$$d_k \ge 0 ~인 ~경우: \quad d_{k+1} = F(x_k -3 / 2, y_k +2) = d_{k} +a^2 (2x_{k+1} + 1) - 2 b^2 x_{k+1}$$
로 주어진다. 그리고 시작 픽셀에서 판별식의 값은
$$ x_0 = a, y_0 = 0 \quad \Rightarrow\quad d_0 = F(a-1/2,0) = (4 a^2 + b^2 (1 - 4 a)) / 4$$
이다. 전체적인 코드는
// setPixel(CDC *pDC, int x, int y)에 (x, y), (-x, y), (x,-y), (-x,-y)를
// 동시에 그리도록 구현이 되어야 한다. 그리고 중심이 원점이 아닌 경우에는
// 평행이동 시키면 된다:
int x = 0, y = b ;
int aa = a * a ;
int bb = b * b ;
int d = (4 * bb + aa * (1 - 4 * b)) / 4 ;
setPixel (pDC, x, y) ;
while ( bb * x < aa * y) {
++x ;
if (d < 0) d += bb * (2 * x + 1); // (x+1, y) 선택;
else { // (x+1, y-1) 선택;
--y ;
d += bb * (2 * x + 1) - 2 * aa * y ;
}
setPixel(pDC, x, y);
};
//y-독립변수 구간;
x = a, y = 0;
d = (4 * aa + bb * (1 - 4 * a)) / 4;
setPixel(pDC, x, y) ;
while (bb * x > aa * y) {
++y ;
if (d < 0) d += aa * (2 * y + 1);
else {
--x ;
d += - 2 * bb * x + aa * (2 * y + 1);
}
setPixel(pDC, x, y);
}
물론 실수 연산을 하면, 아래의 코드로 타원을 그릴 수 있다. 접선의 기울기의 크기 $|dy/dx| = 1$ 인 점을 기준으로 하여 그 값이 1 보다 작은 지점에서는 $x$를 독립변수로, 큰 지점에서는 $y$를 독립변수로 잡으면,
x-구간 ===> b^2 * x < a^2 * y;
y-구간 ===> b^2 * x > a^2 * y;이므로, 아래처럼 쓸 수가 있다:
int aa = a * a, bb = b * b;
x = 0; y = b;
while (bb * x <= aa * y) {
y = (int)((double) b / a * sqrt(aa - x * x) + 0.5);
setPixel(pDC, x, y);
++x;
}
y = 0;
while (bb * x > aa * y) {
x = (int)((double) a / b * sqrt(bb - y * y) + 0.5);
setPixel(pDC, x, y) ;
++y;
}last update: 2021.04.08;
'Computational Geometry' 카테고리의 다른 글
| 삼각형 채우기 (0) | 2009.12.19 |
|---|---|
| Triangulation을 이용한 Imge Effect (0) | 2009.12.18 |
| Circle Drawing Algorithm (1) | 2008.06.03 |
| Wu's Line Algorithm (1) | 2008.06.02 |
| Brute Force Triangulation (1) | 2008.05.28 |
