skip to main content
10.1145/1275808.1276459acmconferencesArticle/Chapter ViewAbstractPublication PagessiggraphConference Proceedingsconference-collections
Article

A variational approach to Eulerian geometry processing

Published: 29 July 2007 Publication History

Abstract

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.

Supplementary Material

JPG File (pps066.jpg)
MP4 File (pps066.mp4)

References

[1]
Abraham, R., Marsden, J., and Ratiu, T., Eds. 1988. Manifolds, Tensor Analysis, and Applications. Applied Mathematical Sciences Vol. 75, Springer.
[2]
Adalsteinsson, D., and Sethian, J. 1999. The Fast Construction of Extension Velocities in Level Set Methods. J. Computational Physics 148, 2--22.
[3]
Alexa, M., Gross, M., Pauly, M., Pfister, H., Stamminger, M., and Zwicke, M., 2006. Point-Based Computer Graphics. ACM SIGGRAPH Course.
[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.
[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.
[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.
[7]
Botsch, M., and Pauly, M., 2006. Geometric Modeling based on Triangle Meshes. ACM SIGGRAPH Course.
[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.
[9]
Bridson, R., Fedkiw, R., and Müller-Fischer, M. 2006. Fluid Simulation. In ACM SIGGRAPH Course Notes.
[10]
Curless, B., and Levoy, M. 1996. A Volumetric Method for Building Complex Models from Range Images. In Proc. of ACM SIGGRAPH, 303--312.
[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.
[12]
Droske, M., and Rumpf, M. 2004. A Level Set Formulation for Willmore Flow. Interfaces and Free Boundaries 6, 3, 361--378.
[13]
Dyadechko, V., and Shashkov, M., 2006. Moment-of-Fluid Interface Reconstruction. LANL Technical Report LA-UR-05-7571.
[14]
Engquist, B., and Osher, S. 1980. One-Sided Difference Schemes and Transonic Flow. PNAS 77, 6, 3071--3074.
[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.
[16]
Federer, H. 1959. Curvature Measures. Trans. Amer. Math. Soc. 93, 418--491.
[17]
Foster, N., and Fedkiw, R. 2001. Practical Animation of Liquids. In ACM SIGGRAPH, 23--30.
[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.
[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.
[20]
Grinspun, E., Hirani, A. N., Desbrun, M., and Schröder, P. 2003. Discrete Shells. In Symposium on Computer Animation, 62--67.
[21]
Grinspun, E., 2006. Discrete Differential Geometry: an applied introduction. ACM SIGGRAPH Course.
[22]
Hieber, S. E., and Koumoutsakos, P. 2005. A Lagrangian particle level set method. J. Comput. Phys. 210, 1, 342--367.
[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.
[24]
Jiang, G.-S., and Shu, C.-W. 1996. Efficient Implementation of Weighted ENO Schemes. J. Comp. Phys. 126, 1, 202--228.
[25]
Lee, H., Desbrun, M., and Schröder, P. 2003. Progressive Encoding of Complex Isosurfaces. In Proc. of ACM SIGGRAPH, 471--476.
[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.
[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.
[28]
Museth, K., Breen, D., Whitaker, R., and Barr, A. 2002. Level Set Surface Editing Operators. ACM Trans. on Graphics 21, 3, 330--338.
[29]
Olsson, E., and Kreiss, G. 2005. A Conservative Level Set Method for Two Phase Flow. J. Comput. Phys. 210, 1, 225--246.
[30]
Osher, S., and Fedkiw, R. 2003. Level Set Methods and Dynamic Implicit Surfaces, vol. 153 of Applied Mathematical Sciences. Springer-Verlag, New York.
[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.
[32]
Pinkall, U., and Polthier, K. 1993. Computing Discrete Minimal Surfaces and Their Conjugates. Experimental Mathematics 2, 1, 15--36.
[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.
[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.
[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.
[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.
[37]
Shu, C., and Osher, S. 1988. Efficient Implementation of Essentially non-Oscillatory Shock Capturing Schemes. J. Sci. Comput. 77, 439--471.
[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.
[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.
[40]
Wood, Z., Hoppe, H., Desbrun, M., and Schröder, P. 2004. Removing excess topology from isosurfaces. ACM Trans. Graph. 23, 2, 190--208.
[41]
Zhang, Y., and Shu, C. 2003. High-Order WENO Schemes for Hamilton-Jacobi Equations on Triangular Meshes. J. Sci. Comput. 24, 1005--1030.

Cited By

View all
  • (2022)The power particle-in-cell methodACM Transactions on Graphics10.1145/3528223.353006641:4(1-13)Online publication date: Jul-2022
  • (2018)Visual Simulation of Multiple Fluids in Computer Graphics: A State-of-the-Art ReportJournal of Computer Science and Technology10.1007/s11390-018-1829-033:3(431-451)Online publication date: 11-May-2018
  • (2015)Coupling 3D Eulerian, Heightfield and Particle Methods for Interactive Simulation of Large Scale Liquid PhenomenaIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2015.244930321:10(1116-1128)Online publication date: 1-Oct-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGGRAPH '07: ACM SIGGRAPH 2007 papers
August 2007
1019 pages
ISBN:9781450378369
DOI:10.1145/1275808
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. digital geometry processing
  2. fluids
  3. foliations
  4. mean curvature flow
  5. normal flows
  6. offset surfaces

Qualifiers

  • Article

Conference

SIGGRAPH07
Sponsor:

Acceptance Rates

SIGGRAPH '07 Paper Acceptance Rate 108 of 455 submissions, 24%;
Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)The power particle-in-cell methodACM Transactions on Graphics10.1145/3528223.353006641:4(1-13)Online publication date: Jul-2022
  • (2018)Visual Simulation of Multiple Fluids in Computer Graphics: A State-of-the-Art ReportJournal of Computer Science and Technology10.1007/s11390-018-1829-033:3(431-451)Online publication date: 11-May-2018
  • (2015)Coupling 3D Eulerian, Heightfield and Particle Methods for Interactive Simulation of Large Scale Liquid PhenomenaIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2015.244930321:10(1116-1128)Online publication date: 1-Oct-2015
  • (2015)Water and BubblesReal-Time Visual Effects for Game Programming10.1007/978-981-287-487-0_2(27-88)Online publication date: 1-May-2015
  • (2014)Coupling 3D eulerian, heightfield and particle methods for interactive simulation of large scale liquid phenomenaProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.5555/2849517.2849519(1-10)Online publication date: 21-Jul-2014
  • (2014)Mass-Conserving Eulerian Liquid SimulationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2013.1920:1(17-29)Online publication date: 1-Jan-2014
  • (2012)Mass-conserving eulerian liquid simulationProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.5555/2422356.2422392(245-254)Online publication date: 29-Jul-2012
  • (2012)Mass-conserving eulerian liquid simulationProceedings of the 11th ACM SIGGRAPH / Eurographics conference on Computer Animation10.5555/2421731.2421767(245-254)Online publication date: 29-Jul-2012
  • (2010)Delaunay deformable mesh for the weathering and erosion of 3D terrainThe Visual Computer10.1007/s00371-010-0506-226:12(1485-1495)Online publication date: 28-Apr-2010
  • (2008)A unified handling of immiscible and miscible fluidsComputer Animation and Virtual Worlds10.1002/cav.25619:3-4(455-467)Online publication date: 6-Aug-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media