Meshing interfaces of multi-label data with Delaunay refinement | Engineering with Computers Skip to main content
Springer Nature Link
Log in

Meshing interfaces of multi-label data with Delaunay refinement

  • Original Article
  • Published:
Engineering with Computers Aims and scope Submit manuscript

Abstract

In medical imaging, the generation of surface representations of anatomical objects obtained by labeling images from various modalities, is a critical component for visualization, simulation, and analysis. The interfaces between labeled regions can meet at arbitrary angles and with complex topologies, causing most automatic meshing algorithms to fail. We apply a recent Delaunay refinement algorithm to generate high quality triangular meshes that approximate the interface surfaces. This algorithm has proven guarantees for meshing piecewise-smooth shapes and its implementation overhead is low. Consequently, the approach is applicable to labeled datasets generated from binary segmentations as well as from probabilistic segmentation algorithms. We show the effectiveness of this technique on data from a variety of medical fields and discuss its ability to control the quality and size of the output meshes. The same algorithm can be used to generate tetrahedral meshes of the segmentation space.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Ahn HT, Shashkov M (2007) Multi-material interface reconstruction on generalized polyhedral meshes. J Comput Phys 226(2):2096–2132

    Article  MATH  MathSciNet  Google Scholar 

  2. Anderson JC, Garth C, Duchaineau MA, Joy KI (2008) Discrete multi-material interface reconstruction for volume fraction data. Comput Graph Forum 27(3):1015–1022

    Article  Google Scholar 

  3. Banks DC, Linton SA (2003) Counting cases in marching cubes: toward a generic algorithm for producing substitopes. In: IEEE Visualization, pp 51–58

  4. Bertram M, Reis G, van Lengen RH, Köhn S, Hagen H (2005) Non-manifold mesh extraction from time-varying segmented volumes used for modeling a human heart. In: EuroVis05, pp 199–206

  5. Bloomenthal J, Ferguson K (1995) Polygonization of non-manifold implicit surfaces. In: SIGGRAPH, pp 309–316

  6. Boissonnat JD, Oudot S (2005) Provably good sampling and meshing of surfaces. Graph Models 67(5):405–451

    Article  MATH  Google Scholar 

  7. Boltcheva D, Yvinec M, Boissonnat JD (2009) Feature preserving Delaunay mesh generation from 3D multi-material images. Comput Graph Forum 28(5):1455–1464

    Article  Google Scholar 

  8. Bonnell KS, Duchaineau MA, Schikore D, Hamann B, Joy KI (2003) Material interface reconstruction. IEEE Trans Vis Comput Graph 9(4):500–511

    Article  Google Scholar 

  9. Cheng SW, Dey TK, Edelsbrunner H, Facello MA, Teng SH (2000) Sliver exudation. J ACM 47(5):883–904

    Article  MathSciNet  Google Scholar 

  10. Cheng SW, Dey TK, Ramos EA (2010) Delaunay refinement for piecewise smooth complexes. Discret Comput Geom 43(1):121–166

    Article  MATH  MathSciNet  Google Scholar 

  11. Chew LP (1993) Guaranteed-quality mesh generation for curved surfaces. In: SOCG, pp 274–280

  12. Chrisochoides N, Chernikov A, Fedorov A, Kot A, Linardakis L, Foteinos P (2009) Towards exascale parallel Delaunay mesh generation. In: International Meshing Roundtable, pp 319–336

  13. Crossno P, Angel E (1997) Isosurface extraction using particle systems. In: IEEE Visualization, pp 495–498

  14. Danielsson PE (1980) Euclidean distance mapping. Comput Graph Image Process 14:227–248

    Article  Google Scholar 

  15. Deriche R (1990) Fast algorithms for low-level vision. IEEE Trans Pattern Anal Mach Intell 12(1):78–87

    Article  Google Scholar 

  16. Dey TK (2007) Curve and surface reconstruction: algorithms with mathematical analysis. Cambridge University Press, New York

    MATH  Google Scholar 

  17. Dey TK, Levine JA (2009) Delaunay meshing of piecewise smooth complexes without expensive predicates. Algorithms 2(4):1327–1349

    Article  MathSciNet  Google Scholar 

  18. Dey TK, Levine JA, Slatton A (2010) Localized Delaunay refinement for sampling and meshing. Comput. Graph. Forum (Eurographics SGP) 29(5):1723–1732

    Article  Google Scholar 

  19. Dillard SE, Bingert J, Thoma D, Hamann B (2007) Construction of simplified boundary surfaces from serial-sectioned metal micrographs. IEEE Trans Vis Comput Graph 13(6):1528–1535

    Article  Google Scholar 

  20. Edelsbrunner H (2001) Geometry and topology for mesh generation. Cambridge University Press, England

    Book  MATH  Google Scholar 

  21. Gerig G, Kuoni W, Kikinis R, Kübler O (1989) Medical imaging and computer vision: an integrated approach for diagnosis and planning. In: Mustererkennung 1989, 11. DAGM-Symposium, Hamburg, 2–4. Oktober 1989, Proceedings, pp 425–432

  22. Hege HC, Seebaß M, Stalling D, Zöckler M (1997) A generalized marching cubes algorithm based on non-binary classifications. Technical Report SC-97-05, Zuse-Institute Berline (ZIB)

  23. Hudson B, Miller GL, Phillips T (2007) Sparse parallel Delaunay mesh refinement. In: ACM SPAA. ACM, pp 339–347

  24. Ju T, Losasso F, Schaefer S, Warren JD (2002) Dual contouring of Hermite data. ACM Trans Graph 21(3):339–346

    Article  Google Scholar 

  25. Kapur T (1999) Model based three dimensional medical image segmentation. Ph.D. thesis, Artificial Intelligence Laboratory, Massachusetts Institute of Technology

  26. Karkanis T, Stewart AJ (2001) Curvature-dependent triangulation of implicit surfaces. IEEE Comput Graph Appl 21(2):60–69

    Article  Google Scholar 

  27. Kim DH, Döring U, Brüderlin B (2000) Polygonization of non-manifolds with the aid of interval operators. pp 145–151

  28. Lorensen WE, Cline HE (1987) Marching cubes: a high resolution 3D surface construction algorithm. In: Proceedings of ACM SIGGRAPH. ACM, pp 163–169

  29. Mazziotta J, Toga A, Evans A, Fox P, Lancaster J, Zilles K, Woods R, Paus T, Simpson G, Pike B, Holmes C, Collins L, Thompson P, MacDonald D, Iacoboni M, Schormann T, Amunts K, Palomero-Gallagher N, Geyer S, Parsons L, Narr K, Kabani N, Goualher GL, Boomsma D, Cannon T, Kawashima R, Mazoyer B (2001) A probabilistic atlas and reference system for the human brain: International consortium for brain mapping (icbm). Philos Trans R Soc Lond B Biol Sci 356(1412):1293–1322

    Article  Google Scholar 

  30. Meyer MD, Whitaker RT, Kirby RM, Ledergerber C, Pfister H (2008) Particle-based sampling and meshing of surfaces in multimaterial volumes. IEEE Trans Vis Comput Graph 14(6):1539–1546

    Article  Google Scholar 

  31. Müller H (1994) Boundary extraction for rasterized motion planning. In: Modelling and planning for sensor based intelligent robot systems. World Scientific, Singapore, pp 41–50

  32. Nielson GM, Franke R (1997) Computing the separating surface for segmented data. In: IEEE Visualization, pp 229–233

  33. Noh W, Woodward P (1976) SLIC (simple line interface calculation). Lecture Notes in Physics 59:330–340

    Article  Google Scholar 

  34. Pasko AA, Adzhiev V, Sourin A, Savchenko VV (1995) Function representation in geometric modeling: concepts, implementation and applications. Vis Comput 11(8):429–446

    Article  Google Scholar 

  35. Pilliod JE, Puckett EG (2004) Second-order accurate volume-of-fluid algorithms for tracking material interfaces. J Comput Phys 199(2):465–502

    Article  MATH  MathSciNet  Google Scholar 

  36. Pons JP, Ségonne F, Boissonnat JD, Rineau L, Yvinec M, Keriven R (2007) High-quality consistent meshing of multi-label datasets. In: IPMI. Springer, Berlin, vol 4584, pp 198–210

  37. Reitinger B, Bornik A, Beichel R (2005) Constructing smooth non-manifold meshes of multi-labeled volumetric datasets. In: WSCG (Full Papers), pp 227–234

  38. Rider WJ, Kothe DB (1998) Reconstructing volume tracking. J Comput Phys 141(2):112–152

    Article  MATH  MathSciNet  Google Scholar 

  39. Schofield SP, Garimella RV, Francois MM, Loubère R (2009) A second-order accurate material-order-independent interface reconstruction technique for multi-material flow simulations. J Comput Phys 228(3):731–745

    Article  MATH  MathSciNet  Google Scholar 

  40. Schreiner JM, Scheidegger CE, Silva CT (2006) High-quality extraction of isosurfaces from regular and irregular grids. IEEE Trans Vis Comput Graph 12(5):1205–1212

    Article  Google Scholar 

  41. Serra J (1983) Image Analysis and Mathematical Morphology. Academic Press, Inc., Orlando

    Google Scholar 

  42. Smith S, Jenkinson M, Woolrich M, Beckmann C, Behrens T, Johansen-Berg H, Bannister P, Luca MD, Drobnjak I, Flitney D, Niazy R, Saunders J, Vickers J, Zhang Y, Stefano ND, Brady J, Matthews P (2004) Advances in functional and structural MR image analysis and implementation as FSL. NeuroImage 23(S1):208–219

  43. Tournois J, Wormser C, Alliez P, Desbrun M (2009) Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation. ACM Trans Graph 28(3)

  44. Wells III WM, Grimson WEL, Kikinis R, Jolesz FA (1996) Adaptive segmentation of MRI data. IEEE Trans Med Imaging 15(4):429–442

    Article  Google Scholar 

  45. Whitaker RT, Pizer SM (1993) A multi-scale approach to nonuniform diffusion. CVGIP: Image Underst 57(1):99–110

    Article  Google Scholar 

  46. Wu Z, Sullivan JM (2003) Multiple material marching cubes algorithm. Int J Numer Methods Eng 58(2):189–207

    Article  MATH  Google Scholar 

  47. Wyvill G, McPheeters C, Wyvill B (1986) Data structure for soft objects. Vis Comput 2(4):227–234

    Article  Google Scholar 

  48. Yamazaki S, Kase K, Ikeuchi K (2002) Non-manifold implicit surfaces based on discontinuous implicitization and polygonization. In: Geometric modeling and processing. IEEE Computer Society, pp 138–148

  49. Youngs D (1982) Time-dependent multi-material flow with large fluid distortion. In: Numerical methods for fluid dynamics. Academic Press, San Diego, pp 273–285

  50. Zhang Y, Hughes T, Bajaj CL (2007) Automatic 3D mesh generation for a domain with multiple materials. In: International meshing roundtable, pp 367–386

