A Study on Intersection Computation in Interval Arithmetic

(1)

178 한국 CAD/CAM 학회 논문집

제 15권 제 3 호 2010년 6월 pp. 178-188

인터벌 연산 기반의 곡면간 교차선 계산에 관한 연구

고광희*

A Study on Intersection Computation in Interval Arithmetic

Kwanghee Ko*

ABSTRACT

This paper addresses the problem of determining if two surfaces intersect tangentially or transversally in a mathematically consistent manner and approximating an intersection curve. When floating point arithmetic is used in the computation, due to the limited precision, it often happens that the decision for tangential and transversal intersection is not clear cut. To handle this problem, in this paper, interval arithmetic is proposed to use, which provides a mathematically consistent way for such decision. After the decision, the intersection is traced using the validated ODE solver, which runs in interval arithmetic.

Then an iterative method is used for computing the accurate intersection point at a given arc-length of the intersection curve. The computed intersection points are then approximated by using a B-spline curve, which is provided as one instance of intersection curve for further geometric processing.

Examples are provided to demonstrate the proposed method.

Key words :validated ODE solver, interval arithmetic, approximation, tracing method, tangential intersection, transversal intersection, surface-to-surface intersection

1. 서 론

CAD연구가시작된지 30여년이지난지금까지,

수많은이론적/기술적결과들이발표되었다. 그결과 다양한 CAD시스템이개발되었으며자동차, 항공, 조 선, ^건축^등^수많은^영역에서^중요한^도구로^사용되고

있다. ^특히 CAD^시스템은^모델을^생성하고^가시화^하

는역할에국한되지않고, ^다양한^해석^및^{시뮬레이션}

도구와의통합을통해서, ^제품의^설계^단계에서^최적

의결과물을얻기위한도구로써그역할을확장해왔 다. ^이러한 CAD^{시스템에서}^제일^핵심^사항은^바로 3

차원모델을생성하는것이다. 3차원모델의생성에 있어서여러문제들이있는데, 그중, 곡면의교차선 계산은가장어려운문제로꼽히고있다.

두곡면이교차할때, 교차부분이점, 선과면, 이 렇게세경우로발생할수있다. 이중, 교차부분이 점과면일경우는, 모델링할때, 특수한경우로분류

되며, 보통계산을진행하지않는다. 그에반해서두 곡면이선으로교차하는경우가모델링할때일반적 으로쓰인다. 본논문에서는두곡면이교차할때, 교 차부분이곡선을이루는경우만을고려하기로한다.

곡선을구하는방법에는대표적으로 lattice 방법^[1], subdivision ^방법^[2], ^그리고, tracing ^방법^[3,4]^을^들 ^수

있다. ^각^방법들에^대한^{장단점들은} [5]^에^잘^소개되

어있으므로본논문에서는생략하기로한다. ^이^세

방법들중에서많이쓰이는것은추적법이다. ^추적법

은교차곡선을 미분방정식으로정식화해서계산해 가는방법이다.

추적법을 사용하기 위해서는 먼저, 교차 곡선이

loop를이루고있는지의여부, 그리고, branch 점이있 는지등을파악해야하고, 또한특이점들과경계점들 을계산해서각교차곡선의시작점과끝점을구하는 것이선행되어야한다. 이러한작업을교차곡선의위 상학적분석이라고하며, 이에대한연구는많이진행

되어 왔다. 먼저 loop의 존재 유무는 collinear

normal vector를이용해서알수있다^[6]. 또한, branch

점이나 경계점들 및 기타의 특이점들(branch, u-

turning과 v-turning점들)은관련된방정식을풀어서찾

*정회원, 광주과학기술원

-논문투고일: 2009. 10. 05 -논문수정일: 2010. 03. 17 -심사완료일: 2010. 03. 22

(2)

을 수 있다^[5,7].

교차곡선의 위상학적 분석을 한 다음 각 교차곡선 의형태(횡단(transversal) 교차 또는 접선(tangential) 교차¹)를 결정하는 단계가 뒤따르며, 이를 위한 이론 은 비교적 알려져 있다^[5]. 이 판단은 추적법을 사용함 에 있어서 매우 중요한 부분이다. 그 이유는, 교차 곡 선이 어떤 것이냐에 따라서 추적법에서 사용해야 하 는 식이 달라지기 때문이다. 두 곡면 p(σ, t)와 q(u, v)를 생각해 보자. 여기서 σ, t, u, v는 매개 변수이고, 그 범위는 0 ≤ σ, t, u, v ≤ 1이다. 교차점에서 각 곡 면의 수직 벡터를 구하면 N^p(σ, t) = pσ× pt, N^q(u, v) = qu× qv가 되며, 여기서 아래첨자는 편미분을 뜻한 다. 이렇게 구한 수직 벡터의 방향을 이용해서 두 곡 면의 교차형태를 찾을 수 있다. 즉, |N^p × N^q|가 0이 아닐 경우에는 transversal 교차인지를 확실히 알 수 있다. 그렇지만, 0일 경우에는 tangential인지 아니면 높은 차수의 교차인지 판단이 어렵다. 여기서 높은 차 수의 교차란 교차점에서 높은 차수의 미분값이 0이 되 는 경우를 말한다. 따라서 본 논문에서는 논의의 범 위를 줄이기 위해서 tangential 교차만을 생각하기로 한다.

위에서 구한 식을 이용하면, 어떤 형태의 교차선 인 지를 파악할 수 있는데, 이 방법에는 한 가지 생각해 야 할 부분이 있다. 보통 계산에서는 부동소수점 연산 을 이용한다. 그런데, 컴퓨터에서 표현할 수 있는 부 동소수점의 정확도에 한계가 있기 때문에, 주어진 실 수를 표현하는 것에도 한계가 따르게 된다. 즉, 정확 한 실수를 표현하는 것은 일반적으로 불가능하다고 볼 수 있다. 예를 들어, 1.0/3.0 같은 숫자는 rounding 오차를 포함시켜야만 표현이 가능하다. 그런데, 주어 진 교차선의 형태를 판단하는 식은 부동소수점 연산 을 기반으로 하고 있으며, 연산의 결과가 0인지 아닌 지를 판단하는 것이므로, rounding에 의한 영향으로 인해서 잘못된 판단을 할 가능성이 많다. 초기에 tangential 교차로 모델링을 했지만, 실제로 연산을 해 보면, 0.0으로 나오는 경우는 드물고 0.0에 가까 운 값을 나타내게 된다. 이럴 경우, 이론적인 관점에 서 볼 때, 주어진 교차선 형태는 tangential이 아닌 transversal로 판단해야 한다. 실제 구현에서는 이러한 오차를 생각해서 적절한 tolerance를 도입하여 처리한

다. 그렇지만, 정밀한 모델링을 해야 하는 입장에서는 tolerance의 도입뿐만 아니라 어느 정도의 tolerance값 을 주어야 하는 지 정하는 것도 중요한 문제가 된다.

또 다른 문제는, 일단 교차선의 형태가 결정된 다 음, 얼마나 정확하게 그 교차선을 추적하는가 이다.

주어진 교차선을 구하는 문제는 미분 방정식으로 주 어진다^[5]. 미분 방정식의 해석적인 해를 구하는 것이 불가능하기 때문에, 수치적인 해석 방법을 도입해야 하며, 이를 위해서 Runge-Kutta 등과 같은 다양한 수 치해석 방법을 사용할 수 있다. 그런데, 이러한 방법 들은 기본적으로 근사적인 해를 구하는 방법이며, 또 한, 구현도 부동소수점연산을 근간으로 되어 있기 때 문에, rounding에 의한 오차가 항상 포함된다. 이에 대한 대응으로 validated ODE solver를 이용한 추적 법이 연구되기도 하였다^[8]. 그 동안 일반 수치해석 법 을 기반으로 추적법이 연구되어 왔으나, 수치 계산의 안정성/강건성의 측면에 있어서 미흡한 점이 있어왔 다. 그런데, [8]에서는 이러한 문제를 해결하기 위해서 validated ODE solver를 처음 교차곡선 계산에 도입 을 하였다. 이 방법은 수학적으로 정확한 해를 직접 구하지는 않지만, 그 해를 포함하는 영역을 구하는 방 법으로 진행된다. 따라서, 해의 존재성 및 유일성은 보 장이 되나, 실제 처리를 위한 하나의 해를 주지 못하 는 단점이 있다. 최근, 교차선 계산에서 validated ODE solver를 이용해서 구한 교차곡선의 오차 영역을 줄이거나^[9], 아니면 그 범위 안에서 하나의 최적 교차 곡선을 선택하는 문제가 소개되어 있다^[10]. 그렇지만 지금까지의 연구는 교차곡선의 종류를 미리 가정하고 난 다음 계산을 수행한 것이라서 실제 응용에서는 문 제를 야기할 수 있다.

이러한 문제들은 많은 경우에 있어서, 실제 기하 모 델링에서 주목을 받지는 못했다. 이는 interval 기반의 연산 특징에 기인한 측면이 강하다. 그렇지만, 정밀한 모델링 및 강건한(robust) 기하모델링의 측면에서 볼 때, 인터벌 연산을 기반으로 한 기하 모델링에 있어서 이론적인 분석이 필요하며, 기존의 연산방법에서 다 루지 못하는 문제까지 접근해야 할 필요가 있다. 본 논문에서는 이러한 문제들에 대해서 논의하고자 한 다. 먼저 교차선 형태의 결정에 있어서 부동소수점연 산을 이용할 때 발생할 수 있는 문제점을 살펴보고, 이를 해결 하기 위한 방법에 대해서 논의한다. 다음, 하나의 교차선을 구하기 위한 방법에 대해서 소개하 고자 한다. 이 방법은 [10]에서 소개된 방법과는 다른 접근법을 이용하고자 하며, 보다 개념적으로 이해하 기가 쉽다. 이를 통해서 교차곡선의 형태 결정시 수치

1본 논문에서 tangential 교차와 transversal 교차의 한글/한자 표현을 접선교차/횡단교차로 소개하고자 한다. 그렇지만, 아직 은 일반적으로 통용되는 공용어가 아니라서 본문에서는 영어 표현을 사용하였다.

(3)

한국CAD／CAM학회 논문집 제15권 제 3호 2010년 6월

180 고 광 희

계산의강인성을높이고, ^높은^정밀도로^교차점을^구

하는방법을제시해서인터벌연산기반의교차곡선 계산방법을실제모델링시보다효용성있도록하고 자한다.

2. Formulation

2.1교차곡선추적법

두매개변수 곡면 p(σ, t)와 q(u, v) (0≤ σ, t, u,

v ≤1)을생각해보자. 그러면두곡면의교차선은다 음의식을만족시키는점들의집합이된다.

(1)

이식을바탕으로하고, 곡선의길이를매개변수로 해서교차곡선을나타내는연립미분방정식을구하면 다음과같다.

(2)

여기서 아래 첨자는 편미분을 나타내고, Det는

determinant를나타낸다. 또한, N^p와N^q는교차점에서 각곡면의수직벡터이다. 위의연립미분방정식은 교차곡선의종류에상관없이교차곡선에서반드시만 족해야하는식이며, 교차곡선의 arc-length를파라미 터로해서표현한식이다. 본미분방정식에서중요한 것은교차곡선의진행방향인교차곡선의접선방향을 구하는것이며 transveral과 tangential일때구하는방 식이달라진다. 주어진교차곡선이 transversal 타입일 때, 교차곡선의진행방향c는

(3)

으로구할수있다. ^두^곡면이 tangential ^형태로^교차

를하게되면, ^{교차점에서} ^두^법선^벡터 ^N^p^와 ^N^q^는

서로평행하므로 위식 (3)을사용할수없게된다.

즉

(4)

이 0일경우에해당한다. 따라서이럴경우에는교차 점에서곡면의높은차수의미분값을이용해서교차

곡선의진행방향을결정해야한다. 먼저 tangential

교차점에서 normal ^곡률이^같다는^점을^이용해서^다

음과같은 2차식을얻을수있다.

(5)

여기서, b11, b12와 b22는 first & second fundamental form계수들로이루어진함수들이다. 이식은교차곡

선의종류가 tangential일경우에만족하는식이다. 이

를얻기위해서는 tangential 교차의성질인교차점에

서두곡면의법선벡터가같고, 그에따라서 normal

곡률이같다는특징을바탕으로구한식이다. 자세한 함수들의형태및유도과정은 [5]을참고하길바란 다. 이렇게주어졌을때, 교차곡선의진행방향c는다 음과같이구할수있다. 먼저b11≠0일경우,

(6)

이며, ^만일^b11= 0^이고, ^b22≠0^일^경우에는

(7)

를이용해서구한다. 식 (6)과 (7)은 tangential 교차일 경우, 교차곡선의진행방향을구하기위한식이다. 이 를이용해서교차곡선의접선방향을 알수있고식

(2)를풀어서최종교차곡선을구할수있다.

