Curve
2D Primitives
- Points, Lines, Triangles, ...
- Circlee, Boxes, Curves, ...
- Curve는 어떻게 표현해야할까? poly line으로? function으로?
Curve를 표현하는 방법
이랬으면 좋겠다!
- Drawing 이 쉬워야해: 그리기 쉽게 컨트롤포인터로 간단하게!
- Editing 이 쉬워야해: 점을 움직이면 원하는 모양으로 수정할 수 있게!
- Fitting 이 쉬워야해: 내가 이상하게 그려도 point를 잡아 올바르게 수정하게!
1. 함수의 표현(Curve Function)
장점: 그리기 쉽다.
단점: Editing, Fitting이 어렵다. 차수가 높아지면 region나누기 어렵다.
- 원의 방정식, 타원의방정식, 2차 방정식 등을 이용한 그리기
Circle
- Implicit: (x-xc)제곱 + (y-yc)제곱 = r제곱
- Implicit 표현식의 장점: 점 내부? 외부? 쉽게 알 수 있음/ 단점: x의 변화에 따른 y 알기 어려움
- Explicit: y = ~~~ 으로 표현이 되는 식
- 그럼 Explicit 표현을 이용하여 그리면 될까?
No. 이걸로 그리면 x 증가에 따른 y증가 각각 달라서 그림에 빈칸이 생겨버림 - 일정한 각도의 증가로 일정하게 나타내자 => poly coordinate로 그리자
- 원은 하나의 점을 그릴 때 8개의 점을 그릴 수 있음 (x, y/ -x, y/ x, -y/ -x, -y/ x, y반대로 4개) Symmetry를 이용하는 것
- 지역을 나눠서 8번씩 그리면 된다. x가 0인 점부터 기울기가 -1이 되는 지점까지 그린다.
- 그릴 때는 Midpoint Algorithm을 이용한다.
Midpoint Algorithm
- 예를들어, x가 1 증가할 때 y를 0.5증가시켜, 원 안에 있으면 증가시키지 않고, 밖에 있으면 증가시킨다.
- 원 안에있는지 밖에있는지에 대한 검사는 Implicit표현식을 이용하면 된다.
- 이제 끝일까? 아니다. 안에있는지 밖에있는지를 계산하는 Implicit표현(함수)속에는 제곱계산이 남아있다.
- 관계식을 구함으로 더 간단한 계산으로 처리할 수 있다.(Pk+1 = Pk + ?) 를 계산해보면 간단한(?) 식이 나온다.
- 정리하자면
- Explicit 표현법으로 정의한다.
- Symmetry를 고민해본다.
- Region을 나눈다.
- Implicit을 통해 계산한 Pk를 이용하여 midpoint Algorithm을 수행한다.
- 관계식에 따라 Pk를 갱신한다.
- 구해진 점에 대해 Symmetry가 가능한 곳에 plot
Ellipse
- 원과 다른점은 초점이 두개 있는 것. 식은 타원의방정식
- 원활한 계산을 위해, 중앙으로 위치시킨 후에 이동해야한다.
- Explicit 표현법으로 정의
- Symmetry는 4개의 점에 대해 같이 그릴 수 있다.
- Region은 x가 0인 지점부터 기울기가 -1인 지점까지 Region 1, 그곳부터 y가 0인 지점까지 Region 2로 나눌 수 있다.
- Implicit을 통해 Pk를 계산할 f를 준비하고, 내부에 있을경우, 외부에 있을 경우에 따른 조건식을 구현하여 Midpoint Algorithm을 구현한다.
Region1의 경우, x가 1 증가할때 y를 0.5 감소시켜본다. Region2의 경우, y가 1 감소할 때 x를 0.5 증가시켜본다. - 관계식에 따라 Pk를 갱신한다.(Pk+1 - Pk계산해서 구하기)
- Symmetry가 가능한 곳에 plot() // (x, y),(-x, y),(x, -y),(-x, -y)
2차원 곡선
- y = ax제곱 +b 와 같은 2차원 곡선일 경우도 위 순서대로 생각하면 금방 알고리즘을 구현할 수 있다.
- 3의 Region정의와, 4의 알고리즘 구현을 한번씩만 잘 생각해보면 된다.
2. Spline Curve
- 함수의 표현은 그리긴 쉬우나... Fitting과 Editing이 매우 약함
- 또 차수가 높아질 수록 mid point 알고리즘을 위한 region을 나누기가 까다로워짐
표현법 정리
- Explicit : y = f(x);
- Implicit : f(x, y) = 0;
- Parametric : x = f(u), y = g(u); // u에 의한 결정
=> x, y를 각각 계산 할 수 있다는 것이 편리. => control 이 편해짐 이걸 이용하자!!
x(u) = ak*uk를 k가 0에서 n까지 더하기 => 0~1사이인 u에서의 특정 지점의 값을 지정할 수 있다 => way point임
Curve Specification
- Interpolation: 보간. way point 지남
- Approximation: 근사. way point에 근사한 값으로
- Weight: 특정 way point에 weight를 줌으로, 다양한 모양을 나타낼 수 있음.
Cubic Spline(n == 3)
- x(u), y(u), z(u)각각 3차식, ax, bx, cx, dx 4개의 unknown 포함 => 4개의 식 필요
- 4개의 식을 위한 2개의 점, 2개의 기울기를 정의하면 곡선의 방정식을 구할 수 있음
- 시작점, 시작기울기, 끝점, 끝기울기를 주면됨. => u벡터 행렬 제어점(시작, 끝, 시작기울기, 끝기울기)계산을 하면 됨
- 여기서 u벡터 행렬을 Basis function이라고 함. => Basis function 제어점을 하면 곡선그리기 가능
- u를 촘촘하게 할수록 예쁜곡선이 나옴.
Hermite Spline
장점: 컨트롤이 쉽다.
단점: 복잡한 모양의 표현이 어렵다. Continuity issue가 발생한다. C2만족 어려움
-
Spline의 대표. N+1개의 control points, N개의 segment
-
Basis function의 각 점의 합은 1. 시작점과 끝점의 구간은 하나의 function만 1을 가지고 나머지는 0 => 이러한 특성때문에 시작점과 끝점을 지난다. 시작점을 정의하는 B0가 시작할 때 1이고 끝점을 정의하는 B2가 끝날 때 1이다.
-
기울기를 특정하는 방법: 기울기를 정의하는 것은 두 점이기 때문에 점으로 정의한다.
Continuity
- Hermite Spline을 그리다보면, 연결이 부드럽지 않은 부분이 쉽게 보인다. 점의 연결은 되어있지만, 기울기의 연결이 되어있지 않기 때문. 연결성을 정의해보자면,
- C0 continuity: 연결하는 곡선의 끝, 시작 위치가 같음
- C1 continuity: 끝, 시작 위치가 같고 기울기가 같음
- C2 continuity: 끝, 시작 위치가 기울기도 같으며 가속도도 같음
C2는 예쁘게 그려지지 않는다는 문제를 해결하기위해 Geometric Continuity가 있다.
- G0 continuity: C0와 같음
- G1 continuity: C1와 근본은 같으나 기울기 방향이 같아도 크기가 다를 수 있음
- G2 continuity: C2와 근본은 같으나 가속도 방향이 같아도 크기가 다를 수 있음
- Hermite은 C0, C1은 만족시키기 어렵지 않지만 C2는 어렵다!
3. Bezier Curve
장점: 여러개의 제어점을 줄 수 있음. C1 쉽게 만족, C2까지 가능, 쉬운 제어
단점: point가 많아지면 차수가 너무 커져서 제어가 어려움. point하나만 건들여도 모양이 다 바뀜. 부분제어가 어려움
- Hermite Spline의 단점을 보완하기 위해 만들어진 커브
- 이또한 계수의 합이 1인 Basis function과 control point의 곱으로 결과를 얻는다.
- Hermite과 제어점의 의미가 다르게 해석됨. Hermite는 지날 점이고 Bezier는 근사할 점
- C2를 만족하려면 2차미분을 한 값이 상수이면 안되므로(연속해야하므로) n이 2 이상이어야 함
Cubic Bezier Curves(n == 3)
- Bk,n(u) = C(n, k)uk제곱(1-u)n-k제곱
- p(u) = B0,3(u) P0 + B1,3(u) P1 + B2,3(u) P2 + B3,3(u) P3
- n이 3이기 때문에 B가 4개의 식으로 나눠진다. 여기서도 마찬가지로 시작점은 하나의 식에서만 1을 가진다. 그러므로 시작과 끝점을 지난다.
- 쉽게 말하자면, 각 Basis 곡선에서 위로 튀어나온부분이 그 식의 영향이 큰 영역이다.
- 계수의 합이 1이라는 특성으로 Control point의 Convex Hull 내부에 점이 생성된다.
- 이제 그리자~
- 촘촘하게 생성된 u에 대해 점을 추가하고 이어주면 된다. Tessellation Shader의 몫
특징있는 Bezier Curve그리기
- Closed curve: 시작과 끝의 점(p0 == p5)을 같게 해주면 된다. 단, C2 를 만족시키기 위해 P1과 P4를 대칭의 위치에 둔다.
- Weighted curve: 특정점에 가깝게 위치시키기.
- Connected curve: 매우 까다로운 조건 만족필요. 지나는 점 앞 뒤 같은 거리, 대칭에 위치, 그 다음 점들의 거리는 같아야함. => 6개의 점에서 5개의 점의 위치가 지정되어버림 => 수정이 어려움
De Castaljau's algorithm
- 점을 2개씩 보간하고 보간된걸 또 2개씩 보간하고...반복해서 하나의 점으로 만들기.
- 보간하는 지점은 비율로 진행됨. 0.3이면 0.3이 되는 부분을 기점으로 보간.
- 장점: 직접 계산할 필요없이 알고리즘만 구현하면 된다.
4. B-Spline Curve
장점: local control이 가능, C2만족, 적정한 차수
- 아이디어: Basis function의 범위를 늘려보자~ => 부드럽게 연결되는 함수 제작
Knot
- Knot이라는 개념은 knot vector로 정의하며, 시작~끝까지를 나눈 값으로, 간격이 중요한 의미를 가진다.
- Basis function이 각각의 knot마다 존재한다.
- knot의 간격이 좁다는 것은 해당 control point로 가까워진다는 의미다.
- 또한 knot값의 중복으로 control point를 지나게 할 수 있다. d가 4인경우, 3개가 같으면 해당점을 지난다.
- k번 같은값을 반복하면 Cd-k-1 continuity를 만족한다.
Cubic B-Spline(d == 4)
- d가 4라면 3차까지 존재, 최소 4개의 Knot값
- Uniform B-Spline의 경우, 행렬식의 곱으로 계산이 가능하다.
- Non-uniform B-Spline의 경우, Basis function을 계산해야한다.(점화식을 이용해서)
- 최종적으로 Non-Uniform B-Spline의 Basis function은 [u3, u4]에서 정의가 된다. 받은 u값을 이 사이값으로 변경하고, 점화식의 계산으로 Basis function을 만든다. 식 그대로 구현하면 된다.
- 단, knot-vector의 크기는 결국 8개가 된다. 왜냐하면, Cubic B-Spline에서 k는 3인데, d의 최대값은 4이므로 k+d <= 8인 관계로 인덱스 7까지 만들어져야 한다.
- 만들어진 Basis function을 각 p에 곱해주면 점을 정의할 수 있다.
De Boor's algorithm
- de Castelijau's algorithm과 비슷.
- knot를 반복하여 control point의 개수를 줄인다.
- 비례식을 통해 새 점을 만든다.
Interpolation
- 점을 지나게 하려면? sudo 행렬 구해서 곱해야함.
Rational B-Spline
- Weight를 갖게 할 수 있음. P(u)를 구하는 과정에서 P0 B0,d w0 하면 그 점에 weight를 준 것.
- NURBS : Non-Uniform Rational B-Spline
- P0, P1, P2 세 점으로 B-Spline을 만들 때, w0 = w2 = 1 이고, w1은 r / 1-r 이라면, w1이 클수록 p1에 가까워짐
Curved Surface
- P(u)만 지정하던 곡선에서 벗어나 P(u, v)를 만들 수 있음
- Pjk * Bjm(v) Bkn(u)를 k(0~n), j(0~m)에 대해 수행하면 됨.
Cubic Bezier Patch
- 이웃한 patch를 붙이기.
- 두개의 면의 가장자리를 공유하고(C0), 그 다음 점들의 위치가 대칭이 되어야 C1 만족 가능
- continuity는 4개씩 진행하면 C2맞추기 어렵지 않음 => B-Spline.
Subdivision Methods
- Catmull78: 4개의 점을 5개로. 표면의 수직벡터의 반대방향으로 내린다.
- Doo78: face가 점으로, edge로 바뀜
- Tessellation Shader이용하면 만들기 쉬워짐. 근데 형상의 제어가 어려움
형상의 제어
문제
- 툭 튀어난 부분은 Subdivision해도 사라지지 않는 경우 존재
- 이 부분은 subdivision하고싶지않다. 그럴 수 있음.
- 줄여나가다보면 크기가 너무 작아짐
정리하자면,
- 비슷한 모양, 크기로 부드럽게 만들고 싶음
- 어디는 뾰족하고 어디는 부드럽게 하고싶음
Boundary Modeling
- Boundary curve: 여기는 보정할것이다. 표시
- Interpolated surface: 작아진 만큼 크기를 키운다.
=> 문제: 너무 많은 patch가 필요. => Modified subdivision method => 날카로운 edge 살아남음
공부를 위한 벨로그