Parent class of various tree types in MOAB. More...

#include <Tree.hpp>

Inheritance diagram for moab::Tree:

Collaboration diagram for moab::Tree:

Public Member Functions
	Tree (Interface *iface)
	Constructor (bare)
virtual	~Tree ()
	Destructor.
virtual ErrorCode	reset_tree ()=0
	Destroy the tree maintained by this object, optionally checking we have the right root.
ErrorCode	delete_tree_sets ()
	Delete the entity sets associated with the tree, starting with the root and traversing children.
virtual ErrorCode	build_tree (const Range &entities, EntityHandle tree_root_set=NULL, FileOptions options=NULL)=0
virtual ErrorCode	get_bounding_box (BoundBox &box, EntityHandle *tree_node=NULL) const
	Get bounding box for tree below tree_node, or entire tree If no tree has been built yet, returns +/- DBL_MAX for all dimensions. Note for some tree types, boxes are not available for non-root nodes, and this function will return failure if non-root is passed in.
virtual ErrorCode	get_info (EntityHandle root, double min[3], double max[3], unsigned int &max_dep)
	Return some basic information about the tree Stats are returned for tree starting from input node or tree root (root = 0)
ErrorCode	find_all_trees (Range &results)
	Find all trees, by bounding box tag.
virtual ErrorCode	point_search (const double point, EntityHandle &leaf_out, const double iter_tol=1.0e-10, const double inside_tol=1.0e-6, bool multiple_leaves=NULL, EntityHandle start_node=NULL, CartVect params=NULL)=0
	Get leaf containing input position.
virtual ErrorCode	distance_search (const double point, const double distance, std::vector< EntityHandle > &leaves_out, const double iter_tol=1.0e-10, const double inside_tol=1.0e-6, std::vector< double > dists_out=NULL, std::vector< CartVect > params_out=NULL, EntityHandle start_node=NULL)=0
	Find all leaves within a given distance from point If dists_out input non-NULL, also returns distances from each leaf; if point i is inside leaf, 0 is given as dists_out[i]. If params_out is non-NULL and myEval is non-NULL, will evaluate individual entities in tree nodes and return containing entities in leaves_out. In those cases, if params_out is also non-NULL, will return parameters in those elements in that vector.
Interface *	moab ()
	Return the MOAB interface associated with this tree.
const Interface *	moab () const
	Return the MOAB interface associated with this tree.
double	get_max_depth ()
	Get max depth set on tree.
double	get_max_per_leaf ()
	Get max entities per leaf set on tree.
TreeStats &	tree_stats ()
	Get tree traversal stats object.
const TreeStats &	tree_stats () const
	Get tree traversal stats object.
ErrorCode	create_root (const double box_min[3], const double box_max[3], EntityHandle &root_handle)
	Create tree root and tag with bounding box.
virtual ErrorCode	print ()=0
	print various things about this tree
ElemEvaluator *	get_eval ()
	get/set the ElemEvaluator
void	set_eval (ElemEvaluator *eval)
	get/set the ElemEvaluator
virtual ErrorCode	parse_options (FileOptions &opts)=0
	Parse options for this tree, including common options for all trees.
Protected Member Functions
ErrorCode	parse_common_options (FileOptions &options)
	Parse options common to all trees.
Tag	get_box_tag (bool create_if_missing=true)
	Get the box tag, possibly constructing it first.
Protected Attributes
Interface *	mbImpl
BoundBox	boundBox
int	maxPerLeaf
int	maxDepth
int	treeDepth
double	minWidth
unsigned int	meshsetFlags
bool	cleanUp
EntityHandle	myRoot
Tag	boxTag
std::string	boxTagName
TreeStats	treeStats
ElemEvaluator *	myEval

Detailed Description

Parent class of various tree types in MOAB.

Definition at line 27 of file Tree.hpp.

Constructor & Destructor Documentation

moab::Tree::Tree ( Interface * iface ) [inline]

Constructor (bare)

Parameters:

iface MOAB instance

Definition at line 257 of file Tree.hpp.

    : mbImpl( iface ), maxPerLeaf( 6 ), maxDepth( 30 ), treeDepth( -1 ), minWidth( 1.0e-10 ), meshsetFlags( 0 ),
      cleanUp( true ), myRoot( 0 ), boxTag( 0 ), myEval( 0 )
{
}

moab::Tree::~Tree ( ) [inline, virtual]

Destructor.

Definition at line 263 of file Tree.hpp.

{}

Member Function Documentation

virtual ErrorCode moab::Tree::build_tree	(	const Range &	entities,
		EntityHandle *	tree_root_set = `NULL`,
		FileOptions *	options = `NULL`
	)		`[pure virtual]`

