Adaptive Mesh Refinement (AMR)

isancestor(o1,o2,b) -> Bool

Is o2 an ancestor of o1

From Burstedde et al. [17];

The octant coordinates are stored as integers of a fixed number b of bits, where the highest (leftmost) bit represents the first vertical level of the octree (counting the root as level zero), the second highest bit the second level of the octree, and so on.

A morton index can thus be constructed by interleaving the integer bits (2D): $m(\text{Oct}) := (y_b,x_b,y_{b-1},x_{b-1},...y_0,x_0)_2$ further we assume the following

Due to the two-complement representation of integers in practically all current hardware, where the highest digit denotes the negated appropriate power of two, bitwise operations as used, for example, in Algorithm 1 yield the correct result even for negative coordinates.

also from Burstedde et al. [17]

TODO: use LUT method from https://www.forceflow.be/2013/10/07/morton-encodingdecoding-through-bit-interleaving-implementations/

children(octant::OctantBWG{dim,N,T}, b::Integer) -> NTuple{M,OctantBWG}

Computes all childern of octant

vertices(octant::OctantBWG{dim}, b::Integer)

Computes all vertices of a given octant. Each vertex is encoded within the octree coordinates i.e. by integers.

edges(octant::OctantBWG{dim}, b::Integer)

Computes all edges of a given octant. Each edge is encoded within the octree coordinates i.e. by integers. Further, each edge consists of two three-dimensional integer coordinates.

faces(octant::OctantBWG{dim}, b::Integer)

Computes all faces of a given octant. Each face is encoded within the octree coordinates i.e. by integers. Further, each face consists of either two two-dimensional integer coordinates or four three-dimensional integer coordinates.

transform_pointBWG(forest, vertices) -> Vector{Vec{dim}}
transform_pointBWG(forest::ForestBWG{dim}, k::Integer, vertex::NTuple{dim,T}) where {dim,T} -> Vec{dim}

Transformation of a octree coordinate system point vertex (or a collection vertices) to the corresponding physical coordinate system.

corner_neighbor(octant::OctantBWG, c::Integer, b::Integer)

Computes the corner neighbor octant which is only connected by the corner c to octant

edge_neighbor(octant::OctantBWG, e::Integer, b::Integer)

Computes the edge neighbor octant which is only connected by the edge e to octant.

facet_neighbor(octant::OctantBWG{dim,N,T}, f::T, b::T=_maxlevel[2]) -> OctantBWG{dim,N,T}

Intraoctree face neighbor for a given faceindex f (in p4est, i.e. z order convention) and specified maximum refinement level b. Implements Algorithm 5 of Burstedde et al. [17].

x-------x-------x
|       |       |
|   3   |   4   |
|       |       |
x-------x-------x
|       |       |
o   1   *   2   |
|       |       |
x-------x-------x

Consider octant 1 at xyz=(0,0), a maximum refinement level of 1 and faceindex 2 (marked as *). Then, the computed face neighbor will be octant 2 with xyz=(1,0). Note that the function is not sensitive in terms of leaving the octree boundaries. For the above example, a query for face index 1 (marked as o) will return an octant outside of the octree with xyz=(-1,0).

possibleneighbors(o::OctantBWG{2},l,b;insidetree=true)

Returns a list of possible neighbors, where the first four are corner neighbors that are exclusively connected via a corner. The other four possible neighbors are face neighbors.

possibleneighbors(o::OctantBWG{3},l,b;insidetree=true)

Returns a list of possible neighbors, where the first eight are corner neighbors that are exclusively connected via a corner. After the first eight corner neighbors, the 6 possible face neighbors follow and after them, the edge neighbors.

transform_corner(forest,k,c',oct,inside::Bool)
transform_corner(forest,v::VertexIndex,oct,inside::Bool)

Algorithm 12 but with flipped logic in Burstedde et al. [17] to transform corner into different octree coordinate system Implements flipped logic in the sense of pushing the Octant oct through vertex v and stays within octree coordinate system k.

transform_edge(forest,k,e,oct,inside::Bool)
transform_edge(forest,e::Edgeindex,oct,inside::Bool)

Algorithm 10 in Burstedde et al. [17] to transform cedge into different octree coordinate system but reversed logic. See transform_edge_remote with logic from paper. In this function we stick to the coordinate system of the pivot tree k and transform an octant through edge e into this k-th octree coordinate system.

transform_facet(forest::ForestBWG, k', f', o::OctantBWG) -> OctantBWG
transform_facet(forest::ForestBWG, f'::FacetIndex, o::OctantBWG) -> OctantBWG

Interoctree coordinate transformation of an given octant o that lies outside of the pivot octree k, namely in neighbor octree k'. However, the coordinate of o is given in octree coordinates of k. Thus, this algorithm implements the transformation of the octree coordinates of o into the octree coordinates of k'. Useful in order to check whether or not a possible neighbor exists in a neighboring octree. Implements Algorithm 8 of Burstedde et al. [17].

x-------x-------x
|       |       |
|   3   |   4   |
|       |       |
x-------x-------x
|       |       |
|   1   *   2   |
|       |       |
x-------x-------x

Consider 4 octrees with a single leaf each and a maximum refinement level of 1 This function transforms octant 1 into the coordinate system of octant 2 by specifying k=1 and f=2. While from the perspective of octree coordinates k=2 octant 1 is at xyz=(-2,0), the returned and transformed octant is located at xyz=(0,0)

transform_corner_remote(forest,k,c',oct,inside::Bool)
transform_corner_remote(forest,v::VertexIndex,oct,inside::Bool)

Algorithm 12 in Burstedde et al. [17] to transform corner into different octree coordinate system. Follows exactly the version of the paper by taking oct and looking from the neighbor octree coordinate system (neighboring to k,v) at oct.

transform_edge_remote(forest,k,e,oct,inside::Bool)
transform_edge_remote(forest,e::Edgeindex,oct,inside::Bool)

Algorithm 10 in Burstedde et al. [17] to transform edge into different octree coordinate system. This function looks at the octant from the octree coordinate system of the neighbor that can be found at (k,e)

transform_facet_remote(forest::ForestBWG, k::T1, f::T1, o::OctantBWG{dim,N,T2}) -> OctantBWG{dim,N,T1,T2}
transform_facet_remote(forest::ForestBWG, f::FacetIndex, o::OctantBWG{dim,N,T2}) -> OctantBWG{dim,N,T2}

Interoctree coordinate transformation of an given octant o to the face-neighboring of octree k by virtually pushing os coordinate system through ks face f. Implements Algorithm 8 of Burstedde et al. [17].

x-------x-------x
|       |       |
|   3   |   4   |
|       |       |
x-------x-------x
|       |       |
|   1   *   2   |
|       |       |
x-------x-------x

Consider 4 octrees with a single leaf each and a maximum refinement level of 1 This function transforms octant 1 into the coordinate system of octant 2 by specifying k=2 and f=1. While in the own octree coordinate system octant 1 is at xyz=(0,0), the returned and transformed octant is located at xyz=(-2,0)