“Temporal Set Inversion for Animated Implicits” by Jazar and Kry
Conference:
Type(s):
Title:
- Temporal Set Inversion for Animated Implicits
Session/Category Title: Real-time Rendering: Gotta Go Fast!
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We exploit the temporal coherence of closed-form animated implicit surfaces by locally re-evaluating an octree-like discretization of the implicit field only as and where is necessary to rigorously maintain a global error invariant over time, thereby saving resources in static or slowly-evolving areas far from the motion where per-frame updates are not necessary. We treat implicit surface rendering as a special case of the continuous constraint satisfaction problem of set inversion, which seeks preimages of arbitrary sets under vector-valued functions. From this perspective, we formalize a temporally-coherent set inversion algorithm that localizes changes in the field by range-bounding its time derivatives using interval arithmetic. We implement our algorithm on the GPU using persistent thread scheduling and apply it to the scalar case of implicit surface and swept volume rendering where we achieve significant speedups in complex scenes with localized deformations like those found in games and modelling applications where interactivity is required and bounded-error approximation is acceptable.
References:
1. Timo Aila and Samuli Laine. 2009. Understanding the Efficiency of Ray Traversal on GPUs. In Proceedings of the Conference on High Performance Graphics 2009 (New Orleans, Louisiana) (HPG ’09). Association for Computing Machinery, New York, NY, USA, 145–149.
2. George Allen. 2019. nTopology Modeling Technology. https://ntopology.com/resources/whitepaper-implicit-modeling-technology/. Accessed: 2022-09-01.
3. John Amanatides and Andrew Woo. 1987. A Fast Voxel Traversal Algorithm for Ray Tracing. In EG 1987-Technical Papers. Eurographics Association, 3–10.
4. Wihelm Barth, Roland Lieger, and Michael Schindler. 1994. Ray tracing general parametric surfaces using interval arithmetic. The Visual Computer 10, 7 (01 Aug 1994), 363–371.
5. Frédéric Benhamou, Frédéric Goualard, Laurent Granvilliers, and Jean-François Puget. 1999. Revising Hull and Box Consistency. In INT. CONF. ON LOGIC PROGRAMMING. MIT press, 230–244.
6. Martin Berz and Georg Hoffstätter. 1998. Computation and Application of Taylor Polynomials with Interval Remainder Bounds. Reliable Computing 4, 1 (Feb. 1998), 83–97.
7. Antoine Bouthors and Matthieu Nesme. 2007. Twinned meshes for dynamic triangulation of implicit surfaces. In Proceedings of Graphics Interface 2007 (Montréal, Québec, Canada) (GI 2007). 3–9.
8. Gilles Chabert and Luc Jaulin. 2009. Contractor programming. Artificial Intelligence 173, 11 (2009), 1079–1100. https://www.sciencedirect.com/science/article/pii/S0004370209000381
9. Luiz Dihl Comba and Jorge Stolfi. 1990. Affine Arithmetic and Its Applications to Computer Graphics.
10. Cyril Crassin, Fabrice Neyret, Sylvain Lefebvre, and Elmar Eisemann. 2009. GigaVoxels: Ray-Guided Streaming for Efficient and Detailed Voxel Rendering. In Proceedings of the 2009 Symposium on Interactive 3D Graphics and Games (Boston, Massachusetts) (I3D ’09). Association for Computing Machinery, New York, NY, USA, 15–22.
11. A. De Cusatis, L.H. De Figueiredo, and M. Gattass. 1999. Interval methods for ray casting implicit surfaces with affine arithmetic. In XII Brazilian Symposium on Computer Graphics and Image Processing (Cat. No.PR00481). 65–71.
12. Fernando De Goes and Doug L. James. 2017. Regularized Kelvinlets: Sculpting Brushes Based on Fundamental Solutions of Elasticity. ACM Trans. Graph. 36, 4, Article 40 (jul 2017), 11 pages.
13. B. Desrochers and L. Jaulin. 2017. Thick set inversion. Artificial Intelligence 249 (2017), 1–18.
14. Jens Deussen, Jan Riehme, and Uwe Naumann. 2016. Automation of significance analyses with interval splitting. In Parallel Computing: On the Road to Exascale. IOS Press, 731–740.
15. J.E.F. Díaz, M. Sbert, J.V. Casellas, and Informàtica i Automàtica Universitat de Girona. Departament d’Electrònica. 2008. Improvements in the Ray Tracing of Implicit Surfaces Based on Interval Arithmetic. Universitat de Girona. Escola Politècnica Superior. Departament d’Electrònica, Informàtica i Automàtica. https://books.google.dk/books?id=brsRzQEACAAJ
16. Tom Duff. 1992. Interval Arithmetic Recursive Subdivision for Implicit Functions and Constructive Solid Geometry. SIGGRAPH Comput. Graph. 26, 2 (jul 1992), 131–138.
17. Oleg Fryazinov, Alexander Pasko, and Peter Comninos. 2010. Fast reliable interrogation of procedurally defined implicit surfaces using extended revised affine arithmetic. Computers & Graphics 34, 6 (2010), 708–718. Graphics for Serious Games Computer Graphics in Spain: a Selection of Papers from CEIG 2009 Selected Papers from the SIGGRAPH Asia Education Program.
18. Eric Galin, Eric Guérin, Axel Paris, and Adrien Peytavie. 2020. Segment Tracing Using Local Lipschitz Bounds. Computer Graphics Forum 39, 2 (2020), 545–554.
19. Michael Gleicher and Michael Kass. 1992. An interval refinement technique for surface intersection. In Proceedings of Graphics Interface ’92 (Vancouver, British Columbia, Canada) (GI ’92). Canadian Human-Computer Communications Society, Toronto, Ontario, Canada, 242–249. http://graphicsinterface.org/wp-content/uploads/gi1992-28.pdf
20. Olivier Gourmel, Anthony Pajot, Mathias Paulin, Loïc Barthe, and Pierre Poulin. 2010. Fitted BVH for Fast Raytracing of Metaballs. Computer Graphics Forum 29, 2 (2010), 281–288.
21. Kshitij Gupta, Jeff A. Stuart, and John D. Owens. 2012. A study of Persistent Threads style GPU programming for GPGPU workloads. In 2012 Innovative Parallel Computing (InPar). 1–14.
22. E.R. Hansen and R.I. Greenberg. 1983. An interval Newton method. Appl. Math. Comput. 12, 2 (1983), 89–98.
23. Eldon R. Hansen. 1992. Global optimization using interval analysis.
24. John C Hart. 1996. Sphere tracing: A geometric method for the antialiased ray tracing of implicit surfaces. The Visual Computer 12, 10 (1996), 527–545.
25. John C. Hart, Ed Bachta, Wojciech Jarosz, and Terry Fleury. 2002. Using Particles to Sample and Control More Complex Implicit Surfaces. In SMI ’02: Proceedings of the Shape Modeling International 2002 (SMI’02). IEEE Computer Society, Washington, DC, USA, 129.
26. Michael Innes. 2018. Don’t unroll adjoint: Differentiating ssa-form programs. In arXiv preprint arXiv:1810.07951.
27. Luc Jaulin, Michel Kieffer, Olivier Didrit, and Eric Walter. 2001. Applied Interval Analysis with Examples in Parameter and State Estimation, Robust Control and Robotics. Springer London Ltd. 398 pages. https://hal.archives-ouvertes.fr/hal-00845131
28. Luc Jaulin and Eric Walter. 1993. Set inversion via interval analysis for nonlinear bounded-error estimation. Automatica 29, 4 (1993), 1053–1064.
29. David Jevans, Brian Wyvill, and Geoff Wyvill. 1988. Speeding up 3-D animation for simulation. In Proceedings of the Fourth SCS Multiconference on Multiprocessors and Array Processors. 94–100.
30. Tao Ju, Frank Losasso, Scott Schaefer, and Joe Warren. 2002. Dual contouring of hermite data. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques. 339–346.
31. Matthew J. Keeter. 2020. Massively Parallel Rendering of Complex Closed-Form Implicit Surfaces. ACM Trans. Graph. 39, 4, Article 141 (jul 2020), 10 pages.
32. Bernhard Kerbl, Michael Kenzel, Joerg H. Mueller, Dieter Schmalstieg, and Markus Steinberger. 2018. The Broker Queue: A Fast, Linearizable FIFO Queue for Fine-Granular Work Distribution on the GPU. In Proceedings of the 2018 International Conference on Supercomputing (Beijing, China) (ICS ’18). Association for Computing Machinery, New York, NY, USA, 76–85.
33. A. Knoll, Y. Hijazi, A. Kensler, M. Schott, C. Hansen, and H. Hagen. 2009. Fast Ray Tracing of Arbitrary Implicit Surfaces with Interval and Affine Arithmetic. Computer Graphics Forum 28, 1 (2009), 26–40.
34. Johann Korndörfer, Benjamin Keinert, Urs Ganse, Michael Sänger, Simon Ley, Konstanze Burkhardt, Mario Spuler, and Jörn Heusipp. 2015. HG_SDF: A glsl library for building signed distance functions. https://mercury.sexy/hg_sdf. Accessed: 2021-07-28.
35. Chris Lattner and Vikram Adve. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation (CGO ’04). IEEE Computer Society, USA, 75.
36. Raph Levien. 2021. Prefix sum on portable compute shaders. https://raphlinus.github.io/gpu/2021/11/17/prefix-sum-portable.html
37. William E. Lorensen and Harvey E. Cline. 1987. Marching Cubes: A High Resolution 3D Surface Construction Algorithm. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’87). Association for Computing Machinery, New York, NY, USA, 163–169.
38. Alexander Majercik, Cyril Crassin, Peter Shirley, and Morgan McGuire. 2018. A Ray-Box Intersection Algorithm and Efficient Dynamic Voxel Rendering. Journal of Computer Graphics Techniques (JCGT) 7, 3 (20 September 2018), 66–81. http://jcgt.org/published/0007/03/04/
39. Mariano Merchante. 2018. Sponza pt2. Shadertoy. https://www.shadertoy.com/view/ltGcRW
40. Alexandre Mercier-Aubin, Alexandre Winter, David I. W. Levin, and Paul G. Kry. 2022. Adaptive Rigidification of Elastic Solids. ACM Trans. Graph. 41, 4, Article 71 (jul 2022), 11 pages.
41. Duane Merrill and Michael Garland. 2016. Single-pass parallel prefix scan with decoupled look-back. Technical Report. NVIDIA, Tech. Rep. NVR-2016-002.
42. D. P. Mitchell. 1990. Robust Ray Intersection with Interval Arithmetic. In Proceedings of Graphics Interface ’90 (Halifax, Nova Scotia, Canada) (GI ’90). Canadian Man-Computer Communications Society, Toronto, Ontario, Canada, 68–74. http://graphicsinterface.org/wp-content/uploads/gi1990-8.pdf
43. R.E. Moore. 1966. Interval Analysis. Prentice-Hall.
44. NAGA 2023. NAGA: Universal Shader Translation in Rust. GitHub. https://github.com/gfx-rs/naga
45. Agata Opalach and Marie-Paule Cani. 1997. Local Deformation for Animation of Implicit Surfaces. In Spring Conference on Computer Graphics (SCCG).
46. Inigo Quilez. 2008. Rendering Worlds with Two Triangles with raytracing on the GPU in 4096 bytes. (2008). NVSCENE 08.
47. Inigo Quilez. 2013. Piano. Shadertoy. https://www.shadertoy.com/view/ldl3zN
48. Dietmar Ratz. 1996. An optimized interval slope arithmetic and its application. Inst. für Angewandte Mathematik.
49. Stephane Redon, Young J. Kim, Ming C. Lin, and Dinesh Manocha. 2005. Fast Continuous Collision Detection for Articulated Models. Journal of Computing and Information Science in Engineering 5, 2 (2005), 126–137.
50. Jan Riehme and Uwe Naumann. 2015. Significance Analysis for Numerical Models. In 1st WorkShop on Approximate Computing (WAPCO 2015).
51. David P. Sanders. 2020. Fast global optimization on the GPU. JuliaCon 2020. https://live.juliacon.org/uploads/posters/8K8P7R.pdf
52. David P. Sanders, Luis Benet, Luca Ferranti, Krish Agarwal, Benoît Richard, Josua Grawitter, Eeshan Gupta, Marcelo Forets, Michael F. Herbst, yashrajgupta, Eric Hanson, Braam van Dyk, Christopher Rackauckas, Rushabh Vasani, Sebastian Miclut,a-Câmpeanu, Sheehan Olver, Twan Koolen, Caroline Wormell, Daniel Karrasch, Favio André Vázquez, Guillaume Dalle, Jeffrey Sarnoff, Julia TagBot, Kevin O’Bryant, Kristoffer Carlsson, Morten Piibeleht, Mosè Giordano, Ryan, Robin Deits, and Tim Holy. 2022. JuliaIntervals/IntervalArithmetic.jl: v0.20.8.
53. Ryan Schmidt. 2006. Interactive Modeling with Implicit Surfaces. Master’s thesis. The University of Calgary.
54. R. Schmidt, B. Wyvill, and E. Galin. 2005. Interactive implicit modeling with hierarchical spatial caching. In International Conference on Shape Modeling and Applications 2005 (SMI’ 05). 104–113.
55. Silvia Sellán, Noam Aigerman, and Alec Jacobson. 2021. Swept Volumes via Spacetime Numerical Continuation. ACM Trans. Graph. 40, 4, Article 55 (jul 2021), 11 pages.
56. Dario Seyb, Alec Jacobson, Derek Nowrouzezahrai, and Wojciech Jarosz. 2019. NonLinear Sphere Tracing for Rendering Deformed Signed Distance Fields. ACM Trans. Graph. 38, 6, Article 229 (nov 2019), 12 pages.
57. Nicholas Sharp and Alec Jacobson. 2022. Spelunking the Deep: Guaranteed Queries on General Neural Implicit Surfaces via Range Analysis. ACM Trans. Graph. 41, 4, Article 107 (jul 2022), 16 pages.
58. John M. Snyder. 1992. Interval Analysis for Computer Graphics. SIGGRAPH Comput. Graph. 26, 2 (jul 1992), 121–130.
59. John M. Snyder, Adam R. Woodbury, Kurt Fleischer, Bena Currin, and Alan H. Barr. 1993. Interval Methods for Multi-Point Collisions between Time-Dependent Curved Surfaces. In Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques (Anaheim, CA) (SIGGRAPH ’93). Association for Computing Machinery, New York, NY, USA, 321–334.
60. Jos Stam and Ryan Schmidt. 2011. On the Velocity of an Implicit Surface. ACM Trans. Graph. 30, 3, Article 21 (may 2011), 7 pages.
61. Martijn Steinrucken. 2021. Newton’s Cradle Tutorial. Shadertoy. https://www.shadertoy.com/view/sdsXWr
62. Jeff Tupper. 2001. Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’01). Association for Computing Machinery, New York, NY, USA, 77–86.
63. Vassilis Vassiliadis, Jan Riehme, Jens Deussen, Konstantinos Parasyris, Christos D. Antonopoulos, Nikolaos Bellas, Spyros Lalis, and Uwe Naumann. 2016. Towards Automatic Significance Analysis for Approximate Computing. In Proceedings of the 2016 International Symposium on Code Generation and Optimization (Barcelona, Spain) (CGO ’16). Association for Computing Machinery, New York, NY, USA, 182–193.
64. Xuan-Ha Vu, Djamila Sam-Haroud, and Boi Faltings. 2009. Enhancing numerical constraint propagation using multiple inclusion representations. Annals of Mathematics and Artificial Intelligence 55, 3 (March 2009), 295.
65. Bolun Wang, Zachary Ferguson, Teseo Schneider, Xin Jiang, Marco Attene, and Daniele Panozzo. 2021. A Large-Scale Benchmark and an Inclusion-Based Algorithm for Continuous Collision Detection. ACM Trans. Graph. 40, 5, Article 188 (sep 2021), 16 pages.
66. Frames White, Michael Abbott, Miha Zgubic, Jarrett Revels, Seth Axen, Alex Arslan, Simeon Schaub, Nick Robinson, Yingbo Ma, Gaurav Dhingra, Will Tebbutt, David Widmann, Niklas Heim, Niklas Schmitz, Andrew David Werner Rosemberg, Christopher Rackauckas, Carlo Lucibello, Rainer Heintzmann, frankschae, Andreas Noack, Keno Fischer, Alex Robson, Jorge Fernandez de Cossio-Diaz, Jerry Ling, mattBrzezinski, Rory Finnegan, Andrei Zhabinski, Daniel Wennberg, Mathieu Besançon, and Pietro Vertechi. 2023. JuliaDiff/ChainRules.jl: v1.48.0.
67. Andrew P. Witkin and Paul S. Heckbert. 1994. Using Particles to Sample and Control Implicit Surfaces. In Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’94). 269–277.
68. Brian Wyvill, Andrew Guy, and Eric Galin. 1999. Extending the CSG Tree. Warping, Blending and Boolean Operations in an Implicit Surface Modeling System. Computer Graphics Forum 18, 2 (1999), 149–158.
69. R.C. Young. 1931. The algebra of many-valued quantities. Math. Ann. 104 (1931), 260–290. http://eudml.org/doc/159462
70. yuntaRobo. 2020. cables2. Shadertoy. https://www.shadertoy.com/view/wlKXWc
71. Xinyu Zhang, Stephane Redon, Minkyoung Lee, and Young J. Kim. 2007. Continuous Collision Detection for Articulated Models Using Taylor Models and Temporal Culling. 26, 3 (jul 2007), 15–es.
