aabb_tree Module Reference

Axis Aligned Bounding Box (aabb) Tree data structure. More...

Data Types
type	aabb_node_t
	Node type for the Axis Aligned Bounding Box (aabb) Tree. More...
type	aabb_tree_t
	Axis Aligned Bounding Box (aabb) Tree. More...

Functions/Subroutines
subroutine	aabb_node_init (this)
	Initializes the AABB node.
pure type(aabb_t) function	aabb_node_get_aabb (this)
	Returns the Axis Aligned Bounding Box (aabb) of the node.
pure integer function	aabb_node_get_object_index (this)
	Returns the object index of the node.
pure integer function	aabb_node_get_parent_index (this)
	Returns the parent index of the node.
pure integer function	aabb_node_get_left_index (this)
	Returns the left index of the node.
pure integer function	aabb_node_get_right_index (this)
	Returns the right index of the node.
real(kind=dp) function	aabb_node_min_distance (this, p)
	Get the minimum possible distance from the aabb to a point.
pure logical function	aabb_node_is_leaf (this)
	Returns true if the node is a leaf node.
pure logical function	aabb_node_is_valid (this)
	Returns true if the node is a valid node.
pure logical function	aabb_node_less (this, other)
	Returns true if the node is less than the other node.
pure logical function	aabb_node_greater (this, other)
	Returns true if the node is greater than the other node.
subroutine	aabb_tree_init (this, initial_capacity)
	Initializes the AABB tree.
subroutine	aabb_tree_build_tree_aabb (this, objects, padding)
	Builds the tree.
subroutine	aabb_tree_build_tree (this, objects, padding)
	Builds the tree.
subroutine	sort (array, indices)
	Return a list of sorted indices of the aabb nodes.
integer function	aabb_tree_get_size (this)
	Returns the size of the tree, in number of leaves.
pure integer function	aabb_tree_get_root_index (this)
	Returns the index of the root node.
pure integer function	aabb_tree_get_parent_index (this, node_index)
	Returns the index of the parent node of the node at the given index.
pure integer function	aabb_tree_get_left_index (this, node_index)
	Returns the index of the left node of the node at the given index.
pure integer function	aabb_tree_get_right_index (this, node_index)
	Returns the index of the right node of the node at the given index.
pure type(aabb_node_t) function	aabb_tree_get_node (this, node_index)
	Returns the node at the given index.
pure type(aabb_node_t) function	aabb_tree_get_root_node (this)
	Returns the root node of the tree.
pure type(aabb_node_t) function	aabb_tree_get_parent_node (this, node_index)
	Returns the parent node of the node at the given index.
pure type(aabb_node_t) function	aabb_tree_get_left_node (this, node_index)
	Returns the left node of the node at the given index.
pure type(aabb_node_t) function	aabb_tree_get_right_node (this, node_index)
	Returns the right node of the node at the given index.
pure type(aabb_t) function	aabb_tree_get_aabb (this, node_index)
subroutine	aabb_tree_insert_object (this, object, object_index)
	Inserts an object into the tree.
subroutine	aabb_tree_query_overlaps (this, object, object_index, overlaps)
	Queries the tree for overlapping objects.
integer function	aabb_tree_allocate_node (this)
	Allocates a new node in the tree.
subroutine	aabb_tree_deallocate_node (this, node_index)
	Deallocates a node in the tree.
subroutine	aabb_tree_insert_leaf (this, leaf_node_index)
	Inserts a leaf into the tree.
logical function	aabb_tree_valid_tree (this)
	Validates the tree.
subroutine	aabb_tree_fix_upwards_tree (this, tree_start_index)
	Fixes the tree upwards.
subroutine	aabb_tree_print (this)
	Prints the tree.
subroutine	aabb_tree_resize_node_pool (this, new_capacity)
	Resizes the node pool.

Variables
integer, parameter, public	aabb_null_node = -1

Detailed Description

This is a Fortran implementation of an Axis Aligned Bounding Box Tree data structure. The purpose of this is to accelerate a Signed Distance Function and other spatial computations.

Function/Subroutine Documentation

aabb_node_get_aabb()

pure type(aabb_t) function aabb_tree::aabb_node_get_aabb ( class(aabb_node_t), intent(in)  this )

private

Definition at line 213 of file aabb_tree.f90.

