Advanced Iso-Surfacing AlgorithmsIso-contour/surface ExtractionsIso-contour (0)Iso-contour (1)Iso-contour (2)Iso-contouring – Step 1Iso-contouring – Step 2Iso-contouring – Step 3Inside or Outside?Iso-surface ExtractionDivide and ConquerHow many cases?Case Reduction (1)Case Reduction (2)Iso-surface CasesMarching Cubes AlgorithmMarching Cubes (2)Marching Cubes (3)Why is it called marching cubes?Iso-surface cell searchIso-surface CellsEfficient iso-surface cell searchEfficient search methodsDomain searchRange Search (1)Range Search (2)Range Search (3)Range Search: Span SpaceSpan SpaceSpan Space Search (1)NOISE Algorithm (K-d tree)NOISE Algorithm (Query)Span Space Search (2)Range Search: Interval TreeInterval TreeRange Search MethodsContour PropagationChallengesSolutionsExtrema Graph (1)Extrema Graph (2)Extrema Graph (3)Extrema Graph (4)We are not done yet …Extrema Graph (5)Extrema Graph (6)Extrema GraphAmbiguity ProblemThe ProblemTo fix it …SolutionsAsymptotic DeciderAsymptotic Decider (2)Asymptotic Decider (3)Asymptotic Decider (4)Asymptotic Decider (5)Asymptotic Decider (6)Advanced Iso-Surfacing AlgorithmsJian Huang, CS594, Spring 2002This set of slides are developed and used by Prof. Han-Wei Shen at Ohio State University.Iso-contour/surface Extractions2D Iso-contour3D Iso-surfaceIso-contour (0)Remember bi-linear interpolationp2p3p0p1P =?p4p5To know the value of P, we can first compute p4 andP5 and then linearly interpolatePIso-contour (1)Consider a simple case: one cell data setThe problem of extracting an iso-contour is an inverse of value interpolation. That is: p2p3p0p1Given f(p0)=v0, f(p1)=v1, f(p2)=v2, f(p3)=v3Find the point(s) P within the cell that have values F(p) = CIso-contour (2)p2p3p0p1We can solve the problem based on linear interpolation (1) Identify edges that contain points P that have value f(P) = C(2) Calculate the positions of P(3) Connect the points with linesIso-contouring – Step 1 (1) Identify edges that contain points P that have value f(P) = Cv1 v2If v1 < C < v2 then the edge contains such a pointIso-contouring – Step 2 (2) Calculate the position of P Use linear interpolation: P = P1 + (C-v1)/(v2-v1) * (P2 – P1)v1 v2Pp1p2CIso-contouring – Step 3p2p3p0p1 Connect the points with line(s)Based on the principle of linear variation, all the points on the line have values equal CInside or Outside? Just a naming convention1. If a value is smaller than the iso-value, we call it “Inside”2. If a value is greater than the iso-value, we call it “Outside”p2p3p0p1- + outside cellp2p3p0p1- inside cellExtend the same divide-and-conquer algorithm to three dimension• 3D cells• Look at one cell at a time • Let’s only focus on voxel Iso-surface ExtractionDivide and Conquer_++++___++++____(2 triangles)How many cases?Now we have 8 verticesSo it is: 2 = 2568How many unique topological cases?Case Reduction (1)Value Symmetry++_ _____++__++++Case Reduction (2)Rotation Symmetry++_ _______++____By inspection, we can reduce 256 14Iso-surface CasesTotal number of cases: 14 + 3Marching Cubes AlgorithmA Divide-and-Conquer Algorithmv1v2v3v4v5v6v7v8 Vi is ‘1’ or ‘0’ (one bit) 1: > C; 0: <C (C= iso-value)Each cell has an index mapped to a value ranged [0,255]Index = v8 v7 v6 v5 v4 v3 v2 v1Marching Cubes (2)Given the index for each cell, a table lookup is performedto identify the edges that has intersections with the iso-surface 012314e1, e3, e5…Index intersection edgese1e2e3e4e5e6e7e8e9 e10e11e12Marching Cubes (3)++++____• Perform linear interpolations at the edges to calculate the intersection points• Connect the pointsWhy is it called marching cubes?Linear search through cells •Row by row, layer by layer•Reuse the interpolated points for adjacent cells•Iso-surface cells: cells that contain iso-surface. min < iso-value < max •Marching cubes algorithm performs a linear search to locate the iso-surface cells – not very efficient for large-scale data sets. Iso-surface cell searchIso-surface Cells•For a given iso-value, only a smaller portion of cells are iso-surface cell. •For a volume with n x n x n cells, the average number of the iso-surface cells is O(n x n) (ratio of surface v.s. volume)nnnEfficient iso-surface cell search•Problem statement: Given a scalar field with N cells, c1, c2, …, cn, with min-max ranges (a1,b1), (a2,b2), …, (an, bn) Find {Ck | ak < C < bk; C=iso-value}Efficient search methods 1. Spatial subdivision (domain search)2. Value subdivision (range search) 3. Contour propagationDomain search •Subdivide the space into several sub-domains, check the min/max values for each sub-domain•If the min/max values (extreme values) do not contain the iso-value, we skip the entire regionMin/max Complexity = O(Klog(n/k))Range Search (1) Subdivide the cells based on their min/max ranges Global minimum Global maximumIsovalueHierarchically subdivide the cells based on their min/max rangesRange Search (2)Within each subinterval, there are more than one cellsTo further improve the search speed, we sort them. Sort by what ? Min and Max values MaxMinM5 M2 M6 M4 M1 M3 M7 M8 M11 M10 M9m5 m1 m6 m3 m8 m7 m2 m9 m11 m4 m10G1G2Isosurface cells = G1 G2Range Search (3)?A clean range subdivision is difficult …Difficult to get an optimal speedRange Search: Span SpaceSpan Space: Instead of treating each cell as a range, we can treat it as a 2D point at (min, max)This space consists of min and max axes is called span space Any problem here?Span SpaceminmaxWhat are the iso-surface cells?CHow to search them?Span Space Search (1)With the point representation, subdividing the space ismuch easier now. Search method 1: K-D tree subdivision (NOISE algorithm)K-d tree: • A multi-dimensional version of binary tree• Partition the data by alternating between each each of the dimensions at each level of the treeNOISE Algorithm (K-d tree)leftrightupdown… … …Construction minmax * One node per cellMinMax?Median pointNOISE Algorithm (Query)Complexity = O( N + k) leftrightupdown… … …MinMax?Median pointIf ( iso-value < root.min )• check the ?? Sub-tree If (iso-value > root.min) • Check the ?? Sub-tree • Don’t forget to check the root‘s interval as well.Span Space Search (2) Search Method (2): ISSUE, discretized span space O(log(N/L))O(log(N/L))O(1)?Complexity = ?Range Search:
View Full Document
Unlocking...