moab
moab::BSPTreePoly Class Reference

Convex polyhedron. More...

#include <BSPTreePoly.hpp>

List of all members.

Classes

struct  Edge
struct  EdgeUse
struct  Face
struct  Vertex
struct  VertexUse

Public Member Functions

 BSPTreePoly (const CartVect hex_corners[8])
 Initialize as a planar-faced hexahedron.
 BSPTreePoly ()
 ~BSPTreePoly ()
ErrorCode set (const CartVect hex_corners[8])
 Initialize as a planar-faced hexahedron.
void clear ()
void get_faces (std::vector< const Face * > &face_list) const
 Get handles for faces.
void get_vertices (const Face *face, std::vector< CartVect > &vertices) const
 Get corner coordinates for a face.
bool cut_polyhedron (const CartVect &plane_normal, double plane_coeff)
bool is_point_contained (const CartVect &point) const
double volume () const
 Assumes planar faces.
bool is_valid () const

Static Public Member Functions

static void reset_debug_ids ()

Private Member Functions

void set_vertex_marks (int value)
 BSPTreePoly (const BSPTreePoly &copy)
BSPTreePolyoperator= (const BSPTreePoly &copy)

Private Attributes

FacefaceList

Detailed Description

Convex polyhedron.

This class is used to represent the convex polyhedron that bounds a node in a general plane-based BSP-tree.

Definition at line 16 of file BSPTreePoly.hpp.


Constructor & Destructor Documentation

moab::BSPTreePoly::BSPTreePoly ( const BSPTreePoly copy) [private]
moab::BSPTreePoly::BSPTreePoly ( const CartVect  hex_corners[8]) [inline]

Initialize as a planar-faced hexahedron.

Parameters:
hex_cornersCorner coordinates for a hexahedron, in Exodus/Patran order

Definition at line 37 of file BSPTreePoly.hpp.

: faceList(0) { set(hex_corners); }

Definition at line 38 of file BSPTreePoly.hpp.

: faceList(0) { }

Definition at line 39 of file BSPTreePoly.hpp.

{ clear(); }

Member Function Documentation

Definition at line 336 of file BSPTreePoly.cpp.

                        {
  while (faceList) {
    Face* face = faceList;
    faceList = faceList->nextPtr;
    delete face;
  }
}
bool moab::BSPTreePoly::cut_polyhedron ( const CartVect plane_normal,
double  plane_coeff 
)

Intersect a plane with a polyhedron, retaining the portion of the polyhedron below the plane. This will fail if polyhedron is not convex.

Definition at line 539 of file BSPTreePoly.cpp.

