728x90

타원도 기본적으로 원 그리기와 동일한 알고리즘을 이용하여 그릴 수 있다. 하지만 원과 달리 좀 더 고려할 부분이 있다. 전체 영역을 $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
Ellipse Drawing Algorithm  (0) 2008.06.04
Circle Drawing Algorithm  (1) 2008.06.03
Wu's Line Algorithm  (1) 2008.06.02
Brute Force Triangulation  (1) 2008.05.28
Posted by helloktk

댓글을 달아 주세요