US5448686A — Multi-resolution graphic representation employing…

Claim 1

Independent Claim 156 words

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.

Claim 2

Independent Claim 156 words

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.

Claim 3

Dependent Claim 39 words

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.

Claim 4

Dependent Claim 46 words

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.

Claim 5

Dependent Claim 51 words

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.

Claim 6

Dependent Claim 58 words

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.

Claim 7

Dependent Claim 58 words

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.

Claim 8

Dependent Claim 67 words

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.

Claim 9

Dependent Claim 31 words

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.

Claim 10

Dependent Claim 59 words

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.

Claim 11

Dependent Claim 63 words

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.

Claim 12

Dependent Claim 47 words

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.

Claim 13

Dependent Claim 101 words

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.

Claim 14

Dependent Claim 104 words

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.

Claim 15

Independent Claim 166 words

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.

Claim 16

Independent Claim 166 words

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.

Claim 17

Dependent Claim 26 words

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.

Claim 18

Dependent Claim 33 words

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.

Claim 19

Dependent Claim 51 words

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.

Claim 20

Dependent Claim 58 words

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.

Claim 21

Dependent Claim 55 words

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.

Claim 22

Dependent Claim 21 words

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

Claim 23

Dependent Claim 21 words

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

Claim 24

Dependent Claim 121 words

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.

Claim 25

Dependent Claim 121 words

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.

Claim 26

Dependent Claim 94 words

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.

Claim 27

Dependent Claim 24 words

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

Claim 28

Dependent Claim 25 words

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.

Claim 29

Dependent Claim 63 words

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.

Claim 30

Dependent Claim 163 words

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.

Claim 31

Dependent Claim 163 words

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.

Claim 32

Independent Claim 179 words

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.

Claim 33

Independent Claim 179 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1998-09-04	1999-03-06	1999-09-05	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2002-09-04	2003-03-06	2003-09-05	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2006-09-04	2007-03-06	2007-09-05	$7700.00	Window Closed / Lapsed

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

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag