Report

1 Automatic mesh-healing technique for model repair and finite element model generation BASED ON PAPER BY C.S. CHONG, A. SENTHIL KUMAR, H.P. LEE PRESENTED BY NURIT MOSCOVICI Good Polygonal Models 2 What is a good model? Equilateral triangles Valence close to 6 Equal edge lengths Feature preservation Used for? 3D printing Finite Element Analysis … Link: DGP lecture 9 Problems in Polygonal Models Holes Gaps T-Joints Overlaps 3 Slivers This Paper Black-box algorithm: automatic* model repair and mesh generation Work on a triangle-meshed version of the model Original geometric model is not repaired Fix mesh so it is watertight Reconstruct mesh to get good quality 4 This Paper 5 Previous Work Directly healing geometry Edge merging [Steinbrenner et al.2001] Stitching using geometric hashing [Barequet 1997] Spatial partitioning [Murali et al. 1997] User-controlled tools [Petersen et al. 2001] [Morvan et al. 1996] Focus on specific elements Zipping small gaps [Sheng and Meier 1995] Healing slivers [Chew 1997] Healing slivers using Delaunay [Edelsbrunner 2000] 6 Important terms 7 Triangle Mesh Elements Nodes Edges Inner Edge Inner Node Free Node Free Edge/ Boundary Edge Element General description of algorithm Initial imperfect model Create initial triangular mesh Search for free edges Mesh healing Identify and heal small gaps and overlaps Identify and heal t-joints Surface reconstruction Identify and heal large gaps/holes Healed mesh model 8 Creating the Initial Mesh Initial imperfect model Create initial triangular mesh 9 Search for free edges Mesh healing Identify and heal small gaps and overlaps Identify and heal t-joints Surface reconstruction Identify and heal large gaps/holes Healed mesh model Creating the Initial Mesh 10 Create mesh by triangulating given model Paving algorithm Create mesh nodes along model boundaries Element edge length defined by user Create triangular elements that conform to mesh nodes http://mathworld.wolfram.com/Triangulation.html http://www.cs.cmu.edu/~quake/triangle.delaunay.html Search for Free Edges Initial imperfect model Create initial triangular mesh 11 Search for free edges Mesh healing Identify and heal small gaps and overlaps Identify and heal t-joints Surface reconstruction Identify and heal large gaps/holes Healed mesh model Healing Small Gaps and Overlaps Initial imperfect model Create initial triangular mesh Search for free edges Mesh healing Identify and heal small gaps and overlaps Identify and heal t-joints Surface reconstruction Identify and heal large gaps/holes Healed mesh model 12 Small Gaps and Overlaps 13 In this paper gaps are defined as an accidental space between two surfaces that should be connected Usually occur because of numerical and translational errors Gaps Overlaps Small Gaps and Overlaps Detection General idea: check proximity between two candidate surface edges Traditionally detected by checking proximity between two element edges Can be difficult if edges are different sizes In this article: check proximity between nodes 14 Nodal Merging Algorithm Node Pair: a pair of free nodes within a user specified tolerance distance Node-pair exists in model? yes Determine location of merged node Collapse both nodes to determined location no Continue to T-Joint healing 15 Determine New Node Location Calculate line intersection between tangential planes at the two nodes. Distance between nodes and line larger than tolerance distance: Location is at midpoint Else: Project both points onto this line Location is at midpoint on line 16 Healing T-Joints Initial imperfect model Create initial triangular mesh 17 Search for free edges Mesh healing Identify and heal small gaps and overlaps Identify and heal t-joints Surface reconstruction Identify and heal large gaps/holes Healed mesh model T-Joints An area in the mesh where the node of one or more elements intersects the edge of another. 18 Modeling error or large truncation error during translation In this article: also an area where a free node is within a small distance from a free edge T-Joints T-Joint detection Still checking proximity between two candidate surface edges Find free edge with a free node within tolerance distance. Edge-node pair 19 T-Joint Stitching Algorithm Node-pair exists in model? Yes Return to nodal merging algorithm No Go to hole-healing algorithm No Edge-pair exists in model? Yes T-Joint found: Nodal Insertion and element splitting 20 Stitching Project free node onto free edge in edge-node pair Create new node at this location Split element belonging to free edge at new node location Merge free node with new node 21 Stitching example 22 Healing Holes Initial imperfect model 23 Create initial triangular mesh Search for free edges Mesh healing Identify and heal small gaps and overlaps Identify and heal t-joints Surface reconstruction Identify and heal large gaps/holes Healed mesh model Types of Holes Simple hole: a single loop of free edges Can be any shape Ring hole: a hole consisting of at least two peripheral loops Holes with “islands” 24 Hole Filling Algorithm For every closed loop of free edges (simple hole), fill hole with triangle elements: Calculate the minimum angle between two adjacent free edges in loop 3 options: 75 75 135 135 25 Option 1: 75 Form triangle using these two free elements. 26 Option 2: 75 135 Create two equilateral triangles using free edges Calculate normal of new triangles to decide on plane neightbor elem ents n N ode 27 ni n1 i 1 neightbor elem ents n2 n nA 2 n nB 2 n1 n2 Option 2: 75 135 Find average location between two new nodes Merge to a single node at this location. Check if any node is within tolerance distance of the new node and merge if found. 28 Option 3: 1 3 5 Create two equilateral triangles using free edges. Calculate normal of new triangles to decide on plane No nodal merging 29 Ring holes Interactively identify ring holes Connect islands to the main loop with a bridge line Bridge line converted to triangle elements during meshing Leaving us with only simple holes 30 If this isn’t done the islands will eventually be discarded Consistent model, worse fidelity. A word about values Why 75 and 135? Good meshes are as close as possible to equilateral triangles (60 degrees) 31 The author decided 75 degrees is tolerable Why? They don’t say If angle is between 75 and 135 degrees you can split into triangles with an angle between 37.5 and 75 If angle is too small it will be handled in next stage Reconstructing Surface Elements Initial imperfect model Create initial triangular mesh Search for free edges Mesh healing Identify and heal small gaps and overlaps Identify and heal t-joints Surface reconstruction Identify and heal large gaps/holes Healed mesh model 32 Slivers 33 Often generated during t-joint and hole healing Long and slender Ratio of surface area/perimeter is small Bad for numerical solution. Slivers Reconstruction options 34 Nodal Merging Edge Flipping Feature Edges 35 Feature Edge: edge that is likely part of shape definition and should be kept. Identified by Smoothness Angle: angle along the edge of a skewed triangle Smoothness Angle Link: DGP lecture 9 Automatic mesh repair thesis Agnes Larsson Shape Factor Value indicating skewedness of a triangle 36 Way to determine if triangle should be fixed Based on equilateral factor 2 Equilateral factor: 2 E j m ax E 3 3 j 1 Shape factor: f 3 2 3 E 2 2 Where j are the angles of a given triangle Reconstruction algorithm User input: shortest edge length Element with edge shorter than the tolerance will be fixed User input: tolerance factor Element with shape factor lower than the tolerance will be fixed In the paper, 0.7 Smoothness angle: default 135o If angle < 135o consider as feature edge If angle > 135o consider as planar 37 Reconstruction algorithm When to invoke nodal merging: Low shape factor and edge shorter than edge length One of the edges is a feature edge No feature edge 38 Reconstruction algorithm When to invoke edge flipping: Low shape factor and no short edges Take smoothness angle into account Edge A is not a feature edge Edge A is a feature edge 39 Results Handles many different input formats Divergence from original model bounded by mesh element size 40 Results 41 Future Work Find non-heuristic tolerance values Should be connected to size of edges Do more during remeshing to ensure optimal mesh Find a way to deal with open loops, missing surfaces, complex holes, etc. Not mentioned: large overlaps, intersections, bad normals 42 Later Work Repairing and meshing imperfect shapes with Delaunay refinement [Busaryev, Dey, Levine 2009] Handles small errors Output: good quality Delaunay mesh Weighted Delaunay triangulation Merge gaps using original boundary data, instead of merging nodes from new mesh Sealing Faceted Surfaces to Achieve Watertight CAD Models[Smith, Tautges, Wilson 2010] Use original CAD face data to fill holes more accurately Can heal non-manifold models 43 Later Work: Surveys 44 Polygon Mesh Repairing: An Application Perspective [Attene et al., 2013] Surface based reconstructions are suitable when there are few errors, and are generally not very robust. Volumetric solutions are more robust. No common strategy for handling self intersections. Existing solutions are tailored to specific problems. No automatic way of dealing with ring holes. Fixing Geometric Errors on Polygonal Models: A Survey [Ju, 2009] Surface based reconstructions better for preserving small details of the model Less robust, and can be very time consuming when large holes/gaps must be filled. Questions? 45