“Algebraic Smooth Occluding Contours” by Capouellez, Dai, Hertzmann and Zorin

  • ©Ryan Capouellez, Jiacheng Dai, Aaron Hertzmann, and Denis Zorin




    Algebraic Smooth Occluding Contours

Session/Category Title: Colorful Topics in Imaging




    Computing occluding contours is a key step in 3D non-photorealistic rendering, but producing smooth contours with consistent visibility has been a notoriously-challenging open problem. This paper describes the first general-purpose smooth surface construction for which the occluding contours can be computed in closed form. Given an input mesh and camera viewpoint, we show how to approximate the mesh with a G1 piecewise-quadratic surface, for which the occluding contours are piecewise-rational curves in image-space. We show that this method produces smooth contours with consistent visibility much more efficiently than the state-of-the-art.


    1. Arthur Appel. 1967. The Notion of Quantitative Invisibility and the Machine Rendering of Solids. In Proceedings of the 1967 22nd National Conference(ACM ’67). ACM, 387–393. https://doi.org/10.1145/800196.806007
    2. Pierre Bénard and Aaron Hertzmann. 2019. Line Drawings from 3D Models. Foundations and Trends in Computer Graphics and Vision 11, 1-2 (2019), 1–159. https://doi.org/10.1561/0600000075
    3. Pierre Bénard, Aaron Hertzmann, and Michael Kass. 2014. Computing Smooth Surface Contours with Accurate Topology. ACM Trans. Graph. 33, 2, Article 19 (2014), 21 pages. https://doi.org/10.1145/2558307
    4. Marcel Campen, Ryan Capouellez, Hanxiao Shen, Leyi Zhu, Daniele Panozzo, and Denis Zorin. 2021. Efficient and robust discrete conformal equivalence with boundary. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1–16.
    5. Roberto Cipolla and Peter Giblin. 2000. Visual Motion of Curves and Surfaces. Cambridge University Press.
    6. Wolfgang Dahmen. 1989. Smooth piecewise quadric surfaces. In Mathematical methods in computer aided geometric design. Elsevier, 181–193.
    7. Doug DeCarlo. 2012. Depicting 3D shape using lines. In Proc. SPIE, Vol. 8291. 8291 – 8291 – 16. https://doi.org/10.1117/12.916463
    8. Philippe Decaudin. 1996. Cartoon Looking Rendering of 3D Scenes. Research Report 2919. INRIA. http://phildec.users.sf.net/Research/RR-2919.php
    9. Elmar Eisemann, Holger Winnemöller, John C. Hart, and David Salesin. 2008. Stylized Vector Art from 3D Models with Region Support. In Proceedings of the Nineteenth Eurographics Conference on Rendering(EGSR ’08). Eurographics Association, 1199–1207. https://doi.org/10.1111/j.1467-8659.2008.01258.x
    10. Gershon Elber and Elaine Cohen. 1990. Hidden Curve Removal for Free Form Surfaces. In Proceedings of the 17th Annual Conference on Computer Graphics and Interactive Techniques(SIGGRAPH ’90). ACM, 95–104. https://doi.org/10.1145/97879.97890
    11. Rafael Sendra Ferrer, Sonia Pérez Díaz, and F Winkler. 2008. Rational algebraic curves: a computer algebra approach. Springer Berlin.
    12. Mark Gillespie, Boris Springborn, and Keenan Crane. 2021. Discrete conformal equivalence of polyhedral surfaces. ACM Transactions on Graphics 40, 4 (2021).
    13. Xianfeng David Gu, Feng Luo, Jian Sun, and Tianqi Wu. 2018. A discrete uniformization theorem for polyhedral surfaces. Journal of Differential Geometry 109, 2 (2018), 223–256.
    14. Ying He, Miao Jin, Xianfeng Gu, and Hong Qin. 2005. A C1 globally interpolatory spline of arbitrary topology. In International Workshop on Variational, Geometric, and Level Set Methods in Computer Vision. Springer, 295–306.
    15. Aaron Hertzmann and Denis Zorin. 2000. Illustrating Smooth Surfaces. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques(SIGGRAPH ’00). ACM Press/Addison-Wesley Publishing Co., 517–526. https://doi.org/10.1145/344779.345074
    16. Tobias Isenberg, Nick Halper, and Thomas Strothotte. 2002. Stylizing silhouettes at interactive rates: From silhouette edges to silhouette strokes. In Computer Graphics Forum, Vol. 21. 249–258. https://doi.org/10.1111/1467-8659.00584
    17. B. Jüttler. 1998. Triangular Bézier surface patches with a linear normal vector field. In The mathematics of surfaces, VIII (R. Cripps, ed.). Info. Geom., Winchester, 431–446.
    18. B. Jüttler and M.L. Sampoli. 2000. Hermite interpolation by piecewise polynomial surfaces with rational offsets. Computer Aided Geometric Design 17, 4 (2000), 361–385.
    19. D. Kirsanov, P. V. Sander, and S. J. Gortler. 2003. Simple Silhouettes for Complex Surfaces. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing(SGP ’03). Eurographics Association, 102–106.
    20. Chenxi Liu, Pierre Bénard, Aaron Hertzmann, and Shayan Hoshyari. 2023. ConTesse: Accurate Occluding Contours for Subdivision Surfaces. ACM Trans. Graph. 42, 1, Article 5 (Feb. 2023), 16 pages. https://doi.org/10.1145/3544778
    21. Marian Neamtu and Pia R Pfluger. 1994. Degenerate polynomial patches of degree 4 and 5 used for geometrically smooth interpolation in 3. Computer Aided Geometric Design 11, 4 (1994), 451–474.
    22. J. D. Northrup and Lee Markosian. 2000. Artistic Silhouettes: A Hybrid Approach. In Proceedings of the 1st International Symposium on Non-photorealistic Animation and Rendering(NPAR ’00). ACM, 31–37. https://doi.org/10.1145/340916.340920
    23. Shinji Ogaki and Yusuke Tokuyoshi. 2011. Direct Ray Tracing of Phong Tessellation. Computer Graphics Forum 30, 4 (2011), 1337–1344. https://doi.org/10.1111/j.1467-8659.2011.01993.x
    24. Michael JD Powell and Malcolm A Sabin. 1977. Piecewise quadratic approximations on triangles. ACM Transactions on Mathematical Software (TOMS) 3, 4 (1977), 316–325.
    25. Takafumi Saito and Tokiichiro Takahashi. 1990. Comprehensible Rendering of 3-D Shapes. In Proceedings of the 17th Annual Conference on Computer Graphics and Interactive Techniques(SIGGRAPH ’90). ACM, 197–206. https://doi.org/10.1145/97879.97901
    26. Thomas W Sederberg and Tomoyuki Nishita. 1990. Curve intersection using Bézier clipping. Computer-Aided Design 22, 9 (1990), 538–549.
    27. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal equivalence of triangle meshes. ACM Transactions on Graphics (TOG) 27, 3 (2008), 1–11.
    28. Matei Stroila, Elmar Eisemann, and John Hart. 2008. Clip Art Rendering of Smooth Isosurfaces. IEEE Transactions on Visualization and Computer Graphics 14, 1 (2008), 135–145. https://doi.org/10.1109/TVCG.2007.1058
    29. Ruth A. Weiss. 1966. BE VISION, A Package of IBM 7090 FORTRAN Programs to Draw Orthographic Views of Combinations of Plane and Quadric Surfaces. J. ACM 13, 2 (1966), 194–204. https://doi.org/10.1145/321328.321330
    30. Georges Winkenbach and David H. Salesin. 1996. Rendering Parametric Surfaces in Pen and Ink. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques(SIGGRAPH ’96). ACM, 469–476. https://doi.org/10.1145/237170.237287

Additional Images:

©Ryan Capouellez, Jiacheng Dai, Aaron Hertzmann, and Denis Zorin

ACM Digital Library Publication:

Overview Page: