“Systematically differentiating parametric discontinuities” by Bangaru, Michel, Mu, Bernstein, Li, et al. …

  • ©Sai Praveen Bangaru, Jesse Michel, Kevin Mu, Gilbert Bernstein, Tzu-Mao Li, and Jonathan Ragan-Kelley




    Systematically differentiating parametric discontinuities



    Emerging research in computer graphics, inverse problems, and machine learning requires us to differentiate and optimize parametric discontinuities. These discontinuities appear in object boundaries, occlusion, contact, and sudden change over time. In many domains, such as rendering and physics simulation, we differentiate the parameters of models that are expressed as integrals over discontinuous functions. Ignoring the discontinuities during differentiation often has a significant impact on the optimization process. Previous approaches either apply specialized hand-derived solutions, smooth out the discontinuities, or rely on incorrect automatic differentiation.We propose a systematic approach to differentiating integrals with discontinuous integrands, by developing a new differentiable programming language. We introduce integration as a language primitive and account for the Dirac delta contribution from differentiating parametric discontinuities in the integrand. We formally define the language semantics and prove the correctness and closure under the differentiation, allowing the generation of gradients and higher-order derivatives. We also build a system, Teg, implementing these semantics. Our approach is widely applicable to a variety of tasks, including image stylization, fitting shader parameters, trajectory optimization, and optimizing physical designs.


    1. Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2015. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems.Google Scholar
    2. Luke Anderson, Tzu-Mao Li, Jaakko Lehtinen, and Frédo Durand. 2017. Aether: An embedded domain specific sampling language for Monte Carlo rendering. ACM Trans. Graph. (Proc. SIGGRAPH) 36, 4 (2017), 1–16.Google ScholarDigital Library
    3. James Arvo. 1994. The Irradiance Jacobian for Partially Occluded Polyhedral Sources. In SIGGRAPH. 343–350.Google Scholar
    4. Sai Praveen Bangaru, Tzu-Mao Li, and Frédo Durand. 2020. Unbiased warped-area sampling for differentiable rendering. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 39, 6 (2020), 1–18.Google ScholarDigital Library
    5. Alan H Barr, Bena Currin, Steven Gabriel, and John F Hughes. 1992. Smooth interpolation of orientations with angular velocity constraints using quaternions. Comput. Graph. (Proc. SIGGRAPH) 26, 2 (1992), 313–320.Google ScholarDigital Library
    6. Harry Bateman. 1931. On dissipative systems and related variational principles. Physical Review 38, 4 (1931), 815.Google ScholarCross Ref
    7. John T Betts. 1998. Survey of numerical methods for trajectory optimization. Journal of guidance, control, and dynamics 21, 2 (1998), 193–207.Google ScholarCross Ref
    8. John T. Betts. 2009. Practical Methods for Optimal Control and Estimation Using Nonlinear Programming (2nd ed.). Cambridge University Press, USA.Google ScholarDigital Library
    9. Eli Bingham, Jonathan P. Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul Szerlip, Paul Horsfall, and Noah D. Goodman. 2019. Pyro: Deep Universal Probabilistic Programming. J. Mach. Learn. Res. 20, 1 (2019), 973–978.Google ScholarDigital Library
    10. James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, and Skye Wanderman-Milne. 2018. JAX: composable transformations of Python+NumPy programs. http://github.com/google/jaxGoogle Scholar
    11. Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. 2018. Neural Ordinary Differential Equations. In Advances in Neural Information Processing Systems, Vol. 31. 6571–6583.Google Scholar
    12. Michael F Cohen. 1992. Interactive spacetime control for animation. Comput. Graph. (Proc. SIGGRAPH) (1992), 293–302.Google Scholar
    13. J.F. Colombeau. 1984. New Generalized Functions and Multiplication of Distributions. North-Holland.Google Scholar
    14. Filipe de Avila Belbute-Peres, Kevin Smith, Kelsey Allen, Josh Tenenbaum, and J. Zico Kolter. 2018. End-to-End Differentiable Physics for Learning and Control. In Advances in Neural Information Processing Systems, Vol. 31. 7178–7189.Google Scholar
    15. Martin de La Gorce, David J Fleet, and Nikos Paragios. 2011. Model-based 3D hand pose estimation from monocular video. IEEE Trans. Pattern Anal. Mach. Intell. 33, 9 (2011), 1793–1805.Google ScholarDigital Library
    16. Zachary Devito, Michael Mara, Michael Zollhöfer, Gilbert Bernstein, Jonathan Ragan-Kelley, Christian Theobalt, Pat Hanrahan, Matthew Fisher, and Matthias Niessner. 2017. Opt: A Domain Specific Language for Non-Linear Least Squares Optimization in Graphics and Imaging. ACM Trans. Graph. 36, 5 (2017), 171:1–171:27.Google ScholarDigital Library
    17. P.A.M. Dirac. 1981. The Principles of Quantum Mechanics. Clarendon Press.Google Scholar
    18. Peter Dyer and SR McReynolds. 1968. On optimal control problems with discontinuities. J. Math. Anal. Appl. 23, 3 (1968), 585–603.Google ScholarCross Ref
    19. Conal Elliott. 2018. The Simple Essence of Automatic Differentiation. International Conference on Functional Programming (2018).Google Scholar
    20. Timon Gehr, Samuel Steffen, and Martin Vechev. 2020. λPSI: exact inference for higherorder probabilistic programs. In Programming Language Design and Implementation. 883–897.Google Scholar
    21. Moritz Geilinger, David Hahn, Jonas Zehnder, Moritz Bächer, Bernhard Thomaszewski, and Stelian Coros. 2020. ADD: Analytically Differentiable Dynamics for Multi-Body Systems with Frictional Contact. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 39, 6 (2020).Google Scholar
    22. Ioannis Gkioulekas, Shuang Zhao, Kavita Bala, Todd Zickler, and Anat Levin. 2013. Inverse Volume Rendering with Material Dictionaries. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 32, 6 (2013), 162:1–162:13.Google Scholar
    23. Andreas Griewank and Andrea Walther. 2008. Evaluating Derivatives. Society for Industrial and Applied Mathematics.Google Scholar
    24. Yu Guo, Miloš Hašan, Lingqi Yan, and Shuang Zhao. 2020. A Bayesian Inference Framework for Procedural Material Parameter Estimation. Comput. Graph. Forum (Proc. Pacific Graphics) 39, 7 (2020), 255–266.Google ScholarCross Ref
    25. Christian Hafner, Christian Schumacher, Espen Knoop, Thomas Auzinger, Bernd Bickel, and Moritz Bächer. 2019. X-CAD: Optimizing CAD Models with Extended Finite Elements. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 38, 6 (2019).Google Scholar
    26. William Rowan Hamilton. 1834. XV. On a general method in dynamics; by which the study of the motions of all free systems of attracting or repelling points is reduced to the search and differentiation of one central relation, or characteristic function. Philosophical transactions of the Royal Society of London 124 (1834), 247–308.Google Scholar
    27. Charles R Hargraves and Stephen W Paris. 1987. Direct trajectory optimization using nonlinear programming and collocation. Journal of guidance, control, and dynamics 10, 4 (1987), 338–342.Google ScholarCross Ref
    28. R.C. Hibbeler. 2000. Mechanics of Materials. Prentice Hall.Google Scholar
    29. Philipp Holl, Nils Thuerey, and Vladlen Koltun. 2020. Learning to Control PDEs with Differentiable Physics. In International Conference on Learning Representations.Google Scholar
    30. Yuanming Hu, Luke Anderson, Tzu-Mao Li, Qi Sun, Nathan Carr, Jonathan Ragan-Kelley, and Frédo Durand. 2020. DiffTaichi: Differentiable Programming for Physical Simulation. International Conference on Learning Representations (2020).Google Scholar
    31. K. H. Hunt and F. R. E. Crossley. 1975. Coefficient of Restitution Interpreted as Damping in Vibroimpact. Journal of Applied Mechanics 42, 2 (1975), 440–445.Google ScholarCross Ref
    32. Jeevana Priya Inala, Sicun Gao, Soonho Kong, and Armando Solar-Lezama. 2018. REAS: combining numerical optimization with SAT solving. arXiv (2018).Google Scholar
    33. Kenneth E. Iverson. 1962. A Programming Language. John Wiley & Sons, Inc.Google ScholarDigital Library
    34. Wenzel Jakob. 2019. Enoki: structured vectorization and differentiation on modern processor architectures. https://github.com/mitsuba-renderer/enoki.Google Scholar
    35. James T. Kajiya. 1986. The Rendering Equation. Comput. Graph. (Proc. SIGGRAPH) 20, 4 (1986), 143–150.Google ScholarDigital Library
    36. Michael Kass. 1992. CONDOR: Constraint-Based Dataflow. Comput. Graph. (Proc. SIGGRAPH) 26, 2 (1992), 321–330.Google ScholarDigital Library
    37. Michael Kass, Andrew Witkin, and Demetri Terzopoulos. 1988. Snakes: Active contour models. Int. J. Comput. Vision 1, 4 (1988), 321–331.Google ScholarCross Ref
    38. Hiroharu Kato, Yoshitaka Ushiku, and Tatsuya Harada. 2018. Neural 3D Mesh Renderer. In Computer Vision and Pattern Recognition. IEEE, 3907–3916.Google Scholar
    39. Diederick P Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In International Conference on Learning Representations.Google Scholar
    40. Donald E Knuth. 1992. Two notes on notation. The American Mathematical Monthly 99, 5 (1992), 403–422.Google ScholarDigital Library
    41. Alp Kucukelbir, Rajesh Ranganath, Andrew Gelman, and David M. Blei. 2015. Automatic Variational Inference in Stan. In Advances in Neural Information Processing Systems. 568–576.Google Scholar
    42. Samuli Laine, Janne Hellsten, Tero Karras, Yeongho Seol, Jaakko Lehtinen, and Timo Aila. 2020. Modular primitives for high-performance differentiable rendering. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 39, 6 (2020), 1–14.Google ScholarDigital Library
    43. Kai Lawonn and Tobias Günther. 2019. Stylized Image Triangulation. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 221–234.Google Scholar
    44. Wonyeol Lee, Hangyeol Yu, Xavier Rival, and Hongseok Yang. 2020. On Correctness of Automatic Differentiation for Non-Differentiable Functions. In Advances in Neural Information Processing Systems.Google Scholar
    45. Wonyeol Lee, Hangyeol Yu, and Hongseok Yang. 2018. Reparameterization gradient for non-differentiable models. In Advances in Neural Information Processing Systems. 5553–5563.Google Scholar
    46. Alexander K Lew, Marco F Cusumano-Towner, Benjamin Sherman, Michael Carbin, and Vikash K Mansinghka. 2019. Trace types and denotational semantics for sound programmable inference in probabilistic languages. Proc. ACM Program. Lang. 4, POPL (2019), 1–32.Google Scholar
    47. Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M Kaufman. 2020a. Incremental potential contact: Intersection-and inversion-free, large-deformation dynamics. ACM Trans. Graph. (Proc. SIGGRAPH) (2020).Google ScholarDigital Library
    48. Tzu-Mao Li. 2019. Differentiable Visual Computing. Ph.D. Dissertation. Massachusetts Institute of Technology. Advisor(s) Durand, Frédo.Google Scholar
    49. Tzu-Mao Li, Miika Aittala, Frédo Durand, and Jaakko Lehtinen. 2018a. Differentiable Monte Carlo Ray Tracing through Edge Sampling. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 37, 6 (2018), 222:1–222:11.Google Scholar
    50. Tzu-Mao Li, Michaël Gharbi, Andrew Adams, Frédo Durand, and Jonathan Ragan-Kelley. 2018b. Differentiable programming for image processing and deep learning in Halide. ACM Trans. Graph. (Proc. SIGGRAPH) 37, 4 (2018), 139:1–139:13.Google ScholarDigital Library
    51. Tzu-Mao Li, Michal Lukáč, Gharbi Michaël, and Jonathan Ragan-Kelley. 2020b. Differentiable Vector Graphics Rasterization for Editing and Learning. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 39, 6 (2020), 193:1–193:15.Google Scholar
    52. Peng Lin, Yonggang Hao, Baoyou Zhang, Shuzhi Zhang, and Jun Shen. 2017. Strain rate sensitivity of Ti-22Al-25Nb (at.alloy during high temperature deformation. Materials Science and Engineering: A (2017).Google Scholar
    53. Seppo Linnainmaa. 1970. The representation of the cumulative rounding error of an algorithm as a Taylor expansion of the local rounding errors. Master’s thesis. Univ. Helsinki.Google Scholar
    54. Shichen Liu, Tianye Li, Weikai Chen, and Hao Li. 2019. Soft Rasterizer: A Differentiable Renderer for Image-based 3D Reasoning. International Conference on Computer Vision (2019).Google ScholarCross Ref
    55. Matthew M. Loper and Michael J. Black. 2014. OpenDR: An Approximate Differentiable Renderer. In European Conference on Computer Vision, Vol. 8695. ACM, 154–169.Google Scholar
    56. Guillaume Loubet, Nicolas Holzschuch, and Wenzel Jakob. 2019. Reparameterizing discontinuous integrands for differentiable rendering. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 38, 6 (2019), 228.Google Scholar
    57. Damiano Mazza and Michele Pagani. 2021. Automatic differentiation in PCF. Proceedings of the ACM on Programming Languages 5 (2021), 1–27.Google ScholarDigital Library
    58. Antoine McNamara, Adrien Treuille, Zoran Popović, and Jos Stam. 2004. Fluid control using the adjoint method. ACM Trans. Graph. (Proc. SIGGRAPH) 23, 3 (2004), 449–456.Google ScholarDigital Library
    59. Brian Vincent Mirtich. 1996. Impulse-based dynamic simulation of rigid body systems. University of California, Berkeley.Google ScholarDigital Library
    60. Don P Mitchell and Arun N Netravali. 1988. Reconstruction filters in computer-graphics. Comput. Graph. (Proc. SIGGRAPH) 22, 4 (1988), 221–228.Google ScholarDigital Library
    61. Igor Mordatch, Emanuel Todorov, and Zoran Popović. 2012. Discovery of Complex Behaviors through Contact-Invariant Optimization. ACM Trans. Graph. (Proc. SIGGRAPH) 31, 4 (2012).Google ScholarDigital Library
    62. Igor Mordatch, Jack M Wang, Emanuel Todorov, and Vladlen Koltun. 2013. Animating human lower limbs using contact-invariant optimization. ACM Trans. Graph. 32, 6 (2013), 1–8.Google ScholarDigital Library
    63. Henry P Moreton and Carlo H Séquin. 1992. Functional optimization for fair surface design. Comput. Graph. (Proc. SIGGRAPH) 26, 2 (1992), 167–176.Google ScholarDigital Library
    64. Merlin Nimier-David, Delio Vicini, Tizian Zeltner, and Wenzel Jakob. 2019. Mitsuba 2: A retargetable forward and inverse renderer. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 38, 6 (2019), 1–17.Google ScholarDigital Library
    65. Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems. 8024–8035.Google Scholar
    66. Barak A. Pearlmutter and Jeffrey Mark Siskind. 2008. Reverse-mode AD in a Functional Framework: Lambda the Ultimate Backpropagator. Trans. Program. Lang. Syst. 30, 2 (2008), 7:1–7:36.Google Scholar
    67. Ken Perlin. 1985. An image synthesizer. Comput. Graph. (Proc. SIGGRAPH) 19, 3 (1985), 287–296.Google ScholarDigital Library
    68. Jovan Popović, Steven M Seitz, Michael Erdmann, Zoran Popović, and Andrew Witkin. 2000. Interactive manipulation of rigid body simulations. In SIGGRAPH. 209–217.Google Scholar
    69. Zoran Popović and Andrew Witkin. 1999. Physically based motion transformation. In Comput. Graph. (Proc. SIGGRAPH). 11–20.Google Scholar
    70. Michael Posa, Cecilia Cantu, and Russ Tedrake. 2014. A direct method for trajectory optimization of rigid bodies through contact. The International Journal of Robotics Research 33, 1 (2014), 69–81.Google ScholarDigital Library
    71. Ravi Ramamoorthi, Dhruv Mahajan, and Peter Belhumeur. 2007. A First-order Analysis of Lighting, Shading, and Shadows. ACM Trans. Graph. 26, 1 (2007), 2.Google ScholarDigital Library
    72. Maxime Roger, Stéphane Blanco, Mouna El Hafi, and Richard Fournier. 2005. Monte Carlo estimates of domain-deformation sensitivities. Physical review letters 95, 18 (2005), 180601.Google Scholar
    73. L. Schwartz. 1950. Théorie des distributions. Number v. 2 in Actualités scientifiques et industrielles. Hermann.Google Scholar
    74. L. Schwartz. 1954. Sur l’impossibilité de la multiplication des distributions. C. R. Acad. Sci. Paris (1954).Google Scholar
    75. Benjamin Sherman, Jesse Michel, and Michael Carbin. 2021. λS: Computable semantics for differentiable programming with higher-order functions and datatypes. Proc. ACM Program. Lang. 5, POPL, Article 3 (2021), 31 pages.Google Scholar
    76. Liang Shi, Beichen Li, Miloš Hašan, Kalyan Sunkavalli, Tamy Boubekeur, Radomir Mech, and Wojciech Matusik. 2020. MATch: Differentiable Material Graphs for Procedural Material Capture. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 39, 6 (2020), 1–15.Google ScholarDigital Library
    77. Stan Development Team. 2015. Stan Modeling Language Users Guide and Reference Manual, Version 2.9.0. http://mc-stan.org/Google Scholar
    78. Robert F Stengel. 1994. Optimal control and estimation. Courier Corporation.Google Scholar
    79. J. Tabin, B. Skoczen, and J. Bielski. 2016. Strain localization during discontinuous plastic flow at extremely low temperatures. International Journal of Solids and Structures (2016).Google Scholar
    80. Emanuel Todorov. 2011. A convex, smooth and invertible contact model for trajectory optimization. In International Conference on Robotics and Automation. IEEE, 1071–1076.Google ScholarCross Ref
    81. Christopher D. Twigg and Doug L. James. 2008. Backward Steps in Rigid Body Simulation. ACM Trans. Graph. (Proc. SIGGRAPH), Article 25 (2008).Google Scholar
    82. Kiwon Um, Robert Brand, Yun Fei, Philipp Holl, and Nils Thuerey. 2020. Solver-in-the-Loop: Learning from Differentiable Physics to Interact with Iterative PDE-Solvers. Advances in Neural Information Processing Systems (2020).Google Scholar
    83. Eric Veach. 1998. Robust Monte Carlo Methods for Light Transport Simulation. Ph.D. Dissertation. Stanford University. Advisor(s) Guibas, Leonidas J.Google ScholarDigital Library
    84. William Welch and Andrew Witkin. 1992. Variational surface modeling. Comput. Graph. (Proc. SIGGRAPH) 26, 2 (1992), 157–166.Google ScholarDigital Library
    85. R. E. Wengert. 1964. A Simple Automatic Derivative Evaluation Program. Commun. ACM 7, 8 (1964), 463–464.Google ScholarDigital Library
    86. Andrew Witkin and Michael Kass. 1988. Spacetime constraints. ACM Trans. Graph. (Proc. SIGGRAPH) 22, 4 (1988), 159–168.Google ScholarDigital Library
    87. Lifan Wu, Guangyan Cai, Shuang Zhao, and Ravi Ramamoorthi. 2020. Analytic spherical harmonic gradients for real-time rendering with many polygonal area lights. ACM Trans. Graph. (Proc. SIGGRAPH) 39, 4 (2020), 134.Google ScholarDigital Library
    88. Dong Yu, Adam Eversole, Mike Seltzer, Kaisheng Yao, Oleksii Kuchaiev, Yu Zhang, Frank Seide, Zhiheng Huang, Brian Guenter, Huaming Wang, Jasha Droppo, Geoffrey Zweig, Chris Rossbach, Jie Gao, Andreas Stolcke, Jon Currey, Malcolm Slaney, Guoguo Chen, Amit Agarwal, Chris Basoglu, Marko Padmilac, Alexey Kamenev, Vladimir Ivanov, Scott Cypher, Hari Parthasarathi, Bhaskar Mitra, Baolin Peng, and Xuedong Huang. 2014. An Introduction to Computational Networks and the Computational Network Toolkit. Technical Report. Microsoft Research.Google Scholar
    89. Dofl Y.H. Yun. 2013. DMesh, Triangulation Image Generator. http://dmesh.thedofl.com/ Accessed: 2021-01-26.Google Scholar
    90. Cheng Zhang, Bailey Miller, Kai Yan, Ioannis Gkioulekas, and Shuang Zhao. 2020. Path-space Differentiable Rendering. ACM Trans. Graph. (Proc. SIGGRAPH) 39, 6 (2020), 143:1–143:19.Google ScholarDigital Library
    91. Cheng Zhang, Lifan Wu, Changxi Zheng, Ioannis Gkioulekas, Ravi Ramamoorthi, and Shuang Zhao. 2019. A differential theory of radiative transfer. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 38, 6 (2019), 227.Google Scholar
    92. Yuan Zhou, Bradley J. Gram-Hansen, Tobias Kohn, Tom Rainforth, Hongseok Yang, and Frank Wood. 2019. LF-PPL: A Low-Level First Order Probabilistic Programming Language for Non-Differentiable Models. In International Conference on Artificial Intelligence and Statistics (AISTATS), Vol. 89. PMLR, 148–157.Google Scholar

ACM Digital Library Publication: