“A variational approach to Eulerian geometry processing” by Mullen, McKenzie, Tong and Desbrun

We present a purely Eulerian framework for geometry processing of surfaces and foliations. Contrary to current Eulerian methods used in graphics, we use conservative methods and a variational interpretation, offering a unified framework for routine surface operations such as smoothing, offsetting, and animation. Computations are performed on a fixed volumetric grid without recourse to Lagrangian techniques such as triangle meshes, particles, or path tracing. At the core of our approach is the use of the Coarea Formula to express area integrals over isosurfaces as volume integrals. This enables the simultaneous processing of multiple isosurfaces, while a single interface can be treated as the special case of a dense foliation. We show that our method is a powerful alternative to conventional geometric representations in delicate cases such as the handling of high-genus surfaces, weighted offsetting, foliation smoothing of medical datasets, and incompressible fluid animation.

1. Abraham, R., Marsden, J., and Ratiu, T., Eds. 1988. Manifolds, Tensor Analysis, and Applications. Applied Mathematical Sciences Vol. 75, Springer. Google ScholarDigital Library
2. Adalsteinsson, D., and Sethian, J. 1999. The Fast Construction of Extension Velocities in Level Set Methods. J. Computational Physics 148, 2–22. Google ScholarDigital Library
3. Alexa, M., Gross, M., Pauly, M., Pfister, H., Stamminger, M., and Zwicke, M., 2006. Point-Based Computer Graphics. ACM SIGGRAPH Course. Google ScholarDigital Library
4. Anderson, D. M., McFadden, G. B., and Wheeler, A. A. 1998. Diffuse-Interface Methods In Fluid Mechanics. Annual Review of Fluid Mechanics 30, 139–165.Google ScholarCross Ref
5. Bargteil, A. W., Goktekin, T. G., O’Brien, J. F., and Strain, J. A. 2006. A Semi-Lagrangian Contouring Method for Fluid Simulation. ACM Trans. Graph. 25, 1, 19–38. Google ScholarDigital Library
6. Barth, T., and Ohlberger, M. 2004. Finite volume methods: foundation and analysis, vol. 1 of Encyclopedia of Computational Mechanics, E. Stein, R. de Borst, T. J. R. Hughes (Eds.). John Wiley and Sons Ltd, 439–474.Google Scholar
7. Botsch, M., and Pauly, M., 2006. Geometric Modeling based on Triangle Meshes. ACM SIGGRAPH Course. Google ScholarDigital Library
8. Breen, D., and Mauch, S. 1999. Generating Shaded Offset Surfaces with Distance, Closest-Point and Color Volumes. In International Workshop on Volume Graphics, 307–320.Google Scholar
9. Bridson, R., Fedkiw, R., and Müller-Fischer, M. 2006. Fluid Simulation. In ACM SIGGRAPH Course Notes.Google Scholar
10. Curless, B., and Levoy, M. 1996. A Volumetric Method for Building Complex Models from Range Images. In Proc. of ACM SIGGRAPH, 303–312. Google ScholarDigital Library
11. Desbrun, M., Meyer, M., Schröder, P., and Barr, A. 1999. Implicit Fairing of Irregular Meshes using Diffusion and Curvature Flow. ACM SIGGRAPH, 317–324. Google ScholarDigital Library
12. Droske, M., and Rumpf, M. 2004. A Level Set Formulation for Willmore Flow. Interfaces and Free Boundaries 6, 3, 361–378.Google ScholarCross Ref
13. Dyadechko, V., and Shashkov, M., 2006. Moment-of-Fluid Interface Reconstruction. LANL Technical Report LA-UR-05-7571.Google Scholar
14. Engquist, B., and Osher, S. 1980. One-Sided Difference Schemes and Transonic Flow. PNAS 77, 6, 3071–3074.Google ScholarCross Ref
15. Enright, D., R. Fedkiw, J. F., and Mitchell, I. 2002. A Hybrid Particle Level Set Method for Improved Interface Capturing. J. Computational Physics 183, 83–116. Google ScholarDigital Library
16. Federer, H. 1959. Curvature Measures. Trans. Amer. Math. Soc. 93, 418–491.Google ScholarCross Ref
17. Foster, N., and Fedkiw, R. 2001. Practical Animation of Liquids. In ACM SIGGRAPH, 23–30. Google ScholarDigital Library
18. Frisken, S., Perry, R., Rockwood, A., and Jones, T. 2000. Adaptively Sampled Distance Fields: A General Representation of Shape for Computer Graphics. In ACM SIGGRAPH Proc., 249–254. Google ScholarDigital Library
19. Frolkovic, P., and Mikula, K., 2005. High-resolution Flux-based Level Set Method. Preprint 2005-12. Department of Mathematics and Descriptive Geometry, Slovak University of Technology, Bratislava.Google Scholar
20. Grinspun, E., Hirani, A. N., Desbrun, M., and Schröder, P. 2003. Discrete Shells. In Symposium on Computer Animation, 62–67. Google ScholarDigital Library
21. Grinspun, E., 2006. Discrete Differential Geometry: an applied introduction. ACM SIGGRAPH Course.Google Scholar
22. Hieber, S. E., and Koumoutsakos, P. 2005. A Lagrangian particle level set method. J. Comput. Phys. 210, 1, 342–367. Google ScholarDigital Library
23. Houston, B., Nielsen, M., Batty, C., Nilsson, O., and Museth, K. 2006. Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface Representation. ACM Trans. on Graphics 25, 1, 151–175. Google ScholarDigital Library
24. Jiang, G.-S., and Shu, C.-W. 1996. Efficient Implementation of Weighted ENO Schemes. J. Comp. Phys. 126, 1, 202–228. Google ScholarDigital Library
25. Lee, H., Desbrun, M., and Schröder, P. 2003. Progressive Encoding of Complex Isosurfaces. In Proc. of ACM SIGGRAPH, 471–476. Google ScholarDigital Library
26. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating Water and Smoke with an Octree Data Structure. ACM Trans. Graph. 23, 3 (Aug.), 457–462. Google ScholarDigital Library
27. Mihalef, V., Unlusu, B., Metaxas, D., Sussman, M., and Hussaini, M. 2006. Physics-based Boiling Simulation. In EG/ACM SIGGRAPH Symp. on Comput. Anim., 317–324. Google ScholarDigital Library
28. Museth, K., Breen, D., Whitaker, R., and Barr, A. 2002. Level Set Surface Editing Operators. ACM Trans. on Graphics 21, 3, 330–338. Google ScholarDigital Library
29. Olsson, E., and Kreiss, G. 2005. A Conservative Level Set Method for Two Phase Flow. J. Comput. Phys. 210, 1, 225–246. Google ScholarDigital Library
30. Osher, S., and Fedkiw, R. 2003. Level Set Methods and Dynamic Implicit Surfaces, vol. 153 of Applied Mathematical Sciences. Springer-Verlag, New York.Google Scholar
31. Osher, S., and Sethian, J. E. 1988. Fronts Propagating with Curvature-dependent Speed: Algorithms based on the Hamilton-Jacobi Formulation. Journal of Computational Physics 79, 12–49. Google ScholarDigital Library
32. Pinkall, U., and Polthier, K. 1993. Computing Discrete Minimal Surfaces and Their Conjugates. Experimental Mathematics 2, 1, 15–36.Google ScholarCross Ref
33. Puckett, E. G., Almgren, A. S., Bell, J. B., Marcus, D. L., and Rider, W. J. 1997. A High-order Projection Method for Tracking Fluid Interfaces in Variable Density Incompressible Flows. J. Comput. Phys. 130, 2, 269–282. Google ScholarDigital Library
34. Rouy, E., and Tourin, A. 1992. A Viscosity Solutions Approach to Shape-From-Shading. SIAM J. on Num.l Analysis 29, 3, 867–884. Google ScholarDigital Library
35. Schröder, P. 2006. What Can We Measure. Discrete Differential Geometry, E. Grinspun, P. Schröder, M. Desbrun (Eds.). ACM SIGGRAPH Course Lecture Notes, 8–12.Google Scholar
36. Sethian, J. A. 1999. Level Set Methods and Fast Marching Methods, 2nd ed., vol. 3 of Monographs on Appl. Comput. Math. Cambridge University Press, Cambridge.Google Scholar
37. Shu, C., and Osher, S. 1988. Efficient Implementation of Essentially non-Oscillatory Shock Capturing Schemes. J. Sci. Comput. 77, 439–471. Google ScholarDigital Library
38. Sussman, M., and Puckett, E. G. 2000. A Coupled Level Set and Volume-Of-Fluid method for Computing 3D and Axisymmetric Incompressible Two-phase Flows. J. Comput. Phys. 162, 2, 301–337. Google ScholarDigital Library
39. Tasdizen, T., Whitaker, R., Burchard, P., and Osher, S. 2003. Geometric Surface Processing via Normal Maps. ACM Trans. on Graphics 2, 4, 1012–1033. Google ScholarDigital Library
40. Wood, Z., Hoppe, H., Desbrun, M., and Schröder, P. 2004. Removing excess topology from isosurfaces. ACM Trans. Graph. 23, 2, 190–208. Google ScholarDigital Library
41. Zhang, Y., and Shu, C. 2003. High-Order WENO Schemes for Hamilton-Jacobi Equations on Triangular Meshes. J. Sci. Comput. 24, 1005–1030. Google ScholarDigital Library