Mesh Oriented datABase  (version 5.5.1)
An array-based unstructured mesh library
moab::BSPTreePoly Class Reference

Convex polyhedron. More...

#include <BSPTreePoly.hpp>

+ Collaboration diagram for moab::BSPTreePoly:

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

Constructor & Destructor Documentation

◆ BSPTreePoly() [1/3]

moab::BSPTreePoly::BSPTreePoly ( const BSPTreePoly copy)
private

◆ BSPTreePoly() [2/3]

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 38 of file BSPTreePoly.hpp.

38  : faceList( 0 )
39  {
40  set( hex_corners );
41  }

References hex_corners, and set().

◆ BSPTreePoly() [3/3]

moab::BSPTreePoly::BSPTreePoly ( )
inline

Definition at line 42 of file BSPTreePoly.hpp.

42 : faceList( 0 ) {}

◆ ~BSPTreePoly()

moab::BSPTreePoly::~BSPTreePoly ( )
inline

Definition at line 43 of file BSPTreePoly.hpp.

44  {
45  clear();
46  }

References clear().

Member Function Documentation

◆ clear()

void moab::BSPTreePoly::clear ( )

Definition at line 388 of file BSPTreePoly.cpp.

389 {
390  while( faceList )
391  {
392  Face* face = faceList;
394  delete face;
395  }
396 }

References faceList, and moab::BSPTreePoly::Face::nextPtr.

Referenced by set(), and ~BSPTreePoly().

◆ cut_polyhedron()

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 599 of file BSPTreePoly.cpp.

