Data Structures for Sparse Volumetric Data

Data Structures for

Sparse Volumetric Data

J. Andreas Bærentzen, DTU Informatics

Random Facts about Volumetric Data

Structures

J. Andreas Bærentzen, DTU Informatics

Selected Tools for

Representing Sparse Volume Data in Given

Scenarios

J. Andreas Bærentzen, DTU Informatics

Overview

• Visualization: Real-time or interactive rendering of (medical) volume data

• Distance fields in conjunction with the level set method

• Very high resolution and adaptive distance fields

• Beyond distance fields: Deformable

Simplicial Complexes

What’s in a voxel?

• Volumetric data: Tabulated f: R ³ → R

• What is a voxel?

1. A grid point with an associated value?

2. A cuboid spatial region?

3. Both of the above!

• Volumetric data is

usually very sparse

How Sparse?

0 50 100 150 200 250

0 500000 1^x10⁶ 1.5^x10⁶ 2^x10⁶ 2.5^x10⁶

0 50 100 150 200 250

0 1^x10⁶ 2^x10⁶ 3^x10⁶ 4^x10⁶ 5^x10⁶ 6^x10⁶

• Sparse means that few voxels are “of interest”

• Red arrow indicates visibility threshold

Dense Voxel Grids

• Computer memory is linear ...

• Assume a volume

• of dimensions: xdim, ydim, zdim

• stored in a linear array data

• Voxel at grid pos [x,y,z] is stored in data at position:

• data[z*xdim*ydim+y*xdim+x]

Coherence

• We usually need to access voxels in a spatially coherent fashion

• Interpolation (trilinear)

• Walking along rays

• Computing gradients, curvature, etc.

• Sometimes, we just need to visit all voxels:

E.g. when computing a histogram.

• Coherence is important on both CPU and GPU

Voxels pierced by ray

Typical gradient stencil

Bilinear Interpolation

Coherence:

Importance on CPU

• An experiment: Compute mean voxel value of 256 ³ volume by traversing the grid in a

triple for loop

• Order ZYX takes 0.22 seconds

• Order XYZ takes 1.02 seconds

• So matching the linear order matters!

• This is good to bear in mind when thinking

about data structures for volumes...

Visualization

• We consider GPU based volume rendering

• Volume stored in GPU memory

MRI data set of Lars Pedersen rendered

using VoxelRay - a tool

from DTU Informatics

Volume Rendering

I ← I + T * col i * alpha i

T ← T * (1 - alpha i )

i-1 i i-2

i-3

• Ray Casting: For each pixel

i+1

walk along a ray through the

volume and integrate

Volume Rendering

I ← I + T * col i * alpha i

T ← T * (1 - alpha i )

Alpha at sample i

i-1 i i-2

i-3

• Ray Casting: For each pixel

i+1

walk along a ray through the

volume and integrate

Volume Rendering

I ← I + T * col i * alpha i

T ← T * (1 - alpha i )

Color

Computed from Shading at sample

i

Alpha at sample i

i-1 i i-2

i-3

• Ray Casting: For each pixel

i+1

walk along a ray through the

volume and integrate

Volume Rendering

I ← I + T * col i * alpha i

T ← T * (1 - alpha i )

Accummulated Transparency

Color

Computed from Shading at sample

i

Alpha at sample i

i-1 i i-2

i-3

• Ray Casting: For each pixel

i+1

walk along a ray through the

volume and integrate

Volume Rendering

I ← I + T * col i * alpha i

T ← T * (1 - alpha i )

Accummulated Transparency Accummulated

Color

Color

Computed from Shading at sample

i

Alpha at sample i

i-1 i i-2

i-3

• Ray Casting: For each pixel

i+1

walk along a ray through the

volume and integrate

• ^{We need}

• Seven trilinearly

interpolated texture

look ups per ray sample.

• Fast parallel ray traversal

• GPU provides

• Fast parallel execution of ray traversal

• Volume as 3D texture

• Built-in nearly FREE trilinear interpolation

i-1 i i-2

i-3

i+1

I ← I + T * col i * alpha i

T ← T * (1 - alpha i )

Volume Rendering

For each pixel:

For i=1 to N:

Interpolation

No significant difference in rendering performance

nearest neighbor trilinear FREE!!

Bricking

• Divide volume into “bricks” - often just to cope with amount of data

• Bricks could be slices (full X,Y dimension)

• Alternatively, exploit sparsity:

• Bricks simply divide volume into smaller

pieces but empty bricks may be omitted

Recursive Decomposition

• Recursively divide space into 2 ^d cells where d is dimension (2 ³ = 8)

• Each node contains:

• Pointer to each child

• Data associated with each child

• Save by culling empty cells

• Note leaves should be bricks not voxels!

this is a 2

²

aka “quad” tree

Giga Voxels

• Crassin et al. [2008] proposed Octree of identical 3D Texture blocks (typically 32 ³ )

• Blocks can be at various levels and also replaced by constant color values.

• Texture blocks support built-in mipmapped (multiresolution) interpolation.

• NOT SIMPLE: Blocks loaded onto GPU as needed

Figure 9: Some results: Trabecular bone data (augmented with Perlin noise) and Hypertextured bunny (based on a distance field approximated on the fly on the GPU)

of the neighboring lists (Figure 8-right). This can induce "false positives", but it remains conservative.

After this first step, each pixel of the selection mask contains a bitvector, whose non-zero entries represent the list elements to keep. We rely on the HistoPyramids [ZTTS06] to reduce the se- lection mask. This algorithm is a special case of the prefix-sum scan and binary search algorithm, highly optimized to exploit 2D locality and GPU’s texture processing units. The final step recovers the actual corresponding node indices, then the compacted texture is transferred to the CPU. During this rearrangement process, the original pixel position will be lost. Having 12 node entries per list, we can avoid this problem by using the remaining 20 bits (over 32) to encode the pixel position of the ray. Only with this location in- formation we will be able to recover the actual node indices.

After the reduction, each pixel contains a ray pixel-position and a bitmask. This information allows the creation of a compact node index texture that will be read back by the CPU. In practice, the bitmask usually contains 2-3 non-zero entries. It is thus possible to make the final compacted texture one single RGBA32 texture which allows us to store indices of four nodes. If this limit is exceeded the requests are automatically postponed to the next frame.

7 Results

All tests were performed on a Core2 bi-core E6600 at 2.4 GHz, and an NVIDIA 8800 GTS 512 graphics card (G92 GPU) with 512 MB.

All images are rendered at 512 × 512 (see Figures 1 and 9).

Example 1: Explicit volume (trabecular bone).

We used a 1024

³

scanned volume of a trabecular bone. Mipmaps were precomputed and analyzed for constant density. This exam- ple still fit in the CPU memory. We copied this volume 8 times in each direction in order to simulate a 8192

³

resolution. In our data structure, we used N = 2 and M = 16. The algorithm achieves 20- 40 Hz with smooth mipmapping activated. Without, an average of 60fps was possible. We also added scales of Perlin noise to increase richness. This noise is added procedurally on the GPU. Evaluating noise in each frame would be expensive, at a low penalty, we cre- ate bricks on the GPU that we can then use in subsequent frames.

In comparison to [GMAG08], this indicates approximately a 50%

speedup (nevertheless, this is based on our implementation).

Example 2: Procedural volume by instantiation (Sierpinski).

We used one unique brick of size 81

³

. We naturally chose N = 3 so that we can rely on one unique instantiation for all non-empty children. The resolution is potentially infinite, but in practice, the floating point precision of coordinates limits the zoom to 2

¹⁹

so the maximum virtual resolution is 8 . 4M

³

. Performance often reaches 90 Hz, and usually stays around 60.

Example 3: Hypertextures and amplification of a mesh.

For this example, we use a volume defined by the interior of a mesh.

We derive a distance field from the mesh on the fly on the GPU. and

very high quality and use 20 octaves of Perlin noise, shading, and complex materials. Due to the complex computations on the GPU to produce the volume information, the frame rate is relatively low (around 20 FPS for a 1024

³

volume).

Example 4: Cumulus cloud.

Our method was used to encode the cloud details in [BNM

^∗

08] (a paper dealing with multiple scattering in clouds). Even in combi- nation with complex shading [BNM

^∗

08], our algorithm allows for an increase of detail. We used N = 2, M = 32, and 5 octaves of Perlin noise to simulate enhance the cumulus cloud, with a virtual resolution of 2048

³

.

Memory usage: In most examples, the node pool was small (4 MB) corresponding to 64

³

entries. Using 16

³

bricks, 1024

³

indices can be referenced.The brick pool used 430 MB giving room for 42

³

bricks.

We usually trade-off some computation time for memory efficiency:

in all our examples, normals are computed on-the-fly. The procedu- ral noise examples further showed that bricks can also be created on the GPU. This on-the-fly noise creation proves actually to be more efficient than a CPU evaluation and transfer.

8 Conclusion and Future Work

We have presented a method for interactive rendering of large and very detailed volumes. Our work shows that real-time performance with high quality volume rendering is possible. The algorithm avoids most of the CPU interaction. Our compact data structure minimizes memory usage on the GPU side. The introduction of smooth transitions based on mipmapping allow temporal coher- ence and anti-aliasing. This hints at the possibility that volume data could be an important future real-time primitive.

Currently, animation is a big problem for volume data. In the future, we would like to investigate possible solutions.

Another interesting avenue would be to apply our method to other hierarchical representations: general mesh subdivisions, point ren- dering, or recent structures like volume-surface trees [BHGS06].

We would like to thank: Digisens for their support; Antoine Bouthors, Eric Brune- ton, and Hedlena Bezerra for proof reading, and the anonymous reviewers for their helpful comments. This work has been partly supported by the Excellence Cluster on Multimodal Computing and Interaction (MMCI - www.m2ci.org).

References

B ^ABOUD L., D ^ÉCORET X.: Realistic water volumes in real-time.

In EG Workshop on Natural Phenomena (2006), Eurographics.

B ^OUBEKEUR T., H ^EIDRICH W., G ^RANIER X., S ^CHLICK C.:

Volume-surface trees. Computer Graphics Forum 25, 3 (2006),

tirsdag den 17. august 2010

Hash Tables

H maps grid positions to array positions:

H(0,2,6)=0, H(5,3,1)=1, H(2,4,3)=2

In some cases we get collisions, i.e. maybe

H(1,2,3) = H(2,4,5)

Sculpting: Anatomy of a System

Volume representation

Visualization Voxelization

Geometry

Constructive or Deformative Manipulation

User

Interface Display

Constructive: According to CSG paradigm Deformative: Continuous deformation

# key data

0 (0,2,6) 23

1 (5,3,1) 232

2 (2,4,3) 67

Hashing is a mapping H from a key (e.g.

[x,y,z] ) to an index in a table of size

tsize

Hash Tables

What would be a good hash function H ? How about

H(x,y,z)=z*xdim*ydim+y*xdim+x

No: of course, tsize << xdim*ydim*zdim .

H(x,y,z)=(z*xdim*ydim+y*xdim+x)%tsize

No: Values of H should be uniformly distributed for actual inputs to avoid collisions!

Collisions are resolved by rehashing or chaining

Perfect Hashing

• The need to deal with collisions makes hash tables GPU unfriendly

• Lefebvre et al. [2006] propose a scheme for perfect hashing

• However GPU built-in inter-

polation is still an issue

!

"#$!%&$'&()*!+%!&,!-(&!&.(!.'%.!&'/-(!/(!'%!0,12'0&!'%!2,%%+/-(!&,!

0,3&'+3!&.(!)+4(3!5'&'6!'35!&.(3!&,!0,3%&$#0&!&.(!,77%(&!&'/-(!&,!/(!

'%! %1'--! '%! 2,%%+/-(! 8.+-(! %&+--! '--,8+3)! '! 2($7(0&! .'%.! 7#30&+,39!!

:,$(! 2$(0+%(-*6! 8(! +3&$,5#0(! '! )$((5*! '-),$+&.1! 7,$! 7+--+3)! &.(!

,77%(&! &'/-(! ;<(0&+,3!=9>?6! '35! +&($'&+4(-*! 0'--! &.+%! '-),$+&.1! 8+&.!

5+77($(3&!,77%(&!&'/-(!%+@(%!;<(0&+,3!=9A?9!!B,$!'!-'$)(!(3,#).!,77%(&!

&'/-(6! %#00(%%! +%! )#'$'3&((56! %,! ,#$! +&($'&+4(! 2$,0(%%! '-8'*%!

&($1+3'&(%!8+&.!'!2($7(0&!.'%.9!

!"#$ %&'&()*+,$+-$)./'&$0*1&0$

B,$!%+12-+0+&*6!8(!'%%#1(!&.'&!&.(!.'%.!&'/-(!+%!'!%C#'$(!,$!0#/(9!!

D(! -(&! +&%! %+@(! ! ! /(! &.(! %1'--(%&! 4'-#(! %#0.! &.'&! ! !^" t # 9!!

E(0'#%(!8(!C#'3&+@(!,77%(&!4'-#(%!&,!F!/+&%6!3,&!'--!,77%(&!4'-#(%!

'$(!$(2$(%(3&'/-(!+7! ! ! GHI 6!+3!8.+0.!0'%(!8(!%-+).&-*!+30$('%(!

&.(! &'/-(! %+@(! &,! ! !^" t ;A9JA?# ! &,! )+4(! (3,#).! -((8'*! 7,$! '!

2($7(0&! .'%.9! ! K,3%(C#(3&-*6! &.(! 2($7(0&! .'%.! 7#30&+,3! +%! 3,&!

%&$+0&-*!1+3+1'-6!/#&!&.(!3#1/($! ! # !,7!#3#%(5!(3&$+(%!+%!%1'--9!

L(M&6!8(!%((N!&,!'%%+)3!&.(!,77%(&!&'/-(!%+@(! $ !&,!/(!'%!%1'--!'%!

2,%%+/-(!8.+-(!%&+--!2($1+&&+3)!'!2($7(0&!.'%.9!!D(!.'4(!(M2-,$(5!

&8,!5+77($(3&!%&$'&()+(%!7,$!%(-(0&+3)! $ 6!5(2(35+3)!,3!8.(&.($!&.(!

%2((5!,7!.'%.!0,3%&$#0&+,3!+%!+12,$&'3&!,$!3,&9!

B,$!7'%&!0,3%&$#0&+,36!8(!+3+&+'--*!%(&!&.(!,77%(&!&'/-(!%+@(! $ !&,!&.(!

%1'--(%&!+3&()($!%#0.!&.'&! $ $ ^" t V # !8+&.!&.(!7'0&,$!VOAP;G"?9!!

E(0'#%(! &.(! ,77%(&! &'/-(! 0,3&'+3%!"! 0.'33(-%! ,7! F! /+&%! ('0.6! &.+%!

%+@(!0,$$(%2,35%!&,!=!/+&%!2($!5'&'!(3&$*6!'35!'--,8%!'!2($7(0&!.'%.!

+3!1'3*!0'%(%9!!Q7!&.(!.'%.!0,3%&$#0&+,3!7'+-%6!8(!+30$('%(! $ !+3!'!

)(,1(&$+0!2$,)$(%%+,3!#3&+-!0,3%&$#0&+,3!%#00((5%9!

B,$! 0,12'0&! 0,3%&$#0&+,36! 8(! 2($7,$1! '! /+3'$*! %('$0.! ,4($! $ 9!!

E(0'#%(! ,#$! 0,3%&$#0&+,3! +%! )$((5*! '35! 2$,/'/+-+%&+06! 7+35+3)! '!

2($7(0&! .'%.! 7,$! '! )+4(3! &'/-(! %+@(! $ ! 1'*! $(C#+$(! %(4($'-! '&R

&(12&%6! 2'$&+0#-'$-*! +7! $ ! +%! 0-,%(! &,! ,2&+1'-9! ! D(! 1'N(! #2! &,! H!

%#0.!'&&(12&%!#%+3)!5+77($(3&!$'35,1!%((5%9!!S'%.!0,3%&$#0&+,3!+%!

'!2$(2$,0(%%6!%,!+34(%&+3)!&.+%!(M&$'!&+1(!1'*!/(!$('%,3'/-(9!

D(!7+35!(12+$+0'--*!&.'&!.'%.!0,3%&$#0&+,3!+%!-(%%!(77(0&+4(!+7! $ ! .'%!'!0,11,3!7'0&,$!8+&.! ! !,$!+7! ^{! 1,5 $ }

^

^{A6 A$}

`

9!!T.#%!7,$!

&.(! 7'%&! 0,3%&$#0&+,3! 8(! '#&,1'&+0'--*! %N+2! &.(%(! #32$,1+%+3)!

%+@(%6!'35!7,$!&.(!0,12'0&!0,3%&$#0&+,3!8(!'5'2&!/+3'$*!%('$0.!&,!

'4,+5!&(%&+3)!&.(1!#3-(%%!'&!&.(!-,8($R(35!,7!&.(!$'3)(9!

!"2$ %&'&()*+,$+-$3.03$(+&--*(*&,)0$

"#$!+3+&+'-!'22$,'0.!8'%!&,!7+--!&.(!1'&$+0(%!%_J6%_A!;5(7+3+3)!&.(!

+3&($1(5+'&(!.'%.!7#30&+,3%!&_J6&_A?!8+&.!$'35,1!2$+1(!0,(77+0+(3&%6!

+3!&.(!%'1(!%2+$+&!'%!2$+,$!.'%.+3)!8,$N9!!T,!+12$,4(!.'%.!0,.($R (30(!8(!&.(3!%,#).&!&,!1'N(!&.(%(!1'&$+0(%!1,$(!$()#-'$9!

T,! ,#$! )$('&! '1'@(1(3&6! 8(! 7,#35! &.'&! -(&&+3)! %_J6%_A! U#%&! /(!

'"(#)')*+!,)$'-(.!5,(%!3,&!%+)3+7+0'3&-*!.+35($!&.(!0,3%&$#0&+,3!,7!

'!2($7(0&!.'%.9!!T.(!7#30&+,3%!&_J6&_A!&.(3!%+12-*!8$'2!&.(!%2'&+'-!

5,1'+3! 1#-&+2-(! &+1(%! ,4($! &.(! ,77%(&! '35! .'%.! &'/-(%6! 1,4+3)!

,4($!5,1'+3!2,+3&%!'35!&'/-(!(3&$+(%!+3!-,0N%&(29!!T.#%!&.(!,77%(&!

&'/-(! '00(%%!

>

A

@

! +%! 2($7(0&-*! 0,.($(3&9! ! V-&.,#).!&_J;/?! +%!

'-%,! 0,.($(3&6! &.(! .'%.! &'/-(! '00(%%!) & /; ?

>

^{; ?}

@

0 & / ! +%! )(3($'--*! 3,&!

/(0'#%(! +&! +%! U+&&($(5! /*! &.(! ,77%(&%9! ! S,8(4($6! +7! '5U'0(3&! ,77%(&!

4'-#(%!+3!)!'$(!&.(!%'1(6!+9(9!+7!&.(!,77%(&!&'/-(!+%!-,0'--*!0,3%&'3&6!

&.(3!&! +&%(-7! 8+--! '-%,! /(! 0,.($(3&9! ! T.+%! 2$,2($&*! +%! 0,3%+5($(5!

7#$&.($!+3!<(0&+,3!=9=9!

"3(! 3(0(%%'$*! 0,35+&+,3! ,3!&_J6&_A! +%! &.'&! &.(*! 1#%&! 1'2! &.(! 5(R 7+3(5!5'&'!&,!5+%&+30&!2'+$%9!!T.'&!+%6! ^{/ 1} o

& / & /_J^{; ?6 ; ?}_A

!1#%&!

/(! +3U(0&+4(9! ! Q35((56! +7! &.($(! 8($(! &8,! 2,+3&%! /_A6/_G1! 8+&.!

&_J;/_A?O&_J;/_G?! '35! &_A;/_A?O&_A;/_G?6! &.(3! &.(%(! 2,+3&%! 8,#-5! '-8'*%!

.'%.!&,!&.(!%'1(!%-,&!&;/_A?O&;/_G?!$()'$5-(%%!,7!&.(!,77%(&!%&,$(5!+3!

)W&_A;/_A?X6!1'N+3)!'!2($7(0&!.'%.!+12,%%+/-(9!

T.(! 0,35+&+,3! 7,$! +3U(0&+4+&*! +%! %+1+-'$! &,! '! 2($7(0&! .'%.! ,7! #!

(-(1(3&%!+3&,!'!&'/-(!,7!%+@(! 0 u ) !$ 9!!V22-*+3)!&.(!%'1(!

7,$1#-'!'%!+3!<(0&+,3!G6!8(!5($+4(!'!2$,/'/+-+&*!,7!%#00(%%!,7!

G P G P G

Y$YS | (^{# !$} | (^{# $} 6!

8.+0.!%((1%!,1+3,#%-*!-,8!Z!,3-*!AG[!7,$!

V

$ #P J9GH ^9!!D(!

/(-+(4(!&.'&!&.+%!+%!&.(!1'+3!$('%,3!&.'&!2$(4+,#%!2($7(0&!.'%.+3)!

%0.(1(%!$(%,$&(5!&,!'55+&+,3'-!&'/-(%!'35!.'%.!7#30&+,3%9!

S,8(4($6!#3-+N(!2$+,$!8,$N!8(!5,!3,&!%(-(0&!&_J6&_A!&,!/(!$'35,1!

7#30&+,3%9!!E(0'#%(!,#$!7#30&+,3%!&_J6&_A!.'4(!2($+,5+0+&+(%! ! !'35!

$ ! $(%2(0&+4(-*6! +7! &.(%(! 2($+,5+0+&+(%! '$(! 0,2$+1(! &.(3! 8(! '$(!

)#'$'3&((5!+3U(0&+4+&*!8.(3!&.(!5,1'+3!%+@(! 2 d ! $ 6!,$!(C#+4'R -(3&-*! ;%+30(! ! #| ?! 8.(3! &.(! 5'&'! 5(3%+&*! 9! ! Q3!

2$'0&+0(6!$! +%! &*2+0'--*! -'$)(! (3,#).! &.'&! &.+%! +%! '-8'*%! &$#(6! '35!

&.#%!8(!3((5!3,&!&(%&!7,$!+3U(0&+4+&*!(M2-+0+&-*9!

P AP

# 2 $

U t

!

\,1'+3!3

"77%(&!&'/-(!)

4

S'%.!&'/-(!0

A A; ?

& 4  1 3

W X4 )

&A

&J

!

B+)#$(!>]!T.(!'%%+)31(3&!,7!,77%(&!4(0&,$! !0,$$(%2,35%!&,!'!

#3+7,$1!&$'3%-'&+,3!,7!&.(!2,+3&%! !8+&.+3!&.(!.'%.!&'/-(9!)W X4

A A; ?

& 4

!"4$ 56&.)*+,$+-$+--0&)$)./'&$

V%!%.,83!+3!B+)#$(!>6!,3!'4($')(!('0.!(3&$*!4!,7!&.(!,77%(&!&'/-(!

+%! &.(! +1')(! &.$,#).!&_A! ,7! ! 5'&'! 2,+3&%! Z! ! 3'1(-*!

&.(! %(&! 9! ! T.(! '%%+)31(3&! ,7! &.(! ,77%(&! 4(0&,$! ! 5(&($1+3(%! '! #3+7,$1! &$'3%-'&+,3! ,7! &.(%(! 2,+3&%! 8+&.+3! &.(! .'%.!

&'/-(9!!T.(!),'-!+%!&,!7+35!'3!'%%+)31(3&!&.'&!5,(%!3,&!0,--+5(!8+&.!

,&.($!2,+3&%!.'%.(5!+3!&.(!&'/-(9!

A # $P =

V |

A A; ?

& 4  1 )W X4

V!3'^4(!'-),$+&.1!7,$!0$('&+3)!'!2($7(0&!.'%.!8,#-5!/(!&,!+3+&+'-R +@(!&.(!,77%(&!&'/-(!)!&,!@($,!,$!$'35,1!4'-#(%6!-,,N!7,$!0,--+%+,3%!

+3!&;/?6!'35!&$*!&,!_#3&'3)-(`!&.(%(!/*!2($&#$/+3)!&.(!,77%(&!4'-#(%6!

7,$!+3%&'30(!#%+3)!$'35,1!5(%0(3&!,$!%+1#-'&(5!'33('-+3)9!!S,8R (4($6! &.+%! 3'^4(! '22$,'0.! 7'+-%! /(0'#%(! +&! C#+0N-*! %(&&-(%! +3&,!

+12($7(0&! 1+3+1'6! 7$,1! 8.+0.! +&! 8,#-5! &'N(! '! -,3)! %(C#(30(! ,7!

,77%(&!$('%%+)31(3&%!&,!7+35!'!-,8($!&,&'-!3#1/($!,7!0,--+%+,3%9!

V!N(*!+3%+).&!7$,1!WB,M!(&!'-!AaaGX!+%!&.'&!&.(!(3&$+(%!)W4X!8+&.!

&.(! -'$)(%&! %(&%! ! ,7! 5(2(35(3&! 5'&'! 2,+3&%! '$(! &.(! 1,%&!

0.'--(3)+3)! &,! '%%+)36! '35! &.($(7,$(! %.,#-5! /(! 2$,0(%%(5! 7+$%&9!!

"#$! '-),$+&.1! '%%+)3%! ,77%(&! 4'-#(%! )$((5+-*! '00,$5+3)! &,! &.+%!

.(#$+%&+0! ,$5($! ;0,12#&(5! (77+0+(3&-*! #%+3)! '! /#0N(&! %,$&?9! ! B,$!

('0.! (3&$*!46! 8(! %('$0.! 7,$! '3! ,77%(&! 4'-#(! ! %#0.! &.'&! &.(!

5'&'! (3&$+(%! ! 5,! 3,&! 0,--+5(! 8+&.! '3*! 5'&'! 2$(4+,#%-*!

'%%+)3(5!+3!&.(!.'%.!&'/-(6!+9(96!

A A; ?

& 4

W X4

A )

A ; ?

& 4

> @

A A; ?6 J; ? W X

/ & 4 0 & / 4 2#"(5

 ) 9!

T.(!%2'0(!,7!FR/+&RC#'3&+@(5!,77%(&!4'-#(%!+%! ]^"_{1+3; 6GHI?!} ª«!P GHHº» 9!!

Q3!2$'0&+0(!+&!+%!+12,$&'3&!&,!%&'$&!&.(!%('$0.!'&!'!$'35,1!-,0'&+,3!

+3!&.+%!%2'0(6!,$!(-%(!/'5!0-#%&($+3)!1'*!$(%#-&9!!Q7!3,!4'-+5!,77%(&!

)W4X!+%!7,#356!,3(!0,#-5!&$*!/'0N&$'0N+3)6!/#&!8(!7,#35!$(%#-&%!&,!

/(!%'&+%7'0&,$*!8+&.,#&!&.+%!'55(5!0,12-(M+&*9!!L,&(!&.'&!&,8'$5%!

&.(! (35! ,7! 0,3%&$#0&+,36! &.(! ,77%(&! (3&$+(%! 0,3%+5($(5! '$(! &.,%(!

8+&.! (M'0&-*! ,3(! 5(2(35(3&! 2,+3&6! +9(9! &_A^A; ?4 OA9! ! T.(%(! '$(!

('%*!0'%(%6!'%!&.(!'-),$+&.1!%+12-*!7+35%!,77%(&!4'-#(%!&.'&!5+$(0&!

&.(%(!%,-(!2,+3&%!&,!,2(3!.'%.!%-,&%9!

!

!

"#!$%&'!()(*+,!-*!.*/&#*!)!(*+/*0$!123$&.&1*#'&4#)3!%)'%!/2#0$&4#!

4/!$%*!/4+1!

> @

5 6

7 8 7 8 7 8

! " ! " ) ! " ,!

-%&0%!0419&#*'!$-4!&1(*+/*0$!%)'%!/2#0$&4#'! ! ₅ ,! ₆ !-&$%!)#! #$$%&'(

')*+&! ):!!"#$2&$&;*3<,!$%*!+43*!4/!$%*!4//'*$!$)93*!&'!$4! =>&$$*+?!$%*!

&1(*+/*0$!%)'%!/2#0$&4#! ! ₅ !&#$4!)!(*+/*0$!4#*:!!@3$%42A%!$%*!4//'*$!

$)93*!2'*'!)..&$&4#)3!1*14+<,!&$!0)#!/4+$2#)$*3<!9*!1).*!'&A#&/&B 0)#$3<!'1)33*+!$%)#!$%*!.)$)!&$'*3/!C!$<(&0)33<!&$!%)'!4#3<!6DBEDF!

)'!1)#<!*#$+&*',!)#.!*)0%!*#$+<!%)'!>2'$!G!9&$'!(*+!044+.&#)$*:!

!"#$%#&'()*+,+-(+.!!H+&4+!-4+I!4#!(*+/*0$!%)'%&#A!%)'!/402'*.!4#!

*J$*+#)3! '$4+)A*! 4/! .)$)! +*04+.'! &#.*J*.! 9<! 0%)+)0$*+! '$+&#A'! 4+!

'()+'*! &#$*A*+':! ! K4! 42+! I#4-3*.A*,! #4! -4+I! %)'! 04#'&.*+*.!

123$&.&1*#'&4#)3! .)$)! )#.! &$'! 2#&L2*! 4((4+$2#&$&*':! ! "#.**.,! &#!

041(2$*+! A+)(%&0',! EM! )#.! NM! $*J$2+*! .)$)! &'! 4/$*#! )00*''*.!

04%*+*#$3<! 9<! $%*! ()+)33*3! OHP,! )#.! &'! $%*+*/4+*! '-&QQ3*.,! $&3*.,!

)#.!0)0%*.:!!".*)33<,!%)'%*.!$*J$2+*'!'%423.!'&1&3)+3<!9*!.*'&A#*.!

$4!*J(34&$!)00*''!04%*+*#0*:!

R2+! '432$&4#! %)'! $-4! ()+$':! ! S%*+*)'! (+&4+! -4+I! '**I'! $4! 1)I*!

&#$*+1*.&)$*!%)'%!/2#0$&4#'!3&I*! ! ₅ ,! ₆ !)'!+)#.41!)'!(4''&93*,!-*!

&#'$*).!.*'&A#!$%*1!$4!9*!'()$&)33<!04%*+*#$,!+*'23$&#A!&#!*//&0&*#$!

)00*''! &#$4! $%*! 4//'*$! $)93*! ):! ! T*1)+I)93<,! -*! .*/&#*! ! ₅ ,! ₆ ! '&1(3<! )'! 14.234! 7-+)()+42#.8! )..+*''&#A! 4;*+! $%*! $)93*':!!

U*04#.,! -*! 4($&1&Q*! $%*! 4//'*$! ;)32*'! &#! )! $4! 1)J&1&Q*! 04%*+B

*#0*! 4/! !! &$'*3/:! ! V+*)$&#A! )! (*+/*0$! %)'%! &'! )3+*).<! )! .&//&023$!

0419&#)$4+&)3! (+493*1:! ! W4#*$%*3*'',! -*! /&#.! $%)$! $%*+*! +*1)&#!

*#42A%! .*A+**'! 4/! /+**.41! $4! &1(+4;*! 04%*+*#0*! )#.! $%*+*9<!

&#0+*)'*!+2#$&1*!%)'%&#A!(*+/4+1)#0*:!

"1(3*1*#$*.! 4#! $%*! OHP,! 42+! (*+/*0$! %)'%! )334-'! .)$)! )00*''!

2'&#A!>2'$!4#*!)..&$&4#)3!$*J$2+*!)00*'',!(32'!4#3<!)942$!XBY!14+*!

'%).*+!&#'$+20$&4#'!.*(*#.&#A!4#!$%*!)((3&0)$&4#!'0*#)+&4:!

!"#,/%$0' +-()1%-2.! ! "#! )..&$&4#! $4! '()+'*! .)$)! 041()0$&4#,! -*!

)3'4!.*'0+&9*!'*;*+)3!'0%*1*'!/4+!*#04.&#A!$%*!'()$&)3!(4'&$&4#'!4/!

$%*'*! '()+'*! ')1(3*':! ! U(*0&/&0)33<,! -*! &#$+4.20*! .41)&#! 9&$',!

(4'&$&4#!$)A',!)#.!()+)1*$*+&Q*.!(4'&$&4#!%)'%*':!!

3%&$+,%-2'#-1'4&)(5%-2.!!Z4+!)((3&0)$&4#'!$%)$!+*L2&+*!04#$&#242'!

340)3!&#$*+(43)$&4#!4/!$%*!'()+'*!.)$),!-*!04#'&.*+!$-4!)((+4)0%*':!!

K%*! /&+'$! &'! $4! )334-! #)$&;*! /&3$*+&#A! &#! $%*! .*.&0)$*.! OHP! %)+.B -)+*! 9<! A+42(&#A! $%*! .)$)! &#$4! ')1(3*B94+.*+*.! 9340I'! [\+)2'!

)#.!]+$3!E55E^:!!"#!$%&'!'*$$&#A,!42+!04#$+&92$&4#!&'!$4!+*(3)0*!$%*!

$+).&$&4#)3!9340I!&#.&+*0$&4#!$)93*!9<!)!041()0$!'()$&)3!%)'%!4;*+!

$%*!'()+'*3<!.*/&#*.!9340I':!!K%*!3&1&$&#A!/)0$4+!&#!2'&#A!9340I'!&'!

$%)$!.)$)!12'$!9*!.2(3&0)$*.!)34#A!9340I!942#.)+&*',!$%2'!.&'042+B )A&#A!'1)33!9340I'!'&Q*'!)#.!3*).&#A!$4!1*14+<!934)$:!

R2+! '*04#.! '432$&4#! )$$)&#'! )! 14+*! 041()0$! +*(+*'*#$)$&4#! 9<!

/4+A4&#A! 9340I&#A! )#.! &#'$*).! (*+/4+1&#A! /&3$*+&#A! *J(3&0&$3<! )'!

A*#*+)3B(2+(4'*!041(2$)$&4#:!!@$!(+*'*#$!$%&'!&#02+'!)#!)((+*0&)B 93*!34''!&#!(*+/4+1)#0*,!92$!0)#!+*.20*!1*14+<!9<!)!/)0$4+!N!4;*+!

9340I&#A!'0%*1*':!

67#8"&+/.! ! K4! (+4;&.*! 04#$*J$! $4! $%*! .&'02''&4#,! -*! /&+'$! &332'B

$+)$*! 42+! '0%*1*! 2'&#A! $-4! 04)+'*! *J)1(3*'! &#! Z&A2+*! 6:! ! K%*!

.41)&#!.)$)!;)32*'!)+*!$)I*#!/+41!'&1(3*!3&#*)+!0434+!+)1(',!)#.!

$%*!4//'*$!$)93*!;*0$4+'!)+*!;&'2)3&Q*.!)'!0434+':!

"#!$%*!EM!*J)1(3*,!$%*!6EG ^E !&1)A*!04#$)&#'!)!'*$!4/!6,NG6!(&J*3'!

7G:XF8!-&$%!'2((3*1*#$)3!&#/4+1)$&4#,!*:A:!;*0$4+!'&3%42*$$*!.)$):!!

K%&'! '()+'*! (&J*3! .)$)! &'! ()0I*.! &#$4! )! %)'%! $)93*! 4/! '&Q*!

NG ^E _6,XXX,! -%&0%! &'! 120%! '1)33*+! $%)#!$%*! 4+&A&#)3! &1)A*:! ! K%*!

(*+/*0$!%)'%!/2#0$&4#!&'!.*/&#*.!2'&#A!)#!4//'*$!$)93*!4/!'&Q*!6G ^E :!

"#!$%*!NM!*J)1(3*,!)!$+&)#A3*!1*'%!&'!0434+*.!9<!)00*''&#A!)!NM!

$*J$2+*! 4/! '&Q*! 6EG ^N :! ! R#3<! X6,6E`! ;4J*3'! 7E:5F8! )+*! )00*''*.!

-%*#!+*#.*+&#A!$%*!'2+/)0*!2'&#A!#*)+*'$B/&3$*+&#A:!!K%*'*!'()+'*!

;4J*3'!)+*!()0I*.!&#$4!)!NM!$)93*!4/!'&Q*!ND ^N _XE,G`D!2'&#A!)!6a ^N ! 4//'*$!$)93*:!

!"# $%&'(%)#*+,-#+.#/'0/1.2#

9+,:+($'*#/*%-2.!!S*!0)#!(+4;&.*!%*+*!4#3<!)!9+&*/!'211)+<!4/!

$%*!3&$*+)$2+*:!!Z4+!)#!*J$*#'&;*!'2+;*<,!+*/*+!$4![VQ*0%!*$!)3!6aa`^:!

K%*!(+49)9&3&$<!$%)$!+)#.413<!)''&A#&#A! ,!*3*1*#$'!&#!)!$)93*!4/!

'&Q*!-!+*'23$'!&#!)!(*+/*0$!%)'%!&'!

^{6 E 6}

H+ 7 , 8 Hb , - 6 ˜ 6 _- ˜ 6 _- " 6 ^, _- :!

S%*#!$%*!$)93*!&'!3)+A*!7&:*:! 8,!-*!0)#!2'*!$%*!)((+4J&1)B

$&4#! & ^. | 6 . !/4+!'1)33!.!$4!49$)&#c! ^{- ,}

E

6d E d 7 68 d

Hb

76 E 7 688 d 7 7 68 d E 8 d E

H+ 7 , 8 6

:

- - , -

, - , , - , -

, - & & &

& & &

| ˜ ˜

! |

"

!

K%2',! $%*! (+*'*#0*! 4/! )! %)'%! 0433&'&4#! &'! %&A%3<! 3&I*3<! -%*#! $%*!

$)93*!'&Q*! -!&'!120%!3*''!$%)#! , ^E :!!K%&'!&'!)#!&#'$)#0*!4/!$%*!-*33!

I#4-#!=9&+$%.)<!()+).4J?!C!)!A+42(!4/!4#3<!EN!(*4(3*!%);*!14+*!

$%)#!D5F!0%)#0*!4/!%);&#A!)$!3*)'$!4#*!'%)+*.!9&+$%.)<:!

K%*!(+49)9&3&$<!4/!/&#.&#A!)!-/,/-)+!(*+/*0$!%)'%!7-%*+*!, -8!&'c!

6 E 6

Hb

34A 34A

34A e 34A e

H+ 7 8

,

, , ,

, , , ,

, , , , ,

, , , ,

, ,

,

& &

&

˜ ˜

|

"

!

-%&0%!2'*'!U$&+3&#Af'!)((+4J&1)$&4#! 34 :!!K%*+*B /4+*,! $%*! *J(*0$*.! #219*+! 4/! 9&$'! #**.*.! $4! .*'0+&9*! $%*'*! +)+*!

1&#&1)3!(*+/*0$!%)'%!/2#0$&4#'!&'!&#$2&$&;*3<!

A e , | , 34A , ,

Hb

E H+ 6 7 8 E E

34A _, | 34A & ^, 34A & , | 6:XXN ,

0

,!

)'!+*(4+$*.!9<!Z4J!*$!)3![6aaE^!)#.!9)'*.!4#!*)+3&*+!)#)3<'&'!9<!

g*%3%4+#![6aGE^:!

U*;*+)3! #219*+B$%*4+*$&0)3! 1*$%4.'! 04#'$+20$! (*+/*0$! %)'%! /2#0B

$&4#'! 9<! *J(34&$&#A! $%*! V%&#*'*!+*1)&#.*+!$%*4+*1! [*:A:! S&#$*+'!

6aa5^:! ! b4-*;*+,! *;*#! /4+! '*$'! 4/! )! /*-! .4Q*#! *3*1*#$',! $%*'*!

/2#0$&4#'!&#;43;*!&#$*A*+!04*//&0&*#$'!-&$%!%2#.+*.'!4/!.&A&$':!

@!14+*!041(2$*+B)1*#)93*!)((+4)0%!&'!$4!.*/&#*!$%*!%)'%!2'&#A!

4#*!4+!14+*!)2J&3&)+<!$)93*':!!Z+*.1)#!*$!)3![6aGX^!2'*!$%+**!'20%!

$)93*'! )#.! $-4! #*'$*.! %)'%! /2#0$&4#'! $4! %)'%! )! '()+'*! '*$! 4/! ,!

&#$*A*+'!$)I*#!/+41 ] ₀ h5, , ! 6i :!K%*&+!'0%*1*!$)I*'!04#'$)#$!

$&1*!)#.! N 3 !9&$'!4/!1*14+<:!!K%*!%)'%!&'!04#'$+20$*.!-&$%!)!

.*$*+1&#&'$&0! )3A4+&$%1! $%)$! $)I*'! ! $&1*:! ! U0%1&.$! )#.!

U&*A*3![6aa5^!+*.20*!'()0*!041(3*J&$<!$4!$%*!$%*4+*$&0)33<!4($&1)3!

!9&$',!92$!$%*!04#'$)#$!&'!3)+A*!)#.!$%*!)3A4+&$%1!.&//&023$:!

4A

, ,

7 8 1 ,0 7 8 ,

4

U41*!'0%*1*'![*:A:!j+)&#!)#.!K%)+(!6aa5^!$+*)$!(*+/*0$!%)'%&#A!

)'! )#! &#'$)#0*! 4/! '()+'*! 1)$+&J! 041(+*''&4#:! ! K%*<! 1)(! )!

942#.*.! +)#A*! 4/! &#$*A*+'! $4! )! EM! 1)$+&J,! )#.! 041()0$! $%*! .*B /&#*.! *#$+&*'! &#$4! )! 6M! )++)<! 9<! $+)#'3)$&#A! $%*! 1)$+&J! +4-':!!

U()+'*!1)$+&J!041(+*''&4#!&'!I#4-#!$4!9*!WHB041(3*$*:!

K%*!14'$!(+)0$&0)3!'0%*1*'!)0%&*;*!041()0$!+*(+*'*#$)$&4#'!)#.!

'0)3*! $4! 3)+A*+! .)$)'*$'! 9<! A&;&#A! 2(! A2)+)#$**'! 4/! 4($&1)3&$<:!!

K%*'*!(+49)9&3&'$&0!04#'$+20$&4#'!1)<!&$*+)$*!4;*+!'*;*+)3!+)#.41!

()+)1*$*+'! 2#$&3! /&#.&#A! )! '432$&4#:! ! Z4+! *J)1(3*,! U)A*+! [6aGD^!

.*/&#*'! )! %)'%! ! 2 7 8 ! 2 ₅ 7 8 3 ! 2 _{6 6} [ 7 8^ 3 ! 2 _E [ 7 8^14. _E - ,! -%*+*!

/2#0$&4#'! ! ₅ ,! ₆ ,! _E ! 1)(! '$+&#A! I*<'! 2! $4! ] ] _{- 4 4} ! +*'(*0$&;*3<,!

)#.! 3 ₆ ,3 _E !)+*!$-4!$)93*'!4/!'&Q*! 4:!!b4-*;*+,!$%&'!)3A4+&$%1!$)I*'!

*J(*0$*.!$&1*!174 ^X 8,!)#.!&'!(+)0$&0)3!4#3<!2(!$4!,_D6E!*3*1*#$':!

, , ]

Z4J!*$!)3![6aaE^!).)($!U)A*+f'!)((+4)0%!$4!0+*)$*!$%*!/&+'$!'0%*1*!

-&$%!A44.!);*+)A*B0)'*!(*+/4+1)#0*!7k66,!9&$'8!4#!3)+A*!.)$)'*$':!!

K%*&+! &#'&A%$! &'! $4! )''&A#! ;)32*'! 4/! )2J&3&)+<! $)93*'! 3 ₆ ,3 _E ! &#! .*B 0+*)'&#A!4+.*+!4/!#219*+!4/!.*(*#.*#0&*':!!K%*<!)3'4!.*'0+&9*!)!

'*04#.! '0%*1*! $%)$! 2'*'! L2).+)$&0! %)'%&#A! )#.! )..'! 9+)#0%&#A!

9)'*.! 4#! )! $)93*! 4/! 9&#)+<! ;)32*'l! $%&'! '*04#.! '0%*1*! )0%&*;*'!

kX,!9&$'!/4+!.)$)'*$'!4/!'&Q*!,k65 ^Y :!

tirsdag den 17. august 2010

Distance Fields

• We can store complex shapes using distance fields

• A distance field stores the

distance to the closest point on some surface, the 0-level set

• Often we do not care about the distance outside a narrow band

• Typically only O(n

²

) voxels are used.

4

f=0 level set

Narrow Band Region

+inf

-inf

Level Set Method

• The LSM represents

surfaces using distance fields

• Surface is updated indirectly by updating distance field:

Φ

ⁿ⁺¹

= Φ

ⁿ

-F|∇Φ|

• Changes to topology are

trivial

Recursive

Decomposition

• Octrees can and have been used for distance fields but octrees exhibit

• O(log n) access time not O(1)

• poor data locality and too many indirections

• Much computational overhead involved in

maintaining data structure.

Hierarchical Grids

• Top-level grid contains pointers to fine grid OR +/- INF

• Fine grid contains precise distance values.

• Three or more levels could be used.

• Analyzed by Bridson (who called it sparse block grids)

+inf +inf +inf +inf

+inf

+inf +inf +inf -inf -inf

-inf

Narrow Band

Run Length Encoding

• A very simple way of compressing data. In 1D:

• Plain: AAAACCDEFFFFFFGGGGGG

• Coded: 4A2C1D1E6F6G

• Hierarchical Run-length encoding is a run

length coding of a run length coding of a

run length coding ....

Discussion

• Houston et al. [2006] claim better memory performance than octrees for H-RLE

• Believable: Narrow band volumes ideal for run length coding.

• Caveat: No comparison to hierarchical grids.

• H-RLE allows the volume to easily be extended in any direction.

• However: A hierarchical grid with a top

level grid as hash table offers the same!

Adaptive Volumes

• Bærentzen used an octree to divide space into cells

• Voxels (grid points) are stored in a grid of hash tables.

An Adaptive Volume

Cells are classified as being interior, surface or exterior.

Voxels are stored at the corners of surface cells.

Interior cell Exterior cell Surface cell

A 16384 ³ Volume

• Very high resolutions is possible if we only use high resolution where needed.

• Decoupling the storage of voxels from the octree, we can deal with huge volumes

• Similar to Frisken et al. [2000]

THE WALL

if you want to do the level set method with adaptive resolution

• Several plausible solutions for extremely high resolution volumes

• Some plausible solutions for adaptive

resolution volumes - but these tend to be static

• Even if a adaptive dynamic volume rep was designed - the level set method has its

flaws!

Top 3 Problems with the LSM

?

The LSM is bound to a scale interval dictated by the grid

resolution The LSM suffers from

numerical diffusion

The LSM has no explicit

interface representation

Deformable Simplical Complexes

• The DSC method addresses all three

“level set issues”

• Interface (boundary) is explicitly represented as a sub-complex of a simplicial complex

• which is irregular, hence may adapt to details.

• Interface vertices are moved directly which leads to very little diffusion.

Deformable Simplicial Complexes Results

Deformable Simplicial Complexes - 2D version

Bærentzen & Misztal Deformable Simplicial Complexes

Deformable Simplicial Complexes Results

Deformable Simplicial Complexes - 2D version

tirsdag den 17. august 2010

In 2D

3D

Steps

1. For each vertex find target positions

2. Move vertices as far as possible towards target without inversions.

3. Improve the mesh

1. Smooth & improve connectivity of tetra mesh

2. Remove degeneracies 3. Improve surface mesh

4. Unless all vertices are at target go to 2

Advantages

1. Robust topological adaptivity 2. Little numerical diffusion

3. Highly scale-adaptive (thanks to the irregular grid) - this is where sparse comes in ...

4. Availability of both surface and volume representation

5. Explicit surface representation does not

change gratuitously between time steps

6. Allows for topology control

Shrinking by Face Offsetting

Conclusions

• Exploiting sparsity has its costs:

• added complexity

• lost coherence

• Hence chooses simple schemes:

hierarchical grids, run length coding.

• For problems where you need topological and spatial adaptivity use DSC (let me

know :-)

Acknowledgements

• DSC is the work

of Marek Misztal

References

• Bridson, R. 2003. Computational aspects of dynamic surfaces. dissertation.

Stanford University, Stanford, CA.

• Bærentzen J.A. Manipulation of Volumetric Solides with Applications to Sculpting, dissertation. Technical University of Denmark.

• Frisken, S. F., Perry, R. N., Rockwood, A. P., and Jones, T. R. 2000.Adaptively

sampled distance fields: A general representation of shape for computer graphics.

In Proceedings of SIGGRAPH 2000, pp. 249–254.

• Ben Houston Michael Bang Nielsen, Christopher Batty, Ola Nilsson and Ken Museth. Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface

Representation, ACM Transactions on Graphics 25(1), January 2006. Pages

151-175

• Lefebvre, S. and Hoppe H. Perfect Spatial Hashing, In Proceedings of SIGGRAPH 2006, pp. 579-588

• Schneider, J., and R. Westermann. 2003. Compression Domain Volume Rendering.

In Proceedings of IEEE Visualization, pp. 293–300.

Thanks ... questions?

bonus

Hash Tables

• Observations:

• We need to store the key

• If the table is nearly full, we get many collisions, so we stay below 70% load factor

• Cache coherence and hashing are at odds!

• Note: we can traverse the hashed-to table linearly

• A hash table could be used to store the top

level grid in a two level hierarchy

Efficient Sparse Voxel Octrees

• Laine et al. 2010 proposed a GPU based method

• Polygonal geometry converted to voxels - stored in octree

• Neighbour information is never used. Blockiness

accepted and fixed in post process blurring

Figure 30: Effects of post-process filtering. All images are ��� � ��� pixels in size. Voxel resolution is limited in order to make the effect stand out better. The leftmost image is from a car scene that was not used in benchmarks.

Figure 31: Voxel renderings without (upper row) and with (lower row) contours. Post-process filtering is disabled to better visualize the individual voxels. Voxel resolution is limited in order to highlight the differences. For example, in F

^AIRY

it would be impossible to find a badly undersampled region if all voxel levels were used.

tirsdag den 17. august 2010

Linear Octrees

100 101

• ^Observe

• x= , y=

• The octree path is

* *

Linear Octrees

*

1 0

1 0 1 0

• ^Observe

• x= , y=

• The octree path is

*

=302 (base 4)

Linear Octrees

• In the normal grid encoding, we shift concatenate Z 0 Z 1 Z 2 Y 0 Y 1 Y 2 X 0 X 1 X 2

• To compute the Morton code we interlace Z 0 Y 0 Z 0 Z 1 Y 1 X 1 Z 2 Y 2 X 2

• A linear octree is an array of Morton

codes. Saves intermediate nodes+pointers!

• We could use b bits from Morton code as a

simple hash function [Lewiner et al. 2010]