Tree Structures for Adaptive Control Space in 3D Meshing

Tomasz Jurczyk, Barbara Głut


The article presents a comparison of several octree- and kd-tree-based structures
used for the construction of control space in the process of anisotropic
mesh generation and adaptation. The adaptive control space utilized by the
authors supervises the construction of meshes by providing the required metric
information regarding the desired shape and size of elements of the mesh at
each point of the modeled domain. Comparative tests of these auxiliary structures
were carried out based on different versions of the tree structures with
respect to computational and memory complexity as well as the quality of the
generated mesh. Analysis of the results shows that kd-trees (not present in
the meshing literature in this role) offer good performance and may become
a reasonable alternative to octree structures.


control space, kd-tree, octree, anisotropic metric, mesh generation and adaptation

Full Text:



Alauzet F.: Size Gradation Control of Anisotropic Meshes. Finite Elem. Anal. Des., vol. 46(1–2), pp. 181–202, 2010.

Alauzet F., Loseille A., Dervieux A., Frey P.: Multi-Dimensional Continuous Metric for Mesh Adaptation, pp. 191–214. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.

Aubry R., Karamete K., Mestreau E., Dey S., Löhner R.: Linear Sources for Mesh Generation. vol. 35(2), pp. A886–A907, 2013, ISSN 1064-8275 (print), 1095-7197 (electronic).

de Berg M., Cheong O., van Kreveld M., Overmars M.: Computational Geometry: Algorithms and Applications. Springer-Verlag, 2008.

Borouchaki H., George P.L., Hecht F., Laug P., Saltel E.: Delaunay mesh generation governed by metric specifications. Part I. Algorithms. Finite Elements in Analysis and Design, vol. 25, pp. 61–83, 1997.

Deister F., Tremel U., Hassan O., Weatherill N.P.: Fully automatic and fast mesh size specification for unstructured mesh generation. Eng. Comput. (Lond.), vol. 20, pp. 237–248, 2004.

George P., Borouchaki H.: Delaunay Triangulation and Meshing: Application to Finite Elements. Butterworth-Heinemann, 1998.

Jurczyk T., Glut B.: Adaptive Control Space Structure for Anisotropic Mesh Generation. Proc. of ECCOMAS CFD 2006 European Conference on Computational Fluid Dynamics, Egmond aan Zee, The Netherlands, 2006.

Jurczyk T., Glut B.: The Insertion of Metric Sources for Three-dimensional Mesh Generation. Proc. 13th Int. Conf. on Civil, Structural and Environmental Engineering Computing, Chania, Crete, Greece, 2011, paper 116.

Jurczyk T., Glut B.: Preparation of the Sizing Field for Volume Mesh Generation. Proc. 13th Int. Conf. on Civil, Structural and Environmental Engineering Computing, Chania, Crete, Greece, 2011, paper 115.

Labbé P., Dompierre J., Vallet M.G., Guibault F., Trépanier J.Y.: A universal measure of the conformity of a mesh with respect to an anisotropic metric field. Int. J. Numer. Meth. Engng, vol. 61, pp. 2675–2695, 2004.

Lo D.S.: Finite Element Mesh Generation. CRC Press, 2015.

Miranda A.C.O., Martha L.F.: Mesh generation on high-curvature surfaces based on a background quadtree structure. Proceedings, 11th International Meshing Roundtable, pp. 333–342, 2002.

Owen S.J., Saigal S.: Surface mesh sizing control. International Journal for Numerical Methods in Engineering, vol. 47(1–3), pp. 497–511, 2000.

Persson P.O., Staten M.L., Xiao Z., Chen J., Zheng Y., Zeng L., Zheng J.: 23rd International Meshing Roundtable (IMR23) Automatic Unstructured Elementsizing Specification Algorithm for Surface Mesh Generation. Procedia Engineering, vol. 82, pp. 240–252, 2014.

Pirzadeh S.Z.: Structured Background Grids for Generation of Unstructured Grids by Advancing-Front Method. AIAA Journal, vol. 31(2), pp. 257–265, 1993.

Quadros W.R., Vyas V., Brewer M., Owen S.J., Shimada K.: A computational framework for automating generation of sizing function in assembly meshing via disconnected skeletons. Engineering with Computers, vol. 26(3), pp. 231–247, 2010.

Zhu J., Blacker T., Smith R.: Background Overlay Grid Size Functions. Proc. 11th Int. Meshing Roundtable, pp. 65–74, Sandia National Laboratories, Ithaca, NY, 2002.



  • There are currently no refbacks.