System, method, and computer program product for optimization of a scene graph

• US 6,995,765 B2
• Filed: 07/13/2001
• Issued: 02/07/2006
• Est. Priority Date: 07/13/2001
• Status: Expired due to Term

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: Vicarious Visions Inc. (Microsoft Corporation)
• Inventors: Boudier, Pierre S.
• Primary Examiner(s): Chauhan, Ulka J.
• Assistant Examiner(s): Santiago, Enrique L.
• Application Number:
  US09/903,504
• Publication Number:
  US 20030011637A1
• Time in Patent Office: 1,670 Days
• Field of Search: 345/771, 345/419, 345/420, 345/421, 345/423, 345/424, 345/426, 345/427, 345/428, 345/440, 345/441, 345/473, 345/474, 345/475, 345/581, 345/582, 345/583, 345/584, 345/585, 345/586, 345/587, 345/501, 345/502, 345/503, 345/504, 345/505, 345/506, 345/519, 345/520, 715/764, 715/771, 715/853
• US Class Current: 345/428
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

The invention described herein is a system, method, and computer program product for optimization of a scene graph. The system includes an optimization base that contains a set of specific atomic optimizations. The system also includes an optimization registry that lists each atomic optimization, parameters associated with each optimization, and priority information relating to the necessary order in which optimizations must be performed. The system also includes an optimization manager which creates, configures, and applies an optimization process to an input scene graph. The system further includes an optimization configuration module for accepting user input to the optimization process. The method includes the steps of receiving an input scene graph, creating the optimization process, applying the optimization process to the input scene graph, and post-optimization processing. The optimization process can be performed for any of a number of purposes, such as the enhancement of scene graph traversal time, the enhancement of drawing time, the reduction of memory usage, improved efficiency of data manipulation, and the targeting of a specific rendering platform.

Claims

1. A system for optimization of a scene graph, comprising:

an optimization base comprising logic for at least one atomic optimization;

an optimization registry listing said at least one atomic optimization, and further listing parameter and priority information associated with said at least one atomic optimization;

an optimization manager for creating, configuring, and applying an optimization process to an input scene graph, wherein said optimization process comprises logic for an atomic optimization; and

an optimization configuration manager for accepting user configuration information to said optimization process, said user configuration information comprising selection of one or more of said at least one atomic optimization.

2. The system of claim 1, further comprising a user interface through which a user can provide said user configuration information to said optimization configuration manager.

3. The system of claim 2, wherein said user interface is provided to a user by a modeler that produces the scene graph to be optimized.

4. The system of claim 1, wherein said user configuration information comprises a specification of parameter values associated with said selected atomic optimization.

5. The system of claim 1, wherein said at least one atomic optimization comprises a collapse geometry optimization.

6. The system of claim 1, wherein said at least one atomic optimization comprises a collapse hierarchy optimization.

7. The system of claim 1, wherein said at least one atomic optimization comprises a convert image optimization.

8. The system of claim 1, wherein said at least one atomic optimization comprises a convert transform optimization.

9. The system of claim 1, wherein said at least one atomic optimization comprises a create bounding boxes optimization.

10. The system of claim 1, wherein said at least one atomic optimization comprises a flatten hierarchy optimization.

11. The system of claim 1, wherein said at least one atomic optimization comprises a generate macro texture optimization.

12. The system of claim 1, wherein said at least one atomic optimization comprises a normalize texture coordinates optimization.

13. The system of claim 1, wherein said at least one atomic optimization comprises a promote attributes optimization.

14. The system of claim 1, wherein said at least one atomic optimization comprises a remove attributes optimization.

15. The system of claim 1, wherein said at least one atomic optimization comprises a resize image optimization.

16. The system of claim 1, wherein said at least one atomic optimization comprises a share attributes optimization.

17. The system of claim 1, wherein said at least one atomic optimization comprises a spatial partition optimization.

18. The system of claim 1, wherein said at least one atomic optimization comprises a strip triangles optimization.

19. The system of claim 1, wherein said at least one atomic optimization comprises a transform alpha optimization.

20. The system of claim 1, wherein said at least one atomic optimization comprises a vertex blending optimization.

21. A method of optimization of a scene graph, comprising the steps of:

a. receiving an input scene graph;

b. creating an optimization process; and

c. applying the optimization process to the input scene graph to create a scene graph optimized for at least one of

enhancement of traversal time,

enhancement of drawing time,

reduction of memory usage,

efficiency of data manipulation, and

targeting a specific rendering platform,

wherein said step b comprises the steps of;

i. receiving user input identifying an atomic optimization and any associated parameters;

ii. accessing the atomic optimization via an optimization registry;

iii. incorporating the atomic optimization into the optimization process;

iv. if the user input comprises parameters associated with the optimization, configuring the optimization process according to the parameters; and

v. if the user input does not comprise parameters, configuring the optimization process according to default parameters.

22. The method of claim 21, wherein the atomic optimization comprises a collapse geometry optimization.

23. The method of claim 21, wherein the atomic optimization comprises a collapse hierarchy optimization.

24. The method of claim 21, wherein the atomic optimization comprises a convert image optimization.

25. The method of claim 21, wherein the atomic optimization comprises a convert transform optimization.

