carrier image

Octree/Quadtree Methods

 Geometry is decomposed based on an octree (3D) or quadtree (2D) algorithm. Octree/Quadtree is refined based on various sizing criteria and elements are placed at the "leaves" of the resulting structure.

MESHING
RESEARCH
CORNER

Baehmann, Peggy L, Scott L. Wittchen, Mark S. Shephard, Kurt R. Grice and Mark A. Yerry

    "Robust, Geometrically Based, Automatic Two-Dimensional Mesh Generation", International Journal for Numerical Methods in Engineering, Wiley, Vol 24, pp.1043-1078, 1987
    keywords:
    • quadrilateral
      		•
    • quadtree
    • triangle
      		•
    Abstract

Beall, Mark W.
    "SCOREC Mesh Database Users Guide, Version 2.2 - Draft", SCOREC Report #26-1993, January 1994
    keywords:
    • data structure
      		•
    • octree
    Abstract

Buratynski, Edward K.
    "A Three-Dimensional Unstructured Mesh Generator for Arbitrary Internal Boundaries", Numerical Grid Generation in Computational Fluid Mechanics `88, Pineridge Press, pp.621-631, 1988
    keywords:
    • tetrahedra
      		•
    • modified octree method
    • octree
      		•
    Abstract

Cheng, J.H., P.M. Finnigan, A.F. Hathaway, A. Kela, W.J. Schroeder
    "Quadtree/Octree Meshing with Adaptive Analysis", Numerical Grid Generation in Computational Fluid Mechanics `88, Pineridge Press, pp.633-642, 1988
    keywords:
    • octree
      		•
    • quadtree
    • adaptivity
      		•
    • Delaunay
    • triangle
      		•
    • tetrahedra
    Abstract

Dey, Saikat, Mark S. Shephard and Marcel K. Georges
    "Elimination of the Adverse Effects of Small Model Features by the Local Modification of Automatically Generated Meshes", Engineering with Computers, 1995
    keywords:
    • geometry management
      		•
    • small features
    • dirty geometry
      		•
    • octree
    Abstract

Field, David A.
    "The legacy of automatic mesh generation from solid modeling", Computer Aided Geometric Design, Elsevier, Vol 12, pp.651-673, 1995
    keywords:
    • advancing front
      		•
    • classification
    • Delaunay
      		•
    • hexahedra
    • octree
      		•
    • overview
    • parametric surface
      		•
    • quality
    • solid model
      		•
    • tetrahedra
    Abstract

Fischer, A. and P. Z. Bar-Yoseph
    "Adaptive mesh generation based on multi-resolution quad tree representation", International Journal For Numerical Methods In Engineering, John Wiley, Vol 48, pp.1571-1582, 2000
    keywords:
    • multiresolution
      		•
    • quadtree
    • adaptivity
      		•
    Abstract

Frey, Pascal and Paul Louis George
    "Maillages. Applications aux elements finis", Hermes Science Publ., Paris, pp.842, 23 chapters, 1999
    keywords:
    • overview
      		•
    • classification
    • survey
      		•
    • multiblock
    • algebraic
      		•
    • quadtree
    • octree
      		•
    • advancing front
    • Delaunay
      		•
    • medial axis
    • surface meshing
      		•
    • curve meshing
    • implicit surfaces
      		•
    • optimization
    • modifications
      		•
    • adaptivity
    • P-method
      		•
    • parallel
    Abstract

Frey, Pascal J. and Loic Marechal
    "Fast Adaptive Quadtree Mesh Generation", Proceedings, 7th International Meshing Roundtable, Sandia National Lab, pp.211-224, October 1998
    keywords:
    • triangle
      		•
    • quadtree
    • spatial decomposition
      		•
    • adaptivity
    Abstract
    Download Full Paper (Postscript Format)

Frey, Pascal, Benoit Sarter and Michel Gautherie
    "Fully Automatic Mesh Generation For 3-D Domains Based Upon Voxel Sets", International Journal For Numerical Methods in Engineering, John Wiley, Num 37, pp.2735-2753, 1994
    keywords:
    • divide-and-conquer
      		•
    • finite elements
    • iso-surface
      		•
    • octree
    • spatial decomposition
      		•
    • tetrahedron
    • three-dimensional
      		•
    • voxels
    Abstract

Garimella, Rao and Mark S. Shephard
    "Tetrahedral Mesh Generation With Mutliple Elements Through the Thickness", Proceedings, 4th International Meshing Roundtable, Sandia National Laboratories, pp.321-333, October 1995
    keywords:
    • octree
      		•
    • tetrahedron
    Abstract
    Download Full Paper (Postscript Format)

