System and method for computer modeling of 3D objects or surfaces by mesh constructions having optimal quality characteristics and dynamic resolution capabilities

• US 6,262,739 B1
• Filed: 03/22/1999
• Issued: 07/17/2001
• Est. Priority Date: 10/16/1996
• Status: Expired due to Term

• Current Assignee: Andreas Acquisitions, LLC
• Original Assignee: Real-Time Geometry Corporation
• Inventors: Lebedev, Alexei, Migdal, Alexander
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/274,243
• Time in Patent Office: 848 Days
• Field of Search: 345/423, 345/426, 345/430, 345/418, 345/419, 345/441, 345/442, 345/118, 345/121
• US Class Current: 345/423
• 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 an optimized mesh model of a real world object, terrain or other three-dimensional surface. The mesh construction technique provides dynamic “up resolution/down resolution” mesh construction capabilities. The system inserts points into the mesh incrementally, ordering the points before each insertion so that dynamic resolution construction can be maintained. The point ordering process determines the distance each point has from the surface of a given mesh configuration such that the next point added will always be the point bringing the most significant detail to the mesh. This procedure of “optimal simplification” optimizes the mesh by guaranteeing the fewest number of points for the most detail at any given resolution. The present invention also provides a system and method to ensure an optimal quality of mesh at any level of insertion or deletion, following in an exemplary configuration a regularized systemized checking function to maintain a mesh of optimal quality such as by Delaunay triangulation principles. The system stores a history of the insertion and deletion steps in a compact list, which can be used for rapid removal of points or rapid regeneration of the mesh.

Claims

1. A computer-based system for displaying an image of a three dimensional (3-D) object comprising:

a set of data points with each data point providing information that describes the 3-D object and with each of the data points ordered in a data structure according to a predetermined ordering scheme according to their determined significance in describing the surface characteristics of the object;

a mesh model constructed with a first subset of the set of data points, the mesh model organizing the first subset of the data points into a set of connected faces, each face being a geometric shape with a predetermined number of vertices, and the ones of the points for each face comprising the vertices of that face, 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;

a data set containing entries that indicate the alterations that should occur to the faces of the mesh model as each of the data points not in the first subset of data points (the remaining data points) is inserted into the mesh model following the sequence of the ordering of the data points;

a mesh building module configured to incrementally insert a plurality of the remaining data points into the mesh model following the sequence of the ordering of the data points and, for each of the data points inserted, to execute alterations to the faces of the mesh model as indicated by the entries in the data set; and

a display module configured to display a view of the 3-D object from a predetermined vantage point, using data contained in the mesh model.

2. A computer-based system for displaying an image of a three dimensional (3-D) object in a multiple, networked computing environment, the system comprising:

a first computer configured to output to a second computer, an initial subset of data points from a set of data points which provide information to describe the 3-D object;

the second computer configured to construct a mesh model from the initial set of data points by organizing the data points into a set of connected faces, each face being a geometric shape with a predetermined number of vertices, and the ones of the points for each face comprising the vertices of that face, 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 first computer further configured to output to the second computer a sequence of additional data points from the set of data points, the sequence of additional data points following a predetermined ordering scheme that orders the points according to their determined significance in describing the surface characteristics of the object;

the first computer further configured to output to the second computer additional codes to direct the second computer to make alterations to the faces of the mesh model as each additional data point in the sequence is added into the mesh model;

the second computer further configured to incrementally insert the output data points into the mesh model following the ordered sequence and, for each of the data points inserted, executing alterations to the faces of the mesh model as directed by the additional codes; and

the second computer further configured to display a view of the 3-D object from a predetermined vantage point, using data contained in the mesh model.

3. The system of claim 2, further comprising:

the second computer further configured to access a value that indicates the maximum number of data points that it will use to display the model; and

the second computer further configured to incrementally insert the data points output by the first computer into the mesh model following the ordered sequence, and for each of the data points inserted executing alterations to the faces of the mesh model as directed by the additional code, but only up to a number that is less than or equal to the value that indicates the maximum number of data points accessed above.

