hexed::Tree Class Reference

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

#include <Tree.hpp>

Public Member Functions
	Tree (int n_dim, double root_size, Mat<> origin=Mat<>::Zero(3))
	Constructs the root element of a tree.
basic instance information
Mat	origin () const
int	refinement_level () const
	how many calls of refine were required to generate this element. E.g. the root element has refinement level 0.
Eigen::VectorXi	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_position () const
	the position of vertex 0 of the element in physical coordinates
Mat	center () const
parent/child status
Tree *	parent ()
std::vector< Tree * >	children ()
	If this cell has been refined, then this vector contains pointers to its children. If it has not, the vector is empty.
Tree *	root ()
	fetch the root element of this tree
bool	is_root () const
	gives the same result as !parent()
bool	is_leaf () const
modifiers
void	refine ()
	Creates \(2^{\verb|n_dim|}\) child elements with refinement level one greater than this element and cover the same volume. Must be leaf.
void	unrefine ()
traversing functions
Tree *	find_leaf (int ref_level, Eigen::VectorXi coords, Eigen::VectorXi bias=Eigen::VectorXi::Zero(3))
	Finds a leaf which contains a specified set of integer coordinates.
Tree *	find_leaf (Mat<> nominal_position)
	Finds a leaf which contains a specified point in physical space.
Tree *	find_neighbor (Eigen::VectorXi direction)
	Finds a leaf neighbor of this element in the specified direction.
std::vector< Tree * >	find_neighbors (Eigen::VectorXi direction)
	Finds all leaf neighbors of this element in a specified direction.
int	count ()
	total number of tree elements descended from this tree (including itself)

Public Attributes
const int	n_dim
Mutual_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 ()

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()

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.

Member Function Documentation

center()

Mat hexed::Tree::center

(

)

const

return the center of this tree element

clear_status()

void hexed::Tree::clear_status

(

)

sets the flood fill status of this and all child elements to unprocessed

coordinates()

Eigen::VectorXi 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}.

find_leaf() [1/2]

Tree * hexed::Tree::find_leaf	(	int	ref_level,
		Eigen::VectorXi	coords,
		Eigen::VectorXi	bias = Eigen::VectorXi::Zero(3) )

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. Example: The element with refinement level 2 and coordinates {1, 2}:

• contains {ref_level = 2, coords = {1, 2}, bias = {0, 0}}
• does not contain {ref_level = 2, coords = {2, 2}, bias = {0, 0}}
• contains {ref_level = 2, coords = {2, 2}, bias = {1, 0}}
• does not contain {ref_level = 2, coords = {2, 2}, bias = {1, 1}}
• contains {ref_level = 3, coords = {3, 5}} regardless of bias.

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

(

Eigen::VectorXi

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.

find_neighbors()

std::vector< Tree * > hexed::Tree::find_neighbors

(

Eigen::VectorXi

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.

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.

is_leaf()

bool hexed::Tree::is_leaf

(

)

const

gives the same result as children().empty()

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, then this is a pointer to the element which was refined to obtain this element. If it is the root, then this is nullptr.

unrefine()

void hexed::Tree::unrefine

(

)

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

---

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