Multi-resolution graphic representation employing at least one simplified model for interactive visualization applications

• US 5,448,686 A
• Filed: 01/02/1992
• Issued: 09/05/1995
• Est. Priority Date: 01/02/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rossignac, Jaroslaw R., Borrel, Paul
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US07/816,687
• Time in Patent Office: 1,342 Days
• Field of Search: 395/119-121, 395/123-132, 395/133, 395/135, 358/456
• US Class Current: 345/420
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

A method for execution by a data processor that prepares an object for display. The method includes a step of processing a first model of the object so as to produce a simplified model thereof, the step of processing including the steps of (a) superimposing a first plurality of grid cells on the first model; for any one of the first plurality of grid cells containing more than one vertex of the first model, (b) combining the vertices into a first representative vertex; (c) generating a first simplified model that includes the first representative vertex or first representative vertices; and (d) storing the first simplified model for subsequent use. The method encompasses a number of criteria for use by the step of combining the vertices within a grid cell. These criteria include: (a) selecting a center of the grid cell as a position of the representative vertex; (b) selecting a position of a predetermined one of the vertices within the grid cell as a position of the representative vertex; (c) selecting an average position of the vertices as a position of the representative vertex; (d) selecting a position of a vertex that is nearest to the average position as a position of the representative vertex; and (e) selecting a position of a vertex that represents a locally extreme point within the grid cell as a position of the representative vertex.

Claims

1. A method for execution by a data processor to prepare an object for display on a display means wherein the object is represented by a plurality of vertices and planar faces each having boundaries defined in terms of the plurality of vertices, the method comprising the steps of:

generating a first model of the object that represents the object'"'"'s original geometry by partitioning the planar faces of the object into a plurality of non-overlapping planar sub-faces each having boundaries defined in terms of the plurality of vertices of the object;

partitioning space enclosing the first model into a first plurality of grid cells;

generating a first simplified model by, for each grid cell of the first plurality of grid cells containing more than one vertex of the first model, combining the vertices of the first model within the grid cell into at least one first representative vertex; and

storing the first simplified model for subsequent use.

2. A method as set forth in claim 1 wherein the combining of the step of generating a first simplified model includes a step of selecting a center of the grid cell as a position of the first representative vertex.

3. A method as set forth in claim 1 wherein the combining of the step of generating a first simplified model includes a step of selecting a position of a predetermined one of the vertices within the grid cell as a position of the first representative vertex.

4. A method as set forth in claim 1 wherein the combining of the step of generating a first simplified model includes a step of determining an average position of the vertices within the grid cell, and a step of selecting the average position as a position of the first representative vertex.

5. A method as set forth in claim 1 wherein the combining of the step of generating a first simplified model includes a step of determining an average position of the vertices within the grid cell, and a step of selecting as the first representative vertex a vertex within the grid cell that is nearest to the average position.

6. A method as set forth in claim 1 wherein the combining of the step of generating a first simplified model includes a step of selecting as the first representative vertex a vertex within the grid cell that represents a locally extreme point, wherein the selected vertex has a greatest probability of lying on a silhouette of the object.

7. A method as set forth in claim 1 wherein the partitioning of the step of generating a first model includes a step of triangulating the faces of the object, and wherein the step of generating a first simplified model includes a step of detecting and eliminating degenerate and duplicate triangles that result from the execution of the combining of the step of generating a first simplified model.

8. A method as set forth in claim 1 and further including a step of selecting one of the first model and the first simplified model for display on the display means.

9. A method as set forth in claim 8 wherein the step of selecting includes a step of determining a size of a projection of the object onto the display means, and wherein the step of selecting selects one of the first model and the first simplified model as a function of at least the determined size of the projection.

10. A method as set forth in claim 8 wherein, in response to a required motion of the object on the display means, the step of selecting selects the first model if a time required to display the first model is sufficiently small for providing realtime motion of the object on the display means, otherwise the step of selecting selects the first simplified model.

11. A method as set forth in claim 8 wherein the step of selecting includes a step of determining a number of faces of the object, and wherein the step of selecting selects the first model if the number of faces is below a threshold number of faces.

12. A method as set forth in claim 1 further including the steps of:

partitioning space enclosing the first model into a second plurality of grid cells, wherein said second plurality of grid cells has a larger dimension than a corresponding dimension of said first plurality of grid cells;

generating a second simplified model by, for each grid cell of the second plurality of grid cells containing more than one vertex of the first model, combining the vertices of the first model within the grid cell into at least one second representative vertex; and

storing the second simplified model for subsequent use.

13. A method as set forth in claim 1 further including the steps of:

partitioning space enclosing the first simplified model into a second plurality of grid cells, wherein said second plurality of grid cells has a larger dimension than a corresponding dimension of said first plurality of grid cells;

generating a second simplified model by, for each grid cell of the second plurality of grid cells containing more than one vertex of the first simplified model, combining the vertices of the first simplified model within the grid cell into at least one second representative vertex; and

storing the second simplified model for subsequent use.

14. A method for execution by a data processor to prepare an object for display on a display means wherein the object is represented by a plurality of vertices and planar faces each having boundaries defined in terms of the plurality of vertices, the method comprising the steps of:

generating a first model of the object that represents the object'"'"'s original geometry by partitioning the planar faces of the object into a plurality of nonoverlapping triangular regions each having boundaries defined in terms of the plurality of vertices of the object;

partitioning space enclosing the first model into a plurality of grid cells;

generating a first simplified model by, for each grid cell of the plurality of grid cells containing more than one vertex of the first model, combining the vertices of the first model within the grid cell into at least one representative vertex in accordance with a combination criteria;

storing the first model for subsequent use; and

storing the first simplified model for subsequent use.

15. A method as set forth in claim 14 wherein the combination criteria selects a center of the grid cell as a position of the representative vertex.

16. A method as set forth in claim 14 wherein the combination criteria selects a position of a predetermined one of the vertices within the grid cell as a position of the representative vertex.

17. A method as set forth in claim 14 wherein the combining of the step of generating a first simplified model includes a step of determining an average position of the vertices within the grid cell, and wherein the combination criteria selects the average position as a position of the representative vertex.

18. A method as set forth in claim 14 wherein the combining of the step of generating a first simplified model includes a step of determining an average position of the vertices within the grid cell, and wherein the combination criteria selects a vertex within the grid cell that is nearest to the average position as the representative vertex.

19. A method as set forth in claim 14 wherein the combination criteria selects a position of a vertex that represents a locally extreme point within the grid cell as a position of the representative vertex, wherein the selected position is a position that has a greatest probability of lying on a silhouette of the object.

20. A method as set forth in claim 14 wherein each of the plurality of grid cells is of substantially equal size.

21. A method as set forth in claim 14 wherein the plurality of the three dimensional grid cells are of different sizes.

22. Graphics display apparatus for displaying at least one object, comprising:

memory means for storing a model of an object and for storing at least one simplified model of the object, the model having a first plurality of vertices and the at least one simplified model having a second plurality of vertices that is less than the first plurality of vertices;

means, responsive to a command from a user of the apparatus, for indicating that a motion of displayed object is to occur; and

processing means, coupled to and responsive to the indicating means, for accessing the memory means to select for display one of the model of the object and one of the at least one simplified models of the object.

23. Graphics display apparatus as set forth in claim 22 wherein said processing means includes means for processing the model of the object so as to produce said at least one simplified model thereof, said processing means including,

means for partitioning space enclosing the model into the plurality of cells;

means, responsive to one of the plurality of cells containing more than one vertex of the model, for combining the vertices within the cell into a representative vertex; and

means for generating said at least one simplified model so as to include the representative vertex.

24. Graphics display apparatus as set forth in claim 23 and further including means for storing a tree data structure containing vertices of the model.

25. Graphics display apparatus as set forth in claim 23 and further including means for storing a linked list data structure containing vertices of the model.

26. Graphics display apparatus as set forth in claim 22 and further including means for storing limit values related to a size of a projection of the object on a display screen means, and wherein said processing means is responsive to a determined size of a projection of the object, and to said stored limit values, to select one of said models for display.

27. Apparatus for displaying an object represented by a plurality of vertices and planar faces each having boundaries defined in terms of the plurality of vertices, the apparatus comprising:

means for generating a first model of the object that represents the object'"'"'s original geometry by partitioning the planar faces of the object into a plurality of non-overlapping planar sub-faces each having boundaries defined in terms of the plurality of vertices of the object;

means for partitioning space enclosing the first model into a plurality of grid cells;

means for generating a simplified model of the object, responsive to a condition wherein one of the plurality of grid cells contains more than one vertex of the first model, by combining the vertices contained within the one grid cell into a resultant vertex having a position that is a function of the positions of the vertices contained within the one grid cell; and

means for storing the simplified model for subsequent use in displaying the object.

28. A method for execution by a data processor to prepare a representation of an object for display on a display means, wherein the object is represented by a plurality of vertices and planar faces each having boundaries defined in terms of the plurality of vertices, the method comprising the steps of:

generating a first model of the object that represents the object'"'"'s original geometry by partitioning the planar faces of the object into a plurality of non-overlapping planar sub-faces each having boundaries defined in terms of the plurality of vertices of the object;

partitioning space enclosing the first model into a plurality of grid cells;

generating a simplified model of the object by combining, in response to a condition wherein one of the plurality of grid cells contains more than one vertex of the first model, the vertices contained within the one grid cell into a resultant vertex having a position that is a function of the positions of the vertices contained within the one grid cell; and

storing the simplified model for subsequent use in displaying the object.