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 mpi mpi module~env_module->mpi module~aotus_module aotus_module module~env_module->module~aotus_module module~flu_binding flu_binding module~env_module->module~flu_binding iso_fortran_env iso_fortran_env module~env_module->iso_fortran_env

Used by

  • module~~tem_topology_module~~UsedByGraph module~tem_topology_module tem_topology_module module~tem_subtree_module tem_subTree_module module~tem_subtree_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_adaptation_module tem_adaptation_module module~tem_adaptation_module->module~tem_topology_module module~tem_vrtx_module tem_vrtx_module module~tem_vrtx_module->module~tem_topology_module module~tem_surfacedata_module tem_surfaceData_module module~tem_surfacedata_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_shape_module tem_shape_module module~tem_shape_module->module~tem_topology_module module~tem_construction_module tem_construction_module module~tem_construction_module->module~tem_topology_module module~tem_pointdata_module tem_pointData_module module~tem_pointdata_module->module~tem_topology_module module~tem_geometry_module tem_geometry_module module~tem_geometry_module->module~tem_topology_module program~tem_construction_test tem_construction_test program~tem_construction_test->module~tem_topology_module module~treelmesh_module treelmesh_module module~treelmesh_module->module~tem_topology_module module~tem_canonicalnd_module tem_canonicalND_module module~tem_canonicalnd_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_path_array_module tem_path_array_module module~tem_path_array_module->module~tem_topology_module module~tem_face_module tem_face_module module~tem_face_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

Contents


Variables

TypeVisibilityAttributesNameInitial
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

    TypeIntentOptionalAttributesName
    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

    TypeIntentOptionalAttributesName
    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

TypeVisibilityAttributesNameInitial
integer, private :: Level

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

integer(kind=long_k), private :: 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

TypeIntentOptionalAttributesName
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

TypeIntentOptionalAttributesName
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

TypeIntentOptionalAttributesName
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

TypeIntentOptionalAttributesName
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

TypeIntentOptionalAttributesName
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

TypeIntentOptionalAttributesName
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

TypeIntentOptionalAttributesName
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

TypeIntentOptionalAttributesName
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

TypeIntentOptionalAttributesName
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

TypeIntentOptionalAttributesName
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

TypeIntentOptionalAttributesName
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

TypeIntentOptionalAttributesName
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

TypeIntentOptionalAttributesName
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