Bin/quad/octree data structure. More...

#include <Tree.hpp>

Inheritance diagram for hexed::Tree:

Classes
struct	Connection_neighbors

Public Member Functions
	Tree (int n_dim, double root_size, Mat<> origin=Mat<>::Zero(3))
	Constructs the root element of a tree.

	Tree (std::string file_name)
	Reads a tree from a file previously written with `write()`.

basic instance information
Mat	origin () const

int	refinement_level () const
	how many calls of `refine` were required to generate this element.

Array< int >	anisotropic_refinement_level () const

Array< int >	desired_refinement_level () const
	Total desired refinement level.

Array< Int >	coordinates () const
	coordinates of vertex 0 of this element relative to `origin` in multiples of the cell size

double	nominal_size () const
	the size of the element in physical coordinates (before any deformation of the actual DG element)

Mat	nominal_shape () const

Mat	nominal_position () const
	the position of vertex 0 of the element in physical coordinates

Mat	center () const

Int	leaf_index () const
	Lowest index of the leaves of this tree in a global ordering.

Int	total_index () const
	An index that uniquely identifies this branch in the whole tree (not just the leaves).

Int	n_leaves () const
	The number of leaves descended from `this`.

Int	n_total () const
	Returns the total number of trees descended from `this`.

parent/child status
Tree *	parent ()

Tree *	graft_parent ()
	If grafted, the tree `this` was created from. Otherwise `nullptr`.

std::vector< Tree * >	children ()

std::vector< Tree * >	unique_children ()

Tree *	root (bool graft=true)
	Fetches the root element of this tree.

bool	is_root (bool graft=true)
	Checks whether `this` is the root of the tree.

bool	is_graft ()
	`true` iff `this` was created by grafting.

bool	is_leaf ()
	gives the same result as `children().empty()`

bool	is_refined (int i_dim)

bool	has_graft_connection ()

modifiers
std::vector< Tree * >	refine (std::vector< bool > refine_dims)
	Refines anisotropically along an arbitrary number of dimensions.

std::vector< Tree * >	refine ()
	Isotropic refinement.

std::vector< Tree * >	refine (int i_dim)
	Equivalent to `refine(std::vector<bool>)` on a vector with exactly one `true` element.

std::vector< Tree * >	unrefine (std::vector< bool > unrefine_dims)
	Unrefines anisotropically along an arbitrary number of dimensions.

std::vector< Tree * >	unrefine ()
	Isotropic unrefinement.

std::vector< Tree * >	unrefine (int i_dim)
	Equivalent to `unrefine(std::vector<bool>)` on a vector with exactly one `true` element.

void	force_unrefine ()
	Deletes all child elements and descendents thereof. This element is now a leaf.

Tree *	graft (Array< int > ref_level, Array< Int > coords)
	Adds a new tree outside the existing refinement heirarchy.

void	connect (std::array< std::vector< Tree * >, 2 >, Connection_direction)

void	connect (std::array< Tree *, 2 >, Connection_direction)

void	delete_grafts ()
	Deletes and disconnects all grafted trees, including their descendent. Can only be called on the root.

void	update_indices ()
	Updates the `leaf_index()` and `n_leaves()` of the entire tree. Can only be called on the root.

traversing functions
Tree *	find_leaf (Array< int > ref_level, Array< Int > coords, Array< int > bias=Array< int >::make_uniform({3}, 0))
	Finds a leaf which contains a specified set of integer coordinates.

Tree *	find_leaf (int ref_level, Array< Int > coords, Array< int > bias=Array< int >::make_uniform({3}, 0))
	Overload for isotropic refinement level.

Tree *	find_leaf (Mat<> nominal_position)
	Finds a leaf which contains a specified point in physical space.

Tree *	find_neighbor (Array< int > direction)
	Finds a leaf neighbor of this element in the specified direction.

Tree *	find_neighbor (int i_face)
	Equivalent to `find_neighbor(Array<int>)` with `direction[i_face/2] == math::sign(i_face%2)`.

std::vector< Tree * >	find_neighbors (Array< int > direction)
	Finds all leaf neighbors of this element in a specified direction.

std::vector< Tree * >	find_neighbors (int i_face)
	Equivalent to `find_neighbors(Array<int>)` with `direction[i_face/2] == math::sign(i_face%2)`.

