aabbtree_m Module

  1. aabbtree_m.f90
  2. aabbtree_m

Implements an axis-aligned bounding box (AABB) tree. This code is adapted from the C++ implementation by Lester Hedges. The original C++ implementation can be found here.


Uses

  • module~~aabbtree_m~~UsesGraph module~aabbtree_m aabbtree_m module~vector_m vector_m module~aabbtree_m->module~vector_m module~strings_m strings_m module~aabbtree_m->module~strings_m module~constants_m constants_m module~aabbtree_m->module~constants_m module~aabb_m aabb_m module~aabbtree_m->module~aabb_m module~vector_m->module~constants_m module~qsort_m qsort_m module~vector_m->module~qsort_m module~strings_m->module~constants_m iso_fortran_env iso_fortran_env module~constants_m->iso_fortran_env module~aabb_m->module~strings_m module~aabb_m->module~constants_m module~qsort_m->module~constants_m

Used by

  • module~~aabbtree_m~~UsedByGraph module~aabbtree_m aabbtree_m module~pairtab_m pairtab_m module~pairtab_m->module~aabbtree_m module~aabbtree_sm aabbtree_sm module~aabbtree_sm->module~aabbtree_m module~interaction_m interaction_m module~interaction_m->module~pairtab_m module~bd_solver_m bd_solver_m module~bd_solver_m->module~interaction_m module~setup_m setup_m module~setup_m->module~interaction_m module~setup_m->module~bd_solver_m program~main main program~main->module~setup_m

Contents

Variables

Interfaces

Derived Types


Variables

TypeVisibility AttributesNameInitial
integer, private, parameter:: NULL_NODE =0
type(ivector_t), private :: stack

Interfaces

interface

  • private module function node_isleaf(this) result(res)

    Is this a leaf node?

    Arguments

    Type IntentOptional AttributesName
    class(node_t), intent(in) :: this

    A node_t instance.

    Return Value logical

    true if this is a leaf node, false otherwise.

interface

  • private module function node_asstr(this, frmt) result(buf)

    Returns a string representation of a node.

    Arguments

    Type IntentOptional AttributesName
    class(node_t), intent(in) :: this

    A node_t instance.
    character(len=*), intent(in), optional :: frmt

    Format string for real numbers, e.g. '(f15.6)'. Default: (g0.6).

    Return Value character(len=:), allocatable

    Return value

interface

  • private module function get_num_atoms(this) result(na)

    Returns the number of atoms in an AABB tree.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.

    Return Value integer

    Return value

interface

  • private module function get_aabb(this, ia) result(aabb)

    Returns a copy of the AABB associated with atom with index ia.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.
    integer, intent(in) :: ia

    Atom index.

    Return Value type(aabb_t)

    AABB of atom ia.

interface

  • private module function get_height(this) result(height)

    Returns the height of an AABB tree.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.

    Return Value integer

    Return value.

interface

  • private module function get_max_balance(this) result(max_balance)

    Returns the maximum difference between the height of two children of a node.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.

    Return Value integer

    Return value.

interface

  • private module function get_srfarea_ratio(this) result(saratio)

    Returns the ratio of the sum of the node surface area to the surface area of the root node.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.

    Return Value real(kind=rp)

    Return value.

interface

  • private module function balance(this, p) result(q)

    Balances an AABB tree.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.
    integer, intent(in) :: p

    Node index

    Return Value integer

interface

  • private recursive module function calc_height(this, p) result(height)

    Calculates the height of a subtree.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.
    integer, intent(in), optional :: p

    Pointer to the root of the subtree. Default: Root of the whole tree.

    Return Value integer

    Return value

interface

  • private module function fs_acquire(this) result(p)

    Acquires a new node from the free store and returns a pointer to it.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.

    Return Value integer

    Return value

interface

  • private module subroutine node_init(this)

    Initializes a node.

    Arguments

    Type IntentOptional AttributesName
    class(node_t), intent(out) :: this

    A node_t instance.

interface

  • private module subroutine init(this, natoms, tskin)

    Initializes an AABB tree.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(out) :: this

    An aabbtree_t instance.
    integer, intent(in) :: natoms

    Estimated number of atoms to be handled by this tree.
    real(kind=rp), intent(in) :: tskin

    Thickness of the skin for fattened AABBs, as a fraction of the AABB base length.

interface

  • private recursive module subroutine print(this, p)

    Prints a subtree of an AABB tree rooted at p in order.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.
    integer, intent(in), optional :: p

    Pointer to the root of the subtree. Default is the root of the whole tree.

interface

  • private module subroutine clear(this)

    Clears an AABB tree. Associated memory is not deallocated.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.

interface

  • private module subroutine delete(this)

    Deletes an AABB tree. All associated memory is deallocated.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.

interface

  • private module subroutine insert(this, ia, pos, radius)

    Inserts an atom into an AABB tree.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.
    integer, intent(in) :: ia

    Atom index
    real(kind=rp), intent(in), dimension(3):: pos

    Atom position
    real(kind=rp), intent(in) :: radius

    Atom radius (or cutoff distance for point particles)

interface

  • private module subroutine remove(this, ia)

    Removes an atom from an AABB tree.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.
    integer, intent(in) :: ia

    Atom index

interface

  • private module subroutine remove_all(this)

    Removes all atoms from an AABB tree.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.