600 {
601  const double EPSILON = 1e-6; // points this close are considered coincident
602 
603  // scale epsilon rather than normalizing normal vector
604  const double epsilon = EPSILON * ( plane_normal % plane_normal );
605 
606  // Classify all points above/below plane and destroy any faces
607  // that have no vertices below the plane.
608  const int UNKNOWN = 0;
609  const int ABOVE = 1;
610  const int ON = 2;
611  const int BELOW = 3;
612  int num_above = 0;
613  set_vertex_marks( UNKNOWN );
614 
615  // Classify all points above/below plane and
616  // split any edge that intersect the plane.
617  for( Face* face = faceList; face; face = face->nextPtr )
618  {
619  EdgeUse* edge = face->usePtr;
620 
621  do
622  {
623  Vertex* start = edge->edgePtr->start();
624  Vertex* end = edge->edgePtr->end();
625 
626  if( !start->markVal )
627  {
628  double d = plane_normal % *start + plane_coeff;
629  if( d * d <= epsilon )
630  start->markVal = ON;
631  else if( d < 0.0 )
632  start->markVal = BELOW;
633  else
634  {
635  start->markVal = ABOVE;
636  ++num_above;
637  }
638  }
639 
640  if( !end->markVal )
641  {
642  double d = plane_normal % *end + plane_coeff;
643  if( d * d <= epsilon )
644  end->markVal = ON;
645  else if( d < 0.0 )
646  end->markVal = BELOW;
647  else
648  {
649  end->markVal = ABOVE;
650  ++num_above;
651  }
652  }
653 
654  if( ( end->markVal == ABOVE && start->markVal == BELOW ) ||
655  ( end->markVal == BELOW && start->markVal == ABOVE ) )
656  {
657  CartVect dir = *end - *start;
658  double t = -( plane_normal % *start + plane_coeff ) / ( dir % plane_normal );
659  Vertex* new_vtx = new Vertex( *start + t * dir );
660  new_vtx->markVal = ON;
661  split_edge( new_vtx, edge->edgePtr ); // This call might delete new_vtx
662  end = new_vtx;
663  }
664 
665  edge = edge->nextPtr;
666  } while( edge && edge != face->usePtr );
667  }
668 
669  if( !num_above ) return false;
670 
671  // Split faces
672  for( Face* face = faceList; face; face = face->nextPtr )
673  {
674  EdgeUse* edge = face->usePtr;
675 
676  EdgeUse *split_start = 0, *split_end = 0, *other_split = 0;
677  do
678  {
679  if( edge->end()->markVal == ON && edge->start()->markVal != ON )
680  {
681  if( !split_start )
682  split_start = edge->nextPtr;
683  else if( !split_end )
684  split_end = edge;
685  else
686  other_split = edge;
687  }
688 
689  edge = edge->nextPtr;
690  } while( edge && edge != face->usePtr );
691 
692  // If two vertices are on plane (but not every vertex)
693  // then split the face
694  if( split_end && !other_split )
695  {
696  assert( split_start );
697  Face* new_face = split_face( split_start, split_end );
698  new_face->nextPtr = faceList;
699  faceList = new_face;
700  }
701  }
702 
703  // Destroy all faces that are above the plane
704  Face** lptr = &faceList;
705  while( *lptr )
706  {
707  EdgeUse* edge = ( *lptr )->usePtr;
708  bool some_above = false;
709  do
710  {
711  if( edge->start()->markVal == ABOVE )
712  {
713  some_above = true;
714  break;
715  }
716  edge = edge->nextPtr;
717  } while( edge && edge != ( *lptr )->usePtr );
718 
719  if( some_above )
720  {
721  Face* dead = *lptr;
722  *lptr = ( *lptr )->nextPtr;
723  delete dead;
724  }
725  else
726  {
727  lptr = &( ( *lptr )->nextPtr );
728  }
729  }
730 
731  // Construct a new face in the cut plane
732 
733  // First find an edge to start at
734  Edge* edge_ptr = 0;
735  for( Face* face = faceList; face && !edge_ptr; face = face->nextPtr )
736  {
737  EdgeUse* co_edge = face->usePtr;
738  do
739  {
740  if( 0 == co_edge->edgePtr->other( co_edge ) )
741  {
742  edge_ptr = co_edge->edgePtr;
743  break;
744  }
745  co_edge = co_edge->nextPtr;
746  } while( co_edge && co_edge != face->usePtr );
747  }
748  if( !edge_ptr ) return false;
749 
750  // Constuct new face and first CoEdge
751  faceList = new Face( faceList );
752  Vertex *next_vtx, *start_vtx;
753  EdgeUse* prev_coedge;
754  if( edge_ptr->forwardPtr )
755  {
756  next_vtx = edge_ptr->start();
757  start_vtx = edge_ptr->end();
758  assert( !edge_ptr->reversePtr );
759  prev_coedge = edge_ptr->reversePtr = new EdgeUse( edge_ptr, faceList );
760  }
761  else
762  {
763  next_vtx = edge_ptr->end();
764  start_vtx = edge_ptr->start();
765  prev_coedge = edge_ptr->forwardPtr = new EdgeUse( edge_ptr, faceList );
766  }
767 
768  // Construct coedges until loop is closed
769  while( next_vtx != start_vtx )
770  {
771  // find next edge adjacent to vertex with only one adjacent face
772  VertexUse* this_use = edge_ptr->use( next_vtx );
773  VertexUse* use = this_use->nextPtr;
774  while( use != this_use )
775  {
776  if( use->edgePtr->forwardPtr == 0 )
777  {
778  edge_ptr = use->edgePtr;
779  assert( edge_ptr->start() == next_vtx );
780  next_vtx = edge_ptr->end();
781  edge_ptr->forwardPtr = new EdgeUse( edge_ptr );
782  edge_ptr->forwardPtr->insert_after( prev_coedge );
783  prev_coedge = edge_ptr->forwardPtr;
784  break;
785  }
786  else if( use->edgePtr->reversePtr == 0 )
787  {
788  edge_ptr = use->edgePtr;
789  assert( edge_ptr->end() == next_vtx );
790  next_vtx = edge_ptr->start();
791  edge_ptr->reversePtr = new EdgeUse( edge_ptr );
792  edge_ptr->reversePtr->insert_after( prev_coedge );
793  prev_coedge = edge_ptr->reversePtr;
794  break;
795  }
796 
797  use = use->nextPtr;
798  assert( use != this_use ); // failed to close loop!
799  }
800  }
801 
802  return true;
803 }

References moab::BSPTreePoly::VertexUse::edgePtr, moab::BSPTreePoly::EdgeUse::edgePtr, moab::BSPTreePoly::Edge::end(), EPSILON, faceList, moab::BSPTreePoly::Edge::forwardPtr, moab::BSPTreePoly::EdgeUse::insert_after(), moab::BSPTreePoly::Vertex::markVal, moab::BSPTreePoly::VertexUse::nextPtr, moab::BSPTreePoly::EdgeUse::nextPtr, moab::BSPTreePoly::Face::nextPtr, moab::BSPTreePoly::Edge::other(), moab::BSPTreePoly::Edge::reversePtr, set_vertex_marks(), moab::split_edge(), moab::split_face(), moab::BSPTreePoly::Edge::start(), and moab::BSPTreePoly::Edge::use().

Referenced by moab::BSPTreeIter::calculate_polyhedron().

◆ get_faces()

void moab::BSPTreePoly::get_faces ( std::vector< const Face * > &  face_list) const

Get handles for faces.

Definition at line 466 of file BSPTreePoly.cpp.

467 {
468  face_list.clear();
469  for( Face* face = faceList; face; face = face->nextPtr )
470  face_list.push_back( face );
471 }

References faceList.

◆ get_vertices()