Connection_neighbors	find_connection_neighbors (int i_face)

Tree *	find_index (Int index, bool leaf=false)
	Finds a `Tree` instance with a specific total or leaf index.

Array< int >	needs_refine (std::function< bool(Tree *)> include)

void	visualize (std::string format, std::string name)

Public Member Functions inherited from hexed::mutual::Multiple< void, void >
	Multiple (const Multiple &)=delete

	Multiple (Multiple &&that)
	steals all of `that`'s partners, leaving `that` unconnected

Multiple &	operator= (const Multiple &)=delete

Multiple &	operator= (Multiple &&that)
	steals all of `that`'s partners, leaving `that` unconnected

next::Sequence< Base< void, void > & >	partners ()
	provides access to the list of partners

next::Sequence< const Base< void, void > & >	partners () const
	provides access to the list of partners

Public Member Functions inherited from hexed::mutual::Base< void, void >
virtual void *	_mine ()

virtual const void *	_mine () const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Public Attributes
const int	n_dim

Reciprocal_ptr< Tree, Element >	elem
	`Element` generated from this tree (to be managed by the user of this class)

Deformed_element *	def_elem = nullptr
	if `elem` points to a deformed element, this can also be set to allow it to be accessed as deformed

std::vector< int >	misc_data
	As the name implies, used to store whatever random information you want.

flood fill algorithm
The flood fill algorithm sets an integer "status" attribute of a connected group of leaf elements. This is useful to distinguish inside, outside, and boundary elements in the mesh. A status value of `unprocessed` indicates an element that has not been processed by the flood fill. Identify the boundary elements by manually setting their status to any other value. Then, to identify a connected region bounded by the elements you have set, invoke `flood_fill()` on one of the elements in the region you want.
static constexpr int	unprocessed = -1

int	get_status ()
	gets the flood fill status value (initialized to `unprocessed`).

void	set_status (int)
	sets the flood fill status value

void	flood_fill (int status)
	Executes flood fill algorithm starting with this element.

void	clear_status ()
	sets the flood fill status of this and all child elements to `unprocessed`

Miscellaneous
void	write (std::string file_name)
	Writes the structure of this tree to a file.

void	traverse (std::function< void(Tree &)> task, bool include_fake=false)
	Calls `task` on every tree in index order.

static Array< int >	get_direction (int i_face, int n_dim)
	Converts between face indices and neighbor search directions.

Additional Inherited Members
Protected Member Functions inherited from hexed::mutual::Base< void, void >
void	_connect (Base< void, void > &that)
	may be overridden by derived classes to provide partners to data of some arbitrary type `T`

void	_disconnect (Base< void, void > &that)
	mutually disconnects `this` and `that` by calling both of their `_unset()` member functions

Static Protected Member Functions inherited from hexed::mutual::Base< void, void >
static void *	_yours (Base< void, void > &that)
	Accesses the `_mine()` of `that`

static const void *	_yours (const Base< void, void > &that)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Protected Attributes inherited from hexed::mutual::Base< void, void >
Lock	_lock

Detailed Description

Bin/quad/octree data structure.

Used to compute the mesh topology, i.e. which cells are connected to which and how. Only knows about the nominal position and size of elements, not deformity or flow variables. In other words, this structure represents the Cartesian elements before any deformation happens. This structure also does not know about any extrusion (for now, anyway). A few general notes about the API:

Each Tree instance is referred to as an "element" of the tree. It's children(), their children(), etc. are referred to as its "descendents". It's parent(), their parent()s, etc. are referred to as its "ancestors".
Most of the recursive traversal functions look only down, not up. That is, they search the element you invoke them on and all its descendents, but not its ancestors. Thus if you want to search the whole tree, you should call the function on the root (which hopefully you would have done anyway). The notable exception is find_neighbor(), which does go all the way up to the root before starting the recursive search.
Tree elements are never reallocated, so any pointer to a tree element remains valid when the tree is modified as long as that element is not deleted with unrefine(). Of course, unrefine() deletes tree elements so it can create dangling pointers.

Thread safety