George, P.L.
    "Automatic Mesh Generation: Application to Finite Element Methods", Wiley, pp.333, 1991
    keywords:
    • advancing front
      		•
    • Delaunay
    • mapped
      		•
    • mulit-block
    • octree
      		•
    • overview
    • surface meshing
      		•
    • Voronoi
    Abstract

Greaves, D. M.; Borthwick, A. G. L.
    "Hierarchical tree-based finite element mesh generation", International Journal for Numerical Methods in Engineering, John Wiley & Sons, Ltd., Vol 45, Num 4, pp.447-471, June 1999
    keywords:
    • finite elements
      		•
    • octree
    • quadtree
      		•
    Abstract

Gursoy, H. N.
    "Tetrahedral Finite Element Mesh Generation from NURBS Solid Models", Engineering with Computers, Springer-Verlag, Vol 12, pp.211-223, December 1996
    keywords:
    • computational geometry
      		•
    • Delaunay
    • NURBS
      		•
    • octree
    Abstract

Guskov, Igor
    "Non-Replicating Indexing for Out-Of-Core Processing of Semi-Regular Triangular Surface Meshes", Proceedings, 13th International Meshing Roundtable, Williamsburg, VA, Sandia National Laboratories, SAND #2004-3765C, pp.39-46, September 19-22 2004
    keywords:
    • data structures
      		•
    • external data structures
    • semi-regular surface meshes
      		•
    • subdivision
    • surface mesh
      		•
    • quadtree
    Abstract
    Download Full Paper (Postscript Format)

Hitschfeld, Nancy, G. Navarro and R. Farias
    "Tessellations of Cuboids with Steiner Points", Proceedings, 9th International Meshing Roundtable, Sandia National Laboratories, pp.275-282, October 2000
    keywords:
    • control volume
      		•
    • cuboid tessellation
    • modified octrees
      		•
    • octree
    • tetrahedra
      		•
    Abstract
    Download Full Paper (Postscript Format)

Kraft, Peter
    "Automatic Remeshing With Hexahedral Elements: Problems, Solutions and Applications", Proceedings, 8th International Meshing Roundtable, South Lake Tahoe, CA, U.S.A., pp.357-367, October 1999
    keywords:
    • hexahedra
      		•
    • automatic remeshing
    • remeshing
      		•
    • octree
    • metal forming
      		•
    Abstract
    Download Full Paper (Postscript Format)

Lewis, Roland W., Yao Zheng, Asif S. Usmani
    "Aspects of adaptive mesh generation based on domain decomposition and Delaunay triangulation", Finite Elements in Analysis and Design, Elsevier, Vol 20, pp.47-70, 1995
    keywords:
    • adaptivity
      		•
    • Delaunay
    • density
      		•
    • domain decomposition
    • point creation
      		•
    • quadrilateral
    • quadtree
      		•
    • triangle
    Abstract

Lohner, Rainald and Juan R. Cebral
    "Parallel Advancing Front Grid Generation", Proceedings, 8th International Meshing Roundtable, South Lake Tahoe, CA, U.S.A., pp.67-74, October 1999
    keywords:
    • parallel
      		•
    • CFD
    • octree
      		•
    • advancing front
    Abstract
    Download Full Paper (Postscript Format)

Marechal, Loic
    "A New Approach to Octree-Based Hexahedral Meshing", Proceedings, 10th International Meshing Roundtable, Sandia National Laboratories, pp.209-221, October 7-10 2001
    keywords:
    • hexahedra
      		•
    • octree
    • conforming patterns
      		•
    • mesh adaptation
    • adaptivity
      		•
    • grid-based
    • inside-out
      		•
    Abstract

Montenegro, R., J.M. Cascon, J.M. Escobar, E. Rodriguez and G. Montero
    "Implementation in ALBERTA of an Automatic Tetrahedral Mesh Generator", Proceedings, 15th International Meshing Roundtable, Springer-Verlag, pp.325-338, September 17-20 2006
    keywords:
    • tetrahedra
      		•
    • Alberta
    • octree
      		•
    Abstract
    Download Full Paper (Postscript Format)

Neto, Joaquim B. Cavalcante, Paul A. Wawrzynek, Marcelo T. M. Carvalho, Luiz F. Martha, Anthony R. Ingraffea
    "An Algorithm for Three-Dimensional Mesh Generation for Arbitrary Regions with Cracks", 2nd Symposium on Trends in Unstructured Mesh Generation, University of Colorado, Boulder, August 1999
    keywords:
    • tetrahedra
      		•
    • crack propogation
    • octree
      		•
    • advancing front
    Abstract

Neugebauer, Friedhelm and Ralf Diekmann
    "Improved Mesh Generation: Not Simple but Good", 5th International Meshing Roundtable, Sandia National Laboratories, pp.257-272, October 1996
    keywords:
    • metric
      		•
    • provable angle bounds
    • quadtree
      		•
    • quality
    • rhomboidal quadtree
      		•
    • surface meshing
    • triangle
      		•
    Abstract
    Download Full Paper (Postscript Format)

Owen, Steven J.
    "A Survey of Unstructured Mesh Generation Technology", Proceedings, 7th International Meshing Roundtable, Sandia National Lab, pp.239-267, October 1998
    keywords:
    • overview
      		•
    • classification
    • software
      		•
    • triangle
    • quadrilateral
      		•
    • tetrahedra
    • hexahedra
      		•
    • surface meshing
    • refinement
      		•
    • clean-up
    • smoothing
      		•
    • Delaunay
    • advancing front
      		•
    • octree
    • plastering
      		•
    • paving
    • whisker weaving
      		•
    • grid-based
    • indirect
      		•
    Abstract
    Download Full Paper (Postscript Format)

Parthasarathy, V.N. and Srinivas Kodiyalam
    "A constrained optimization approach to finite element mesh smoothing", Finite Elements in Analysis and Design, Elsevier, Vol 9, pp.309-320, 1991
    keywords:
    • smoothing
      		•
    • optimization-based smoothing
    • octree
      		•
    Abstract

Perucchio, Renato, Makul Saxena and Ajay Kela
    "Automatic Mesh Generation From Solid Models Based On Recursive Spatial Decompositions", International Journal For Numerical Methods In Engineering, John Wiley, Num 28, pp.2469-2501, 1989
    keywords:
    • finite elements
      		•
    • octree
    • solid models
      		•
    • tetrahedron

Potyondy, David O., Paul A. Wawrzynek and Anthony R. Ingraffea
    "An Algorithm to Generate Qudrilateral or Triangular Element Surface Meshes in Arbitrary Domains with Aplications to Crack Propogation", International Journal for Numerical Methods in Engineering, John Wiley & Sons, Ltd., Vol 38, pp.2677-2701, 1995
    keywords:
    • crack propagation
      		•
    • quadrilateral
    • quadtree
      		•
    • triangle
    Abstract

Rassineux, A.
    "Generation and Optimization of Tetrahedral Meshes by Advancing Front Technique", International Journal for Numerical Methods in Engineering, Wiley, Vol 41, pp.651-674, 1998
    keywords:
    • advancing front
      		•
    • octree
    • optimization
      		•
    • quality
    • tetrahedra
      		•
    Abstract

Schneiders, R., R. Schindler and F. Weiler
    "Octree-based Generation of Hexahedral Element Meshes", 5th International Meshing Roundtable, Sandia National Laboratories, pp.205-216, October 1996
    keywords:
    • grid based
      		•
    • hexahedron
    • octree
      		•
    Abstract
    Download Full Paper (Postscript Format)

Schneiders, Robert
    "An Algorithm for the Generation of Hexahedral Element Meshes based on an Octree Technique", Proceedings, 6th International Meshing Roundtable, Sandia National Laboratories, pp.183-194, October 1997
    keywords:
    • grid-based
      		•
    • hexahedron
    • octree
      		•
    Abstract
    Download Full Paper (Postscript Format)

Schroeder, W.J. and M.S. Shephard
    "A Combined Octree/Delaunay Method For Fully Automatic 3-D Mesh Generation", International Journal For Numerical Methods in Engineering, John Wiley, Num 29, pp.37-55, 1990
    keywords:
    • Delaunay
      		•
    • finite elements
    • octree
      		•
    • triangulation

Schroeder, W.J., M.S. Shephard
    "An O(N) Algorithm to Automatically Generate Geometric Triangulations Satisfying the Delaunay Circumsphere Criteria", Engineering With Computers, Springer-Verlag, Num 5, pp.177-193, 1989
    keywords:
    • Delaunay triangulation
      		•
    • octree
    • three dimensional
      		•

Schroeder, William J. and Mark S. Shephard
    "On Rigorous Conditions for Automatically Generating Finite Element Meshes", Product Modeling for Computer-Aided Design and Manufacturing, Elsevier, pp.267-281, 1991
    keywords:
    • quality
      		•
    • octree
    • criteria
      		•
    • data structures
    • mesh criteria
      		•
    Abstract

Shephard Mark S, Saikat Dey and Marcel K. Georges
    "Automatic Meshing of Curved Three-Dimensional Domains: Curving Finite Elements and Curvature-Based Mesh Control", Proceedings of the IMA Swnmer program Modeling, Mesh Generation, and Adaptive Numerical Method for Partial Differential Equations, Springer-Verlag, July 1993
    keywords:
    • surface meshing
      		•
    • curvature
    • triangles
      		•
    • geometric evaluation
    • octree
      		•
    • nodal spacing
    Abstract

Shephard, M.S., F. Guerinoni, J.E. Flaherty, R.A. Ludwig and P.L. Baehmann
    "Finite Octree Mesh Generation for Three-Dimensional Flow Analysis", Numerical Grid Generation in Computational Fluid Mechanics `88, Pineridge Press, pp.709-718, 1988
    keywords:
    • octree
      		•
    • tetrahedra
    • finite volume
      		•
    • finite octree technique
    Abstract

Shephard, Mark S and Marcel K. Georges
    "Automatic Three-Dimensional Mesh Generation by the Finite Octree Technique", International Journal for Numerical Methods in Engineering, Wiley, Vol 32, pp.709-749, 1991
    keywords:
    • octree
      		•
    • tetrahedra
    Abstract

Shephard, Mark S. and Marcel K. Georges
    "Reliability of automatic 3D mesh generation", Computer Methods in Applied Mechanics and Engineering, North-Holland, Vol 101, pp.443-462, 1992
    keywords:
    • data structure
      		•
    • criteria
    • mesh criteria
      		•
    • reliability
    • robustness
      		•
    • octree
    • geometry evaluation
      		•
    Abstract

Shephard, Mark S. and Peter M. Finnigan
    "Toward Automatic Model Generation", State-of-the-Art Surveys on Computational Mechanics, eds. Ahmed K. Noor and J. Tinsley Oden, ASME, Vol 11, pp.335-366, 1991
    keywords:
    • data structure
      		•
    • overview
    • octree
      		•
    • tetrahedra
    • artificial intelligence
      		•
    Abstract

Tchon, Ko-Foa, Mohammed Khachan, François Guibault and Ricardo Camarero
    "Constructing anisotropic geometric metrics using octrees and skeletons", Proceedings, 12th International Meshing Roundtable, Sandia National Laboratories, pp.293-304, Sept. 2003
    keywords:
    • geometric adaptation
      		•
    • anisotropic metric
    • octree skeleton
      		•
    • boundary curvature
    • domain thickness
      		•
    • medial axis transform
    • brush fire
      		•
    • sizing function
    Abstract
    Download Full Paper (Postscript Format)

Tu, Tiankai and David R. O’Hallaron
    "Extracting Hexahedral Mesh Structures from Balanced Linear Octrees", Proceedings, 13th International Meshing Roundtable, Williamsburg, VA, Sandia National Laboratories, SAND #2004-3765C, pp.191-200, September 19-22 2004
    keywords:
    • balanced linear octree
      		•
    • hexahedra
    • database
      		•
    • two-level bucket sort
    • dangling and anchored nodes
      		•
    • octree
    • data structures
      		•
    Abstract
    Download Full Paper (Postscript Format)

Wake, Dan, Kias Lilja and Victor Moroz
    "A Hybrid Mesh Generation Method for Two and Three Dimensional Simulation of Semiconductor Processes and Devices", Proceedings, 7th International Meshing Roundtable, Sandia National Lab, pp.159-166, October 1998
    keywords:
    • hybrid
      		•
    • octree
    • level set methods
      		•
    • semiconductors
    • mixed-elements
      		•
    • pyramid
    • prism
      		•
    Abstract
    Download Full Paper (Postscript Format)

Weiler, F. R. Schindler and R. Schneiders
    "Automatic Geometry-Adaptive Generation of Quadrilateral and Hexahedral Element Meshes for FEM", 5th International Conference on Numerical Grid Generation in Computational Field Simmulations, Mississippi State University, pp.689-697, April 1996
    keywords:
    • data structures
      		•
    • grid-based mesh generation
    • hexahedron
      		•
    • octree
    • quadtree
      		•
    • refinement
    Abstract

Yerry, Mark A. and Mark S. Shephard
    "Trends in Engineering Software and Hardware: Automatic Mesh Generation for Three-Dimensional Solids", Computers and Structures, Pergammon, Vol 20, Num 1, pp.31-39, 1985
    keywords:
    • octree
      		•
    • tetrahedra
    Abstract

Yerry, Mark A. and Mark S. Shephard
    "Automatic Three-Dimensional Mesh Generation By The Modified Octree Technique", International Journal For Numerical Methods in Engineering, John Wiley, Num 20, pp.1965-1990, 1984
    keywords:
    • finite elements
      		•
    • octree
    • tetrahedron
      		•
    • three-dimensional

Contact author(s) or publisher for availability and copyright information on above referenced articles