Build the tree Build a tree with the entities input. If a non-NULL tree_root_set pointer is input, use the pointed-to set as the root of this tree (*tree_root_set!=0) otherwise construct a new root set and pass its handle back in *tree_root_set. Options vary by tree type, with a few common to all types of trees. Common options: MAX_PER_LEAF: max entities per leaf; default = 6 MAX_DEPTH: max depth of the tree; default = 30 MIN_WIDTH: minimum width of box, used like a tolerance; default = 1.0e-10 MESHSET_FLAGS: flags passed into meshset creation for tree nodes; should be a value from ENTITY_SET_PROPERTY (see Types.hpp); default = MESHSET_SET CLEAN_UP: if false, do not delete tree sets upon tree class destruction; default = true TAG_NAME: tag name to store tree information on tree nodes; default determined by tree type

Parameters:

entities	Entities with which to build the tree
tree_root	Root set for tree (see function description)
opts	Options for tree (see function description)

Returns:: Error is returned only on build failure

Implemented in moab::BVHTree, and moab::AdaptiveKDTree.

Referenced by moab::SpatialLocator::add_elems(), and moab::SpatialLocator::SpatialLocator().

ErrorCode moab::Tree::create_root	(	const double	box_min[3],
		const double	box_max[3],
		EntityHandle &	root_handle
	)

Create tree root and tag with bounding box.

Definition at line 63 of file Tree.cpp.

References moab::BoundBox::bMax, moab::BoundBox::bMin, boundBox, box_max(), box_min(), moab::Interface::create_meshset(), ErrorCode, get_box_tag(), MB_SUCCESS, mbImpl, meshsetFlags, myRoot, and moab::Interface::tag_set_data().

Referenced by moab::AdaptiveKDTree::build_tree(), and moab::BVHTree::build_tree().

{
    ErrorCode rval = mbImpl->create_meshset( meshsetFlags, root_handle );
    if( MB_SUCCESS != rval ) return rval;

    myRoot = root_handle;

    double box_tag[6];
    for( int i = 0; i < 3; i++ )
    {
        box_tag[i]     = box_min[i];
        box_tag[3 + i] = box_max[i];
    }
    rval = mbImpl->tag_set_data( get_box_tag(), &root_handle, 1, box_tag );
    if( MB_SUCCESS != rval ) return rval;

    boundBox.bMin = box_min;
    boundBox.bMax = box_max;

    return MB_SUCCESS;
}

ErrorCode moab::Tree::delete_tree_sets ( )

Delete the entity sets associated with the tree, starting with the root and traversing children.

Definition at line 85 of file Tree.cpp.

References boxTag, children, moab::Interface::delete_entities(), ErrorCode, moab::Interface::get_child_meshsets(), MB_SUCCESS, mbImpl, myRoot, and moab::Interface::tag_delete_data().

Referenced by moab::BVHTree::reset_tree(), and moab::AdaptiveKDTree::reset_tree().

{
    if( !myRoot ) return MB_SUCCESS;

    ErrorCode rval;
    std::vector< EntityHandle > children, dead_sets, current_sets;
    current_sets.push_back( myRoot );
    while( !current_sets.empty() )
    {
        EntityHandle set = current_sets.back();
        current_sets.pop_back();
        dead_sets.push_back( set );
        rval = mbImpl->get_child_meshsets( set, children );
        if( MB_SUCCESS != rval ) return rval;
        std::copy( children.begin(), children.end(), std::back_inserter( current_sets ) );
        children.clear();
    }

    rval = mbImpl->tag_delete_data( boxTag, &myRoot, 1 );
    if( MB_SUCCESS != rval ) return rval;

    rval = mbImpl->delete_entities( &dead_sets[0], dead_sets.size() );
    if( MB_SUCCESS != rval ) return rval;

    myRoot = 0;

    return MB_SUCCESS;
}

virtual ErrorCode moab::Tree::distance_search	(	const double *	point,
		const double	distance,
		std::vector< EntityHandle > &	leaves_out,
		const double	iter_tol = `1.0e-10`,
		const double	inside_tol = `1.0e-6`,
		std::vector< double > *	dists_out = `NULL`,
		std::vector< CartVect > *	params_out = `NULL`,
		EntityHandle *	start_node = `NULL`
	)		`[pure virtual]`

Find all leaves within a given distance from point If dists_out input non-NULL, also returns distances from each leaf; if point i is inside leaf, 0 is given as dists_out[i]. If params_out is non-NULL and myEval is non-NULL, will evaluate individual entities in tree nodes and return containing entities in leaves_out. In those cases, if params_out is also non-NULL, will return parameters in those elements in that vector.

Parameters:

point	Point to be located in tree
distance	Distance within which to query
leaves_out	Leaves within distance or containing point
iter_tol	Tolerance for convergence of point search
inside_tol	Tolerance for inside element calculation
dists_out	If non-NULL, will contain distsances to leaves
params_out	If non-NULL, will contain parameters of the point in the ents in leaves_out
start_node	Start from this tree node (non-NULL) instead of tree root (NULL)

