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

• US 6,611,267 B2
• Filed: 05/14/2002
• Issued: 08/26/2003
• Est. Priority Date: 10/16/1996
• Status: Expired due to Fees

• Current Assignee: Sizmek Technologies Inc (Sizmek, Inc.)
• Original Assignee: Viewpoint Mhc
• Inventors: Lebedev, Alexei, Migdal, Alexander
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US10/145,176
• Publication Number:
  US 20020167518A1
• Time in Patent Office: 469 Days
• Field of Search: 345/419, 345/428, 345/606, 345/619, 345/440, 345/441, 345/442
• US Class Current: 345/428
• 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 method for generating a mesh model of an object, comprising:

receiving an ordered set of data points, the data points including coordinates that describe the object;

when a minimum number of data points have been received, displaying an initial representation of the mesh model based on the received minimum number of data points; and

increasing a resolution of the displayed mesh model by inserting into the displayed mesh model data points received after the minimum number of data points was received.

2. The method according to claim 1, wherein the ordered set of data points is received over an information network.

3. The method according to claim 1, wherein the minimum number of data points is the number of data points required to describe the basic shape of the object.

4. The method according to claim 1, wherein the minimum number of data points is determined based on a user specified tolerance level.

5. The method according to claim 1, wherein the data points are ordered so that a resolution of the displayed mesh model depends on a quantity of data points applied from the ordered set of data points.

6. The method according to claim 1, further comprising:

storing an insertion list of data points inserted during the display of the mesh model; and

decreasing a resolution of the displayed mesh model by removing data points from the displayed mesh model based on the insertion list.

7. The method according to claim 6, wherein the data points are removed from the displayed mesh model in an order reverse to which they were stored in the insertion list.

8. A medium storing instructions adapted to be executed by a processor to perform the steps of:

receiving an ordered set of data points, the data points including coordinates that describe the object;

when a minimum number of data points have been received, displaying an initial representation of the mesh model based on the received minimum number of data points; and

increasing a resolution of the displayed mesh model by inserting, into the displayed mesh model, data points received after the minimum number of data points was received.

9. The medium of claim 8, wherein the minimum number of data points is the number of data points required to describe the basic shape of the object.

10. The medium of claim 8, wherein the minimum number of data points is determined based on a user specified tolerance level.

11. The medium of claim 8, wherein the ordered set of data points is received over an information network.

12. The medium of claim 8, wherein the data points are ordered so that a resolution of the displayed mesh model depends on a quantity of data points applied from the ordered set of data points.

13. The medium of claim 8, further storing instructions adapted to be executed by a processor to perform the steps of:

storing an insertion list of data points inserted during the display of the mesh model; and

decreasing a resolution of the displayed mesh model by removing data points from the displayed mesh model based on the insertion list.

14. The medium of claim 13, wherein the data points are removed from the displayed mesh model in an order reverse to which they were stored in the insertion list.

15. A method for displaying a mesh model of an object, comprising:

receiving a history list of ordered operations;

displaying an initial representation of the mesh model by performing a minimum number of the ordered operations stored in the history list; and

increasing a resolution of the displayed mesh model by performing additional ordered operations stored in the history list after the minimum number of ordered operations.

16. The method according to claim 15, wherein the history list is received over an information network.

17. The method according to claim 15, wherein the minimum number of ordered operations is a quantity of ordered operations required to create a mesh model that describes the basic shape of the object.

18. The method according to claim 15, wherein the minimum number of ordered operations is determined based on a user specified tolerance level.

19. The method according to claim 15, wherein the ordered operations are ordered so that a resolution of the displayed mesh model depends on a quantity of ordered operations performed from the history list.

20. The method according to claim 15, further comprising:

decreasing a resolution of the displayed mesh model by performing the operations in an order reverse to which the operations are ordered in the history list.

21. A medium storing instructions adapted to be executed by a processor to perform the steps of:

receiving a history list of ordered operations;

displaying an initial representation of the mesh model by performing a minimum number of the ordered operations stored in the history list; and

increasing a resolution of the displayed mesh model by performing additional ordered operations stored in the history list after the minimum number of ordered operations.

22. The medium of claim 21, wherein the history list is received over an information network.

23. The medium of claim 21, wherein the minimum number of ordered operations is a quantity of ordered operations required to create a mesh model that describes the basic shape of the object.

24. The medium of claim 21, wherein the minimum number of ordered operations is determined based on a user specified tolerance level.

25. The medium of claim 21, wherein the ordered operations are ordered so that a resolution of the displayed mesh model depends on a quantity of ordered operations performed from the history list.

26. The medium of claim 21, further storing instructions adapted to be executed by a processor to perform the step of:

decreasing a resolution of the displayed mesh model by performing the operations in an order reverse to which the operations are ordered in the history list.

27. A method for displaying a mesh model, comprising:

displaying an initial representation of the mesh model based on a first predetermined number of data points of a set of ordered data points;

increasing a resolution of the displayed mesh model by inserting, into the displayed mesh model, additional data points that follow the first predetermined number of data points in the set of ordered data points.

28. The method according to claim 27, wherein the predetermined number of data points is a quantity of data points required to describe the basic shape of the mesh model.

29. The method according to claim 27, wherein the predetermined number of data points is determined based on a user specified tolerance level.

30. The method according to claim 27, wherein the data points are ordered so that a resolution of the mesh model depends on a quantity of data points for the mesh model applied from the ordered set of data points.

31. The method according to claim 27, further comprising:

storing an insertion list of data points inserted during the display of the mesh model.

32. A method for displaying a mesh model, comprising:

displaying an initial representation of the mesh model based on a first predetermined number of data points of a set of ordered data points;

decreasing a resolution of the displayed mesh model by removing, from the displayed mesh model, data points of said first predetermined number of data points in said set of ordered data points in an order reverse to which they are ordered in said set of ordered data points.

33. The method according to claim 32, wherein the predetermined number of data points is determined based on a user specified tolerance level.

34. The method according to claim 32, wherein the data points are ordered so that a resolution of the displayed mesh model depends on a quantity of data points for the mesh model applied from the ordered set of data points.

35. The method according to claim 32, further comprising:

storing an ordered list of data points used during the display of the mesh model; and

determining which data points to remove from the mesh model based on the ordered list of data points.