A visibility algorithm for converting 3D meshes into editable 2D vector graphics

ABSTRACT

Artists often need to import and embellish 3D models coming from CAD-CAM into 2D vector graphics software to produce, e.g., brochures or manuals. Current automatic solutions tend to result, at best, in a 2D triangle soup and artists often have to trace over 3D renderings. We describe a method to convert 3D models into 2D layered vector illustrations that respect visibility and facilitate further editing. Our core contribution is a visibility method that can partition a mesh into large components that can be layered according to visibility. Because self-occluding objects and objects forming occlusion cycles cannot be represented by layers without being cut, we introduce a new cut algorithm that uses a graph representation of the mesh and curvature-aware geodesic distances.

REFERENCES

• 1: Arthur Appel, The notion of quantitative invisibility and the machine rendering of solids, Proceedings of the 1967 22nd national conference, p.387-393, January 1967, Washington, D.C., United States [doi>10.1145/800196.806007]
• 2: Paul Asente , Mike Schuster , Teri Pettit, Dynamic planar map illustration, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 3: M. Attene , S. Katz , M. Mortara , G. Patane , M. Spagnuolo , A. Tal, Mesh Segmentation - A Comparative Study, Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006, p.7, June 14-16, 2006 [doi>10.1109/SMI.2006.24]
• 4: Forrester Cole , Aleksey Golovinskiy , Alex Limpaecher , Heather Stoddart Barros , Adam Finkelstein , Thomas Funkhouser , Szymon Rusinkiewicz, Where do people draw lines?, ACM SIGGRAPH 2008 papers, August 11-15, 2008, Los Angeles, California
• 5: Doug DeCarlo , Adam Finkelstein , Szymon Rusinkiewicz , Anthony Santella, Suggestive contours for conveying shape, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 6: Eisemann, E., Winnemöller, H., Hart, J. C., and Salesin, D. 2008. Stylized vector art from 3d models with region support. Computer Graphics Forum 27, 4. Proceedings of the Eurographics Symposium on Rendering.
• 7: Grabli, S., Turquin, E., Durand, F., and Sillion, F. 2004. Programmable style for npr line drawing. In Rendering Techniques (Proceedings of the Eurographics Symposium on Rendering), ACM Press, 33--44.
• 8: Isenberg, T., Carpendale, M. S. T., and Sousa, M. C. 2005. Breaking the pixel barrier. In Proceedings of the Eurographics Workshop on Computational Aesthetics in Graphics, Visualization and Imaging.
• 9: Tilke Judd , Frédo Durand , Edward Adelson, Apparent ridges for line drawing, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 10: Robert D. Kalnins , Lee Markosian , Barbara J. Meier , Michael A. Kowalski , Joseph C. Lee , Philip L. Davidson , Matthew Webb , John F. Hughes , Adam Finkelstein, WYSIWYG NPR: drawing strokes directly on 3D models, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 11: Kann, V. 1992. On the Approximability of NP-complete Optimization Problems. PhD thesis, Royal Institute of Technology, Stockholm.
• 12: Wilmot Li , Lincoln Ritter , Maneesh Agrawala , Brian Curless , David Salesin, Interactive cutaway illustrations of complex 3D models, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 13: Wilmot Li , Maneesh Agrawala , Brian Curless , David Salesin, Automated generation of interactive 3D exploded view diagrams, ACM SIGGRAPH 2008 papers, August 11-15, 2008, Los Angeles, California
• 14: Abraham Mammen, Transparency and Antialiasing Algorithms Implemented with the Virtual Pixel Maps Technique, IEEE Computer Graphics and Applications, v.9 n.4, p.43-55, July 1989 [doi>10.1109/38.31463]
• 15: M. E. Newell , R. G. Newell , T. L. Sancha, A solution to the hidden surface problem, Proceedings of the ACM annual conference, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800193.569954]
• 16: Fakir S. Nooruddin , Greg Turk, Simplification and Repair of Polygonal Models Using Volumetric Techniques, IEEE Transactions on Visualization and Computer Graphics, v.9 n.2, p.191-205, April 2003 [doi>10.1109/TVCG.2003.1196006]
• 17: Alexandrina Orzan , Adrien Bousseau , Holger Winnemöller , Pascal Barla , Joëlle Thollot , David Salesin, Diffusion curves: a vector representation for smooth-shaded images, ACM SIGGRAPH 2008 papers, August 11-15, 2008, Los Angeles, California
• 18: Press, W., Teukolsky, S., Vetterling, W., and Flannery, B. 1992. Numerical Recipes in C. Cambridge University Press, Cambridge, UK.
• 19: Ryu, D. 2001. Visibility Layer Decomposition. Senior thesis, Harvard University.
• 20: Steven S. Skiena, The algorithm design manual, Springer-Verlag New York, Inc., New York, NY, 1997
• 21: John Snyder , Jed Lengyel, Visibility sorting and compositing without splitting for image layer decompositions, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.219-230, July 1998 [doi>10.1145/280814.280878]
• 22: Matei Stroila , Elmar Eisemann , John Hart, Clip Art Rendering of Smooth Isosurfaces, IEEE Transactions on Visualization and Computer Graphics, v.14 n.1, p.135-145, January 2008 [doi>10.1109/TVCG.2007.1058]
• 23: Jian Sun , Lin Liang , Fang Wen , Heung-Yeung Shum, Image vectorization using optimized gradient meshes, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 24: Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]
• 25: VectorTuts.com, 2008. Rendering a 2d spark plug diagram from 3d components in illustrator. http://vectortuts.com/tutroials/illustration/.
• 26: Ian Vollick , Daniel Vogel , Maneesh Agrawala , Aaron Hertzmann, Specifying label layout style by example, Proceedings of the 20th annual ACM symposium on User interface software and technology, October 07-10, 2007, Newport, Rhode Island, USA [doi>10.1145/1294211.1294252]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
      I.3.8 Applications

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Theory

Keywords:
NPR, geometry processing, vector graphics, visibility