A Morton-type space-filling curve for pyramid subdivision and hybrid adaptive mesh refinement

David Knapp, Johannes Albrecht Holke, Thomas Spenke, Carsten Burstedde · 2026

Read A Morton-type space-filling curve for pyramid subdivision and hybrid adaptive mesh refinement by David Knapp, Johannes Albrecht Holke, Thomas Spenke, Carsten Burstedde (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-20887.txt.

Introduction

Adaptive mesh refinement lets simulations sharpen their grids where detail matters, at little extra cost. David Knapp and four co-authors extend that machinery to mixed three-dimensional meshes in this 2026 arXiv paper. They add the pyramid as a new element type, whose job is to join tetrahedral and hexahedral elements without hanging edges.

The paper defines a Morton-type space-filling curve for the pyramid and resolves the element-level and forest-level problems its refinement raises. It also generalizes the core parallel routines for refinement, coarsening, partitioning, and ghost exchange to support the new element. Demonstrations confirm the resulting hybrid framework runs efficiently and scales well.

Catalog record

CREATORDavid Knapp, Johannes Albrecht Holke, Thomas Spenke, Carsten Burstedde
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-20887

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Morton-type space-filling curve for pyramid subdivision and hybrid adaptive mesh refinement David Knapp, Johannes Albrecht Holke, Thomas Spenke, Carsten Burstedde Abstract The forest-of-refinement-trees approach allows for dynamic adaptive mesh refinement (AMR) at negligible cost. While originally developed for quadrilateral and hexahedral elements, previous work established the theory and algorithms for unstructured meshes of simplicial and prismatic elements. To harness the full potential of tree-based AMR for three-dimensional mixed-element meshes, this paper introduces the pyramid as a new functional element type; its primary purpose is to connect tetrahedral and hexahedral elements without hanging edges. We present a well-defined space-filling curve (SFC) for the pyramid and detail how the unique challenges on the element and forest level associated with the pyramidal refinement are resolved. We propose the necessary functional design and generalize the fundamental global parallel algorithms for refinement, coarsening, partitioning, and face ghost exchange to fully support this new element. Our demonstrations confirm the efficiency and scalability of this complete, hybrid-element dynamic AMR framework. keywords Adaptive mesh refinement, parallel algorithms, forest of octrees, hybrid mesh, pyramid † † runningheads: A Morton-type SFC for pyramid subdivision and hybrid AMR / D. Knapp, J. Holke, T. Spenke, and C. Burstedde AMS 65M50, 68W10, 65Y05, 65D18 1 Introduction Numerical simulations are indispensable for analyzing complex physical systems. The fidelity of their results depends critically on the spatial resolution of the simulation domain. Adaptive meshes are widely used for efficient resolution of local features, which reduces computational cost [ 1 , 15 , 39 , 30 ] . The prevailing strategy for distributing the computational mesh onto multiple processes is graph-oriented partitioning [ 50 , 42 , 47 , 48 ] . It typically relies on third-party libraries [ 26 , 27 , 38 , 5 ] to compute near-optimal partitions that minimize inter-process communication. While these algorithms are well established for static unstructured meshes, where the partition is computed only once, their computational overhead becomes a significant factor in dynamic scenarios and for extreme process counts. A robust alternative to graph-based partitioning is dynamic, hierarchical adaptation based on a forest of refinement trees. This approach exploits the locality-preserving properties of space-filling curves (SFCs) [ 37 , 18 , 34 , 41 , 40 ] to linearize the multidimensional domain. While classically restricted to quadrilateral or hexahedral elements [ 43 ] , this method allows for rapid, logic-based repartitioning without the overhead of global graph algorithms. Consequently, it is highly effective for massively parallel, dynamic simulations, as demonstrated by several scalable implementations [ 17 , 46 , 11 , 49 ] , some of which are now integrated into general-purpose parallel-computing libraries [ 2 , 22 , 10 ] . Most of these libraries support the usage of a fixed element shape, such as pure hexahedral or pure tetrahedral meshes. Both choices come with their own strengths and weaknesses; for example, hexahedral elements are beneficial to various classes of solvers, while tetrahedra offer more flexibility to cover complex geometries. Combining both shapes can be advantageous but requires bridging elements, such as prisms or pyramids, to prevent hanging edges [ 23 , 16 ] . By themselves, these shapes do not offer further advantages, but they allow for conforming transitions wherever tetrahedral and hexahedral mesh elements meet. In this paper, we present a generalization of Morton-type space-filling curves [ 36 ] to pyramids, a crucial development that enables fully general, tree-based hybrid adaptive mesh refinement (AMR) [ 23 , 24 ] . In previous works, we have established the underlying theory, parallel algorithms, and scalable demonstrations for hypercubical and simplicial elements up to three dimensions [ 8 ] , and we have conducted initial research on suitable space-filling curves for prisms [ 31 ] and pyramids [ 32 ] . To fully support the pyramid primitive in practice, this work introduces a set of new per-element algorithms, such as computing the child, parent, and face neighbor, along with extensions to global mesh modification and interrogation algorithms like computing the bounds of a uniformly partitioned mesh. We present a reference implementation within the open-source adaptive-meshing software library t8code [ 20 ] . We propose a novel refinement strategy that partitions a pyramid into six pyramidal and four tetrahedral children. The decisive advantage of this decomposition is its commutativity with cubic refinement. Analogous to the tetrahedral Morton index [ 19 ] , this property allows us to uniquely identify any pyramid in the forest solely by its enclosing sub-cube and a local orientation integer. Unlike standard element shapes that refine self-similarly, this strategy results in heterogeneous children (pyramids and tetrahedra). While this geometric irregularity poses a significant challenge for low-level index arithmetic, our solution overcomes this barrier, providing the essential component to enable fully general, tree-based hybrid adaptive mesh refinement. 1.1 Summary Our proposed refinement strategy introduces heterogeneity in the descendants, as children of a pyramid are either tetrahedra or pyramids. Furthermore, the refinement pattern leads to a structure that is neither strictly self-similar nor uniformly balanced, with child numbers of eight (for tetrahedra) or ten (for pyramids). This geometric complexity requires sophisticated, novel approaches for the atomic element algorithms. For example, generating a sibling element, which is a straightforward operation for hypercubes and manageable for simplices, becomes non-trivial due to the mixed nature of the children. We propose functional designs for these essential algorithms and describe how the fundamental global parallel routines for refinement, coarsening, and gathering ghost elements are successfully generalized to robustly include pyramids. The design of the space-filling curve itself is achieved through a relatively benign generalization, following the successful methodology developed previously for tetrahedra. Crucially, primitives like six tetrahedra, two prisms, or the combination of two pyramids and two tetrahedra (as shown in Figure 2(c) ) may be arranged to tile a reference cube. We complement the standard cubic Morton SFC by introducing a type index that uniquely counts through the multiple, similar incarnations of a given primitive within that reference cube. The partitioning algorithm follows without additional efforts, since it relies entirely on the SFC. The adaptive refinement and coarsening, however, are complicated significantly by several novel aspects: 1. Each pyramid refines into six pyramids and four tetrahedra; each of the pyramids may have one of two orientations in relation to the reference cube. This makes the generation of an initial uniform mesh non-trivial, since it contains a mix of equal-depth pyramidal and tetrahedral elements. 2. Formally generating the parent within pyramid refinement trees is quite involved compared to the much simpler algorithms for hexahedra, tetrahedra, and prisms, since it is not obvious whether the parent of a tetrahedron is a tetrahedron or a pyramid. 3. The face neighbor of a pyramid may be taken across a triangular or a quadrilateral face, as opposed to standard element shapes in t8code like tetrahedra and hexahedra, for which the face always has the same shape. This requires additional lookup tables and branching. Section 2 briefly reviews the forest-of-octrees structure implemented in t8code . We define and encode the space-filling curve for pyramids in Section 3 . Section 4 develops the necessary per-element algorithms. In Section 5 , we describe the global parallel algorithms for mesh manipulation, including the generation of the initial hybrid

Read the complete text