void moab::BSPTreePoly::get_vertices ( const Face face,
std::vector< CartVect > &  vertices 
) const

Get corner coordinates for a face.

Definition at line 473 of file BSPTreePoly.cpp.

474 {
475  vertices.clear();
476  if( !face || !face->usePtr ) return;
477 
478  EdgeUse* coedge = face->usePtr;
479  do
480  {
481  vertices.push_back( *coedge->end() );
482  coedge = coedge->nextPtr;
483  } while( coedge != face->usePtr );
484 }

References moab::BSPTreePoly::EdgeUse::end(), and moab::BSPTreePoly::EdgeUse::nextPtr.

◆ is_point_contained()

bool moab::BSPTreePoly::is_point_contained ( const CartVect point) const

Test if a point is contained in the polyhedron.

\NOTE algorithm assumes convex polyhedron.

Definition at line 877 of file BSPTreePoly.cpp.

878 {
879  if( !faceList ) // empty (zero-dimension) polyhedron
880  return false;
881 
882  const double EPSILON = 1e-6;
883  // Test that point is below the plane of each face
884  // NOTE: This will NOT work for polyhedra w/ concavities
885  for( Face* face = faceList; face; face = face->nextPtr )
886  {
887  Vertex *pt1, *pt2, *pt3;
888  pt1 = face->usePtr->start();
889  pt2 = face->usePtr->end();
890  pt3 = face->usePtr->nextPtr->end();
891 
892  if( pt3 == pt1 ) // degenerate
893  continue;
894 
895  CartVect norm = ( *pt3 - *pt2 ) * ( *pt1 - *pt2 );
896  double coeff = -( norm % *pt2 );
897  if( ( norm % point + coeff ) > EPSILON ) // if above plane, with some -epsilon
898  return false;
899  }
900 
901  return true;
902 }

References EPSILON, and faceList.

◆ is_valid()

bool moab::BSPTreePoly::is_valid ( ) const

Definition at line 805 of file BSPTreePoly.cpp.

806 {
807  std::set< Face* > list_faces;
808 
809  int i = 0;
810  for( Face* ptr = faceList; ptr; ptr = ptr->nextPtr )
811  {
812  if( ++i > 10000 ) return false;
813  if( !list_faces.insert( ptr ).second ) return false;
814  }
815 
816  std::set< Vertex* > vertices;
817  for( Face* face = faceList; face; face = face->nextPtr )
818  {
819  i = 0;
820  EdgeUse* coedge = face->usePtr;
821  do
822  {
823  if( ++i > 10000 ) return false;
824 
825  if( coedge->facePtr != face ) return false;
826 
827  Edge* edge = coedge->edgePtr;
828  if( !edge->startPtr || !edge->endPtr ) return false;
829 
830  vertices.insert( edge->start() );
831  vertices.insert( edge->end() );
832 
833  EdgeUse* other;
834  if( edge->forwardPtr == coedge )
835  other = edge->reversePtr;
836  else if( edge->reversePtr != coedge )
837  return false;
838  else
839  other = edge->forwardPtr;
840  if( !other ) return false;
841  if( list_faces.find( other->facePtr ) == list_faces.end() ) return false;
842 
843  EdgeUse* next = coedge->nextPtr;
844  if( next->prevPtr != coedge ) return false;
845  if( coedge->end() != next->start() ) return false;
846 
847  coedge = next;
848  } while( coedge != face->usePtr );
849  }
850 
851  for( std::set< Vertex* >::iterator j = vertices.begin(); j != vertices.end(); ++j )
852  {
853  Vertex* vtx = *j;
854 
855  i = 0;
856  VertexUse* use = vtx->usePtr;
857  do
858  {
859  if( ++i > 10000 ) return false;
860 
861  if( use->vtxPtr != vtx ) return false;
862 
863  Edge* edge = use->edgePtr;
864  if( !edge ) return false;
865  if( edge->startPtr != use && edge->endPtr != use ) return false;
866 
867  VertexUse* next = use->nextPtr;
868  if( next->prevPtr != use ) return false;
869 
870  use = next;
871  } while( use != vtx->usePtr );
872  }
873 
874  return true;
875 }

References moab::BSPTreePoly::VertexUse::edgePtr, moab::BSPTreePoly::EdgeUse::edgePtr, moab::BSPTreePoly::EdgeUse::end(), faceList, moab::BSPTreePoly::EdgeUse::facePtr, moab::BSPTreePoly::VertexUse::nextPtr, moab::BSPTreePoly::EdgeUse::nextPtr, moab::BSPTreePoly::Face::nextPtr, moab::BSPTreePoly::VertexUse::prevPtr, moab::BSPTreePoly::EdgeUse::prevPtr, moab::BSPTreePoly::EdgeUse::start(), moab::BSPTreePoly::Vertex::usePtr, and moab::BSPTreePoly::VertexUse::vtxPtr.

