Generation of octree meshes with cut cells in multiple material domains


  • A.Yu. Chernyshenko


octree meshes
cut cells
hexahedral meshes
polyhedral meshes


An algorithm for the generation of octree meshes with cut cells generation in complex multiple material domains is proposed. The method of cell cutting is based on the cubical marching squares and multiple material marching cubes algorithms. The algorithm and mesh examples are analyzed.





Section 1. Numerical methods and applications

Author Biography

A.Yu. Chernyshenko


  1. Livnat Y., Shen H., Johnson C.R. A near optimal isosurface extraction algorithm using the span space // IEEE Trans. Vis. Comp. Graphics. 1996. 2. 73-84.
  2. Ho C.-C., Wu F.-C., Chen B.-Y., Chuang Y.-Y., Ouhyoung M. Cubical marching squares: adaptive feature preserving surface extraction from volume data // Proc. EUROGRAPHICS. 2005. 24, N 3. 537-545.
  3. Wu Z., Sullivan J.M. Multiple material marching cubes algorithm // Int. J. Numer. Meth. Engng. 2003. 58. 189-207.
  4. Lorensen W.E., Cline H.E. Marching cubes: a high resolution 3d surface construction algorithm // ACM SIGGRAPH. 1987. 21. 163-169.
  5. Wu Z. Accurate and efficient three-dimensional mesh generation for biomedical engineering applications // Ph.D. Dissertation. Worcester Polytechnic Institute, 2001.
  6. Kobbelt L.P., Botsch M., Schwanecke U., Seidel H.-P. Feature sensitive surface extraction from volume data // Proc. ACM SIGGRAPH. New York: ACM Press, 2001. 57-66.
  7. Bretonnet L., Li Y., Hirsch Ch. 3D Navier-Stokes cutcell solver for octree meshes. Academy Colloquium on Immersed Boundary Methods. Amsterdam, 2009.
  8. Sutherland I.E., Hogdman G.W. Reentrant polygon clipping // Comm. of the ACM on Graphics and Image Processing. 1974. 17, N 1. 32-42.
  9. Hu S.R., Hen C.Z., Ankanhalli K.M. Adaptive marching cubes // The Visual Computer. 1995. 11, N 4. 202-217.
  10. Hekhar S.R., Fayyad E., Yagel R., Cornhill J.F. Octree-based decimation of marching cubes surfaces // Proc. of IEEE Visualization. San Francisco, 1996. 335-342.
  11. Lopes A., Brodlie K. Improving the robustness and accuracy of the marching cubes algorithm for isosurfacing // IEEE Transactions on Visualization &; Computer Graphics. 2003. 9, N 1. 16-29.
  12. Wilhelms J., Gelder A.V. Octrees for faster isosurface generation // ACM Transactions on Graphics. 1992. 11, N 3. 201-227.
  13. Schroeder W.J., Zarge J.A., Lorensen W.E. Decimation of triangle meshes // Comput. Graph. 1992. 26. 65-70.
  14. Golodetz S. Seeing things differently // Overload. 2007. 87. 4-9.
  15. Shephard M.S., Georges M.K. Three-dimensional mesh generation by finite octree technique // Int. J. for Numerical Methods in Engineering. 1991. 32. 709-749.
  16. Ju T., Losasso F., Schaefer S., Warren J. Dual contouring of Hermite data // Proc. of SIGGRAPH. 2002. 21, N 3. 339-346.
  17. Zhang Y., Hughes T.J., Bajaj C.L. An automatic 3D mesh generation method for domains with multiple materials // Comput. Methods Appl. Mech. Eng. 2010. 199. 405-415.
  18. d’Otreppe V., Boman R., Ponthot J.-P. Generating smooth surface meshes from multi-region medical images // Int. J. Numer. Meth. Biomed. Engng. 2011. 28, N 6. 642-660.