Optimized mixed media rendering

• US 20030222883A1
• Filed: 05/31/2002
• Published: 12/04/2003
• Est. Priority Date: 05/31/2002
• Status: Active Grant

• Current Assignee: MK Systems USA Inc. (JP Morgan Chase & Co)
• Original Assignee: Envivio Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Deniau, Eric, Cazoulat, Renaud
• Granted Patent: US 7,439,982 B2
• Time in Patent Office: Days
• US Class Current: 345/582
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 2210/61 Scene description

Abstract

A method and system for rendering mixed media at a presentation workstation in response to a mixed media stream, in which the amount of computation is minimized. A tree structure includes nodes, each of which might point to sub-trees, and each of which designates a geometric object, a transformation to be applied to a geometric object, or a time-varying presentation. A scene includes nodes for each element in the scene. Depending from these would be nodes describing aspects of those elements, such as their texture and shape. A root node join the descriptions of each of the objects in the scene. Optimizing the amount of computation includes selecting nodes in the tree and calculating how to render each sub-tree. When possible, rendering information is calculated for only those portions of objects that will ultimately be shown to the user.

Claims

1. A method, including steps of

generating a first data graph, in response to a set of values associated with at least one object included in a data stream associated with a mixed media presentation;

generating a second data graph responsive to a set of changes in said values included in said first data graph;

processing a set of nodes included in said second data graph substantially depth first and generating a list of said changes responsive to an order in which said nodes were processed;

processing said set of nodes substantially depth first and updating a set of objects in response to said order of said list;

rendering said objects responsive to said order;

whereby said objects that are visible or audible to a user are rendered and said objects that have not been changed or are not visible or audible to said user are not rendered.

2. A method as in claim 1, wherein said first data graph includes values associated with at least one of the following aspects of said object:

size, color, position, angular position, texture, transparency and shape.

3. A method as in claim 2, wherein said aspects are used to animate said object.

4. A method as in claim 1, wherein said second data graph includes information about rendering changes in said values associated with at least one of the following aspects of said object:

size, color, position, rotation, texture, transparency, and shape.

5. A method as in claim 1, wherein said changes are responsive to input from a user.

6. A method as in claim 1, wherein the order in which said changes are described on said list is responsive to their relative depth in said second data graph.

7. A method as in claim 1, wherein said step of processing said first data graph is performed substantially depth first.

8. A method as in claim 1, wherein said step of processing said second data graph is performed substantially depth first.

9. A method as in claim 1, wherein said step of rendering said objects includes generating a bit map and a set of pixels.

10. A method as in claim 1, wherein said data stream includes at least one of the following:

MPEG-1, MPEG-2, H.261, H.263, ITU-T or MPEG-4.

11. A method as in claim 1, wherein said step of rendering is responsive to the relative transparency of said objects.

12. An apparatus, including

a means for generating a first data graph including a set of nodes, in response to values associated with at least one object included in said mixed media scene;

a means for generating a second data graph, including a set of nodes, wherein said second data graph is responsive to one or more changes in said first data graph;

a means for processing said second data graph so as to generate a list of said one or more changes, wherein the order of one or more changes on said list is responsive to a location in said second data graph;

a means for processing said second data graph and updating objects in response to said list;

a means for rendering said objects in an order responsive to the order in which they were updated such that said objects that are visible or audible to a user are rendered and said objects that are not visible or audible to said user are not rendered.

13. An apparatus as in claim 12, wherein said means for generating a first data graph include a binary scene decoder.

14. An apparatus as in claim 12, wherein said means for generating a second data graph include a binary scene decoder.

15. An apparatus as in claim 12, wherein said means for processing said second data graph include a binary scene decoder.

16. An apparatus as in claim 12, wherein at least some of said nodes in said first scene graph are linked to a corresponding said node in said second data graph.

17. An apparatus as in claim 12, wherein said first data graph includes a scene graph.

18. An apparatus as in claim 12, wherein first data graph includes values associated with at least one of the following aspects of said object:

size, color, position, rotation, texture, transparency, and shape.

19. An apparatus as in claim 12, wherein said second data graph includes a direct acylic graph.

20. An apparatus as in claim 12, wherein said second data graph includes information about rendering changes in values associated with at least one of the following aspects of said object:

size, color, position, rotation, texture, transparency, and shape.

21. An apparatus as in claim 12, wherein said changes are responsive to input from a user.

22. An apparatus as in claim 12, wherein said means for processing process said second data graph method substantially depth first.

23. A apparatus as in claim 12, wherein said means for rendering includes a rasterizer.

24. An apparatus, including

a computing device, having a memory;

a binary scene decoder stored in said memory, including a first data graph and a second data graph, wherein said first data graph having been generated by said binary scene decoder in response to a scene included in a mixed media presentation, and said second data graph having been generated in response to a set of changes in values associated with said first data graph; and

a rasterizer having an input from said second data graph, wherein said input is used to rendering objects that are visible or audible to a user and not render objects that are not visible or audible or which have already been rendered.

25. An apparatus as in claim 24, wherein said first data graph includes a set of nodes at least one of which is linked to a set of nodes included in said second data graph.

26. An apparatus as in claim 24, wherein said first data graph is a scene graph.

27. An apparatus as in claim 24, wherein first data graph includes values associated with at least one of the following aspects of said object:

size, color, position, rotation, texture, transparency, and shape.

28. An apparatus as in claim 24, wherein said second data graph includes a direct acylic graph.

29. An apparatus as in claim 24, wherein said second data graph includes information about rendering changes in values associated with at least one of the following aspects of said object:

size, color, position, rotation, texture, transparency, and shape.

30. An apparatus as in claim 24, wherein said changes are responsive to input from a user.

31. A memory storing information including instructions, wherein the instructions are executable by a processor, the instructions including method, including instructions of

generating a first data graph, in response to a set of values associated with at least one object included in a data stream associated with a mixed media presentation;

generating a second data graph responsive to a set of changes in said values included in said first data graph;

processing a set of nodes included in said second data graph substantially depth first and generating a list of changes responsive to said nodes

processing said set of nodes substantially depth first and updating a set of objects in response to an ordering of said list;

rendering said objects responsive to the order in which they were updated

whereby said objects that are visible or audible to a user are rendered and said objects that are not visible or audible to said user are not rendered.

32. A memory as in claim 31, wherein said first data graph includes values associated with at least one of the following aspects of said object:

size, color, position, angular position, texture, transparency and shape.

33. A memory as in claim 32, wherein said aspects are used to animate said object.

34. A method as in claim 31, wherein said second data graph includes information about rendering changes in said values associated with at least one of the following aspects of said object:

size, color, position, rotation, texture, transparency, and shape.

35. A memory as in claim 31, wherein said changes are responsive to input from a user.

36. A memory as in claim 31, wherein the order in which said changes are described on said list is responsive to their relative depth in said second data graph.

37. A memory as in claim 31, wherein said instruction for processing said first data graph is performed substantially depth first.

38. A memory as in claim 31, wherein said instruction for processing said second data graph is performed substantially depth first.

39. A memory as in claim 31, wherein said instruction for rendering said object s includes generating a bit map and a set of pixels.

40. A memory as in claim 31, wherein said data stream includes at least one of the following:

MPEG-1, MPEG-2, H.261, H.263, ITU-T or MPEG-4.

41. A memory as in claim 31, wherein said instruction for rendering is responsive to the relative transparency of said objects.