Multiple calls to traversing functions may be made concurrently, and multiple elements may be modified concurrently. However, concurrent attempts to modify the same element (directly or indirectly) or modifying elements and calling a traversing function concurrently may result in data races.

Constructor & Destructor Documentation

◆ Tree() [1/2]

hexed::Tree::Tree	(	int	n_dim,
		double	root_size,
		Mat<>	origin = Mat<>::Zero(3) )

Constructs the root element of a tree.

All other elements will be descendents of this one.

Parameters

n_dim	number of spatial dimensions of the tree. `n_dim = 1` => bintree, `n_dim = 2` => quadtree, etc.
root_size	sets the `nominal_size` of the root element.
origin	sets the origin of the physical coordinate system. That is, the root element will have `nominal_position() == origin()`. `origin` must have at least `n_dim` elements, and only the first `n_dim` will be read.

◆ Tree() [2/2]

hexed::Tree::Tree ( std::string file_name )

Reads a tree from a file previously written with write().

New trees will automatically update_indices() (resulting in the same leaf_index() and n_leaves() as the original) but will forget the Tree::elem, Tree::def_elem, and Tree::misc_data. File extension (.tree.h5) is added automatically.

Member Function Documentation

◆ center()

Mat hexed::Tree::center ( ) const

return the center of this tree element

◆ children()

std::vector< Tree * > hexed::Tree::children ( )

If this cell has been refined, then this vector contains pointers to its children. If it has not, the vector is empty.

◆ coordinates()

Array< Int > hexed::Tree::coordinates ( ) const

coordinates of vertex 0 of this element relative to origin in multiples of the cell size

Combined with the refinement_level, this is the minimal amount of information required to locate a tree element. By vertex 0 we mean the vertex with the smallest coordinates in every dimension, e.g. the lower left corner in 2D. For example, in 2D, the root element has coordinates {0, 0}. The root element's children will have coordinates {0, 0}, {0, 1}, {1, 0}, {1, 1}. If those cells are all refined, their children will have coordinates ranging from {0, 0}, to {3, 3}.

◆ desired_refinement_level()

Array< int > hexed::Tree::desired_refinement_level ( ) const

Total desired refinement level.

anisotropic_refinement_level() plus elem->desired_refinement(), if elem is not null.

◆ find_index()

Tree * hexed::Tree::find_index	(	Int	index,
		bool	leaf = false )

Finds a Tree instance with a specific total or leaf index.

If leaf is true, finds a tree with the specified leaf index. Otherwise, finds a tree with the specified total index. If there is not tree with the specified index descended from this, returns nullptr.

◆ find_leaf() [1/2]

Tree * hexed::Tree::find_leaf	(	Array< int >	ref_level,
		Array< Int >	coords,
		Array< int >	bias = Array<int>::make_uniform({3}, 0) )

Finds a leaf which contains a specified set of integer coordinates.

Note: Only considers this element and its descendents, not neighbors that share the same root.

Recursively searches this tree and its descendents for a leaf element which contains the point determined by _coords and _ref_level. If no element is found (i.e. if the specified coordinates are outside this cell) then nullptr is returned. For each dimension, if the corresponding element of bias is 0, then the point is permitted to lie on the lower face of that dimension but not the upper face. If the corresponding element of bias is 1, then it may lie on the upper face but not the lower. The arguments _coords and bias must have at least n_dim elements and only the first n_dim are read. All elements of bias must be either 0 or 1, or the behavior is unspecified. _ref_level must be nonnegative, but there are no restrictions on how it relates to the refinement levels of the cells to be searched.

◆ find_leaf() [2/2]

Tree * hexed::Tree::find_leaf ( Mat<> nominal_position )

Finds a leaf which contains a specified point in physical space.

Note: Only considers this element and its descendents, not neighbors that share the same root.

Recursively searches this tree and its descendents for a leaf element that contains nominal_position. If no element is found (i.e. if the specified coordinates are outside this cell) then nullptr is returned. Elements are considered to contain points which are on their boundary. If multiple elements contain the specified point (i.e. it is on a boundary shared by multiple elements) then which one you get is unspecified. You are only guaranteed to get an element that contains the point.

◆ find_neighbor()

Tree * hexed::Tree::find_neighbor ( Array< int > direction )

Finds a leaf neighbor of this element in the specified direction.