26. The method of claim 21, wherein the atomic optimization comprises a create bounding boxes optimization.

27. The method of claim 21, wherein the atomic optimization comprises a flatten hierarchy optimization.

28. The method of claim 21, wherein the atomic optimization comprises a generate macro texture optimization.

29. The method of claim 21, wherein the atomic optimization comprises a normalize texture coordinates optimization.

30. The method of claim 21, wherein the atomic optimization comprises a promote attributes optimization.

31. The method of claim 21, wherein the atomic optimization comprises a remove attributes optimization.

32. The method of claim 21, wherein the atomic optimization comprises a resize image optimization.

33. The method of claim 21, wherein the atomic optimization comprises a share attributes optimization.

34. The method of claim 21, wherein the atomic optimization comprises a spatial partition optimization.

35. The method of claim 21, wherein the atomic optimization comprises a strip triangles optimization.

36. The method of claim 21, wherein the atomic optimization comprises a transform alpha optimization.

37. The method of claim 21, wherein the atomic optimization comprises a vertex blending optimization.

38. The method of claim 21, further comprising the step of:

d. performing post optimization processing.

39. The method of claim 21, further comprising the step of:

d. outputting an optimized scene graph.

40. A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer that optimizes a scene graph, said computer readable program code means comprising:

a. computer readable program code means for causing the computer to receive an input scene graph;

b. computer readable program code means for causing the computer to create an optimization process; and

c. computer readable program code means for causing the computer to apply the optimization process to the input scene graph to create a scene graph optimized for at least one of

enhancement of traversal time,

enhancement of drawing time,

reduction of memory usage,

efficiency of data manipulation, and

targeting a specific rendering platform,

wherein said computer readable program code means b comprises;

i. computer readable program code means for causing the computer to receive user input identifying an atomic optimization and any associated parameters;

ii. computer readable program code means for causing the computer to access the atomic optimization via an optimization registry;

iii. computer readable program code means for causing the computer to incorporate the atomic optimization into the optimization process;

iv. computer readable program code means for causing the computer to configure the optimization process according to the parameters, if the user input comprises parameters associated with the optimization; and

v. computer readable program code means for causing the computer to configure the optimization process according to default parameters, if the user input does not comprise parameters.

41. The computer program product of claim 40, wherein the atomic optimization comprises a collapse geometry optimization.

42. The computer program product of claim 40, wherein the atomic optimization comprises a collapse hierarchy optimization.

43. The computer program product of claim 40, wherein the atomic optimization comprises a convert image optimization.

44. The computer program product of claim 40, wherein the atomic optimization comprises a convert transform optimization.

45. The computer program product of claim 40, wherein the atomic optimization comprises a create bounding boxes optimization.

46. The computer program product of claim 40, wherein the atomic optimization comprises a flatten hierarchy optimization.

47. The computer program product of claim 40, wherein the atomic optimization comprises a generate macro texture optimization.

48. The computer program product of claim 40, wherein the atomic optimization comprises a normalize texture coordinates optimization.

49. The computer program product of claim 40, wherein the atomic optimization comprises a promote attributes optimization.

50. The computer program product of claim 40, wherein the atomic optimization comprises a remove attributes optimization.

51. The computer program product of claim 40, wherein the atomic optimization comprises a resize image optimization.

52. The computer program product of claim 40, wherein the atomic optimization comprises a share attributes optimization.

53. The computer program product of claim 40, wherein the atomic optimization comprises a spatial partition optimization.

54. The computer program product of claim 40, wherein the atomic optimization comprises a strip triangles optimization.

55. The computer program product of claim 40, wherein the atomic optimization comprises a transform alpha optimization.

56. The computer program product of claim 40, wherein the atomic optimization comprises a vertex blending optimization.

57. The computer program product of claim 40, further comprising:

d. computer readable program code means for causing the computer to perform post optimization processing.

58. The computer program product of claim 40, further comprising:

d. computer readable program code means for causing the computer to output an optimized scene graph.

59. A method of optimization of a scene graph, comprising the steps of:

a. receiving an input scene graph;

b. creating an optimization process;

c. applying the optimization process to the input scene graph to create a scene graph optimized for at least one of

enhancement of traversal time,

enhancement of drawing time,

reduction of memory usage,

efficiency of data manipulation, and

targeting a specific rendering platform; and

d. performing post optimization processing, wherein said step d comprises the steps of;

i. performing validity checks on the optimized scene graph;

ii. creating statistics based on the optimization process; and

iii. outputting the statistics.

60. A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer that optimizes a scene graph, said computer readable program code means comprising:

first computer readable program code means for causing the computer to receive an input scene graph;

second computer readable program code means for causing the computer to create an optimization process; and

third computer readable program code means for causing the computer to apply the optimization process to the input scene graph to create a scene graph optimized for at least one of

enhancement of traversal time,

enhancement of drawing time,

reduction of memory usage,

efficiency of data manipulation, and

targeting a specific rendering platform; and

fourth computer readable program code means for causing the computer to perform post optimization processing

wherein said fourth computer readable program code means comprises;

i. computer readable program code means for causing the computer to perform validity checks on the optimized scene graph;

ii. computer readable program code means for causing the computer to create statistics based on the optimization process; and

iii. computer readable program code means for causing the computer to output the statistics.