Computer aided ship design Part 1. Curve & Surface

Computer aided ship design Computer aided ship design

Part 1. Curve & Surface Part 1. Curve & Surface

[2008][03-2]

Computer aided ship design Computer aided ship design

Part 1. Curve & Surface Part 1. Curve & Surface

September 2008

Prof. Kyu-Yeul Lee

Geometrical Meaning of Geometrical Meaning of the de Boor Algorithm

the de Boor Algorithm

Geometrical Meaning of the de Boor Algorithm(1) Geometrical Meaning of the de Boor Algorithm(1)

d

2

d

3

d

⁴

d

5

D

2

D

3

D

4 ³

D D

⁴

D

₅

D

4

D

5

D

6

D

2

D

₃

D

₄

D

₅

D

₆

1

d

3

1

d

4

1

d

5

d

1

d

6

( ) ( ) ( ) u

u u

u u u

u u

u

u u

_i^k

i k n i k i

i i k n i

k n k i

i

1 1 1 1

1 1

- - -

+ - -

- - -

+ - +

- + -

-

= - d d

d

u

0

u

1

u

2

u

3

u

₄

u

₅

u

₆

u

₇

u

8

u

9

u

1

= k

D

2

D

₃

D

₄

D

₅

D

₆

d

0

d

1

d

7

¡ Linear Interpolation 비율이 t:(1-t)로 일정했던 de Casteljau algorithm에 비하여 de Boor algorithm에서는 Linear Interpolation 비율이 변한다

¡ 이는 B-spline curve 를 구성하는 Bezier curve segment 의 매개변수 간격이

Geometrical Meaning of the de Boor Algorithm(2) Geometrical Meaning of the de Boor Algorithm(2)

d

2

d

3

d

⁴

d

5 2

d

4

D

2

D

3

D

4

2

d

5

D

3

D

⁴

D

₅

D

4

D

5

D

6

D

2

D

₃

D

₄

D

₅

D

₆

1

d

3

1

d

4

1

d

5

d

1

d

6

( ) ( ) ( ) u

u u

u u u

u u

u

u u

_i^k

i k n i k i

i i k n i

k n k i

i

1 1 1 1

1 1

- - -

+ - -

- - -

+ - +

- + -

-

= - d d

d

Computer Aided Ship Design 2008

Computer Aided Ship Design 2008 –– PART I: Curve & SurfacePART I: Curve & Surface

)

4

( )

( )

( )

( )

( u d 0 N 0 3 u d 1 N 1 3 u d 2 N 2 3 u d n N n 3 u

r = + + + × × × +

u

0

u

1

u

2

u

3

u

₄

u

₅

u

₆

u

₇

u

8

u

9

u

1

= k

2

= k

D

2

D

₃

D

₄

D

₅

D

₆

d

0

d

1

d

7

Geometrical Meaning of the de Boor Algorithm(3) Geometrical Meaning of the de Boor Algorithm(3)

d

2

d

3

d

⁴

d

5 2

d

4

3

d

5

D

2

D

3

D

4

2

d

5

D

3

D

⁴

D

₅

D

4

D

5

D

6

D

2

D

₃

D

₄

D

₅

D

₆

1

d

3

1

d

4

1

d

5

d

1

d

6

( ) ( ) ( ) u

u u

u u u

u u

u

u u

_i^k

i k n i k i

i i k n i

k n k i

i

1 1 1 1

1 1

- - -

+ - -

- - -

+ - +

- + -

-

= - d d

d

u

0

u

1

u

2

u

3

u

₄

u

₅

u

₆

u

₇

u

8

u

9

u

1

= k

2

= k

3

= k

D

2

D

₃

D

₄

D

₅

D

₆

d

0

d

1

d

7

Geometrical Meaning of the de Boor Algorithm(3) Geometrical Meaning of the de Boor Algorithm(3)

d

2

d

3

d

⁴

d

5 2

d

4

3

d

5

D

2

D

3

D

4

2

d

5

D

3

D

⁴

D

₅

D

4

D

5

D

6

D

2

D

₃

D

₄

D

₅

D

₆

1

d

3

1

d

4

1

d

5

d

1

d

6

( ) ( ) ( ) u

u u

u u u

u u

u

u u

_i^k

i k n i k i

i i k n i

k n k i

i

1 1 1 1

1 1

- - -

+ - -

- - -

+ - +

- + -

-

= - d d

d

Computer Aided Ship Design 2008

Computer Aided Ship Design 2008 –– PART I: Curve & SurfacePART I: Curve & Surface

)

6

( )

( )

( )

( )

( u d 0 N 0 3 u d 1 N 1 3 u d 2 N 2 3 u d n N n 3 u

r = + + + × × × +

u

0

u

1

u

2

u

3

u

₄

u

₅

u

₆

u

₇

u

8

u

9

u

1

= k

2

= k

3

= k

D

2

D

₃

D

₄

D

₅

D

₆

d

0

d

1

d

7

Relationship between Relationship between de Boor algorithm & B

de Boor algorithm & B--spline spline curves curves

¡ de Boor 알고리즘 : “Constructive Approach”

Input: d

_i

(de Boor Points)

Processor: 구간별로 d

_i

를 n 번 순차적 ‘linear interpolation’

Output : n 차 곡선상의 점

à ‘ B-spline function’(Cox-de Boor recurrence formula)

형태로 표현 됨

) ( )

( )

( )

( )

( u d 0 N 0 3 u d 1 N 1 3 u d 2 N 2 3 u d n N n 3 u

r = + + + × × × +

¡ de Boor 알고리즘 : “Constructive Approach”

Input: d

_i

(de Boor Points)

Processor: 구간별로 d

_i

를 n 번 순차적 ‘linear interpolation’

Output : n 차 곡선상의 점

à ‘ B-spline function’(Cox-de Boor recurrence formula)

형태로 표현 됨

Relationship between Relationship between de Boor algorithm & B

de Boor algorithm & B--spline spline curves curves

¡ de Boor 알고리즘 : “Constructive Approach”

Input: d i (de Boor Points)

Processor: 구간별로 d i 를 n 번 순차적 ‘ linear interpolation’

Output : n 차 곡선상의 점

à ‘ B-spline function’(Cox-de Boor recurrence formula)

형태로 표현 됨

¡ B-spline 곡선식: “B-spline function evaluation Approach”

Input: d i (de Boor Points)

Processor: 공간 상의 점 d i 와 B-spline function 을 “ blending” 하여

함수 값을 계산하면 곡선상의 점을 구할 수 있음

Output: B-spline function 과 d i 의 혼합 함수 형태로 표현

Computer Aided Ship Design 2008

Computer Aided Ship Design 2008 –– PART I: Curve & SurfacePART I: Curve & Surface

8

¡ de Boor 알고리즘 : “Constructive Approach”

Input: d i (de Boor Points)

Processor: 구간별로 d i 를 n 번 순차적 ‘ linear interpolation’

Output : n 차 곡선상의 점

à ‘ B-spline function’(Cox-de Boor recurrence formula)

형태로 표현 됨

¡ B-spline 곡선식: “B-spline function evaluation Approach”

Input: d i (de Boor Points)

Processor: 공간 상의 점 d i 와 B-spline function 을 “ blending” 하여

함수 값을 계산하면 곡선상의 점을 구할 수 있음

Output: B-spline function 과 d i 의 혼합 함수 형태로 표현

Bezier Curve and B

Bezier Curve and B--Spline Spline Curve Curve

항목 Bezier Curve B-Spline Curve

Make Curve

Given

Bezier Control Point b

_i

Parameter t

Bernstein Polynomial Func.

B-Spline Control Point d

_i

Parameter u

B-Spline Basis Func.

Find Bezier Curve r(t) B-Spline Curve r(u) Bernstein Polynomial Function B-Spline Basis Function

(Cox-de boor Recursive Formula)

).

( ...

) ( )

( )

(t b₀B₀ⁿ t b₁B₁ⁿ t b_nB_nⁿ t

r = + + + r(u)=d₀N₀³(u)+d₁N₁³(u)+d₂N₂³(u)+×××+d_D-1N_D³_-1(u)

else 0

if ï î

ï í

ì £ £

= -

÷÷ = ø ö çç è æ

÷÷ - ø ö çç è

= æ

^-

n i i

n i

n i C

n

t i t

t n B

i n

i n i

n i

)! 0 (

!

! , ) 1 ( )

(

) (t

B

_iⁿ

N

_iⁿ

(u )

-

B-Spline Basis Function

(Cox-de boor Recursive Formula)

Constructive Approach

de Casteljau Algorithm de Boor Algorithm

Inter- Given Points on Curve: p , p , … , p Points on Curve: p , p , … , p

) ( )

