System and method for optimizing 3D animation and textures

• US 6,538,654 B1
• Filed: 12/23/1999
• Issued: 03/25/2003
• Est. Priority Date: 12/24/1998
• Status: Expired due to Term

• Current Assignee: B3D Incorporated
• Original Assignee: B3D Incorporated
• Inventors: Rose, Anthony, Davie, Andrew D., Vuillemin, Alexis
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US09/471,722
• Time in Patent Office: 1,188 Days
• Field of Search: 345/418, 345/473, 345/474
• US Class Current: 345/473
• CPC Class Codes: G06T 13/20 3D [Three Dimensional] animation
• CPC Class Codes: G06T 15/30 Clipping
• CPC Class Codes: H04N 21/234318 by decomposing into objects, e.g. MPEG-4 objects
• CPC Class Codes: H04N 21/44012 involving rendering scenes according to scene graphs, e.g. MPEG-4 scene graphs
• CPC Class Codes: H04N 21/45452 applied to an object-based stream, e.g. MPEG-4 streams
• CPC Class Codes: H04N 21/6125 involving transmission via Internet transmission by internet of broadcast information H04H60/82
• CPC Class Codes: H04N 21/8146 involving graphical data, e.g. 3D object, 2D graphics
• CPC Class Codes: H04N 21/8541 involving branching, e.g. to different story endings

Abstract

A system and method facilitating the production, processing, and Internet distribution of 3D animated movies including 3D multipath movies. A key reduction algorithm reduces the keyframes associated with the 3D movie to facilitate the streaming of the data over the Internet. An animation optimization and texture optimization algorithm allows the system to get statistical information of the portions of the 3D object which are invisible (outside the view frame), and whose animation and texture data may thus be safely removed. If the 3D object is within the view frame, the optimization algorithm gathers information about the distance and size of the 3D object and its associated texture data within the frame. The system and method further allows creation of various versions of the 3D object from a single production process. The various versions are tagged with an identifier identifying the target platforms and media platforms in which they are suitable for display. During playback, the correct version of the 3D object is selected for display based on the detected Internet bandwidth and/or CPU speed. To stream the 3D animation content over the Internet for real-time playback, the present system and method allows the data to be divided into an upfront file and various stream files. The upfront file is downloaded prior to the playback of the movie. The stream files are streamed over the Internet and made available to the 3D engine in time for their use.

Claims

1. In a computer system for creating animation data for a 3D object appearing in a 3D animated content, the 3D object having a hierarchy of parent nodes and children nodes, each node being associated with animation data, a method for optimizing the animation data associated with each node comprising:

determining if the node is outside a view frame;

determining if any child node associated with the node is outside the view frame; and

removing the animation data associated with the node if the node and any associated child node are outside the view frame.

2. The method of claim 1, wherein the animation data is stored in a series of source keyframes and removing the animation data comprises:

setting a threshold value for the node to infinity;

selecting a keyframe from the series of source keyframes;

storing the keyframe into a keyframe array;

interpolating the stored keyframes in the keyframe array;

obtaining a first interpolated value based on the interpolation of the stored keyframes in the keyframe array;

obtaining a second interpolated value based on the interpolation of the source keyframes; and

computing a difference between the first interpolated value and the second interpolated value.

3. The method of claim 1 further comprising:

obtaining a distance to the node from a view plane if the node is within the view frame and the node is not obscured by other nodes; and

removing the animation data associated with the node based on the obtained distance.

4. The method of claim 3, wherein the animation data is stored in a series of source keyframes and removing the animation data further comprises:

setting a threshold value for the node based on the obtained distance;

selecting a first keyframe from the series of source keyframes;

storing the first keyframe into a keyframe array;

interpolating the stored keyframes in the keyframe array;

obtaining a first interpolated value based on the interpolation of the stored keyfraMes in the keyframe array;

obtaining a second interpolated value based on the interpolation of the source keyframes;

computing a difference between the first interpolated value and the second interpolated value;

selecting a second keyframe from the series of source keyframes if the computed difference is greater than the computed threshold value; and

storing the second keyframe into the keyframe array.

5. The method of claim 4, wherein the threshold value of the node increases as the obtained distance increases.

6. In a computer system for creating animation data for a 3D object appearing in a 3D animated content, the 3D object having a plurality of nodes, each node identifying a discrete piece of 3D geometry having a plurality of polygons, each polygon being associated with a texture map having texture data, a method for optimizing the texture data comprising:

determining if the node is outside a view frame;

indicating in a texture map array that the node is outside the view frame; and

removing the texture data associated with the node if the node is outside the view frame.

7. In a computer system for creating animation data for a 3D object appearing in a 3D animated content, the 3D object having a plurality of nodes, each node identifying a discrete piece of 3D geometry having a plurality of polygons, each polygon being associated with a texture map having texture data, a method for optimizing the texture data comprising:

retrieving the texture map for the polygon;

rendering the polygon according to the retrieved texture map onto a screen space;

computing a ratio of pixels in the texture map to pixels on the screen space, the ratio being indicative of a magnification of the texture map on the screen space;

comparing the computed ratio with a magnification value stored in a texture map array;

replacing the stored magnification value with the computed ratio if the computed ratio indicates a bigger magnification of the texture map than the stored magnification value; and

recreating the texture map according to the magnification value in the texture map array.

8. A system for optimizing animation data associated with a node of a 3D object appearing in a 3D animated content, the node having one or more children nodes, the system comprising:

means for determining if the node is outside a view frame;

means for determining if the children nodes are outside the view frame; and

means for removing the animation data associated with the node if the node and all its children nodes are outside the view frame.

9. The system of claim 8 further comprising:

means for obtaining a distance to the node from a view plane if the node is within the view frame; and

means for removing the animation data associated with the node based on the obtained distance.

10. A system for optimizing texture data in a texture map associated with a polygon making up a 3D geometry of a node of a 3D object, the system comprising:

means for determining if the node is outside a view frame;

means for determining if the node is obscured by other nodes;

means for indicating in a texture map array that the node is outside the view frame;

means for indicating in the texture map array that the node is obscured by other nodes;

means for removing the texture data associated with the node if the node is outside the view frame; and

means for removing the texture data associated with the node if the node is obscured by other nodes.

11. A system for optimizing texture data in a texture map associated with a polygon making up a 3D geometry of a node of a 3D object, the system comprising:

means for retrieving the texture map for the polygon;

means for rendering the polygon according to the retrieved texture map onto a screen space;

means for computing a ratio of pixels in the texture map to pixels on the screen space, the ratio being indicative of a magnification of the texture map on the screen space;

means for comparing the computed ratio with a magnification value stored in a texture map array;

means for replacing the stored magnification value with the computed ratio if the computed ratio indicates a bigger magnification of the texture map than the stored magnification value; and

means for recreating the texture map according to the magnification value in the texture map array.

12. A computer readable medium encoded with a computer program comprising:

a program code for optimizing animation data associated with a node of a 3D object appearing in a 3D animated content, the node having one or more children nodes, the computer program comprising instructions for;

determining if the node is outside a view frame;

determining if the children nodes are outside the view frame; and

removing the animation data associated with the node if the node and all its children nodes are outside the view frame.

13. The computer program product of claim 12 further comprising instructions for:

obtaining a distance to the node from a view plane if the node is within the view frame and the node is not obscured by other nodes; and

removing the animation data associated with the node based on the obtained distance.

14. A computer readable medium encoded with a computer program comprising:

a program code for optimizing texture data in a texture map associated with a polygon making up a 3D geometry of a node of a 3D object, the computer program comprising instructions for;

determining if the node is outside a view frame;

indicating in a texture map array that the node is outside the view frame;

indicating in the texture map array that the node is obscured by other nodes;

removing the texture data associated with the node if the node is outside the view frame; and

removing the texture data associated with the node if the node is obscured by the other nodes.

15. A computer readable medium encoded with a computer program comprising:

a program code for optimizing texture data in a texture map associated with a polygon making up a 3D geometry of a node of a 3D object, the computer program comprising instructions for;

retrieving the texture map for the polygon;

rendering the polygon according to the retrieved texture map onto a screen space;

computing a ratio of pixels in the texture map to pixels on the screen space, the ratio being indicative of a magnification of the texture map on the screen space;

comparing the computed ratio with a magnification value stored in a texture map array;

replacing the stored magnification value with the computed ratio if the computed ratio indicates a bigger magnification of the texture map than the stored magnification value; and

recreating the texture map according to the magnification value in the texture map array.