“Fast grid-free surface tracking” by Chentanez, Müller-Fischer, Macklin and Kim

We present a novel explicit surface tracking method. Its main advantage over existing approaches is the fact that it is both completely grid-free and fast which makes it ideal for the use in large unbounded domains. A further advantage is that its running time is less sensitive to temporal variations of the input mesh than existing approaches. In terms of performance, the method provides a good trade-off point between speed and quality. The main idea behind our approach to handle topological changes is to delete all overlapping triangles and to fill or join the resulting holes in a robust and efficient way while guaranteeing that the output mesh is both manifold and without boundary. We demonstrate the flexibility, speed and quality of our method in various applications such as Eulerian and Lagrangian liquid simulations and the simulation of solids under large plastic deformations.

1. Adams, B., Pauly, M., Keiser, R., and Guibas, L. J. 2007. Adaptively sampled particle fluids. ACM Trans. Graph. 26 (July). Google ScholarDigital Library
2. Amato, N. M., Goodrich, M. T., and Ramos, E. A. 2000. Linear-time triangulation of a simple polygon made easier via randomization. In In Proc. 16th Annu. ACM Sympos. Comput. Geom, 201–212. Google ScholarDigital Library
3. Attene, M., Campen, M., and Kobbelt, L. 2013. Polygon mesh repairing: An application perspective. ACM Comput. Surv. 45, 2 (Mar.), 15:1–15:33. Google ScholarDigital Library
4. Attene, M. 2010. A lightweight approach to repairing digitized polygon meshes. The Visual Computer 26, 11, 1393–1406. Google ScholarDigital Library
5. Barber, C. B., Dobkin, D. P., and Huhdanpaa, H. 1996. The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software 22, 4, 469–483. Google ScholarDigital Library
6. Barequet, G., and Sharir, M. 1993. Filling gaps in the boundary of a polyhedron. Computer Aided Geometric Design 12, 207–229. Google ScholarDigital Library
7. 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 (Jan.), 19–38. Google ScholarDigital Library
8. Bernstein, G. L., and Wojtan, C. 2013. Putting holes in holey geometry: Topology change for arbitrary surfaces. ACM Trans. Graph. 32, 4 (July), 34:1–34:12. Google ScholarDigital Library
9. Blinn, J. F. 1982. A generalization of algebraic surface drawing. ACM Trans. Graph. 1, 3 (July), 235–256. Google ScholarDigital Library
10. Borodin, P., Novotni, M., and Klein, R. 2002. Progressive gap closing for meshrepairing. In Advances in Modelling, Animation and Rendering, J. Vince and R. Earnshaw, Eds. Springer London, 201–213.Google Scholar
11. Bredno, J., Lehmann, T., and Spitzer, K. 2003. A general discrete contour model in two, three, and four dimensions for topology-adaptive multichannel segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on 25, 5 (May), 550–563. Google ScholarDigital Library
12. Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM Journal on Scientific Computing 31, 4, 2472–2493. Google ScholarDigital Library
13. Campen, M., and Kobbelt, L. 2010. Exact and robust (self-)intersections for polygonal meshes. Comput. Graph. Forum 29, 2, 397–406.Google ScholarCross Ref
14. Chazelle, B. 1991. Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6, 5 (Aug.), 485–524. Google ScholarDigital Library
15. Da, F., Batty, C., and Grinspun, E. 2014. Multimaterial mesh-based surface tracking. ACM Trans. on Graphics (SIGGRAPH 2014). Google ScholarDigital Library
16. Enright, D., Marschner, S., and Fedkiw, R. 2002. Animation and rendering of complex water surfaces. ACM Trans. Graph. 21, 3 (July), 736–744. Google ScholarDigital Library
17. Enright, D., Nguyen, D., Gibou, F., and Fedkiw, R. 2003. Using the particle level set method and a second order accurate pressure boundary condition for free surface flows. In Proc. 4th ASME-JSME Joint Fluids Eng. Conf., 2003–45144.Google Scholar
18. Enright, D., Losasso, F., and Fedkiw, R. 2005. A fast and accurate semi-Lagrangian particle level set method. Comput. Struct. 83, 6-7 (Feb.), 479–490. Google ScholarDigital Library
19. Guziec, A., Taubin, G., Lazarus, F., and Horn, W. 2001. Cutting and stitching: Converting sets of polygons to manifold surfaces. IEEE Trans. Vis. Comput. Graph. 7, 2, 136–151. Google ScholarDigital Library
20. Hu, P., Wang, C., Li, B., and Liu, M. 2012. Filling holes in triangular meshes in engineering. JSW 7, 1, 141–148.Google ScholarCross Ref
21. Jun, Y. 2005. A piecewise hole filling algorithm in reverse engineering. Computer-Aided Design 37, 2, 263–270.Google ScholarCross Ref
22. Liepa, P. 2003. Filling holes in meshes. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SGP ’03, 200–205. Google ScholarDigital Library
23. Lorensen, W. E., and Cline, H. E. 1987. Marching cubes: A high resolution 3d surface construction algorithm. SIGGRAPH Comput. Graph. 21, 4 (Aug.), 163–169. Google ScholarDigital Library
24. Lorensen, W. E., and Cline, H. E. 1987. Marching cubes: A high resolution 3D surface construction algorithm. SIGGRAPH Comput. Graph. 21 (August), 163–169. Google ScholarDigital Library
25. Macklin, M., Müller, M., Chentanez, N., and Kim, T. 2014. Unified particle physics for real-time applications. ACM Trans. Graph. 33, 4, 153. Google ScholarDigital Library
26. Möller, T. 1997. A fast triangle-triangle intersection test. Journal of Graphics Tools 2, 25–30. Google ScholarDigital Library
27. Müller, M. 2009. Fast and robust tracking of fluid surfaces. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, ACM, New York, NY, USA, SCA ’09, 237–245. Google ScholarDigital Library
28. Osher, S., and Sethian, J. A. 1988. Fronts propagating with curvature-dependent speed: Algorithms based on hamilton=jacobi formulations. Journal of Computational Physics 79, 1, 12–49. Google ScholarDigital Library
29. Paul Chew, L. 1989. Constrained delaunay triangulations. Algorithmica 4, 1–4, 97–108.Google ScholarCross Ref
30. Pavic, D., Campen, M., and Kobbelt, L. 2010. Hybrid booleans. Computer Graphics Forum 29, 1, 75–87.Google ScholarCross Ref
31. Pernot, J.-P., Moraru, G., and Vron, P. 2006. Filling holes in meshes using a mechanical model to simulate the curvature variation minimization. Computers & Graphics 30, 6, 892–902. Google ScholarDigital Library
32. Podolak, J., and Rusinkiewicz, S. 2005. Atomic volumes for mesh completion. In Symposium on Geometry Processing. Google ScholarDigital Library
33. Pons, J.-P., and Boissonnat, J.-D. 2007. Delaunay deformable models: Topology-adaptive meshes based on the restricted delaunay triangulation. In Computer Vision and Pattern Recognition, 2007. CVPR ’07. IEEE Conference on, 1–8.Google Scholar
34. Shewchuk, J. R. 1996. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 305–363.Google ScholarCross Ref
35. Stanculescu, L., Chaine, R., and Cani, M.-P. 2011. Freestyle: Sculpting meshes with self-adaptive topology. Comput. Graph.-UK 35, 3 (June), 614–622. Special Issue: Shape Modeling International (SMI) Conference 2011. Google ScholarDigital Library
36. Strain, J. 2001. A fast semi-Lagrangian contouring method for moving interfaces. Journal of Computational Physics 170, 1, 373–394.Google ScholarCross Ref
37. Teschner, M., Heidelberger, B., Mueller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. 47–54.Google Scholar
38. Thuerey, N., Wojtan, C., Gross, M., and Turk, G. 2010. A Multiscale Approach to Mesh-based Surface Tension Flows. ACM Transactions on Graphics (SIGGRAPH) 29 (4) (July), 10. Google ScholarDigital Library
39. Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2009. Deforming meshes that split and merge. ACM Trans. Graph. 28, 3 (July), 76:1–76:10. Google ScholarDigital Library
40. Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2010. Physics-inspired topology changes for thin fluid features. ACM Trans. on Graphics (Proc. SIGGRAPH) 29, 3. Google ScholarDigital Library
41. Yu, J., and Turk, G. 2010. Reconstructing surfaces of particle-based fluids using anisotropic kernels. In Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SCA ’10, 217–225. Google ScholarDigital Library
42. Yu, J., Wojtan, C., Turk, G., and Yap, C. 2012. Explicit mesh surfaces for particle based fluids. EUROGRAPHICS 2012 30, 41–48.Google Scholar
43. Zaharescu, A., Boyer, E., and Horaud, R. 2007. TransforMesh : A Topology-Adaptive Mesh-Based Approach to Surface Evolution. In Asian Conference on Computer Vision, 166–175. Google ScholarDigital Library
44. Zhao, W., Gao, S., and Lin, H. 2007. A robust hole-filling algorithm for triangular mesh. In Computer-Aided Design and Computer Graphics, 2007 10th IEEE International Conference on, 22–22.Google Scholar
45. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. 24, 3 (July), 965–972. Google ScholarDigital Library