MOAB: Mesh Oriented datABase  (version 5.4.1)
Classes | Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes
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.
 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)
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

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

References hex_corners.

                                                 : faceList( 0 )
    {
        set( hex_corners );
    }
moab::BSPTreePoly::BSPTreePoly ( ) [inline]

Definition at line 42 of file BSPTreePoly.hpp.

: faceList( 0 ) {}
moab::BSPTreePoly::~BSPTreePoly ( ) [inline]

Definition at line 43 of file BSPTreePoly.hpp.

References clear().

    {
        clear();
    }

Member Function Documentation

void moab::BSPTreePoly::clear ( )

Definition at line 388 of file BSPTreePoly.cpp.

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

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

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

References moab::BSPTreePoly::VertexUse::edgePtr, moab::BSPTreePoly::EdgeUse::edgePtr, moab::BSPTreePoly::EdgeUse::end(), 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::EdgeUse::start(), moab::BSPTreePoly::Edge::start(), t, and moab::BSPTreePoly::Edge::use().

Referenced by moab::BSPTreeIter::calculate_polyhedron(), and test_cut_with_plane().

{
    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;
}
void moab::BSPTreePoly::get_faces ( std::vector< const Face * > &  face_list) const

Get handles for faces.

Definition at line 466 of file BSPTreePoly.cpp.

References faceList.

Referenced by find_face(), test_construct_from_hex(), and test_cut_with_plane().

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

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

Referenced by find_face().

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

References EPSILON, and faceList.

Referenced by test_leaf_polyhedron().

{
    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;
}
bool moab::BSPTreePoly::is_valid ( ) const

Definition at line 805 of file BSPTreePoly.cpp.

References moab::BSPTreePoly::VertexUse::edgePtr, moab::BSPTreePoly::EdgeUse::edgePtr, moab::BSPTreePoly::EdgeUse::end(), moab::BSPTreePoly::Edge::end(), moab::BSPTreePoly::Edge::endPtr, faceList, moab::BSPTreePoly::EdgeUse::facePtr, moab::BSPTreePoly::Edge::forwardPtr, moab::BSPTreePoly::VertexUse::nextPtr, moab::BSPTreePoly::EdgeUse::nextPtr, moab::BSPTreePoly::Face::nextPtr, moab::BSPTreePoly::VertexUse::prevPtr, moab::BSPTreePoly::EdgeUse::prevPtr, moab::BSPTreePoly::Edge::reversePtr, moab::BSPTreePoly::EdgeUse::start(), moab::BSPTreePoly::Edge::start(), moab::BSPTreePoly::Edge::startPtr, moab::BSPTreePoly::Vertex::usePtr, vtx(), and moab::BSPTreePoly::VertexUse::vtxPtr.

Referenced by test_construct_from_hex(), test_cut_with_plane(), test_leaf_polyhedron(), and test_volume().

{
    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]
void moab::BSPTreePoly::reset_debug_ids ( ) [static]

For debugging, does nothing unless debug feature is enabled

Definition at line 189 of file BSPTreePoly.cpp.

Referenced by test_construct_from_hex(), and test_cut_with_plane().

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

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

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

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

References moab::BSPTreePoly::EdgeUse::edgePtr, moab::BSPTreePoly::Edge::end(), faceList, moab::BSPTreePoly::Vertex::markVal, moab::BSPTreePoly::EdgeUse::nextPtr, and moab::BSPTreePoly::Edge::start().

Referenced by cut_polyhedron().

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

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

Referenced by test_leaf_polyhedron(), test_volume(), and moab::BSPTreeIter::volume().

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

Member Data Documentation

Face* moab::BSPTreePoly::faceList [private]

Definition at line 24 of file BSPTreePoly.hpp.

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

List of all members.

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