Download references

Acknowledgments

Datasets were obtained with the aid of Thomas Kerwin, Miriah Meyer, and Ross Whitaker. The temporal bone and dog skull are provided by Don Stredney at the Ohio Supercomputer Center. The tomato and orange were produced at Lawrence Berkeley Laboratory by Bill Johnston and Wing Nip of the Information and Computing Sciences Division. The torso is courtesy of John Triedman and Matthew Jolley at Boston Children’s Hospital.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, The Ohio State University, 2015 Neil Avenue, 395 Dreese Laboratories, Columbus, OH, 43210, USA

    Tamal K. Dey

  2. Department of Radiology, Harvard Medical School, 25 Shattuck Street, Boston, MA, 02115, USA

    Firdaus Janoos

  3. Scientific Computing and Imaging Institute, 72 S Central Campus Drive, Room 3750, Salt Lake City, UT, 84112, USA

    Joshua A. Levine

Authors
  1. Tamal K. Dey
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Firdaus Janoos
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Joshua A. Levine
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Joshua A. Levine.

Additional information

This work was supported by NSF grants CCF-0430735 and CCF-0635008.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dey, T.K., Janoos, F. & Levine, J.A. Meshing interfaces of multi-label data with Delaunay refinement. Engineering with Computers 28, 71–82 (2012). https://doi.org/10.1007/s00366-011-0217-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00366-011-0217-y

Keywords