Method of hierarchical static scene simplification

• US 6,307,558 B1
• Filed: 03/03/1999
• Issued: 10/23/2001
• Est. Priority Date: 03/03/1999
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Mao, Crusoe
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Santiago, Enrique L
• Application Number:
  US09/262,171
• Time in Patent Office: 965 Days
• Field of Search: 345/419, 345/420, 345/421, 345/423, 345/428
• US Class Current: 345/428
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A method of scene simplification includes concurrently simplifying a plurality of objects in a scene represented by a hierarchical scene graph. The objects are represented as polygonal meshes and the hierarchical scene graph includes a plurality of nodes, each node storing a mesh. The scene is a three dimensional scene and the objects are representations of three dimensional objects. Concurrently simplifying the plurality of objects includes determining an initial least level of detail polygon reduction ratio (LPPR) for at least one mesh, generating levels of detail variables for at least one mesh using the LPRR, and generating a simplified version of at least one mesh by using the levels of detail variables.

Claims

1. A method of scene simplification comprising:

concurrently simplifying a plurality of polygonal meshes in a scene represented by a hierarchical scene graph, the hierarchical scene graph comprising a plurality of nodes, each node storing a mesh;

by

determining an initial least level of detail polygon reduction ratio (LPPR) for at least one mesh;

generating levels of detail variables for at least one mesh using the LPRR;

generating a simplified version of at least one mesh by using the levels of detail variables; and

rendering the simplified scene on a display;

wherein determining the LPRR comprises;

computing the surface area and polygon density for a mesh;

determining a predicted polygon density for the mesh within a three dimensional bounding box;

obtaining a reference density; and

generating the LPRR for the mesh as a function of the three dimensional bounding box, the reference density, and the predicted polygon density of the mesh.

2. The method of claim 1, wherein the scene comprises a three dimensional scene and the polygonal meshes comprise representations of three dimensional objects.

3. The method of claim 1, further comprising determining a LPRR, generating levels of detail variables, and generating a simplified version, for all meshes in the hierarchical scene graph.

4. The method of claim 1, wherein the simplified mesh comprises the same topological type as the mesh'"'"'s original geometric representation, but with a smaller number of vertices.

5. The method of claim 1, wherein determining the LPRR comprises using a scene polygon reduction ratio to determine, at least in part, the LPRR.

6. The method of claim 1, wherein the levels of detail variables comprise at least a switch in distance and a mesh polygon reduction ratio.

7. The method of claim 1, wherein the data structure comprises an octree.

8. An article comprising:

a machine readable medium having a plurality of machine readable instructions, wherein when the instructions are executed by a processor, the instructions implement concurrent simplification of a plurality of polygonal meshes in a scene represented by a hierarchical scene graph, the hierarchical scene graph comprising a plurality of nodes, each node storing a mesh;

by

determining an initial least level of detail polygon reduction ratio (LPPR) for at least one mesh;

generating levels of detail variables for at least one mesh using the LPRR;

generating a simplified version of at least one mesh by using the levels of detail variables; and

rendering the simplified scene on a display;

wherein determining the LPRR comprises;

computing the surface area and polygon density for a mesh;

determining a predicted polygon density for the mesh within a three dimensional bounding box;

obtaining a reference density; and

generating the LPRR for the mesh as a function of the three dimensional bounding box, the reference density, and the predicted polygon density of the mesh.

9. The article of claim 8, wherein the scene comprises a three dimensional scene and the polygonal meshes comprise representations of three dimensional objects.

10. The article of claim 8, wherein the simplified mesh comprises the same topological type the mesh'"'"'s original geometric representation, but with a smaller number of vertices.

11. The article of claim 8, wherein instructions to determine the LPRR comprise instructions for using a scene polygon reduction ratio to determine, at least in part, the LPRR.

12. The article of claim 8, wherein the levels of detail variables comprise at least a switch in distance and a mesh polygon reduction ratio.

13. A method of simplifying a scene represented by a hierarchical scene graph having polygonal meshes as nodes comprising:

for each mesh in the hierarchical scene graph, determining each mesh'"'"'s initial least level of detail polygon reduction ratio (LPRR);

for each mesh, generating levels of detail variables using the mesh'"'"'s LPRR, the levels of detail variables including a switch in distance and a mesh polygon reduction ratio (MPRR);

for each mesh, generating a simplified version of the mesh using the levels of detail variables; and

rendering the simplified scene on a display;

wherein determining LPRRs comprises;

computing the surface area and polygon density for each mesh;

building a data structure to partition the space of the scene;

inserting each mesh'"'"'s surface area and density into the data structure;

analyzing the data structure to obtain a predicted polygon density for each mesh within a three dimensional bounding box;

sorting the meshes according to each mesh'"'"'s predicted polygon density;

using a convolution method to obtain a reference density; and

determining a LPRR for each mesh as a function of the mesh'"'"'s three dimensional bounding box, the reference density and the mesh'"'"'s predicted polygon density.

14. An article comprising:

a machine readable medium having a plurality of machine readable instructions, wherein when the instructions are executed by a processor, the instructions simplify a scene represented by a hierarchical scene graph having polygonal meshes as nodes by determining, for each mesh in the hierarchical scene graph, each mesh'"'"'s initial least level of detail polygon reduction ratio (LPRR), generating, for each mesh, levels of detail variables using the mesh'"'"'s LPRR, the levels of detail variables including a switch in distance and a mesh polygon reduction ratio (MPRR), generating, for each mesh, a simplified version of the mesh using the levels of detail variables; and

rendering the simplified scene on a display;

wherein instructions to determine the LPRRs comprise instructions to;

compute the surface area and polygon density for each mesh;

build a data structure to partition the space of the scene;

insert each mesh'"'"'s surface area and density into the data structure;

analyze the data structure to obtain a predicted polygon density for each mesh within a three dimensional bounding box;

sort the meshes according to each mesh'"'"'s predicted polygon density;

use a convolution method to obtain a reference density; and

determine a LPRR for each mesh as a function of the mesh'"'"'s three dimensional bounding box, the reference density and the mesh'"'"'s predicted polygon density.