14장. 스플라인 학습목표 제어점, 지역성, 컨벡스 헐 등의 용어가 지닌 개념을 명확히 이해한다.

Presentation on theme: "14장. 스플라인 학습목표 제어점, 지역성, 컨벡스 헐 등의 용어가 지닌 개념을 명확히 이해한다."— Presentation transcript:

1 14장. 스플라인 학습목표 제어점, 지역성, 컨벡스 헐 등의 용어가 지닌 개념을 명확히 이해한다.
선형조합에 의해 곡선을 만드는 방법을 이해한다. 구간별 곡선의 연결에 가해지는 제약조건을 이해한다. 허미트 스플라인, 베지에 스플라인, 너브스의 특징과 장단점을 이해한다. 곡선을 확장하여 곡면을 생성하는 방법을 이해한다.

2 스플라인(Splines) 목수들이 부드러운 곡선을 긋기 위해 사용하던 얇은 금속 띠
추(Ducks)의 무게에 의해 부드러운 곡선 수학의 발전에 의해 다항식으로 표현. 다항식 곡선=스플라인 용도 곡선설계, 곡면설계 영상 윤곽의 디지타이제이션(제어점+스플라인) 애니메이션의 동작경로

3 제어점(CP: Control Points)
곡선의 모양을 제어하는 특징적인 점 제어점의 추가, 삭제, 위치변경 등에 의해 곡선의 모습을 제어 구간(Segment) = 한 쌍의 제어점 사이 스플라인 = 구간별 다항식(Piecewise Polynomials) 곡선에 대한 어파인 변환 제어점에 어파인 변환을 가한 후 변환된 제어점에 곡선의 식을 가함.

4 스플라인 분류 보간 스플라인(Interpolating Splines) 제어점을 통과(Pass-Throughness)
근사 스플라인(Approximating Splines) 부드러움을 위해 제어점을 통과하지 않음 제어점은 곡선을 끌어당기는 역할 (Remote Control) 경우에 따라서 첫점과 마지막 점은 통과

5 스플라인의 지역성 지역성(Locality) 제어점을 움직일 때 여타 구간에 미치는 영향력
이미 설계완료된 부분에 영향을 미치지 않도록 작을수록 좋음. 3개 구간 vs. 9개 구간(아래 예제에서 변하는 구간의 수) 구간별로 서로 다른 계수의 다항식: 지역성 향상을 위함.

6 제어 그래프, 컨벡스 헐 제어 그래프(Control Graph, Control Polygon, Defining Polygon)
제어점들을 순서대로 선분으로 연결한 그래프 컨벡스 헐(Convex Hull) :스플라인 차수에 의해 모양 결정 제어 그래프 일부에 대해서 시작점과 끝점을 연결한 도형 구간별 3차 다항식: 4개의 인접한 제어점 구간별 2차 다항식: 3개의 인접한 제어점

7 컨벡스 헐 특성 컨벡스 헐 특성(Convex Hull Property) 스플라인이 컨벡스 헐 내부에만 존재할 경우
진동(Oscillation)이나 이탈(Overshoot)을 방지 제어점이 일직선(Co-linear)이면 스플라인은 직선 직선도 곡선과 동일하게 취급

8 파라미터 표현 y = x + 1 (0 ≤ x ≤ 4) (t, t + 1) or (t2, t2 + 1) or (3t, 3t + 1) 정규화 파라미터(Normalized Parameter) (4t, 4t + 1) 파라미터는 범위가 (0 ≤ t ≤ 1) 파라미터 표현의 장점 균등 길이 유한 기울기(예: x = 1) 차원의 확장이 용이: (t, t+1, t+3, 2t, …) cf. 현시적 표현

9 스플라인의 연속성(Continuity)
곡선의 부드러움(Smoothness) 제어점 부근에서의 곡선의 기울기(Slope)와 곡률(Curvature) 불연속, C0, C1, G1, C2 C1 연속 들어오는기울기 = 나가는기울기. 기울기 = 접선 = 1차 미분계수 G1 연속 기하학적(Geometric) 또는 시각적(Visual) 연속성 나가는 기울기가 들어오는 기울기의 상수배, 방향만 같음. C2 연속 들어오는 기울기의 변화율(Curvature, 곡률, 기울기의 기울기, 2차 미분계수) = 나가는 기울기의 변화율. 가장 부드러운 곡선. 이를 위해 제어점을 피해 갈수 있음 = 근사 스플라인

10 바이어스(Bias), 텐션(Tension)
Barsky의 Beta Spline 텐션(Tension) 곡선의 장력 즉 긴장도. 두 개의 제어점에 의해 정의된 하나의 구간에 적용 구간 BC가 AB보다 텐션이 높음. 바이어스(Bias) 제어점 근처에서의 곡선 행동 제어점 B에서 (a)는 나가는 방향으로 바이어스, (b)는 들어오는 방향으로 바이어스가 걸려있음.

11 카디날 스플라인(Cardinal Splines)
혼합함수(Blending Function) 점을 섞어 선분의 식을 표시 기반함수(Basis Function), 가중치 함수(Weighting Function) 이 경우 혼합함수는 (1-t), (t)이므로 선형 혼합함수

12 카디날 스플라인 (Cardinal Splines)
선분의 선형조합 m(t1)에서 t1 = 0 인 점 p1은 p(t)로 볼 때 t = 0인 점 m(t1)에서 t1 = 1 인 점 p2는 p(t)에서 t = 1/2 인 중간점으로 간주 m(t2)에서 t2 = 0 인 점 p2는 t = 1/2 따라서 t1 = 2t, t2 = 2t -1. 이를 윗 식에 대입

13 카디날 스플라인 (Cardinal Splines)
곡선의 선형조합 p2, p3 사이의 곡선. 굴절곡선은 2차함수로는 안되고 3차함수

14 카디날 스플라인 (Cardinal Splines)
제어점 p1, p2, p3, p4가 주어지면 곡선은 p2-p3 구간에서만 정의된다. 주어진 제어점들을 정확히 통과하는 보간 스플라인 C1 연속성을 지님. 지역성으로 인해 더 이상의 혼합을 가하지 않음. 4 개의 3차 기반함수에 의해 제어점 p1, p2, p3, p4를 혼합 기반함수:

15 허미트 스플라인(Hermite Splines)
양 끝점의 위치와 해당 점에서의 기울기에 의해 정의

16 허미트 스플라인(Hermite Splines)
좌변 첫 행렬의 역행렬을 곱해 MhPt를 구함

17 허미트 스플라인(Hermite Splines)
곡선의 개형 기울기 크기 변화, 기울기 방향변화

18 베지에 스플라인(Bezier Splines)
3 개의 제어점에 의한 베지에 곡선 베지에가 제안하기 이전에 이미 번스타인(Bernstein)에 의해 수학적으로 유도가 완료된 상태

19 베지에 스플라인(Bezier Splines)
선형혼합에 의함. 예시: 3개의 제어점, 4개의 제어점. 그림은 t = 1/3일 경우의 예

20 베지에 스플라인(Bezier Splines)
일반식 3개의 제어점에 의한 2차 베지에

21 베지에 스플라인(Bezier Splines)
2차 베지에 기반함수 J2,0(t),= (1-t)2, J2,1(t) = 2t(1-t), J2,2(t) = t2 기반함수 제어점이 곡선을 자신 쪽으로 끌어당기는 영향력 (가중치) t = 0 인 p0 에서는 J2,0(t)의 영향력만 1. 따라서 t = 0인 점에서의 곡선의 위치는 p0 점 자체 t = .5인 p1 에서는 p0 점의 영향력은 J2,0(.5) = .25, p1 점의 영향력은 J2,1(.5)=.5, p2점의 영향력은 J2,1(.5) = .25 만큼. 따라서 근사 스플라인

22 베지에 스플라인(Bezier Splines)
3차 베지에 곡선

23 베지에 스플라인(Bezier Splines)
베지에 곡선의 특성 주어진 제어점 중 처음 점과 마지막 점만 통과 주어진 제어점에 의해 형성되는 컨벡스 헐 내부에만 곡선이 존재(임의의 t에서 기반함수 값이 모두 양이며 그 합이 항상 1) 처음 점과 마지막 점에서 곡선의 기울기는 제어 그래프와 일치 4 개의 제어점에 의한 3차 베지에 곡선은 제어점 p0, p1, p2, p3 전 구간에서 정의됨. cf. 카디날 스플라인 n 개의 제어점이 주어지면 베지에 곡선은 파라미터 t에 대한 (n - 1)차 함수. 지역성을 감안하면 3차 정도가 좋으므로 4 개의 제어점 단위로 구간 구간을 잘라서 정의.

24 베지에 스플라인 개형

25 베지에 스플라인 구간별 베지에 곡선의 연결조건 G1 연속성이 요구됨. 베지에 스플라인은 허미트 스플라인의 특수한 경우

26 베지에 스플라인 중점 분할(Midpoint Subdivision)
재귀 호출(Recursive Call)에 의해 베지에 곡선을 그리는 방법 1개의 구간이 2개의 구간으로 나뉘어짐. 이를 반복적으로 적용 구간별 연속성이 보장됨(7-9-8이 직선상에 존재)

27 B-스플라인 구간별 연결에 C2 연속성 보장 더욱 부드러운 곡선 일반적으로 제어점을 통과하지 않음
인접한 곡선끼리 제어점을 공유 3차 스플라인이라면 3개의 제어점을 공유

28 B-스플라인 3차 B-스플라인 제어점 4개에 의해 1개의 구간 곡선이 정의됨.
3개의 제어점이 공유되므로 q0, ..., q6 까지 6개의 구간 곡선 구간별 파라미터 [0, 1]의 범위 대신 [i, i+1]의 범위에서 움직임. 나트(매듭, Knot): t = i일 때의  곡선 상의 점 나트벡터(Knot Vector): 연속된 나트 값의 집합. B-스플라인의 나트벡터: 균등 나트벡터(Uniform Knot Vector) 나트벡터: 제어점에 추가로 곡선에 대한 제어를 강화

29 B-스플라인 B-스플라인의 B는 기반함수(Basis)를 의미함.

30 B-스플라인 제어점 p3가 영향을 미치는 구간곡선
q0에 대해서 B3, q1에 대해서 B2,  q2에 대해서 B1, q3에 대해서 B0의 가중치. 제어점 p3가 이웃한 4개의 곡선에 주는 영향 점 a, a', b, b', c는 나트에서의 기반함수 값. 다항식이므로 C2 연속을 보장

31 B-스플라인 제어점별 기반함수의 중첩

32 B-스플라인 곡선을 제어점 쪽으로 끌어당길 필요성이 존재 방법 1: 제어점 반복 수학적으로는 모두 C2 연속
시각적으로는 (b)는 G1 연속, (c)는 G0 연속

33 B-스플라인 방법 2: 나트 반복. 3번 제어점 으로 당기기 위해 동일한 나트 값을 2번 나열. 나트 t4=t5=1 로 설정

34 B-스플라인 차등 B-스플라인(Non-Uniform B-Splines) 나트간격을 불규칙하게 함으로써 곡선의 모습을 제어

35 B-스플라인 일반적인 B-스플라인 = 차등 B-스플라인 재귀호출에 의한 B-스플라인 기반함수 생성

36 B-스플라인 균등 나트벡터의 기반함수와 결과

37 B-스플라인 차등 나트벡터의 기반함수와 결과

38 B-스플라인 차등 나트벡터의 사용 나트벡터 변경 결과 곡선의 모습을 예측하기 어려움
첫 제어점과 마지막 제어점을 통과하도록 하는데 사용 예: 나트벡터 (0.0, 0.0, 0.0, 3.0, 4.0, 5.0, 6.0, 7.0) 뾰족한 부분(Kink)이나 각진 모서리(Corner)를 표현할 때 사용 예: 나트벡터 (0.0, 1.0, 2.0, 3.0, 3.0, 5.0, 6.0, 7.0) 제어점 p2의 나트 값을 2번 나열 k차 기반함수 나트에서 C(k-1)의 연속성. 2차 기반함수는 나트에서 C1 연속성 나트 값이 한 번 중복될 때마다 연속성이 1차씩 감소. 아래 2차 기반함수에서는 원래 C1 연속이 C0 연속으로 바뀜.

39 너브스(NURBS) 원근변환 원근변환 된 모습의 곡선을 그려내려면 기반함수 자체가 유리함수(Rational Function)이어야 함 너브스(NURBS) 차등 유리 B-스플라인(Non-Uniform Rational B Spline) 제어점 마다 가중치 wi를 부여: 규칙곡선이 가능

40 너브스(NURBS) 너브스 표현 는 기반함수에 가중치에 의해 크기조절이 가해진 결과 크게 봐서 의 형태

41 너브스(NURBS) 곡선의 제어 3 가지 방법 나트벡터의 간격. 예: 불규칙 나트벡터
나트벡터의 반복. 곡선을 제어점쪽으로 끌어당김 제어점의 가중치. 곡선을 제어점쪽으로 끌어당김 베지에 곡선 너브스의 특수한 경우 양 끝 제어점을 통과 예:불규칙나트벡터 (0, 0, 0, 0, 1, 1, 1, 1)을 가진 너브스 모든 베지에 곡선은 너브스로 표현가능

42 스플라인 연산 첫번째 함수호출에 따른 오버헤드를 없앤 것이 두번째.
세번째 호르너 규칙(Horner’s Rule) 적용: 연산속도, 정밀성 향상

43 스플라인의 분할 더욱 정밀한 제어를 위해 베지에 곡선: 중점 분할, 1/3점 분할, …
너브스 곡선: 나트 추가에 의한 새로운 제어점 생성

44 스플라인 곡면(Spline Surfaces)
곡면은 평면의 집합으로 근사화 균등분할(Uniform Subdivision), 가변분할(Adaptive Subdivision) 스플라인 곡선의 직접적인 확장이 스플라인 곡면 곡선의 제어 그래프가 서로 교차

45 스플라인 곡면 스플라인 곡선 양방향 3차 곡면(Parametric Bicubic Surface) u, w 파라미터가 필요함
우변 두 번째 행렬 M에 보간 방법과 점 p의 위치를 반영

46 공간상의 4 점이 주어졌을 경우 4점으로 채워진 곡면

47 2 개의 공간곡선이 주어졌을 경우 공간곡선(Space Curve) 3차원 곡선 괘선 면(Ruled Surface)

48 4 개의 경계곡선이 주어질 경우 4개 곡선의 영향력을 모두 감안 윗 식의 오류
수정 결과 = 쿤스 패치(Coon's Patch)

49 허미트 곡면(Hermite Surfaces)
이 곡선을 위로 올림 p1(w), p2(w)도 허미트 곡선.

50 베지에 곡면(Bezier Surface)
선형보간에 의함 1차 베지에 곡면 1차 베지에 곡면, 2차 베지에 곡면

51 베지에 곡면(Bezier Surface)
3차 베지에 곡면 4 by 4 = 16개의 제어점 J 는 베지에 곡선의 공식 양방향의 스플라인을 직접 곱하는 형식 = 직교적(直交積, Cartesian Product, Tensor Product)

52 베지에 곡면(Bezier Surface)
베지에 곡면의 연결 베지에 곡선과 마찬가지로 연결성에 유의 u, w 양 방향 모두에 대해 제어점이 일직선 위에 놓이게 제한

53 베지에 곡면(Bezier Surface)

54 B-스플라인 곡면(B-Spline Surfaces)
C2 연속성을 보장. cf. 베지에 곡면: G1 연속성 적은 수의 제어점만으로 규칙적인 입체 표면을 완벽히 표현

55 2차곡면(Quadric Surfaces)
파라미터 표현이 아님. x, y, z에 관한 2차 함수. x, y, z 사이의 직접적인 관계에 의해 표현 예: 원구 일반적인 2차곡면 대각선 행렬(Diagonal Matrix). 대각선을 중심으로 서로 대칭

56 2차곡면(Quadric Surfaces)
장점 어떤 점이 표면 위에 존재하는지 검증하기 쉽다. x, y 좌표가 주어졌을 때 z 좌표를 계산하기 쉽다. 선분과의 교차점을 계산하기 쉽다. 표면의 법선벡터를 계산하기 쉽다. 법선벡터