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

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