728x90

한 개의 Bezier 곡선을 이용해서 원을 표현할 수 없음은 잘 알려진 사실이다. 그럼 Bezier 곡선을 이용해서 얼마나 원(호)을 잘 근사할 수 있을까? 3차 Bezier 곡선을 이용해서 원점에 중심을 둔 반지름 1인 원의 1 사분면 원호를 근사해보도록 하자. 3차 Bezier 곡선은 4개의 control point $\{ \mathbf {P}_i | i=0,1,2, 3\}$이 주어진 경우

$$ \mathbf {B}(t) = (1-t^3) \mathbf {P}_0 + 3t(1-t)^2 \mathbf {P}_1 + 3t^2 (1-t) \mathbf {P}_2 + t^3 \mathbf {P}_3$$

으로 표현된다. 원호 근사에 필요한 control point는 다음 조건을 부여하면 얻을 수 있다. (1) $t=0,1$일 때 원 위에 있어야 하므로

$$\mathbf {B}(t=0) = (0,1) \quad \rightarrow \quad \mathbf {P_0} = (0,1)$$

$$\mathbf {B}(t=1) = (1,0) \quad \rightarrow \quad \mathbf {P_3} = (1,0)$$

그리고 또 그 두 지점에서 접선의 기울기가 원의 기울기와 같아야 하므로

$$ {\mathbf {B}'}(t=0) \propto (1,0)\quad \text {and}\quad {\mathbf {B}'}(t=1)\propto (0,-1)$$

에서

$$ \mathbf {P}_1 = (k, 1), \quad \mathbf {P}_2 = (1, k)$$

처럼 잡을 수 있다. (2) Bezier 곡선의 중간지점이  원 위에 있도록 조건을 부여하면

$$ \mathbf {B}(t=1/2) = (1/\sqrt {2}, 1/\sqrt {2})$$

을 얻고, 이를 이용하면

$$k= \frac {4}{3} (\sqrt {2}-1) = 0.5522847498...$$

을 얻는다.

그럼 원에서 얼마나 벗어날까? 원 중심에서 거리를 차이를 구해보면 Bezier 곡선이 항상 원의 바깥으로 치우쳐 있음을 알 수 있다:

$$\Delta(t) = ||\mathbf {B}(t)||-1\ge 0$$ 

최대로 벗어나는 정도는 $t=(3\pm \sqrt{3})/6$일 때 $\Delta_\text {max}=\frac{1}{3}\sqrt{ \frac{71}{6}-2\sqrt{2}}-1=0.00027253...$이므로 대부분의 경우 크게 벗어남이 없는 원의 근사를 준다.

(2-2) $t=1/2$에서 Bezier 곡선이 원을 통과하는 조건 대신 원에서 벗어남을 최소로 하는 조건을 부여하면 더 좋은 근사를 얻을 수 있다:

$$k=\text{argmin}|\Delta|_\text{max}$$

이 경우  Bezier 곡선은 원의 바깥에 놓이지 않고 교차하게 된다. $t=1/2$에서 최솟값, $t=\frac{1}{2}\left(1\pm \frac{\sqrt{3k^2+20k -12}}{2-3k}\right) $일 때 최댓값을 가지는데, 두 값의 절대값이 같게 되려면(closed form이 없다)

$$ k = 0.551915023...$$

을 선택해야 하고, 이 때 벗어남의 최대값은 $|\Delta|_\text{max} =  0.00019607...$이므로 더 좋은 근사가 된다.

 

(2-3) 또 다른 제한조건은 없을까? Bezier 곡선이 만드는 면적이 사분원의 면적을 표현하도록 제한을 가하는 경우:

$$\frac{\pi}{4} = \int_{0}^{1} \frac{1}{2}\left( B_y B'_x - B_x B'_y\right) dt \\ = \int_0^1  \left(-\frac{3}{2} \left(3 k^2 (t-1)^2 t^2+k \left(-2 t^4+4 t^3-6 t^2+4 t-1\right)+2 (t-1) t\right) \right)dt \\= \frac{1}{2}+\frac{3k}{5}-\frac{3k^2}{20}$$ 에서 

$$ k = 2 - \sqrt{ \frac{22 - 5 \pi }{3}} =0.551778477...$$

이다. 이 경우 면적은 같으나 벗어남 오차는 $t=1/2$일 때

$$|\Delta |_\text{max} = \frac{1}{8} \sqrt{332-40 \sqrt{66-15 \pi }-30 \pi }-1= 0.00026849...$$

로 주어지는데, 중심을 지나는 경우보다는 벗어남이 작지만 최소는 아니다.

(2-4) Bezier 곡선의 길이가 원주가 되는 제한조건을 걸 수도 있다:

$$\frac{\pi}{2}  = \int_0^1\sqrt{ (B'_x)^2 + (B'_y)^2}dt.$$

그런데 우측 적분이 closed form으로 주어지지 않는다. 때문에 $k$ 값을 구하기 위해서 전적으로 numerical method에 의존해야되는데,  그 결과만 쓰면

$$k=0.551777131...$$

'Computational Geometry' 카테고리의 다른 글