{
  const double EPSILON = 1e-6; // points this close are considered coincident

    // scale epsilon rather than normalizing normal vector
  const double epsilon = EPSILON * (plane_normal % plane_normal);

    // Classify all points above/below plane and destroy any faces
    // that have no vertices below the plane.
  const int UNKNOWN = 0;
  const int ABOVE = 1;
  const int ON = 2;
  const int BELOW = 3;
  int num_above = 0;
  set_vertex_marks( UNKNOWN );
  
    // Classify all points above/below plane and 
    // split any edge that intersect the plane.
  for (Face* face = faceList; face; face = face->nextPtr) {
    EdgeUse* edge = face->usePtr;
    
    do {
      Vertex* start = edge->edgePtr->start();
      Vertex* end = edge->edgePtr->end();

      if (!start->markVal) {
        double d = plane_normal % *start + plane_coeff;
        if (d*d <= epsilon) 
          start->markVal = ON;
        else if (d < 0.0)
          start->markVal = BELOW;
        else {
          start->markVal = ABOVE;
          ++num_above;
        }
      }

      if (!end->markVal) {
        double d = plane_normal % *end + plane_coeff;
        if (d*d <= epsilon) 
          end->markVal = ON;
        else if (d < 0.0)
          end->markVal = BELOW;
        else {
          end->markVal = ABOVE;
          ++num_above;
        }
      }

      if ((end->markVal == ABOVE && start->markVal == BELOW) ||
          (end->markVal == BELOW && start->markVal == ABOVE)) {
        CartVect dir = *end - *start;
        double t = -(plane_normal % *start + plane_coeff) / (dir % plane_normal);
        Vertex* new_vtx = new Vertex( *start + t*dir );
        new_vtx->markVal = ON;
        split_edge( new_vtx, edge->edgePtr );
        end = new_vtx;
      }

      edge = edge->nextPtr;
    } while (edge && edge != face->usePtr);
  }
  
  if (!num_above)
    return false;
  
    // Split faces
  for (Face* face = faceList; face; face = face->nextPtr) {
    EdgeUse* edge = face->usePtr;
    
    EdgeUse *split_start = 0, *split_end = 0, *other_split = 0;
    do {
      if (edge->end()->markVal == ON && edge->start()->markVal != ON) {
        if (!split_start)
          split_start = edge->nextPtr;
        else if (!split_end)
          split_end = edge;
        else
          other_split = edge;
      }

      edge = edge->nextPtr;
    } while (edge && edge != face->usePtr);

      // If two vertices are on plane (but not every vertex)
      // then split the face
    if (split_end && !other_split) {
      assert(split_start);
      Face* new_face = split_face( split_start, split_end );
      new_face->nextPtr = faceList;
      faceList = new_face;
    }
  }
  
    // Destroy all faces that are above the plane
  Face** lptr = &faceList;
  while (*lptr) {
    EdgeUse* edge = (*lptr)->usePtr;
    bool some_above = false;
    do {
      if (edge->start()->markVal == ABOVE) {
        some_above = true;
        break;
      }
      edge = edge->nextPtr;
    } while (edge && edge != (*lptr)->usePtr);
    
    if (some_above) {
      Face* dead = *lptr;
      *lptr = (*lptr)->nextPtr;
      delete dead;
    }
    else {
      lptr = &((*lptr)->nextPtr);
    }
  }
  
    // Construct a new face in the cut plane
    
    // First find an edge to start at
  Edge* edge_ptr = 0;
  for (Face* face = faceList; face && !edge_ptr; face = face->nextPtr) {
    EdgeUse* co_edge = face->usePtr;
    do {
      if (0 == co_edge->edgePtr->other(co_edge)) {
        edge_ptr = co_edge->edgePtr;
        break;
      }
      co_edge = co_edge->nextPtr;
    } while (co_edge && co_edge != face->usePtr);
  }
  if (!edge_ptr) return false;
  
    // Constuct new face and first CoEdge
  faceList = new Face( faceList );
  Vertex *next_vtx, *start_vtx;
  EdgeUse* prev_coedge;
  if (edge_ptr->forwardPtr) {
    next_vtx = edge_ptr->start();
    start_vtx = edge_ptr->end();
    assert(!edge_ptr->reversePtr);
    prev_coedge = edge_ptr->reversePtr = new EdgeUse( edge_ptr, faceList );
  }
  else {
    next_vtx = edge_ptr->end();
    start_vtx = edge_ptr->start();
    prev_coedge = edge_ptr->forwardPtr = new EdgeUse( edge_ptr, faceList );
  }
  
    // Construct coedges until loop is closed
  while (next_vtx != start_vtx) {
      // find next edge adjacent to vertex with only one adjacent face
    VertexUse* this_use = edge_ptr->use( next_vtx );
    VertexUse* use = this_use->nextPtr;
    while (use != this_use) {
      if (use->edgePtr->forwardPtr == 0) {
        edge_ptr = use->edgePtr;
        assert(edge_ptr->start() == next_vtx);
        next_vtx = edge_ptr->end();
        edge_ptr->forwardPtr = new EdgeUse( edge_ptr );
        edge_ptr->forwardPtr->insert_after( prev_coedge );
        prev_coedge = edge_ptr->forwardPtr;
        break;
      }
      else if (use->edgePtr->reversePtr == 0) {
        edge_ptr = use->edgePtr;
        assert(edge_ptr->end() == next_vtx);
        next_vtx = edge_ptr->start();
        edge_ptr->reversePtr = new EdgeUse( edge_ptr );
        edge_ptr->reversePtr->insert_after( prev_coedge );
        prev_coedge = edge_ptr->reversePtr;
        break;
      }
      
      use = use->nextPtr;
      assert( use != this_use ); // failed to close loop!
    }
  }
  
  return true;
}
void moab::BSPTreePoly::get_faces ( std::vector< const Face * > &  face_list) const

