Iterate over leaves of a BSPTree. More...

#include <BSPTree.hpp>

Inheritance diagram for moab::BSPTreeBoxIter:

Classes
struct	Corners
Public Types
enum	SideBits { B0154 = 0x33, B1265 = 0x66, B2376 = 0xCC, B3047 = 0x99, B3210 = 0x0F, B4567 = 0xF0 }
	Faces of a hex : corner bitmap. More...
enum	XSect { MISS = 0, SPLIT = 1, NONHEX = -1 }
	test if a plane intersects the leaf box More...
Public Member Functions
virtual ErrorCode	step (Direction direction)
ErrorCode	step ()
ErrorCode	back ()
ErrorCode	get_box_corners (double coords[8][3]) const
	Get coordinates of box corners, in Exodus II hexahedral ordering.
double	volume () const
	Get volume of leaf box.
XSect	splits (const BSPTree::Plane &plane) const
bool	intersects (const BSPTree::Plane &plane) const
	test if a plane intersects the leaf box
bool	intersect_ray (const double ray_point[3], const double ray_vect[3], double &t_enter, double &t_exit) const
ErrorCode	sibling_side (SideBits &side_out) const
ErrorCode	get_neighbors (SideBits side, std::vector< BSPTreeBoxIter > &results, double epsilon=0.0) const
ErrorCode	calculate_polyhedron (BSPTreePoly &polyhedron_out) const
	Calculate the convex polyhedron bounding this leaf.
Static Public Member Functions
static SideBits	side_above_plane (const double hex_coords[8][3], const BSPTree::Plane &plane)
static SideBits	side_on_plane (const double hex_coords[8][3], const BSPTree::Plane &plane)
static SideBits	opposite_face (const SideBits &bits)
static ErrorCode	face_corners (const SideBits face, const double hex_corners[8][3], double face_corners_out[4][3])
Protected Member Functions
virtual ErrorCode	step_to_first_leaf (Direction direction)
virtual ErrorCode	up ()
virtual ErrorCode	down (const BSPTree::Plane &plane, Direction direction)
virtual ErrorCode	initialize (BSPTree tool, EntityHandle root, const double point=0)
Private Attributes
double	leafCoords [8][3]
std::vector< Corners >	stackData

Detailed Description

Iterate over leaves of a BSPTree.

Definition at line 340 of file BSPTree.hpp.

Member Enumeration Documentation

enum moab::BSPTreeBoxIter::SideBits

Faces of a hex : corner bitmap.

Enumerator:

B0154	Face defined by corners {0,1,5,4}: 1st Exodus side.
B1265	Face defined by corners {1,2,6,5}: 2nd Exodus side.
B2376	Face defined by corners {2,3,7,6}: 3rd Exodus side.
B3047	Face defined by corners {3,0,4,7}: 4th Exodus side.
B3210	Face defined by corners {3,2,1,0}: 5th Exodus side.
B4567	Face defined by corners {4,5,6,7}: 6th Exodus side.

Definition at line 362 of file BSPTree.hpp.

                { B0154 = 0x33, 
                  B1265 = 0x66, 
                  B2376 = 0xCC, 
                  B3047 = 0x99, 
                  B3210 = 0x0F, 
                  B4567 = 0xF0  
                 };

enum moab::BSPTreeBoxIter::XSect

test if a plane intersects the leaf box

Enumerator:

MISS
SPLIT
NONHEX

Definition at line 408 of file BSPTree.hpp.

{ MISS = 0, SPLIT = 1, NONHEX = -1 };

Member Function Documentation

ErrorCode moab::BSPTreeBoxIter::back ( ) [inline]

Move back to previous leaf Returns MB_ENTITY_NOT_FOUND if at beginning. Note: steping past the start of the tree will invalidate the iterator. Calling step() will not work.

Reimplemented from moab::BSPTreeIter.

Definition at line 399 of file BSPTree.hpp.

{ return BSPTreeIter::back(); }

ErrorCode moab::BSPTreeBoxIter::calculate_polyhedron ( BSPTreePoly & polyhedron_out ) const [virtual]

Calculate the convex polyhedron bounding this leaf.

Reimplemented from moab::BSPTreeIter.

Definition at line 1214 of file BSPTree.cpp.

{
  const CartVect* ptr = reinterpret_cast<const CartVect*>(leafCoords);
  return poly_out.set( ptr );
}

ErrorCode moab::BSPTreeBoxIter::down	(	const BSPTree::Plane &	plane,
		Direction	direction
	)		`[protected, virtual]`

Reimplemented from moab::BSPTreeIter.

Definition at line 898 of file BSPTree.cpp.

{
  childVect.clear();
  ErrorCode rval = tool()->moab()->get_child_meshsets( mStack.back(), childVect );
  if (MB_SUCCESS != rval)
    return rval;
  if (childVect.empty())
    return MB_ENTITY_NOT_FOUND;
  
  BSPTree::Plane plane(plane_ref);
  if (direction == RIGHT)
    plane.flip();
  
  Corners clipped_face;
  rval = plane_cut_box( clipped_face.coords, leafCoords, plane );
  if (MB_SUCCESS != rval)
    return rval;
  
  mStack.push_back( childVect[direction] );
  stackData.push_back( clipped_face );
  return MB_SUCCESS;
}

ErrorCode moab::BSPTreeBoxIter::face_corners	(	const SideBits	face,
		const double	hex_corners[8][3],
		double	face_corners_out[4][3]
	)		`[static]`

Definition at line 651 of file BSPTree.cpp.

{
  switch (face) {
    case BSPTreeBoxIter::B0154:
      copy_coords( hex_corners[0], face_corners[0] );
      copy_coords( hex_corners[1], face_corners[1] );
      copy_coords( hex_corners[5], face_corners[2] );
      copy_coords( hex_corners[4], face_corners[3] );
      break;
    case BSPTreeBoxIter::B1265:
      copy_coords( hex_corners[1], face_corners[0] );
      copy_coords( hex_corners[2], face_corners[1] );
      copy_coords( hex_corners[6], face_corners[2] );
      copy_coords( hex_corners[5], face_corners[3] );
      break;
    case BSPTreeBoxIter::B2376:
      copy_coords( hex_corners[2], face_corners[0] );
      copy_coords( hex_corners[3], face_corners[1] );
      copy_coords( hex_corners[7], face_corners[2] );
      copy_coords( hex_corners[6], face_corners[3] );
      break;
    case BSPTreeBoxIter::B3047:
      copy_coords( hex_corners[3], face_corners[0] );
      copy_coords( hex_corners[0], face_corners[1] );
      copy_coords( hex_corners[4], face_corners[2] );
      copy_coords( hex_corners[7], face_corners[3] );
      break;
    case BSPTreeBoxIter::B3210:
      copy_coords( hex_corners[3], face_corners[0] );
      copy_coords( hex_corners[2], face_corners[1] );
      copy_coords( hex_corners[1], face_corners[2] );
      copy_coords( hex_corners[0], face_corners[3] );
      break;
    case BSPTreeBoxIter::B4567:
      copy_coords( hex_corners[4], face_corners[0] );
      copy_coords( hex_corners[5], face_corners[1] );
      copy_coords( hex_corners[6], face_corners[2] );
      copy_coords( hex_corners[7], face_corners[3] );
      break;
    default:
      return MB_FAILURE; // child is not a box
  }
  
  return MB_SUCCESS;

}

ErrorCode moab::BSPTreeBoxIter::get_box_corners ( double coords[8][3] ) const

Get coordinates of box corners, in Exodus II hexahedral ordering.

Definition at line 984 of file BSPTree.cpp.

