Skip to main content
SpringerLink
Log in

Template-based quadrilateral mesh generation from imaging data

  • Original Article
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

This paper describes a novel template-based meshing approach for generating good quality quadrilateral meshes from 2D digital images. This approach builds upon an existing image-based mesh generation technique called Imeshp, which enables us to create a segmented triangle mesh from an image without the need for an image segmentation step. Our approach generates a quadrilateral mesh using an indirect scheme, which converts the segmented triangle mesh created by the initial steps of the Imesh technique into a quadrilateral one. The triangle-to-quadrilateral conversion makes use of template meshes of triangles. To ensure good element quality, the conversion step is followed by a smoothing step, which is based on a new optimization-based procedure. We show several examples of meshes generated by our approach, and present a thorough experimental evaluation of the quality of the meshes given as examples.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alliez, P., Ucelli, G., Gotsman, C., Attene, M.: Recent advances in remeshing of surfaces. In: Floriani, L.D., Spagnuolo, M. (eds.) Shape Analysis and Structuring, Mathematics and Visualization. Springer, Berlin Heidelberg (2008)

    Google Scholar 

  2. Allman, D.: A quadrilateral finite element including vertex rotations for plane elasticity analysis. Int. J. Numer. Methods Eng. 26, 717–730 (1988)

    Article  MATH  Google Scholar 

  3. Atalay, F.B., Ramaswami, S., Xu, D.: Quadrilateral meshes with bounded minimum angle. In: Proceedings of the 17th International Meshing Roundtable (IMR), pp. 73–91 (2008)

    Chapter  Google Scholar 

  4. Bern, M., Plassmann, P.: Mesh generation. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Comput. Geom. Elsevier, Amsterdam (2000)

    Google Scholar 

  5. Berti, G.: Image-based unstructured 3D mesh generation for medical applications. In: ECCOMAS—European Congress on Computational Methods in Applied Sciences and Engineering (2004)

    Google Scholar 

  6. Boissonnat, J.D., Pons, J.P., Yvinec, M.: From segmented images to good quality meshes using Delaunay refinement. In: Lecture Notes in Computer Science, vol. 5416, pp. 13–37. Springer, Berlin (2009)

    Google Scholar 

  7. Johnston, B.P., Sullivan, J.M., Kwasnik, A.: Automatic conversion of triangular finite meshes to quadrilateral meshes. Int. J. Numer. Methods Eng. 31(1), 67–84 (1991)

    Article  MATH  Google Scholar 

  8. Cebral, J., Lohner, R.: From medical images to CFD meshes. In: Proc. of the 8th Intern. Meshing Roundtable, pp. 321–331 (1999)

    Google Scholar 

  9. Coleman, S., Scotney, B.: Mesh modeling for sparse image data set. In: IEEE ICIP, pp. 1342–1345. IEEE Computer Society, Los Alamitos (2005)

    Google Scholar 

  10. Cuadros-Vargas, A.J., Lizier, M.A.S., Minghim, R., Nonato, L.G.: Generating segmented quality meshes from images. J. Math. Imaging Vis. 33, 11–23 (2009)

    Article  MathSciNet  Google Scholar 

  11. Douglas, D.H., Peucker, T.K.: Algorithms for the reduction of the number of points required to represent a line or its caricature. Can. Cartogr. 10(2), 122–122 (1973)

    Google Scholar 

  12. Everett, H., Lenhart, W., Overmars, M., Shermer, T., Urrutia, J.: Strictly convex quadrilateralizations of polygons. In: Proceedings of the 4th Canadian Conference on Computational Geometry, pp. 77–82 (1992)

    Google Scholar 

  13. García, M., Sappa, A., Vintimilla, B.: Efficient approximation of gray-scale images through bounded error triangular meshes. In: IEEE Intern. Conf. on Image Processing, pp. 168–170 (1999)

    Google Scholar 

  14. Gevers, T., Smeulders, A.: Combining region splitting and edge detection through guided Delaunay image subdivision. In: IEEE Proceedings of CVPR, pp. 1021–1026 (1997)

    Google Scholar 

  15. Green, P., Sibson, R.: Computing Dirichlet tesselation in the plane. Comput. J. 21(2), 168–173 (1977)

    MathSciNet  Google Scholar 

  16. Herman, G.: Geometry of Digital Spaces. Birkhäuser, Boston (1998)

    MATH  Google Scholar 

  17. Knupp, P.M.: Algebraic mesh quality metrics. SIAM J. Sci. Comput. 23(1), 193–218 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  18. Kocharoen, P., Ahmed, K., Rajatheva, R., Fernando, W.: Adaptive mesh generation for mesh-based image coding using node elimination approach. In: IEEE International Conference on Image Processing, pp. 2052–2056 (2005)

    Google Scholar 

  19. Lai, M.J.: Scattered data interpolation and approximation using bivariate c 1 piecewise cubic polynomials. Comput. Aided Geom. Des. 13(1), 81–88 (1996)

    Article  MATH  Google Scholar 

  20. Lawson, C.L., Hanson, R.J.: Solving least squares problem. In: Classics in Applied Mathematics, vol. 15. SIAM, Philadelphia (1995)

    Google Scholar 

  21. Lizier, M.A.S., Martins, D.C. Jr., Cuadros-Vargas, A.J., Cesar, R.M. Jr., Nonato, L.G.: Generating segmented meshes from textured color images. J. Vis. Commun. Image Represent. 20, 190–203 (2009)

    Article  Google Scholar 

  22. Malanthara, A., Gerstle, W.: Comparative study of unstructured meshes made of triangles and quadrilaterals. In: Proceedings of the 6th International Meshing Roundtable (IMR), pp. 437–447 (1997)

    Google Scholar 

  23. Miller, G., Pave, S., Walkington, N.: When and why Ruppert’s algorithm works. In: Proceedings of the 12th International Meshing Roundtable (IMR), pp. 91–102 (2003)

    Google Scholar 

  24. Owen, S., Staten, M., Cannan, S., Saigal, S.: Q-morph: an indirect approach to advancing front quad meshing. Int. J. Numer. Methods Eng. 9(44), 1317–1340 (1999)

    Article  Google Scholar 

  25. Powell, M.J.D.: An efficient method for finding the minimum of a function of several variables without calculating derivatives. Comput. J. 7(2), 155–162 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  26. Ramaswami, S., Ramos, P., Toussaint, G.: Converting triangulations to quadrangulations. Comput. Geom. Theory Appl. 9(4), 257–276 (1998)

    MathSciNet  MATH  Google Scholar 

  27. Ramaswami, S., Siqueira, M., Sundaram, T., Gallier, J., Gee, J.: Constrained quadrilateral meshes of bounded size. Int. J. Comput. Geom. Appl. 15(1), 55–98 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  28. Ruppert, J.: A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J. Algorithms 18(3), 548–585 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  29. Schneiders, R.: Refining quadrilateral and hexahedral element meshes. In: Proc. 5th International Conference on Numerical Grid Generation in Computational Field Simulations, pp. 679–688 (1996)

    Google Scholar 

  30. Shamir, A.: A survey on mesh segmentation techniques. Comput. Graph. Forum 27(6), 1539–1556 (2007)

    Article  MathSciNet  Google Scholar 

  31. Shewchuk, J.: What is a good linear element? Interpolation, conditioning, and quality measures. In: Proceeding of the 11th International Meshing Roundtable, pp. 115–126 (2002)

    Google Scholar 

  32. Shimada, K., Liao, J.H., Itoh, T.: Quadrilateral meshing with directionality control through the packing of square cells. In: Proceedings of the 7th International Meshing Roundtable, Dearborn, Michigan, USA, pp. 61–76 (1998)

    Google Scholar 

  33. Skrinjar, O., Bistoquet, A.: Generation of myocardial wall surface meshes from segmented MRI. Int. J. Biomed. Imaging (2009). doi:10.1155/2009/313517

    MATH  Google Scholar 

  34. Staples, J., Eades, P., Katoh, N., Moffat, A. (eds.): No Quadrangulation is Extremely Odd. Lecture Notes in Computer Science, Cairns, Australia, vol. 1004. Springer, Berlin (1995)

    Google Scholar 

  35. Velho, L., Zorin, D.: 4–8 subdivision. Comput. Aided Geom. Des. 18(5), 397–427 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  36. Viswanath, N., Shimada, K., Itoh, T.: Quadrilateral meshing with anisotropy and directionality control via close packing of rectangular cells. In: Proceedings of the 9th International Meshing Roundtable, New Orleans, Louisiana, USA, pp. 217–225 (2000)

    Google Scholar 

  37. Yang, Y., Wernick, M., Brankov, J.: A fast approach for accurate content-adaptive mesh generation. IEEE Trans. Image Process. 12(8), 866–881 (2003)

    Article  MathSciNet  Google Scholar 

  38. Zhang, Y., Bajaj, C., Sohn, B.S.: Adaptive and quality 3D meshing from imaging data. In: SM’03: Proceedings of the Eighth ACM Symposium on Solid Modeling and Applications, pp. 286–291 (2003)

    Chapter  Google Scholar 

  39. Teng, S.-H., Wong, C.W.: Unstructured mesh generation: theory, practice, and perspectives. Int. J. Comput. Geom. Appl. 10(3), 227–266 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  40. Daniels, J., Nonato, L.G., Siqueira, M., Liziér, M., Silva, C.T.: In: SMI’11: Proceedings of the Shape Modeling International (2011, to appear)

Download references

Author information

Authors and Affiliations

  1. Departamento de Computação, Universidade Federal de São Carlos, São Carlos, Brazil

    Mario A. S. Liziér

  2. Departamento de Informática e Matemática Aplicada, Universidade Federal do Rio Grande do Norte, Natal, Brazil

    Marcelo F. Siqueira

  3. Scientific Computing and Imaging Institute, University of Utah, Salt Lake City, USA

    Joel Daniels II

  4. Computer Science and Engineering Polytechnic Institute, New York University, New York, USA

    Claudio T. Silva

  5. Instituto de Ciências Matemáticas e de Computação, Universidade de São Paulo, São Paulo, Brazil

    L. Gustavo Nonato

Authors
  1. Mario A. S. Liziér
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marcelo F. Siqueira
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Joel Daniels II
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Claudio T. Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. L. Gustavo Nonato
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mario A. S. Liziér.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liziér, M.A.S., Siqueira, M.F., Daniels, J. et al. Template-based quadrilateral mesh generation from imaging data. Vis Comput 27, 887–903 (2011). https://doi.org/10.1007/s00371-011-0603-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00371-011-0603-x

Keywords

Search

Navigation