tem_topology_module Module

This module provides informations and operations on the topology of the complete linearized octree. It is completely independent of the actual sparse octree and therefore this module is independent of the Treelmesh_module.

Node identification in the octree

Due to the breadth first numbering of the octree it is straight forward to move in vertical direction through the tree.

The parent $i_p$ of a node with a certain treeID $i_n$ is given by: Where the bracket $\left\lfloor\cdot\right\rfloor$ denotes the integer floor rounding to the next smaller integer number. While the children $i_{c1..8}$ of a given node $i_n$ can be obtained by: The numbering scheme begins at the root node with a treeID of 0 for this element, that covers the complete enclosed cubic domain. All further treeIDs are then given by the rules stated above. What remains to be defined is the actual spatial placement of the nodes in the tree as elements in the mesh. This is achieved by a space filling curve, that describes the numbering scheme of the 8 children for a given node.

Our choice here is the Morton ordering [6] (bibliography of treelm) , that allows an efficient computation of the index from the coordinates with the same orientation on each refinement level. For this ordering the coordinates of the children within their parent element are first noted as a three dimensional tuple, where each index might be 0 or 1. Now this tuple is interpreted as a single number of the basis 2 with three digits. The recursive in depth traversal results then in a concatenation of these numbers visited during the traversal. This concatenated number provides the sorting key for all elements on a given level according to the space filling curve.

Variables

TypeVisibility AttributesNameInitial
integer(kind=long_k), public, parameter:: firstIdAtLevel(20) =[1_long_k, 9_long_k, 73_long_k, 585_long_k, 4681_long_k, 37449_long_k, 299593_long_k, 2396745_long_k, 19173961_long_k, 153391689_long_k, 1227133513_long_k, 9817068105_long_k, 78536544841_long_k, 628292358729_long_k, 5026338869833_long_k, 40210710958665_long_k, 321685687669321_long_k, 2573485501354569_long_k, 20587884010836553_long_k, 164703072086692425_long_k]

Interfaces

• private elemental function tem_directParent(TreeID) result(res)

This function delivers the parent ID of a given TreeID

Arguments

Type IntentOptional AttributesName
integer(kind=long_k), intent(in) :: TreeID

current treeID

Return Value integer(kind=long_k)

result of function containing parent ID

• private function tem_ParentAtLevel(TreeID, level) result(parentID)

This function provides the parent ID of a given tree ID on a given level.

Arguments

Type IntentOptional AttributesName
integer(kind=long_k), intent(in) :: TreeID

treeID of which the pID is requested

integer, intent(in) :: level

the level on which the pID is requested

Return Value integer(kind=long_k)

resulting parent ID

Derived Types

type, public :: tem_path_type

Paths of elements from the root node to themselves going through the hierarchy of the tree. Is used to compare to elements

Components

TypeVisibility AttributesNameInitial
integer, public :: Level

Levels counted from 1 This level is 1 higher than the actual level.

integer(kind=long_k), public :: Node(globalMaxLevels+1)

treeIDs from current leaf to root

Functions

public elemental function tem_LevelOf(TreeID) result(res)

This function delivers the refinement level of a TreeID

Arguments

Type IntentOptional AttributesName
integer(kind=long_k), intent(in) :: TreeID

ID in the complete tree to look up

Return Value integer

Level of the given TreeID

public elemental function tem_FirstIdAtLevel(level) result(res)

This function delivers the refinement level of a TreeID

Arguments

Type IntentOptional AttributesName
integer, intent(in) :: level

level to check

Return Value integer(kind=long_k)

resulting first treeID

public elemental function tem_LastIdAtLevel(level) result(res)

Last ID in the complete tree on a given level

Arguments

Type IntentOptional AttributesName
integer, intent(in) :: level

level to check

Return Value integer(kind=long_k)

resulting last treeID

public function tem_SiblingsOfId(TreeID) result(siblings)

This function delivers all sibling treeIDs of TreeID in an array

Arguments

Type IntentOptional AttributesName
integer(kind=long_k), intent(in) :: TreeID