aabb_node_get_left_index()

pure integer function aabb_tree::aabb_node_get_left_index ( class(aabb_node_t), intent(in)  this )

private

Definition at line 237 of file aabb_tree.f90.

aabb_node_get_object_index()

pure integer function aabb_tree::aabb_node_get_object_index ( class(aabb_node_t), intent(in)  this )

private

Definition at line 221 of file aabb_tree.f90.

aabb_node_get_parent_index()

pure integer function aabb_tree::aabb_node_get_parent_index ( class(aabb_node_t), intent(in)  this )

private

Definition at line 229 of file aabb_tree.f90.

aabb_node_get_right_index()

pure integer function aabb_tree::aabb_node_get_right_index ( class(aabb_node_t), intent(in)  this )

private

Definition at line 245 of file aabb_tree.f90.

aabb_node_greater()

pure logical function aabb_tree::aabb_node_greater ( class(aabb_node_t), intent(in)  this, class(aabb_node_t), intent(in)  other  )

private

Definition at line 307 of file aabb_tree.f90.

aabb_node_init()

subroutine aabb_tree::aabb_node_init

(

class(aabb_node_t), intent(inout)

this

)

Definition at line 199 of file aabb_tree.f90.

aabb_node_is_leaf()

pure logical function aabb_tree::aabb_node_is_leaf ( class(aabb_node_t), intent(in)  this )

private

Definition at line 266 of file aabb_tree.f90.

aabb_node_is_valid()

pure logical function aabb_tree::aabb_node_is_valid ( class(aabb_node_t), intent(in)  this )

private

Definition at line 275 of file aabb_tree.f90.

aabb_node_less()

pure logical function aabb_tree::aabb_node_less ( class(aabb_node_t), intent(in)  this, class(aabb_node_t), intent(in)  other  )

private

Definition at line 297 of file aabb_tree.f90.

aabb_node_min_distance()

real(kind=dp) function aabb_tree::aabb_node_min_distance ( class(aabb_node_t), intent(in)  this, real(kind=dp), dimension(3), intent(in)  p  )

private

Definition at line 253 of file aabb_tree.f90.

aabb_tree_allocate_node()

integer function aabb_tree::aabb_tree_allocate_node ( class(aabb_tree_t), intent(inout)  this )

private

Definition at line 770 of file aabb_tree.f90.

aabb_tree_build_tree()

subroutine aabb_tree::aabb_tree_build_tree ( class(aabb_tree_t), intent(inout)  this, class(*), dimension(:), intent(in), target  objects, real(kind=dp), intent(in), optional  padding  )

private

Definition at line 447 of file aabb_tree.f90.

Here is the call graph for this function:

aabb_tree_build_tree_aabb()

subroutine aabb_tree::aabb_tree_build_tree_aabb ( class(aabb_tree_t), intent(inout)  this, type(aabb_t), dimension(:), intent(in)  objects, real(kind=dp), intent(in), optional  padding  )

private

Definition at line 348 of file aabb_tree.f90.

Here is the call graph for this function:

aabb_tree_deallocate_node()

subroutine aabb_tree::aabb_tree_deallocate_node ( class(aabb_tree_t), intent(inout)  this, integer, intent(in)  node_index  )

private

Definition at line 794 of file aabb_tree.f90.

aabb_tree_fix_upwards_tree()

subroutine aabb_tree::aabb_tree_fix_upwards_tree ( class(aabb_tree_t), intent(inout)  this, integer, intent(in)  tree_start_index  )

private

This method is used to fix the tree upwards after an insertion. It is used to expand the nodes of the tree to fit the new leaf node.

Definition at line 994 of file aabb_tree.f90.

aabb_tree_get_aabb()

pure type(aabb_t) function aabb_tree::aabb_tree_get_aabb ( class(aabb_tree_t), intent(in)  this, integer, intent(in)  node_index  )

private

Definition at line 696 of file aabb_tree.f90.

aabb_tree_get_left_index()

pure integer function aabb_tree::aabb_tree_get_left_index ( class(aabb_tree_t), intent(in)  this, integer, intent(in)  node_index  )

private

Definition at line 628 of file aabb_tree.f90.

aabb_tree_get_left_node()

