Tumws 20VDA-Formulas - Formulas PDF

Preview

Summary

Visual Data Analytics - FormulasAdrian CastroFebruary 20211 General KnowledgeVisualization Pipeline: Data Acquisition Filtering/Enhancement (obtain useful data/cleaning) Visualization/Mapping (how to repre- sent data) Rendering (generate 2D images/video) Indipendent Variables: 2D/3D space, time Depe...

Description

Visual Data Analytics - Formulas Adrian Castro February 2021

1

General Knowledge

Visualization Pipeline: • Data Acquisition • Filtering/Enhancement (obtain useful data/cleaning) • Visualization/Mapping (how to represent data) • Rendering (generate 2D images/video) Indipendent Variables: 2D/3D space, time Dependent Variables: temperature, velocity Characteristics of data values: • Attribute types • Domain • Value range • Dimension • Error & Uncertainty • Physical Interpretration Qualitative data: categorical, nonmeasurable, discrete Nominal data: no natural ordering, membership Ordinal data: natural ordering Categorical data: values from fixed number or categories Scalar data: if we can map from higher dimensional data to a lower dimensional data (f (x) : Rn → R) Tensor data: multi-dimensional data

b

f (pj ) =

N X

wi · ϕ(kpi − pj k) = fj

i=1

c

Yields a system of linear equations to be solved for wi :  ϕ(kp1 − p1 k) · · · ϕ(kpN − p1 k)   .. .. ... A=   . . ϕ(kp1 − pN k) · · · ϕ(kpN − pN k)     f1 w1     W =  ...  F =  ...  fN wN 

W = A−1 · F

Drawbacks: global influence of every sample, adding a new point requires solving the equation system, computationally expensive Inverse Distance Weighting Assumption: Nearby points are more similar than those further away. f (x) =

N X

2.1

Radial Basis Functions

Each point (pi , fi ) influences f (x) based on distance: r = kpi − xk f (x) =

N X

fi · ϕ(kpi − xk)

i=1

ϕ(r) = e−r

2

Weighted radial basis functions f (pj ) interpolates the value fj

2.3

Interpolation Inside a Triangle p0 f 0

fi ϕ(kpi − xk)

p1 f 1

p2 f 2 1

di = kpi − xk

Interpolation

ISOContours: all points lying on the same line with the same values Goal of interpolation: construct continuous function f which approximates given values

Every Voronoi Sample (a, b, c) is a vertex of a Delaunay triangulation

i=1

N X i=1

ϕ(r) = PNr

2

1 i=1 d2 i

Adjusted formula:

2

a

N X 1 fi / kpi − xk2 i=1 kpi − xk2

Drawbacks: still costly, still global influence of every sample

2.2

Find a function f that interpolates fi at the point pi such that:

f (pi ) = fi Linear function:

Triangulation

Giving up smooth, precise reconstruction in favor of speed Generating a Triangulation Goals: avoid long and thin triangles, maximize minimum angle in the trianradius of circle gulation, maximize radius of circumcircle Delaunay Triangulation 1. Circumcircle does not contain another point of the set 2. Maximizes minimum angle of triangulation 3. Triangulation is unique for all but trivial cases Voronoi Diagram 1

i = 0, · · · , N

f (x) = a + bx + cy

Where a, b, c can be obtained with:



1 X = 1 1

x0 x1 x2

     y0 f0 a y1 A = b  F = f1  c y2 f2

A = X −1 · F

2.4

Baricentric Interpolation

The gradient in a scalar field f (x):

We want to have a smooth, continuous interpolation ∀α ∈ [0, 1]

p1

x α

1−α

f (α, β) = Aα + Bβ + Cαβ + D

 δfδx (x)  ∇f (x) =  δy 

A = fi+1,j − fij

δf (x) δz

f (α) = α · p0 + (1 − α) · p0 p0

Transform to hyperbola form:

 δf (x) 

