OverviewMotivationWhat does the paper do?Consistent MeshesTopological SimplificationRelated WorkReconstruction via Implicit SurfacesReconstruction via Implicit SurfacesReconstruction via Implicit SurfacesReconstruction via Implicit SurfacesReconstruction via Implicit SurfacesReconstruction via Implicit SurfacesWhat is this paper about?UtilityUtilityUtilityImplicit Surface Fitting for Polygon SoupLeast-SquaresLeast-SquaresLeast-SquaresMoving Least-SquaresMoving Least-SquaresApplication...Weighting FunctionPolygonal ConstraintsPolygonal ConstraintsPolygonal ConstraintsApplication...Normal ConstraintsNormal ConstraintsApplication...Computational AspectsComputing IntegralsComputing IntegralsComplexity ProblemHierarchical ApproximationExtensionsTight Bounding VolumesTight Bounding VolumesPreprocessingResultsExampleSharp FeaturesBounding VolumesContinuous SimplificationTimingsConclusionsConclusionsInterpolating and Approximating Implicit Surfaces from Polygon SoupChen Shen, James F. O’Brien,Jonathan R. ShewchukUniversity of California, BerkeleyGeometric Algorithms SeminarCS 468 – Fall 20052CS 468 – Geometric Algorithms Seminar – Fall 2005OverviewOverviewTalk Overview:•Motivation• Implicit Surface Fittingfor Polygon Soup• Computational Aspects• Extensions•ResultsTalk Overview:• Motivation• Implicit Surface Fittingfor Polygon Soup• Computational Aspects• Extensions• Results3MotivationMotivation4CS 468 – Geometric Algorithms Seminar – Fall 2005What does the paper do?What does the paper do?Goal: Convert polygon mesh into implicit surface(and back again)Applications:• Mesh cleanup – create consistent meshesfrom polygon soup• Topological simplification• Creating bounding volumesGoal: Convert polygon mesh into implicit surface(and back again)Applications:• Mesh cleanup – create consistent meshesfrom polygon soup• Topological simplification• Creating bounding volumes5CS 468 – Geometric Algorithms Seminar – Fall 2005Consistent MeshesConsistent MeshesPolygon models often show consistency issues:• Holes and gaps (no closed surface)• T-junctions in meshing• Non-manifold structure,self intersections• Inconsistent normals• Sometimes: Internal structureshould be omittedPolygon models often show consistency issues:• Holes and gaps (no closed surface)• T-junctions in meshing• Non-manifold structure,self intersections• Inconsistent normals• Sometimes: Internal structureshould be omitted}– preprocessing}– partially fixed}– fixed6CS 468 – Geometric Algorithms Seminar – Fall 2005Topological SimplificationTopological Simplification[Shen et al. 04]Create simplified bounding volume, allowing topological changes:Useful for...•Mesh simplification• Spatial queries (e.g. collision detection)Create simplified bounding volume, allowing topological changes:Useful for...• Mesh simplification• Spatial queries (e.g. collision detection)7CS 468 – Geometric Algorithms Seminar – Fall 2005Related WorkRelated WorkReconstruction via Implicit Surfaces:• Standard technique: see e.g. [Hoppe et al. ’92],[Turk et al. ’99], [Carr et al. ’01], [Turk et al. ’02], ...• General reconstruction procedure:• Estimate normals• Approx. signed distance function• Apply marching cubes• (Possibly: Simplify result)Reconstruction via Implicit Surfaces:• Standard technique: see e.g. [Hoppe et al. ’92],[Turk et al. ’99], [Carr et al. ’01], [Turk et al. ’02], ...• General reconstruction procedure:• Estimate normals• Approx. signed distance function• Apply marching cubes• (Possibly: Simplify result)This paper8CS 468 – Geometric Algorithms Seminar – Fall 2005Reconstruction via Implicit SurfacesReconstruction via Implicit SurfacesInitial dataEstimate normalsSigned distance func.Marching cubesFinal meshInitial dataEstimate normalsSigned distance func.Marching cubesFinal mesh9CS 468 – Geometric Algorithms Seminar – Fall 2005Reconstruction via Implicit SurfacesReconstruction via Implicit SurfacesInitial dataEstimate normalsSigned distance func.Marching cubesFinal meshInitial dataEstimate normalsSigned distance func.Marching cubesFinal mesh10CS 468 – Geometric Algorithms Seminar – Fall 2005Reconstruction via Implicit SurfacesReconstruction via Implicit SurfacesInitial dataEstimate normalsSigned distance func.Marching cubesFinal meshInitial dataEstimate normalsSigned distance func.Marching cubesFinal mesh11CS 468 – Geometric Algorithms Seminar – Fall 2005Reconstruction via Implicit SurfacesReconstruction via Implicit SurfacesInitial dataEstimate normalsSigned distance func.Marching cubesFinal meshThis paper: technique for polygon meshesInitial dataEstimate normalsSigned distance func.Marching cubesFinal meshThis paper: technique for polygon meshes12CS 468 – Geometric Algorithms Seminar – Fall 2005Reconstruction via Implicit SurfacesReconstruction via Implicit SurfacesInitial dataEstimate normalsSigned distance func.Marching cubesFinal meshInitial dataEstimate normalsSigned distance func.Marching cubesFinal mesh13CS 468 – Geometric Algorithms Seminar – Fall 2005Reconstruction via Implicit SurfacesReconstruction via Implicit SurfacesInitial dataEstimate normalsSigned distance func.Marching cubesFinal meshInitial dataEstimate normalsSigned distance func.Marching cubesFinal mesh14CS 468 – Geometric Algorithms Seminar – Fall 2005What is this paper about?What is this paper about?thisstepIn this paper:Defining theimplicitfunctionBut:Considerpolygon modelsinput: polygons15CS 468 – Geometric Algorithms Seminar – Fall 2005UtilityUtilityHole Filling: Create well-defined closed surfaceHole Filling: Create well-defined closed surface16CS 468 – Geometric Algorithms Seminar – Fall 2005UtilityUtilityAlso: Remeshing (Marching Cubes)T-vertex, small holefixed: remeshed17CS 468 – Geometric Algorithms Seminar – Fall 2005UtilityUtilityMissing Normals: Reconstruct (a few) missing normalsMissing Normals: Reconstruct (a few) missing normals???18Implicit Surface Fitting for Polygon SoupImplicit Surface Fitting for Polygon Soup19CS 468 – Geometric Algorithms Seminar – Fall 2005Least-SquaresLeast-SquaresLeast Squares Approximation:target valuesbasis functionsB1B2B3pi= (xi, φi)w(x)weighting functions least squares fit20CS 468 – Geometric Algorithms Seminar – Fall 2005Least-SquaresLeast-SquaresLeast Squares Approximation:)()(~1xBcxinii∑==φBest Fit:()∑=−niiiiixwxc12)()(~argminφφ21CS 468 –