{
  memcpy( coords, leafCoords, 24*sizeof(double) );
  return MB_SUCCESS;
}

ErrorCode moab::BSPTreeBoxIter::get_neighbors	(	SideBits	side,
		std::vector< BSPTreeBoxIter > &	results,
		double	epsilon = `0.0`
	)		const

Get adjacent leaf nodes on indicated side

Parameters:

side	Face of box for which to retrieve neighbors
results	List to which to append results. This function does not* clear existing values in list.
epsilon	Tolerance on overlap. A positive value E will result in nodes that are separated by as much as E to be considered touching. A negative value -E will cause leaves that do not overlap by at least E to be considered non-overlapping. Amongst other things, this value can be used to control whether or not leaves adjacent at only their edges or corners are returned.

Definition at line 1107 of file BSPTree.cpp.

{
  EntityHandle tmp_handle;
  BSPTree::Plane plane;
  ErrorCode rval;
  int n;
   
  Corners face;
  rval = face_corners( side, leafCoords, face.coords );
  if (MB_SUCCESS != rval)
    return rval;
  
    // Move up tree until we find the split that created the specified side.
    // Push the sibling at that level onto the iterator stack as
    // all neighbors will be rooted at that node.
  BSPTreeBoxIter iter( *this ); // temporary iterator (don't modifiy *this)
  for (;;) {
    tmp_handle = iter.handle();
  
    rval = iter.up();
    if (MB_SUCCESS != rval) // reached root - no neighbors on that side
      return (rval == MB_ENTITY_NOT_FOUND) ? MB_SUCCESS : rval;
    
    iter.childVect.clear();
    rval = tool()->moab()->get_child_meshsets( iter.handle(), iter.childVect );
    if (MB_SUCCESS!= rval)
      return rval;
    
    rval = tool()->get_split_plane( iter.handle(), plane );
    if (MB_SUCCESS != rval)
      return rval;
    SideBits s = side_above_plane( iter.leafCoords, plane );

    if (tmp_handle == iter.childVect[0] && s == side) {
      rval = iter.down( plane, RIGHT );
      if (MB_SUCCESS != rval)
        return rval;
      break;
    }
    else if (tmp_handle == iter.childVect[1] && opposite_face(s) == side) {
      rval = iter.down( plane, LEFT );
      if (MB_SUCCESS != rval)
        return rval;
      break;
    }
  }

    // now move down tree, searching for adjacent boxes
  std::vector<BSPTreeBoxIter> list;
    // loop over all potential paths to neighbors (until list is empty)
  for (;;) {
      // follow a single path to a leaf, append any other potential
      // paths to neighbors to 'list'
    for (;;) { 
      rval = tool()->moab()->num_child_meshsets( iter.handle(), &n );
      if (MB_SUCCESS != rval)
        return rval;
        
        // if leaf
      if (!n) {
        results.push_back( iter );
        break; 
      }
      
      rval = tool()->get_split_plane( iter.handle(), plane );
      if (MB_SUCCESS != rval)
        return rval;
     
      bool some_above = false, some_below = false;
      for (int i = 0; i < 4; ++i) {
        double signed_d = plane.signed_distance( face.coords[i] );
        if (signed_d > -epsilon)
          some_above = true;
        if (signed_d < epsilon)
          some_below = true;
      }
     
      if (some_above && some_below) {
        list.push_back( iter );
        list.back().down( plane, RIGHT );
        iter.down( plane, LEFT );
      }
      else if (some_above) {
        iter.down( plane, RIGHT );
      }
      else if (some_below) {
        iter.down( plane, LEFT );
      }
      else {
        // tolerance issue -- epsilon to small? 2D box?
        return MB_FAILURE;
      }
    }
    
    if (list.empty())
      break;
    
    iter = list.back();
    list.pop_back();
  }
  
  return MB_SUCCESS;
}

