Key Points of AlgorithmMedial AxisAlgorithm in 2D2D Theoretical ResultsExtension to 3DRaw CrustNormal FilteringManifold Extraction (Trimming)Heuristic for sharp edges• A New Voronoi-Based Surface Reconstruction AlgorithmNina Amenta, Marshall Bern & Manolis Kamvysselis• Surface Reconstruction by Voronoi FilteringNina Amenta & Marshall BernScannerVoronoifilteringSmooth closedmanifoldPoints + noiseTriangular piecewiselinear approximationof surfaceKey Points of Algorithm• Assumes smooth curve/surface without boundary• Uses Delaunay triangulation• Result exactly interpolates sample points• Use medial axis to define “good” sample and to derive theoretical results• If sample is “good”, theory guarantees• Allows nonuniform sampling1) convergence to original surface in positions and normals2) result is topologically correctRelated Workα – Shapes (Edelsbrunner et al)• Assigns a polyhedral shape to a point cloud S.• Complement of the union of all spheres of radius α not containing S.•α must be chosen experimentally.• No globally suitable value of α may exist.• Voronoi filtering produces an inherently 2d “crust”. ComparisonZero-Set Algorithms (Hoppe et al)• Define a signed distance function on ℜ3• Polygonalize zero-set using marching cubes• Produces an approximating mesh• Zero-set algorithm is faster, but crust is easier to implement• Approximating rather than interpolating• Low-pass filtering• Sampling criterion and normal estimation ideas may be applicable to zero-set algorithms too Comparison+ve-veMedial AxisMedial axis of a (d-1) dimensional surface F in ℜdis the set of pointswith more than one closest point in F.In ℜ2medial axis is a curve. In ℜ3 medial axis is a surface.Local Feature Size of a point p on F (LFS(p)) is the minimumdistance of p to the medial axis.S is called an r-sample of F if every p in F has a sample withina distance r∗LFS(p),r<1.Intuitively, a sample is “good” if the sampling density is inverselyproportional to the distance from the medial axis.r∗LFS(p)··LFS(p)p sUsing the medial axis accounts for both curvature plus proximityto other parts of the surface.κ is highIf medial axis touches the surface, theory states that we need infinitely dense sampling for convergence. .κ is low.In 2D, the vertices of the Voronoi diagram of a dense sampleapproximate the medial axis. In 3D, this is not true. Need to use the “poles” of the Voronoi cells.Algorithm in 2DInput - Set of sample points S in ℜ2.Output - Set of edges connecting points in S.1. Compute Voronoi vertices V of S2. Calculate Delaunay of V ∪ S3. Pick edges (p,q) where both p,q in S -- “Crust”Voronoi “filtering”: adding Voronoi vertices filters out unwanted edges2D Theoretical ResultsTheorem 1:Given the crust of an r-sample S from a smooth curve F,r ≤ .40 => crust includes all edges between pairs of sample pointsr ≤ .25 => exactly Theoretical guarantee that we have an accurate polylinereconstruction of F if the sample set fulfills this criteria.Extension to 3D• Not straight forward 2D extension. 5 theorems.• Voronoi cell vertices don’t necessarily lie near medial axis- use 2 Voronoi poles not all Voronoi vertices • Need two post processing steps on “raw crust”- Normal filtering- Manifold extractionTheoretical results in 3DTheorem 2:If S is an r-sample of F for r ≤ .1, then good trianglesform a polyhedron homeomorphic to F.Theorem 3:If S is an r-sample of F for r ≤ .1, the crust includes all good triangles.Theorem 4:If S is an r-sample of F for r ≤ .06, the crust lies within a fattened surface by placing a ball of radius 5r∗LFS(q) around each q in F.Guarantees that the raw crust contains a triangular mesh (the good triangles) that is topologically equivalent to F.The crust can be brought arbitrarily close to the surface as r gets smaller. Does not guarantee raw crust is a manifold or converges in surface normals.Theorem 5:Assume S is an r-sample and set θ = 4r. Let T be a triangle of the θ crust, where the θ crust is obtained after normal trimmingand let t be any position on T. The angle between the normal of T and the normal of F at the point p in F closest to t = O( ) radians...rtpnpntGuarantees that after the normal filtering phase, the trimmedconverges in the surface normal. acos (np·nt)= O( )rFTTheorem 6:Assume S is an r-sample and set θ = 4r. After the θ crust has been trimmed by the manifold extraction step, the trimmed crust is homeomorphic to F. Guarantees we have a manifold that is topologically equivalent to the surface.Raw Crust• Not all Voronoi vertices are close to medial axis.• Only use “poles” -- 2 Voronoi vertices farthest from s on oppositeends of F.p+ - Farthest vertex of cell from sp- - Farthest vertex of cell such that sp-·sp+<0• Compute Voronoi diagram of S.• Find all poles P.• Compute Delaunay triangulation of S ∪ P.• Extract triangles for which all 3 vertices are in S to get the “raw”crust.• So far we have only guaranteed pointwise convergence.• Triangle normals may be off (small triangles normal to the surface).• Surface may not be a manifold (flat tetrahedron).• Two more steps required: Normal Filtering and Manifold Extraction.Normal Filtering• Lemma states that n+ = sp+and n-= sp-are nearly orthogonal to thesurface at S.• Throw away triangles whose normals are too different from n+or n-.• For each vertex in a triangle, inspect the angle between the trianglenormal and the vector to p+and the vertex.• Throw away triangle if largest angle vertex > θother vertex angles > 3θ/2• θ is connected to r. Since r is unknown, requires experimentation.• Normal filtering is dangerous around boundaries & sharp edges since n+and n-are not normal to all tangent planes and good triangles can be filtered out.• Perhaps n+,n-can be used as an estimate of tangent plane for zero-set methods.Manifold Extraction (Trimming)• Remaining triangles are roughly parallel to the surface but somemay be oriented incorrectly. For example, a sliver.• Two steps:- Orient all triangles consistently- Remove triangles on sharp edges• Triangle orientation- Pick an s on convexhull (S)-Call p+outside, p-inside- Pick a triangle incident to s and orient its pole to agree- Continue via breadth first search• Sharp edges- A sharp edge is an edge where two successive incident