Get handles for faces.

Definition at line 407 of file BSPTreePoly.cpp.

{
  face_list.clear();
  for (Face* face = faceList; face; face = face->nextPtr)
    face_list.push_back( face );
}
void moab::BSPTreePoly::get_vertices ( const Face face,
std::vector< CartVect > &  vertices 
) const

Get corner coordinates for a face.

Definition at line 414 of file BSPTreePoly.cpp.

{
  vertices.clear();
  if (!face || !face->usePtr)
    return;
    
  EdgeUse* coedge = face->usePtr;
  do {
    vertices.push_back( *coedge->end() );
    coedge = coedge->nextPtr;
  } while (coedge != face->usePtr);
}
bool moab::BSPTreePoly::is_point_contained ( const CartVect point) const

Test if a point is contained in the polyhedron.

algorithm assumes *convex* polyhedron.

Definition at line 803 of file BSPTreePoly.cpp.

{
  if (!faceList) // empty (zero-dimension) polyhedron
    return false;
  
    // Test that point is below the plane of each face
    // NOTE: This will NOT work for polyhedra w/ concavities
  for (Face* face = faceList; face; face = face->nextPtr) {
    Vertex *pt1, *pt2, *pt3;
    pt1 = face->usePtr->start();
    pt2 = face->usePtr->end();
    pt3 = face->usePtr->nextPtr->end();
    
    if (pt3 == pt1) // degenerate
      continue;

    CartVect norm = (*pt3 - *pt2) * (*pt1 - *pt2);
    double coeff = -(norm % *pt2);
    if (norm % point > -coeff) // if above plane
      return false;
  }
  
  return true;
}

Definition at line 722 of file BSPTreePoly.cpp.

{
  std::set<Face*> list_faces;
  
  int i = 0;
  for (Face* ptr = faceList; ptr; ptr = ptr->nextPtr) {
    if (++i > 10000)
      return false;
    if (!list_faces.insert(ptr).second)
      return false;
  }
  
  std::set<Vertex*> vertices;
  for (Face* face = faceList; face; face = face->nextPtr) {
    i = 0;
    EdgeUse* coedge = face->usePtr;    
    do {
      if (++i > 10000)
        return false;
      
      if (coedge->facePtr != face)
        return false;
      
      Edge* edge = coedge->edgePtr;
      if (!edge->startPtr || !edge->endPtr)
        return false;
      
      vertices.insert( edge->start() );
      vertices.insert( edge->end() );
      
      EdgeUse* other;
      if (edge->forwardPtr == coedge)
        other = edge->reversePtr;
      else if (edge->reversePtr != coedge)
        return false;
      else
        other = edge->forwardPtr;
      if (!other)
        return false;
      if (list_faces.find( other->facePtr ) == list_faces.end())
        return false;
      
      EdgeUse* next = coedge->nextPtr;
      if (next->prevPtr != coedge)
        return false;
      if (coedge->end() != next->start())
        return false;
      
      coedge = next;
    } while (coedge != face->usePtr);
  }
  
  for (std::set<Vertex*>::iterator j = vertices.begin(); j != vertices.end(); ++j) {
    Vertex* vtx = *j;

    i = 0;
    VertexUse* use = vtx->usePtr;    
    do {
      if (++i > 10000)
        return false;
    
      if (use->vtxPtr != vtx)
        return false;
      
      Edge* edge = use->edgePtr;
      if (!edge)
        return false;
      if (edge->startPtr != use && edge->endPtr != use)
        return false;
        
      VertexUse* next = use->nextPtr;
      if (next->prevPtr != use)
        return false;
      
      use = next;
    } while (use != vtx->usePtr);
  }
  
  return true;
}
BSPTreePoly& moab::BSPTreePoly::operator= ( const BSPTreePoly copy) [private]

