diff options
Diffstat (limited to 'tool_src/BspLib/Polygon.cpp')
| -rw-r--r-- | tool_src/BspLib/Polygon.cpp | 1042 |
1 files changed, 1042 insertions, 0 deletions
diff --git a/tool_src/BspLib/Polygon.cpp b/tool_src/BspLib/Polygon.cpp new file mode 100644 index 0000000..543a1f7 --- /dev/null +++ b/tool_src/BspLib/Polygon.cpp @@ -0,0 +1,1042 @@ +//----------------------------------------------------------------------------- +// BSPLIB MODULE: Polygon.cpp +// +// Copyright (c) 1996-1998 by Markus Hadwiger +// All Rights Reserved. +//----------------------------------------------------------------------------- + +// bsplib headers +#include "BspObject.h" +#include "Polygon.h" +#include "BoundingBox.h" +#include "BSPNode.h" +#include "BspTool.h" +#include "Vertex.h" + + +BSPLIB_NAMESPACE_BEGIN + + +// construct a Polygon -------------------------------------------------------- +// +Polygon::Polygon( BspObject *bobj, int pno, int fno, Polygon *next, int num ) +{ + baseobject = bobj; + polygonno = pno; + faceno = fno; + nextpolygon = next; + numpolygons = num; + numvertindxs = 0; + vertindxs = NULL; + vindxinsertpos = NULL; +} + + +// get vertexlist of object polygon belongs to -------------------------------- +// +VertexChunk& Polygon::getVertexList() +{ + CHECK_DEREFERENCING( + if ( baseobject == NULL ) + Error(); + ); + return baseobject->getVertexList(); +} + + +// get facelist of object polygon belongs to ---------------------------------- +// +FaceChunk& Polygon::getFaceList() +{ + CHECK_DEREFERENCING( + if ( baseobject == NULL ) + Error(); + ); + return baseobject->getFaceList(); +} + + +// create new polygon and prepend it to list (append list to new polygon) ----- +// +Polygon *Polygon::NewPolygon() +{ + //CAVEAT: + // the automatical assignment of polygon and face number + // must be used judiciously! it's very easy to get the + // numbering wrong. also, a single polygon cannot be + // used as "polygon-factory" since it will always assign + // the same numbers to the new polygons, based on its own. + + //NOTE: + // normally, this function should only be used like this: + // poly = poly->NewPolygon(); + + // automatically assign sequential polygon- and face-number + return new Polygon( baseobject, numpolygons, numpolygons, this, numpolygons + 1 ); +} + + +// prepend existing polygon to list (polygon- and face id are not changed!) --- +// +Polygon *Polygon::InsertPolygon( Polygon *poly ) +{ + poly->nextpolygon = this; + poly->numpolygons = numpolygons + 1; + poly->baseobject = baseobject; + return poly; +} + + +// delete head of polygon list; return rest of list --------------------------- +// +Polygon *Polygon::DeleteHead() +{ + Polygon *temp = nextpolygon; + nextpolygon = NULL; + delete this; + //CAVEAT: + // this can create problems if function not used correctly! + // INVOKE ONLY LIKE THIS: poly = poly->DeleteHead(); + // otherwise a dangling pointer will be created! + // THIS FUNCTION MAY ALSO NEVER BE INVOKED ON STATICALLY + // ALLOCATED POLYGONS!! + return temp; +} + + +// find polygon with specific id ---------------------------------------------- +// +Polygon *Polygon::FindPolygon( int id ) +{ + // scan entire list and compare ids + for ( Polygon *scanpo = this; scanpo; scanpo = scanpo->getNext() ) { + if ( scanpo->getId() == id ) + return scanpo; + } + // no polygon with this id found + return NULL; +} + + +// sum up vertex numbers for all polygons of list ----------------------------- +// +int Polygon::SumVertexNumsEntireList() +{ + // scan entire list and compare ids + int count = 0; + for ( Polygon *scanpo = this; scanpo; scanpo = scanpo->getNext() ) + count += scanpo->getNumVertices(); + return count; +} + + +// correct relative values to refer to new base ------------------------------- +// +void Polygon::CorrectBase( BspObject *newbaseobj, int vertexindxbase, int faceidbase, int polygonidbase ) +{ + baseobject = newbaseobj; + faceno += faceidbase; + polygonno += polygonidbase; + // correct all vertex indexes by just adding offset value + for ( VIndx *vertlist = vertindxs; vertlist; vertlist = vertlist->getNext() ) + vertlist->setIndx( vertlist->getIndx() + vertexindxbase ); +} + + +// correct relative values to refer to new base using vertex index map -------- +// +void Polygon::CorrectBaseByTable( BspObject *newbaseobj, int *vtxindxmap, int faceidbase, int polygonidbase ) +{ + baseobject = newbaseobj; + faceno += faceidbase; + polygonno += polygonidbase; + // correct all vertex indexes using mapping table + for ( VIndx *vertlist = vertindxs; vertlist; vertlist = vertlist->getNext() ) + vertlist->setIndx( vtxindxmap[ vertlist->getIndx() ] ); +} + + +// write list of vertices to text-file ---------------------------------------- +// +void Polygon::FillVertexIndexArray( dword *arr ) const +{ + // scan list of vertex indexes and write them into the int array + for ( VIndx *vertlist = vertindxs; vertlist; vertlist = vertlist->getNext() ) + *arr++ = vertlist->getIndx(); +} + + +// write list of vertices to text-file ---------------------------------------- +// +void Polygon::WriteVertexList( FILE *fp, int cr ) const +{ + // scan list of vertex indexes and write them to text file + for ( VIndx *vertlist = vertindxs; vertlist; vertlist = vertlist->getNext() ) + fprintf( fp, vertlist->getNext() ? "%d, " : "%d", vertlist->getIndx() + 1 ); + if ( cr ) + fprintf( fp, "\n" ); +} + + +// write list of polygon numbers to text-file (reverse ordering) -------------- +// +void Polygon::WritePolyList( FILE *fp ) const +{ + // recurse to achieve reverse ordering + if ( nextpolygon ) + nextpolygon->WritePolyList( fp ); + + fprintf( fp, "%d, ", getId() + 1 ); +} + + +// add new VIndx for polygon at head of vertindxs ----------------------------- +// +void Polygon::PrependNewVIndx( int indx ) +{ + // prepend new VIndx + VIndx *oldhead = vertindxs; + vertindxs = new VIndx( indx, oldhead ); + // remember last node in list + if ( vindxinsertpos == NULL ) + vindxinsertpos = vertindxs; + // update number of vertex indexes + numvertindxs++; +} + + +// add new VIndx for polygon at tail of vertindxs ----------------------------- +// +void Polygon::AppendNewVIndx( int indx ) +{ + // append new VIndx + if ( vindxinsertpos != NULL ) { + vindxinsertpos->setNext( new VIndx( indx ) ); + vindxinsertpos = vindxinsertpos->getNext(); + } else { + vertindxs = new VIndx( indx ); + vindxinsertpos = vertindxs; + } + // update number of vertex indexes + numvertindxs++; +} + + +// append existing VIndx at tail of vertindxs --------------------------------- +// +void Polygon::AppendVIndx( VIndx *vindx ) +{ + // append passed in VIndx + if ( vindxinsertpos ) { + vindxinsertpos->setNext( vindx ); + } else { + vertindxs = vindx; + } + + vindxinsertpos = vindx; + //CAVEAT: + // if passed in VIndx is the head of a list + // that list is unlinked when appending! + vindx->setNext( NULL ); + // update number of vertex indexes + numvertindxs++; +} + + +// unlink last node in list of vertex indexes --------------------------------- +// +VIndx *Polygon::UnlinkLastVIndx() +{ + VIndx *vlist = vertindxs; + if ( vlist ) { + numvertindxs--; + if ( vlist->getNext() ) { + for ( ; vlist->getNext()->getNext(); vlist = vlist->getNext() ) ; + vindxinsertpos = vlist; + VIndx *node = vlist->getNext(); + vlist->setNext( NULL ); + return node; + } else { + // return one and only node in list + vindxinsertpos = NULL; + vertindxs = NULL; + return vlist; + } + } else { + // list was already empty + return NULL; + } +} + + +// calculate bounding box encompassing all polygons in list ------------------- +// +void Polygon::CalcBoundingBox( BoundingBox* &boundingbox ) +{ + VertexChunk& vtxlist = getVertexList(); + VIndx *polyvertlist = getVList(); + + Vertex3 minvertex = vtxlist[ polyvertlist->getIndx() ]; + Vertex3 maxvertex = vtxlist[ polyvertlist->getIndx() ]; + polyvertlist = polyvertlist->getNext(); + + for ( Polygon *curpoly = this; ; ) { + + for ( ; polyvertlist; polyvertlist = polyvertlist->getNext() ) { + Vertex3& testvertex = vtxlist[ polyvertlist->getIndx() ]; + + if ( testvertex.getX() < minvertex.getX() ) + minvertex.setX( testvertex.getX() ); + if ( testvertex.getY() < minvertex.getY() ) + minvertex.setY( testvertex.getY() ); + if ( testvertex.getZ() < minvertex.getZ() ) + minvertex.setZ( testvertex.getZ() ); + + if ( testvertex.getX() > maxvertex.getX() ) + maxvertex.setX( testvertex.getX() ); + if ( testvertex.getY() > maxvertex.getY() ) + maxvertex.setY( testvertex.getY() ); + if ( testvertex.getZ() > maxvertex.getZ() ) + maxvertex.setZ( testvertex.getZ() ); + } + + if ( ( curpoly = curpoly->getNext() ) != NULL ) + polyvertlist = curpoly->getVList(); + else + break; + } + + //CAVEAT: + // boundingbox MUST NOT be initialized, since it + // is overwritten without deletion! + boundingbox = new BoundingBox( minvertex, maxvertex ); +} + + +// check which class with respect to the splitter a given polygon belongs to -- +// +int Polygon::CheckIntersection( Polygon *testpoly ) +{ + VertexChunk& vtxlist = getVertexList(); + Plane splitterplane = getPlane(); + + int numneg = 0, numpos = 0, numzero = 0; + + // classify all vertices of polygon with respect to splitting plane + VIndx *polyvertlist = testpoly->getVList(); + for ( ; polyvertlist; polyvertlist = polyvertlist->getNext() ) { + Vertex3 curvertex = vtxlist[ polyvertlist->getIndx() ]; + + if ( splitterplane.PointInPositiveHalfspace( curvertex ) ) + numpos++; + else if ( splitterplane.PointInNegativeHalfspace( curvertex ) ) + numneg++; + else + numzero++; + } + + // determine polygon's classification from vertex classifications + if ( ( numneg == 0 ) && ( numpos == 0 ) ) + return POLY_IN_SAME_PLANE; + else if ( numneg == 0 ) + return POLY_IN_FRONT_SUBSPACE; + else if ( numpos == 0 ) + return POLY_IN_BACK_SUBSPACE; + else + return POLY_STRADDLES_SPLITTER; +} + + +// check which halfspace another polygon's normal's tip lies in --------------- +// +int Polygon::NormalDirectionSimilar( Polygon *testpoly ) +{ + // calculate position of normal's tip + Vertex3 normalstip = testpoly->getFirstVertex() + testpoly->getPlaneNormal(); + + // check position of tip with respect to this polygon's plane + return !getPlane().PointInNegativeHalfspace( normalstip ); +} + + +// split polygon straddling two subspaces ------------------------------------- +// +void Polygon::SplitPolygon( Polygon *poly, Polygon* &frontsubspace, Polygon* &backsubspace ) +{ + VertexChunk& vtxlist = getVertexList(); + FaceChunk& facelist = getFaceList(); + + if ( display_messages & MESSAGE_SPLITTING_POLYGON ) { + sprintf( str_scratchpad, "--- Splitting polygon %d\n", poly->getId() + 1 ); + InfoMessage( str_scratchpad ); + } + + // create the two new polygons: one for each subspace. + // the original polygon (this) will not be deleted by this function. + Polygon *frontpoly = new Polygon( baseobject, + poly->getId(), + poly->getFaceId(), + frontsubspace ); + Polygon *backpoly = new Polygon( baseobject, + poly->getId(), + poly->getFaceId(), + backsubspace ); + + // fetch normal vector and arbitrary point on splitter plane + Vector3 splitternormal = getPlaneNormal(); + Vertex3 splittervertex = getFirstVertex(); + + // init pointer to vertex-list of source polygon + VIndx *polyvertlist = poly->getVList(); + + // check location of first vertex and set starting subspace accordingly + Vector3 directionvec( splittervertex, poly->getFirstVertex() ); + if ( normalize_vectors ) + directionvec.Normalize(); + double scalprod( splitternormal.DotProduct( directionvec ) ); + + // check if first vertex lies in splitter plane + if ( fabs( scalprod ) < EPS_SCALAR ) { + + if ( display_messages & MESSAGE_STARTVERTEX_IN_SPLITTER_PLANE ) { + sprintf( str_scratchpad, "Startvertex in splitter-plane: %d\n", + polyvertlist->getIndx() + 1 ); + InfoMessage( str_scratchpad ); + } + VIndx *scan = NULL; + // scan vertex list for vertex not contained in splitter plane + for ( scan = polyvertlist->getNext(); scan; scan = scan->getNext() ) { + directionvec.CreateDirVec( splittervertex, vtxlist[ scan->getIndx() ] ); + if ( normalize_vectors ) + directionvec.Normalize(); + // set scalprod such that the start-subspace is opposite + // the first non-contained vertex's subspace + scalprod = -splitternormal.DotProduct( directionvec ); + // exit loop if non-contained vertex found + if ( fabs( scalprod ) >= EPS_SCALAR ) + break; + } + + if ( display_messages & MESSAGE_STARTVERTEX_IN_SPLITTER_PLANE ) { + if ( scan == NULL ) { + sprintf( str_scratchpad, "WARNING: all vertices contained in splitter-plane!\n" ); + } else { + sprintf( str_scratchpad, "Using vertex %d for halfspace classification.\n", + scan->getIndx() + 1 ); + } + InfoMessage( str_scratchpad ); + } + } +/* + // check if polygon to split is non-convex + if ( [non-convex polygon] ) { + ErrorMessage( "***ERROR*** Non-convex polygon encountered while splitting." ); + HandleCriticalError(); + } +*/ + // select subspace to start in + int cursubspace = ( scalprod > 0.0 ) ? FRONT_SUBSPACE : BACK_SUBSPACE; + + // split polygon into two polygons; one for each subspace --------------- + int twas1 = 0; + for ( ; polyvertlist; polyvertlist = polyvertlist->getNext() ) { + + // copy current vertex from source polygon to its respective subspace + if ( cursubspace == FRONT_SUBSPACE ) + frontpoly->AppendNewVIndx( polyvertlist->getIndx() ); + else + backpoly->AppendNewVIndx( polyvertlist->getIndx() ); + + // check intersection of splitter plane with next lineseg ----- + int nextvertex = polyvertlist->getNext() ? + polyvertlist->getNext()->getIndx() : poly->getVList()->getIndx(); + + // denominator is length of projection of lineseg onto plane normal + Vector3 linevec( vtxlist[ polyvertlist->getIndx() ], vtxlist[ nextvertex ] ); + double denominator = splitternormal.DotProduct( linevec ); + + // numerator is distance from splittervertex to startvertex of lineseg + Vector3 directionvec( splittervertex, vtxlist[ polyvertlist->getIndx() ] ); + double numerator = splitternormal.DotProduct( directionvec ); + + // if lineseg isn't parallel to splitter plane, check for intersection + if ( fabs( denominator ) >= EPS_DENOM_ZERO ) { + + double t = - numerator / denominator; + if ( twas1 || ( fabs( t ) < EPS_POINT_ON_LINESEG ) ) { + + if ( display_messages & MESSAGE_VERTEX_IN_SPLITTER_PLANE ) { + sprintf( str_scratchpad, "Vertex in splitter-plane! (%d)\n", polyvertlist->getIndx() + 1 ); + InfoMessage( str_scratchpad ); + } + + // reset flag + twas1 = 0; + + // switch subspace and insert same vertex again + cursubspace = -cursubspace; + if ( cursubspace == FRONT_SUBSPACE ) + frontpoly->AppendNewVIndx( polyvertlist->getIndx() ); + else + backpoly->AppendNewVIndx( polyvertlist->getIndx() ); + + // check if next vertex is contained in the other subspace + Vector3 directionvec( splittervertex, vtxlist[ nextvertex ] ); + if ( normalize_vectors ) + directionvec.Normalize(); + double scalprod( splitternormal.DotProduct( directionvec ) ); + if ( ( ( scalprod < 0.0 ) && ( cursubspace == FRONT_SUBSPACE ) ) || + ( ( scalprod > 0.0 ) && ( cursubspace == BACK_SUBSPACE ) ) ) { + // switch back again + cursubspace = -cursubspace; + if ( display_messages & MESSAGE_VERTEX_IN_SPLITTER_PLANE ) { + sprintf( str_scratchpad, "Vertex alone in %s halfspace!\n", + ( cursubspace == BACK_SUBSPACE ) ? "front" : "back" ); + InfoMessage( str_scratchpad ); + } + } + + //NOTE: + // the above check is necessary to avoid problems with polygons actually + // entirely contained in a single subspace but nevertheless classified as + // straddling. in this case the implicit subspace-switching for t=0 vertices + // would cause these vertices to be inserted into the wrong subspace! + + } else if ( ( t >= EPS_POINT_ON_LINESEG ) && ( t <= 1.0 - EPS_POINT_ON_LINESEG ) ) { + + // insert intersection point into both subspaces and switch + cursubspace = -cursubspace; + Vertex3 newvertex( linevec * t + vtxlist[ polyvertlist->getIndx() ] ); + int newvertindx = vtxlist.FindCloseVertex( newvertex ); + if ( newvertindx == -1 ) { + newvertindx = vtxlist.AddVertex( newvertex ); + if ( display_messages & MESSAGE_NEW_SPLITVERTEX ) { + sprintf( str_scratchpad, "Inserting new split-vertex (%d)\n", vtxlist.getNumElements() ); + InfoMessage( str_scratchpad ); + } + } else if ( display_messages & MESSAGE_REUSING_SPLITVERTEX ) { + sprintf( str_scratchpad, "Reusing split-vertex (%d)\n", newvertindx + 1 ); + InfoMessage( str_scratchpad ); + } + + frontpoly->AppendNewVIndx( newvertindx ); + backpoly->AppendNewVIndx( newvertindx ); + + } else if ( fabs( t - 1.0 ) < EPS_POINT_ON_LINESEG ) { + + // set flag + twas1 = 1; + + //NOTE: + // this flag is necessary to avoid numerical problems when + // a vertex is classified as t=1 for one edge but is not + // classified as t=0 for the next edge. + + // if this is not the last vertex it will be inserted + // during the next iteration. if not, the insertion + // must be done here, otherwise a vertex will be missing + // for the current polygon! + if ( polyvertlist->getNext() == NULL ) { + // determine vertex's subspace + Polygon *testpoly = ( cursubspace == FRONT_SUBSPACE ) ? frontpoly : backpoly; + // check if not already inserted as first vertex + if ( ( testpoly->getVList() != NULL ) && + ( testpoly->getVList()->getIndx() == nextvertex ) ) + continue; + // insert last vertex into its subspace + testpoly->AppendNewVIndx( nextvertex ); + } + } + + } else if ( polyvertlist->getNext() == NULL ) { + + // determine last vertex's subspace + Polygon *testpoly = ( cursubspace == FRONT_SUBSPACE ) ? frontpoly : backpoly; + // check if not already inserted as first vertex + if ( ( testpoly->getVList() != NULL ) && + ( testpoly->getVList()->getIndx() == nextvertex ) ) + continue; + // insert last vertex into its subspace + testpoly->AppendNewVIndx( nextvertex ); + } + } + + // check generated polygons for degeneration + if ( frontpoly->HasArea() ) { + // insert front poly into front subspace + frontsubspace = frontpoly; + // check back poly + if ( backpoly->HasArea() ) { + // insert back poly into back subspace + backsubspace = backpoly; + // set new id in sequence + backpoly->setId( baseobject->getNumPolygons() ); + // this poly has not been counted yet + baseobject->numpolygons++; + } else { + // remove degenerated back poly + backpoly->setNext( NULL ); + delete backpoly; + if ( display_messages & MESSAGE_SPLITTING_POLYGON ) + InfoMessage( "Split not carried out due to boundary case: polygon in front halfspace.\n" ); + } + } else { + // remove degenerated front poly + frontpoly->setNext( NULL ); + delete frontpoly; + if ( display_messages & MESSAGE_SPLITTING_POLYGON ) + InfoMessage( "Split not carried out due to boundary case: polygon in back halfspace.\n" ); + // check back poly + if ( backpoly->HasArea() ) { + // insert back poly into back subspace + backsubspace = backpoly; + } else { + // both polygons degenerated: should be impossible! + Error(); + } + } +} + + +// partition list of polygons into two halfspaces (heavily recursive!) -------- +// +BSPNode *Polygon::PartitionSpace() +{ + // display invocation message if flag set + if ( display_messages & MESSAGE_INVOCATION ) { + sprintf( str_scratchpad, "PartitionSpace() called: #%d polygon %d\n", + partition_callcount, getId() + 1 ); + InfoMessage( str_scratchpad ); + partition_callcount++; + } + + // only one polygon in this halfspace? + if ( nextpolygon == NULL ) { + if ( display_messages & MESSAGE_INVOCATION ) { + sprintf( str_scratchpad, "Leaf: polygon %d\n", getId() + 1 ); + InfoMessage( str_scratchpad ); + } + return new BSPNode( NULL, NULL, this, NULL ); + } + + // used after recursive calls: has to be automatic!! + Polygon *splitter = this; + + // take first polygon in list without testing? + if ( splitter_crit == SPLITTERCRIT_FIRST_POLY ) + goto splitter_selected; + + // find best candidate for splitter ----------------------------- + static int bestnumsplitted; + static int bestnumcontained; + bestnumsplitted = INT_MAX; + bestnumcontained = 0; + + static int samplecount; + samplecount = 0; + + static Polygon *currentsplitter; + static Polygon *precpolygon; + static Polygon *splitterpred; + currentsplitter = this; + precpolygon = NULL; + splitterpred = NULL; + + // walk polygon list trying to find appropriate splitter + for ( ; currentsplitter; precpolygon = currentsplitter, currentsplitter = currentsplitter->getNext() ) { + + if ( splitter_crit == SPLITTERCRIT_RANDOM_SAMPLE ) { + //TODO: don't use rtl rand() as pseudo random number generator + //NOTE: assumes that RAND_MAX is at least 10000 + if ( ( rand() % 10000 ) > test_probability ) + continue; + } + + static int numsplitted; + static int numcontained; + numsplitted = 0; + numcontained = 0; + + // determine number of polygons splitted and contained by *currentsplitter, respectively + static Polygon *scanpo; + for ( scanpo = this; scanpo; scanpo = scanpo->getNext() ) { + if ( scanpo != currentsplitter ) { + switch ( currentsplitter->CheckIntersection( scanpo ) ) { + case POLY_STRADDLES_SPLITTER: + numsplitted++; + break; + case POLY_IN_SAME_PLANE: + numcontained++; + break; + default: + // *currentsplitter neither splits nor contains *scanpo + break; + } + } + } + + if ( numsplitted == 0 ) { + // if nothing splitted at all, skip all other tests + splitter = currentsplitter; + splitterpred = precpolygon; + break; + } else if ( numsplitted < bestnumsplitted ) { + splitter = currentsplitter; + splitterpred = precpolygon; + bestnumsplitted = numsplitted; + bestnumcontained = numcontained; + } else if ( ( numsplitted == bestnumsplitted ) && ( numcontained > bestnumcontained ) ) { + splitter = currentsplitter; + splitterpred = precpolygon; + bestnumcontained = numcontained; + } + + // test sample size for SPLITTERCRIT_SAMPLE_FIRST_N and SPLITTERCRIT_RANDOM_SAMPLE + if ( splitter_crit & SPLITTERCRITMASK_SAMPLESIZ ) { + // desired sample size already reached? + if ( ++samplecount >= sample_size ) + break; + } + } + +splitter_selected: + + // build polygon list without splitter + static Polygon *polylist; + polylist = this; + if ( splitter == polylist ) { + polylist = splitter->getNext(); + } else { + splitterpred->setNext( splitter->getNext() ); + } + + splitter->setNext( NULL ); // unlink splitter from rest of list + splitter->setNumPolygons( 1 ); // splitter contains only itself + + // display splitter info + if ( display_messages & MESSAGE_INVOCATION ) { + sprintf( str_scratchpad, "Splitter: polygon %d\n", splitter->getId() + 1 ); + InfoMessage( str_scratchpad ); + } + + // partition space; create subspace lists ----------------------- + Polygon *frontsubspace = NULL; + Polygon *backsubspace = NULL; + Polygon *backlist = NULL; // list of backfacing polygons + + static Polygon *containlist; // append position for contained polygons + containlist = splitter; + while ( polylist != NULL ) { + + static Polygon *temppoly; + switch ( splitter->CheckIntersection( polylist ) ) { + + // polygon completely contained in front-subspace + case POLY_IN_FRONT_SUBSPACE: + temppoly = polylist->getNext(); + polylist->setNext( frontsubspace ); + frontsubspace = polylist; + polylist = temppoly; + break; + + // polygon completely contained in back-subspace + case POLY_IN_BACK_SUBSPACE: + temppoly = polylist->getNext(); + polylist->setNext( backsubspace ); + backsubspace = polylist; + polylist = temppoly; + break; + + // polygon straddles plane of splitter + case POLY_STRADDLES_SPLITTER: + // split polygon and add split pieces to the front- and back-subspace, respectively + splitter->SplitPolygon( polylist, frontsubspace, backsubspace ); + // delete split polygon + polylist = polylist->DeleteHead(); + break; + + // polygon lies in same plane as splitter + case POLY_IN_SAME_PLANE: + temppoly = polylist->getNext(); + if ( splitter->NormalDirectionSimilar( polylist ) ) { + // insert frontfacing polygon into contained list (at tail) + containlist->setNext( polylist ); + containlist = polylist; + containlist->setNext( NULL ); + containlist->setNumPolygons( 1 ); + //CAVEAT: + // numpolygons is only correct for first polygon in contained-list (splitter)!! + splitter->numpolygons++; + } else { + // insert backfacing polygon into backlist (at head) + polylist->setNext( backlist ); + polylist->setNumPolygons( backlist ? backlist->getNumPolygons() + 1 : 1 ); + backlist = polylist; + } + polylist = temppoly; + break; + } + } + + // allocate new root; partition halfspaces recursively and return root + BSPNode *front = frontsubspace ? frontsubspace->PartitionSpace() : NULL; + BSPNode *back = backsubspace ? backsubspace->PartitionSpace() : NULL; + return new BSPNode( front, back, splitter, backlist ); +} + + +// calculate plane normals for planes of all polygons ------------------------- +// +void Polygon::CalcPlaneNormals() +{ + // scan entire polygon list + FaceChunk& facelist = getFaceList(); + for ( Polygon *polyscan = this; polyscan; polyscan = polyscan->getNext() ) { + // calculate plane (and normal) if not valid yet + Face& curface = facelist[ polyscan->getFaceId() ]; + if ( !curface.PlaneValid() ) + curface.CalcPlane( polyscan->getFirstVertex(), + polyscan->getSecondVertex(), + polyscan->getThirdVertex() ); + } +} + + +// check all edges for t-vertices and insert trace-vertices as appropriate ---- +// +void Polygon::CheckEdges() +{ + //NOTE: + // this function is terribly slow, because for every polygon + // every single edge is checked whether it contains any vertices. + // thus, overall every edge is checked twice for containment + // of all vertices and no topological information is used at all! + + VertexChunk& vtxlist = getVertexList(); + + // scan all polygons + for ( Polygon *poly = this; poly; poly = poly->getNext() ) { + // just to be sure + int numvtxs = vtxlist.getNumElements(); + if ( numvtxs < 3 ) + continue; + // create vertex mask array + char *vmask = new char[ numvtxs ]; + memset( vmask, 0, sizeof( char ) * numvtxs ); + // scan all edges: init mask + VIndx *polyvertlist = poly->getVList(); + for ( ; polyvertlist; polyvertlist = polyvertlist->getNext() ) + vmask[ polyvertlist->getIndx() ] = 1; + // scan all edges: check t-junctions + polyvertlist = poly->getVList(); + for ( ; polyvertlist; polyvertlist = polyvertlist->getNext() ) { + // determine next vertex with wrap-around + int nextvertex = polyvertlist->getNext() ? + polyvertlist->getNext()->getIndx() : poly->getVList()->getIndx(); + // create directed edge + Vector3 linevec( vtxlist[ polyvertlist->getIndx() ], vtxlist[ nextvertex ] ); + // check edge against all vertices not masked out + for ( int i = 0; i < numvtxs; i++ ) + if ( vmask[ i ] == 0 ) { + LineSeg3 lineseg( vtxlist[ polyvertlist->getIndx() ], linevec ); + if ( lineseg.PointOnLineSeg( vtxlist[ i ] ) ) { + + // create new vertex-index + VIndx *tempvindx = new VIndx( i, polyvertlist->getNext() ); + polyvertlist->setNext( tempvindx ); + if ( tempvindx->getNext() == NULL ) { + + //NOTE: + // if tracevertex is inserted into last edge, AppendNewVIndx() and AppendVIndx() + // wouldn't work anymore if the insertposition in the polygon isn't + // updated correctly; normally this isn't done anyway, though + + vindxinsertpos = tempvindx; + } + + // new endpoint for lineseg to check + nextvertex = i; + vmask[ i ] = 1; + linevec.CreateDirVec( vtxlist[ polyvertlist->getIndx() ], vtxlist[ nextvertex ] ); + baseobject->numtracevertices++; + + if ( display_messages & MESSAGE_TRACEVERTEX_INSERTED ) { + sprintf( str_scratchpad, "Trace vertex inserted: polygon %d, vertex %d\n", + poly->getId() + 1, i + 1 ); + InfoMessage( str_scratchpad ); + } + } + } + } + // remove mask array + delete vmask; + } +} + + +// split polygons with vertices not contained in the same plane --------------- +// +Polygon *Polygon::CheckPlanesAndMappings() +{ + //NOTE: + // for historical reasons this function checks only quadrilaterals + // for planarity! i.e., if a polygon has more than 4 vertices no + // check is done at all whether all vertices are contained in the + // same plane. quadrilaterals, however, are checked and split into + // two triangles if nonplanar. + // explicit triangulation of quadrilaterals can be forced by using + // the static Polygon::triangulate_all flag. + + // fetch vertex and face lists + VertexChunk& vtxlist = getVertexList(); + FaceChunk& facelist = getFaceList(); + + if ( display_messages & MESSAGE_CHECKING_POLYGON_PLANES ) + InfoMessage( "\nChecking polygon planes and mappings...\n" ); + + // scan entire polygon list + Polygon *polylist = this; + for ( Polygon *polyscan = polylist; polyscan; polyscan = polyscan->getNext() ) { + + Face& curface = facelist[ polyscan->getFaceId() ]; + int vertindx1 = polyscan->getFirstVertexIndx(); + int vertindx2 = polyscan->getSecondVertexIndx(); + int vertindx3 = polyscan->getThirdVertexIndx(); + + // calculate face plane/normal if not already done + if ( !curface.PlaneValid() ) + curface.CalcPlane( vtxlist[ vertindx1 ], vtxlist[ vertindx2 ], vtxlist[ vertindx3 ] ); + + // convert correspondences to face mapping if not already done + if ( curface.FaceTexMapped() && !curface.MappingAttached() ) { + // calc correspondence number + int corrno = 0; + for ( int i = 0; i < polyscan->getFaceId(); i++ ) + if ( facelist[ i ].FaceTexMapped() ) + corrno++; + // set projective space coordinates + curface.MapXY( 0 ).InitFromVertex3( vtxlist[ vertindx1 ] ); + curface.MapXY( 1 ).InitFromVertex3( vtxlist[ vertindx2 ] ); + curface.MapXY( 2 ).InitFromVertex3( vtxlist[ vertindx3 ] ); + // set (u,v)-space coordinates + Vertex2 corrpoint; + corrpoint = baseobject->mappinglist[ corrno ].FetchMapPoint( vertindx1 ); + curface.MapUV( 0 ) = corrpoint; + corrpoint = baseobject->mappinglist[ corrno ].FetchMapPoint( vertindx2 ); + curface.MapUV( 1 ) = corrpoint; + corrpoint = baseobject->mappinglist[ corrno ].FetchMapPoint( vertindx3 ); + curface.MapUV( 2 ) = corrpoint; + } + + // check fourth vertex if face is quadrilateral + if ( polyscan->getNumVertices() == 4 ) { + + VIndx *vindxscan = polyscan->getVList()->getNext()->getNext(); // pointer to third VIndx + int testvertindx = vindxscan->getNext()->getIndx(); // fourth vertindx + if ( !curface.getPlane().PointContained( vtxlist[ testvertindx ] ) || triangulate_all ) { + + // split quadrilateral into triangles + polylist = polylist->NewPolygon(); // create second triangle + polylist->AppendNewVIndx( vertindx3 ); // append VIndx for third vertex + polylist->AppendVIndx( polyscan->UnlinkLastVIndx() ); // append existing VIndx for fourth vertex + polylist->AppendNewVIndx( vertindx1 ); // append VIndx for first vertex + + if ( display_messages & MESSAGE_SPLITTING_QUADRILATERAL ) { + sprintf( str_scratchpad, "Splitting quadrilateral: polygon %d\n", + polyscan->getId() + 1 ); + InfoMessage( str_scratchpad ); + sprintf( str_scratchpad, "-->Creating new triangle: polygon %d\n", + polylist->getId() + 1 ); + InfoMessage( str_scratchpad ); + } + // update count of split quadrilaterals + baseobject->numsplitquadrilaterals++; + // create new face + int newfaceno = facelist.AddElement( curface ); + Face& newface = facelist[ newfaceno ]; + // update face id of new polygon + polylist->setFaceId( newfaceno ); + // fetch first three vertices + vertindx1 = polylist->getFirstVertexIndx(); + vertindx2 = polylist->getSecondVertexIndx(); + vertindx3 = polylist->getThirdVertexIndx(); + // calculate face normal + newface.CalcPlane( vtxlist[ vertindx1 ], vtxlist[ vertindx2 ], vtxlist[ vertindx3 ] ); + // transfer mapping into face + if ( curface.FaceTexMapped() ) { + // calc correspondence number + int corrno = 0; + for ( int i = 0; i < polyscan->getFaceId(); i++ ) + if( facelist[ i ].FaceTexMapped() ) + corrno++; + // set projective space coordinates + newface.MapXY( 0 ).InitFromVertex3( vtxlist[ vertindx1 ] ); + newface.MapXY( 1 ).InitFromVertex3( vtxlist[ vertindx2 ] ); + newface.MapXY( 2 ).InitFromVertex3( vtxlist[ vertindx3 ] ); + // set (u,v)-space coordinates + Vertex2 corrpoint; + corrpoint = baseobject->mappinglist[ corrno ].FetchMapPoint( vertindx1 ); + newface.MapUV( 0 ) = corrpoint; + corrpoint = baseobject->mappinglist[ corrno ].FetchMapPoint( vertindx2 ); + newface.MapUV( 1 ) = corrpoint; + corrpoint = baseobject->mappinglist[ corrno ].FetchMapPoint( vertindx3 ); + newface.MapUV( 2 ) = corrpoint; + } + } + } + } + + return polylist; +} + + +// calculate probability with which to test a single polygon ------------------ +// +int Polygon::CalcSplitterTestProbability() +{ + double numerator = sample_size; + double denominator = numpolygons; + double prob = ( denominator > 0.0 ) ? numerator / denominator : 1.0; + prob = ( prob < 1.0 ) ? prob * 10000.0 : 10000.0; + test_probability = (int) floor( prob + 0.5 ); + if ( test_probability < 1 ) test_probability = 1; + return ( numpolygons > 0 ); +} + + +// unspecified error encountered ---------------------------------------------- +// +void Polygon::Error() const +{ + ErrorMessage( "\n***ERROR*** in object of class BspLib::Polygon." ); + HandleCriticalError(); +} + + +// splitter selection --------------------------------------------------------- +// +int Polygon::splitter_crit = Polygon::SPLITTERCRIT_SAMPLE_ALL; +int Polygon::sample_size = 20; +int Polygon::test_probability = 10000; // means 100.00% + + +// static flags --------------------------------------------------------------- +// +int Polygon::triangulate_all = FALSE; +int Polygon::normalize_vectors = FALSE; +int Polygon::display_messages = Polygon::MESSAGEMASK_DISPLAY_ALL; + + +// counter for invocations of PartitionSpace() -------------------------------- +// +int Polygon::partition_callcount = 0; + + +// string scratch pad --------------------------------------------------------- +// +char Polygon::str_scratchpad[ 256 ] = ""; + + +BSPLIB_NAMESPACE_END + +//----------------------------------------------------------------------------- |