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