For debugging, does nothing unless debug feature is enabled

Definition at line 143 of file BSPTreePoly.cpp.

                                  {
#ifdef DEBUG_IDS
  BSPTreePoly::Vertex::nextID = 1;
  BSPTreePoly::Edge::nextID = 1;
  BSPTreePoly::Face::nextID = 1;
#endif
}
ErrorCode moab::BSPTreePoly::set ( const CartVect  hex_corners[8])

Initialize as a planar-faced hexahedron.

Parameters:
hex_cornersCorner coordinates for a hexahedron, in Exodus/Patran order

Definition at line 344 of file BSPTreePoly.cpp.

{
  clear();
  
  Vertex* vertices[8];
  for (int i = 0; i < 8; ++i)
    vertices[i] = new Vertex(hex_corners[i]);
  
  Edge* edges[12];
#ifdef DEBUG_IDS
  int start_id = Edge::nextID;
#endif
  for (int i = 0; i < 4; ++i) {
    int j= (i+1)%4;
    edges[i  ] = new Edge( vertices[i  ], vertices[j  ] );
    edges[i+4] = new Edge( vertices[i  ], vertices[i+4] );
    edges[i+8] = new Edge( vertices[i+4], vertices[j+4] );
  }
#ifdef DEBUG_IDS
  for (int i = 0; i < 12; ++i)
    edges[i]->id = start_id++;
#endif
  
  static const int face_conn[6][4] = { {  0,  5,  -8, -4 },
                                       {  1,  6,  -9, -5 },
                                       {  2,  7, -10, -6 },
                                       {  3,  4, -11, -7 },
                                       { -3, -2,  -1,-12 },
                                       {  8,  9,  10, 11 } };
  for (int i = 0; i < 6; ++i) {
    faceList = new Face(faceList);
    EdgeUse* prev = 0;
    for (int j = 0; j < 4; ++j) {
      int e = face_conn[i][j];
      if (e < 0) {
        e = (-e) % 12;
        assert(!edges[e]->reversePtr);
        if (!prev) {
          edges[e]->reversePtr = new EdgeUse( edges[e], faceList );
        }
        else {
          edges[e]->reversePtr = new EdgeUse( edges[e] );
          edges[e]->reversePtr->insert_after( prev );
        }
        prev = edges[e]->reversePtr;
      }
      else {
        assert(!edges[e]->forwardPtr);
        if (!prev) {
          edges[e]->forwardPtr = new EdgeUse( edges[e], faceList );
        }
        else {
          edges[e]->forwardPtr = new EdgeUse( edges[e] );
          edges[e]->forwardPtr->insert_after( prev );
        }
        prev = edges[e]->forwardPtr;          
      }
    }
  }
  
  return MB_SUCCESS;
}
void moab::BSPTreePoly::set_vertex_marks ( int  value) [private]

Definition at line 449 of file BSPTreePoly.cpp.

{
  for (Face* face = faceList; face; face = face->nextPtr) {
    EdgeUse* edge = face->usePtr;
    do {
      edge->edgePtr->start()->markVal = value;
      edge->edgePtr->end()->markVal = value;
      edge = edge->nextPtr;
    } while (edge && edge != face->usePtr);
  }
}
double moab::BSPTreePoly::volume ( ) const

Assumes planar faces.

Definition at line 441 of file BSPTreePoly.cpp.

{
  double result = 0;
  for (Face* ptr = faceList; ptr; ptr = ptr->nextPtr)
    result += ptr->signed_volume();
  return result;
}

Member Data Documentation

Definition at line 23 of file BSPTreePoly.hpp.


The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines