System and method for rapidly generating an optimal mesh model of a 3D object or surface

• US 5,945,996 A
• Filed: 10/16/1996
• Issued: 08/31/1999
• Est. Priority Date: 10/16/1996
• Status: Expired due to Term

• Current Assignee: Sizmek Technologies Inc (Sizmek, Inc.)
• Original Assignee: Real-Time Geometry Corporation
• Inventors: Lebedev, Alexei, Migdal, Alexander
• Primary Examiner(s): Feild, Joseph H.
• Assistant Examiner(s): Kindred, Alford W.
• Application Number:
  US08/730,980
• Time in Patent Office: 1,049 Days
• Field of Search: 345/420, 345/423, 345/419, 345/433, 345/425, 364/488, 364/474.24
• US Class Current: 345/420
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A system and method for the rapid creation of a mesh model depicting a real world object, terrain or other three-dimensional surface. The system inserts points into the mesh incrementally, building the mesh point by point. Before incremental building, the system orders the points so that each next point is a near neighbor to the previously inserted point. This ordering procedure optimizes mesh construction by guaranteeing a minimal time for locating the area on the mesh into which the next point will be inserted. The present invention also provides a system and method to ensure an optimal quality of mesh at any level of insertion or deletion, following systematized checking function to maintain quality such as that required in Delaunay triangulation. The system and method can also incorporate a history file to store data concerning the results of the checking to substantially reduce processing time in mesh regeneration applications.

Claims

1. A computer-based system for generation of an optimized mesh model of a three-dimensional object or surface, the computer, including a processor coupled to a memory and program elements, adapted to accept as input a plurality of data points, with each data point being a coordinate describing the object or surface to be modeled, and construct a mesh to model the object or surface, the system comprising:

(a) a data point detail element to order the plurality of data points into a sequence from first point to last point for insertion into the mesh model and storing the sequence of data points in an ordered list, the data point detail element ordering the plurality of data points such that each of the data points in the ordered list is a near neighbor to a next data point in the ordered list;

(b) a mesh model construction element to construct a mesh following the ordered list, the mesh comprising a plurality of faces, with each face being a geometric shape with a predetermined number of vertices, the face vertices being ones of the data points from the ordered list, the boundary connection between any two adjacent vertices of a face comprising an edge of the face, with a face being connected to another adjacent face in the mesh through a shared edge and shared vertices creating that shared edge, the mesh model construction element constructing the mesh by creating an initial mesh with the mesh model comprising of a plurality of faces;

(c) an optimality checking element to determine whether the construction of newly created faces as a result of construction, meets a predetermined optimality criteria and to redefine in a sequenced order the boundaries of the newly created faces when one of the newly created faces does not meet the predetermined optimality criteria; and

(d) the optimality checking element further comprised to place an indication on a history list in sequence for each check or redefinition made for a particular face.

2. The system of claim 1, wherein the mesh construction element inserts data points starting from the first point of the ordered list and continues building the mesh with each succeeding point in sequence until the last point of the ordered list and the list is followed using a pointer.

3. The system of claim 1 where the optimality criteria is the Delaunay principle of optimality for an irregular triangulated mesh.

4. The system of claim 1 further comprising a mesh regeneration element where the mesh construction element inserts data points starting from the first point of the insert list and continues building the mesh with each succeeding point in sequence until last point of the ordered list and then regenerates the following the sequence of indications on the history list.

5. A computer-based system for generation of an optimized mesh model of a three-dimensional object or surface, the computer, including a processor coupled to a memory and program elements adapted to accept as input a plurality of data points, with each data point being a coordinate describing the object or surface to be modeled, and construct a mesh to model the object or surface, the system comprising:

(a) a data point ordering element to order the plurality of data points by subdividing the plurality of data points into partitions and continuing to subdivide until each partition contains a single data point and listing the data points in a sequence corresponding to the subdividing to create an ordered list where each point in the list is a near neighbor to the next point in the ordered list;

(b) a mesh model construction element to construct a mesh comprising at least one face using a subset of the plurality of data points, the mesh comprising a plurality of faces with each face being a geometric shape with a predetermined number of vertices, the face vertices being ones of the subset of data points, the boundary connection between any two adjacent vertices of a face comprising an edge of the face, with a face being connected to another adjacent, neighboring face in the mesh through a shared edge and shared vertices creating that shared edge;

(c) the mesh model construction element further adapted to further construct the mesh by inserting data points and making those insertions in a sequence following the ordered list, the mesh model construction selecting a data point from the ordered list for further building the mesh;

(d) a location element to identify the mesh face which is closest in distance to the data point from the ordered list;

(e) the mesh construction element to further construct the mesh by inserting the data point into the face identified by the location element, by rearranging the vertices of the face and including the data point for insertion to create a set of new faces with the data point for insertion being shared in each new face, the new faces being connected to other faces in the mesh through vertices and edges as were previously established in the insertion face, the processor establishing neighbor relationships for each new face and the point insertion element further adapted to advance the pointer to the next data point in the ordered list;

(f) an optimality checking element to check one of the newly created faces to determine whether its construction meets a predetermined optimality criteria, the checking procedure checking the new face and the neighbor face opposite the newly inserted data point to evaluate its vertex and edge configuration for optimality and reconfiguring the face being checked and the neighbor to redefine their boundaries when the newly created face does not meet the predetermined optimality procedure;

(g) a optimality checking element further comprised to place an indication of either a successful check or the rearrangement on a history list for this check;

(h) the optimality checking element further configured to check the all the newly created faces in a rotational direction moving from the location of the first checked face;

(i) a optimality checking element further comprised to place an indication of either a successful check or the rearrangement on a history list in succession as each subsequent check is executed; and

(j) a mesh regeneration element further comprised to construct the complete mesh inserting all point following the sequence of the ordered list and checking to add indications to the history list, and thereafter regenerating the mesh using only the ordered list to insert points and the indications on the history list to make the data point insertions.

6. A computer-based system for generation of an optimized mesh model of a three-dimensional object or surface, the computer, including a processor coupled to a memory and program elements adapted to accept as input a plurality of data points, with each data point being a coordinate describing the object or surface to be modeled, and construct a mesh to model the object or surface, the system comprising:

(a) a data point detail element to order the plurality of data points by recursively subdividing the plurality of data points into partitions until each partition contains a single data point, ordering the partitions during the recursive subdivision, ordering the data points in a sequence corresponding to the order of the partitions containing the data points and storing this sequence of data points in an ordered list;

(b) a mesh model construction element to construct a mesh comprising of a plurality of triangular faces, the face vertices being ones of the data points from the ordered list, the vertices for each face being ordered sequentially to have first, second and third vertices with a boundary connection between any two adjacent vertices of a face comprising an edge of the face, with a face being connected to another adjacent, neighboring face in the mesh through a shared edge and shared vertices creating that shared edge, the neighbors of the face being ordered following a sequential order corresponding to the ordering of the face'"'"'s vertices;

(c) the mesh model construction element further adapted to place a pointer to the data point on the ordered list that is next in sequence after the last data point used to construct a face, the pointer indicating the next data point for insertion into the mesh;

(d) a location element to determine the mesh face which is closest in distance to the next data point for insertion;

(e) a mesh insertion element, comprised to enable the processor to insert the next data point for insertion into the mesh by incorporating the data point for insertion and reorganizing the arrangement of vertices of the face that is closest in distance to the point for insertion (the insertion face) to create a set of three new triangles, each having its vertices ordered in a sequential manner with the data point for insertion being the first point in each new triangular face, the new triangles being connected to other triangles in the mesh through vertices and edges as were previously established in the insertion face, the new faces creating a continuous surface with the other faces of the mesh, the neighbors for each new face being ordered following the sequential order and corresponding to ordering of the face'"'"'s vertices;

(f) an optimality checking element to enable the processor to check one of the newly created faces to determine whether their construction meets Delaunayian optimality criteria, by checking the newly created face with a neighbor triangle to determine whether the non-shared vertex of the neighbor lies within a circumcircle determined by the vertices of the newly created triangle and place an indication on a history list if the faces meet the Delaunayian optimality criteria;

(g) a rearrangement element to reconfigure the shared edge between the triangle being checked and the neighbor to create two new flipped triangles, if the combination does not pass Delaunayian optimality, the rearrangement element further comprised to place an indication of the flip on the history list as the next action;

(h) the optimality checking element further comprised to recheck the triangle previously being checked if it was rearranged, using the rearrangement element to flip and indicate the flip history, if the new configuration does not meet Delaunayian optimality;

(i) the optimality checking element further comprised to proceed to a neighbor of the triangle being checked according to a preselected sequence and perform a check for optimality;

j) the optimality checking element further comprised to proceed checking the first neighbor of all checked triangles until it arrives again to the first triangle checked; and

(k) a mesh regeneration element which can reconstruct the complete mesh, after the complete mesh has been constructed at least once by having all data points inserted and all operations stored on the history list, by using only the ordered list to insert points and the associated operations stored in the history list for each data point insertion.

7. The system of claim 6 further comprising:

(a) the point insertion element, further comprised to enable the processor to insert the next data point for insertion into the mesh by rearranging the face for insertion by replacing the first vertex of that triangle with the data point for insertion, creating a new right neighbor triangle having the data point for insertion as a first vertex, the first face point as the second vertex and the second face point as the third vertex, and creating a new left face with the data point for insertion as the first vertex, the third face point as the second vertex and the first face point as the third vertex, the newly organized triangles being referred to as insertion face, left and right, and the processor configured to adjust the identification of neighboring triangles to follow the order of vertices; and

(b) the optimality checking element further comprised with a flipping element to rearrange the shared edge between the triangle being checked and the first neighbor, if the combination does not pass Delaunayian optimality, the flipping element enabling the processor to rearrange the triangles by redefining the vertices for the first neighbor triangle by setting the first vertex to be the first vertex of the triangle being checked, setting the second vertex to be the first neighbor'"'"'s former first vertex and setting the third vertex to be the first neighbor'"'"'s former second vertex and redefining the vertices of the triangle being checked to change its third vertex to be the former first vertex of the first neighbor.

8. A system for generation of an optimized mesh model of a three-dimensional object or surface, the system adapted to accept as input a plurality of data points, with each data point being a coordinate describing the object or surface to be modeled, and construct a mesh to model the object or surface, the system comprising:

(a) means for ordering the plurality of data points into a sequence for insertion into the mesh model and storing the sequence of data points in an ordered list;

(b) means for construct a mesh comprising of a plurality of faces, each face being a geometric shape with a predetermined number of vertices, the face vertices being ones of the data points from the ordered list, the boundary connection between any two adjacent vertices of a face comprising an edge of the face, with a face being connected to another adjacent face in the mesh through a shared edge and shared vertices creating that shared edge;

(c) means for access a data point using the ordered list the accessing means yielding the next data point for insertion into the mesh following the sequence of points in the ordered list;

(d) means for insert the next data point for insertion, by taking predetermined reorganizing steps to connect the data point for insertion into the mesh and advance the pointer to the next data point on the ordered list;

(e) means for check whether the construction of newly created faces as a result of data point insertion, meets a predetermined optimality criteria;

(f) means for redefine in a sequenced order the boundaries of the newly created faces when one of the newly created faces does not meet the predetermined optimality criteria, and place an indication on a history list in sequence for each redefinition made for a particular face.

9. A computer based system for checking optimality, based on Delaunayian principles, of data points being inserted into a triangulated 3D mesh model, the computer including a processor coupled to a memory, configured to accept as input a plurality of data points, with each data point being a coordinate describing the object or surface to be modeled, the data points contained on an ordered list which is the sequential order for insertion of the data points and the computer further configured to construct a 3D mesh to model the object or surface, the system comprising:

(a) a data structure to describe faces of the 3D mesh to include each data point in the 3D mesh as a vertex of at least one triangular face of the triangulated 3D mesh, sequentially order the vertices of each face of the 3D mesh, and describe the relationship of each face being connected to another adjacent, neighboring face through a shared edge and the pair of shared vertices creating that shared edge;

(b) the computer adapted to insert a new data point into the 3D mesh by reorganizing the arrangement of vertices of a face for insertion to create a set of three new faces, each new face having a data structure similar to the existing faces;

(c) the computer further adapted to check the faces of the 3D mesh for Delaunayian optimality;

(d) the computer further adapted to rearrange the 3D mesh if any of the faces do not pass the Delaunayian optimality check; and

(e) the computer further adapted to continue checking all the faces affected by the input of the new data point, the check to proceed in an order determined by the ordering of the vertices in the face data structure.

10. A computer based system for checking optimality, based on Delaunayian principles, of data points being inserted into a triangulated 3D mesh model, the computer including a processor coupled to a memory, configured to accept as input a plurality of data points, with each data point being a coordinate describing the object or surface to be modeled, the data points contained on an ordered list which is the sequential order for insertion of the data points and the computer further configured to construct a mesh to model the object or surface, the system comprising:

(a) a data structure to describe the mesh faces such that each data point in the mesh is a vertex of at least one triangular face of the mesh, each face of the mesh has its vertices ordered sequentially to have first, second and third vertices with a boundary connection between any two adjacent vertices of a face comprising an edge of the face and any face being connected to another adjacent, neighboring face through a shared edge and the pair of shared vertices creating that shared edge, the neighbors of the face being ordered following the sequential order corresponding to the ordering of the face'"'"'s vertices with a first neighbor face, second neighbor face and third neighbor face;

(b) the computer adapted to insert a new data point in the order indicated on the ordered list, into an existing face and alter the data structure such that the existing face is reorganized to create a set of three new faces, each having the new data point as one vertex and the remaining two vertices being vertices of the existing face, the vertices of the new faces being ordered in a sequence consistent with the existing face'"'"'s vertices, where the new data point is the first ordered vertex in each of the three new faces, and the neighbors of the new faces being ordered following a predetermined sequential order corresponding to the ordering of the new face'"'"'s vertices;

(c) the computer further adapted to begin a checking one of the new faces created by the insertion of the new data point for Delaunayian optimality;

(d) the computer further adapted to reorient the vertices of the first neighbor face in the data structure, if the combination does not pass Delaunayian optimality, so that the vertices of the first neighbor are ordered such that the first vertex is opposite the face being checked;

(e) the computer further adapted to rearrange the shared edge between the face being checked and the first neighbor, if the combination does not pass Delaunayian optimality, the rearrangement occurring by redefinition in the data structure of the vertices for the first neighbor face by setting the first vertex to be the first vertex of the face being checked, setting the second vertex to be the first neighbor'"'"'s former first vertex and setting the third vertex to be the first neighbor'"'"'s former second vertex and redefining in the data structure the vertices of the face being checked to change its third vertex to be the former first vertex of the first neighbor;

(f) the computer further adapted to redefine the neighbors of the rearranged faces in the data structure based on the new ordering of the vertices; and

(g) the computer further adapted to recheck the face previously being checked if it was rearranged, the checking on the face proceeding until it passes the Delaunayian optimality criteria.

11. The system of claim 10 further comprising the computer adapted to proceed, after completing a Delaunayian optimality check on a face, to the first neighbor of the face and perform a Delaunayian optimality check on the first neighbor, the computer proceeding thereafter to each succeeding first neighbor face and performing a Delaunayian optimality check at each said face until it arrives at the first face checked.

12. The system of claim 10 further comprising the computer adapted to project the 3D mesh model onto a 2D reference object creating a 2D triangulated mesh on the reference object that is representative of the original 3D mesh model, and performing the checking on the 2D projected mesh.

13. The system of claim 10 where the reorientation of the first neighbor'"'"'s vertices is accomplished by assigning the values 0,1,2 to the first, second and third vertices and neighbors respectively, storing a variable (k) equal to the neighbor value of the face being checked in the data structure of the first neighbor face, the first neighbor'"'"'s vertices are redefined such that the vertex k value is assigned to the original vertex (3-k), the original vertex (3-k) value is assigned to the original vertex with value 0, and the value 0 is assigned to the original vertex k, resulting in a reorientation of the first neighbor vertices such that the vertex assigned value 0 is the first vertex, the vertex assigned value 1 is the second vertex, and vertex assigned value 2 is the third vertex.

14. A computer-based system for ordering a plurality of data points to be inserted into a mesh model of an object or surface comprised of geometric faces, the computer comprising a processor to manipulate the order of the data points and a memory to store the order of the data points, each data point being a coordinate describing the object or surface to be modeled, the system comprising:

