|
moab
|
#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 206 of file element_tree.hpp.
| typedef _Box moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Box |
Definition at line 211 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 227 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 233 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 231 of file element_tree.hpp.
| typedef Entity_handles::value_type moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Entity_handle |
Definition at line 214 of file element_tree.hpp.
| typedef _Entity_handles moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Entity_handles |
Definition at line 210 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 222 of file element_tree.hpp.
| typedef _Moab moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Moab |
Definition at line 212 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 223 of file element_tree.hpp.
typedef std::vector< Node> moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Nodes [private] |
Definition at line 228 of file element_tree.hpp.
| typedef _Parametrizer moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::Parametrizer |
Definition at line 213 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 234 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 221 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 238 of file element_tree.hpp.
:
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 269 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 520 of file element_tree.hpp.
{
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 443 of file element_tree.hpp.
{
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 277 of file element_tree.hpp.
{
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 372 of file element_tree.hpp.
{
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 560 of file element_tree.hpp.
{
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 336 of file element_tree.hpp.
{
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 576 of file element_tree.hpp.
Parametrizer moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::entity_contains [private] |
Definition at line 577 of file element_tree.hpp.
const Entity_handles& moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::entity_handles_ [private] |
Definition at line 573 of file element_tree.hpp.
Moab& moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::moab [private] |
Definition at line 575 of file element_tree.hpp.
Nodes moab::Element_tree< _Entity_handles, _Box, _Moab, _Parametrizer >::tree_ [private] |
Definition at line 574 of file element_tree.hpp.
1.7.6.1