current treeID

treeIDs siblings

public elemental function tem_childNumber(TreeID) result(res)

This function delivers of TreeID, which child number it is from its parent

Arguments

Type IntentOptional AttributesName
integer(kind=long_k), intent(in) :: TreeID

current treeID

Return Value integer

result of function containing child number

public elemental function tem_PathOf(TreeID) result(res)

This function returns the complete path through the tree from a given treeID to the root (all parents).

Arguments

Type IntentOptional AttributesName
integer(kind=long_k), intent(in) :: TreeID

current treeID

resulting path

public function tem_directChildren(TreeID) result(childrenIDs)

This function delivers the direct children in the full tree for a given tree ID

Arguments

Type IntentOptional AttributesName
integer(kind=long_k), intent(in) :: TreeID

given treeID

Return Value integer(kind=long_k) (8)

Array for the treeIDs of the 8 direct children

public elemental function tem_TreeIDComparison(left, right) result(relation)

Compare Position of two treeIDs in the linearized tree This is relatively expansive, therefore the result should be stored, if more than one comparison of the same treeIDs has to be done. Result: -1: left is lower than right 0: left is same than right 1: left is higher than right

Arguments

Type IntentOptional AttributesName
integer(kind=long_k), intent(in) :: left

candidate treeID

integer(kind=long_k), intent(in) :: right

candidate treeID

Return Value integer

relation between the treeIDs

public elemental function tem_PathComparison(left, right) result(relation)

Compare two Paths in the linearized tree Result: -1: left is lower than right 0: left is same than right 1: left is higher than right

Arguments

Type IntentOptional AttributesName
type(tem_path_type), intent(in) :: left

candidate path

type(tem_path_type), intent(in) :: right

candidate path

Return Value integer

relation between the paths

public pure function tem_CoordOfId(TreeID, offset) result(coord)

The following function provides the spatial index triple for a given ID in the complete mesh, on its refinement level. The returned coordinates start at 0. The fourth entry is the level on which the coordinates are located in the tree. The steps are following: 1. calculate the refinement level, store to coord(4). 2. Calcualte the level offset. 3. the Morton index is obtained by subtracting the offset from treeID. 4. Apply bit interleaving rule to generate coordinates.

Arguments

Type IntentOptional AttributesName
integer(kind=long_k), intent(in) :: TreeID

input element ID

integer(kind=long_k), intent(in), optional :: offset

First Elem of current level, if known, to avoid recomputations

Return Value integer (4)

coordinate of element return value

public pure function tem_IdOfCoord(coord, offset) result(nTreeID)

This function calculates the tree ID for a given x,y and z on the given refinement level. This ID in the complete tree does not have to be in the list of leafs (treeIDlist) An example of this procedure is following: 1. Convert coordinates into binary representation: (x,y,z) = (5,9,1) = (0101,1001,0001) 2. Interleaving the bits by 3 digits for each direction: x(0101): 0 1 0 1 y(1001): 1 0 0 1 z(0001): 0 0 0 1 Combining these bits results in a binary number: 010 001 000 111, which is 1095 when seen as a 10-base number. 3. This number is the cell position in a single level sorted element list. Its treeID can be obtained by adding the correspoding level offset.

Arguments

Type IntentOptional AttributesName
integer, intent(in) :: coord(4)

3D Coordinates to translate

integer(kind=long_k), intent(in), optional :: offset

resulting treeID

private elemental function tem_directParent(TreeID) result(res)

This function delivers the parent ID of a given TreeID

Arguments

Type IntentOptional AttributesName
integer(kind=long_k), intent(in) :: TreeID

current treeID

Return Value integer(kind=long_k)

result of function containing parent ID

private function tem_ParentAtLevel(TreeID, level) result(parentID)

This function provides the parent ID of a given tree ID on a given level.

Arguments

Type IntentOptional AttributesName
integer(kind=long_k), intent(in) :: TreeID

treeID of which the pID is requested

integer, intent(in) :: level

the level on which the pID is requested

Return Value integer(kind=long_k)

resulting parent ID