“Edge subdivision schemes and the construction of smooth vector fields” by Wang, Weiwei, Tong, Desbrun and Schröder

Vertex- and face-based subdivision schemes are now routinely used in geometric modeling and computational science, and their primal/dual relationships are well studied. In this paper, we interpret these schemes as defining bases for discrete differential 0- resp. 2-forms, and complete the picture by introducing edge-based subdivision schemes to construct the missing bases for discrete differential 1-forms. Such subdivision schemes map scalar coefficients on edges from the coarse to the refined mesh and are intrinsic to the surface. Our construction is based on treating vertex-, edge-, and face-based subdivision schemes as a joint triple and enforcing that subdivision commutes with the topological exterior derivative. We demonstrate our construction for the case of arbitrary topology triangle meshes. Using Loop’s scheme for 0-forms and generalized half-box splines for 2-forms results in a unique generalized spline scheme for 1-forms, easily incorporated into standard subdivision surface codes. We also provide corresponding boundary stencils. Once a metric is supplied, the scalar 1-form coefficients define a smooth tangent vector field on the underlying subdivision surface. Design of tangent vector fields is made particularly easy with this machinery as we demonstrate.

1. Arnold, D. N., Falk, R. S., and Winther, R. 2006. Finite Element Exterior Calculus, Homological Techniques, and Applications. Acta Numerica 15.Google Scholar
2. Biermann, H., Levin, A, and Zorin, D. 2000. Piecewise Smooth Subdivision Surfaces with Normal Control. Comp. Graphics (ACM/SIGGRAPH Proc.), 113–120. Google ScholarDigital Library
3. Bossavit, A 1998. Computational Electromagnetism. Academic Press, Boston.Google Scholar
4. Catmull, E, and Clark, J. 1978. Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes. Comp. Aid Des. 10, 6, 350–355.Google ScholarCross Ref
5. Desbrun, M., Kanso. E., and Tong, Y. 2005. Discrete Differential Forms for Computational Modeling. In Discrete Differential Geometry, E. Grinspun, P. Schröder, and M. Desbrun, Eds., Course Notes. ACM SIGGRAPH.Google Scholar
6. Doo, D., and Sabin, M. 1978. Analysis of the Behaviour of Recursive Division Surfaces near Extraordinary Points. Comp. Aid. Des. 10, 6, 356–360.Google ScholarCross Ref
7. Dyn, N., Gregory, J. A. and Levin, D. 1987. A 4-point Interpolatory Subdivision Scheme for Curve Design, Comput. Aided Geom. Des. 4, 4, 257–268.Google ScholarDigital Library
8. Elcott, S., Tong, Y, Kanso, E., Schröder P., and Desbrun, M. 2005. Stable, Circulation-Preserving, Simplicial Fluids. Submitted for Publication.Google Scholar
9. Grinspun. E., Krysl, P. and Schröder P 2002, CHARMS: A Simple Framework for Adaptive Simulation. ACM Trans. on Graph. 21, 3, 281–290. Google ScholarDigital Library
10. Halstead, M., Kass, M., and DeRose, T. 1993. Efficient, Fair Interpolation using Catmull-Clark Surfaces. Comp. Graphics (ACM/SIGGRAPH Proc.), 35–44. Google ScholarDigital Library
11. Hiptmair, R. 2001. Higher-Order Whitney Forms. Progress in Electromagnetics Research 32, 271–299.Google ScholarCross Ref
12. Khodakovsky, A, Schröder P, and Sweldens, W 2000. Progressive Geometry Compression. Comp. Graphics (ACM/SIGGRAPH Proc.), 271–278. Google ScholarDigital Library
13. Kobbelt, L. 2000. √3 Subdivision. Comp. Graphics (ACM/SIGGRAPH Proc.), 103–112. Google ScholarDigital Library
14. Litke, N., Levin, A, and Schröder P 2001. Fitting Subdivision Surfaces. In Visualization ’01, 319–324. Google ScholarDigital Library
15. Loop, C. 1987. Smooth Subdivision Surfaces Based on Triangles. Master’s thesis, University of Utah, Department of Mathematics.Google Scholar
16. Oswald, P, and Schröder, P. 2003. Composite Primal/Dual √3 Subdivision Schemes. Comput. Aided Geom. Des. 20, 5, 135–164. Google ScholarDigital Library
17. Prautzsch, H., Boehm W. and Paluszny, M. 2002. Bézier and B-Spline Techniques. Springer. Google ScholarDigital Library
18. Reif. U. 1995. A Unified Approach to Subdivision Algorithms Near Extraordinary Points. Comput. Aided Geom. Des. 12, 153–174. Google ScholarDigital Library
19. Reif, U. 1999. Analyse und Konstruktion von Subdivisionsalgorithmen für Freiform-flächen beliebiger Topologie. Shaker Verlag. Habilitationsschrift.Google Scholar
20. Reynolds, C. W. 1999. Steering Behaviors For Autonomous Characters. In Game Developers Conference.Google Scholar
21. Schlick, C. 1994. An Inexpensive BRDF Model for Physically-Based Rendering. Comput. Graph. Forum 13, 3, 233–246.Google ScholarCross Ref
22. Shi, L., and Yu, Y. 2005. Taming Liquids for Rapidly Changing Targets. In ACM/EG Symp. on Comp. Anim., 229–236. Google ScholarDigital Library
23. Shiue, L.-J., Alliez. P, Ursu, R., and Kettner, L., 2005. A Tutorial on CGAL Polyhedron for Subdivision Algorithms.Google Scholar
24. Stam, J. 1998. Exact Evaluation of Catmull-Clark Subdivision Surfaces at Arbitrary Parameter Values. Comp. Graphics (ACM/SIGGRAPH Proc.), 395–404. Google ScholarDigital Library
25. Tong, Y, Lombeyda, S., Hirani, A. N., and Desbrun, M. 2003. Discrete Multiscale Vector Field Decomposition. ACM Trans. on Graph. 22, 3, 445–452. Google ScholarDigital Library
26. Turk, G. 2001. Texture Synthesis on Surfaces. Comp. Graphics (ACM/SIGGRAPH Proc.), 347–354. Google ScholarDigital Library
27. Wang, K. 2006. Online Companion to “Edge Subdivision Schemes and the Con struction of Smooth Vector Fields”. Tech. rep., Caltech. Google ScholarDigital Library
28. Warren, J., and Weimer H. 2001. Subdivision Methods for Geometric Design: A Constructive Approach, first ed. Morgan Kaufman Publishers. Google ScholarDigital Library
29. Whitney. H. 1957. Geometric Integration Theory. Princeton University Press.Google Scholar
30. Zorin, D., and Kristjansson, D. 2002. Evaluation of Piecewise Smooth Subdivision Surfaces. Visual Computer 18, 5–6, 299–315.Google ScholarCross Ref
31. Zorin, D., and Schröder P., Eds. 2000. Subdivision for Modeling and Animation. Course Notes. ACM SIGGRAPH.Google Scholar
32. Zorin, D. 2000. A Method for Analysis of C1-Continuity of Subdivision Surfaces. SIAM J. Numer. Anal. 37, 5, 1677–1708. Google ScholarDigital Library
33. Zorin, D. 2000. Smoothness of Subdivision on Irregular Meshes. Constructive Approximation 16, 3, 359–397.Google ScholarCross Ref