ErrorCode moab::BSPTreeBoxIter::initialize	(	BSPTree *	tool,
		EntityHandle	root,
		const double *	point = `0`
	)		`[protected, virtual]`

Reimplemented from moab::BSPTreeIter.

Definition at line 603 of file BSPTree.cpp.

{
  ErrorCode rval = BSPTreeIter::initialize( tool_ptr, root );
  if (MB_SUCCESS != rval)
    return rval;
  
  tool()->get_tree_box( root, leafCoords );
  if (MB_SUCCESS != rval)
    return rval;

  if (point && !point_in_box( leafCoords, point ))
    return MB_ENTITY_NOT_FOUND;

  stackData.resize(1);
  return MB_SUCCESS;
}

bool moab::BSPTreeBoxIter::intersect_ray	(	const double	ray_point[3],
		const double	ray_vect[3],
		double &	t_enter,
		double &	t_exit
	)		const `[virtual]`

Find range of overlap between ray and leaf.

Parameters:

ray_point	Coordinates of start point of ray
ray_vect	Directionion vector for ray such that the ray is defined by r(t) = ray_point + t * ray_vect for t > 0.
t_enter	Output: if return value is true, this value is the parameter location along the ray at which the ray entered the leaf. If return value is false, then this value is undefined.
t_exit	Output: if return value is true, this value is the parameter location along the ray at which the ray exited the leaf. If return value is false, then this value is undefined.

Returns:: true if ray intersects leaf, false otherwise.

Reimplemented from moab::BSPTreeIter.

Definition at line 1356 of file BSPTree.cpp.

{
  BoxPlaneIter iter( this->leafCoords ), end;
  return ray_intersect_halfspaces( CartVect(ray_point),
                                   CartVect(ray_vect),
                                   iter, end,
                                   t_enter, t_exit );
}

bool moab::BSPTreeBoxIter::intersects ( const BSPTree::Plane & plane ) const

test if a plane intersects the leaf box

Definition at line 1083 of file BSPTree.cpp.

{
  // test each corner relative to the plane
  unsigned count  = 0;
  for (unsigned i = 0; i < 8u; ++i) 
    count += plane.above( leafCoords[i] );
  return count > 0 && count < 8u;
}

static SideBits moab::BSPTreeBoxIter::opposite_face ( const SideBits & bits ) [inline, static]

Definition at line 376 of file BSPTree.hpp.

    { return (SideBits)((~bits) & 0xFF); }

ErrorCode moab::BSPTreeBoxIter::sibling_side ( SideBits & side_out ) const

Return the side of the box bounding this tree node that is shared with the immediately adjacent sibling (the tree node that shares a common parent node with this node in the binary tree.)

Returns:: MB_ENTITY_NOT FOUND if root node. MB_FAILURE if internal error. MB_SUCCESS otherwise.

Definition at line 1092 of file BSPTree.cpp.

{
  if (mStack.size() < 2) // at tree root
    return MB_ENTITY_NOT_FOUND;
  
  EntityHandle parent = mStack[mStack.size()-2];
  BSPTree::Plane plane;
  ErrorCode rval = tool()->get_split_plane( parent, plane );
  if (MB_SUCCESS != rval)
    return MB_FAILURE;
  
  side_out = side_on_plane( leafCoords, plane );
  return MB_SUCCESS;
}

BSPTreeBoxIter::SideBits moab::BSPTreeBoxIter::side_above_plane	(	const double	hex_coords[8][3],
		const BSPTree::Plane &	plane
	)		`[static]`

Definition at line 623 of file BSPTree.cpp.

{
  unsigned result  = 0;
  for (unsigned i = 0; i < 8u; ++i) 
    result |= plane.above(hex_coords[i]) << i;
  return (BSPTreeBoxIter::SideBits)result;
}

BSPTreeBoxIter::SideBits moab::BSPTreeBoxIter::side_on_plane	(	const double	hex_coords[8][3],
		const BSPTree::Plane &	plane
	)		`[static]`

Definition at line 633 of file BSPTree.cpp.

{
  unsigned result  = 0;
  for (unsigned i = 0; i < 8u; ++i) {
    bool on = plane.distance(hex_coords[i]) <= BSPTree::epsilon();
    result |= on << i;
  }
  return (BSPTreeBoxIter::SideBits)result;
}

BSPTreeBoxIter::XSect moab::BSPTreeBoxIter::splits ( const BSPTree::Plane & plane ) const

Definition at line 1043 of file BSPTree.cpp.

{
  // test each corner relative to the plane
  unsigned result  = 0;
  for (unsigned i = 0; i < 8u; ++i) {
    double d = plane.signed_distance( leafCoords[i] );
      // if corner is on plane, than intersection 
      // will result in a degenerate hex
    if (fabs(d) < BSPTree::epsilon())
      return NONHEX;
      // if mark vertices above plane
    if (d > 0.0)
      result |= 1<<i;
  }
  
  switch (result) {
      // if all vertices or no vertices above plane,
      // then plane doesn't intersect
    case 0:
    case 0xFF:
      return MISS;
  
      // if there are four vertices above the plane
      // and they compose a single face of the hex,
      // then the cut will result in two hexes
    case B0154:
    case B1265:
    case B2376:
    case B3047:
    case B3210:
    case B4567:
      return SPLIT;
      
      // otherwise intersects, but split would not result
      // in two hexahedrons
    default:
      return NONHEX;
  }
}

ErrorCode moab::BSPTreeBoxIter::step ( Direction direction ) [virtual]

Advance the iterator either left or right in the tree Note: stepping past the end of the tree will invalidate the iterator. It will *not* work to subsequently step the other direction.

Reimplemented from moab::BSPTreeIter.

Definition at line 921 of file BSPTree.cpp.

{
  EntityHandle node, parent;
  Corners clipped_face;
  ErrorCode rval;
  BSPTree::Plane plane;
  const Direction opposite = static_cast<Direction>(1-direction);
  
    // If stack is empty, then either this iterator is uninitialized
    // or we reached the end of the iteration (and return 
    // MB_ENTITY_NOT_FOUND) already.
  if (mStack.empty())
    return MB_FAILURE;
    
    // Pop the current node from the stack.
    // The stack should then contain the parent of the current node.
    // If the stack is empty after this pop, then we've reached the end.
  node = mStack.back();
  mStack.pop_back();
  clipped_face = stackData.back();
  stackData.pop_back();
  
  while(!mStack.empty()) {
      // Get data for parent entity
    parent = mStack.back();
    childVect.clear();
    rval = tool()->moab()->get_child_meshsets( parent, childVect );
    if (MB_SUCCESS != rval)
      return rval;
    rval = tool()->get_split_plane( parent, plane );
    if (MB_SUCCESS != rval)
      return rval;
    if (direction == LEFT)
      plane.flip();
    
      // If we're at the left child
    if (childVect[opposite] == node) {
        // change from box of left child to box of parent
      plane_uncut_box( clipped_face.coords, leafCoords, plane );
        // change from box of parent to box of right child
      plane.flip();
      plane_cut_box( clipped_face.coords, leafCoords, plane );
        // push right child on stack
      mStack.push_back( childVect[direction] );
      stackData.push_back( clipped_face );
        // descend to left-most leaf of the right child
      return step_to_first_leaf(opposite);
    }
    
      // The current node is the right child of the parent,
      // continue up the tree.
    assert( childVect[direction] == node );
    plane.flip();
    plane_uncut_box( clipped_face.coords, leafCoords, plane );
    node = parent;
    clipped_face = stackData.back();
    mStack.pop_back();
    stackData.pop_back();
  }
  
  return MB_ENTITY_NOT_FOUND;
}

ErrorCode moab::BSPTreeBoxIter::step ( ) [inline]