(a) the computer adapted to recursively subdivide the plurality of data points into partitions until a single data point is contained in each partition;

(b) the computer further adapted to sequentially order the partitions as the recursive subdivision is occurring;

(c) the computer further adapted to sequentially order the data points corresponding to the ordering of the partition in which the data point is in and storing this sequential order of data points in an ordered list.

15. A computer-based system for ordering a plurality of data points to be inserted into a mesh model of an object or surface comprised of geometric faces, the computer comprising a processor to manipulate the order of the data points and a memory to store the order of the data points, each data point being a coordinate describing the object or surface to be modeled, the system comprising:

(a) a distance computing element to determine the larger extent in two dimensions of the plurality of data points;

(b) a partitioning element to partition the plurality of date points along the larger extent into three boxes, with each box containing approximately the same number of points;

(c) an ordering element to order the boxes as a first, second and third box along the larger extent, and order the data points in the boxes such that all data points in the first box are before all the data points in the second box, and all data points in the second box are before all the data points in the third box;

(d) the partitioning element further adapted to continue partitioning each box along its larger extent into three boxes, until each box contains a single data point;

(e) the ordering element further adapted to order the newly created boxes as a new first, new second and new third box for each original box along the larger extent, such that the new boxes created from the original second box are ordered in the opposite direction of the new boxes created from the original first and third boxes and order the data points in each of the new boxes such that all data points in the new first box are before all the data points in the new second box, and all data points in the new second box are before all the data points in the new third box; and

(f) the ordering element further adapted to store the order of the data points in an ordered list corresponding to the order determined when each partitioned box contains a single data point.

16. A method for generation of an optimized mesh model of a three-dimensional object or surface on a computer, the computer, including a processor coupled to a memory and program elements, adapted to accept as input a plurality of data points, with each data point being a coordinate describing the object or surface to be modeled, and construct a 3D mesh to model the object or surface, the method comprising the steps of:

(a) ordering the plurality of data points into a sequence from first point to last point for insertion into the 3D mesh model and storing the sequence of data points in an ordered list;

(b) constructing a 3D mesh following the ordered list, the 3D mesh comprising a plurality of faces, with each face being a geometric shape with a predetermined number of vertices, the face vertices being ones of the data points from the ordered list, the boundary connection between any two adjacent vertices of a face comprising an edge of the face, with a face being connected to another adjacent face in the 3D mesh through a shared edge and shared vertices creating that shared edge, a 3D mesh model construction element constructing the 3D mesh by creating an initial mesh with the 3D mesh model comprising of a plurality of faces;

(c) determining whether the construction of newly created faces as a result of construction, meets a predetermined optimality criteria and to redefine in a sequenced order the boundaries of the newly created faces when one of the newly created faces does not meet the predetermined optimality criteria; and

(d) placing an indication on a history list in sequence for each check or redefinition made for a particular face.

17. The method of claim 16 comprising the additional step of starting from the first point of the insert list and continues building the mesh with each succeeding point in sequence until last point of the ordered list and the list is followed using a pointer.

18. The method of claim 16 where the optimality criteria is the Delaunay principle of optimality for an irregular triangulated mesh.

19. The method of claim 16 further comprising the further step of inserting data points starting from the first point of the insert list and continuing to building the mesh with each succeeding point in sequence until last point of the ordered list and then regenerating the following the sequence of indications on the history list.

20. A method for generation of an optimized mesh model of a three-dimensional object or surface using a plurality of data points, with each data point being a coordinate describing the object or surface to be modeled, the method comprising the steps of:

(a) ordering the plurality of data points by subdividing the plurality into partitions and continuing to subdivide until each partition contains a single data point and listing the data points in a sequence corresponding to the subdividing to create an ordered list where each point in the list is a near neighbor to the next point in the ordered list;

(b) constructing a mesh comprising at least one face using a subset of the plurality of data points, the mesh comprising a plurality of faces with each face being a geometric shape with a predetermined number of vertices, the face vertices being ones of the subset of data points, the boundary connection between any two adjacent vertices of a face comprising an edge of the face, with a face being connected to another adjacent, neighboring face in the mesh through a shared edge and shared vertices creating that shared edge;