Implemented in moab::AdaptiveKDTree.

ErrorCode moab::Tree::find_all_trees ( Range & results )

Find all trees, by bounding box tag.

Definition at line 47 of file Tree.cpp.

References moab::Range::begin(), boundBox, moab::Range::empty(), ErrorCode, get_box_tag(), moab::Interface::get_entities_by_type_and_tag(), MB_SUCCESS, MBENTITYSET, moab(), myRoot, moab::Range::size(), moab::Interface::tag_get_data(), and moab::BoundBox::update().

Referenced by main().

{
    Tag tag        = get_box_tag();
    ErrorCode rval = moab()->get_entities_by_type_and_tag( 0, MBENTITYSET, &tag, 0, 1, results );
    if( MB_SUCCESS != rval || results.empty() ) return rval;
    std::vector< BoundBox > boxes( results.size() );
    rval = moab()->tag_get_data( tag, results, &boxes[0] );
    if( MB_SUCCESS != rval ) return rval;
    for( std::vector< BoundBox >::iterator vit = boxes.begin(); vit != boxes.end(); ++vit )
        boundBox.update( *vit );

    if( results.size() == 1 ) myRoot = *results.begin();

    return MB_SUCCESS;
}

ErrorCode moab::Tree::get_bounding_box	(	BoundBox &	box,
		EntityHandle *	tree_node = `NULL`
	)		const `[inline, virtual]`

Get bounding box for tree below tree_node, or entire tree If no tree has been built yet, returns +/- DBL_MAX for all dimensions. Note for some tree types, boxes are not available for non-root nodes, and this function will return failure if non-root is passed in.

Parameters:

box	The box for this tree
tree_node	If non-NULL, node for which box is requested, tree root if NULL

Returns:: Only returns error on fatal condition

Reimplemented in moab::BVHTree.

Definition at line 265 of file Tree.hpp.

References boundBox, MB_SUCCESS, and myRoot.

Referenced by moab::AdaptiveKDTree::distance_search(), moab::AdaptiveKDTree::get_info(), moab::Coupler::initialize_tree(), moab::AdaptiveKDTree::point_search(), moab::AdaptiveKDTree::print(), moab::AdaptiveKDTree::ray_intersect_triangles(), moab::SpatialLocator::SpatialLocator(), and moab::Coupler::test_local_box().

{
    if( ( tree_node && *tree_node == myRoot ) || !tree_node )
    {
        box = boundBox;
        return MB_SUCCESS;
    }
    else
        return MB_FAILURE;
}

Tag moab::Tree::get_box_tag ( bool create_if_missing = true ) [inline, protected]

Get the box tag, possibly constructing it first.

Parameters:

create_if_missing If true and it has not been made yet, make it

Definition at line 284 of file Tree.hpp.

References boxTag, boxTagName, ErrorCode, MB_INVALID_SIZE, MB_SUCCESS, MB_TAG_CREAT, MB_TAG_SPARSE, MB_TYPE_DOUBLE, moab(), moab::Interface::tag_delete(), and moab::Interface::tag_get_handle().

Referenced by create_root(), and find_all_trees().

{
    if( !boxTag && create_if_missing )
    {
        assert( boxTagName.length() > 0 );
        ErrorCode rval =
            moab()->tag_get_handle( boxTagName.c_str(), 6, MB_TYPE_DOUBLE, boxTag, MB_TAG_CREAT | MB_TAG_SPARSE );
        if( MB_INVALID_SIZE == rval )
        {
            // delete the tag and get it again, legacy file...
            rval = moab()->tag_delete( boxTag );
            if( MB_SUCCESS != rval ) return 0;
            boxTag = 0;
            return get_box_tag( true );
        }

        if( MB_SUCCESS != rval ) return 0;
    }

    return boxTag;
}

ElemEvaluator* moab::Tree::get_eval ( ) [inline]

get/set the ElemEvaluator

Definition at line 187 of file Tree.hpp.

References myEval.

Referenced by moab::SpatialLocator::locate_points().

    {
        return myEval;
    }

ErrorCode moab::Tree::get_info	(	EntityHandle	root,
		double	min[3],
		double	max[3],
		unsigned int &	max_dep
	)		`[inline, virtual]`

Return some basic information about the tree Stats are returned for tree starting from input node or tree root (root = 0)

Parameters:

root	If non-0, give stats below and including root
min	Minimum corner of bounding box
max	Maximum corner of bounding box
max_dep	Maximum depth of tree below root

Reimplemented in moab::AdaptiveKDTree.

Definition at line 276 of file Tree.hpp.

References MB_NOT_IMPLEMENTED.

{
    return MB_NOT_IMPLEMENTED;
}

