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)
BSPTreePoly &	operator= (const BSPTreePoly &copy)

Private Attributes
Face *	faceList

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_corners

Corner coordinates for a hexahedron, in Exodus/Patran order

Definition at line 38 of file BSPTreePoly.hpp.

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

References hex_corners, and set().

BSPTreePoly() [3/3]

moab::BSPTreePoly::BSPTreePoly ( )

inline

Definition at line 42 of file BSPTreePoly.hpp.

: faceList( 0 ) {}

~BSPTreePoly()

moab::BSPTreePoly::~BSPTreePoly ( )

inline

Definition at line 43 of file BSPTreePoly.hpp.

 {
 clear();
 }

References clear().

Member Function Documentation

clear()

void moab::BSPTreePoly::clear

(

)

Definition at line 388 of file BSPTreePoly.cpp.

{
 while( faceList )
 {
 Face* face = faceList;
 faceList = faceList->nextPtr;
 delete face;
 }
}

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.

{
 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 ); // This call might delete new_vtx
 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;
}

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(), t, 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.

{
 face_list.clear();
 for( Face* face = faceList; face; face = face->nextPtr )
 face_list.push_back( face );
}

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.

{
 vertices.clear();
 if( !face || !face->usePtr ) return;
 
 EdgeUse* coedge = face->usePtr;
 do
 {
 vertices.push_back( *coedge->end() );
 coedge = coedge->nextPtr;
 } while( coedge != face->usePtr );
}

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.

{
 if( !faceList ) // empty (zero-dimension) polyhedron
 return false;
 
 const double EPSILON = 1e-6;
 // 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 ) > EPSILON ) // if above plane, with some -epsilon
 return false;
 }
 
 return true;
}

References EPSILON, and faceList.

is_valid()

bool moab::BSPTreePoly::is_valid

(

)

const

Definition at line 805 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;
}

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.

{
#ifdef DEBUG_IDS
 BSPTreePoly::Vertex::nextID = 1;
 BSPTreePoly::Edge::nextID = 1;
 BSPTreePoly::Face::nextID = 1;
#endif
}

set()

ErrorCode moab::BSPTreePoly::set

(

const CartVect

hex_corners[8]

)

Initialize as a planar-faced hexahedron.

Parameters

hex_corners

Corner coordinates for a hexahedron, in Exodus/Patran order

Definition at line 398 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;
}

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.

{
 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 );
 }
}

References faceList.

Referenced by cut_polyhedron().

volume()

double moab::BSPTreePoly::volume

(

)

const

Assumes planar faces.

Definition at line 500 of file BSPTreePoly.cpp.

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

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

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

Member Data Documentation

faceList

Face* moab::BSPTreePoly::faceList

private

Definition at line 27 of file BSPTreePoly.hpp.

Referenced by clear(), cut_polyhedron(), get_faces(), is_point_contained(), is_valid(), set(), set_vertex_marks(), and volume().

---

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

• BSPTreePoly.hpp
• BSPTreePoly.cpp