moab
|
Convex polyhedron. More...
#include <BSPTreePoly.hpp>
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 ©) | |
BSPTreePoly & | operator= (const BSPTreePoly ©) |
Private Attributes | |
Face * | faceList |
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.
moab::BSPTreePoly::BSPTreePoly | ( | const BSPTreePoly & | copy | ) | [private] |
moab::BSPTreePoly::BSPTreePoly | ( | const CartVect | hex_corners[8] | ) | [inline] |
Initialize as a planar-faced hexahedron.
hex_corners | Corner coordinates for a hexahedron, in Exodus/Patran order |
Definition at line 37 of file BSPTreePoly.hpp.
: faceList(0) { set(hex_corners); }
moab::BSPTreePoly::BSPTreePoly | ( | ) | [inline] |
Definition at line 38 of file BSPTreePoly.hpp.
: faceList(0) { }
moab::BSPTreePoly::~BSPTreePoly | ( | ) | [inline] |
Definition at line 39 of file BSPTreePoly.hpp.
{ clear(); }
void moab::BSPTreePoly::clear | ( | ) |
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.
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; }
bool moab::BSPTreePoly::is_valid | ( | ) | const |
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] |
void moab::BSPTreePoly::reset_debug_ids | ( | ) | [static] |
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.
hex_corners | Corner 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.
double moab::BSPTreePoly::volume | ( | ) | const |
Face* moab::BSPTreePoly::faceList [private] |
Definition at line 23 of file BSPTreePoly.hpp.