Optimizing octree motion representation for 3D animation

ABSTRACT

Geometry compression is the coding of 3D geometric data in a form that requires less space to store and less bandwidth to transmit. Animated geometry compression is the compression of temporal sequences of geometric data. An octree-based motion representation method in which a small set of motion vectors are generated for each frame by analyzing the motion between consecutive frames was proposed in a previous research. The goal of this paper is to optimize the octree-based animated geometry compression algorithm by storing the motion vectors at non-leaf nodes in contrast to the original method where motion vectors are stored only in leaf nodes. Some leaf nodes do not need to store the motion vectors by inheriting their parents' motion vectors. This method especially benefits the animation where most regions have simple movement and small area has complicated movements. The proposed technique will always perform better than the original method. In some cases, it may have much better compression ratio than the original method. This new approach is easy to implement on top of original octree-based algorithm and has faster encoding and decoding speed.

REFERENCES

• 1: M. Alexa and W. Müller, Representing Animations by Principal Components. Computer Graphics Forum, vol. 19, pp. 411--418, 2000.
• 2: Chandrajit L. Bajaj , Valerio Pascucci , Guozhong Zhuang, Progressive compressive and transmission of arbitrary triangular meshes, Proceedings of the conference on Visualization '99: celebrating ten years, p.307-316, October 1999, San Francisco, California, United States
• 3: F. Bossen, On The Art Of Compressing Three-Dimensional Polygonal Meshes And Their Associated Properties: cole Polytechnique Fdrale de Lausanne (EPFL), 1999.
• 4: Hector M. Briceño , Pedro V. Sander , Leonard McMillan , Steven Gortler , Hugues Hoppe, Geometry videos: a new representation for 3D animations, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 5: Daniel Cohen-Or , David Levin , Offir Remez, Progressive compression of arbitrary triangular meshes, Proceedings of the conference on Visualization '99: celebrating ten years, p.67-72, October 1999, San Francisco, California, United States
• 6: Michael Deering, Geometry compression, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.13-20, September 1995 [doi>10.1145/218380.218391]
• 7: Nick Foster , Ronald Fedkiw, Practical animation of liquids, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.23-30, August 2001 [doi>10.1145/383259.383261]
• 8: Nick Foster , Dimitris Metaxas, Modeling water for computer animation, Communications of the ACM, v.43 n.7, p.60-67, July 2000 [doi>10.1145/341852.341864]
• 9: A. Fournier , D. Y. Montuno, Triangulating Simple Polygons and Equivalent Problems, ACM Transactions on Graphics (TOG), v.3 n.2, p.153-174, April 1984 [doi>10.1145/357337.357341]
• 10: Pierre-Marie Gandoin , Olivier Devillers, Progressive lossless compression of arbitrary simplicial complexes, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 11: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 12: Lawrence Ibarria , Jarek Rossignac, Dynapack: space-time compression of the 3D animations of triangle meshes with fixed connectivity, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 13: Z. Karni and C. Gotsman, Compression of soft-body animation sequences. Computers & Graphics, vol. 28, pp. 25--34, 2004.
• 14: Andrei Khodakovsky , Peter Schröder , Wim Sweldens, Progressive geometry compression, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.271-278, July 2000 [doi>10.1145/344779.344922]
• 15: Jerome Edward Lengyel, Compression of time-dependent geometry, Proceedings of the 1999 symposium on Interactive 3D graphics, p.89-95, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300533]
• 16: J. Li and C. C. Kuo, Progressive coding of 3D graphic models. In Proceedings of IEEE Multimedia and Systems, 1998.
• 17: Renato Pajarola , Jarek Rossignac, Compressed Progressive Meshes, IEEE Transactions on Visualization and Computer Graphics, v.6 n.1, p.79-93, January 2000 [doi>10.1109/2945.841122]
• 18: Jovan Popović , Hugues Hoppe, Progressive simplicial complexes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.217-224, August 1997 [doi>10.1145/258734.258852]
• 19: Jarek Rossignac, Edgebreaker: Connectivity Compression for Triangle Meshes, IEEE Transactions on Visualization and Computer Graphics, v.5 n.1, p.47-61, January 1999 [doi>10.1109/2945.764870]
• 20: Raimund Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Computational Geometry: Theory and Applications, v.1 n.1, p.51-64, July 1991 [doi>10.1016/S0925-7721(99)00042-5]
• 21: Gabriel Taubin , André Guéziec , William Horn , Francis Lazarus, Progressive forest split compression, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.123-132, July 1998 [doi>10.1145/280814.280834]
• 22: G. Taubin and J. Rossignac, 3D Geometry Compression. In ACM SIGGRPAH 98 Course Notes 21, Orlando, Florida, 1998.
• 23: Gabriel Taubin , Jarek Rossignac, Geometric compression through topological surgery, ACM Transactions on Graphics (TOG), v.17 n.2, p.84-115, April 1998 [doi>10.1145/274363.274365]
• 24: C. Touma and C. Gotsman, Triangle Mesh Compression. In Proceedings of 24th Conference on Graphics Interface (GI-98), San Francisco, 1998.
• 25: Jinghua Zhang , Charles B. Owen, Octree-based Animated Geometry Compression, Proceedings of the Conference on Data Compression, p.508, March 23-25, 2004

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Keywords:
animated geometry compression, motion vectors, octree, trilinear interpolation