위의논의에서알수있는것은, ω의값에의해서 교차곡선을 구하기위해사용하는식이달라진다는 것이다. 이는곧추적법을사용하기위해서는먼저어 떤타입의교차곡선인지를알고있어야함을의미하 며, 이를판단하기위해서는교차선에서ω의값을계 산한다음그값이 0인지아닌지를확인해야한다. 그 p σ t( , ) q u v= ( , )

σ′ dσ

---ds Det c p( , ,_tN^p) N^p⋅N^p

---, ^{t′ dt}_ds--- ^{Det p}⁽ ^σ^{, ,}^{c N}^p⁾

N^p⋅N^p

---

= =

u′ du---ds ^{Det c q}⁽ ^{, ,}^v ^N^q⁾ N^q⋅N^q

---, ^{v′ dv}---_ds ^{Det q}⁽ ^t^{, ,}^{c N}^q⁾

N^q⋅N^q

---

= =

c N^p×N^q N^p×N^q

---

=±

ω= N^p×N^q

b₁₁( )σ′ ²+2^b12( ) bσ′ + ₂₂( )t′²=0

c νp_σ+p_t νp_σ+p_t

---, ν σ′---t′

= =

c p_σ+µp_t p_σ+µp_t

---, ^µ _σ′---^t′

= =

Fig. 1. Tangential하게 교차하고 있는 두 곡면.

(4)

렇지만, 앞서 언급한 바와 같이 부동소수점연산을 기 반으로 연산을 수행했을 경우에는 이 판단식이 잘못 된 결과를 줄 수 있다.

Fig. 1에서와 같이 두 개의 베지에 곡면을 생각해 보자. 여기서 하나의 곡면은 평면으로 주어 졌으며, 다 른 하나는 2차 곡면으로 주어졌고, 두 곡면이 서로 tangential하게 교차하도록 만들어졌다. 하나의 교차점 에서 ω를 구해보면 6.3569 × 10⁻¹⁷이 나온다. 이 값의 크기는 실제 응용 프로그램의 관점에서 보면 0.0에 가 깝다고 볼 수 있다. 그렇지만, 수학적인 관점에서 보 면, 이는 0.0이 아니다. 다시 말하면, 두 곡면이 서로 tangential하게 교차하도록 만들어졌고, 이에 따라서, ω값이 0.0이 되어야 하지만, 실제 계산을 해 보면, 0.0이 나오질 않는다는 것이다. 이럴 경우, 단순히 ω 값만을 이용해서 판단한다면, 주어진 두 곡면은 transversal하도록 교차한다고 봐야 타당할 것이다. 이 렇게 판단이 되면, 위상학적으로 오류를 범하게 되 며, 이후 문제를 일으킬 소지가 많다.

실제 응용에서는 tolerance 값을 부여해서 이보다 작을 경우, 0.0으로 판단하는 방법을 취하는데, 일반 적인 상황에서는 문제가 없지만, 수학적으로는 일관 성이 없는 방법이 된다. 따라서, 이론적으로 혼돈이 없 는 방법에 대한 고려가 필요하다.

인터벌 연산의 경우, 인터벌을 정의하기 위한 두 경계값들을 계산해야 하므로, 일반 부동소수점 연산 에 비해서 일반적으로 두 배의 연산량과 시간이 든다 고 볼 수 있다. 그렇지만, 일반 부동소수점은 많은 경 우에 있어서 정확한 표현 값을 이용해서 연산을 수행 할 경우, 제한된 정확도에 의해서 그 결과값을 정확 하게 표현 못하는 문제가 있다. 이에 반해 인터벌 연 산의 경우 항상 일관성 있는 값을 주게 된다. 본 논 문에서는 이러한 측면을 고려함과 동시에 validated ODE solver의 특성(해의 존재성과 유일성을 보장)을 이용해서 부동소수점연산기반의 일반적인 solver가 해결 할 수 없는 문제를 해결하고자 한다. 두 곡면 이 교차해서 교차선을 생성할 때, 하나의 교차선이 만들어지고, 두 교차선에서 두 곡면의 법선 벡터가 서로 근접하지 않을 경우에는 부동소수점 연산 기반 의 solver를 이용하더라도 문제없다. 그렇지만 많은 경우에 있어서 교차선을 추적할 때, 특이점 근처나 두 교차곡선이 근접할 경우를 생각할 수 있으며, [8]