◆ operator=()

BSPTreePoly& moab::BSPTreePoly::operator= ( const BSPTreePoly copy)
private

◆ reset_debug_ids()

void moab::BSPTreePoly::reset_debug_ids ( )
static

For debugging, does nothing unless debug feature is enabled

Definition at line 189 of file BSPTreePoly.cpp.

190 {
191 #ifdef DEBUG_IDS
192  BSPTreePoly::Vertex::nextID = 1;
193  BSPTreePoly::Edge::nextID = 1;
194  BSPTreePoly::Face::nextID = 1;
195 #endif
196 }

◆ set()

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 398 of file BSPTreePoly.cpp.

399 {
400  clear();
401 
402  Vertex* vertices[8];
403  for( int i = 0; i < 8; ++i )
404  vertices[i] = new Vertex( hex_corners[i] );
405 
406  Edge* edges[12];
407 #ifdef DEBUG_IDS
408  int start_id = Edge::nextID;
409 #endif
410  for( int i = 0; i < 4; ++i )
411  {
412  int j = ( i + 1 ) % 4;
413  edges[i] = new Edge( vertices[i], vertices[j] );
414  edges[i + 4] = new Edge( vertices[i], vertices[i + 4] );
415  edges[i + 8] = new Edge( vertices[i + 4], vertices[j + 4] );
416  }
417 #ifdef DEBUG_IDS
418  for( int i = 0; i < 12; ++i )
419  edges[i]->id = start_id++;
420 #endif
421 
422  static const int face_conn[6][4] = { { 0, 5, -8, -4 }, { 1, 6, -9, -5 }, { 2, 7, -10, -6 },
423  { 3, 4, -11, -7 }, { -3, -2, -1, -12 }, { 8, 9, 10, 11 } };
424  for( int i = 0; i < 6; ++i )
425  {
426  faceList = new Face( faceList );
427  EdgeUse* prev = 0;
428  for( int j = 0; j < 4; ++j )
429  {
430  int e = face_conn[i][j];
431  if( e < 0 )
432  {
433  e = ( -e ) % 12;
434  assert( !edges[e]->reversePtr );
435  if( !prev )
436  {
437  edges[e]->reversePtr = new EdgeUse( edges[e], faceList );
438  }
439  else
440  {
441  edges[e]->reversePtr = new EdgeUse( edges[e] );
442  edges[e]->reversePtr->insert_after( prev );
443  }
444  prev = edges[e]->reversePtr;
445  }
446  else
447  {
448  assert( !edges[e]->forwardPtr );
449  if( !prev )
450  {
451  edges[e]->forwardPtr = new EdgeUse( edges[e], faceList );
452  }
453  else
454  {
455  edges[e]->forwardPtr = new EdgeUse( edges[e] );
456  edges[e]->forwardPtr->insert_after( prev );
457  }
458  prev = edges[e]->forwardPtr;
459  }
460  }
461  }
462 
463  return MB_SUCCESS;
464 }

References clear(), faceList, moab::BSPTreePoly::Edge::forwardPtr, hex_corners, moab::BSPTreePoly::EdgeUse::insert_after(), MB_SUCCESS, and moab::BSPTreePoly::Edge::reversePtr.

Referenced by BSPTreePoly(), moab::BSPTreeIter::calculate_polyhedron(), and moab::BSPTreeBoxIter::calculate_polyhedron().

◆ set_vertex_marks()

void moab::BSPTreePoly::set_vertex_marks ( int  value)
private

Definition at line 508 of file BSPTreePoly.cpp.

509 {
510  for( Face* face = faceList; face; face = face->nextPtr )
511  {
512  EdgeUse* edge = face->usePtr;
513  do
514  {
515  edge->edgePtr->start()->markVal = value;
516  edge->edgePtr->end()->markVal = value;
517  edge = edge->nextPtr;
518  } while( edge && edge != face->usePtr );
519  }
520 }

References faceList.

Referenced by cut_polyhedron().

◆ volume()

double moab::BSPTreePoly::volume ( ) const

Assumes planar faces.

Definition at line 500 of file BSPTreePoly.cpp.

501 {
502  double result = 0;
503  for( Face* ptr = faceList; ptr; ptr = ptr->nextPtr )
504  result += ptr->signed_volume();
505  return result;
506 }

References faceList, and moab::BSPTreePoly::Face::nextPtr.

Referenced by moab::BSPTreeIter::volume().

Member Data Documentation

◆ faceList

Face* moab::BSPTreePoly::faceList
private

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