“Robust inside-outside segmentation using generalized winding numbers” by Jacobson, Kavan and Sorkine-Hornung
Conference:
Type(s):
Title:
- Robust inside-outside segmentation using generalized winding numbers
Session/Category Title: Geometry & Topology
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
