Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Instant field-aligned meshes

Published: 02 November 2015 Publication History

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.

Supplementary Material

ZIP File (a189-jakob.zip)
Supplemental files.

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.

Cited By

View all
  • (2024)Evaluation of Denoising and Voxelization Algorithms on 3D Point CloudsRemote Sensing10.3390/rs1614263216:14(2632)Online publication date: 18-Jul-2024
  • (2024)Reviving Antiquity in the Digital Era: Digitization, Semantic Curation, and VR Exhibition of Contemporary DressesComputers10.3390/computers1303005713:3(57)Online publication date: 22-Feb-2024
  • (2024)Bicubic Splines for Fast-Contracting Control NetsAxioms10.3390/axioms1306039013:6(390)Online publication date: 9-Jun-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 34, Issue 6
November 2015
944 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/2816795
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 November 2015
Published in TOG Volume 34, Issue 6

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. N-RoSy
  2. extrinsic smoothing
  3. point cloud
  4. quadrangulation
  5. range scan
  6. remeshing
  7. triangulation

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)206
  • Downloads (Last 6 weeks)36
Reflects downloads up to 22 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Evaluation of Denoising and Voxelization Algorithms on 3D Point CloudsRemote Sensing10.3390/rs1614263216:14(2632)Online publication date: 18-Jul-2024
  • (2024)Reviving Antiquity in the Digital Era: Digitization, Semantic Curation, and VR Exhibition of Contemporary DressesComputers10.3390/computers1303005713:3(57)Online publication date: 22-Feb-2024
  • (2024)Bicubic Splines for Fast-Contracting Control NetsAxioms10.3390/axioms1306039013:6(390)Online publication date: 9-Jun-2024
  • (2024) Cartography of Touch : Transformation of Touch through Anatomical Projections Leonardo10.1162/leon_a_0240357:1(25-32)Online publication date: 1-Feb-2024
  • (2024)Proxy Asset Generation for Cloth Simulation in GamesACM Transactions on Graphics10.1145/365817743:4(1-12)Online publication date: 19-Jul-2024
  • (2024)CWF: Consolidating Weak Features in High-quality Mesh SimplificationACM Transactions on Graphics10.1145/365815943:4(1-14)Online publication date: 19-Jul-2024
  • (2024)Fabric Tessellation: Realizing Freeform Surfaces by SmockingACM Transactions on Graphics10.1145/365815143:4(1-20)Online publication date: 19-Jul-2024
  • (2024)Digital reconstruction of partially lost altarpieces. The case of the Rosary's altarpiece of Sant Pere Màrtir de ManresaJournal on Computing and Cultural Heritage 10.1145/365286017:3(1-18)Online publication date: 15-May-2024
  • (2024)Singular Foliations for Knit Graph DesignACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657487(1-11)Online publication date: 13-Jul-2024
  • (2024)Designing Bending-Active Freeform SurfacesProceedings of the 9th ACM Symposium on Computational Fabrication10.1145/3639473.3665793(1-11)Online publication date: 7-Jul-2024
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media