(c) further constructing the mesh by inserting data points and making those insertions in a sequence following the ordered list, the mesh model construction selecting a data point from the ordered list for further building the mesh;

(d) identifying the mesh face which is closest in distance to the data point from the ordered list;

(e) further construct the mesh by inserting the data point into the face identified by the location element, by rearranging the vertices of the face and including the data point for insertion to create a set of new faces with the data point for insertion being shared in each new face, the new faces being connected to other faces in the mesh through vertices and edges as were previously established in the insertion face, establishing neighbor relationships for each new face and advancing the pointer to the next data point in the ordered list;

(f) checking one of the newly created faces to determine whether its construction meets a predetermined optimality criteria by checking the new face and the neighbor face opposite the newly inserted data point to evaluate its vertex and edge configuration for optimality and reconfiguring the face being checked and the neighbor to redefine their boundaries when the newly created face does not meet the predetermined optimality procedure;

(g) placing an indication of either a successful check or the rearrangement on a history list for this check;

(h) checking the all the newly created faces in a rotational direction moving from the location of the first checked face;

(i) placing an indication of either a successful check or the rearrangement on a history list in succession as each subsequent check is executed; and

j) constructing the complete mesh inserting all point following the sequence of the ordered list and checking to add indications to the history list, and thereafter regenerating the mesh using only the ordered list to insert points and the indications on the history list to make the data point insertions.

21. A method for generation of an optimized mesh model of a three-dimensional object or surface on a computer, the computer, including a processor coupled to a memory and program elements adapted to accept as input a plurality of data points, with each data point being a coordinate describing the object or surface to be modeled, and construct a mesh to model the object or surface, the method comprising the steps of:

(a) ordering the plurality of data points by recursively subdividing the plurality of data points into partitions until each partition contains a single data point, ordering the partitions during the recursive subdivision, ordering the data points in a sequence corresponding to the order of the partitions containing the data points and storing this sequence of data points in an ordered list;

(b) constructing a mesh comprising of a plurality of triangular faces, the face vertices being ones of the data points from the ordered list, the vertices for each face being ordered sequentially to have first, second and third vertices with a boundary connection between any two adjacent vertices of a face comprising an edge of the face, with a face being connected to another adjacent, neighboring face in the mesh through a shared edge and shared vertices creating that shared edge, the neighbors of the face being ordered following a sequential order corresponding to the ordering of the face'"'"'s vertices;

(c) placing a pointer to the data point on the ordered list that is next in sequence after the last data point used to construct a face, the pointer indicating the next data point for insertion into the mesh;

(d) determining the mesh face which is closest in distance to the next data point for insertion;

(e) inserting the next data point for insertion into the mesh by incorporating the data point for insertion and reorganizing the arrangement of vertices of the face that is closest in distance to the point for insertion (the insertion face) to create a set of three new triangles, each having its vertices ordered in a sequential manner with the data point for insertion being the first point in each new triangular face, the new triangles being connected to other triangles in the mesh through vertices and edges as were previously established in the insertion face, the new faces creating a continuous surface with the other faces of the mesh, the neighbors for each new face being ordered following the sequential order and corresponding to ordering of the face'"'"'s vertices;

(f) checking one of the newly created faces to determine whether their construction meets Delaunayian optimality criteria, by checking the newly created face with a neighbor triangle to determine whether the non-shared vertex of the neighbor lies within a circumcircle determined by the vertices of the newly created triangle and place an indication on a history list if the faces meet the Delaunayian optimality criteria;

(g) reconfiguring the shared edge between the triangle being checked and the neighbor to create two new flipped triangles, if the combination does not pass Delaunayian optimality and placing an indication of the flip on the history list as the next action;

(h) rechecking the triangle previously being checked if it was rearranged, using the rearrangement element to flip and indicate the flip history, if the new configuration does not meet Delaunayian optimality;

(i) proceeding to a neighbor of the triangle being checked according to a preselected sequence and perform a check for optimality;

(j) checking the first neighbor of all checked triangles until arriving again to the first triangle checked;

(k) reconstructing the complete mesh, after the complete mesh has been constructed, using only the ordered list to insert points and the associated operations stored in the history list for each data point insertion.