4. The system of claim 2, further comprising:

the second computer further configured to access value that indicates the maximum number of data points that it will use to display the model;

the second computer further configured to transmit to the first computer the value that indicates the maximum number of data points that the second computer will use to display the model; and

the first computer further configured to output to the second computer a sequence of additional data points from the set of data points up to a number equal to the value of the maximum number of data points, with each data point in the sequence providing information that describes the 3-D object;

the sequence of data points following a predetermined ordering scheme that orders the points according to their determined significance in describing the surface characteristics of the object.

5. The system of claim 2, further comprising:

the display element of the second computer further arranged to display a view of the 3-D object on a computer output screen from a predetermined vantage point, using data contained in the mesh model constructed from the initial subset of data points then display a view of the 3-D object on a computer output screen from a predetermined vantage point, using data contained in the mesh model as it was further constructed.

6. The system of claim 2 wherein the multiple, networked computing environment is the Internet.

7. A computer-based system for generating an image of a three dimensional (3-D) object in a multiple, networked computing environment, the system comprising:

a computer configured to receive from a data source, an initial subset of data points from a set of data points at the data source which provide information to describe the 3-D object;

the computer further configured to construct a mesh model from the initial set of data points by organizing the data points into a set of connected faces, each face being a geometric shape with a predetermined number of vertices, and the ones of the points for each face comprising the vertices of that face, 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 computer further configured to receive from the data source a sequence of additional data points from the set of data points, with each data point in the sequence providing information that describes the 3-D object;

the sequence of data points following a predetermined ordering scheme that orders the points according to their determined significance in describing the surface characteristics of the object;

the computer configured to receive from the data source additional codes to direct the computer to make alterations to the faces of the mesh model as each data point in the sequence is added into the mesh model;

the computer further configured to incrementally insert the output data points into the mesh model following the ordered sequence and, for each of the data points inserted, executing alterations to the faces of the mesh model as directed by the additional codes; and

the computer further configured to generate a view of the 3-D object from a predetermined vantage point, using data contained in the mesh model.

8. A system for generating an image of a 3-D object at differing resolutions, the system comprising:

a set of data points with each data point providing information that describes the 3-D object;

a mesh model constructed from an initial subset of the data points, the mesh model organizing the points into a set of connected faces, each face being a geometric shape with a predetermined number of vertices, and the ones of the points for each face comprising the vertices of that face, 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;

a image generation element to generate an image of the 3-D object from a predetermined vantage point using data contained in the mesh model;

a mesh building element configured to further construct the mesh model by (i) incrementally inserting into the mesh model a plurality of additional ones of the data points from the set of data points following the sequence of ordering where data points are ordered according to their determined significance in describing the surface characteristics of the object and (ii) altering the mesh model with each data point insertion by following entries contained in a data set of entries that indicate the alterations that would occur to the faces of the mesh model as each of the additional ones of the data points not in the first subset of data points are inserted into the mesh model following the sequence of ordering; and

the image generation element further arranged to generate a view of the 3-D object from a predetermined vantage point using data contained in the mesh model as it was further constructed.

9. The system of claim 8 further comprising a data point removing element configured to alter the mesh model by (i) incrementally removing a plurality of data points previously inserted into the mesh following in reverse order the sequence of ordering for data point insertion;

and (ii) altering the mesh model with point removal by reversing the alterations that were made as the data point in question was inserted; and

the image generation element further arranged to generate a view of the 3-D object from a predetermined vantage point, using data contained in the mesh model as resulted after the process of point removal.

10. A computer-based system for increasing the resolution of a mesh model of an object or surface, the computer including a processor coupled to a memory, adapted to accept as input a plurality of data points comprising coordinates that describe the object or surface and further construct and manipulate the mesh based on the data points, the system comprising:

(a) an insertion list to sequentially record the order of insertion into the mesh of the data points as the processor constructs a mesh;

(b) a history list to record any information concerning the sequence of alterations made by the processor to the mesh as the data points are inserted into the mesh during construction;

(c) the computer adapted to regenerate a mesh model by incrementally inserting insert data points into a replica mesh model of the mesh model following the sequential order indicated on the insertion list; and

(d) the computer further adapted to execute changes to the replica mesh model mesh as each additional data point is inserted as indicated on the history list.

11. A computer-based method for constructing and displaying an image of a three dimensional (3-D) object comprising the steps of:

constructing with a computer a mesh model from a first subset of a set of data points that describe the 3-D object, the mesh model organizing the points into a set of connected faces, each face being a geometric shape with a predetermined number of vertices, and the ones of the points for each face comprising the vertices of that face, 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;

further constructing the mesh model by (i) incrementally inserting additional ones of the data points from the set of data point into the mesh model following the sequence of ordering where the data points are ordered according to their determined significance in describing the surface characteristics of the object and (ii) altering the mesh model with each data point insertion by following entries contained in a data set containing entries that indicate the alterations that would occur to the faces of the mesh model as each of the additional ones of the data points are inserted into the mesh model following the sequence of ordering; and

displaying a view of the 3-D object from a predetermined vantage point, using data contained in the mesh model.

12. A computer-based method for displaying an image of a three dimensional (3-D) object in a multiple, networked computing environment, the method comprising the steps of:

outputting from a first computer to a second computer, an initial subset of data points from a set of data points which provide information to describe the 3-D object;

constructing at the second computer a mesh model from the initial set of data points by organizing the data points into a set of connected faces, each face being a geometric shape with a predetermined number of vertices, and the ones of the points for each face comprising the vertices of that face, 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;

outputting from the first computer to the second computer a sequence of additional data points from the set of data points, with each data point in the sequence providing information that describes the 3-D object;

the sequence of data points following a predetermined ordering scheme that orders the points according to their determined significance in describing the surface characteristics of the object;

outputting from the first computer to the second computer additional codes to direct the second computer to make alterations to the faces of the mesh model as each data point in the sequence is added into the mesh model;

at the second computer, incrementally inserting the output data points into the mesh model following the ordered sequence and, for each of the data points inserted, executing alterations to the faces of the mesh model as directed by the additional codes; and

displaying a view of the 3-D object from a predetermined vantage point, using data contained in the mesh model.

13. The method of claim 12, further comprising the steps of:

at the second computer accessing a value that indicates the maximum number of data points that it will use to display the mesh model; and

incrementally inserting the output data points into the mesh model following the ordered sequence and, for each of the data points inserted, executing alterations to the faces of the mesh model as directed by the additional codes;

but only up to a number that is less than or equal to the value that indicates the maximum number of data points accessed above.

14. The method of claim 12, further comprising the steps of:

at the second computer accessing a value that indicates the maximum number of data points that it will use to display the model;

at the second computer transmitting to the first computer the value that indicates the maximum number of data points that the second computer will use to display the model; and

at the first computer, outputting to the second computer a sequence of additional data points from the set of data points up to a number equal to the value that indicated the maximum number of data points, with each data point in the sequence providing information that describes the 3-D object;

the sequence of data points following a predetermined ordering scheme that orders the points according to their determined significance in describing the surface characteristics of the object.

15. The method of claim 12, further comprising the steps of:

at the second computer, displaying a view of the 3-D object on a computer output screen from a predetermined vantage point, using data contained in the mesh model constructed from the initial subset of data points then displaying a view of the 3-D object on a computer output screen from a predetermined vantage point, using data contained in the mesh model as it was further constructed.

16. A computer-based method for displaying an image of a three dimensional (3-D) object in a multiple, networked computing environment, the method comprising the steps of:

at a computer, receiving from a data source an initial subset of data points from a set of data points at the data source which provide information to describe the 3-D object;

at the computer, constructing a mesh model from the initial set of data points by organizing the data points into a set of connected faces, each face being a geometric shape with a predetermined number of vertices, and the ones of the points for each face comprising the vertices of that face, 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;

at the computer, receiving from the data source a sequence of additional data points from the set of data points, with each data point in the sequence providing information that describes the 3-D object;

the sequence of data points following a predetermined ordering scheme that orders the points according to their determined significance in describing the surface characteristics of the object;

at the computer, receiving from the data source additional codes to direct the computer to make alterations to the faces of the mesh model as each data point in the sequence is added into the mesh model;

at the computer, incrementally inserting the output data points into the mesh model following the ordered sequence and, for each of the data points inserted, executing alterations to the faces of the mesh model as directed by the additional codes; and

at the computer, displaying a view of the 3-D object from a predetermined vantage point, using data contained in the mesh model.

17. The method of claim 16 wherein the multiple, networked computing environment is the Internet.

18. A computer-based method for displaying an image of a 3-D object at differing resolutions, the method comprising the steps of:

constructing a mesh model from an initial subset of a set of data points which provides information that describes the 3-D object by organizing the data points into a set of connected faces, each face being a geometric shape with a predetermined number of vertices, and the ones of the points for each face comprising the vertices of that face, 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;

displaying a view of the 3-D object on a computer output screen from a predetermined vantage point, using data contained in the mesh model.

further constructing the mesh model by (i) incrementally inserting into the mesh model a plurality of additional ones of the data points from the set of data points following the sequence of ordering where data points are ordered according to their determined significance in describing the surface characteristics of the object and (ii) altering the mesh model with each data point insertion by following entries contained in a data set of entries that indicate the alterations that would occur to the faces of the mesh model as each of the additional ones of the data points not in the first subset of data points are inserted into the mesh model following the sequence of ordering; and

displaying a view of the 3-D object on a computer output screen from a predetermined vantage point, using data contained in the mesh model as it was further constructed.

19. The method of claim 18 further comprising the steps of:

altering the mesh model by (i) incrementally removing a plurality of data points previously inserted into the mesh following in reverse order the sequence of ordering for data point insertion; and

(ii) further altering the mesh model for each point removal by reversing the alterations that were made as the data point in question was inserted; and

displaying a view of the 3-D object on a computer output screen from a predetermined vantage point, using data contained in the mesh model as resulted after the process of point removal.

20. A method for increasing the resolution of a mesh model of an object or surface on a computer, the computer including a processor coupled to a memory, adapted to accept as input a plurality of data points comprising coordinates that describe the object or surface and further construct and manipulate the mesh based on the data points, the method comprising the steps of:

(a) creating an insertion list to sequentially record the order of insertion into the mesh of the data points as the processor constructs a mesh;

(b) creating a history list to record any information concerning the sequence of alterations made by the processor to the mesh as the data points are inserted into the mesh during construction;

(c) regenerating a mesh model by incrementally inserting data points into the regenerated mesh following the sequential order indicated on the insertion list; and

(d) executing changes to the regenerated mesh model as each additional data point is inserted as indicated on the history list.

21. A computer-based system for displaying an image of a 3-D object, comprising:

an ordered list of data points, the data points representing coordinates describing a surface of the 3-D object;

an ordered list of operations; and

a module applying at least some of the operations in an order in which the at least some of the operations appear in the ordered list of operations, to a corresponding number of the data points in an order in which the corresponding number of the data points appear in the ordered list of data points, to display at least part of the image of the 3-D object.

22. The computer-based system of claim 21, wherein the module determines how far down the ordered list of operations to proceed as a function of a selected resolution of the image.

23. The computer-based system of claim 21, wherein the ordered list of operations and the ordered list of data points are transmitted to the module over a network.

24. The computer-based system of claim 23, wherein the network is the Internet.

25. The computer-based system of claim 21, wherein the data points are ordered so that a resolution of the image depends on a quantity of the operations applied from the ordered list of operations.

26. The computer-based system of claim 21, wherein the operations include mesh-building operations.

27. A method of displaying an image of a 3-D object, comprising the steps of:

receiving an ordered list of data points, the data points representing coordinates describing a surface of the 3-D object;

receiving an ordered list of operations; and

applying by a module at least some of the operations in an order in which the at least some of the operations appear in the ordered list of operations, to a corresponding number of the data points in an order in which the corresponding number of the data points appear in the ordered list of data points, to display at least part of the image of the 3-D object.

28. The method of claim 27, further comprising the steps of:

determining how far down the ordered list of operations the module should proceed as a function of a predetermined desired resolution of the image.

29. A method of displaying an image of a 3-D object, comprising the steps of:

supplying an ordered list of data points to a module, the data points representing coordinates describing a surface of the 3-D object; and

supplying an ordered list of operations to the module, the module applying at least some of the operations in an order in which the at least some of the operations appear in the ordered list of operations, to a corresponding number of the data points in an order in which the corresponding number of the data points appear in the ordered list of data points, to display at least part of the image of the 3-D object.

30. A computer-based system for displaying an image of a three dimensional (3-D) object comprising:

a set of data points with each data point providing information that describes the 3-D object and each data point being capable of being used to construct a mesh model of the 3D object, the mesh model organizing the data points into a set of connected faces, each face being a geometric shape with a predetermined number of vertices, and the ones of the data points for each face comprising the vertices of that face, 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 edges;

the data points being further ordered in a data structure according to a predetermined ordering scheme according to their determined significance in describing the surface characteristics of the object, the data points in the data structure associated with entries that indicate the alterations that should occur to the faces the mesh model as each of the data points is used build the mesh when the mesh is build with the data points following the sequence of the predetermined ordering; and

a mesh building module configured to build the mesh model following the sequence of the ordered list and, for each of the data points used to construct the mesh, to execute alterations to the faces of the mesh model as indicated by the entries in the data set.

31. The system of claim 30 further comprising

a display module configured to display a view of the 3-D object from a predetermined vantage point, using data contained in the mesh model.

32. A computer-based method for displaying an image of a three dimensional (3-D) object in a multiple, networked computing environment, the method comprising the steps of:

outputting from a first computer to a second computer, a sequence of data points from a set of data points, with each data point in the sequence providing information that describes the 3-D object;

the sequence of data points following a predetermined ordering scheme that orders the points according to their determined significance in describing the surface characteristics of the object; and

outputting from the first computer to the second computer additional codes to direct the construction of a mesh model from the sequence of data points according to a process to organize the data points into a set of connected faces, each face being a geometric shape with a predetermined number of vertices, and the ones of the points for each face comprising the vertices of that face, 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 process of organizing the data points including the incremental insertion of a plurality of ones of the sequence of data points into the mesh model following the ordered sequence and, for each of the data points inserted, executing alterations to the faces of the mesh model as directed by the additional codes.

33. The method of claim 32 further comprising the step of displaying a view of the 3-D object from a predetermined vantage point, using data contained in the mesh model.

34. The method of claim 32, further comprising the steps of:

at the second computer accessing a value that indicates the maximum number of data points that it will use to display the mesh model; and

incrementally inserting a plurality of the output data points into the mesh model following the ordered sequence and, for each of the data points inserted, executing alterations to the faces of the mesh model as directed by the additional codes;

but only up to a number that is less than or equal to the value that indicates the maximum number of data points accessed above.

35. The method of claim 32, further comprising the steps of:

at the second computer accessing a value that indicates the maximum number of data points that it will use to display the model;

at the second computer transmitting to the first computer the value that indicates the maximum number of data points that the second computer will use to display the model; and

at the first computer, outputting to the second computer a sequence of additional data points from the set of data points up to a number equal to the value that indicated the maximum number of data points, with each data point in the sequence providing information that describes the 3-D object;

the sequence of data points following a predetermined ordering scheme that orders the points according to their determined significance in describing the surface characteristics of the object.