Compression of animated geometry using a hierarchical level of detail coder

• US 6,614,428 B1
• Filed: 06/07/1999
• Issued: 09/02/2003
• Est. Priority Date: 06/08/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lengyel, Jerome E.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US09/326,968
• Time in Patent Office: 1,548 Days
• Field of Search: 345/473, 345/474, 345/475, 345/419, 345/420, 345/423, 345/428, 345/441, 395/133, 395/155, 382/100, 382/103, 382/154, 382/243
• US Class Current: 345/420
• CPC Class Codes: G06T 13/00 Animation
• CPC Class Codes: G06T 13/20 3D [Three Dimensional] animation
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109

Abstract

A space-time level of detail coder converts a time dependent geometry stream into a hierarchical structure, including levels of detail in the space and time dimensions, and expansion records. The expansion records specify how to reconstruct a mesh from deltas representing differences between levels of detail. For low bandwidth transmission, only selected expansion records need be sent depending on the appropriate level of detail of the object being represented for the current time sample.

Claims

1. A method for compressing a series of 3D meshes representing time-dependent geometry in an animation, the method comprising:

converting a matrix of vertex positions into a data structure hierarchically representing the meshes in geometric levels of detail that provide geometric scalability and temporal levels of detail that provide temporal scalability;

encoding deltas between each level of detail; and

encoding records, wherein each record specifies information for at least one of the geometric or temporal levels of detail for reconstruction of at least part of the time-dependent geometry in the animation.

2. The method of claim 1 further including:

selectively transmitting one or more of the records.

3. The method of claim 2 further including:

evaluating a screen space projection of the animation for a current time sample to determine which of the records to transmit for the current time sample.

4. The method of claim 1 wherein the converting the matrix of vertex positions into a data structure includes:

segmenting the matrix into segments that are animated independently; and

converting each of the segments into a segment data structure.

5. The method of claim 1 wherein the geometric levels of detail are coded using mesh edge collapses.

6. The method of claim 1 wherein the converting the matrix of vertex positions into a data structure includes:

converting a base mesh into a base mesh hierarchy of mesh refinements.

7. The method of claim 1 wherein the temporal levels of detail are coded using temporal edge collapses.

8. The method of claim 1 wherein the temporal levels of detail are for vertex positions and animation coefficients splined through time.

9. The method of claim 8 wherein detail is added with knot insertions.

10. The method of claim 1 wherein the temporal levels of detail are separated with wavelets.

11. A computer readable medium having instructions for performing the method of claim 1.

12. A method for selective playback of time-dependent geometry in an animation, the method comprising:

specifying a geometric level of detail for the animation;

receiving a geometric update record indicating at least part of the time-dependent geometry in the animation for the specified geometric level of detail;

specifying a temporal level of detail for the animation, wherein plural temporal levels of detail provide temporal scalability of the time-dependent geometry in the animation; and

receiving a temporal update record indicating at least part of the time-dependent geometry in the animation for the specified temporal level of detail.

13. The method of claim 12 wherein the geometric update record indicates coarsening or refinement for the specified geometric level of detail.

14. The method of claim 12 wherein a texture image to be mapped to an object in the animation is encoded hierarchically such that the texture image is represented at varying spatial resolutions, a first texture level of detail is transferred initially, and then a higher or lower texture level of detail is communicated to provide a selected texture level of detail for the texture image.

15. The method of claim 14 wherein the texture image is animated and temporal texture level of detail of the texture image is selectively increased or decreased to provide a selected temporal texture level of detail.

16. The method of claim 14 wherein a texture update record provides texture image information for the selected texture level of detail in response to a request for the selected texture level of detail.

17. A computer readable medium having software for performing the method of claim 12.

18. A method for encoding a series of 3D meshes representing moving geometry in an animation, the method comprising:

selecting a spatial or temporal dimension for inter-mesh scalability along the selected dimension in the animation;

converting a matrix of vertex positions into a data structure hierarchically representing the meshes in geometric levels of detail for intra-mesh geometric scalability and selected dimensional levels of detail for the inter-mesh scalability along the selected dimension; and

encoding update records, wherein each update record specifies information for at least one of the geometric or selected dimensional levels of detail for reconstruction of at least part of the moving geometry in the animation.

19. The method of claim 18 wherein the selected dimension is spatial and a desired position in the spatial dimension is specified through user input to control playback of the animation along the spatial dimension.

20. The method of claim 18 wherein the selected dimension is temporal and a desired granularity in the temporal dimension is specified to control temporal level of detail during playback of the animation along the time dimension.

21. In a method of compressing a series of plural geometry meshes representing time-dependent geometry in an animation, an improvement comprising:

encoding the series of plural geometry meshes in plural temporal levels of detail, wherein the plural temporal levels of detail provide temporal scalability in transmission or reconstruction of the time-dependent geometry in the animation.

22. The improvement of claim 21 wherein one or more update records include one or more temporal edge collapse/split records for vertex positions splined through time for the plural temporal levels of detail.

23. The improvement of claim 21 wherein one or more update records include one or more temporal edge collapse/split records for animation coefficients splined through time for the plural temporal levels of detail.

24. The improvement of claim 21 wherein one or more update records include wavelet coefficients for the plural temporal levels of detail.