에서도 언급된 바와 같이 부동소수점 연산 기반의 solver의 경우, 잘못된 결과를 낼 수 있는 반면, 인터 벌 기반의 validated ODE solver는 이러한 문제를 해결할 수 있다.

3. 인터벌 연산 기반 판별식

앞서 제기된 문제를 다루기 위해서 인터벌 연산을 사용할 수 있다. 인터벌 연산이 소개 된지는 오래 되 었다. 그렇지만, 기하 모델링에 도입된 것은 최근의 일 이다. 특히, 솔리드 모델링^[11,12], 근 계산^[13] 및 교차선 계산^[14]에 있어서 인터벌 연산의 적용가능성에 대한 연구가 진행되었다. 최근에 들어서는, validated ODE solver와 연관해서 인터벌 연산 기반의 교차곡선 계산 에도 이용되었다^[8].

두 곡면이 교차를 할 때, 먼저 교차곡선의 위상학적 배열이 분석되었다고 가정한다. 즉, [7]에 소개된 방법 을 사용해서 각 교차곡선의 시작점, 종점, loop, singular 점들을 찾은 다음 추적을 위한 각 교차 곡선 단위로 나누어졌다고 가정한다.

인터벌 연산을 본 논문에서 제기한 문제에 적용하 기 위해서는 모든 연산을 인터벌로 수행을 해야 한다.

이 중에서 2장에서 언급된 문제를 살펴보기로 하자.

주어진 교차가 tangential인지 transversal인지 판별을 위해서 ω값을 계산해야 하는데, 이 계산 또한 인터벌 을 바탕으로 이루어져야 한다. 이럴 경우, tangential인 지 아닌지를 판단하는 기준은 0이 [ω]에 포함되어 있 는지 아닌지가 된다. 여기서 [ ]의 기호는 인터벌 값을 의미한다. 즉, 0∈[ω]일 경우에는 tangential교차로, 그 렇지 않을 경우에는 transversal교차로 판단하게 된다.

앞서 주어진 예(Fig. 1)를 이용해서 계산을 해 보면 다 음과 같다. 먼저 ω를 인터벌연산 기반으로 계산을 하 면 [0,1.0572 × 10⁻¹⁵]가 된다. 이 인터벌은 0을 포함하 고 있으므로, 주어진 교차가 tangential인지를 알 수 있 다. 이 방법은 정확히 0.0인지 아닌지를 보는 것이 아 니라 0.0이 범위에 포함되어 있는지 아닌지를 보는 것 이기 때문에, 판단에 있어서 혼동을 일으키지 않는다.

두 곡면이 교차하게 될 때, ω값을 이용해서 교차의 형태를 판단하게 되면, 주어진 교차가 transversal인지 tangential인지 알게 된다. Transversal로 교차할 경우 는 위상학적 배열로부터 시작점과 끝점을 쉽게 알 수 있으므로 교차곡선을 계산하는 것이 어렵지 않다. 그 렇지만, tangential하게 교차할 때, 다음의 세 가지 경 우를 생각해야 한다.

• 두 곡면이 한 점에서 tangential하게 교차할 때.

• 두 곡면이 tangential하게 교차를 하면서, 교차 곡 선을 이룰 때.

• 두 곡면이 겹쳐질 때.

이 세 가지 경우에서 본 논문에서는 두 번째만을 고려하고자 한다.

(5)

한국CAD／CAM학회 논문집 제15권 제 3호 2010년 6월

182 고 광 희

두 polynomial ^곡면이 ^교차를 ^하고, ^그 ^교차되는

부분은곡선을이룬다고가정한다. 이럴경우, 제일먼 저해야하는것은, 그교차곡선이 tangential 교차곡 선인지아닌지를파악해야하는데, 앞서언급한바와 같이ω값을교차곡선상에서계산을한다음, 0이포 함되는지아닌지를확인하면가능하다. 이럴때, 한 가지고려해야할문제점이있다. 실제연산에서는교 차곡선의모든점에서ω값을계산하고판단하는것은 불가능하다. 그래서, 교차곡선상의어느한점에서

tangential 교차임을확인하면, 그나머지부분에대해

서도 tangential 교차임을알수있는것이필요하다.

여기서, 추적법을사용하기때문에, 교차곡선의시작 점은주어지므로, 확인하는점을이점으로고려하기 로한다. 이러한것이사실임을보이기위해서다음과

같은논의를할수있다. ^두 polynomial ^곡면이^교차

를하고, ^그^교차가^곡선을^이룬다고^가정한다. ^그러

면, ^그^{교차곡선이} tangential ^{교차곡선일}^경우, [14]^의 Theorem 2^에^의해서, ^그^교차^곡선은, loop^를^이루고

있지않는이상, ^반드시^곡면의^한^{경계점으로부터}^시

작해서다른경계점에서끝나게된다. ^이 theorem^을

이용하면, 시작점에서 tangential교차곡선임이확인

되면, 그전체의 교차곡선이 tangential교차곡선임을 알 수 있게된다. 이 논의를 바탕으로, 시작점에서

tangential 교차가아닐경우, 그나머지부분에대해서

도 tangential 교차가일어나지않음을확인할수있다.

4. 교차 곡선의 추적

교차곡선의타입이결정된다음에는주어진미분방 정식을풀어서교차곡선을구하게된다. 이미분방정 식을풀때, 여러가지수치계산법을적용할수있는

데, 인터벌연산기반의방법중에서 [8,15]에서소개

된 validated ODE solver^를^사용한다. ^일반 solver^가

초기시작점에서오차조절을하면서하나의근사해

를구하는반면, validated ODE solver^는^정확한 ^해

를포함하는영역을해의존재성과유일성을점검해 가면서구하는방법이다. ^따라서^시작점을^기준으로

validated ODE solver를이용해서교차곡선을 구하

면, 정확한교차곡선을포함하는영역을구할수있 다. Validated ODE solver는 기본적으로 predictor- corrector의틀을갖추고있다. predictor단계에서는해 의 존재성과 유일성이 보장되는 영역을 구하고,

corrector 단계에서는그영역을줄이는방식을취한

다. 각단계에서의계산은인터벌연산을기반으로 한다.

교차곡선을추적하기위해서시작점과끝점을구 해야하며이는위상학적분석을통해서구할수있 다. 시작점이주어지게되면, 교차곡선에서만족해야 하는미분방정식인식 (2)를풀어야한다. 시작점은인 터벌로주어지며, 이를바탕으로정확한교차곡선을

포함하는 영역을 validated ODE solver를 이용해서

구하게된다.

이경우, [10]에서보여진바와같이, 하나의근사

교차곡선을선택하는것이필요하며, 최적화기법을 이용해서점진적으로가장근사한교차곡선을얻을 수있다. 그렇지만, 이방법은최적화를하는데시간

이 많이 걸리는 단점이 존재한다. Validated ODE

solver를이용한교차곡선의추적에대한자세한사

항은 [8]를참고하길바란다.

5. 교차점의 계산 및 교차곡선의 근사

본장에서는 validated ODE solver^를^사용해서^구한

결과에서, ^정확한^교차점을^계산하고, ^계산된^교차점

을바탕으로하나의근사곡선을구하는방법을소개 한다. 본방법은두단계로구성이되어있다. 첫번째 단계에서는먼저 validated ODE solver에서연산의기 반이되는점들에서높은정확도로교차점들을구한

다. 여기서연산의기반이되는점들은 validated ODE

solver에서사용하는계산점을의미하며, 이계산점에

서교차점을수치해석법을이용해서정확하게구할 수있다. 여기서정확도는응용범위에따라다르지 만, 본논문에서는 10⁻¹⁷로근사되도록하는것으로 가정하였다. 주어진미분방정식은 arc-length를매개 변수로이용해서, 정식화되어있으며이연산의기반 이되는점들은 arc-length 값으로주어진다. Validated ODE solver는각각의 arc-length 값에대해서정확한 교차점을포함하는인터벌값을각매개변수에대해 서계산한다. ^두^번째^{단계에서는}^이렇게^구한^인터벌

값들에서정확한교차점을찾는다. ^이렇게^구한^교차

점들을바탕으로, ^그^점들을^가장^잘^근사^시키는^곡

선을구하고, ^이를^{근사교차곡선으로}^사용한다.

5.1 교차점의계산

두곡면p(σ, t)와q(u, v)가서로교차하며, 그교 차된부분은곡선을이룬다고가정한다. 이때, 하나의 매개변수σ는상수(σ0)로고정되어있다고가정한다.

이렇게되면, Fig. 2에서보여진것과같이곡면p로

부터하나의 iso-parametric 곡선 f(t) =p(σ0, t)을얻 을수있다.

(6)

이 문제는 결국 곡선과 곡면의 교차로 정식화 할 수 있게 된다.

(8) 위의 방정식 (8)은 세 개의 미지수와 세 개의 방정 식으로 구성되어 있으므로 유일 해를 구할 수 있다.

5.1.1 Transversal Intersection ^경우

이 경우에는 뉴튼법을 이용해서 식 (8)의 해를 쉽게 구할 수 있다. 이 방법은 기본적으로 lattice 방법^[1]과 동일하다.

여기서 인터벌 기반의 방법대신 일반 수치해석법을 사용하였다. 그 이유는, 인터벌 기반의 방법을 사용할 경우, 식 (8)을 만족시키는 정확한 해를 포함하는 영 역을 얻을 수 있으나, 하나의 해를 구하기 위해서는 그 영역 내에서 선택을 해야 한다. 이 선택을 위한 방 법으로 뉴튼법을 사용하였다.

5.1.2 Tangential Intersection 경우

두 곡면이 tangential하게 교차할 경우, 주어진 방정 식 (8)을 직접 뉴튼법을 사용해서 풀 수 없다. 그 이 유는 주어진 식에서 계산되는 Jacobian 행렬이 tangential 교차일 경우에는 singular가 되기 때문에 뉴 튼법의 적용이 불가능하다. 이를 위해서 새로운 방법 을 고안해야 한다.

교차부분에서 곡면 q의 법선 벡터는 f(t)의 접선 벡 터와 직교해야 한다. 이 조건을 도입하면 다음과 같은 추가의 식을 얻을 수 있다.

(9)

따라서, 식 (8)과 (9)를 합쳐서 모두 세 개의 미지 항과 네 개의 방정식을 얻을 수 있다. 이를 풀기 위해 서 다음과 같은 식을 세운다.

(10) 이 식에서 Φ가 0이 되는 u, v, t 값이 앞서 구한 방정식의 해가 되며, 이는 곧 Φ을 최소화하는 u, v, t 를 구하는 것과 같다. 위의 식이 최소가 되는 점에서 는 다음의 세 식이 만족해야 한다.

(11)

이것을 만족시키는 u, v, t 값을 구하기 위해서 여러 가지 수치해석 방법을 도입할 수 있으며, 본 논문에서 는 뉴튼법을 사용하였다.

5.1.3 Iterative Scheme

앞서 소개한 validated ODE solver를 이용해서 교 차곡선 미분 방정식을 풀면, 각각의 arc-length 값, s 에 대해서 u, v, σ, t에 해당하는 인터벌 값들을 구할 수 있다. 그렇지만, 이 방법은 하나의 선택된 매개 변 수 값에 대해서 나머지 변수 값들을 구하는 방법이어 서 다음과 같은 문제점이 있다. 우선 선택된 σ0에 대 해서 식 (8)을 만족시키는 t, u, v를 5.1.1 또는 5.1.2 방법을 이용해서 구했다고 가정하자. 그러면, 일단은 교차곡선 위에 있는 점 중에서 매개변수 값 σ0에 해 당하는 t, u, v를 구한 것이 된다. 그런데, Fig. 3에서 보여진 바와 같이 σ0은 하나의 arc-length 값 sj에 해 당하는 인터벌 [σ]에서 선택된 값이다. 따라서, sj에 해당하는 교차곡선 위의 정확한 σ값(σexact)이 일반적 f t( ) q u v= ( , )

∂q∂u --- ∂q

---∂v

⎝ × ⎠

⎛ ⎞ ∂p ---∂t

⋅ σ σ= ₀=0

Φ t u v(, , ) f q( – ) f q⋅( – ) ∂q --- ∂q∂u

---∂v

⎝ × ⎠

⎛ ⎞ ∂p ---∂t

⋅ σ σ= ₀

⎝ ⎠

⎛ ⎞²=0 +

=

∂Φ∂t

--- 0, ∂Φ= --- 0∂u= , ∂Φ--- 0∂v= Fig. 2. Tangential하게 교차하고 있는 두 곡면과 iso-

parametric 곡선.

Fig. 3. 계산된인터벌에서선택된 σ0과 arc-length^값 ^s와의

관계.

(7)

한국CAD^／CAM^학회^논문집 ^제15^권^제3^호 2010^년 6^월

184 ^고^광^희

으로는아니므로, ^sj가아니라sj± δ (0 <^δ)^에^해당하