interface

  • private module subroutine update_fatm(this, ia, pos, radius, lstat)

    Updates an AABB tree for the case when an atom leaves its fattened AABB.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.
    integer, intent(in) :: ia

    Atom index
    real(kind=rp), intent(in), dimension(3):: pos

    Atom position
    real(kind=rp), intent(in) :: radius

    Atom radius (or cutoff distance for point particles)
    logical, intent(out) :: lstat

    true if the atom was reinserted, false otherwise.

interface

  • private module subroutine update_fatmaabb(this, ia, lbnd, ubnd, lstat)

    Updates an AABB tree for the case when an atom leaves its fattened AABB, with the bounds of the new AABB for the atom as input.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.
    integer, intent(in) :: ia

    Atom index
    real(kind=rp), intent(in), dimension(3):: lbnd

    Lower bound of atom AABB
    real(kind=rp), intent(in), dimension(3):: ubnd

    Upper bound of atom AABB
    logical, intent(out) :: lstat

    true if the atom was reinserted, false otherwise.

interface

  • private module subroutine query_watm(this, ia, nbrs)

    Query an AABB tree for a set of potential neighbors of an atom.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.
    integer, intent(in) :: ia

    Atom index
    type(ivector_t), intent(inout) :: nbrs

    List of potential neighbors.

interface

  • private module subroutine query_watmaabb(this, ia, aabb, nbrs)

    Query an AABB tree for a set of potential neighbors of an atom & its bounding AABB.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.
    integer, intent(in) :: ia

    Atom index.
    type(aabb_t), intent(in) :: aabb

    Bounding AABB for atom with index ia.
    type(ivector_t), intent(inout) :: nbrs

    List of potential neighbors.

interface

  • private module subroutine query_waabb(this, aabb, atms)

    Query an AABB tree for the set of atoms whose AABBS overlap with aabb.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.
    type(aabb_t), intent(in) :: aabb

    An aabb_t instance.
    type(ivector_t), intent(inout) :: atms

    List of potential neighbors.

interface

  • private module subroutine rebuild(this)

    Rebuilds an optimal AABB tree.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.

interface

  • private module subroutine validate(this)

    Validates an AABB tree.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.

interface

  • private module subroutine insert_leaf(this, leaf)

    Inserts a leaf node into a tree.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.
    integer, intent(in) :: leaf

    Pointer to a leaf node

interface

  • private module subroutine remove_leaf(this, leaf)

    Removes a leaf node from a tree.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.
    integer, intent(in) :: leaf

    Pointer to a leaf node

interface

  • private module subroutine fs_return(this, p)

    Returns a node to the free store.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(inout) :: this

    An aabbtree_t instance.
    integer, intent(in) :: p

    Node pointer.

interface

  • private recursive module subroutine validate_structure(this, p)

    Asserts that an AABB subtree has a valid structure.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.
    integer, intent(in) :: p

    Pointer to the root of the subtree.

interface

  • private recursive module subroutine validate_metrics(this, p)

    Asserts that an AABB subtree has a valid metric.

    Arguments

    Type IntentOptional AttributesName
    class(aabbtree_t), intent(in) :: this

    An aabbtree_t instance.
    integer, intent(in) :: p

    Pointer to the root of the subtree.

Derived Types

type, private :: node_t

Components

TypeVisibility AttributesNameInitial
integer, public :: next =NULL_NODE
integer, public :: parent =NULL_NODE
integer, public :: left =NULL_NODE
integer, public :: right =NULL_NODE
integer, public :: height =-1
integer, public :: atom =0
type(aabb_t), public :: aabb

Type-Bound Procedures

procedure, public :: init => node_init
procedure, public :: isleaf => node_isleaf
procedure, public :: asstr => node_asstr

type, public :: aabbtree_t

Components

TypeVisibility AttributesNameInitial
type(node_t), public, dimension(:), allocatable:: nodes
integer, public, dimension(:), allocatable:: atnd_tab

Atom -> node map.
integer, public :: capacity

Maximum number of nodes that the tree can currently handle. This may increase as more atoms are inserted.
integer, public :: freestore

Pointer to head to the free store.
integer, public :: size

Number of nodes in the tree.
integer, public :: root

Pointer to the tree root.
real(kind=rp), public :: tskin

Thickness of the skin for fattened AABBs, as a fraction of the AABB base length.

Type-Bound Procedures

procedure, public :: init
procedure, public :: print
procedure, public :: clear
procedure, public :: delete
procedure, public :: insert
procedure, public :: remove
procedure, public :: remove_all
procedure, public :: update_fatm
procedure, public :: update_fatmaabb
generic, public :: update => update_fatm, update_fatmaabb
procedure, public :: query_watm
procedure, public :: query_waabb
procedure, public :: query_watmaabb
generic, public :: query => query_watm, query_waabb, query_watmaabb
procedure, public :: get_num_atoms
procedure, public :: get_aabb
procedure, public :: get_height
procedure, public :: get_max_balance
procedure, public :: get_srfarea_ratio
procedure, public :: rebuild
procedure, public :: validate
procedure, private :: insert_leaf
procedure, private :: remove_leaf
procedure, private :: balance
procedure, private :: calc_height
procedure, private :: fs_acquire
procedure, private :: fs_return
procedure, private :: validate_structure
procedure, private :: validate_metrics