Transcript lect05_Contouring_II

CSE 554
Lecture 5: Contouring (faster)
Fall 2013
CSE554
Contouring II
Slide 1
Review
• Iso-contours
– Points where a function evaluates to a
same value (iso-value)
• Smooth thresholded boundaries
• Contouring methods
– Primal methods
• Marching Squares (2D) and Cubes (3D)
• Placing vertices on grid edges
– Dual methods
• Dual Contouring (2D,3D)
• Placing vertices in grid cells
CSE554
Contouring II
Primal
Dual
Slide 2
Efficiency
• Iso-contours is very often used for visualizing 3D volumes
– The volume data can be large (e.g, 1000^3)
• MRI, CT, Ultrasound, EM, etc.
– The user often needs to view surfaces as she changes iso-values
• An efficient contouring algorithm is needed
– Optimized for viewing one volume at multiple iso-values
CSE554
Contouring II
Slide 3
Marching Squares - Revisited
• Active cell
– A grid cell where {min, max} of 4 corner
1
2
3
2
1
2
3
4
3
2
3
4
5
4
3
2
3
4
3
2
1
2
3
2
1
values encloses the iso-value
• Algorithm
O(n)
– Visit each cell.
O(k)
– If active, create vertices and edges
• Time complexity: O(n+k)
• n: the number of all grid cells
• k: the number of active cells
CSE554
Contouring II
Iso-value = 3.5
Slide 4
Marching Squares - Revisited
Marching Squares
O(n+k)
1.2
1.0
Running
time
(seconds)
0.8
0.6
0.4
Only visiting each square and
checking if it is active (without
creating vertices and edges)
O(n)
0.2
0
CSE554
50
100
150
Contouring II
200
250
Iso-value
Slide 5
Speeding Up Contouring
• Data structures that allow faster query of active cells
– Quadtrees (2D), Octrees (3D)
• Hierarchical spatial structures for quickly pruning large areas of inactive cells
• Complexity: O(k*Log(n))
– Interval trees
• An optimal data structure for range finding
• Complexity: O(k+Log(n))
CSE554
Contouring II
Slide 6
Interval Trees
Marching Squares
O(n+k)
1.2
1.0
Running
time
(seconds)
0.8
Quadtree
O(k*Log(n))
0.6
Interval tree
O(k+Log(n))
0.4
0.2
0
CSE554
50
100
150
Contouring II
200
250
Iso-value
Slide 7
Speeding Up Contouring
• Data structures that allow faster query of active cells
– Quadtrees (2D), Octrees (3D)
• Hierarchical spatial structures for quickly pruning large areas of inactive cells
• Complexity: O(k*Log(n))
– Interval trees
• An optimal data structure for range finding
• Complexity: O(k+Log(n))
CSE554
Contouring II
Slide 8
Quadtrees (2D)
• Basic idea: coarse-to-fine search
– Start with the entire grid:
• If the {min, max} of all grid values does not enclose the iso-value, stop.
• Otherwise, divide the grid into four sub-grids and repeat the check within each
sub-grid. If the sub-grid is a unit cell, it’s an active cell.
CSE554
Contouring II
Slide 9
Quadtrees (2D)
• Basic idea: coarse-to-fine search
– Start with the entire grid:
• If the {min, max} of all grid values does not enclose the iso-value, stop.
• Otherwise, divide the grid into four sub-grids and repeat the check within each
sub-grid. If the sub-grid is a unit cell, it’s an active cell.
Iso-value not in {min,max}
Iso-value in {min,max}
CSE554
Contouring II
Slide 10
Quadtrees (2D)
• Basic idea: coarse-to-fine search
– Start with the entire grid:
• If the {min, max} of all grid values does not enclose the iso-value, stop.
• Otherwise, divide the grid into four sub-grids and repeat the check within each
sub-grid. If the sub-grid is a unit cell, it’s an active cell.
Iso-value not in {min,max}
Iso-value in {min,max}
CSE554
Contouring II
Slide 11
Quadtrees (2D)
• Basic idea: coarse-to-fine search
– Start with the entire grid:
• If the {min, max} of all grid values does not enclose the iso-value, stop.
• Otherwise, divide the grid into four sub-grids and repeat the check within each
sub-grid. If the sub-grid is a unit cell, it’s an active cell.
Iso-value not in {min,max}
Iso-value in {min,max}
CSE554
Contouring II
Slide 12
Quadtrees (2D)
• Basic idea: coarse-to-fine search
– Start with the entire grid:
• If the {min, max} of all grid values does not enclose the iso-value, stop.
• Otherwise, divide the grid into four sub-grids and repeat the check within each
sub-grid. If the sub-grid is a unit cell, it’s an active cell.
Iso-value not in {min,max}
Iso-value in {min,max}
CSE554
Contouring II
Slide 13
Quadtrees (2D)
• Basic idea: coarse-to-fine search
– Start with the entire grid:
• If the {min, max} of all grid values does not enclose the iso-value, stop.
• Otherwise, divide the grid into four sub-grids and repeat the check within each
sub-grid. If the sub-grid is a unit cell, it’s an active cell.
Iso-value not in {min,max}
Iso-value in {min,max}
CSE554
Contouring II
Slide 14
Quadtrees (2D)
• A degree-4 tree
– Root node: entire grid
– Each node maintains:
• {min, max} in the enclosed part of the image
• (in a non-leaf node) 4 children nodes for the 4 quadrants
Root node {1,5}
Level-1 nodes
(leaves)
CSE554
{1,3}
{2,4}
{2,4}
Quadtree
Contouring II
1
2
3
2
3
4
3
4
5
{3,5}
Grid
Slide 15
Quadtrees (2D)
• Tree building: bottom-up
Root
node
{1,5}
– Each grid cell becomes a leaf node
– Assign a parent node to every group of 4 nodes
• Compute the {min, max} of the parent node from
those of the children nodes
{1,3}
{2,4}
{2,4}
{3,5}
Leaf
nodes
• Padding dummy leaf nodes (e.g., {-∞,-∞}) if the
dimension of grid is not power of 2
CSE554
Contouring II
1
2
3
2
3
4
3
4
5
Grid
Slide 16
Quadtrees (2D)
• Tree building: a recursive algorithm
// A recursive function to build a single quadtree node
// for a sub-grid at corner (lowX, lowY) and with length len
buildNode (lowX, lowY, len)
1. If (lowX, lowY) is out of range: Return a leaf node with {-∞,-∞}
2. If len = 1: Return a leaf node with {min, max} of corner values
3. Else
1. c1 = buildNode (lowX, lowY, len/2)
2. c2 = buildNode (lowX + len/2, lowY, len/2)
3. c3 = buildNode (lowX, lowY + len/2, len/2)
4. c4 = buildNode (lowX + len/2, lowY + len/2, len/2)
5. Return a node with children {c1,…,c4} and {min, max} of all
{min, max} of these children
// Building a quadtree for a grid whose longest dimension is len
Return buildNode (1, 1, 2^Ceiling[Log[2,len]])
CSE554
Contouring II
Slide 17
Quadtrees (2D)
• Tree building: bottom-up
Root
node
{1,5}
– Each grid cell becomes a leaf node
– Assign a parent node to every group of 4 nodes
• Compute the {min, max} of the parent node from
those of the children nodes
{1,3}
{2,4}
{2,4}
{3,5}
Leaf
nodes
• Padding background leaf nodes (e.g., {-∞,-∞}) if the
dimension of grid is not power of 2
– Complexity: O(n)
• Total number of nodes in the tree is < 2n
1
2
3
2
3
4
3
4
5
• But we only need to do this once (after that, the
tree can be used to speed up contouring at any isovalue)
CSE554
Contouring II
Grid
Slide 18
Quadtrees (2D)
• Contouring with a quadtree: top-down
– Starting from the root node
Root
node
{1,5}
iso-value
= 2.5
– If {min, max} of the node encloses the iso-value
• If the node is not a leaf, search within each of its
children
{1,3}
{2,4}
{2,4}
{3,5}
Leaf
nodes
• If the node is a leaf, contour in that grid cell
CSE554
Contouring II
1
2
3
2
3
4
3
4
5
Grid
Slide 19
Quadtrees (2D)
• Contouring with a quadtree: a recursive algorithm
// A recursive function to contour in a quadtree node
// for a sub-grid at corner (lowX, lowY) and with length len
contourNode (node, iso, lowX, lowY, len)
1. If iso is within {min, max} of node
1. If len = 1: do Marching Squares in this grid square
2. Else (let the 4 children be c1,…,c4)
1. contourNode (c1, iso, lowX, lowY, len/2)
2. contourNode (c2, iso, lowX + len/2, lowY, len/2)
3. contourNode (c3, iso, lowX, lowY + len/2, len/2)
4. contourNode (c4, iso, lowX + len/2, lowY + len/2, len/2)
// Contouring using a quadtree whose root node is Root
// for a grid whose longest dimension is len
contourNode (Root, iso, 1, 1, 2^Ceiling[Log[2,len]])
CSE554
Contouring II
Slide 20
Quadtrees (2D)
• Contouring with a quadtree: top-down
– Starting from the root node
Root
node
{1,5}
iso-value
= 2.5
– If {min, max} of the node encloses the iso-value
• If the node is an intermediate node, search
within each of its children nodes
{1,3}
{2,4}
{2,4}
{3,5}
Leaf
nodes
• If the node is a leaf, output contour in that grid
square
– Complexity: (at most) O(k*Log(n))
• Much faster than O(k+n) (Marching Squares) if
1
2
3
2
3
4
3
4
5
k<<n
• But not efficient when k is large (can be as slow
Grid
as O(n))
CSE554
Contouring II
Slide 21
Quadtrees (2D)
Marching Squares
O(n+k)
1.2
1.0
Running
time
(seconds)
0.8
0.6
Quadtree
O(k*Log(n))
0.4
0.2
0
CSE554
50
100
150
Contouring II
200
250
Iso-value
Slide 22
Quadtrees (2D): Summary
• Algorithm
– Preprocessing: building the quad tree
• Independent of iso-values
– Contouring: traversing the quad tree
– Both are recursive algorithms
• Time complexity
– Tree building: O(n)
• Slow, but one-time only
– Contouring: O(k*Log(n))
CSE554
Contouring II
Slide 23
Octrees (3D): Overview
• Algorithm: similar to quadtrees
– Preprocessing: building the octree
• Each non-leaf node has 8 children nodes, one for each octant of grid
– Contouring: traversing the octree
– Both are recursive algorithms
• Time complexity: same as quadtrees
– Tree building: O(n)
• Slow, but one-time only
– Contouring: O(k*Log(n))
CSE554
Contouring II
Slide 24
Speeding Up Contouring
• Data structures that allow faster query of active cells
– Quadtrees (2D), Octrees (3D)
• Hierarchical spatial structures for quickly pruning large areas of inactive cells
• Complexity: O(k*Log(n))
– Interval trees
• An optimal data structure for range finding
• Complexity: O(k+Log(n))
CSE554
Contouring II
Slide 25
Interval Trees
• Basic idea
– Each grid cell occupies an interval of values {min, max}
• An active cell’s interval intersects the iso-value
– Stores all intervals in a search tree for efficient intersection queries
• Minimizes the “path” from root to all leaves intersecting any given iso-value
0
255
Iso-value
CSE554
Contouring II
Slide 26
Interval Trees
• A binary tree
– Root node: all intervals in the grid
– Each node maintains:
• δ: Median of end values of all intervals (used to split the children intervals)
• (in a non-leaf node) Two children nodes
– Left child: intervals strictly lower than δ
– Right child: intervals strictly higher than δ
• Two sorted lists of intervals intersecting δ
– Left list (AL): ascending order of min-end of each interval
– Right list (DR): descending order of max-end of each interval
CSE554
Contouring II
Slide 27
Interval Trees
AL: d,e,f,g,h,i
DR: i,e,g,h,d,f
AL: a,b,c
DR: c,a,b
Interval tree:
δ=7
δ=4
AL: j,k,l
DR: l,j,k
δ=10
AL: m
DR: m
δ=12
Intervals:
CSE554
Contouring II
Slide 28
Interval Trees
• Intersection queries: top-down
– Starting with the root node
• If the iso-value is smaller than δ
– Scan through AL: output all intervals whose min-end is smaller than iso-value.
– Go to the left child.
• If the iso-value is larger than δ
– Scan through DR: output all intervals whose max-end is larger than iso-value.
– Go to the right child.
• If iso-value equals δ
– Output AL (or DR).
CSE554
Contouring II
Slide 29
Interval Trees
AL: d,e,f,g,h,i
DR: i,e,g,h,d,f
AL: a,b,c
DR: c,a,b
Interval tree:
δ=7
δ=4
iso-value = 9
AL: j,k,l
DR: l,j,k
δ=10
AL: m
DR: m
δ=12
Intervals:
CSE554
Contouring II
Slide 30
Interval Trees
AL: d,e,f,g,h,i
DR: i,e,g,h,d,f
AL: a,b,c
DR: c,a,b
Interval tree:
δ=7
δ=4
iso-value = 9
AL: j,k,l
DR: l,j,k
δ=10
AL: m
DR: m
δ=12
Intervals:
CSE554
Contouring II
Slide 31
Interval Trees
AL: d,e,f,g,h,i
DR: i,e,g,h,d,f
AL: a,b,c
DR: c,a,b
Interval tree:
δ=7
δ=4
iso-value = 9
AL: j,k,l
DR: l,j,k
δ=10
AL: m
DR: m
δ=12
Intervals:
CSE554
Contouring II
Slide 32
Interval Trees
• Intersection queries: top-down
– Starting with the root node
• If the iso-value is smaller than δ
– Scan through AL: output all intervals whose min-end is smaller than iso-value.
– Go to the left child.
• If the iso-value is larger than δ
– Scan through DR: output all intervals whose max-end is larger than iso-value.
– Go to the right child.
• If iso-value equals δ
– Output AL (or DR).
– Complexity: O(k + Log(n))
• k: number of intersecting intervals (active cells)
• Much faster than O(k+n) (Marching squares/cubes)
CSE554
Contouring II
Slide 33
Interval Trees
• Tree building: top-down
– Starting with the root node (which includes all intervals)
– To create a node from a set of intervals,
• Find δ (the median of all ends of the intervals).
• Sort all intervals intersecting with δ into the AL, DR
• Construct the left (right) child from intervals strictly below (above) δ
– A recursive algorithm
CSE554
Contouring II
Slide 34
Interval Trees
Interval tree:
Intervals:
CSE554
Contouring II
Slide 35
Interval Trees
AL: d,e,f,g,h,i
DR: i,e,g,h,d,f
δ=7
Interval tree:
Intervals:
CSE554
Contouring II
Slide 36
Interval Trees
AL: d,e,f,g,h,i
DR: i,e,g,h,d,f
AL: a,b,c
DR: c,a,b
Interval tree:
δ=7
δ=4
Intervals:
CSE554
Contouring II
Slide 37
Interval Trees
AL: d,e,f,g,h,i
DR: i,e,g,h,d,f
AL: a,b,c
DR: c,a,b
Interval tree:
δ=7
δ=4
AL: j,k,l
DR: l,j,k
δ=10
Intervals:
CSE554
Contouring II
Slide 38
Interval Trees
AL: d,e,f,g,h,i
DR: i,e,g,h,d,f
AL: a,b,c
DR: c,a,b
Interval tree:
δ=7
δ=4
AL: j,k,l
DR: l,j,k
δ=10
AL: m
DR: m
δ=12
Intervals:
CSE554
Contouring II
Slide 39
Interval Trees
• Tree building: top-down
– Starting with the root node (which includes all intervals)
– To create a node from a set of intervals,
• Find δ (the median of all ends of the intervals).
• Sort all intervals intersecting with δ into the AL, DR
• Construct the left (right) child from intervals strictly below (above) δ
– A recursive algorithm
– Complexity: O(n*Log(n))
• A linear sweep at each level of the tree
• Depth of the tree is Log(n) (as a result of using the median to split)
• Again, this is one-time only 
CSE554
Contouring II
Slide 40
Interval Trees
Marching Squares
O(n+k)
1.2
1.0
Running
time
(seconds)
0.8
Quadtree
O(k*Log(n))
0.6
Interval tree
O(k+Log(n))
0.4
0.2
0
CSE554
50
100
150
Contouring II
200
250
Iso-value
Slide 41
Interval Trees: Summary
• Algorithm
– Preprocessing: building the interval tree
• Independent of iso-values
– Contouring: traversing the interval tree
– Both are recursive algorithms
• Tree-building and traversing are same in 2D and 3D
• Time complexity
– Tree building: O(n*log(n))
• Slow, but one-time
– Contouring: O(k+log(n))
CSE554
Contouring II
Slide 42
Further Readings
• Quadtree/Octrees:
– “Octrees for Faster Isosurface Generation”, Wilhelms and van Gelder (1992)
• Interval trees:
– “Dynamic Data Structures for Orthogonal Intersection Queries”, by Edelsbrunner
(1980)
– “Speeding Up Isosurface Extraction Using Interval Trees”, by Cignoni et al. (1997)
CSE554
Contouring II
Slide 43
Further Readings
• Other acceleration techniques:
– “Fast Iso-contouring for Improved
Interactivity”, by Bajaj et al. (1996)
• Growing connected component of active
cells from pre-computed seed locations
– “View Dependent Isosurface Extraction”,
Livnat and Hansen
by Livnat and Hansen (1998)
• Culling invisible mesh parts
– “Interactive View-Dependent Rendering
Of Large Isosurfaces”, by Gregorski et al.
(2002)
• Level-of-detail: decreasing mesh
resolution based on distance from the
viewer
CSE554
Contouring II
Gregorski et al.
Slide 44