Automatic three-dimensional mesh generation by the finite octree technique.

*(English)*Zbl 0755.65116The automatic generation of finite element meshes for general three- dimensional geometries represents a topic of active research. A number of algorithmic approaches have been proposed for performing this task. This paper presents an automatic mesh generator that combines octree decomposition techniques with octant level meshing procedures. The procedure is the result of several years of development of quadtree- and octree-based mesh generation techniques.

The finite octree mesh generator has been designed to meet the needs of fully automatic mesh generation of non-manifold objects of arbitrary geometric complexity. The basic concept of the octree representation consists of placing the object of interest in a parallelepiped, typically a cube, which totally encloses it. This parallelepiped is then subdivided into its eight octants which are then recursively subdivided a number of times based on criteria defined by the application.

The mesh generator is capable of meshing non-manifold models of arbitrary geometric complexity through the explicit tracking and enforcement of geometric compatibility and geometric similarity at each step of the meshing process. The results section demonstrates a linear growth rate with respect to the number of elements. Future researches of the authors to improve the finite octree procedures will include the ability to match to existing meshes and supporting directional refinement.

The finite octree mesh generator has been designed to meet the needs of fully automatic mesh generation of non-manifold objects of arbitrary geometric complexity. The basic concept of the octree representation consists of placing the object of interest in a parallelepiped, typically a cube, which totally encloses it. This parallelepiped is then subdivided into its eight octants which are then recursively subdivided a number of times based on criteria defined by the application.

The mesh generator is capable of meshing non-manifold models of arbitrary geometric complexity through the explicit tracking and enforcement of geometric compatibility and geometric similarity at each step of the meshing process. The results section demonstrates a linear growth rate with respect to the number of elements. Future researches of the authors to improve the finite octree procedures will include the ability to match to existing meshes and supporting directional refinement.

Reviewer: G.Dimitriu (Iaşi)

##### MSC:

65N50 | Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs |

65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |

##### Keywords:

automatic three-dimensional mesh generation; Delaunay triangulation; automatic generation of finite element meshes; three-dimensional geometries; octree decomposition techniques; octant level meshing; arbitrary geometric complexity
PDF
BibTeX
XML
Cite

\textit{M. S. Shephard} and \textit{M. K. Georges}, Int. J. Numer. Methods Eng. 32, No. 4, 709--749 (1991; Zbl 0755.65116)

Full Text:
DOI

**OpenURL**

##### References:

[1] | ’Catia/octree interface’, Technical Report, SCOREC Report # 34-1990, Scientific Computation Research Center, Rensselaer Polytechnic Institute, Troy, NY, 1990. |

[2] | ’Edge collapsing’, Technical Report, Scientific Computation Research Center, Rensselaer Polytechnic Institute, Troy, NY, 1990. |

[3] | Baehmann, Eng. Computers 5 pp 235– (1989) |

[4] | Baehmann, Int. j. numer. methods eng. 24 pp 1043– (1987) |

[5] | ’Shape design modeling using fully-automatic 3-D mesh generation’, Technical Report AIAA-90-1009, AIAA, Washington, DC, Apr. 1990. |

[6] | ’A three-dimensional unstructured mesh generator for arbitrary internal boundaries’, in et al. (eds.), Numerical Grid Generation in Computational Fluid Mechanics, Pineridge Press, Swansea, U.K., 1988. |

[7] | CAM-I, ’Applications interface specification (restructured version)’, Technical Report, CAM-I Report R-86-GM-01, Arlington, TX, Jan. 1986. |

[8] | and , ’Explicit node point smoothing within the finite octree mesh generator’, SCOREC Report # 10-1990, Scientific Computation Research Center, Rensselaer Polytechnic Institute, Troy, NY 12180-3590, 1990. |

[9] | ’Geometric operators for the finite octree mesh generator’, Technical Report, Scientific Computation Research Center, Rensselaer Polytechnic Institute, Troy, NY, 1990. |

[10] | and , ’Element removal meshing of three-dimensional domains’, Technical Report, Scientific Computation Research Center, Rensselaer Polytechnic Institute, Troy, NY, 1991, in progress. |

[11] | Jackins, Comp. Graphics Image Processing 14 pp 249– (1980) |

[12] | ’Exact octree approximations from geometric (csg/brep) models: Their derivation and application in finite element mesh generation’, General Electric Corporate Research and Development, Schenectady NY (1989). |

[13] | Kela, Comp. Aided Des. 21 pp 355– (1989) |

[14] | and , ’Toward automatic finite element analysis’, Comp. Mech. Eng., 57-71, July (1986). |

[15] | Perucchio, Int. j. numer. methods eng. 28 pp 2469– (1989) |

[16] | ’Geometric triangulations: with application to fully automatic 3D mesh generation’, Ph.D. Thesis, Rensselaer Polytechnic Institute, Troy, NY, 1990. |

[17] | Schroeder, Int. j. numer. methods eng. 26 pp 2503– (1988) |

[18] | Schroeder, Eng. Computers 5 pp 177– (1989) |

[19] | Shephard, Appl. Mech. Rev. 41 pp 169– (1988) |

[20] | ’Algorithmic approach to eliminating small features from the finite octree: Dual representation of features’, Technical Report, Scientific Computation Research Center, Rensselaer Polytechnic Institute, Troy, NY, 1989. |

[21] | Shephard, Commun. Appl. numer. methods 4 pp 379– (1988) |

[22] | and , ’Toward automatic model generation’, in and (eds.), State-of-the-Art Surveys on Computational Mechanics, ASME, New York, 1989, pp. 335-366. |

[23] | Shephard, Comp. Methods Appl. Mech. Eng. 55 pp 161– (1986) |

[24] | ’Automatic generation of three-dimensional all-hexahedral and mixed-element finite element meshes’, Master’s Thesis, Rensselaer Design Research Center, Rensselaer Polytechnic Institute, Troy, NY, 1989. |

[25] | ’Topological structures for geometric modeling’, Ph.D. Thesis, Rensselaer Design Research Center, Rensselaer Polytechnic Institute, Troy, NY, May 1986. |

[26] | ’Boundary graph operators for non-manifold geometric modelling topology representation’, in et al. (eds.), Geometric Modeling for CAD Applications, North-Holland, Amsterdam, 1988. |

[27] | ’The radial-edge structure: A topological representation for non-manifold geometric boundary representations’, in et al. (eds.), Geometric Modeling for CAD Applications, North-Holland, Amsterdam, 1988, pp. 3-36. |

[28] | Woo, Comp. Struct. 18 pp 333– (1984) |

[29] | Wordenweber, Comp.-Aided Des. 16 pp 285– (1984) |

[30] | Yerry, IEEE Comp. Graphics Applic. 3 pp 36– (1983) |

[31] | Yerry, Int. j. numer. methods eng. 20 pp 1965– (1984) |

[32] | Yerry, Comp. Struct. 20 pp 31– (1985) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.