Advanced Iso Surfacing Algorithms Jian Huang CS594 Spring 2002 This set of slides are developed and used by Prof Han Wei Shen at Ohio State University Iso contour surface Extractions 2D Iso contour 3D Iso surface Iso contour 0 Remember bi linear interpolation p2 p3 P p4 p0 p5 p1 To know the value of P we can first compute p4 and P5 and then linearly interpolate P Iso contour 1 Consider a simple case one cell data set The problem of extracting an iso contour is an inverse of value interpolation That is p2 p3 Given f p0 v0 f p1 v1 f p2 v2 f p3 v3 Find the point s P within the cell that have values F p C p0 p1 Iso contour 2 We can solve the problem based on linear interpolation p2 p3 1 Identify edges that contain points P that have value f P C 2 Calculate the positions of P p0 p1 3 Connect the points with lines Iso contouring Step 1 1 Identify edges that contain points P that have value f P C If v1 C v2 then the edge contains such a point v1 v2 Iso contouring Step 2 2 Calculate the position of P p1 P p2 v1 C v2 Use linear interpolation P P1 C v1 v2 v1 P2 P1 Iso contouring Step 3 p2 p0 p3 p1 Connect the points with line s Based on the principle of linear variation all the points on the line have values equal C Inside or Outside Just a naming convention 1 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 p2 p3 p0 p1 outside cell p2 p3 p0 p1 inside cell Iso surface Extraction Extend the same divide and conquer algorithm to three dimension 3D cells Look at one cell at a time Let s only focus on voxel Divide and Conquer 2 triangles How many cases Now we have 8 vertices So it is 2 8 256 How many unique topological cases Case Reduction 1 Value Symmetry Case Reduction 2 Rotation Symmetry By inspection we can reduce 256 14 Iso surface Cases Total number of cases 14 3 Marching Cubes Algorithm A Divide and Conquer Algorithm v8 v4 v6 Each cell has an index mapped to a value ranged 0 255 v3 v5 v1 v7 Vi is 1 or 0 one bit 1 C 0 C C iso value v2 Index v8 v7 v6 v5 v4 v3 v2 v1 Marching Cubes 2 Given the index for each cell a table lookup is performed to identify the edges that has intersections with the iso surface Index intersection edges 0 e7 e11 e8 e3 e4 e9 e12 e6 e5 e2 1 2 3 e10 e1 14 e1 e3 e5 Marching Cubes 3 Perform linear interpolations at the edges to calculate the intersection points Connect the points Why is it called marching cubes Linear search through cells Row by row layer by layer Reuse the interpolated points for adjacent cells Iso surface cell search Iso surface cells cells that contain isosurface 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 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 n average number of the iso surface cells is O n x n ratio of surface v s volume n n Efficient iso surface cell search Problem statement Given a scalar field with N cells c 1 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 propagation Domain 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 region Min max Complexity O Klog n k Range Search 1 Subdivide the cells based on their min max ranges Global minimum Isovalue Global maximum Hierarchically subdivide the cells based on their min max ranges Range Search 2 Within each subinterval there are more than one cells To further improve the search speed we sort them Sort by what Min and Max values G1 MaxM5 M2 M6 M4 M1 M3 M7 M8 M11 M10 M9 G2 Minm5 m1 m6 m3 m8 m7 m2 m9 m11 m4 m10 Isosurface cells G1 G2 Range Search 3 A clean range subdivision is difficult Difficult to get an optimal speed Range Search Span Space Span 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 Space What are the iso surface cells max How to search them C min Span Space Search 1 With the point representation subdividing the space is much 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 tree NOISE Algorithm K d tree Median point Min Construction left right Max max up down One node per cell min NOISE Algorithm Query Median point Min left right Max up down Complexity O N k If 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 1 Complexity O log N L Range Search Interval Tree Interval Tree I I left I right Sort all the data points x1 x2 x3 x4 xn Let x mid point n 2 We use to divide the cells into three sets I I left and I right I cells that have I left cells that have I right cells that have min max max min Interval Tree Now given an isovalue C 1 I 2 3 I left I cells that have I left cells that have I right cells that have If C If C If C I right Complexity O log n k min max max min Optimal Range Search Methods In general range search methods all are super fast two orders of magnitude faster than the marching cubes algorithm in terms of cell search But they all suffer a common problem Excessive extra memory requirement Contour Propagation Basic Idea Given an initial cell that contains iso surface the remainder of the iso surface can be found by propagation Initial cell A C E A B D Enqueue B C FIFO Queue A BC Dequeue B C Enqueue D CD Breadth First Search Challenges Need to know the initial cells For any given iso value C finding the initial cells to start the propagation …
View Full Document
Unlocking...