Method for reconstructing the topology of a polygonal soup
AssigneeFord Global Technologies, LLC
InventorsPietro Buttolo, Paul Joseph Stewart
Life of this patent
Estimating the term…
Abstract
A method for automatically reconstructing topographical information for a given mesh, altering the mesh by introducing, deleting, or splitting existing polygons when needed. An OctTree space decomposition is used to achieve a log2-complexity search method to find the closest vertex in the polygonal soup to a given point in space. Linear complexities are used to find triangles connected to a given vertex and all triangles connected to a given triangle. The triangles are split to enforce conductivity.
Claims11
A computer-implemented method for reconstructing topological information for a mesh for use in interactive simulation with complex vehicle models, said mesh comprising a polygonal soup of triangles with sides and vertices, said method comprising the steps of:
- building vertex and edge connectivity data;
- finding duplicates of vertices;
- removing said duplicates of vertices;
- splitting at least one triangle into at least two new elements;
- and
- realigning strips of triangles without common vertices.
A computer-implemented method for fixing holes in topological information for a mesh for use with interactive simulations, said mesh comprising a polygonal soup of triangles with sides and vertices, said method comprising the steps of:
- building vertex and edge connectivity data;
- finding duplicates of vertices;
- removing said duplicates of vertices;
- splitting at least one triangle into at least two new elements;
- and
- realigning strips of triangles without common vertices.
A computer-implemented method for fixing holes in topological information for a mesh for use with interactive simulations, said mesh comprising a polygonal soup of triangles with sides and vertices, said method comprising the steps of:
- (a) building vertex and edge connectivity data comprising:
- generating a representative index;
- creating a vertex-neighbor table;
- and
- building an edge-neighbor table;
- (b) finding duplicates of vertices;
- (c) removing said duplicates of vertices comprising:
- searching for unconnected sides of triangles;
- searching for duplicates of the vertices at the ends of said unconnected sides;
- replacing all duplicate vertices with original vertices;
- adding triangles connected to the duplicate vertices to said original vertices;
- and
- rebuilding said edge-neighbor table for all triangles connected said original vertices, and
- (d) realigning strips of triangles without common vertices.
Dependencies are inferred from the claim text.