Efficient Contouring Methods in Engineering

washington university in st louis school n.w
1 / 44
Embed
Share

Washington University in St. Louis, School of Engineering and Applied Science explores contouring methods for efficiently visualizing iso-contours in 2D and 3D spaces. The lecture covers primal and dual methods, including Marching Squares and Cubes, discussing algorithms for quick extraction of iso-values in large datasets. Efficient data structures like quadtrees and octrees are introduced for faster query of active cells, optimizing contouring processes for real-time visualization in medical imaging.

  • Contouring Methods
  • Iso-contours
  • Efficient Visualization
  • Engineering
  • Data Structures
rayaanacharya
cel_eri Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Washington University in St. Louis, School of Engineering and Applied Science CSE 554 Lecture 5: Contouring (faster) Fall 2016 CSE554 Contouring II Slide 1

  2. Washington University in St. Louis, School of Engineering and Applied Science Review Iso-contours Points where a function evaluates to be a given 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) Primal Dual Placing vertices in grid cells CSE554 Contouring II Slide 2

  3. Washington University in St. Louis, School of Engineering and Applied Science Efficiency Iso-contours are often used for visualizing (3D) medical images The data can be large (e.g, 512^3) The user often wants to change iso-values and see the result in real-time An efficient contouring algorithm is needed Optimized for viewing one volume at multiple iso-values CSE554 Contouring II Slide 3

  4. Washington University in St. Louis, School of Engineering and Applied Science Marching Squares - Revisited Active cell/edge 1 2 3 2 1 A grid cell/edge where {min, max} of its corner/end values encloses the iso- value Algorithm 2 3 4 3 2 3 4 5 4 3 Visit each cell. O(n) 2 3 4 3 2 If active, create vertices on active edges and connect them by lines Time complexity? O(k) 1 2 3 2 1 O(n+k) Iso-value = 3.5 n: the number of all grid cells k: the number of active cells CSE554 Contouring II Slide 4

  5. Washington University in St. Louis, School of Engineering and Applied Science Marching Squares - Revisited Marching Squares O(n+k) 1.2 1.2 1.0 1.0 Running time (seconds) 0.8 0.8 0.6 0.6 0.4 0.4 Only visiting each square and checking if it is active (without creating vertices and edges) O(n) 0.2 0.2 Iso-value 0 0 50 50 100 100 150 150 200 200 250 250 CSE554 Contouring II Slide 5

  6. Washington University in St. Louis, School of Engineering and Applied Science 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/k)) Interval trees An optimal data structure for range finding Complexity: O(k+Log(n)) CSE554 Contouring II Slide 6

  7. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees Marching Squares O(k+n) 1.2 1.0 Running time (seconds) 0.8 Quadtree O(k*Log(n/k)) 0.6 Interval tree O(k+Log(n)) 0.4 0.2 Iso-value 0 50 100 150 200 250 CSE554 Contouring II Slide 7

  8. Washington University in St. Louis, School of Engineering and Applied Science 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

  9. Washington University in St. Louis, School of Engineering and Applied Science 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

  10. Washington University in St. Louis, School of Engineering and Applied Science 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

  11. Washington University in St. Louis, School of Engineering and Applied Science 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

  12. Washington University in St. Louis, School of Engineering and Applied Science 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

  13. Washington University in St. Louis, School of Engineering and Applied Science 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

  14. Washington University in St. Louis, School of Engineering and Applied Science 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

  15. Washington University in St. Louis, School of Engineering and Applied Science Quadtrees (2D) A degree-4 tree Root node represents the entire image Each node represents a square part of the image: {min, max} in the square (in a non-leaf node) one child node for each quadrant of the square {1,5} 1 2 3 Root node 2 3 4 Grid {1,3} {2,4} {2,4} {3,5} Level-1 nodes (leaves) Quadtree 3 4 5 CSE554 Contouring II Slide 15

  16. Washington University in St. Louis, School of Engineering and Applied Science 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 {min, max} of the children nodes {1,3} {2,4} Leaf nodes Padding dummy leaf nodes (e.g., { , }) if the dimension of grid is not power of 2 {2,4} {3,5} 1 2 3 2 3 4 Grid 3 4 5 CSE554 Contouring II Slide 16

  17. Washington University in St. Louis, School of Engineering and Applied Science 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 buildSubTree (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 = buildSubTree (lowX, lowY, len/2) 2. c2 = buildSubTree (lowX + len/2, lowY, len/2) 3. c3 = buildSubTree (lowX, lowY + len/2, len/2) 4. c4 = buildSubTree (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 buildSubTree (1, 1, 2^Ceiling[Log[2,len]]) CSE554 Contouring II Slide 17

  18. Washington University in St. Louis, School of Engineering and Applied Science Quadtrees (2D) Tree-building: time complexity? O(n) Pre-computation We only need to do this once (after that, the tree can be used to speed up contouring at any iso-value) CSE554 Contouring II Slide 18

  19. Washington University in St. Louis, School of Engineering and Applied Science Quadtrees (2D) Contouring with a quadtree: top-down Root node {1,5} iso-value = 2.5 Starting from the root node If {min, max} of the node encloses the iso-value If it is not a leaf, continue onto its children {1,3} {2,4} If the node is a leaf, contour in that grid cell Leaf nodes {2,4} {3,5} 1 2 3 2 3 4 Grid 3 4 5 CSE554 Contouring II Slide 19

  20. Washington University in St. Louis, School of Engineering and Applied Science 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 ctSubTree (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. ctSubTree (c1, iso, lowX, lowY, len/2) 2. ctSubTree (c2, iso, lowX + len/2, lowY, len/2) 3. ctSubTree (c3, iso, lowX, lowY + len/2, len/2) 4. ctSubTree (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 ctSubTree (Root, iso, 1, 1, 2^Ceiling[Log[2,len]]) CSE554 Contouring II Slide 20

  21. Washington University in St. Louis, School of Engineering and Applied Science Quadtrees (2D) Contouring with a quadtree: time complexity? O(k*Log(n/k)) Faster than O(k+n) (Marching Squares) if k<<n But not efficient when k is large (can be as slow as O(n)) CSE554 Contouring II Slide 21

  22. Washington University in St. Louis, School of Engineering and Applied Science Quadtrees (2D) Marching Squares O(n+k) 1.2 1.0 Running time (seconds) 0.8 0.6 Quadtree O(k*Log(n/k)) 0.4 0.2 Iso-value 0 50 100 150 200 250 CSE554 Contouring II Slide 22

  23. Washington University in St. Louis, School of Engineering and Applied Science Quadtrees (2D): Summary Preprocessing: building the tree bottom-up Independent of iso-values Contouring: traversing the tree top-down For a specific iso-value Both are recursive algorithms CSE554 Contouring II Slide 23

  24. Washington University in St. Louis, School of Engineering and Applied Science Octrees (3D) Each tree node has 8 children nodes Similar algorithms and same complexity as quadtrees CSE554 Contouring II Slide 24

  25. Washington University in St. Louis, School of Engineering and Applied Science 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/k)) Interval trees An optimal data structure for range finding Complexity: O(k+Log(n)) CSE554 Contouring II Slide 25

  26. Washington University in St. Louis, School of Engineering and Applied Science 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 0 255 Iso-value CSE554 Contouring II Slide 26

  27. Washington University in St. Louis, School of Engineering and Applied Science 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 child nodes Left child: intervals < Right child: intervals > 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

  28. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees AL: d,e,f,g,h,i DR: i,e,g,h,d,f AL: a,b,c DR: c,a,b AL: j,k,l DR: l,j,k =7 AL: m DR: m =12 Interval tree: =4 =10 Intervals: CSE554 Contouring II Slide 28

  29. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees Intersection queries: top-down Starting with the root node If the iso-value is smaller than median Scan through AL: output all intervals whose min-end <= iso-value. Go to the left child. If the iso-value is larger than Scan through DR: output all intervals whose max-end >= iso-value. Go to the right child. If iso-value equals Output AL (or DR). CSE554 Contouring II Slide 29

  30. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees AL: d,e,f,g,h,i DR: i,e,g,h,d,f iso-value = 9 AL: a,b,c DR: c,a,b AL: j,k,l DR: l,j,k =7 AL: m DR: m =12 Interval tree: =4 =10 Intervals: CSE554 Contouring II Slide 30

  31. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees AL: d,e,f,g,h,i DR: i,e,g,h,d,f iso-value = 9 AL: a,b,c DR: c,a,b AL: j,k,l DR: l,j,k =7 AL: m DR: m =12 Interval tree: =4 =10 Intervals: CSE554 Contouring II Slide 31

  32. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees AL: d,e,f,g,h,i DR: i,e,g,h,d,f iso-value = 9 AL: a,b,c DR: c,a,b AL: j,k,l DR: l,j,k =7 AL: m DR: m =12 Interval tree: =4 =10 Intervals: CSE554 Contouring II Slide 32

  33. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees Intersection queries: time complexity? O(k + Log(n)) Much faster than O(k+n) (Marching squares/cubes) CSE554 Contouring II Slide 33

  34. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees Marching Squares O(n+k) 1.2 1.0 Running time (seconds) 0.8 Quadtree O(k*Log(n/k)) 0.6 Interval tree O(k+Log(n)) 0.4 0.2 Iso-value 0 50 100 150 200 250 CSE554 Contouring II Slide 34

  35. Washington University in St. Louis, School of Engineering and Applied Science 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 35

  36. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees Interval tree: Intervals: CSE554 Contouring II Slide 36

  37. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees AL: d,e,f,g,h,i DR: i,e,g,h,d,f =7 Interval tree: Intervals: CSE554 Contouring II Slide 37

  38. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees AL: d,e,f,g,h,i DR: i,e,g,h,d,f AL: a,b,c DR: c,a,b =7 Interval tree: =4 Intervals: CSE554 Contouring II Slide 38

  39. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees AL: d,e,f,g,h,i DR: i,e,g,h,d,f AL: a,b,c DR: c,a,b AL: j,k,l DR: l,j,k =7 Interval tree: =4 =10 Intervals: CSE554 Contouring II Slide 39

  40. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees AL: d,e,f,g,h,i DR: i,e,g,h,d,f AL: a,b,c DR: c,a,b AL: j,k,l DR: l,j,k =7 AL: m DR: m =12 Interval tree: =4 =10 Intervals: CSE554 Contouring II Slide 40

  41. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees Tree building: time complexity? O(n*Log(n)) O(n) at each level of the tree (after pre-sorting all intervals in O(n*Log(n))) Depth of the tree is O(Log(n)) CSE554 Contouring II Slide 41

  42. Washington University in St. Louis, School of Engineering and Applied Science Interval Trees: Summary Preprocessing: building the tree top-down Independent of iso-values Contouring: traversing the tree top-down For a specific iso-value Both are recursive algorithms CSE554 Contouring II Slide 42

  43. Washington University in St. Louis, School of Engineering and Applied Science 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

  44. Washington University in St. Louis, School of Engineering and Applied Science 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 , by Livnat and Hansen (1998) Livnat and Hansen 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 Gregorski et al. CSE554 Contouring II Slide 44

Related


Best Laser Hair Removal Treatment in Don Valley Village

Best Laser Hair Removal Treatment in Don Valley Village

Olivia2
Which Type of Liposuction is Best for You - High Definition Liposuction

Which Type of Liposuction is Best for You - High Definition Liposuction

highdefinition
A comprehensive guide on VASER LIPOSURATION - moein surgical Arts

A comprehensive guide on VASER LIPOSURATION - moein surgical Arts

moeinsurgicalarts
Introducing the Dugard Eagle 850 CNC Machining Center

Introducing the Dugard Eagle 850 CNC Machining Center

Mudar
Dr. Smiley: Premier Cosmetic Surgeon in Beverly Hills

Dr. Smiley: Premier Cosmetic Surgeon in Beverly Hills

Dr8
One of the Best facility for Anti Wrinkle Injections in Merry Hill

One of the Best facility for Anti Wrinkle Injections in Merry Hill

Parker1
Dr. Smiley | The Premier Choice for Liposuction in Beverly Hills

Dr. Smiley | The Premier Choice for Liposuction in Beverly Hills

Dr8
Dr. Smiley _ The Premier Choice for Liposuction in Beverly Hills

Dr. Smiley _ The Premier Choice for Liposuction in Beverly Hills

Dr8
Best Botox treatment in Middleton Grange

Best Botox treatment in Middleton Grange

Jack3
Smooth Skin Studios, LLC

Smooth Skin Studios, LLC

Cathleen
Investigation of Potato Slices in Various NaCl Solutions

Investigation of Potato Slices in Various NaCl Solutions

abush
Comprehensive Proposal Template for Advanced Bridal Makeup Training

Comprehensive Proposal Template for Advanced Bridal Makeup Training

cor_fol
Best Make Up Services in Blackbutt

Best Make Up Services in Blackbutt

Jack3
Wood Therapy Massage NJ: Sculpt, Tone, and Relax

Wood Therapy Massage NJ: Sculpt, Tone, and Relax

Zen1
Volift Fillers In Dubai

Volift Fillers In Dubai

Iqra1
Best Anti-wrinkle treatments in Darling Point

Best Anti-wrinkle treatments in Darling Point

Jack3
Best Facials in Temple Hill

Best Facials in Temple Hill

jack4
Best Skin Needling treatment in Boolaroo

Best Skin Needling treatment in Boolaroo

Jack3

More Related Content