Topological surface detector

Abstract

A method of identifying surfaces within a discretized mesh model is provided. The method comprises identifying a number of faces in the mesh model and constructing an adjacency graph of connections between the faces. A value is assigned to each connection in the adjacency graph according to a metric of similarity between incident faces of the connection. Connections with a metric of similarity value that satisfies a prescribed policy of elimination are removed from the adjacency graph. From the remaining connections in the adjacency graph a number of strongly connected components in the mesh model are determined.

What is claimed is: 
     
       1. A computer-implement method of identifying surfaces within a discretized mesh model, the method comprising:
 identifying, by a number of processors, a number of faces in the mesh model; 
 constructing, by the number of processors, an adjacency graph of connections between the faces; 
 assigning, by the number of processors, a value to each connection in the adjacency graph according to a metric of similarity between incident faces of the connection; 
 removing from the adjacency graph, by the number of processors, connections with a metric of similarity value that satisfies a prescribed policy of elimination; 
 determining, by the number of processors, a number of strongly connected components in the mesh model from remaining connections in the adjacency graph; 
 constructing a temporary incident map; 
 mapping each undirected edge of each face to the temporary incident map; 
 for each undirected edge of a face, determining if other faces share the undirected edge; 
 if another face shares the undirected edge, mapping the undirected edge to the other face in the temporary incident map; and 
 discarding the temporary incident map after all edges of all faces in the mesh model have been iterated. 
 
     
     
       2. The method of  claim 1 , wherein the adjacency graph comprises a number of nodes and a number of edges connecting the nodes, wherein each node represents a face in the mesh model and each edge presents a geometric edge shared by faces in the mesh model. 
     
     
       3. The method of  claim 1 , wherein assigning the value of the metric of similarity to a connection in the adjacency graph comprises:
 mapping a unique normal vector for each incident face of the connection; and 
 calculating an angle subtended by the normal vectors, wherein the connection is removed from the adjacency graph if the angle is greater than a specified threshold. 
 
     
     
       4. The method of  claim 1 , wherein assigning the value of the metric of similarity to a connection in the adjacency graph comprises:
 mapping a unique normal vector for each incident face of the connection; and 
 calculating a scalar product of the normal vectors, wherein the connection is removed from the adjacency graph if the scalar product is below a specified threshold. 
 
     
     
       5. The method of  claim 1 , wherein the metric of similarity between the incident faces of a connection is derived from at least one of:
 normal vectors mapped to the faces; 
 number of vertices; 
 number of edges; 
 surface curvature of originating geometry; 
 area; 
 thickness; 
 material composition; 
 isotropic material type; 
 orthotropic material type; 
 material axis system; 
 Young's modulus; 
 shear modulus; or 
 Poisson ratio. 
 
     
     
       6. The method of  claim 1 , wherein the strongly connected component are identified according to a linear algorithm. 
     
     
       7. The method of  claim 6 , wherein the linear algorithm is Kosaraju's algorithm. 
     
     
       8. The method of  claim 1 , wherein surfaces are identified in the mesh model according to relative geometric similarity irrespective of any predefined axis system. 
     
     
       9. The method of  claim 1 , further comprising displaying, by the number of processors, geometric surfaces detected in the mesh model according to the strongly connected components. 
     
     
       10. A system for identifying surfaces within a discretized mesh model, the system comprising:
 a bus system; 
 a storage device connected to the bus system, wherein the storage device stores program instructions; and 
 a number of processors connected to the bus system, wherein the number of processors execute the program instructions to: 
 identify a number of faces in the mesh model; 
 construct an adjacency graph of connections between the faces; 
 assign a value to each connection in the adjacency graph according to a metric of similarity between incident faces of the connection; 
 remove from the adjacency graph connections with a metric of similarity value that satisfies a prescribed policy of elimination; 
 determine a number of strongly connected components in the mesh model from remaining connections in the adjacency graph; 
 construct a temporary incident map; 
 map each undirected edge of each face to the temporary incident map; 
 for each undirected edge of a face, determine if other faces share the undirected 
 if another face shares the undirected edge, map the undirected edge to the other face in the temporary incident map; and 
 discard the temporary incident map after all edges of all faces in the mesh model have been iterated. 
 
     
     
       11. The system of  claim 10 , wherein the adjacency graph comprises a number of nodes and a number of edges connecting the nodes, wherein each node represents a face in the mesh model and each edge presents a geometric edge shared by faces in the mesh model. 
     
     
       12. The system of  claim 10 , wherein assigning the value of the metric of similarity to a connection in the adjacency graph comprises the processors executing instructions to:
 map a unique normal vector for each incident face of the connection; and 
 calculate an angle subtended by the normal vectors, wherein the connection is removed from the adjacency graph if the angle is greater than a specified threshold. 
 
     
     
       13. The system of  claim 10 , wherein assigning the value of the metric of similarity to a connection in the adjacency graph comprises the processors executing instructions to:
 map a unique normal vector for each incident face of the connection; and 
 calculate a scalar product of the normal vectors, wherein the connection is removed from the adjacency graph if the scalar product is below a specified threshold. 
 
     
     
       14. The system of  claim 10 , wherein the metric of similarity between the incident faces of a connection is derived from at least one of:
 normal vectors mapped to the faces; 
 number of vertices; 
 number of edges; 
 surface curvature of originating geometry; 
 area; 
 thickness; 
 material composition; 
 isotropic material type; 
 orthotropic material type; 
 material axis system; 
 Young's modulus; 
 shear modulus; or 
 Poisson ratio. 
 
     
     
       15. The system of  claim 10 , wherein the strongly connected component are identified according to a linear algorithm. 
     
     
       16. The system of  claim 15 , wherein the linear algorithm is Kosaraju's algorithm. 
     
     
       17. The system of  claim 10 , wherein surfaces are identified in the mesh model according to relative geometric similarity irrespective of any predefined axis system. 
     
     
       18. The system of  claim 10 , wherein the processors further execute instructions to display geometric surfaces detected in the mesh model according to the strongly connected components. 
     
     
       19. A computer program product for identifying surfaces within a discretized mesh model, the computer program product comprising:
 a non-transient computer readable storage medium having program instructions embodied therewith, the program instructions executable by a number of processors to cause a number of computers to perform the steps of: 
 identifying a number of faces in the mesh model; 
 constructing an adjacency graph of connections between the faces; 
 assigning a value to each connection in the adjacency graph according to a metric of similarity between incident faces of the connection; 
 removing from the adjacency graph connections with a metric of similarity value that satisfies a prescribed policy of elimination; 
 determining a number of strongly connected components in the mesh model from remaining connections in the adjacency graph; 
 constructing an empty adjacency graph; 
 iterating through all faces in the mesh model; 
 iterating through all edges of each face; and 
 if an edge of a face is shared by another face, adding the edge to the adjacency graph as a connection; 
 constructing a temporary incident map; 
 mapping each undirected edge of each face to the temporary incident map; 
 for each undirected edge of a face, determining if other faces share the undirected 
 if another face shares the undirected edge, mapping the undirected edge to the other face in the temporary incident map; and 
 discarding the temporary incident map after all edges of all faces in the mesh model have been iterated. 
 
     
     
       20. The computer program product of  claim 19 , wherein the adjacency graph comprises a number of nodes and a number of edges connecting the nodes, wherein each node represents a face in the mesh model and each edge presents a geometric edge shared by faces in the mesh model. 
     
     
       21. The computer program product of  claim 19 , wherein assigning the value of the metric of similarity to a connection in the adjacency graph comprises instructions for:
 mapping a unique normal vector for each incident face of the connection; and 
 calculating an angle subtended by the normal vectors, wherein the connection is removed from the adjacency graph if the angle is greater than a specified threshold. 
 
     
     
       22. The computer program product of  claim 19 , wherein assigning the value of the metric of similarity to a connection in the adjacency graph comprises instructions for:
 mapping a unique normal vector for each incident face of the connection; and 
 calculating a scalar product of the normal vectors, wherein the connection is removed from the adjacency graph if the scalar product is below a specified threshold. 
 
     
     
       23. The computer program product of  claim 19 , wherein the metric of similarity between the incident faces of a connection is derived from at least one of:
 normal vectors mapped to the faces; 
 number of vertices; 
 number of edges; 
 surface curvature of originating geometry; 
 area; 
 thickness; 
 material composition; 
 isotropic material type; 
 orthotropic material type; 
 material axis system; 
 Young's modulus; 
 shear modulus; or 
 Poisson ratio. 
 
     
     
       24. The computer program product of  claim 19 , wherein the strongly connected component are identified according to a linear algorithm. 
     
     
       25. The computer program product of  claim 24 , wherein the linear algorithm is Kosaraju's algorithm. 
     
     
       26. The computer program product of  claim 19 , wherein surfaces are identified in the mesh model according to relative geometric similarity irrespective of any predefined axis system. 
     
     
       27. The computer program product of  claim 19 , further comprising instructions for displaying geometric surfaces detected in the mesh model according to the strongly connected components.