“Tracking surfaces with evolving topology” by Bojsen-Hansen, Li and Wojtan

  • ©Morten Bojsen-Hansen, Hao Li, and Chris Wojtan




    Tracking surfaces with evolving topology



    We present a method for recovering a temporally coherent, deforming triangle mesh with arbitrarily changing topology from an incoherent sequence of static closed surfaces. We solve this problem using the surface geometry alone, without any prior information like surface templates or velocity fields. Our system combines a proven strategy for triangle mesh improvement, a robust multi-resolution non-rigid registration routine, and a reliable technique for changing surface mesh topology. We also introduce a novel topological constraint enforcement algorithm to ensure that the output and input always have similar topology. We apply our technique to a series of diverse input data from video reconstructions, physics simulations, and artistic morphs. The structured output of our algorithm allows us to efficiently track information like colors and displacement maps, recover velocity information, and solve PDEs on the mesh as a post process.


    1. Bargteil, A., Goktekin, T., O’brien, J., and Strain, J. 2006. A semi-lagrangian contouring method for fluid simulation. ACM Transactions on Graphics (TOG) 25, 1, 19–38. Google ScholarDigital Library
    2. Bargteil, A., Sin, F., Michaels, J., Goktekin, T., and O’Brien, J. 2006. A texture synthesis method for liquid animations. In Proceedings of the 2006 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), Eurographics Association, 345–351. Google ScholarDigital Library
    3. Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., and Levy, B. 2010. Polygon mesh processing. AK Peters Ltd.Google Scholar
    4. 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
    5. Brochu, T., Batty, C., and Bridson, R. 2010. Matching fluid simulation elements to surface geometry and topology. ACM Transactions on Graphics (TOG) 29, 4, 47:1–47:9. Google ScholarDigital Library
    6. Campen, M., and Kobbelt, L. 2010. Exact and robust (self-) intersections for polygonal meshes. Computer Graphics Forum (Eurographics) 29, 2, 397–406.Google ScholarCross Ref
    7. Chang, W., Li, H., Mitra, N. J., Pauly, M., and Wand, M. 2010. Geometric registration for deformable shapes. In Eurographics 2010: Tutorial Notes.Google Scholar
    8. Dinh, H., Yezzi, A., Turk, G., et al. 2005. Texture transfer during shape transformation. ACM Transactions on Graphics (TOG) 24, 2, 289–310. Google ScholarDigital Library
    9. Du, J., Fix, B., Glimm, J., Jia, X., Li, X., Li, Y., and Wu, L. 2006. A simple package for front tracking. Journal of Computational Physics 213, 2, 613–628. Google ScholarDigital Library
    10. Enright, D., Marschner, S., and Fedkiw, R. 2002. Animation and rendering of complex water surfaces. ACM Transactions on Graphics (TOG) 21, 3, 736–744. Google ScholarDigital Library
    11. Goktekin, T., Bargteil, A., and O’Brien, J. 2004. A method for animating viscoelastic fluids. ACM Transactions on Graphics (TOG) 23, 3, 463–468. Google ScholarDigital Library
    12. Jiao, X. 2007. Face offsetting: A unified approach for explicit moving interfaces. Journal of computational physics 220, 2, 612–625. Google ScholarDigital Library
    13. Kagaya, M., Brendel, W., Deng, Q., Kesterson, T., Todorovic, S., Neill, P. J., and Zhang, E. 2011. Video painting with space-time-varying style parameters. IEEE Transactions on Visualization and Computer Graphics (TVCG) 17, 74–87. Google ScholarDigital Library
    14. Kim, B., Liu, Y., Llamas, I., and Rossignac, J. 2007. Advections with significantly reduced dissipation and diffusion. IEEE Transactions on Visualization and Computer Graphics (TVCG) 13, 135–144. Google ScholarDigital Library
    15. Kwatra, V., Adalsteinsson, D., Kim, T., Kwatra, N., Carlson, M., and Lin, M. 2007. Texturing fluids. IEEE Transactions on Visualization and Computer Graphics (TVCG) 13, 939–952. Google ScholarDigital Library
    16. Li, H., Adams, B., Guibas, L. J., and Pauly, M. 2009. Robust single-view geometry and motion reconstruction. ACM Transactions on Graphics (TOG) 28, 5, 175:1–175:10. Google ScholarDigital Library
    17. Li, H., Luo, L., Vlasic, D., Peers, P., Popović, J., Pauly, M., and Rusinkiewicz, S. 2012. Temporally coherent completion of dynamic shapes. ACM Transactions on Graphics (TOG) 31, 1, 2:1–2:11. Google ScholarDigital Library
    18. Mitra, N. J., Flory, S., Ovsjanikov, M., Gelfand, N., Guibas, L., and Pottmann, H. 2007. Dynamic geometry registration. In Proceedings of the fifth Eurographics Symposium on Geometry Processing (SGP), Eurographics Association, 173–182. Google ScholarDigital Library
    19. Müller, M. 2009. Fast and robust tracking of fluid surfaces. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), ACM, 237–245. Google ScholarDigital Library
    20. Osher, S., and Fedkiw, R. 2003. Level set methods and dynamic implicit surfaces, vol. 153. Springer.Google Scholar
    21. Pons, J., and Boissonnat, J. 2007. Delaunay deformablemodels: Topology-adaptive meshes based on the restricted delaunay triangulation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), IEEE, 1–8.Google Scholar
    22. Sharf, A., Alcantara, D. A., Lewiner, T., Greif, C., Sheffer, A., Amenta, N., and Cohen-Or, D. 2008. Space-time surface reconstruction using incompressible flow. ACM Transactions on Graphics (TOG) 27, 5, 110:1–110:10. Google ScholarDigital Library
    23. Stam, J., and Schmidt, R. 2011. On the velocity of an implicit surface. ACM Transactions on Graphics (TOG) 30, 3, 21:1–21:7. Google ScholarDigital Library
    24. Sumner, N., Hoon, S., Geiger, W., Marino, S., Rasmussen, N., and Fedkiw, R. 2003. Melting a terminatrix. In ACM SIGGRAPH 2003 Sketches & Applications, ACM.Google Scholar
    25. Süssmuth, J., Winter, M., and Greiner, G. 2008. Reconstructing animated meshes from time-varying point clouds. Computer Graphics Forum (SGP) 27, 5, 1469–1476. Google ScholarDigital Library
    26. Tevs, A., Berner, A., Wand, M., Ihrke, I., Bokeloh, M., Kerber, J., and Seidel, H.-P. 2012. Animation cartography – intrinsic reconstruction of shape and motion. ACM Transactions on Graphics (TOG) 31, 2, 12:1–12:15. Google ScholarDigital Library
    27. Thürey, N., Wojtan, C., Gross, M., and Turk, G. 2010. A multiscale approach to mesh-based surface tension flows. ACM Transactions on Graphics (TOG) 29, 4, 48:1–48:10. Google ScholarDigital Library
    28. Wand, M., Jenke, P., Huang, Q.-X., Bokeloh, M., Guibas, L., and Schilling, A. 2007. Reconstruction of deforming geometry from time-varying point clouds. In Proceedings of the fifth Eurographics Symposium on Geometry Processing (SGP), Eurographics Association, 49–58. Google ScholarDigital Library
    29. Wand, M., Adams, B., Ovsjanikov, M., Berner, A., Bokeloh, M., Jenke, P., Guibas, L., Seidel, H.-P., and Schilling, A. 2009. Efficient reconstruction of nonrigid shape and motion from real-time 3d scanner data. ACM Transactions on Graphics (TOG) 28, 2, 15:1–15:15. Google ScholarDigital Library
    30. Wang, H., Liao, M., Zhang, Q., Yang, R., and Turk, G. 2009. Physically guided liquid surface modeling from videos. ACM Transactions on Graphics (TOG) 28, 3, 90:1–90:11. Google ScholarDigital Library
    31. Wiebe, M., and Houston, B. 2004. The tar monster: Creating a character with fluid simulation. In ACM SIGGRAPH 2004 Sketches & Applications, ACM. Google ScholarDigital Library
    32. Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2009. Deforming meshes that split and merge. ACM Transactions on Graphics (TOG) 28, 3, 76:1–76:10. Google ScholarDigital Library
    33. Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2010. Physics-inspired topology changes for thin fluid features. ACM Transactions on Graphics (TOG) 29, 4, 50:1–50:8. Google ScholarDigital Library
    34. Wojtan, C., Müller-Fischer, M., and Brochu, T. 2011. Liquid simulation with mesh-based surface tracking. In ACM SIGGRAPH 2011 Courses, ACM. Google ScholarDigital Library
    35. Yu, J., Wojtan, C., Turk, G., and Yap, C. 2012. Explicit mesh surfaces for particle based fluids. Computer Graphics Forum (Eurographics) 31, 2, 41–48. Google ScholarDigital Library
    36. Zaharescu, A., Boyer, E., and Horaud, R. P. 2007. TransforMesh: a topology-adaptive mesh-based approach to surface evolution. In Proceedings of the Eighth Asian Conference on Computer Vision, Springer, vol. II of LNCS 4844, 166–175. Google ScholarDigital Library

ACM Digital Library Publication: