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 of a node with a certain treeID is given by: Where the bracket denotes the integer floor rounding to the next smaller integer number. While the children of a given node 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.


Uses

  • module~~tem_topology_module~~UsesGraph module~tem_topology_module tem_topology_module module~env_module env_module module~tem_topology_module->module~env_module aotus_module aotus_module module~env_module->aotus_module flu_binding flu_binding module~env_module->flu_binding iso_fortran_env iso_fortran_env module~env_module->iso_fortran_env mpi mpi module~env_module->mpi

Used by

  • module~~tem_topology_module~~UsedByGraph module~tem_topology_module tem_topology_module module~tem_adaptation_module tem_adaptation_module module~tem_adaptation_module->module~tem_topology_module module~tem_bc_prop_module tem_bc_prop_module module~tem_bc_prop_module->module~tem_topology_module module~tem_canonicalnd_module tem_canonicalND_module module~tem_canonicalnd_module->module~tem_topology_module module~tem_construction_module tem_construction_module module~tem_construction_module->module~tem_topology_module module~tem_face_module tem_face_module module~tem_face_module->module~tem_topology_module module~tem_geometry_module tem_geometry_module module~tem_geometry_module->module~tem_topology_module module~tem_intersection_module tem_intersection_module module~tem_intersection_module->module~tem_topology_module module~tem_meshinfo_module tem_meshInfo_module module~tem_meshinfo_module->module~tem_topology_module module~tem_path_array_module tem_path_array_module module~tem_path_array_module->module~tem_topology_module module~tem_pointdata_module tem_pointData_module module~tem_pointdata_module->module~tem_topology_module module~tem_reduction_spatial_module tem_reduction_spatial_module module~tem_reduction_spatial_module->module~tem_topology_module module~tem_shape_module tem_shape_module module~tem_shape_module->module~tem_topology_module module~tem_spacetime_var_module tem_spacetime_var_module module~tem_spacetime_var_module->module~tem_topology_module module~tem_surfacedata_module tem_surfaceData_module module~tem_surfacedata_module->module~tem_topology_module module~tem_vrtx_module tem_vrtx_module module~tem_vrtx_module->module~tem_topology_module module~treelmesh_module treelmesh_module module~treelmesh_module->module~tem_topology_module

Variables

Type Visibility Attributes Name Initial
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

public interface tem_ParentOf

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

    This function delivers the parent ID of a given TreeID

    Arguments

    Type IntentOptional Attributes Name
    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.

    The parent ID on a given level is calculated using the equation \f[ id_{l-1}=\frac{id_{l}-1}{8} \f] in a loop.

    Arguments

    Type IntentOptional Attributes Name
    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

Read more…

Components

Type Visibility Attributes Name Initial
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

Read more…

Arguments

Type IntentOptional Attributes Name
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

Read more…

Arguments

Type IntentOptional Attributes Name
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 Attributes Name
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 Attributes Name
integer(kind=long_k), intent(in) :: TreeID

current treeID

Return Value integer(kind=long_k), (7)

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 Attributes Name
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 Attributes Name
integer(kind=long_k), intent(in) :: TreeID

current treeID

Return Value type(tem_path_type)

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 Attributes Name
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 Attributes Name
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 Attributes Name
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 Attributes Name
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.

Read more…

Arguments

Type IntentOptional Attributes Name
integer, intent(in) :: coord(4)

3D Coordinates to translate
integer(kind=long_k), intent(in), optional :: offset

Return Value integer(kind=long_k)

resulting treeID

private elemental function tem_directParent(TreeID) result(res)

This function delivers the parent ID of a given TreeID

Arguments

Type IntentOptional Attributes Name
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.

Read more…

Arguments

Type IntentOptional Attributes Name
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