double moab::Tree::get_max_depth ( ) [inline]

Get max depth set on tree.

Definition at line 156 of file Tree.hpp.

References maxDepth.

    {
        return maxDepth;
    }

double moab::Tree::get_max_per_leaf ( ) [inline]

Get max entities per leaf set on tree.

Definition at line 162 of file Tree.hpp.

References maxPerLeaf.

    {
        return maxPerLeaf;
    }

Interface* moab::Tree::moab ( ) [inline]

Return the MOAB interface associated with this tree.

Definition at line 143 of file Tree.hpp.

References mbImpl.

    {
        return mbImpl;
    }

const Interface* moab::Tree::moab ( ) const [inline]

Return the MOAB interface associated with this tree.

Definition at line 150 of file Tree.hpp.

References mbImpl.

    {
        return mbImpl;
    }

ErrorCode moab::Tree::parse_common_options ( FileOptions & options ) [protected]

Parse options common to all trees.

Parameters:

options Options for representing tree; see Tree::build_tree() and subclass build_tree() functions for allowed options

Returns:: Non-success returned from base class function only under catastrophic circumstances; derived classes also can recognize subclass-specific options

Definition at line 9 of file Tree.cpp.

References boxTagName, cleanUp, ErrorCode, moab::FileOptions::get_int_option(), moab::FileOptions::get_real_option(), moab::FileOptions::get_str_option(), moab::FileOptions::get_toggle_option(), maxDepth, maxPerLeaf, MB_SUCCESS, meshsetFlags, and minWidth.

Referenced by moab::BVHTree::parse_options(), and moab::AdaptiveKDTree::parse_options().

{
    double tmp_dbl;
    int tmp_int;
    // MAX_PER_LEAF: max entities per leaf; default = 6
    ErrorCode rval = options.get_int_option( "MAX_PER_LEAF", tmp_int );
    if( MB_SUCCESS == rval ) maxPerLeaf = std::max( tmp_int, 1 );

    // MAX_DEPTH: max depth of the tree; default = 30
    rval = options.get_int_option( "MAX_DEPTH", tmp_int );
    if( MB_SUCCESS == rval ) maxDepth = tmp_int;
    if( maxDepth < 1 ) maxDepth = std::numeric_limits< unsigned >::max();

    // MIN_WIDTH: minimum width of box, used like a tolerance; default = 1.0e-10
    rval = options.get_real_option( "MIN_WIDTH", tmp_dbl );
    if( MB_SUCCESS == rval ) minWidth = tmp_dbl;

    // MESHSET_FLAGS: flags passed into meshset creation for tree nodes; should be a value from
    //          ENTITY_SET_PROPERTY (see Types.hpp); default = MESHSET_SET
    rval = options.get_int_option( "MESHSET_FLAGS", tmp_int );
    if( MB_SUCCESS == rval && 0 <= tmp_int )
        meshsetFlags = (unsigned)tmp_int;
    else if( 0 > tmp_int )
        return MB_FAILURE;

    // CLEAN_UP: if false, do not delete tree sets upon tree class destruction; default = true
    bool tmp_bool;
    rval = options.get_toggle_option( "CLEAN_UP", true, tmp_bool );
    if( MB_SUCCESS == rval && !tmp_bool ) cleanUp = false;

    // TAG_NAME: tag name to store tree information on tree nodes; default = "AKDTree"
    std::string tmp_str;
    rval = options.get_str_option( "TAG_NAME", tmp_str );
    if( MB_SUCCESS == rval ) boxTagName = tmp_str;

    return MB_SUCCESS;
}

virtual ErrorCode moab::Tree::parse_options ( FileOptions & opts ) [pure virtual]

Parse options for this tree, including common options for all trees.

Parameters:

opts Options

Implemented in moab::AdaptiveKDTree, and moab::BVHTree.

virtual ErrorCode moab::Tree::point_search	(	const double *	point,
		EntityHandle &	leaf_out,
		const double	iter_tol = `1.0e-10`,
		const double	inside_tol = `1.0e-6`,
		bool *	multiple_leaves = `NULL`,
		EntityHandle *	start_node = `NULL`,
		CartVect *	params = `NULL`
	)		`[pure virtual]`

Get leaf containing input position.

Does not take into account global bounding box of tree.

Therefore there is always one leaf containing the point.

If caller wants to account for global bounding box, then caller can test against that box and not call this method at all if the point is outside the box, as there is no leaf containing the point in that case.

Parameters:

point	Point to be located in tree
leaf_out	Leaf containing point
iter_tol	Tolerance for convergence of point search
inside_tol	Tolerance for inside element calculation
multiple_leaves	Some tree types can have multiple leaves containing a point; if non-NULL, this parameter is returned true if multiple leaves contain the input point
start_node	Start from this tree node (non-NULL) instead of tree root (NULL)