여러분은 이미 미분과 적분의 개념을 알고 있다

답) 130 km = 0 km + 1h x 130 km/h

Quiz

Diﬀerentiation (미분) / Integration (적분)

A Particle Motion

•

^위치^p^{에 질량}^m^{과 속도}^v를 갖는 입자(particle)가 하나 있다.

•

^{v: 1}초 뒤에는 이 방향으로 이 만큼 위치가 변화한다.

(속도: 위치의 시간에 대한 변화량)

p = p₀ v = v₀

A Particle Motion

외력

A Particle Motion

Numerics

(수치해석)

Field (장, 場)

•

^장(field)⁼함수(function) (ex) y=f(x,y,z,t)

•

속해 있는 모든 지점마다 하나의 물리량이 정의되어 있는 공간

•

중력장(gravitational field), 자기장(magnetic field), 온도장(temperature field), 속도장(velocity field),

압력장(pressure field), 밀도장(density field), …

Scalar Field vs Vector Field

온도장 (temperature field) 자기장 (magnetic force field)

Continuous vs Discrete

from Continuous to Discrete

•

Lagrangian (particles)

•

Eulerian (grid)

Eulerian vs Lagrangian

Eulerian

교통 정보 시스템

Lagrangien 교통 정보 시스템

지점에서의 속력은?

Lagrangian::getValue(x)

f (x) = f_i

ρ_i ^{W ( x} ^{− x} ⁱ

∑i ^,h)

Eulerian::getValue(x)

•

1D: linear interpolation (길이비)

r = (1− α ⁾ × p + α × q

α ₁₋ α

p r q

Eulerian::getValue(x)

•

2D: bi-linear interpolation

(면적비)

•

3D: tri-linear interpolation (부피비)

min(values of nodes) ≤ value at x ≤ max(values of nodes)

Several Grid Structures

unstructured grid structured grid

uniform grid adaptive grid

Uniform Discrete Scalar Field

@ cell center @ node

Uniform Discrete Vector Field

@ cell center @ node @ face center

Staggered Grid MAC Grid

Conventional Fluid Fields

•

@ cell center

‣ Pressure, Divergence

‣ Density, Temperature, SDF

•

@ face center

‣ Velocity

Uniform Grid Data

•

Scalar field defined @ node

•

Size: 4 bytes x 9 elements = 36 bytes

Uniform Grid Data

•

2D vector field defined @ node

•

Size: ( 4 bytes x 2 ) x 9 elements = 72 bytes

(1.0,1.0) (2.0,1.0) (1.0,2.0)

(1.0,3.0) (2.0,3.0) (1.0,1.0)

(1.0,1.0) (1.0,1.0) (1.0,1.0)

Uniform Scalar Field Size

•

¹⁰⁰³: 4 bytes × 100 × 100 × 100 = 4,000,000 bytes = 4 Mb

•

²⁵⁶³: 4 bytes × 256 × 256 × 256 = 67,108,864 bytes = 64 Mb

•

⁵¹²³: 4 bytes × 512 × 512 × 512 = 536,870,912 bytes = 512 Mb

Uniform Vector Field Size

•

¹⁰⁰³: 4 bytes × 3 × 100 × 100 × 100 = 12,000,000 bytes = 4 Mb

•

²⁵⁶³: 4 bytes × 3 × 256 × 256 × 256 = 201,326,592 bytes = 192 Mb

•

⁵¹²³: 4 bytes × 3 × 512 × 512 × 512

= 1,610,612,736 bytes = 1,536 Mb = 1.5 Gb

Computer Graphics

(컴퓨터 그래픽스)

2D Density Field Visualization

0: black, 1: white, and 0.5: gray

All Cells Together

3D Density Field Visualization

?

3D Density Field Visualization

Ray Marching Algorithm

3D Temperature Field Visualization

Using Only Velocity Field

Fluid Dynamics

(유체역학)

Density Field Advection

Lagrangian Advection

•

시간에 따라 변하지 않는 2D 속도장이 있습니다.

Lagrangian Advection

0.5

•

이 속도장을 따라 움직이는 하나의 입자를 생각해 봅시다.

•

^{이 입자는}^0.5^{의 밀도(}^density)를 가지고 있습니다.

Lagrangian Advection

0.5

•

^{이 입자는 유선(}streamline)을 따라 움직이게 됩니다.

Lagrangian Advection

0.5

•

이 입자가 움직인 결과입니다. (즉, 다음 프레임에서의 위치)

Lagrangian Advection

0.5

•

똑같이 그 다음 프레임에서의 위치도 찾을 수 있습니다.

Lagrangian Advection

0.5

n frame n+1 frame n+2 frame

•

하지만, 이 입자가 가지고 있는 밀도값은 불변입니다.

Semi-Lagrangian Advection

△x = 6.0

△t = 2.0

0.0 0.0 0.0

1.0 0.0 0.0

•

ⁿ프레임에서의 밀도장은 다음과 같습니다.

Semi-Lagrangian Advection

? ? ?

△x = 6.0

△t = 2.0

•

ⁿ⁺¹프레임에서의 밀도장을 어떻게 구할 수 있을까요?

Semi-Lagrangian Advection

△x = 6.0

△t = 2.0

0.0 0.0 0.0

1.0 0.0 0.0

•

^다시ⁿ프레임에서의 밀도장을 보겠습니다.

Semi-Lagrangian Advection

•

이 위치의 밀도(density)값은 bi-linear interpolation으로 구할 수 있습니다.

Semi-Lagrangian Advection

n frame n+1 frame

•

두 프레임의 밀도장을 비교하면 속도장에 의해 움직인 것을 확인할 수 있습니다.

More Plausible Example

Also, Velocity Advection

•

다.^속도장 또한 물리량이므로 마찬가지 방법으로 이동시킬 수 있습니

•

다.벡터장의 이동은 각 성분별로 스카라장과 동일하게 업데이트 합니

Semi-Lagrangian Advection

•

Pros: unconditionally stable

‣ Large time step size

•

Cons: numerical dissipation

‣ Smoothing effects while interpolation

‣ Wrong back-tracked position

Without Sub-Time Step

v v

dt × v

With Sub-Time Step

Comparison

without sub-step with sub-step

Time Step Size

•

^{△t ↓}

‣ Accuracy ↑, but Computations ↑

•

^{△t ↑}

‣ Accuracy ↓, but Computations ↓

CFL Condition Number

•

Courant–Friedrichs–Lewy

•

CFL > 1: unphysical

But, acceptable in computer graphics

Δt < CFL⋅ Δx

u max

Adaptive Time Step Process 0000.den 0001.den 0002.den 0003.den 0004.den 0005.den

Cache

Rendering

BFECC

•

Back and Forth Error Compensation and Correction

ˆx _n₊₁ = Advect(x _n )

ˆx _n = Advect ⁻¹( ˆx _n₊₁ ) x _n = 3x( _n − ˆx _n ) ^{/ 2}

x _n₊₁ = Advect(x _n )

Semi-Lagrangin vs BFECC

MacCormack

•

No third advection step in BFECC

•

Still 2nd order accuracy in space and time

Runge-Kutta

•

Semi-Lagrangian advection scheme

•

RK2: Runge-Kutta 2nd order advection scheme

ρ^(p,t + Δt) = ρ (^p − Δt ⋅ V(p,t),t )

ρ^(p,t + Δt) = ρ

(

^p − Δt ⋅ ˆV(p,t),t

)

= V(p − Δt

2 ⋅ V(p,t),t)

back traced position

이제 남은 문제는 ...

속도장(velocity field)을 어떻게 유체(fluid)의 움직임처럼 만들 것인가?

Calculus

(미적분학)

Three Operators for Fluid Simulation

Input Output Physical Meaning

Gradient

(구배, 勾配) Scalar Field

(Signed Distance Field)

Vector Field 

Gradient (구배, 勾配)

Divergence (발산, 發散)

Curl (회전, 回轉)

Quiz

gradient?

Quiz

? ? ?

Quiz

divergence? curl?

Fluid Dynamics

(유체역학)

질량 보존의 법칙

mass flow in = mass flow out (if and only if no source or sink)

유체의 유동 (Fluid Flow)

•

Incompressibility (비압축성, 非壓縮性)

•

Conservation of mass (질량 보존의 법칙)

•

Divergence = 0 div(vel)=0 for every cell

유체의 속도장 (Fluid Velocity Field)

•

유체의 유동(fluid flow)을 나타내는 속도장(velocity field)은 어떠한 형태로 영역(control volume)을 잡더라도

해당 표면(control surface)를 통해서

나가고(output) 들어오는(input) 양(flux)이 항상 같다.

•

만약 같지 않다면 해당 영역 안에는 source 또는 sink가 존재한다.

•

^즉,divergence-free field이어야 한다.

Divergence-Free Velocity Field

Helmholtz-Hodge Decomposition

•

^{임의의 부드러운}vector field는

모든 지점에서의 divergence=0인 vector field와

모든 지점에서의 curl=0인 vector field로 분리될 수 있다.

•

그리고 그 분해 결과는 한 가지 밖에 없다. (유일성)

divergence-free

curl-free

다음과 같이 수학적으로 증명되어 있다.

is the well-known problem. [Neumann boundary problem]

The solution to this problem exists and is unique.

∴ p₁ = p₂

Just trust.

Helmholtz-Hodge Decomposition

irrotational part

incompressible part

global constant part

Fluid Flow를 얻는 방법 a given velocity field

(원본)

모든 지점에서의 divergence=0이기 때문에 질량보존의 법칙이 성립하면서

원본과 가장 비슷한 velocity field

Helmholtz-Hodge Decomposition

Per Frame Simulation Process

External Force Step (grid)

Pressure Projection Step (grid)

Advection Step (fields & particles)

Velocity Field가 엉망이 되는 이유

•

Velocity advection

•

External force field (gravity, turbulence, wind, etc.)

Why “Pressure Projection”?

divergence-free field curl-free field

projection

the closest incompressible velocity field

One Simulation Step

messed-up velocity field

One Simulation Step

pressure projection

messed-up velocity field

divergence-free velocity field

One Simulation Step

Two Main Parts

•

Pressure projection step

‣ 주어진 velocity field를 divergence-free하게 만드는 과정

‣ 계산량이 많다. 병렬화가 어렵다.

•

Advection step

‣ 주어진 velocity field를 따라 물리량을 흘려 보내는 과정

‣ 계산량이 적다. 병렬화가 쉽다.

Pressure Projection Methods

•

Jacobi Iteration

•

Gauss-Seidel Iteration

•

Conjugate Gradient Method (CG)

•

Preconditioned Conjugate Gradient Method (PCG)

•

Multi-grid Method (MG)

What makes visually plausible?

•

Conservation of mass (질량 보존의 법칙)

•

Convervation of momentum (운동량 보존의 법칙)

•

Convervation of energy (에너지 보존의 법칙)

Navier-Stokes Equations

•

Mass conservation (continuity equation)

•

Momentum conservation (Euler equation)

∇ ⋅u = 0

∂u

∂t = − u⋅∇( ) ^u ^{+∇ ⋅} (^ν^∇u) ⁻ _ρ¹ ^{∇p + f}

advection diffusion external

force pressure

Derivation #1

a fluid parcel

∂( )ρ^u

Derivation #2

F = ma ρ^a = F_i

i=1

∑N ^{= f}^body ^{+ f}^surface

= f_normal + f_tangential

= f_pressure + f_viscosity

ρ ^Du

Dt = f_body − ∇p + ∇ ⋅ ( )µ∇u

∴ ∂u

∂t = − u⋅∇( ) û ^{+ ∇ ⋅} ( )^υ^∇u ⁻ _ρ¹ ^{∇p + f}^body ^⎛_⎝⎜^∵ ^Du_Dt ^{= ∂}_∂tû ^{+ u⋅∇}^{( )} û^⎞_⎠⎟

Just trust.

Navier-Stokes Equations

•

Mass conservation (continuity equation)

•

Momentum conservation (Euler equation)

∇ ⋅u = 0

∂u

∂t = − u⋅∇( ) ^u ^{+∇ ⋅} (^ν^∇u) ⁻ _ρ¹ ^{∇p + f}

advection diffusion external

force

문서에서 All About Volume for Houdini Artists (페이지 56-167)