“Robust inside-outside segmentation using generalized winding numbers” by Jacobson, Kavan and Sorkine-Hornung

  • ©Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung



Session Title:

    Geometry & Topology


    Robust inside-outside segmentation using generalized winding numbers




    Solid shapes in computer graphics are often represented with boundary descriptions, e.g. triangle meshes, but animation, physically-based simulation, and geometry processing are more realistic and accurate when explicit volume representations are available. Tetrahedral meshes which exactly contain (interpolate) the input boundary description are desirable but difficult to construct for a large class of input meshes. Character meshes and CAD models are often composed of many connected components with numerous self-intersections, non-manifold pieces, and open boundaries, precluding existing meshing algorithms. We propose an automatic algorithm handling all of these issues, resulting in a compact discretization of the input’s inner volume. We only require reasonably consistent orientation of the input triangle mesh. By generalizing the winding number for arbitrary triangle meshes, we define a function that is a perfect segmentation for watertight input and is well-behaved otherwise. This function guides a graphcut segmentation of a constrained Delaunay tessellation (CDT), providing a minimal description that meets the boundary exactly and may be fed as input to existing tools to achieve element quality. We highlight our robustness on a number of examples and show applications of solving PDEs, volumetric texturing and elastic simulation.


    1. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3. Google ScholarDigital Library
    2. Alliez, P., Cohen-Steiner, D., Tong, Y., and Desbrun, M. 2007. Voronoi-based variational reconstruction of unoriented point sets. In Proc. SGP. Google ScholarDigital Library
    3. Attene, M., Ferri, M., and Giorgi, D. 2007. Combinatorial 3-manifolds from sets of tetrahedra. In Proc. CW. 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. Baran, I., and Popović, J. 2007. Automatic rigging and animation of 3D characters. ACM Trans. Graph. 26, 3, 72:1–72:8. Google ScholarDigital Library
    6. Bischoff, S., and Kobbelt, L. 2005. Structure preserving CAD model repair. Comput. Graph. Forum 24, 3, 527–536.Google ScholarCross Ref
    7. Bischoff, S., Pavic, D., and Kobbelt, L. 2005. Automatic restoration of polygon models. ACM Trans. Graph. 24, 4. Google ScholarDigital Library
    8. Borodin, P., Zachmann, G., and Klein, R. 2004. Consistent normal orientation for polygonal meshes. In Proc. CGI. Google ScholarDigital Library
    9. Boykov, Y., and Funka-Lea, G. 2006. Graph cuts and efficient ND image segmentation. IJCV 70, 2. Google ScholarDigital Library
    10. Bridson, R., Teran, J., Molino, N., and Fedkiw, R. 2005. Adaptive physics based tetrahedral mesh generation using level sets. Engineering with Computers 21, 1, 2–18. Google ScholarDigital Library
    11. Bronstein, A. M., Bronstein, M. M., Castellani, U., Falcidieno, B., Fusiello, A., Godil, A., Guibas, L. J., Kokkinos, I., Lian, Z., Ovsjanikov, M., Patané, G., Spagnuolo, M., and Toldo, R. 2010. SHREC 2010: robust large-scale shape retrieval benchmark. In Proc. 3DOR, 71–78. Google ScholarDigital Library
    12. Campen, M., and Kobbelt, L. 2010. Exact and robust (self-)intersections for polygonal meshes. Comput. Graph. Forum 29, 2.Google ScholarCross Ref
    13. Campen, M., Attene, M., and Kobbelt, L., 2012. A practical guide to polygon mesh repairing. Eurographics Tutorial.Google Scholar
    14. Cgal, Computational Geometry Algorithms Library. http://www.cgal.org.Google Scholar
    15. Char, B., Geddes, K., and Gonnet, G. 1983. The Maple symbolic computation system. SIGSAM Bull. 17, 3–4, 31–42. Google ScholarDigital Library
    16. Chen, C., Freedman, D., and Lampert, C. 2011. Enforcing topological constraints in random field image segmentation. In Proc. CVPR. Google ScholarDigital Library
    17. Davis, J., Marschner, S. R., Garr, M., and Levoy, M. 2002. Filling holes in complex surfaces using volumetric diffusion. In Proc. 3DPVT, 428–438.Google Scholar
    18. Dey, T. K., and Goswami, S. 2003. Tight cocone: a water-tight surface reconstructor. In Proc. SM. Google ScholarDigital Library
    19. Floater, M. S. 2003. Mean value coordinates. Computer-Aided Geometric Design 20, 1, 19–27. Google ScholarDigital Library
    20. George, P. L., Hecht, F., and Saltel, E. 1990. Automatic 3D mesh generation with prescribed meshed boundaries. IEEE Transactions on Magnetics 26, 2, 771–774.Google ScholarCross Ref
    21. Geuzaine, C., and Remacle, J. F. 2009. gmsh: A 3-D finite element mesh generator with built-in pre- and post-processing. Numerical Methods in Engineering.Google Scholar
    22. Guéziec, A., Taubin, G., Lazarus, F., and Hom, B. 2001. Cutting and stitching: Converting sets of polygons to manifold surfaces. IEEE TVCG 7, 2. Google ScholarDigital Library
    23. Hoppe, H., Derose, T., Duchamp, T., Mcdonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In Proc. ACM SIGGRAPH. Google ScholarDigital Library
    24. Hoppe, H., Derose, T., Duchamp, T., Mcdonald, J., and Stuetzle, W. 1993. Mesh optimization. In Proc. ACM SIGGRAPH. Google ScholarDigital Library
    25. Hornung, A., and Kobbelt, L. 2006. Robust reconstruction of watertight 3D models from non-uniformly sampled point clouds without normal information. In Proc. SGP. Google ScholarDigital Library
    26. Houston, B., Bond, C., and Wiebe, M. 2003. A unified approach for modeling complex occlusions in fluid simulations. In ACM SIGGRAPH 2003 Sketches & Applications. Google ScholarDigital Library
    27. Jacobson, A., Baran, I., Popović, J., and Sorkine, O. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4. Google ScholarDigital Library
    28. Joshi, B., and Ourselin, S. 2003. BSP-assisted constrained tetrahedralization. In Proc. IMR, 251–260.Google Scholar
    29. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3. Google ScholarDigital Library
    30. Ju, T. 2004. Robust repair of polygonal models. ACM Trans. Graph. 23, 3. Google ScholarDigital Library
    31. Ju, T. 2009. Fixing geometric errors on polygonal models: a survey. Journal of Computer Science and Technology 24, 1. Google ScholarDigital Library
    32. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Proc. SGP. Google ScholarDigital Library
    33. Klingner, B. M., and Shewchuk, J. R. 2007. Agressive tetrahedral mesh improvement. In Proc. IMR.Google Scholar
    34. Kolluri, R., Shewchuk, J., and O’Brien, J. 2004. Spectral surface reconstruction from noisy point clouds. In Proc. SGP. Google ScholarDigital Library
    35. Kolmogorov, V., and Zabin, R. 2004. What energy functions can be minimized via graph cuts? IEEE PAMI 26, 2. Google ScholarDigital Library
    36. Kraevoy, V., Sheffer, A., and Gotsman, C. 2003. Matchmaker: constructing constrained texture maps. ACM Trans. Graph. 22, 3. Google ScholarDigital Library
    37. Labelle, F., and Shewchuk, J. R. 2007. Isosurface stuffing: fast tetrahedral meshes with good dihedral angles. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
    38. McAdams, A., Zhu, Y., Selle, A., Empey, M., Tamstorf, R., Teran, J., and Sifakis, E. 2011. Efficient elasticity for character skinning with contact and collisions. ACM Trans. Graph. 30, 37:1–37:12. Google ScholarDigital Library
    39. Meister, A. 1769/70. Generalia de genesi figurarum planarum et inde pendentibus earum ajfectionibus. Novi Comm. Soc. Reg. Scient. Gotting., 144–180+9 plates.Google Scholar
    40. Mullen, P., De Goes, F., Desbrun, M., Cohen-Steiner, D., and Alliez, P. 2010. Signing the unsigned: Robust surface reconstruction from raw pointsets. Comput. Graph. Forum 29, 5.Google ScholarCross Ref
    41. Murali, T. M., and Funkhouser, T. A. 1997. Consistent solid and boundary representations from arbitrary polygonal data. In Proc. I3D. Google ScholarDigital Library
    42. Nooruddin, F. S., and Turk, G. 2003. Simplification and repair of polygonal models using volumetric techniques. IEEE TVCG 9, 2. Google ScholarDigital Library
    43. Orzan, A., Bousseau, A., Winnemöller, H., Barla, P., Thollot, J., and Salesin, D. 2008. Diffusion curves: a vector representation for smooth-shaded images. ACM Trans. Graph. 27, 3, 92:1–92:8. Google ScholarDigital Library
    44. Podolak, J., and Rusinkiewicz, S. 2005. Atomic volumes for mesh completion. In Proc. SGP. Google ScholarDigital Library
    45. Schöberl, J. 1997. NETGEN: An advancing front 2D/3D-mesh generator based on abstract rules. Computing and Visualization in Science.Google Scholar
    46. Shen, C., O’Brien, J. F., and Shewchuk, J. R. 2004. Interpolating and approximating implicit surfaces from polygon soup. ACM Trans. Graph. 23, 3, 896–904. Google ScholarDigital Library
    47. Shewchuk, J. R. 1996. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering, vol. 1148 of Lecture Notes in Computer Science. 203–222. Google ScholarDigital Library
    48. Shewchuk, J. 2012. Unstructured mesh generation. Combinatorial Scientific Computing 12, 257.Google ScholarCross Ref
    49. Shimada, K., and Gossard, D. C. 1995. Bubble mesh: automated triangular meshing of non-manifold geometry by sphere packing. In Proc. SMA, 409–419. Google ScholarDigital Library
    50. Si, H., 2003. TetGen: A 3D Delaunay tetrahedral mesh generator. http://tetgen.berlios.de.Google Scholar
    51. Takayama, K., Okabe, M., Ijiri, T., and Igarashi, T. 2008. Lapped solid textures: Filling a model with anisotropic textures. ACM Trans. Graph. 27, 3. Google ScholarDigital Library
    52. Turk, G., and Levoy, M. 1994. Zippered polygon meshes from range images. In Proc. ACM SIGGRAPH. Google ScholarDigital Library
    53. van Oosterom, A., and Strackee, J. 1983. The solid angle of a plane triangle. IEEE Trans. Biomedical Engineering 30, 2.Google Scholar
    54. Wan, M., Wang, Y., and Wang, D. 2011. Variational surface reconstruction based on Delaunay triangulation and graph cut. Int. Journal of Numerical Engineering.Google ScholarCross Ref
    55. Wan, M., Wang, Y., Bae, E., Tai, X., and Wang, D. 2012. Reconstructing open surfaces via graph-cuts. IEEE TVCG 19, 2. Google ScholarDigital Library
    56. Yamakawa, S., and Shimada, K. 2009. Removing self intersections of a triangular mesh by edge swapping, edge hammering, and face lifting. In Proc. IMR.Google Scholar
    57. Zhang, L., Cui, T., and Liu, H. 2009. A set of symmetric quadrature rules on triangles and tetrahedra. J. Comput. Math 27, 1, 89–96.Google Scholar
    58. Zhang, S., Nealen, A., and Metaxas, D. 2010. Skeleton based as-rigid-as-possible volume modeling. In Proc. Eurographics, short papers volume, 21–24.Google Scholar
    59. Zhou, K., Huang, J., Snyder, J., Liu, X., Bao, H., Guo, B., and Shum, H.-Y. 2005. Large mesh deformation using the volumetric graph Laplacian. ACM Trans. Graph, 24, 3, 496–503. Google ScholarDigital Library
    60. Zhou, K., Zhang, E., Bittner, J., and Wonka, P. 2008. Visibility-driven mesh analysis and visualization through graph cuts. IEEE TVCG 14, 6. Google ScholarDigital Library

ACM Digital Library Publication: