Adaptive mesh refinement

ForestBWG{dim, C <: OctreeBWG, T <: Real} <: Ferrite.AbstractGrid{dim}

p4est adaptive grid implementation based on Burstedde et al. [15] and Isaac et al. [16].

Constructor

ForestBWG(grid::AbstractGrid{dim}, b) where dim

Builds an adaptive grid based on a non-adaptive one grid and a given max refinement level b, i.e. no leaf may be refined beyond level b.

b must satisfy 0 ≤ b ≤ 30 in 2D and 0 ≤ b ≤ 19 in 3D, and defaults to those upper bounds (p4est's P4EST_MAXLEVEL/P8EST_MAXLEVEL). They are hard limits, not just defaults: a larger b makes octree coordinates exceed the per-axis bit budget of the UInt64 boundary-table keys that creategrid uses to identify nodes across tree boundaries. An out-of-range b therefore throws a DomainError rather than silently producing a grid with wrongly merged nodes.

refine!(forest::ForestBWG, cellid::Integer)

Refine the single leaf addressed by the global cellid (the same flat, tree-major / Morton-within-tree numbering used by the grid from creategrid). The owning tree is found from the per-tree leaf counts; the leaf is then refined via the refine_octant!(octree, octant) method. To refine several cells, use the vector method below — it is linear, whereas looping this one is O(n^2).

refine!(forest::ForestBWG, cellids::AbstractVector{<:Integer})

Refine all leaves addressed by the global cellids — the production refinement entry point, e.g. for the cells flagged by an error estimator in an adaptive FE loop. cellids are global cell ids in the grid's flat numbering (tree-major, Morton-within-tree); duplicates are ignored and ids at the maximum level tree.b are skipped.

Runs in O(n + k) for n leaves and k = length(cellids): the sorted ids are mapped to per-tree local indices in one merge pass and each tree's leaf list is rebuilt once (children spliced in z-order in place of their parent, preserving Morton order). This avoids the O(n^2) of refining cells one at a time, where every in-place insert! memmoves the leaf-array tail. The caller's cellids vector is not modified (a sorted copy is taken when needed).

Combine with balanceforest! to restore 2:1 balance and coarsen! for derefinement; both preserve the Morton-sorted leaf invariant this method relies on.

refine_all!(forest::ForestBWG, l)

Uniformly refine every leaf currently at level l - 1 across all trees of forest, i.e. take a forest refined to level l - 1 to level l. A convenience wrapper for a uniform refinement; adaptive refinement of marked cells goes through the refine!(forest, cellids) vector method.

Runs in O(n): each tree's leaf list is rebuilt in a single pass (children spliced in z-order in place of their parent, preserving Morton order) rather than via n in-place insert!s, which would be O(n^2).

coarsen!(forest::ForestBWG, cellids::AbstractVector{<:Integer}; require_all_siblings::Bool = true)

Coarsen the 2^dim-sibling families addressed by the global cellids — the batch, derefinement counterpart of refine!. cellids are global cell ids in the grid's flat numbering (tree-major, Morton-within-tree); each replaces the family it belongs to with the common parent (one level up).

require_all_siblings selects the trigger policy:

• true (default): a family is coarsened only if all 2^dim of its children are in cellids (standard p4est semantics; never collapses un-flagged cells).
• false: a single marked sibling collapses its whole family (like coarsen_octant!(octree, octant)).

Only complete families count: a family is coarsened solely when its full 2^dim same-level sibling set is physically present and contiguous in the leaves. Ids addressing an incomplete family (e.g. a sibling that was refined further) are silently skipped, mirroring how refine! skips ids already at the maximum level. Coarsening is one level per call and duplicates are ignored.

Runs in O(n + k) like the vector refine!: the sorted ids are mapped to per-tree local indices in one merge pass and each tree's leaf list is rebuilt once (families collapsed to their parent in place, preserving Morton order). The caller's cellids vector is not modified (a sorted copy is taken when needed). Combine with balanceforest! to restore 2:1 balance before creategrid.

refine_and_coarsen!(forest::ForestBWG, coarsen_ids, refine_ids; balance = true, require_all_siblings = true)

Coarsen the families addressed by coarsen_ids and refine the leaves addressed by refine_ids in a single pass, then (if balance, the default) restore 2:1 balance via balanceforest!. Both id vectors use the same global, flat cell numbering (tree-major, Morton-within-tree) as refine! and coarsen!.

Doing both at once is the point: a global cell id encodes a leaf's position in the current leaf lists, so as soon as one operation runs, every id at or after the touched leaf is stale. Calling coarsen! and refine! back-to-back with ids gathered against one numbering would therefore misfire. Instead this resolves both id sets against the original numbering and applies them in one rebuild pass per tree, so no intermediate renumbering ever exists.

require_all_siblings has the same meaning as in coarsen!. The two id sets must be disjoint, and no refine_ids entry may fall inside a family selected for coarsening; either conflict throws an ArgumentError. Refinement and coarsening are one level per call.

balanceforest!(forest::ForestBWG)

Enforce the 2:1 balance condition across the whole forest: no two leaves sharing a face, edge or corner may differ by more than one refinement level. Each tree is balanced internally (balancetree); boundary leaves (_touches_tree_boundary) are additionally balanced against their out-of-tree neighbours via _balance_leaf!. Iterated to a fixed point, then duplicate/over-refined leaves are pruned and re-sorted into Morton order.

A balance refinement can itself create new 2:1 violations (also in trees processed earlier in the same pass), which is why the outer loop reruns until a whole pass adds no cells. This ripple can cascade across the domain, but it always terminates: balancing only ever refines, the cell count is strictly increasing across repeated passes, and it is bounded above by the uniformly max-refined forest. On return the invariant holds globally — the non-conformity level after refine! + balanceforest! is always exactly one, independent of the refinement history.

Algorithm 17 of Burstedde et al. [15].

creategrid(forest::ForestBWG) -> NonConformingGrid

Materialize a ForestBWG (a forest of adaptively refined octrees) into a NonConformingGrid. The returned grid can be used like any Ferrite grid, complete with the hanging-node constraints (conformity_info) and the transferred boundary and subdomain sets (facetsets, cellsets).

This is the Lnodes construction of Isaac et al. [16] §6 on the point iterator iterate_points (Alg 5.2/5.3): node ids are assigned inside the iterator callbacks and scattered into the element-node matrix E — there is no global node map; identity is carried by E plus O(surface) per-tree boundary tables, the layout that generalizes to distributed forests (each process numbers the nodes it owns; only interface ids are reconciled). The whole construction is integer/topological — node identity is decided on integer octree coordinates, never physical positions, which are interpolated once per node (_interp_treepoint).

Pipeline:

1. Numbering + hanging detection. One iterate_points traversal per tree (mindim = 0) fires the LnodesVisitor callbacks: corners create + scatter node ids, non-conforming faces and (3D) edges create the hanging vertices and record their constraints as (element, slot) references into E.
2. Inter-tree hanging. _iterate_interface_hanging! descends each shared tree face from both sides and records the cross-tree hanging constraints (no-op for a single tree).
3. Cross-tree identity. A shared boundary node has one provisional id per incident tree; _merge_intertree_nodes! aliases them onto a single owner through the per-tree boundary tables.
4. Global numbering + cells + constraints. _global_numbering (Alg 6.1) assigns the final dense ids in one sweep over E, _build_cells materializes the cells, the constraint records are resolved against E, and reconstruct_facetsets / reconstruct_cellsets carry the named boundaries and subdomains onto the refined grid (vertex and node sets are not transferred, see the warning above).

Requires a 2:1-balanced forest (see balanceforest!) — balance is what guarantees hanging vertices are simple feature midpoints with non-hanging masters, and it is checked (an unbalanced forest leaves element vertices without node ids, which raises an error).

ConformityConstraint(field_name::Symbol)

This constraint can be passed to the constraint handler when working with non-conforming meshes to add the affine constraints required to make the associated interpolation conforming. It applies to the single field field_name; combine several ConformityConstraints to constrain several fields of a multi-field DofHandler.

The named field must be defined on every cell of the grid: subdomains (SubDofHandlers covering only part of the grid, e.g. via L2Projector(...; set = ...)) are not supported yet and throw an ArgumentError.

For a full example visit the adaptive heat equation tutorial.