Data-driven curvature for real-time line drawing of dynamic scenes

ABSTRACT

This article presents a method for real-time line drawing of deforming objects. Object-space line drawing algorithms for many types of curves, including suggestive contours, highlights, ridges, and valleys, rely on surface curvature and curvature derivatives. Unfortunately, these curvatures and their derivatives cannot be computed in real-time for animated, deforming objects. In a preprocessing step, our method learns the mapping from a low-dimensional set of animation parameters (e.g., joint angles) to surface curvatures for a deforming 3D mesh. The learned model can then accurately and efficiently predict curvatures and their derivatives, enabling real-time object-space rendering of suggestive contours and other such curves. This represents an order-of-magnitude speedup over the fastest existing algorithm capable of estimating curvatures and their derivatives accurately enough for many different types of line drawings. The learned model can generalize to novel animation sequences and is also very compact, typically requiring a few megabytes of storage at runtime. We demonstrate our method for various types of animated objects, including skeleton-based characters, cloth simulation, and blend-shape facial animation, using a variety of nonphotorealistic rendering styles.

An important component of our system is the use of dimensionality reduction for differential mesh data. We show that Independent Component Analysis (ICA) yields localized basis functions, and gives superior generalization performance to that of Principal Component Analysis (PCA).

REFERENCES

• 1: Bartlett, M., Movellan, J., and Sejnowski, T. 2002. Face recognition by independent component analysis. IEEE Trans. Neural Netw. 13, 6, 1450--1464.
• 2: Bell, A. J. and Sejnowski, T. J. 1997. The independent components of natural scenes are edge filters. Vision Res. 37, 3327--3338.
• 3: Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 4: Yong Cao , Petros Faloutsos , Frédéric Pighin, Unsupervised learning for speech motion editing, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 5: David Cohen-Steiner , Jean-Marie Morvan, Restricted delaunay triangulations and normal cycle, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777839]
• 6: Dorin Comaniciu , Peter Meer, Mean Shift: A Robust Approach Toward Feature Space Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.5, p.603-619, May 2002 [doi>10.1109/34.1000236]
• 7: Pierre Comon, Independent component analysis, a new concept?, Signal Processing, v.36 n.3, p.287-314, April 1994 [doi>10.1016/0165-1684(94)90029-9]
• 8: Doug DeCarlo , Adam Finkelstein , Szymon Rusinkiewicz, Interactive rendering of suggestive contours with temporal coherence, Proceedings of the 3rd international symposium on Non-photorealistic animation and rendering, June 07-09, 2004, Annecy, France [doi>10.1145/987657.987661]
• 9: Doug DeCarlo , Adam Finkelstein , Szymon Rusinkiewicz , Anthony Santella, Suggestive contours for conveying shape, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 10: Doug DeCarlo , Szymon Rusinkiewicz, Highlight lines for conveying shape, Proceedings of the 5th international symposium on Non-photorealistic animation and rendering, August 04-05, 2007, San Diego, California [doi>10.1145/1274871.1274881]
• 11: Udo Diewald , Tobias Preuβer , Martin Rumpf, Anisotropic Diffusion in Vector Field Visualization on Euclidean Domains and Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.6 n.2, p.139-149, April 2000 [doi>10.1109/2945.856995]
• 12: Eigensatz, M., Sumner, R. W., and Pauly, M. 2008. Curvature-Domain shape processing. In Proceedings of the EuroGraphics Computer Graphics Forum 27, 2, 241--250.
• 13: Gershon Elber , Elaine Cohen, Hidden curve removal for free form surfaces, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.95-104, September 1990, Dallas, TX, USA
• 14: Bruce Gooch , Peter-Pike J. Sloan , Amy Gooch , Peter Shirley , Richard Riesenfeld, Interactive technical illustration, Proceedings of the 1999 symposium on Interactive 3D graphics, p.31-38, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300526]
• 15: Todd Goodwin , Ian Vollick , Aaron Hertzmann, Isophote distance: a shading approach to artistic stroke thickness, Proceedings of the 5th international symposium on Non-photorealistic animation and rendering, August 04-05, 2007, San Diego, California [doi>10.1145/1274871.1274880]
• 16: Paul S. Heckbert , Michael Garland, Optimal triangulation and quadric-based surface simplification, Computational Geometry: Theory and Applications, v.14 n.1-3, p.49-65, Nov. 1999 [doi>10.1016/S0925-7721(99)00030-9]
• 17: Aaron Hertzmann , Denis Zorin, Illustrating smooth surfaces, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.517-526, July 2000 [doi>10.1145/344779.345074]
• 18: Hyvärinen, A. 1999. Fast and robust fixed-point algorithms for independent component analysis. IEEE Trans. Neural Netw. 10, 3, 626--634.
• 19: Victoria Interrante , Henry Fuchs , Stephen Pizer, Enhancing Transparent Skin Surfaces with Ridge and Valley Lines, Proceedings of the 6th conference on Visualization '95, p.52, October 29-November 03, 1995
• 20: Doug L. James , Kayvon Fatahalian, Precomputing interactive dynamic deformable scenes, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 21: Doug L. James , Christopher D. Twigg, Skinning mesh animations, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 22: Tilke Judd , Frédo Durand , Edward Adelson, Apparent ridges for line drawing, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 23: Evangelos Kalogerakis , Patricio Simari , Derek Nowrouzezahrai , Karan Singh, Robust statistical estimation of curvature on discretized surfaces, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 24: Yunjin Lee , Lee Markosian , Seungyong Lee , John F. Hughes, Line drawings via abstracted shading, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 25: J. P. Lewis , Matt Cordner , Nickson Fong, Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.165-172, July 2000 [doi>10.1145/344779.344862]
• 26: Lee Markosian , Michael A. Kowalski , Daniel Goldstein , Samuel J. Trychin , John F. Hughes , Lubomir D. Bourdev, Real-time nonphotorealistic rendering, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.415-420, August 1997 [doi>10.1145/258734.258894]
• 27: Meyer, M., Desbrun, M., Schröder, P., and Barr, A. H. 2002. Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and Mathematics III, 35--57.
• 28: Alex Mohr , Michael Gleicher, Building efficient, accurate character skins from examples, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 29: Alex Ni , Kyuman Jeong , Seungyong Lee , Lee Markosian, Multi-scale line drawings from 3D meshes, Proceedings of the 2006 symposium on Interactive 3D graphics and games, March 14-17, 2006, Redwood City, California [doi>10.1145/1111411.1111435]
• 30: Nocedal, J. and Wright, S. J. 1999. Numerical Optimization. Springer-Verlag.
• 31: J. D. Northrup , Lee Markosian, Artistic silhouettes: a hybrid approach, Proceedings of the 1st international symposium on Non-photorealistic animation and rendering, p.31-37, June 05-07, 2000, Annecy, France [doi>10.1145/340916.340920]
• 32: Nowrouzezahrai, D., Kalogerakis, E., and Fiume, E. 2009. Shadowing dynamic scenes with arbitrary BRDFs. In Proceedings of the EuroGraphics Conference. To appear.
• 33: Nowrouzezahrai, D., Kalogerakis, E., Simari, P., and Fiume, E. 2008. Shadowed relighting of dynamic geometry with 1d BRDFs. In Proceedings of the EuroGraphics Conference .
• 34: Derek Nowrouzezahrai , Patricio Simari , Evangelos Kalogerakis , Karan Singh , Eugene Fiume, Compact and efficient generation of radiance transfer for dynamically articulated characters, Proceedings of the 5th international conference on Computer graphics and interactive techniques in Australia and Southeast Asia, December 01-04, 2007, Perth, Australia [doi>10.1145/1321261.1321288]
• 35: Yutaka Ohtake , Alexander Belyaev , Hans-Peter Seidel, Ridge-valley lines on meshes via implicit surface fitting, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 36: Pauly, M., Keiser, R., and Gross, M. 2003. Multi-Scale feature extraction on point-sampled surfaces. In Proceedings of EuroGraphics Conference. 281--289.
• 37: Polthier, K. 2002. Polyhedral surfaces of constant mean curvature. Ph.D. thesis, TU-Berlin.
• 38: Szymon Rusinkiewicz, Estimating Curvatures and Their Derivatives on Triangle Meshes, Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium, p.486-493, September 06-09, 2004 [doi>10.1109/3DPVT.2004.54]
• 39: Rusinkiewicz, S. 2007. Trimesh2 library. http://www.cs.princeton.edu/gfx/proj/trimesh2/.
• 40: Szymon Rusinkiewicz , Michael Burns , Doug DeCarlo, Exaggerated shading for depicting shape and detail, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 41: Takafumi Saito , Tokiichiro Takahashi, Comprehensible rendering of 3-D shapes, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.197-206, September 1990, Dallas, TX, USA
• 42: Peter-Pike Sloan , Jan Kautz , John Snyder, Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 43: G. Taubin, Estimating the tensor of curvature of a surface from a polyhedral approximation, Proceedings of the Fifth International Conference on Computer Vision, p.902, June 20-23, 1995
• 44: Jean-Philippe Thirion , Alexis Gourdon, The 3D marching lines algorithm, Graphical Models and Image Processing, v.58 n.6, p.503-509, Nov. 1996 [doi>10.1006/gmip.1996.0042]
• 45: Romain Vergne , Pascal Barla , Xavier Granier , Christophe Schlick, Apparent relief: a shape descriptor for stylized shading, Proceedings of the 6th international symposium on Non-photorealistic animation and rendering, June 09-11, 2008, Annecy, France [doi>10.1145/1377980.1377987]
• 46: Robert Y. Wang , Kari Pulli , Jovan Popović, Real-time enveloping with rotational regression, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 47: Weisberg, S. 2003. Applied Linear Regression, 3rd ed. Wiley/Interscience.
• 48: Georges Winkenbach , David H. Salesin, Rendering parametric surfaces in pen and ink, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.469-476, August 1996 [doi>10.1145/237170.237287]
• 49: Shin Yoshizawa , Alexander Belyaev , Hideo Yokota , Hans-Peter Seidel, Fast and Faithful Geometric Algorithm for Detecting Crest Lines on Meshes, Proceedings of the 15th Pacific Conference on Computer Graphics and Applications, p.231-237, October 29-November 02, 2007 [doi>10.1109/PG.2007.26]
• 50: Jingyi Yu , Xiaotian Yin , Xianfeng Gu , Leonard McMillan , Steven Gortler, Focal surfaces of discrete geometry, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Line and curve generation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Design

Keywords:
Independent Component Analysis (ICA), Real-time curvature, data-driven curvature, neural network regression, real-time line drawing, real-time nonphotorealistic rendering for deforming objects