“Multiresolution signal processing for meshes” by Guskov, Sweldens and Schroeder

We generalize basic signal processing tools such as downsampling, upsampling, and filters to irregular connectivity triangle meshes. This is accomplished through the design of a non-uniform relaxation procedure whose weights depend on the geometry and we show its superiority over existing schemes whose weights depend only on connectivity. This is combined with known mesh simplification methods to build subdivision and pyramid algorithms. We demonstrate the power of these algorithms through a number of application examples including smoothing, enhancement, editing, and texture mapping.

1. BURT, P. J., AND ADELSON, E. H. Laplacian Pyramid as a Compact Image Code. IEEE Trans. Commun. 31, 4 (1983), 532-540.
2. DAUBECHIES, I., GUSKOV, I., AND SWELDENS, W. Regularity of irregular subdivision. Const. Approx. (1999), to appear.
3. DE BOOR, C. A multivariate divided differences. Approximation Theory VIII 1 (1995), 87-96.
4. DE BOOR, C., AND RON, A. On multivariate polynomial interpolation. Const~: Approx. 6 (1990), 287-302.
5. DEROSE, T., KASS, M., AND TRUONG, T. Subdivision Surfaces in Character Animation. Computer Graphics (SIGGRAPH ’98 Proceedings) (1998), 85-94.
6. DESBRUN, M., MEYER, M., SCHR(3DER, P., AND BARR, A. Implicit Fairing of Irregular Meshes using Diffusion and Curvature Flow. In Computer Graphics (SIGGRAPH ’99 Proceedings), Aug. 1999.
7. DOBKIN, D., AND KIRKPATRICK, D. A Linear Algorithm for Determining the Separation of Convex Polyhedra. Journal of Algorithms 6 (1985), 381-392.
8. ECK, M., DEROSE, T., DUCHAMP, T., HOPPE, H., LOUNSBERY, M., AND STUETZLE, W. Multiresolution Analysis of Arbitrary Meshes. In Computer Graphics (SIGGRAPH ’95 P1vceedings), 173-182, 1995.
9. FLOATER, M. S. Parameterization and Smooth Approximation of Surface Triangulations. Computer Aided Geometric Design 14 (1997), 231-250.
10. FORNBERG, B. Generation of finite difference formulas on arbitrarily spaced grids. Math. Comput. 51 (1988), 699-706.
11. GARLAND, M., AND HECKBERT, P. S. Surface Simplification Using Quadric Error Metrics. In Computer Graphics (SIGGRAPH ’96 P1vceedings), 209-216, 1996.
12. GUSKOV, I. Multivariate Subdivision Schemes and Divided Differences. Tech. rep., Department of Mathematics, Princeton University, 1998.
13. HECKBERT, P. S., AND GARLAND, M. Survey of Polygonal Surface Simplification Algorithms. Tech. rep., Carnegie Mellon University, 1997.
14. HOPPE, H. Progressive Meshes. In Computer Graphics (SIGGRAPH ’96 P~vceedings), 99-108, 1996.
15. KHODAKOVSKY, A., AND SCHRC)DER, P. Fine Level Feature Editing for Subdivision Surfaces. In ACM Solid Modeling Symposium, 1999.
16. KOBBELT, L. Discrete Fairing. In P1vceedings of the Seventh IMA Conference on the Mathematics of Sulfaces, 101-131, 1997.
17. KOBBELT, L., CAMPAGNA, S., AND SEIDEL, H.-P. A General Framework for Mesh Decimation. In P1vceedings of Graphics Intelface, 1998.
18. KOBBELT, L., CAMPAGNA, S., VORSATZ, J., AND SEIDEL, H.-P. Interactive Multi-Resolution Modeling on Arbitrary Meshes. In Computer Graphics (SIC- GRAPH ’98 Proceedings), 105-114, 1998.
19. LEE, A., SWELDENS, W., SCHR<3DER, P., COWSAR, L., AND DOBKIN, D. MAPS: Multiresolution Adaptive Parametrization of Surfaces. In Computer Graphics (SIGGRAPH ’98 P1vceedings), 95-104, 1998.
20. Ll~vY, B., AND MALLET, J. Non-Distorted Texture Mapping for Sheared Triangulated Meshes. In Computer Graphics (SIGGRAPH ’98 P1vceedings), 343- 352, July 1998.
21. MORETON, H. P., AND SI~QUIN, C. H. Functional optimization for fair surface design. In Computer Graphics (SIGGRAPH ’92 P1vceedings), vol. 26, 167-176, July 1992.
22. SCHR<3DER, P., AND ZORIN, D., Eds. Course Notes: Subdivision for Modeling and Animation. ACM SIGGRAPH, 1998.
23. SINGH, K., AND FIUME, E. Wires: A Geometric Deformation Technique. In Computer Graphics (SIGGRAPH ’98 P1vceedings), 405-414, 1998.
24. SPANIER, E. H. Algebraic Topology. McGraw-Hill, New York, 1966.
25. SWELDENS, W. The lifting scheme: A construction of second generation wavelets. SlAM J. Math. Anal. 29, 2 (1997), 511-546.
26. TAUBIN, G. A Signal Processing Approach to Fair Surface Design. In Computer Graphics (SIGGRAPH’ 95 Proceedings), 351-358, 1995.
27. TAUBIN, G., ZHANG, Y., AND GOLUB, G. Optimal Surface Smoothing as Filter Design. Tech. Rep. 90237, IBM T.J. Watson Research, March 1996.
28. WELCH, W., AND WITKIN, A. Free-Form Shape Design Using Triangulated Surfaces. In Computer Graphics (SIGGRAPH ’94 Proceedings), 247-256, July 1994.
29. ZORIN, D., SCHR(3DER, P., AND SWELDENS, W. Interactive Multiresolution Mesh Editing. In Computer Graphics (SIGGRAPH ’97 P1vceedings), 259-268, 1997.