Mesh Oriented datABase
(version 5.4.1)
Array-based unstructured mesh datastructure
|
#include <element_tree.hpp>
Public Types | |
typedef _Entity_handles | Entity_handles |
typedef _Box | Box |
typedef _Moab | Moab |
typedef _Parametrizer | Parametrizer |
typedef Entity_handles::value_type | Entity_handle |
Public Member Functions | |
Element_tree (Entity_handles &_entities, Moab &_moab, Box &_bounding_box, Parametrizer &_entity_contains) | |
Element_tree (Self &s) | |
template<typename Vector , typename Result > | |
Result & | find (const Vector &point, Result &result) const |
Private Types | |
typedef Element_tree < _Entity_handles, _Box, _Moab, _Parametrizer > | Self |
typedef std::pair< Box, Entity_handle > | Leaf_element |
typedef _element_tree::_Node < Entity_handles, std::vector < Leaf_element > > | Node |
typedef common_tree::_Element_data < Box, std::bitset< NUM_DIM *MAX_ITERATIONS *2 > > | Element_data |
typedef std::vector< Node > | Nodes |
typedef std::tr1::unordered_map < Entity_handle, Element_data > | Element_map |
typedef std::vector< typename Element_map::iterator > | Element_list |
typedef _element_tree::_Partition_data < Box > | Partition_data |
Private Member Functions | |
template<typename Iterator , typename Split_data > | |
void | compute_split (Iterator &begin, Iterator &end, Split_data &split_data, bool iteration=false) |
template<typename Split_data > | |
bool | update_split_line (Split_data &data) const |
template<typename Iterator , typename Split_data , typename Directions > | |
void | determine_split (Iterator &begin, Iterator &end, Split_data &data, const Directions &directions) |
template<typename Iterator , typename Node_index , typename Directions , typename Partition_data > | |
void | build_tree (Iterator begin, Iterator end, const Node_index node, const Directions &directions, Partition_data &_data, int &depth, const bool is_middle=false) |
template<typename Vector , typename Node_index , typename Result > | |
Result & | _find_point (const Vector &point, const Node_index &index, Result &result) const |
Private Attributes | |
const Entity_handles & | entity_handles_ |
Nodes | tree_ |
Moab & | moab |
Box | bounding_box |
Parametrizer | entity_contains |
Definition at line 231 of file element_tree.hpp.
typedef _Box moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Box |
Definition at line 237 of file element_tree.hpp.
typedef common_tree::_Element_data< Box, std::bitset< NUM_DIM * MAX_ITERATIONS * 2 > > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_data [private] |
Definition at line 249 of file element_tree.hpp.
typedef std::vector< typename Element_map::iterator > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_list [private] |
Definition at line 253 of file element_tree.hpp.
typedef std::tr1::unordered_map< Entity_handle, Element_data > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_map [private] |
Definition at line 252 of file element_tree.hpp.
typedef Entity_handles::value_type moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Entity_handle |
Definition at line 240 of file element_tree.hpp.
typedef _Entity_handles moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Entity_handles |
Definition at line 236 of file element_tree.hpp.
typedef std::pair< Box, Entity_handle > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Leaf_element [private] |
Definition at line 245 of file element_tree.hpp.
typedef _Moab moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Moab |
Definition at line 238 of file element_tree.hpp.
typedef _element_tree::_Node< Entity_handles, std::vector< Leaf_element > > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Node [private] |
Definition at line 246 of file element_tree.hpp.
typedef std::vector< Node > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Nodes [private] |
Definition at line 250 of file element_tree.hpp.
typedef _Parametrizer moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Parametrizer |
Definition at line 239 of file element_tree.hpp.
typedef _element_tree::_Partition_data< Box > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Partition_data [private] |
Definition at line 254 of file element_tree.hpp.
typedef Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer > moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Self [private] |
Definition at line 244 of file element_tree.hpp.
moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree | ( | Entity_handles & | _entities, |
Moab & | _moab, | ||
Box & | _bounding_box, | ||
Parametrizer & | _entity_contains | ||
) | [inline] |
Definition at line 258 of file element_tree.hpp.
References moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::bounding_box, moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::build_tree(), moab::common_tree::construct_element_map(), moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::entity_handles_, moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::moab, and moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::tree_.
: entity_handles_( _entities ), tree_(), moab( _moab ), bounding_box( _bounding_box ), entity_contains( _entity_contains ) { tree_.reserve( _entities.size() ); Element_map element_map( _entities.size() ); Partition_data _data; common_tree::construct_element_map( entity_handles_, element_map, _data.bounding_box, moab ); bounding_box = _data.bounding_box; _bounding_box = bounding_box; Element_list element_ordering( element_map.size() ); std::size_t index = 0; for( typename Element_map::iterator i = element_map.begin(); i != element_map.end(); ++i, ++index ) { element_ordering[index] = i; } // We only build nonempty trees if( element_ordering.size() ) { // initially all bits are set std::bitset< 3 > directions( 7 ); tree_.push_back( Node() ); int depth = 0; build_tree( element_ordering.begin(), element_ordering.end(), 0, directions, _data, depth ); std::cout << "depth: " << depth << std::endl; } }
moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree | ( | Self & | s | ) | [inline] |
Definition at line 287 of file element_tree.hpp.
: entity_handles_( s.entity_handles_ ), tree_( s.tree_ ), moab( s.moab ), bounding_box( s.bounding_box ) { }
Result& moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::_find_point | ( | const Vector & | point, |
const Node_index & | index, | ||
Result & | result | ||
) | const [inline, private] |
Definition at line 543 of file element_tree.hpp.
References moab::common_tree::box_contains_point(), moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::entity_contains, moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::moab, and moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::tree_.
Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::find().
{ typedef typename Node::Entities::const_iterator Entity_iterator; typedef typename std::pair< bool, Vector > Return_type; const Node& node = tree_[index]; if( node.leaf() ) { // check each node for( Entity_iterator i = node.entities.begin(); i != node.entities.end(); ++i ) { if( common_tree::box_contains_point( i->first, point ) ) { Return_type r = entity_contains( moab, i->second, point ); if( r.first ) { result = std::make_pair( i->second, r.second ); } return result; } } return Result( 0, point ); } if( point[node.dim] < node.left_line ) { return _find_point( point, node.left_, result ); } else if( point[node.dim] > node.right_line ) { return _find_point( point, node.right_, result ); } else { Entity_handle middle = _find_point( point, node.middle_, result ); if( middle != 0 ) { return result; } if( point[node.dim] < node.split ) { return _find_point( point, node.left_, result ); } return _find_point( point, node.right_, result ); } }
void moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::build_tree | ( | Iterator | begin, |
Iterator | end, | ||
const Node_index | node, | ||
const Directions & | directions, | ||
Partition_data & | _data, | ||
int & | depth, | ||
const bool | is_middle = false |
||
) | [inline, private] |
Definition at line 470 of file element_tree.hpp.
References moab::common_tree::assign_entities(), children, moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::determine_split(), dim, ELEMENTS_PER_LEAF, entities, EPSILON, and moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::tree_.
Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree().
{ std::size_t number_elements = std::distance( begin, end ); if( depth < MAX_DEPTH && number_elements > ELEMENTS_PER_LEAF && ( !is_middle || directions.any() ) ) { determine_split( begin, end, _data, directions ); // count_sort( begin, end, _data); std::sort( begin, end, _element_tree::Iterator_comparator< Iterator >() ); // update the tree tree_[node] = _data; Iterator middle_begin( begin + _data.left() ); Iterator middle_end( middle_begin + _data.middle() ); std::vector< int > depths( 3, depth ); // left subtree if( _data.left() > 0 ) { Partition_data data( _data ); tree_.push_back( Node() ); tree_[node].children[0] = tree_.size() - 1; correct_bounding_box( _data, data.bounding_box, 0 ); Directions new_directions( directions ); const bool axis_is_very_small = ( data.bounding_box.max[_data.dim] - data.bounding_box.min[_data.dim] < EPSILON ); new_directions.set( _data.dim, axis_is_very_small ); build_tree( begin, middle_begin, tree_[node].children[0], new_directions, data, ++depths[0], is_middle ); } // middle subtree if( _data.middle() > 0 ) { Partition_data data( _data ); tree_.push_back( Node() ); tree_[node].children[1] = tree_.size() - 1; correct_bounding_box( _data, data.bounding_box, 1 ); // force the middle subtree to split // in a different direction from this one Directions new_directions( directions ); new_directions.flip( tree_[node].dim ); bool axis_is_very_small = ( data.bounding_box.max[_data.dim] - data.bounding_box.min[_data.dim] < EPSILON ); new_directions.set( _data.dim, axis_is_very_small ); build_tree( middle_begin, middle_end, tree_[node].children[1], new_directions, data, ++depths[1], true ); } // right subtree if( _data.right() > 0 ) { Partition_data data( _data ); tree_.push_back( Node() ); tree_[node].children[2] = tree_.size() - 1; correct_bounding_box( _data, data.bounding_box, 2 ); Directions new_directions( directions ); const bool axis_is_very_small = ( data.bounding_box.max[_data.dim] - data.bounding_box.min[_data.dim] < EPSILON ); new_directions.set( _data.dim, axis_is_very_small ); build_tree( middle_end, end, tree_[node].children[2], directions, data, ++depths[2], is_middle ); } depth = *std::max_element( depths.begin(), depths.end() ); } if( tree_[node].leaf() ) { common_tree::assign_entities( tree_[node].entities, begin, end ); } }
void moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::compute_split | ( | Iterator & | begin, |
Iterator & | end, | ||
Split_data & | split_data, | ||
bool | iteration = false |
||
) | [inline, private] |
Definition at line 295 of file element_tree.hpp.
References dim, left_line, moab::common_tree::print_vector(), right_line, and split.
Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::determine_split().
{ typedef typename Iterator::value_type::value_type Map_value_type; typedef typename Map_value_type::second_type::second_type Bitset; // we will update the left/right line double& left_line = split_data.left_line; double& right_line = split_data.right_line; double& split = split_data.split; const int& dim = split_data.dim; #ifdef ELEMENT_TREE_DEBUG std::cout << std::endl; std::cout << "-------------------" << std::endl; std::cout << "dim: " << dim << " split: " << split << std::endl; std::cout << "bounding_box min: "; print_vector( split_data.bounding_box.min ); std::cout << "bounding_box max: "; print_vector( split_data.bounding_box.max ); #endif // for each elt determine if left/middle/right for( Iterator i = begin; i != end; ++i ) { const Box& box = ( *i )->second.first; Bitset& bits = ( *i )->second.second; // will be 0 if on left, will be 1 if in the middle // and 2 if on the right; const bool on_left = ( box.max[dim] < split ); const bool on_right = ( box.min[dim] > split ); const bool in_middle = !on_left && !on_right; // set the corresponding bits in the bit vector // looks like: [x_1 = 00 | x_2 = 00 | .. | z_1 = 00 | z_2 = 00] // two bits, left = 00, middle = 01, right = 10 const int index = 4 * dim + 2 * iteration; if( on_left ) { split_data.sizes[0]++; } else if( in_middle ) { split_data.sizes[1]++; bits.set( index, 1 ); left_line = std::min( left_line, box.min[dim] ); right_line = std::max( right_line, box.max[dim] ); } else if( on_right ) { bits.set( index + 1, 1 ); split_data.sizes[2]++; } } #ifdef ELEMENT_TREE_DEBUG std::size_t _count = std::accumulate( split_data.sizes.begin(), split_data.sizes.end(), 0 ); std::size_t total = std::distance( begin, end ); if( total != _count ) { std::cout << total << "vs. " << _count << std::endl; } std::cout << " left_line: " << left_line; std::cout << " right_line: " << right_line << std::endl; std::cout << "co/mputed partition size: "; print_vector( split_data.sizes ); std::cout << "-------------------" << std::endl; #endif }
void moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::determine_split | ( | Iterator & | begin, |
Iterator & | end, | ||
Split_data & | data, | ||
const Directions & | directions | ||
) | [inline, private] |
Definition at line 401 of file element_tree.hpp.
References moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::compute_split(), left_rightline, moab::common_tree::print_vector(), right_leftline, and moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::update_split_line().
Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::build_tree().
{ typedef typename Iterator::value_type Pair; typedef typename Pair::value_type Map_value_type; typedef typename Map_value_type::second_type::second_type Bitset; typedef typename Map_value_type::second_type::first_type Box; typedef typename std::map< std::size_t, Split_data > Splits; typedef typename Splits::value_type Split; typedef _element_tree::Split_comparator< Split > Comparator; Splits splits; for( std::size_t dir = 0; dir < directions.size(); ++dir ) { if( directions.test( dir ) ) { Split_data split_data( data.bounding_box, dir ); compute_split( begin, end, split_data ); splits.insert( std::make_pair( 2 * dir, split_data ) ); if( update_split_line( split_data ) ) { compute_split( begin, end, split_data, true ); splits.insert( std::make_pair( 2 * dir + 1, split_data ) ); } } } Split best = *std::min_element( splits.begin(), splits.end(), Comparator() ); #ifdef ELEMENT_TREE_DEBUG std::cout << "best: " << Comparator().split_objective( best ) << " "; print_vector( best.second.sizes ); #endif const int dir = best.first / 2; const int iter = best.first % 2; double& left_rightline = best.second.left_rightline = best.second.bounding_box.min[dir]; double& right_leftline = best.second.right_leftline = best.second.bounding_box.max[dir]; Bitset mask( 0 ); mask.flip( 4 * dir + 2 * iter ).flip( 4 * dir + 2 * iter + 1 ); for( Iterator i = begin; i != end; ++i ) { Bitset& bits = ( *i )->second.second; const Box& box = ( *i )->second.first; // replace 12 bits with just two. bits &= mask; bits >>= 4 * dir + 2 * iter; // if box is labeled left/right but properly contained // in the middle, move the element into the middle. // we can shrink the size of left/right switch( bits.to_ulong() ) { case 0: if( box.max[dir] > best.second.left_line ) { left_rightline = std::max( left_rightline, box.max[dir] ); } break; case 2: if( box.min[dir] < best.second.right_line ) { right_leftline = std::min( right_leftline, box.max[dir] ); } break; } } data = best.second; }
Result& moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::find | ( | const Vector & | point, |
Result & | result | ||
) | const [inline] |
Definition at line 591 of file element_tree.hpp.
References moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::_find_point().
{ typedef typename Vector::const_iterator Point_iterator; typedef typename Box::Pair Pair; typedef typename Pair::first_type Box_iterator; return _find_point( point, 0, result ); }
bool moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::update_split_line | ( | Split_data & | data | ) | const [inline, private] |
Definition at line 360 of file element_tree.hpp.
Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::determine_split().
{ const int max = 2 * ( data.sizes[2] > data.sizes[0] ); const int min = 2 * ( 1 - ( max == 2 ) ); bool one_side_empty = data.sizes[max] == 0 || data.sizes[min] == 0; double balance_ratio = data.sizes[max] - data.sizes[min]; // if ( !one_side_empty && balance_ratio < .05*total){ return false; } if( !one_side_empty ) { // if we have some imbalance on left/right // try to fix the situation balance_ratio /= data.sizes[max]; data.split += ( max - 1 ) * balance_ratio * ( data.split / 2.0 ); } else { // if the (left) side is empty move the split line just past the // extent of the (left) line of the middle box. // if middle encompasses everything then wiggle // the split line a bit and hope for the best.. const double left_distance = std::abs( data.left_line - data.split ); const double right_distance = std::abs( data.right_line - data.split ); if( ( data.sizes[0] == 0 ) && ( data.sizes[2] != 0 ) ) { data.split += right_distance; } else if( data.sizes[2] == 0 && data.sizes[0] != 0 ) { data.split -= left_distance; } else { data.split *= 1.05; } } data.left_line = data.right_line = data.split; data.sizes.assign( data.sizes.size(), 0 ); return true; }
Box moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::bounding_box [private] |
Definition at line 606 of file element_tree.hpp.
Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree().
Parametrizer moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::entity_contains [private] |
Definition at line 607 of file element_tree.hpp.
Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::_find_point().
const Entity_handles& moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::entity_handles_ [private] |
Definition at line 603 of file element_tree.hpp.
Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree().
Moab& moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::moab [private] |
Definition at line 605 of file element_tree.hpp.
Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::_find_point(), and moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree().
Nodes moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::tree_ [private] |
Definition at line 604 of file element_tree.hpp.
Referenced by moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::_find_point(), moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::build_tree(), and moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Element_tree().