“A visibility algorithm for converting 3D meshes into editable 2D vector graphics” by Eisemann, Paris and Durand

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.

1. Appel, A. 1967. The notion of quantitative invisibility and the machine rendering of solids. In Proceedings of the 22nd National Conference, 387–393. Google ScholarDigital Library
2. Asente, P., Schuster, M., and Pettit, T. 2007. Dynamic planar map illustration. ACM Transactions on Graphics 26, 3. Proceedings of ACM SIGGRAPH. Google ScholarDigital Library
3. Attene, M., Katz, S., Mortara, M., Patané, G., Spagnuolo, M., and Tal, A. 2006. Mesh segmentation: A comparative study. In Proceedings of Shape Modelling International. Google ScholarDigital Library
4. Cole, F., Golovinskiy, A., Limpaecher, A., Barros, H. S., Finkelstein, A., Funkhouser, T., and Rusinkiewicz, S. 2008. Where do people draw lines? ACM Transactions on Graphics 27, 3. Proceedings of ACM SIGGRAPH. Google ScholarDigital Library
5. DeCarlo, D., Finkelstein, A., Rusinkiewicz, S., and Santella, A. 2003. Suggestive contours for conveying shape. ACM Transactions On Graphics 22, 3. Proceedings of ACM SIGGRAPH. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
9. Judd, T., Durand, F., and Adelson, E. H. 2007. Apparent ridges for line drawing. ACM Transactions on Graphics 26, 3. Proceedings of ACM SIGGRAPH. Google ScholarDigital Library
10. Kalnins, R. D., Markosian, L., Meier, B. J., Kowalski, M. A., Lee, J. C., Davidson, P. L., Webb, M., Hughes, J. F., and Finkelstein, A. 2002. WYSIWYG NPR: Drawing strokes directly on 3D models. ACM Transactions on Graphics 21, 3. Proceedings of ACM SIGGRAPH. Google ScholarDigital Library
11. Kann, V. 1992. On the Approximability of NP-complete Optimization Problems. PhD thesis, Royal Institute of Technology, Stockholm.Google Scholar
12. Li, W., Ritter, L., Agrawala, M., Curless, B., and Salesin, D. 2007. Interactive cutaway illustrations of complex 3D models. ACM Transactions on Graphics 26, 3. Proceedings of ACM SIGGRAPH. Google ScholarDigital Library
13. Li, W., Agrawala, M., Curless, B., and Salesin, D. 2008. Automated generation of interactive 3D exploded view diagrams. ACM Transactions on Graphics 27, 3. Proceedings of ACM SIGGRAPH. Google ScholarDigital Library
14. Mammen, A. 1989. Transparency and antialiasing algorithms implemented with the virtual pixel maps technique. Computer Graphics and Applications 9, 4. Google ScholarDigital Library
15. Newell, M. E., Newell, R. G., and Sancha, T. L. 1972. A solution to the hidden surface problem. In Proceedings of the ACM National Conference. Google ScholarDigital Library
16. Nooruddin, F. S., and Turk, G. 2003. Simplification and repair of polygonal models using volumetric techniques. IEEE Trans. Vis. Comput. Graph 9, 2, 191–205. Google ScholarDigital Library
17. Orzan, A., Bousseau, A., Winnemöller, H., Barla, P., Thollot, J., and Salesin, D. 2008. Diffusion curves: A vector representation for smooth-shaded images. ACM Transactions on Graphics 27, 3. Proceedings of ACM SIGGRAPH. Google ScholarDigital Library
18. Press, W., Teukolsky, S., Vetterling, W., and Flannery, B. 1992. Numerical Recipes in C. Cambridge University Press, Cambridge, UK.Google Scholar
19. Ryu, D. 2001. Visibility Layer Decomposition. Senior thesis, Harvard University.Google Scholar
20. Skiena, S. S. 1998. The Algorithm Design Manual. Springer-Verlag. Google ScholarDigital Library
21. Snyder, J., and Lengyel, J. 1998. Visibility sorting and compositing without splitting for image layer decompositions. In Proceedings of ACM SIGGRAPH. Google ScholarDigital Library
22. Stroila, M., Eisemann, E., and Hart, J. C. 2008. Clip art rendering of smooth isosurfaces. IEEE Transactions on Visualization and Computer Graphics 14, 1. Google ScholarDigital Library
23. Sun, J., Liang, L., Wen, F., and Shum, H.-Y. 2007. Image vectorization using optimized gradient meshes. Proceedings of ACM SIGGRAPH. Google ScholarDigital Library
24. Sutherland, I. E., Sproull, R. F., and Robert, A. S. 1974. A characterization of ten hidden-surface algorithms. ACM Computing Surveys. Google ScholarDigital Library
25. VectorTuts.com, 2008. Rendering a 2d spark plug diagram from 3d components in illustrator. http://vectortuts.com/tutroials/illustration/.Google Scholar
26. Vollick, I., Vogel, D., Agrawala, M., and Hertzmann, A. 2007. Specifying label layout styles by example. In Proc. of ACM Symposium on User Interface Software and Technology. Google ScholarDigital Library