는교차곡선위의점을구하는것이된다. 따라서, 주 어진sj에해당하는교차선위의점을나타내는매개 변수값을구하기위해서는새로운알고리즘이필요 하다.

각각의인터벌에서가장정확한값들을구하기위 해서는다음의식을만족시키는값을찾아야한다.

(12)

그렇지만, 각매개변수의인터벌값에서위의식을 만족시키는 하나의 u, v, σ, t 값 들을구하는것은 쉬운일이아니다. 근사적으로, 각인터벌의중앙점을 선택할수있다. 그렇지만, 일반적으로주어진식 (12)

를만족시키지는못한다. 그래서식 (12)를가장근사 하게만족시키는매개변수값을구하기위해서다음 과같은알고리즘을사용하였다.

먼저, û에^대해서^인터벌 ^값[ûl, ûh]^가^{주어졌다고}

가정한다. ^이 ^값을 ^바탕으로 ^{알고리즘을} ^구성하면 Table 1^과^같다.

여기서함수 NewtonU(u, v, σ, t)는 u의값이주어졌 을때, 교차곡선의식 (12)를가장잘만족시키는 v,

σ, t를구해주는함수이며, 5.1.1과 5.1.2절에서소개된 방법을이용해서구현하였다. 본알고리즘에서 Line 4

에서계산되는 error^함수는^최소값이 0^인^값을^갖는

함수이다. ^그렇지만, ^함수의^형태가 monotone^하는지

는항상보증할수없는문제점이있다. ^이를^보완하

기위해서 iteration^의^최대^횟수(N)^를^제한하는^부분

을적용하였다. ^본^{알고리즘은}^{개념상으로} bisection^방

법하고비슷하며, ^분할된^인터벌이 tolerance^보다^작을

경우 iteration이멈추게된다. 본알고리즘은 tangential

과 transversal 교차곡선의 두경우모두사용할수

있다.

5.2 교차점의근사

본절에서는앞에서소개한방법을이용해서구한

정확한교차점을 B-spline 곡선으로근사시키는방법

을소개한다. ^본^{논문에서는} 3^차원^{공간상에서}^직접

교차곡선을근사시키지않고, 2차원매개변수공간 에서근사시키는방법을고려한다. 본방법을 3차원 에서교차곡선을근사시킬때에도직접이용할수도 있다. 먼저 각 arc-length si에 대해서, 매개변수 값 Li= (ui, vi), i = 1, 2, …, n이주어졌다고가정한다.

그러면다음과같은식이성립한다.

(13)

여기서kuv는uv 영역에서근사된곡선을나타내며, lj

는 B-spline의조정점들, 그리고Bj, 4(s)는 knot vector T를이용한 B-spline basis함수이다. 위의식에서구해 야할것은lj이며이를행렬식으로쓰면다음과같다. (14)

이행렬식은 singular value decomposition^을 ^통해

서풀수있다. ^추가로, ^{행렬식으로}^구한^해를^조절해

서보다정확한근사곡선을구할수있다. ^이를^위해

서식 (13)을다음과같이구성한다.

(14)

여기서, ∆l은조정량을나타낸다. 이식은다음과같 이쓸수있다.

(15)

이방정식을만족시키는∆l을구하고, 이를식 (14)

에적용시키면, Li에보다더근사된곡선을얻을수 있다.

E u v σ t( , , , )= p σ t( , ) q u v– ( , ) =0

Table 1. Iteration algorithm 1.ûmid= (ûl+ûh)/2

2.Umidl= (ul+umid)/2, umidh= (umid+uh)/2

3. NewtonU(umidl, v, σ, t); NewtonU(umidh, v, σ, t) 4.Êl = Ê(ûmidl, ^v, σ, ^t); Êh = E(ûmidh,^v, σ, ^t);

5. If(Êl≤E_h) ûh=ûmid. Otherwise ûl=ûmid;

6. If(|uh− ul|<TOL) break. If the number of iteration exceeds N, break. Otherwise go to Step 1.

L_i k_uv( )s_i l_jB_{j 4}_, ( )s_i

j 1= n

= = ∑

Bl L=

L_i k_uv( )s_i ⁽l_j+∆l_j^)Bj 4, ( )s_i

j 1= n

= = ∑

L_i l_jB_{j 4}_, ( )s_i

j 1= n

–∑ ∆ Bl_j _{j 4}_, ( )s_i

j 1= n

= ∑

Fig. 4. 매개변수공간상의곡선과 3차원공간상의교차곡선 과의관계.