“Skinning cubic Bézier splines and Catmull-Clark subdivision surfaces” by Liu, Jacobson and Gingold
Conference:
Type(s):
Title:
- Skinning cubic Bézier splines and Catmull-Clark subdivision surfaces
Session/Category Title: Smash and Stretch
Presenter(s)/Author(s):
Abstract:
Smooth space deformation has become a vital tool for the animation and design of 2D and 3D shapes. Linear methods, under the umbrella term of “linear blend skinning”, are the de facto standard for 3D animations. Unfortunately such approaches do not trivially extend to deforming vector graphics, such as the cubic Bézier splines prevalent in 2D or subdivision surfaces in 3D. We propose a variational approach to reposition the control points of cubic Bézier splines and Catmull-Clark subdivision surfaces—or any linear subdivision curves or surfaces—to produce curves or surfaces which match a linear blend skinning deformation as closely as possible. Exploiting the linearity of linear blend skinning, we show how this optimization collapses neatly into the repeated multiplication of a matrix per handle. We support C0, C1, G1, and fixed-angle continuity constraints between adjacent Bézier curves in a spline. Complexity scales linearly with respect to the number of input curves and run-time performance is fast enough for real-time editing and animation of high-resolution shapes.
References:
1. Adobe Systems Inc., 2014. Photoshop CS6’s Liquify tool. http://www.adobe.com/photoshop/.
2. Baran, I., and Popović, J. 2007. Automatic rigging and animation of 3D characters. ACM Trans. Graph. 26, 3, 72:1–72:8.
3. Baran, I., Lehtinen, J., and Popović, J. 2010. Sketching clothoid splines using shortest paths. In Comput. Graph. Forum.
4. Barbič, J., Sin, F., and Grinspun, E. 2012. Interactive editing of deformable simulations. ACM Trans. Graph..
5. Beier, T., and Neely, S. 1992. Feature-based image metamorphosis. In Proc. SIGGRAPH.
6. Blender Foundation, 2008. Big Buck Bunny. http://www.bigbuckbunny.org.
7. Botsch, M., and Kobbelt, L. 2004. An intuitive framework for real-time freeform modeling. ACM Trans. Graph. 23, 3, 630–634.
8. Bouaziz, S., Deuss, M., Schwartzburg, Y., Weise, T., and Pauly, M. 2012. Shape-up: Shaping discrete geometry with projections. In Comput. Graph. Forum.
9. Davis, T. A., and Hager, W. W. 1999. Modifying a sparse Cholesky factorization. SIAM Journal on Matrix Analysis and Applications 20, 3, 606–627.
10. Der, K. G., Sumner, R. W., and Popović, J. 2006. Inverse kinematics for reduced deformable models. ACM Trans. Graph..
11. DeRose, A. D. 1985. Geometric Continuity: A Parametrization Independent Measure of Continuity for Computer Aided Geometric Design. PhD thesis, EECS Department, University of California, Berkeley.
12. Fowler, B., and Bartels, R. 1993. Constraint-based curve manipulation. IEEE Comput. Graph. Appl. 13, 5, 43–49.
13. Frisken, S. 2008. Efficient curve fitting. Journal of Graphics, GPU, and Game Tools 13, 2, 37–54.Cross Ref
14. Hager, W. W. 1989. Updating the inverse of a matrix. SIAM Review 31, 2, 221–239.
15. Hildebrandt, K., Schulz, C., Tycowicz, C. V., and Polthier, K. 2011. Interactive surface modeling using modal analysis. ACM Trans. Graph. 30, 5, 119:1–119:11.
16. Hormann, K., and Floater, M. S. 2006. Mean value coordinates for arbitrary planar polygons. ACM Trans. Graph..
17. Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph..
18. Jacobson, A., Baran, I., Popović, J., and Sorkine, O. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4, 78:1–78:8.
19. Jacobson, A., Baran, I., Kavan, L., Popović, J., and Sorkine, O. 2012. Fast automatic skinning transformations. ACM Trans. Graph..
20. Jacobson, A., Kavan, L., and Sorkine, O. 2013. Robust inside-outside segmentation using generalized winding numbers. ACM Trans. Graph. 32, 4, 33:1–33:12.
21. James, D. L., and Twigg, C. D. 2005. Skinning mesh animations. ACM Trans. Graph. 24, 3, 399–407.
22. Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3, 71:1–71:9.
23. Kavan, L., Gerszewski, D., Bargteil, A., and Sloan, P.-P. 2011. Physics-inspired upsampling for cloth simulation in games. ACM Trans. Graph. 30, 4, 93:1–93:9.
24. Kim, M., Hyun, K., Kim, J., and Lee, J. 2009. Synchronized multi-character motion editing. ACM Trans. Graph. 28, 3.
25. Krishnamurthy, V., and Levoy, M. 1996. Fitting smooth surfaces to dense polygon meshes. In Proc. SIGGRAPH.
26. Liao, Z., Hoppe, H., Forsyth, D., and Yu, Y. 2012. A subdivision-based representation for vector image editing. IEEE TVCG 18, 11, 1858–1867.
27. Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Trans. Graph. 27, 3, 78:1–78:10.
28. McCrae, J., and Singh, K. 2009. Sketching piecewise clothoid curves. Computers & Graphics 33, 4, 452–461.
29. Milliron, T., Jensen, R. J., Barzel, R., and Finkelstein, A. 2002. A framework for geometric warps and deformations. ACM Trans. Graph. 21, 1, 20–51.
30. Niessner, M., Loop, C., Meyer, M., and DeRose, T. 2012. Feature-adaptive gpu rendering of catmull-clark subdivision surfaces. ACM Trans. Graph. 31, 1, 6:1–6:11.
31. Noris, G., Hornung, A., Simmons, M., Sumner, R., and Gross, M. 2013. Topology-driven vectorization of clean line drawings. ACM Transactions on Graphics 32, 1, 4:1–4:11.
32. Olsen, L., Samavati, F. F., Sousa, M. C., and Jorge, J. A. 2009. Sketch-based modeling: A survey. Computers & Graphics.
33. Pixar, 2014. Opensubdiv. http://graphics.pixar.com/opensubdiv/.
34. Plass, M., and Stone, M. 1983. Curve-fitting with piecewise parametric cubics. SIGGRAPH Comput. Graph..
35. Schaefer, S., McPhail, T., and Warren, J. 2006. Image deformation using moving least squares. ACM Trans. Graph..
36. Schmitt, F. J. M., Barsky, B. A., and Du, W.-H. 1986. An adaptive subdivision method for surface-fitting from sampled data. SIGGRAPH Comput. Graph. 20, 4, 179–188.
37. Schneider, P. J. 1990. Graphics gems. ch. An Algorithm for Automatically Fitting Digitized Curves, 612–626.
38. Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In Proceedings of the 1968 23rd ACM national conference, ACM, 517–524.
39. Shewchuk, J. R. 1996. Triangle: Engineering a 2D quality mesh generator and delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering, vol. 1148 of Lecture Notes in Computer Science. Springer-Verlag, 203–222.
40. Si, H., 2003. TetGen: A 3D delaunay tetrahedral mesh generator. http://tetgen.berlios.de.
41. Wang, W., Pottmann, H., and Liu, Y. 2006. Fitting b-spline curves to point clouds by curvature-based squared distance minimization. ACM Trans. Graph. 25, 2, 214–238.
42. Weber, O., and Gotsman, C. 2010. Controllable conformal maps for shape deformation and interpolation. ACM Trans. Graph. 29, 4, 78:1–78:11.
43. Weber, O., Sorkine, O., Lipman, Y., and Gotsman, C. 2007. Context-aware skeletal shape deformation. Comput. Graph. Forum 26, 3, 265–274.Cross Ref
44. Weber, O., Ben-Chen, M., and Gotsman, C. 2009. Complex barycentric coordinates with applications to planar shape deformation. Comput. Graph. Forum 28, 2, 587–597.Cross Ref
45. Weber, O., Ben-Chen, M., Gotsman, C., and Hormann, K. 2011. A complex view of barycentric mappings. In Proc. SGP, vol. 30, 1533–1542.
46. Zheng, J. M., Chan, K. W., and Gibson, I. 1998. A new approach for direct manipulation of free-form curve. Comput. Graph. Forum 17, 3, 327–334.Cross Ref
47. Zhou, K., Huang, X., Xu, W., Guo, B., and Shum, H.-Y. 2007. Direct manipulation of subdivision surfaces on gpus. ACM Trans. Graph. 26, 3 (July).
48. Zimmermann, J., Nealen, A., and Alexa, M. 2007. Silsketch: automated sketch-based editing of surface meshes. In Proceedings of the 4th Eurographics workshop on Sketch-based interfaces and modeling (SBIM), 23–30.