25. A computer-readable medium storing computer-executable instructions for causing a computer programmed thereby to perform a method of compressing a series of three-dimensional geometric meshes representing moving geometry in an animation, the method comprising:

identifying a spatial or temporal dimension for inter-mesh scalability along the identified dimension in the animation; and

converting the series of three-dimensional geometric meshes into one or more hierarchical representations including geometric levels of detail that provide geometric scalability and identified dimensional levels of detail that provide the inter-mesh scalability along the identified dimension.

26. The computer-readable medium of claim 25 wherein the converting includes:

converting a base mesh for the series into a base mesh hierarchy, wherein the base mesh is a first mesh of the series.

27. The computer-readable medium of claim 25 wherein the converting includes:

converting a base mesh for the series into a base mesh hierarchy, wherein the base mesh is an average mesh for the series or is computed by non-linear optimization of transformation parameters and the base mesh.

28. The computer-readable medium of claim 25 wherein the identified dimension is time.

29. The computer-readable medium of claim 25 wherein the identified dimension is a path in space.

30. The computer-readable medium of claim 25 wherein the identified dimension is an angle in space.

31. The computer-readable medium of claim 25 wherein the identified dimension is predetermined.

32. The computer-readable medium of claim 25 further comprising:

creating one or more update records, each of the one or more update records specifying information for at least one of the levels of detail for updating at least part of the moving geometry in the animation; and

selectively transmitting the one or more update records.

33. The computer-readable medium of claim 32 wherein the selectively transmitting depends upon user input.

34. The computer-readable medium of claim 32 wherein the selectively transmitting depends upon expected focus of attention for the animation.

35. The computer-readable medium of claim 32 wherein the selectively transmitting depends upon bandwidth constraints.

36. The computer-readable medium of claim 25 wherein the converting includes:

identifying plural segments in the series and converting each of the plural segments into a segment hierarchical representation of the one or more hierarchical representations.

37. The computer-readable medium of claim 25 wherein the converting includes splining one or more identified dimension edge collapse/split records for vertex positions through time for the identified dimensional levels of detail.

38. The computer-readable medium of claim 25 wherein the converting includes splining one or more identified dimension edge collapse/split records for animation coefficients through time for the identified dimensional levels of detail.

39. The computer-readable medium of claim 25 wherein the converting includes computing wavelet coefficients for the identified dimensional levels of detail.

40. A computer-readable medium storing moving geometry for an animation, the moving geometry comprising:

a base three-dimensional geometric mesh comprising basic portions of one or more hierarchical representations of the animation, wherein the one or more hierarchical representations include plural geometric levels of detail that provide geometric intra-mesh scalability and plural other levels of detail that provide inter-mesh scalability along a spatial or temporal dimension; and

one or more update records, each of the one or more update records specifying information for at least one of the levels of detail for reconstruction of at least part of the moving geometry in the animation.

41. In a method of playing back time-dependent geometry in an animation, an improvement comprising:

specifying a temporal level of detail for the animation, wherein plural temporal levels of detail provide temporal scalability of the time-dependent geometry in the animation; and

receiving additional time-dependent geometry information for the animation at the specified temporal level of detail.

42. The improvement of claim 41 further comprising:

before the specifying, receiving base time-dependent geometry information for the animation at a base level of detail.

43. In a method of facilitating playback of time-dependent geometry in an animation, an improvement comprising:

receiving an indication of a temporal level of detail for the animation, wherein plural temporal levels of detail provide temporal scalability of the time-dependent geometry in the animation; and

sending additional time-dependent geometry information for the animation at the indicated temporal level of detail.

44. The improvement of claim 43 further comprising:

before the receiving, sending base time-dependent geometry information for the animation at a base level of detail.

45. A computer-readable medium storing computer-executable instructions for causing a computer programmed thereby to perform a method of playing back moving geometry in an animation, the method comprising:

identifying a spatial or temporal dimension for inter-mesh scalability along the identified dimension in the animation;

specifying a geometric level of detail for the animation; and

receiving time-dependent geometry information for the animation at the specified geometric level of detail;

specifying an identified dimensional level of detail for the animation; and

receiving time-dependent geometry information for the animation at the specified identified dimensional level of detail.

46. A computer-readable medium storing computer-executable instructions for causing a computer programmed thereby to perform a method of compressing a series of plural three-dimensional geometric meshes for an animation, each of the plural three-dimensional geometric meshes including three-dimensional coordinate values for each of plural points for the animation, the method comprising:

storing the series of plural three-dimensional geometric meshes in a data structure, wherein the data structure includes plural geometry records, each of the plural geometry records including three-dimensional geometry information for a corresponding three-dimensional geometric mesh of the plural three-dimensional geometric meshes, wherein the data structure aligns each of the plural points for the animation between meshes across the series of plural three-dimensional geometric meshes; and

compressing the series of plural three-dimensional geometric meshes.

47. The computer-readable medium of claim 46 wherein the compressing includes:

converting the series of plural three-dimensional geometric meshes into a hierarchical representation including plural inter-mesh levels of detail across the series of plural three-dimensional geometric meshes and plural geometric levels of detail for each of the plural geometry records.