pure type(aabb_node_t) function aabb_tree::aabb_tree_get_left_node ( class(aabb_tree_t), intent(in)  this, integer, intent(in)  node_index  )

private

Definition at line 678 of file aabb_tree.f90.

aabb_tree_get_node()

pure type(aabb_node_t) function aabb_tree::aabb_tree_get_node ( class(aabb_tree_t), intent(in)  this, integer, intent(in)  node_index  )

private

Definition at line 651 of file aabb_tree.f90.

aabb_tree_get_parent_index()

pure integer function aabb_tree::aabb_tree_get_parent_index ( class(aabb_tree_t), intent(in)  this, integer, intent(in)  node_index  )

private

Definition at line 618 of file aabb_tree.f90.

aabb_tree_get_parent_node()

pure type(aabb_node_t) function aabb_tree::aabb_tree_get_parent_node ( class(aabb_tree_t), intent(in)  this, integer, intent(in)  node_index  )

private

Definition at line 668 of file aabb_tree.f90.

aabb_tree_get_right_index()

pure integer function aabb_tree::aabb_tree_get_right_index ( class(aabb_tree_t), intent(in)  this, integer, intent(in)  node_index  )

private

Definition at line 638 of file aabb_tree.f90.

aabb_tree_get_right_node()

pure type(aabb_node_t) function aabb_tree::aabb_tree_get_right_node ( class(aabb_tree_t), intent(in)  this, integer, intent(in)  node_index  )

private

Definition at line 687 of file aabb_tree.f90.

aabb_tree_get_root_index()

pure integer function aabb_tree::aabb_tree_get_root_index ( class(aabb_tree_t), intent(in)  this )

private

Definition at line 610 of file aabb_tree.f90.

aabb_tree_get_root_node()

pure type(aabb_node_t) function aabb_tree::aabb_tree_get_root_node ( class(aabb_tree_t), intent(in)  this )

private

Definition at line 660 of file aabb_tree.f90.

aabb_tree_get_size()

integer function aabb_tree::aabb_tree_get_size ( class(aabb_tree_t), intent(in)  this )

private

Definition at line 576 of file aabb_tree.f90.

aabb_tree_init()

subroutine aabb_tree::aabb_tree_init ( class(aabb_tree_t), intent(inout)  this, integer, intent(in)  initial_capacity  )

private

Definition at line 321 of file aabb_tree.f90.

aabb_tree_insert_leaf()

subroutine aabb_tree::aabb_tree_insert_leaf ( class(aabb_tree_t), intent(inout)  this, integer, intent(in)  leaf_node_index  )

private

Definition at line 804 of file aabb_tree.f90.

aabb_tree_insert_object()

subroutine aabb_tree::aabb_tree_insert_object ( class(aabb_tree_t), intent(inout)  this, class(*), intent(in)  object, integer, intent(in)  object_index  )

private

Definition at line 707 of file aabb_tree.f90.

Here is the call graph for this function:

aabb_tree_print()

subroutine aabb_tree::aabb_tree_print ( class(aabb_tree_t), intent(inout)  this )

private

Definition at line 1014 of file aabb_tree.f90.

aabb_tree_query_overlaps()

subroutine aabb_tree::aabb_tree_query_overlaps ( class(aabb_tree_t), intent(in)  this, class(*), intent(in)  object, integer, intent(in)  object_index, type(stack_i4_t), intent(inout)  overlaps  )

private

Definition at line 722 of file aabb_tree.f90.

Here is the call graph for this function:

aabb_tree_resize_node_pool()

subroutine aabb_tree::aabb_tree_resize_node_pool ( class(aabb_tree_t), intent(inout)  this, integer, intent(in)  new_capacity  )

private

Definition at line 1046 of file aabb_tree.f90.

aabb_tree_valid_tree()

logical function aabb_tree::aabb_tree_valid_tree ( class(aabb_tree_t), intent(in)  this )

private

Definition at line 957 of file aabb_tree.f90.

sort()

subroutine aabb_tree::sort ( type(aabb_t), dimension(:), intent(in)  array, integer, dimension(:), intent(inout), allocatable  indices  )

private

Definition at line 544 of file aabb_tree.f90.

Here is the caller graph for this function:

Variable Documentation

aabb_null_node

integer, parameter, public aabb_tree::aabb_null_node = -1

Definition at line 79 of file aabb_tree.f90.