Advance to next leaf Returns MB_ENTITY_NOT_FOUND if at end. Note: steping past the end of the tree will invalidate the iterator. Calling back() will not work.

Reimplemented from moab::BSPTreeIter.

Definition at line 393 of file BSPTree.hpp.

{ return BSPTreeIter::step(); }

ErrorCode moab::BSPTreeBoxIter::step_to_first_leaf ( Direction direction ) [protected, virtual]

Reimplemented from moab::BSPTreeIter.

Definition at line 840 of file BSPTree.cpp.

{
  ErrorCode rval;
  BSPTree::Plane plane;
  Corners clipped_corners;
  
  for (;;) {
    childVect.clear();
    rval = tool()->moab()->get_child_meshsets( mStack.back(), childVect );
    if (MB_SUCCESS != rval)
      return rval;
    if (childVect.empty()) // leaf
      break;
  
    rval = tool()->get_split_plane( mStack.back(), plane );
    if (MB_SUCCESS != rval)
      return rval;
    
    if (direction == RIGHT)
      plane.flip();
    rval = plane_cut_box( clipped_corners.coords, leafCoords, plane );
    if (MB_SUCCESS != rval)
      return rval; 
    mStack.push_back( childVect[direction] );
    stackData.push_back( clipped_corners );
  }
  return MB_SUCCESS;
}

ErrorCode moab::BSPTreeBoxIter::up ( ) [protected, virtual]

Reimplemented from moab::BSPTreeIter.

Definition at line 869 of file BSPTree.cpp.

{
  ErrorCode rval;
  if (mStack.size() == 1)
    return MB_ENTITY_NOT_FOUND;
  
  EntityHandle node = mStack.back();
  Corners clipped_face = stackData.back();
  mStack.pop_back();
  stackData.pop_back();
  
  BSPTree::Plane plane;
  rval = tool()->get_split_plane( mStack.back(), plane );
  if (MB_SUCCESS != rval) {
    mStack.push_back( node );
    stackData.push_back( clipped_face );
    return rval;
  }
  
  rval = plane_uncut_box( clipped_face.coords, leafCoords, plane );
  if (MB_SUCCESS != rval) {
    mStack.push_back( node );
    stackData.push_back( clipped_face );
    return rval;
  }
  
  return MB_SUCCESS;
}

double moab::BSPTreeBoxIter::volume ( ) const [virtual]

Get volume of leaf box.

Reimplemented from moab::BSPTreeIter.

Definition at line 1023 of file BSPTree.cpp.

{
    // have planar sides, so use mid-face tripple product
  double f1[3], f2[3], f3[3], f4[3], f5[3], f6[3];
  sum( f1, leafCoords[0], leafCoords[1], leafCoords[4], leafCoords[5] );
  sum( f2, leafCoords[1], leafCoords[2], leafCoords[5], leafCoords[6] );
  sum( f3, leafCoords[2], leafCoords[3], leafCoords[6], leafCoords[7] );
  sum( f4, leafCoords[0], leafCoords[3], leafCoords[4], leafCoords[7] );
  sum( f5, leafCoords[0], leafCoords[1], leafCoords[2], leafCoords[3] );
  sum( f6, leafCoords[4], leafCoords[5], leafCoords[6], leafCoords[7] );
  double v13[3], v24[3], v65[3];
  subtr( v13, f1, f3 );
  subtr( v24, f2, f4 );
  subtr( v65, f6, f5 );
  double cr[3];
  cross( cr, v13, v24 );
  return (1./64) * dot( cr, v65 );
}

Member Data Documentation

double moab::BSPTreeBoxIter::leafCoords[8][3] [private]

Definition at line 344 of file BSPTree.hpp.

std::vector<Corners> moab::BSPTreeBoxIter::stackData [private]

Definition at line 346 of file BSPTree.hpp.

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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

Member Function Documentation

Member Data Documentation