B = fi,j+1 − fij C = fij − fi,j+1 − fi+1,j + fi+1,j +1

In the case of a tetrahedron with function the gradient is always constant:

D = fij

f (x) = a + bx + cy + dz α0 = A0 /A, α1 = A1 /A, α2 = A2 /A Where A = area of the triangle x = α0 p 0 + α1 p 1 + α2 p 2 α0 + α1 + α2 = 1

 b δx  δf (x)    ∇f (x) =  δy  = c δf (x) d

Piece-Wise Linear Interpolation

For data points (x0 , y0 ), · · · , (xN , yN ) Evaluate

A = P −1 · X

2.5

γ=C

2.7

Marching Squares

Algorithm used to compute isolines on a 2D surface, given a grid of values. Step 1: mark all the data with:

f (x) = (1 − α)yi + αyi

value >= isovalue: +

x − x1 xi+1 − xi Bilinear Interpolation

value < isovalue: −

f (x) = α0 f0 + α1 f1 + (1 − α0 − α1) · f2 Given a point Q we can find α by solving the linear system:   p0x p1x p2x P = p0y p1y p2y 1 1 1     α0 Qx A = α1  X = Qy  α2 1

β0 = −A/C

δz

2.6

If αi are known, then f (x) can be interpolated from values fi at the vertices via:

(fij · fi+1,j+1 − fi+1,j · fi,j+1 ) C α0 = −B/C δ=

 δf (x) 

where: α =

Step 2: 16 different combinations, but we are interested in 4 base cases: +

+

+

+

fi+1,j+1 · αβ fi,j+1

+

f (x) = a + bx + cy + dz

f α·β

(1 − α) · β fi+1,j

α

fcenter =

A = X −1 · F

Computing Gradient of Scalar Field

f (α, β ) = γ(α − α0 )(β − β0 ) + δ

f (α, β ) = γ(α − α0 )(β − β0 ) + δ

+

where δ is the value at point (α0 , β0 ) fi,j+1

fi+1,j +1

3 (α0 , β0 )

fij

β0

fi+1,j

α0

2

1 (fij + fi+1,j + fi,j+1 + fi+1,j +1 ) 4

• if midpoint decider is right in the middle, hence the ambiguity is still there, we can use the asymptotic decider previously defined as:

Asymptotic Decider Hyperbola form: p 2 f2

−

In the last case, we have ambiguity, which can be resolved in two ways: • midpoint decider: β

p 0 f0

fij

+

−

+

Formula of tetrahedron:

Can get values a, b, c, d by solving linear system:   1 x0 y0 z0 1 x1 y1 z1  X= 1 x2 y2 z2 1 x3 y3 z3     f0 a f1  b     A=  c  F = f2  f3 d

+

fi+1,j +1

α · (1 − β) (1 − α) · (1 − β )

p 3 f3

−

fi+i,j · α(1 − β)+ fi,j+1 · (1 − α)β+

Scalar Interpolation

p 1 f1

+

f (α, β) =fij · (1 − α)(1 − β)+

−

−

+

f

f

− + (decider < c)

+ − (decider >= c)

Phong Illumination Model

Components: • Ambient Light: background light, constant everywhere • Diffuse Reflector: reflects equally into all directions • Specular Reflector: reflects mostly into the mirror direction

3.1

Lighting

4

C = Ka Ca Od Ka : ambient reflection coefficient ∈ [0, 1] Ca : color of the ambient light Oa : object color

3.2

Diffuse Reflection ~n ~ l

θ

Volume Visualization

• Indirect Volume Rendering (Marching Cubes, data is reduced to intermediate representation, which can then be rendered) • Direct Volume Rendering (Ray Casting, data is considered semi-transparent with physical properties, and directly rendered) • Voxel: point sample in 3D • Transfer Function: maps data values to color & opacity

4.5

Direct Volume Rendering: Phong Shading

We have to evaluate Phong’s illumination model based on: • position of current sample and light source • sample’s color emission assigned by transfer function • sample’s normal/gradient (central difference)

4.6

Gradient Estimation

We can estimate the gradient using finite differencing. However, this technique is not feasible with large amounts of data. C = Kd Cp Od · cos θ cos θ =

4.1

~n · ~l ~ |~n| · |l|

Kd : diffuse reflection coefficient ∈ [0, 1] Cp : color of point of light

Associates distinct materials (value range) to distinct properties (color and opacity). Maps a different color to each scalar value. T : scalar value → color + α

Od : object color cos θ : angle between light vector ~ l and ~n

Reminder: |~v | =

3.3

p

(v0 )2 + · · · + (vn )2

4.2

C = Ks Cp Od · cosn ϕ

~r = 2 · (

~r · ~v |~r| · |~v |

~l ~n ~n · ~l )· − ~ ~ |~n| · |l| |~n| | l|

Ks : specular reflection coefficient ∈ [0, 1] Cp : color of point of light Od : object color

(· · · )n : shininess factor (extent of highlight)

Light Emission and Attenuation

Volume rendering integral: Z s Rs α(t) dt ds′ C(s) = C(s′ ) · e− s′ s0

We are calculating the accumulated color until C(s′ ), with the absorption coefficient between the last color s′ and the point of view s.

4.4

cosn ϕ : angle between reflected light ray ~r and the vector to the viewer ~v

Direct Volume Rendering

Each voxel emits light of the color assigned to it, and absorbs light according to its opacity.

4.3

Specular Reflection

cos ϕ =

Transfer Function

Ray Casting - Compositing

~l

θi

Cin = (0, 0, 0), αin = 0 αout = αin + (1 − αin ) · α

θr

4.7

Compositing Schemes

• Surface Rendering/First-Hit: stop ray traversal if an ISOSurface is hit • Average: simply accumulate colors, but ignore opacity • Maximum: take maximum color along axis and display it

5

Flow Visualization

• Motion of fluids (gases, liquids) • Geometric boundaries • Conservation of mass, energy and momentum • Velocity/Flow field v(x, t)

Front-to-back Strategy

Cout = Cin + (1 − αin ) · α · C ~n

∇f (x, y, z) ≈   1 f (x + h, y, z ) − f (x − h, y, z ) f (x, y + h, z) − f (x, y − h, z) ≈ 2h f (x, y, z + h) − f (x, y, z − h)

5.1

Vector Field Visualization

• Vector data representing Direction and Magnitude • Steady (time-indipendent) flow:

~r ϕ

~v

Cout , αout v(x) : Rn → Rn C, α • Unsteady (time dependent) flow:

Perfect Mirror: shininess factor n has to be very large, going to infinity.

Cin , αin v(x, t) : Rn × R1 → Rn 3

5.2

Vector and Scalar Functions

5.5

Midpoint Method

Im(λ1 , λ2 ) 6= 0 and Re(λ1 , λ2 ) = 0 Circulating Sink

nd

• Also known as Runge-Kutta 2 order method • Better, faster than Euler method

Scalar function: ρ(x, t)

∆x = ∆t · v(x, t) ∆x vmid = v(x + ) 2 x(t + ∆t) = x(t) + ∆t · vmid

 δρ(x,t)  5.6

Jacobian matrix applied to vector field v(x, t):

δvx  δx  δv  y J = ∇v(x, t) =   δx  δvz δx 

δvx δy δvy δy δvz δy

 δvx δz  δvy    δz  δvz  δz

Divergence: Diagonal of Jacobian, describes flow into/out of a region: div v(x, t) =

δvx δvz δvy + + δz δy δx

Non-Circulating Sink Im(λ1 , λ2 ) = 0 and Re(λ1 , λ2 ) < 0

The gradient points to the direction of maximum change of ρ(x, t):

 δρ(δx x,t )  ∇ρ(x, t) =  δy  δρ(x,t ) δz

Im(λ1 , λ2 ) 6= 0 and Re(λ1 , λ2 ) < 0

Saddle Point Im(λ1 , λ2 ) = 0 and λ1 · λ2 < 0

5.9

Runge-Kutta 4th Order

• The most accurate

• Better information coverage • Critical point detection and classification

k1 = ∆t · v(x, t) k1 ) 2 k2 k3 = ∆t · v(x + ) 2 k4 = ∆t · v(x + k3 ) k1 k4 k2 k3 x(t + ∆t) = k + + + + 6 3 3 6

5.10

k2 = ∆t · v(x +

5.7

Vector Field Topology

• We want ot draw along the most important lines • Draw topological skeleton of flow

div v(x0 ) < 0 : v has sink in x0

5.8

div v(x0 ) = 0 : v is source-free in x0

• Singularities in vector fields such that:

δv δvy  z − δz   δy δvx δvz   curl v(x, t) = ∇v(x, t) =  −  δz δx  δv δvx y − δx δy

5.3

Computing Characteristic Lines

Characteristic lines are tangential to the flow. δx(t) = v(x(t), t) δt • do not intersect • they are the solutions to the initial value problem

Critical Points

v(x∗ ) = 0 • Points where magnitude of veectors goes to zero and direction of vectors is undefined To find critical points: points where:

5.11

s(x′ ) = [f ∗ g](x′ ) =

Classification First, we build the Jacobian matrix for v(x∗ ) δvx δx δvy δx

δvx δy δvy δy

!

Then, for each x∗ calculate the eigenvalues λ1 , λ2 of J . To find the eigen values:

det(J −λI ) = det

δvx − δx δvy δx

Filtering By Convolution

• Sliding a function g(x) along a function f (x):

v(x∗ ) = 0

J =

Line-Integral Convolution (LIC)

• Global visualization technique • Starts with random noise (white noise) • Smear out the texture along trajectories of vector field • Results in low correlation between neighbouring lines and high correlation along flow direction • The larger the kernel, the more the values of the noise texture are blurred Steps: • Vector Field → (integration) Stream Line • Stream Line → (convolution) Noise Texture • Noise Texture → (result) Output Image

div v(x0 ) > 0 : v has source in x0

Curl/vorticity: tells how fast the flow is rotating, and the axis around which it is rotating.

Dense Texture-Based Flow Visualization

λ

δvx δy

δvy δy

−λ

!

Z

∞

f (x)g(x′ − x) dx −∞

• Function f is averaged with a weight function g • (x′ − x) centers g around x′ • We use the single stream lines that pass through a single pixel to smear out the noise • Φ0 (u) is the stream line containing the point (x0 , y0 ) • T (x, y) is the randomly generated noise texture • Compute the intensity at (x0 , y0 ) as: Z L k(u) · T (Φ(u)) du I(x0 , y0 ) = −L

5.4

Euler Method

• First order method • higher accuracy with smaller step size (∆t)

Circulating Source Im(λ1 , λ2 ) 6= 0 and Re(λ1 , λ2 ) > 0 Non-Circulating Source Im(λ1 , λ2 ) = 0 and Re(λ1 , λ2 ) > 0

x(t + ∆t) ≈ x(t) + ∆t · v(x(t), t)

Center 4

6

Visualization Mapping

Decide: • Which part of the data is shown • How to represent the data

6.1

Mapping Techniques

Properties: • Accuracy • Pop-Out (emphasize important information) • Discriminability • Separability (judge each channel indipendently) • Relative vs absolute judgement Graphical Primitives: • Points

• Lines • Areas • Surfaces Visual Channels: • Position • Color • Tilt • Shape • Size Pop-Out: • Pre-Attentive Processing: automatic and parallel detection of basic features in

5

visual information • Speed indipendent of distractor count • Works on many individual channels From Most Accurate/Effective to Less Accurate/Effective: • Position • Length • Slope/Tilt/Angle • 2D Area • Saturation/Luminance • Curvature • 3D Volume...