“Instant field-aligned meshes” by Jakob, Tarini, Panozzo and Sorkine-Hornung
Conference:
Type(s):
Title:
- Instant field-aligned meshes
Session/Category Title: Mappings and Parameterizations
Presenter(s)/Author(s):
Abstract:
We present a novel approach to remesh a surface into an isotropic triangular or quad-dominant mesh using a unified local smoothing operator that optimizes both the edge orientations and vertex positions in the output mesh. Our algorithm produces meshes with high isotropy while naturally aligning and snapping edges to sharp features. The method is simple to implement and parallelize, and it can process a variety of input surface representations, such as point clouds, range scans and triangle meshes. Our full pipeline executes instantly (less than a second) on meshes with hundreds of thousands of faces, enabling new types of interactive workflows. Since our algorithm avoids any global optimization, and its key steps scale linearly with input size, we are able to process extremely large meshes and point clouds, with sizes exceeding several hundred million elements. To demonstrate the robustness and effectiveness of our method, we apply it to hundreds of models of varying complexity and provide our cross-platform reference implementation in the supplemental material.
References:
1. Aksoylu, B., Khodakovsky, A., and Schröder, P. 2005. Multilevel solvers for unstructured surface meshes. SIAM J. Sci. Comput. 26, 4 (Apr.).
2. Alliez, P., Meyer, M., and Desbrun, M. 2002. Interactive geometry remeshing. ACM Trans. Graph. 21, 3.
3. Alliez, P., Cohen-Steiner, D., Devillers, O., Lévy, B., and Desbrun, M. 2003. Anisotropic polygonal remeshing. ACM Trans. Graph. 22, 3.
4. Alliez, P., de Verdiére, E. C., Devillers, O., and Isenburg, M. 2005. Centroidal Voronoi diagrams for isotropic surface remeshing. Graphical Models 67, 3.
5. Anderson, R. J., and Woll, H. 1991. Wait-free parallel algorithms for the union-find problem. In Proc. STOC.
6. Belkin, M., Sun, J., and Wang, Y. 2009. Constructing laplace operator from point clouds in rd. In Proc. ACM-SIAM Symposium on Discrete Algorithms.
7. Bommes, D., Zimmer, H., and Kobbelt, L. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3.
8. Bommes, D., Lévy, B., Pietroni, N., Puppo, E., Silva, C., Tarini, M., and Zorin, D. 2013. Quad-mesh generation and processing: A survey. Comput. Graph. Forum 32.
9. Bommes, D., Campen, M., Ebke, H.-C., Alliez, P., and Kobbelt, L. 2013. Integer-grid maps for reliable quad meshing. ACM Trans. Graph. 32, 4.
10. Botsch, M., Pauly, M., Gross, M., and Kobbelt, L. 2006. Primo: Coupled prisms for intuitive surface modeling. In In Proc. Symposium of Geometry Processing 2006.
11. Botsch, M., Pauly, M., Rossl, C., Bischoff, S., and Kobbelt, L. 2006. Geometric modeling based on triangle meshes. In ACM SIGGRAPH 2006 Courses.
12. Campen, M., and Kobbelt, L. 2014. Dual strip weaving: Interactive design of quad layouts using elastica strips. ACM Trans. Graph. 33, 6.
13. Catmull, E., and Clark, J. 1978. Recursively generated b-spline surfaces on arbitrary topological meshes. Computer-Aided Design 10, 6.
14. Crane, K., Desbrun, M., and Schröder, P. 2010. Trivial connections on discrete surfaces. Comput. Graph. Forum 29, 5.
15. Daniels, J., Silva, C. T., Shepherd, J., and Cohen, E. 2008. Quadrilateral mesh simplification. ACM Trans. Graph. 27, 5.
16. DeRose, T., Kass, M., and Truong, T. 1998. Subdivision surfaces in character animation. In Proc. ACM SIGGRAPH.
17. Diamanti, O., Vaxman, A., Panozzo, D., and Sorkine-Hornung, O. 2014. Designing N-PolyVector fields with complex polynomials. Comput. Graph. Forum 33, 5.
18. Diamanti, O., Vaxman, A., Panozzo, D., and Sorkine-Hornung, O. 2015. Integrable PolyVector fields. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH) 34, 4.
19. Ebke, H.-C., Bommes, D., Campen, M., and Kobbelt, L. 2013. QEx: Robust quad mesh extraction. ACM Trans. Graph..
20. Ebke, H.-C., Campen, M., Bommes, D., and Kobbelt, L. 2014. Level-of-detail quad meshing. ACM Trans. Graph. 33, 6.
21. Gu, X., Gortler, S. J., and Hoppe, H. 2002. Geometry images. ACM Trans. Graph. 21, 3.
22. Hertzmann, A., and Zorin, D. 2000. Illustrating smooth surfaces. In Proc. ACM SIGGRAPH.
23. Hoppe, H., Derose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1993. Mesh optimization. In Proc. ACM SIGGRAPH.
24. Huang, J., Zhang, M., Ma, J., Liu, X., Kobbelt, L., and Bao, H. 2008. Spectral quadrangulation with orientation and alignment control. ACM Trans. Graph. 27, 5.
25. Jiang, T., Fang, X., Huang, J., Bao, H., Tong, Y., and Desbrun, M. 2015. Frame field generation through metric customization. ACM Trans. Graph. 34, 4.
26. Kälberer, F., Nieser, M., and Polthier, K. 2007. Quad-Cover — surface parameterization using branched coverings. Comput. Graph. Forum 26, 3.
27. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Proc. Eurographics Symposium on Geometry Processing.
28. Khodakovsky, A., Litke, N., and Schröder, P. 2003. Globally smooth parameterizations with low distortion. ACM Trans. Graph. 22, 3.
29. Knöppel, F., Crane, K., Pinkall, U., and Schröder, P. 2013. Globally optimal direction fields. ACM Trans. Graph..
30. Kovacs, D., Bisceglio, J., and Zorin, D. 2015. Dyadic t-mesh subdivision. ACM Trans. Graph. 34, 4 (July).
31. Lai, Y.-K., Kobbelt, L., and Hu, S.-M. 2008. An incremental approach to feature aligned quad dominant remeshing. In Proc. ACM Symposium on Solid and Physical Modeling.
32. Lai, Y.-K., Jin, M., Xie, X., He, Y., Palacios, J., Zhang, E., Hu, S.-M., and Gu, X. 2010. Metric-driven rosy field design and remeshing. IEEE TVCG 16, 1.
33. Levi, Z., and Zorin, D. 2014. Strict minimizers for geometric optimization. ACM Trans. Graph. 33, 6.
34. Levoy, M., Pulli, K., Curless, B., Rusinkiewicz, S., Koller, D., Pereira, L., Ginzton, M., Anderson, S., Davis, J., Ginsberg, J., Shade, J., and Fulk, D. 2000. The digital Michelangelo project: 3D scanning of large statues. In Proc. ACM SIGGRAPH.
35. Lévy, B., and Liu, Y. 2010. Lp centroidal voronoi tessellation and its applications. ACM Trans. Graph. 29, 4 (July).
36. Li, E. R., Lévy, B., Zhang, X., Che, W.-J., Dong, W., and Paul, J.-C. 2011. Meshless quadrangulation by global parameterization. Computers and Graphics.
37. Lindstrom, P., and Turk, G. 2000. Image-driven simplification. ACM Trans. Graph. 19, 3.
38. Ling, R., Huang, J., Jüttler, B., Sun, F., Bao, H., and Wang, W. 2014. Spectral quadrangulation with feature curve alignment and element size control. ACM Trans. Graph. 34, 1.
39. Lorensen, W. E., and Cline, H. E. 1987. Marching cubes: A high resolution 3D surface construction algorithm. In Proc. ACM SIGGRAPH.
40. Marinov, M., and Kobbelt, L. 2004. Direct anisotropic quad-dominant remeshing. In Proc. Pacific Graphics.
41. Marinov, M., and Kobbelt, L. 2006. A robust two-step procedure for quad-dominant remeshing. Computer Graphics Forum.
42. Micciancio, D. 2001. The shortest vector problem is NP-hard to approximate to within some constant. SIAM Journal on Computing 30, 6 (Mar.). Preliminary version in FOCS 1998.
43. Myles, A., and Zorin, D. 2013. Controlled-distortion constrained global parametrization. ACM Trans. Graph. 32, 4.
44. Myles, A., Pietroni, N., Kovacs, D., and Zorin, D. 2010. Feature-aligned t-meshes. ACM Trans. Graph. 29, 4.
45. Myles, A., Pietroni, N., and Zorin, D. 2014. Robust field-aligned global parametrization. ACM Trans. Graph. 33, 4.
46. Nieser, M., Palacios, J., Polthier, K., and Zhang, E. 2012. Hexagonal global parameterization of arbitrary surfaces. IEEE Trans. Visualization and Computer Graphics 18, 6.
47. Owen, S. J. 1998. A survey of unstructured mesh generation technology. In Proc. IMR.
48. Palacios, J., and Zhang, E. 2007. Rotational symmetry field design on surfaces. ACM Trans. Graph. 26, 3.
49. Panozzo, D., Puppo, E., Tarini, M., and Sorkine-Hornung, O. 2014. Frame fields: Anisotropic and non-orthogonal cross fields. ACM Trans. Graph. 33, 4.
50. Peng, C.-H., Zhang, E., Kobayashi, Y., and Wonka, P. 2011. Connectivity editing for quadrilateral meshes. ACM Trans. Graph. 30, 6.
51. Pietroni, N., Tarini, M., and Cignoni, P. Almost isometric mesh parameterization through abstract domains. IEEE Trans. Visualization and Computer Graphics 16, 4.
52. Pietroni, N., Tarini, M., Sorkine, O., and Zorin, D. 2011. Global parametrization of range image sets. ACM Trans. Graph..
53. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experiment. Math. 2, 1.
54. Ray, N., Li, W. C., Lévy, B., Sheffer, A., and Alliez, P. 2006. Periodic global parameterization. ACM Trans. Graph..
55. Ray, N., Vallet, B., Li, W. C., and Lévy, B. 2008. N-symmetry direction field design. ACM Trans. Graph. 27, 2.
56. Sederberg, T. W., Zheng, J., Bakenov, A., and Nasri, A. 2003. T-splines and T-NURCCs. ACM Trans. Graph. 22, 3.
57. Sifri, O., Sheffer, A., and Gotsman, C. 2003. Geodesic-based surface remeshing. In Proc. Intnl. Meshing Roundtable.
58. Surazhsky, V., and Gotsman, C. 2003. Explicit surface remeshing. In Proc. Symposium on Geometry Processing.
59. Surazhsky, V., Alliez, P., and Gotsman, C. 2003. Isotropic remeshing of surfaces: A local parameterization approach. In Proc. International Meshing Roundtable.
60. Takayama, K., Panozzo, D., Sorkine-Hornung, A., and Sorkine-Hornung, O. 2013. Sketch-based generation and editing of quad meshes. ACM Trans. Graph. 32, 4.
61. Tarini, M., Pietroni, N., Cignoni, P., Panozzo, D., and Puppo, E. 2010. Practical quad mesh simplification. Comput. Graph. Forum 29, 2.
62. Taubin, G. 1995. A signal processing approach to fair surface design. In Proc. ACM SIGGRAPH.
63. Turk, G. 1992. Re-tiling polygonal surfaces. In Proc. ACM SIGGRAPH.
64. Yan, D.-M., Lévy, B., Liu, Y., Sun, F., and Wang, W. 2009. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. Comput. Graph. Forum 28, 5.
65. Zhang, E., Mischaikow, K., and Turk, G. 2006. Vector field design on surfaces. ACM Trans. Graph. 25, 4 (Oct.).
66. Zhang, M., Huang, J., Liu, X., and Bao, H. 2010. A wave-based anisotropic quadrangulation method. ACM Trans. Graph..