( )

(

¹ ₁¹

1 1

1

N u

u u

u u u

u N u

u u u

N

_iⁿ

i n i

n n i

i i n i n i

i

- + +

- + - - +

-

- + -

-

= -

î í

ì £ <

=

^-

else

if 0 ) 1

(

¹

0 i i

i

u u u u

N å

-

=

=

1 0

1 ) ( ,

D i

n i

u N

( ) ( = 1 - )

_i^k-1

+

^k_i+^-₁¹

k

i

t t b t b

b ( ) ( ) ( ) u

u u

u u u

u u

u

u u

_i^k

i k n i k i

i i k n i

k n k i

i

1 1 1 1

1 1

- - -

+ - -

- - -

+ - +

- + -

-

= - d d

d

else 0

if ï î

ï í

ì £ £

= -

÷÷ = ø ö çç è æ

÷÷ - ø ö çç è

= æ

^-

n i i

n i

n i C

n

t i t

t n B

i n

i n i

n i

)! 0 (

!

! , ) 1 ( )

(

Example of

de Boor Algorithm

Example : de Boor Algorithm

– Given problem

( )

x u

0 0

Given: , Find:

i i

i

V u x

6 5 4 3 9 2

8 0 7

7

6 5

4 3

8 2 7 0 6

6

6 5 4

3 7 2

6 0 5

5

5 4 3

6 2 5 0 4

4

4 3 5 2

4 0 3

3

3 2 3

2 4 2

3 0 2

2

2 3 2

2 0 1

1

2 1 0 0

0

3

3

2 3

3 3

3 3

3

2 3

3 3

3

3 2 3

3 3

3 2 3

3

3 2 3

) (

0 3

3 3

0 0 3

3 0 0 0 0 3

D + D + D + D + D + =

= +

D

´ + D

´ + D

´ + D

´ + D

= ´ +

= +

D + D

´ + D

´ + D

´ + D

= ´ +

= +

D + D

´ + D

´ + D

= ´ +

= +

D + D

´ + D

= ´ +

= +

D + D

= ´ D + D + D

= + +

= +

= D D +

= + +

= +

+ =

= + +

= +

u u u

u u u

u u u

u u u

u u u

u u u

u u u

u u u

x x x x x x x x

0

V

0

0

V

1

V

₂⁰

0

V

3

0

V

4

0

V

5

V

₆⁰

0

V

7

u

3

u

₄

u

₆

D

2

D

₃

D

₄

u

6 5 4 3 9 2

8 0 7

7

6 5

4 3

8 2 7 0 6

6

6 5 4

3 7 2

6 0 5

5

5 4 3

6 2 5 0 4

4

4 3 5 2

4 0 3

3

3 2 3

2 4 2

3 0 2

2

2 3 2

2 0 1

1

2 1 0 0

0

3

3

2 3

3 3

3 3

3

2 3

3 3

3

3 2 3

3 3

3 2 3

3

3 2 3

) (

0 3

3 3

0 0 3

3 0 0 0 0 3

D + D + D + D + D + =

= +

D

´ + D

´ + D

´ + D

´ + D

= ´ +

= +

D + D

´ + D

´ + D

´ + D

= ´ +

= +

D + D

´ + D

´ + D

= ´ +

= +

D + D

´ + D

= ´ +

= +

D + D

= ´ D + D + D

= + +

= +

= D D +

= + +

= +

+ =

= + +

= +

u u u

u u u

u u u

u u u

u u u

u u u

u u u

u u u

x x x x x x x x

u

0

u

1²

u

0

x

0 0

V

0

u

5

D

5

u

7

u

8

u

9

D

6

0

V

7 0

x

1

x

₂⁰

x

₃⁰

x

₄⁰

x

₅⁰

x

₆⁰

x

₇⁰

Example : de Boor Algorithm

– 1 st Knot Insertion

( )

x u

0

V

0

0

V

1

V

₂⁰

0

V

3

0

V

4

0

V

5

V

₆⁰

0

V

7

D

2

D3

D

4

D

4

D3

D5

D4

D5

D6

0 1 2 0

0

2 2 0

1 2 3

1

4 2 2 3 2 3 0

2 3

2

2 3

3 1 0

1 1

1 2

4

2 3 4

4 5

2 3 4 5

5 6

5 6 7

1 3

1 4

1 5

1 6

0 0 0

3 3 0

0 0

3 3 3

0 ( ) 2

3 3 3

3 2

3 3

3 3

3 3

3 3 2

3 3

ˆ

3 ˆ

ˆ

3

u u u

u u u

u u u

u u u

u u u u u

u

u u u

x

x

x x x

x

x

x

d

x

x

d

d

+ + + +

= = = =

+ + + + D D

= = = =

+ + + D + D + D ´ D + D

= = = =

+ + ´ D + ´ D +

= =

+ + ´ D + ´ D + D +

= =

+ + ´ D + ´ D + ´ D + D +

= =

+ + ´

= = ^{2 3 4 5 6} ₅⁰

2 3 4 5 6 0

6 7 8

6

0

7 8 9

2 3 4 5 6 7

1 7

1 8

3 3 2

3

3 3 3 3 2

3 3

3

u u u

u u u

x x

x x x

D + ´ D + ´ D + ´ D + D

= + + ´ D + ´ D + ´ D + ´ D + ´ D

= = =

+ +

= = D + D + D + D + D =

1

V

3

1

V

4 1

V

5

Computer Aided Ship Design 2008

Computer Aided Ship Design 2008 –– PART I: Curve & SurfacePART I: Curve & Surface

12

u

3

u

₄

u

₆

D

2

D

₃

D

₄

u

u

0

u

1²

u

0

x

0 0

V

0

u

5

D

5

u

7

u

8

u

9

D

6

0

V

7 0

x

1

x

₂⁰

x

₃⁰

x

₄⁰

x

₅⁰

x

₆⁰

x

₇⁰

1

= k

u ˆ

d - D

₄

d

1

x

3

x

₄¹

x

₅¹

0 1 2 0

0

2 2 0

1 2 3

1

4 2 2 3 2 3 0

2 3

2

2 3

3 1 0

1 1

1 2

4

2 3 4

4 5

2 3 4 5

5 6

5 6 7

1 3

1 4

1 5

1 6

0 0 0

3 3 0

0 0

3 3 3

0 ( ) 2

3 3 3

3 2

3 3

3 3

3 3

3 3 2

3 3

ˆ

3 ˆ

ˆ

3

u u u

u u u

u u u

u u u

u u u u u

u

u u u

x

x

x x x

x

x

x

d

x

x

d

d

+ + + +

= = = =

+ + + + D D

= = = =

+ + + D + D + D ´ D + D

= = = =

+ + ´ D + ´ D +

= =

+ + ´ D + ´ D + D +

= =

+ + ´ D + ´ D + ´ D + D +

= =

+ + ´

= = ^{2 3 4 5 6} ₅⁰

2 3 4 5 6 0

6 7 8

6

0

7 8 9

2 3 4 5 6 7

1 7

1 8

3 3 2

3

3 3 3 3 2

3 3

3

u u u

u u u

x x

x x x

D + ´ D + ´ D + ´ D + D

= + + ´ D + ´ D + ´ D + ´ D + ´ D

= = =

+ +

= = D + D + D + D + D =

Example : de Boor Algorithm

– 1 st Knot Insertion

( )

x u

0

V

0

0

V

1

V

₂⁰

0

V

3 1

V

3

D

2

D3

D

4 _{0 2 3 4}

2

0 3 4 5

1 3 3

2 3

ˆ

3 3 3

u u u

u u u

u u u

x

x x

+ + ì =

ï

ï + +

ï = í ï

+ + ï =

ï î

1 1 1 1

3 3 3 3

0 0 0 0

2

:

3 2

:

3

V V V V = x x x x

0 0

0 0

3 1

2

1 1

1 3 3

0 0 0 0 3

3 2 3 2

V

3

x x V x x V

x x x x

- -

= +

- -

0 0

5 2

2 2 1

3 3

5 5 2

ˆ ˆ

u u

V V

u u u

u u

V - u -

= +

- -

u

3

u

₄

u

6

D

2

D

₃

D

₄

u

u

0

u

1²

u

0

x

0 0

V

0

u

5

D

5

u

7

D

6 0

x

1

x

₂⁰

x

₃⁰

1

= k

u ˆ

d - D

₄

d

1

x

3

x

₄¹

0 2 3 4

2

0 3 4 5

1 3 3

2 3

ˆ

3 3 3

u u u

u u u

u u u

x

x x

+ + ì =

ï

ï + +

ï = í ï

+ + ï =

ï î

를 잇는 선분을 내분한 점은 Δ 2 : Δ 3 : Δ 4 로 내분한 선분상에 Δ 구간에 위치한다

1 1 1

1

1 1

( ) ( ) ( )

k i n k k - i k -

i i i

i n k i i n k i

u u u u

V u V u V u

u u u u

+ - -

-

+ - - + - -

- -

= +

- -

de Boor algorithm

0 0

2

,

3

V V

0 0

5 2

2 2 1

3 3

5 5 2

ˆ ˆ

u u

V V

u u u

u u

V - u -

= +

- -

( 아래의 식에서 i=3, n=3, k=1 인 경우 )

Example : de Boor Algorithm

– 2 nd Knot Insertion

( )

x u

0

V

0

0

V

1

V

₂⁰

0

V

3

0

V

4

0

V

5

V

₆⁰

0

V

7 1

V

3

1

V

4 1

V

5

D

4

D3

D4

D5

0 1 2 0

0

2 2 0

1 2 3

1

4 2 2 3 2 3 0

2 3

2

2 3

3 2 0

2 1

2 2

2 3

4

2 3

4

2 2

4

2 5 3 4

5 6

1

5

3

2 6

0 0 0

3 3 0

0 0

3 3 3

0 ( ) 2

3 3 3

3 2

3 3

3 3 2

3 3

ˆ ˆ ˆ ˆ ˆ ˆ

3 3 2

3 3

3 3

u u u u

u u u

u u u

u u u

u u u

u

u

u

u

u x

x x x x x x

d d

d x x

x

x

+ + + +

= = = =

+ + + + D D

= = = =

+ + + D + D + D ´ D + D

= = = =

+ + ´ D + ´ D +

= = =

+ + ´ D + ´ D + ´

= =

+ + ´ D + ´ D + D + ´

= =

+ + ´

= =

^{2 3 4 5}

2 3 4 5 6 0

5 6 7

5

2 3 4 5 6 0

2 7

2 8

2 9

6 7 8

6

0

7 8 9

2 5

5

6

1

3 4 7

3 2

3

3 3 3 2

3 3

3 3 3 3 2

3 3

3

u u u

u u u

u u u

d

x x x

x x

x

x

D + ´ D + ´ D + D +

= + + ´ D + ´ D + ´ D + ´ D + D

= = =

+ + ´ D + ´ D + ´ D + ´ D + ´ D

= = =

+ +

= = D + D + D + D + D =

2

V

4

2

V

5

Computer Aided Ship Design 2008

Computer Aided Ship Design 2008 –– PART I: Curve & SurfacePART I: Curve & Surface

14

u

3

u

₄

u

₆

D

2

D

₃

D

₄

u

u

0

u

1²

u

0

x

0 0

V

0

u

5

D

5

u

7

u

8

u

9

D

6

0

V

7 0

x

1

x

₂⁰

x

₃⁰

x

₄⁰

x

₅⁰

x

₆⁰

x

₇⁰

1

= k

u ˆ

d - D

₄

d

1

x

3

x

₄¹

x

₅¹

2

= k

2

x

4

x

₅²

u ˆ

0 1 2 0

0

2 2 0

1 2 3

1

4 2 2 3 2 3 0

2 3

2

2 3

3 2 0

2 1

2 2

2 3

4

2 3

4

2 2

4

2 5 3 4

5 6

1

5

3

2 6

0 0 0

3 3 0

0 0

3 3 3

0 ( ) 2

3 3 3

3 2

3 3

3 3 2

3 3

ˆ ˆ ˆ ˆ ˆ ˆ

3 3 2

3 3

3 3

u u u u

u u u

u u u

u u u

u u u

u

u

u

u

u x

x x x x x x

d d

d x x

x

x

+ + + +

= = = =

+ + + + D D

= = = =

+ + + D + D + D ´ D + D

= = = =

+ + ´ D + ´ D +

= = =

+ + ´ D + ´ D + ´

= =

+ + ´ D + ´ D + D + ´

= =

+ + ´

= =

^{2 3 4 5}

2 3 4 5 6 0

5 6 7

5

2 3 4 5 6 0

2 7

2 8

2 9

6 7 8

6

0

7 8 9

2 5

5

6

1

3 4 7

3 2

3

3 3 3 2

3 3

3 3 3 3 2

3 3

3

u u u

u u u

u u u

d

x x x

x x

x

x

D + ´ D + ´ D + D +

= + + ´ D + ´ D + ´ D + ´ D + D

= = =

+ + ´ D + ´ D + ´ D + ´ D + ´ D

= = =

+ +

= = D + D + D + D + D =

Example : de Boor Algorithm

– 2 nd Knot Insertion

( )

x u

0

V

0

0

V

1

V

₂⁰

0

V

3

0

V

4

1

V

3

1

V

4 1

V

5

D

4

D3

2 2 2 2

4 4 4 4

1 1 1 1

3

:

4 3

:

4

V V V V = x x x x

1 1

1 3 1

4

3 2 2

2 4

1 1 1 1 4

4 3 4

4

3

4

V V

V x x

x x x

x x x

-

= - +

- -

1 1

3

5 3

5 3 5 3

2

4 4

ˆ ˆ

u u

V u u

u u u V

V u

- -

= +

- -

3 4

4 5

1 3

1

2 4

4 4

ˆ ˆ

3 ˆ 3

ˆ 3 u u

u u u

u

u

u u x

x x

+ + ì =

ï

ï + +

ï = í ï

+ + ï =

ï î

2

V

4

u

3

u

₄

u

₆

D

2

D

₃

D

₄

u

u

0

u

1²

u

0

x

0 0

V

0

u

5

D

5

u

7

u

8

u

9

D

6 0

x

1

x

₂⁰

x

₃⁰

1

= k

u ˆ

d - D

₄

d

1

x

3

x

₄¹

2

x

4

u ˆ

1 1

3

5 3

5 3 5 3

2

4 4

ˆ ˆ

u u

V u u

u u u V

V u

- -

= +

- -

( 아래의 식에서 i=4, n=3, k=2 인 경우 )

3 4

4 5

1 3

1

2 4

4 4

ˆ ˆ

3 ˆ 3

ˆ 3 u u

u u u

u

u

u u x

x x

+ + ì =

ï

ï + +

ï = í ï

+ + ï =

ï î

를 잇는 선분을 내분한 점은 Δ 2 : Δ 3 : Δ 로 내분한

1 1 1

1

1 1

( ) ( ) ( )

k i n k k - i k -

i i i

i n k i i n k i

u u u u

V u V u V u

u u u u

+ - -

-

+ - - + - -

- -

= +

- -

de Boor algorithm

1 1

3

,

4

V V

Example : de Boor Algorithm

– 2 nd Knot Insertion

( )

x u

0

V

0

0

V

1

V

₂⁰

0

V

3

0

V

4

0

V

5

V

₆⁰

0

V

7 1

V

3

1

V

4 1

V

5 2

V

4

2

V

5 3

V

5

0 1 2 0

0

2 2 0

1 2 3

1

4 2 2 3 2 3 0

2 3

2

2 3

3 3 0

3 1

3 2

3 3

4

2 3

4

2 3

1 3

5

2 4 3

4

3 5

3 6

0 0 0

3 3 0

0 0

3 3 3

0 ( ) 2

3 3 3

ˆ 3 2

3 3

ˆ ˆ 3 3 2

3 3

ˆ ˆ ˆ 3 3 3

3 3

ˆ ˆ 3

3

u u u

u u u

u u u

u u u

u u u u u u u u u x

x x

x x x

x

x d

d x

x x x

d

+ + + +

= = = =

+ + + + D D

= = = =

+ + + D + D + D ´ D + D

= = = =

+ + ´ D + ´ D +

= = =

+ + ´ D + ´ D + ´

= = =

+ + ´ D + ´ D + ´

= =

+ +

= =

^{2 3 4}

2 3 4 5

5 6

2 3 4 5 6 0

5 6 7

5

2 3 4 5

3 7

3 8

3 9

6 0

6 7 8

6

7 8 9 0

2 3

2

4

1 5

3

10 6 7

5

5

3 2

3

ˆ 3 3 2

3 3

3 3 3 2

3 3

3 3 3 3 2

3 3

3 u u u

u u u

u u u

u u u

x x

x x x

d d

x x

x x

´ D + ´ D + D + ´

= + + ´ D + ´ D + ´ D + D +

= = =

+ + ´ D + ´ D + ´ D + ´ D + D

= = =

+ + ´ D + ´ D + ´ D + ´ D + ´ D

= = =

+ +

= = D + D + D + D + D =

Computer Aided Ship Design 2008

Computer Aided Ship Design 2008 –– PART I: Curve & SurfacePART I: Curve & Surface

16

u

3

u

₄

u

₆

D

2

D

₃

D

₄

u

u

0

u

1²

u

0

x

0 0

V

0

u

5

D

5

u

7

u

8

u

9

D

6

0

V

7 0

x

1

x

₂⁰

x

₃⁰

x

₄⁰

x

₅⁰

x

₆⁰

x

₇⁰

1

= k

u ˆ

d - D

₄

d

1

x

3

x

₄¹

x

₅¹

2

= k

2

x

4

x

₅²

u ˆ

3

x

5

u ˆ

3

= k

0 1 2 0

0

2 2 0

1 2 3

1

4 2 2 3 2 3 0

2 3

2

2 3

3 3 0

3 1

3 2

3 3

4

2 3

4

2 3

1 3

5

2 4 3

4

3 5

3 6

0 0 0

3 3 0

0 0

3 3 3

0 ( ) 2

3 3 3

ˆ 3 2

3 3

ˆ ˆ 3 3 2

3 3

ˆ ˆ ˆ 3 3 3

3 3

ˆ ˆ 3

3

u u u

u u u

u u u

u u u

u u u u u u u u u x

x x

x x x

x

x d

d x

x x x

d

+ + + +

= = = =

+ + + + D D

= = = =

+ + + D + D + D ´ D + D

= = = =

+ + ´ D + ´ D +

= = =

+ + ´ D + ´ D + ´

= = =

+ + ´ D + ´ D + ´

= =

+ +

= =

^{2 3 4}

2 3 4 5

5 6

2 3 4 5 6 0

5 6 7

5

2 3 4 5

3 7

3 8

3 9

6 0

6 7 8

6

7 8 9 0

2 3

2

4

1 5

3

10 6 7

5

5

3 2

3

ˆ 3 3 2

3 3

3 3 3 2

3 3

3 3 3 3 2

3 3

3 u u u

u u u

u u u

u u u

x x

x x x

d d

x x

x x

´ D + ´ D + D + ´

= + + ´ D + ´ D + ´ D + D +

= = =

+ + ´ D + ´ D + ´ D + ´ D + D

= = =

+ + ´ D + ´ D + ´ D + ´ D + ´ D

= = =

+ +

= = D + D + D + D + D =

Example:

Example:

n

n--th th B B--Spline Spline function function 으로부터 으로부터 n

n--th th Bezier function Bezier function 찾기 찾기

) (u y

0

V

0

0

V

1

0

V

2

0

V

3

0

V

4 1

V

2

1

V

3

0

3

D

₀

3

D

₀

3

D

₁

3

D

₁

3

D

₁

3 D

n

n--th th B B--Spline Spline function function 으로부터 으로부터 n n--th th Bezier function Bezier function 찾기 찾기

-- 원래 원래 knot knot 위치에 위치에 n n 번 번 knot knot 중첩 중첩

D

0

D

1

D

1

D

0

Computer Aided Ship Design 2008

Computer Aided Ship Design 2008 –– PART I: Curve & SurfacePART I: Curve & Surface

18

u

0

x

0

x

₁⁰

x

₂⁰

x

₃⁰

x

₄⁰

u₀ u₁ u₂

u₃ u₄

u₅ u₆

1

x

2

x

₃¹

u₄

u₅ u₆ u₇

D

1

D

0 0

3

D

₀

3

D

₀

3

D

₁

3

D

₁

3

D

₁

3 D

0 1 2 0

2 0

1

0

3

u u u

x = + + = u = x

1 2 3 3 2

2 1

1 1

0 0 2

3 3

3

u u u u u

u u

x

x

+ + -

= = +

= + D =

2 3 2 3

3 2 0

3 2

3

1 4

2

3 3

3 3

u u u u

u u

u u u

x = + + = + =

- D

= - = -

3 5 5

3

1 0

1 4 4

3

3 3

3

u u u u u

x = + + = u + -

= D + D

1 4 4

4

4

5 6 5

5

0

5 1

5 5 3

3 3

3 3

u u u u

u u u

u

u u

x

x = + + = - -

- D

= - = - =

5 6 7 0

5 4

1

5

3

u u u

x = + + = u = x

) (u y

0

V

0

0

V

1

0

V

2

0

V

3

0

V

4 1

V

2

1

V

3

0

3

D

₀

3

D

₀

3

D

₁

3

D

₁

3

D

₁

3 D

n

n--th th B B--Spline Spline function function 으로부터 으로부터 n n--th th Bezier function Bezier function 찾기 찾기

-- 원래 원래 knot knot 위치에 위치에 n n 번 번 knot knot 중첩 중첩

2

V

3

D

0

D

1

D

1

D

0

D

0

D

1

u

0

x

0

x

₁⁰

x

₂⁰

x

₃⁰

x

₄⁰

u₀ u₁ u₂

u₃ u₄

u₅ u₆

1

x

2

x

₃¹

u₄

u₅ u₆ u₇

D

1

D

0 0

3

D

₀

3

D

₀

3

D

₁

3

D

₁

3

D

₁

3 D

u₅

u₆ u₇ u₈

2

x

3

0 1 2 0

2 0

2

0

3

u u u

x = + + = u = x

1 2 3 3 2

2 2

1

3 3

u u u u u

x = + + = u + - D

2 3 2 3

3 2

2

3

1 2 2

4

0 3

2

3 3

3 3

u u u u

u u u

u

u x

x = + + = +

- D

= - = - =

u + u + u

2 4 5

4

5 4

6

1 0

1 3 6

3 3

3

u u u u u u

x

x

+ + -

= = +

= D + D =

6 7 6

6

5 5

5

2

u u u u

u u

x = + + = - -

6 7 8

0 4 2

6

3

u u u

x x

+ +

=

=

) (u y

0

V

0

n

n--th th B B--Spline Spline function function 으로부터 으로부터 n n--th th Bezier function Bezier function 찾기 찾기

-- 원래 원래 knot knot 위치에 위치에 n n 번 번 knot knot 중첩 중첩

0

V

1

0

V

2

0

V

3

0

V

4 1

V

2

1

V

3

0

3

D

₀

3

D

₀

3

D

₁

3

D

₁

3

D

₁

3 D

2

V

3

D

0

D

1

D

1

D

0

D

0

D

1

0

V

0

0

V

1

1

V

2 ₂

V V

3₃²

1

V

3

0

V

3

0

V

4

Computer Aided Ship Design 2008

Computer Aided Ship Design 2008 –– PART I: Curve & SurfacePART I: Curve & Surface

20

u

0

x

0

x

₁⁰

x

₂⁰

x

₃⁰

x

₄⁰

u₀ u₁ u₂

u₃ u₄

u₅ u₆

1

x

2

x

₃¹

u₄

u₅ u₆ u₇

D

1

D

0 0

3

D

₀

3

D

₀

3

D

₁

3

D

₁

3

D

₁

3 D

u₅

u₆ u₇ u₈

2

x

3

1개의 B-Spline Function 1개의 B-Spline Function

2 개의 Bezier Function 으로 나누어짐

2 개의 Bezier Function 으로 나누어짐

u

₃

위치에 knot 를 차수(=3)만큼 중첩

분홍색 function: 를 y-control ordinate로 하는 Bezier Function

분홍색 function: 를 y-control ordinate로 하는 Bezier Function

0 0 1 2

0

,

1

,

2

,

3

V V V V

녹색 function: 를 y-control ordinate로 하는 Bezier Function

녹색 function: 를 y-control ordinate로 하는 Bezier Function

2 1 0 0

3

,

3

,

3

,

4

V V V V

Example

Example

Example: Knot Insertion of Bezier Curve Example: Knot Insertion of Bezier Curve

-- Knot Insertion #1 Knot Insertion #1

u

0 1

1 2

knot Insertion 1 knot Insertion 1

÷÷ø ö ççè æ 2 1

÷ ÷ ø ö ç ç è æ 3

÷÷ 4 ø ö çç è æ 4 2

÷÷ ø ö çç è æ 1

5

1 2 3 4 5

) (u y

0

b

0

0

b

1

0

b

2

0

b

3 1

b

2 1

b

1

1

b

3 1

0

1