Bezier Curve Arc Length  (0) 2021.04.21
Bezier Curve Approximation of an Ellipse  (0) 2021.04.11
Bezier Curve Approximation of a Circle  (0) 2021.04.10
Bresenham's Line Algorithm  (0) 2021.04.07
Rotating Calipers  (3) 2021.03.31
Convex Hull Peeling  (0) 2021.03.29
Posted by helloktk

댓글을 달아 주세요

728x90

원을 그리기 위해서는 원의 방정식을 이용하면 된다. 반지름이 $r$인 경우에 원점이 중심인 원은 $x^2 + y^2 = r^2$이므로 (중심이 원점이 아닌 경우는 단순 평행 이동만 하면 되기 때문에 따로 취급하지 않는다), $x$를 독립변수로 잡으면 $y= \sqrt {r^2 - y^2}$으로 주어져서 1/2 사분면을 그릴 수 있다. 그리고 부호를 반대로 하면 3/4 분면에 그려진다. 그러나 $x$가 $r$에 근접하는 경우 $y$의 변화율이 급격해져서 $y$값이 연속적으로 그려지지 않는다. 이 문제는 전체 4 사분면을 45도 단위로 8개 영역으로 쪼개서 $x$와 $y$의 역할을 적당히 바꾸면서 그리면 이러한 문제를 피할 수 있다. 그러나, 여전히 실수 연산을 수행해야 하는 문제가 남아 있다. 이를 피하는 방법을 고안하도록 하자. 힌트는 Bresenham의 라인 알고리즘에서 얻을 수 있다. 우선, 영역을 $x = 0$에서 $x = y$인 90-도에서 45-도 사이의 구간만 생각하자. 이 구간에서 $y$의 변화율의 크기는 항상 0에서 1 사이 이므로, 8-방향으로 연결성을 갖도록 그리려면 현재의 점이 $(x, y)$로 주어지는 경우

          (x, y) ---> (x+1, y)     변화율 = 0;
                      (x+1, y-1)   변화율 = 1      (절대값)

의 두 가지 경우만 있다.  그럼 이 두 점 중 어느 것을 선택을 해야 하는가? 이것을 판별하기 위한 식은 이 두 점의 중심인 $(x, y - 1/2)$이 원의 내부에 있는가 또는 외부에 있는가를 보고서 결정하면 된다.

          (x+1, y-1/2) 이  원의 내부점인 경우---->(x+1, y)  선택
                           원의 외부점인 경우---->(x+1, y-1) 선택;

하면 각각의 상황에서 보다 정확한 원에 가까운 점을 선택한 것이 된다. 다음 점에서도 동일한 과정을 거치면 된다.

사용자 삽입 이미지

그러면 $(x+1, y-1/2)$가 원의 내부점인지 외부점인지를 항상 계산해야 하는가? 매 스텝마다 이것을 계산을 할 필요는 없다. 왜냐면 처음 $(0, r-1/2)$에서 계산을 하고

          d = x^2+y^2-r^2 at (0, r-1/2) ;
             = (5-4*r)/4  ; -> 이런 식으로 표현을 하는 것은 정수 연산만으로 
                               하기 위해서 계산 우선 순위를 조절한 것임.

이것과, $F(x, y)=x^2-y^2-r^2$ 라고 할 때,

(1),  $(x+1, y)$를 선택할 때 새로운 $d$값은 $(x+2, y-1/2)$에서 계산하므로

         d_old = F(x+1, y-1/2) = (x+1)^2+(y-1/2)^2-r^2 ;
         d_new = F(x+2, y-1/2) = d_old + 2*(x+1) + 1;

(2),  $(x+1, y-1)$를 선택할 때, 새로운 $d$값은 $(x+2, y-1-1/2)$에서 계산하므로

        d_old = F(x+1, y-1/2) = (x+1)^2+(y-1/2)^2-r^2 ;
        d_new = F(x+2, y-3/2) = d_old + 2 * ((x+1) -(y-1)) + 1;

인 관계를 이용하면 쉽게 정수 연산만으로 $d$값을 업데이트할 수 있다. 따라서 전체적인 코드는

   int x = 0, y = r ;
   int d = (5 - 4 * r) / 4;
   setPixel (x, y) ; 
   while ( x < y ) {
        ++x ;
        if (d < 0)                            // (x+1, y) 선택;
            d +=  2*x + 1;                    // ++x와 연관해서 잘 살펴야 한다.
        else {                                // (x+1, y-1) 선택;
            --y ;
            d += 2 * (x - y) + 1;             // ++x,--y;
        }
        setPixel(x, y);
   };

8 방향 대칭성으로 인해 점 $(x, y)$를 그리면 아래의 점도 그려야 한다 (처음 점 $(0, r)$은 4방향만, 그리고 $x=y$인 경우도 마찬가지나 따로 분리하기보다는 그냥 그리는 것이 더 낫다).

   {(x,-y), (-x,y), (-x,-y), (y,x), (y,-x), (-y,x),(-y,-x)}

단, 원의 중심이 원점이 아닐 경우는 전체적으로 평행이동을 시키면 된다.

사용자 삽입 이미지

'Computational Geometry' 카테고리의 다른 글

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
Polygon Triangulation (II)  (0) 2008.05.26
Posted by helloktk

댓글을 달아 주세요

  1. hansune 2008.09.10 00:40  댓글주소  수정/삭제  댓글쓰기

    와~ 그렇군요.