Recursively searches the entire Tree (all decendents of this element's root) for the nearest element which is a leaf and whose vertex 0 is in the direction specified by direction from this element's vertex 0. All elements of direction must be -1, 0, 1. If no neighbor is found, nullptr is returned.

Note: If exactly one element of direction is nonzero, this function finds a face neighbor. If there are multiple neighbors on the same face, the one with the lowest coordinates is returned and other neighbors can be found by locating the appropriate neighbors of that cell. If more than one element of direction is nonzero, then edge or vertex neighbors are returned.

Todo: document behavior for grafted connections

◆ find_neighbors()

std::vector< Tree * > hexed::Tree::find_neighbors ( Array< int > direction )

Finds all leaf neighbors of this element in a specified direction.

Finds all elements in the entire tree which border on this one in a given direction. If the neighbors have the same or lower refinement level, this vector will contain one element which is equal to find_neighbor(direction). If the neighbors have a higher refinement level, it will find all of them instead of returning the one with the lowest coordinates. In particular, if exactly one element of direction is nonzero, you will get a vector of all the neighbors on a specific face. If no neighbors are found, the vector will be empty. Neighbors are returned in a depth-first, row-major order (in the coordinates of their own root, in the case of grafted neighbors).

◆ flood_fill()

void hexed::Tree::flood_fill ( int status )

Executes flood fill algorithm starting with this element.

Sets this element's status to the specified value. It will then check the status of all face neighbors. For any neighbors with status unprocessed, it will continue the flood fill algorithm from those elements including setting their status and evaluating their neighbors. If the element you call this function on is not a leaf, it will instead start the flood fill on the leaf descendent of this cell with the smallest coordinates (e.g. for the root in 2D, it will start with the lower-left element). The parameter status must not be equal to unprocessed. If the start element has a status value which is not unprocessed, the algorithm does nothing.

◆ graft()

Tree * hexed::Tree::graft	(	Array< int >	ref_level,
		Array< Int >	coords )

Adds a new tree outside the existing refinement heirarchy.

A tree created this way and all its descendents are said to be "grafted". By default, this tree will not have any neighbors, regardless of its ref level and coordinates. connect() can be called to establish a neighbor connection with other trees. Grafted trees can be refined, and their descendents will share their neighbor connections. For the purpose of indexing (see leaf_index()), a tree created with graft() is considered to be descended from the tree that graft() was called on. Furthermore, it will only be assigned an index if you subsequently connect the grafted tree to the tree you called graft() on. Therefore, it is recommended to graft trees from a tree you intend to connect them to.

◆ is_root()

bool hexed::Tree::is_root ( bool graft = true )

Checks whether this is the root of the tree.

Depending on graft, this can check for either the graft root or the global root. See root() for more details.

◆ leaf_index()

Int hexed::Tree::leaf_index ( ) const

Lowest index of the leaves of this tree in a global ordering.

Every leaf is assigned an index that uniquely identifies it in the global tree (starting with 0). If this is a leaf, then leaf_index() returns that index. If this is not a leaf, then leaf_index() returns the lowest index of all the leaves descended from this. New elements created by refinement/coarsening will have an index of -1 until update_indices() is called to recompute the indices of the entire tree. All leaves descended from this will have consecutive indices, implying that the difference between the lowest and highest indices is equal to n_leaves() - 1.

Warning: Any modifications to the tree (refinement, unrefinement, grafting) will invalidate the indices of any leaves that formerly had higher indices than the modified leaves. Indices will not be accurate again until update_indices() is called on the root.

◆ n_leaves()

Int hexed::Tree::n_leaves ( ) const

The number of leaves descended from this.

Warning: This count is computed by update_indices(). As a result, n_leaves() is inexpensive to call, but modifications to any of the descendents of this will cause it to be inaccurate until update_indices() is called again.

◆ n_total()

Int hexed::Tree::n_total ( ) const

Returns the total number of trees descended from this.

Includes leaves, non-leavs, grafts, and this itself.

Warning: This count is computed by update_indices(). As a result, n_total() is inexpensive to call, but modifications to any of the descendents of this will cause it to be inaccurate until update_indices() is called again.

◆ nominal_position()

Mat hexed::Tree::nominal_position ( ) const

the position of vertex 0 of the element in physical coordinates

Note that this expressed in floating point format whereas coordinates is in integer format. As an example, in 2D the root element has nominal position origin + {0, 0} and its children have coordinates origin + {0, 0}, origin + {0, .5}, origin + {.5, 0}, origin + {.5, .5}.

◆ nominal_size()

double hexed::Tree::nominal_size ( ) const

the size of the element in physical coordinates (before any deformation of the actual DG element)

Equal to \(2^{-\verb|n_dim|}\verb|root_size|\).

◆ parent()

Tree * hexed::Tree::parent ( )

If this element is not the root or a graft root, then this is a pointer to the element which was refined to obtain this element. If it is the root, then this is nullptr.

◆ refine() [1/2]

std::vector< Tree * > hexed::Tree::refine ( )

Isotropic refinement.

Equivalent to refine(std::vector<bool>) on a vector of all true.

◆ refine() [2/2]

std::vector< Tree * > hexed::Tree::refine ( std::vector< bool > refine_dims )

Refines anisotropically along an arbitrary number of dimensions.

Will refine along dimension i iff refine_dims[i] is true. refine_dims must have size n_dim. If all entries of refine_dims are true, the refenement is isotropic. If none are true, no refinement is performed. Must be leaf in order to refine. Will also attempt to simplify the structure of the tree to reduce the number of branches and make the refinement level just before the leaves as isotropic as possible (to allow the leaves maximal freedom to unrefine along any dimension). This will not change any of the leaves, but may invalidate pointers to branches that are neither roots or leaves, including this.

Returns: Pointers to the new leaves created by refining.

Warning: If refinement simplification occurs, this may be destroyed!

◆ refinement_level()

int hexed::Tree::refinement_level ( ) const

how many calls of refine were required to generate this element.

E.g. the root element has refinement level 0.

◆ root()

Tree * hexed::Tree::root ( bool graft = true )

Fetches the root element of this tree.

If graft == true and this is grafted, then this will be only the graft root. That is, it will traverse up the parent hierarchy, but when it gets to the original grafted tree that was refined to create this, it will stop and return that tree. If graft == false, then it will traverse graft-parent relations as well, so it will always return the global root of the entire tree.

◆ total_index()

Int hexed::Tree::total_index ( ) const

An index that uniquely identifies this branch in the whole tree (not just the leaves).

All Tree instances are assigned indices that uniquely and consecutively identify them among all Trees descended from the same root. (This is different from the leaf_index(), which is only unique for the leaves.) This function returns that index. Like leaf_index(), descendents are indexed consecutively and the difference between the highest index of any descendent of this is n_total() - 1.

Warning: Any modifications to the tree (refinement, unrefinement, grafting) will invalidate the indices of any leaves that formerly had higher indices than the modified leaves. Indices will not be accurate again until update_indices() is called on the root.

◆ traverse()

void hexed::Tree::traverse	(	std::function< void(Tree &)>	task,
		bool	include_fake = false )

Calls task on every tree in index order.

If include_fake is true, this will include certain "fake trees" which are automatically created to facilitate hanging-node graft connections but are not assigned total_index values or accessible by neighbor-finding algorithms. By default, these trees are skipped.

◆ unrefine() [1/2]

std::vector< Tree * > hexed::Tree::unrefine ( )

Isotropic unrefinement.

Equivalent to unrefine(std::vector<bool>) on a vector of all true.

◆ unrefine() [2/2]

std::vector< Tree * > hexed::Tree::unrefine ( std::vector< bool > unrefine_dims )

Unrefines anisotropically along an arbitrary number of dimensions.

Will refine along dimension i iff refine_dims[i] is true. For each i where unrefine_dims[i] is true, is_refined[i] must also be true, or else it throws. Each child must also be a leaf, or else it also throws.

◆ write()

void hexed::Tree::write ( std::string file_name )

Writes the structure of this tree to a file.

File extension (.tree.h5) is added automatically.

The documentation for this class was generated from the following files:

/home/micaiah/Desktop/hexed/include/Tree.hpp
/home/micaiah/Desktop/hexed/libhexed/Tree.cpp

Classes

Public Member Functions

Public Attributes

flood fill algorithm

Miscellaneous

Additional Inherited Members