diff options
Diffstat (limited to 'tool_src/BspLib/BSPNode.cpp')
| -rw-r--r-- | tool_src/BspLib/BSPNode.cpp | 401 |
1 files changed, 401 insertions, 0 deletions
diff --git a/tool_src/BspLib/BSPNode.cpp b/tool_src/BspLib/BSPNode.cpp new file mode 100644 index 0000000..4edd283 --- /dev/null +++ b/tool_src/BspLib/BSPNode.cpp @@ -0,0 +1,401 @@ +//----------------------------------------------------------------------------- +// BSPLIB MODULE: BSPNode.cpp +// +// Copyright (c) 1996-1998 by Markus Hadwiger +// All Rights Reserved. +//----------------------------------------------------------------------------- + +// bsplib header files +#include "BSPNode.h" +#include "BoundingBox.h" +#include "BspFormat.h" + + +BSPLIB_NAMESPACE_BEGIN + + +// construct BSPNode ---------------------------------------------------------- +// +BSPNode::BSPNode( BSPNode *front, BSPNode *back, Polygon *poly, Polygon *backpoly, Plane *sep, BoundingBox *box, int num ) +{ + frontsubtree = front; + backsubtree = back; + polygon = poly; + backpolygon = backpoly; + separatorplane = sep; + boundingbox = box; + nodenumber = num; +} + + +// destroy BSPNode ------------------------------------------------------------ +// +BSPNode::~BSPNode() +{ + delete polygon; + delete backpolygon; + delete separatorplane; + delete boundingbox; + delete frontsubtree; + delete backsubtree; +} + + +// traverse bsp tree (preorder) and number nodes as encountered --------------- +// +void BSPNode::NumberBSPNodes( int& curno ) +{ + // store nodenumber + nodenumber = ++curno; + + // assign node numbers to all polygons contained in splitter plane + static Polygon *polylist; + for ( polylist = polygon ? polygon->getNext() : NULL; polylist; polylist = polylist->getNext() ) { + // only increment numbering, numbers don't get stored in polygons! + ++curno; + } + for ( polylist = backpolygon; polylist; polylist = polylist->getNext() ) { + // only increment numbering, numbers don't get stored in polygons! + ++curno; + } + + // do numbering recursively for front- and backsubtree + if ( frontsubtree ) frontsubtree->NumberBSPNodes( curno ); + if ( backsubtree ) backsubtree->NumberBSPNodes( curno ); +} + + +// sum number of vertices of all polygon in tree ------------------------------ +// +void BSPNode::SumVertexNums( int& vtxnum ) +{ + // sum number of vertices of polygons contained in this plane + static Polygon *polylist; + for ( polylist = polygon; polylist; polylist = polylist->getNext() ) + vtxnum += polylist->getNumVertices(); + for ( polylist = backpolygon; polylist; polylist = polylist->getNext() ) + vtxnum += polylist->getNumVertices(); + + // do sum recursively for front- and backsubtree + if ( frontsubtree ) frontsubtree->SumVertexNums( vtxnum ); + if ( backsubtree ) backsubtree->SumVertexNums( vtxnum ); +} + + +// traverse entire tree and correct relative polygon info to new base values -- +// +void BSPNode::CorrectPolygonBases( BspObject *newbaseobj, int vertexindxbase, int faceidbase, int polygonidbase ) +{ + static Polygon *polylist; + for ( polylist = polygon; polylist; polylist = polylist->getNext() ) + polylist->CorrectBase( newbaseobj, vertexindxbase, faceidbase, polygonidbase ); + for ( polylist = backpolygon; polylist; polylist = polylist->getNext() ) + polylist->CorrectBase( newbaseobj, vertexindxbase, faceidbase, polygonidbase ); + + if ( frontsubtree ) frontsubtree->CorrectPolygonBases( newbaseobj, vertexindxbase, faceidbase, polygonidbase ); + if ( backsubtree ) backsubtree->CorrectPolygonBases( newbaseobj, vertexindxbase, faceidbase, polygonidbase ); +} + + +// traverse entire tree and correct relative polygon info to new base values -- +// +void BSPNode::CorrectPolygonBasesByTable( BspObject *newbaseobj, int *vtxindxmap, int faceidbase, int polygonidbase ) +{ + static Polygon *polylist; + for ( polylist = polygon; polylist; polylist = polylist->getNext() ) + polylist->CorrectBaseByTable( newbaseobj, vtxindxmap, faceidbase, polygonidbase ); + for ( polylist = backpolygon; polylist; polylist = polylist->getNext() ) + polylist->CorrectBaseByTable( newbaseobj, vtxindxmap, faceidbase, polygonidbase ); + + if ( frontsubtree ) frontsubtree->CorrectPolygonBasesByTable( newbaseobj, vtxindxmap, faceidbase, polygonidbase ); + if ( backsubtree ) backsubtree->CorrectPolygonBasesByTable( newbaseobj, vtxindxmap, faceidbase, polygonidbase ); +} + + +// write bsp tree structure to output file (preorder traversal) --------------- +// +void BSPNode::WriteBSPTree( FILE *fp ) +{ + static int lnodnum, rnodnum, cnodnum, bnodnum; + static int curnodnum; + static Polygon *polylist; + + lnodnum = frontsubtree ? frontsubtree->nodenumber : 0; + rnodnum = backsubtree ? backsubtree->nodenumber : 0; + + if ( polygon != NULL ) { + cnodnum = polygon->getNext() ? nodenumber + 1 : 0; + bnodnum = backpolygon ? nodenumber + polygon->getNumPolygons() : 0; + } else { + cnodnum = 0; + bnodnum = 0; + } + + if ( outputformat == OUTPUT_OLD_STYLE ) { + + if ( polygon != NULL ) { + // print head node + fprintf( fp, "%d: %d |%d|%d|%d-%d|\n", + nodenumber, polygon->getId() + 1, cnodnum, bnodnum, lnodnum, rnodnum ); + + // print list of contained nodes (frontfacing) + curnodnum = cnodnum; + polylist = polygon; + while ( ( polylist = polylist->getNext() ) != NULL ) { + cnodnum = polylist->getNext() ? ( curnodnum + 1 ) : 0; + fprintf( fp, "%d: %d |%d|0|\n", curnodnum++, polylist->getId() + 1, cnodnum ); + } + + // print list of contained nodes (backfacing) + curnodnum = bnodnum; + for ( polylist = backpolygon; polylist; polylist = polylist->getNext() ) { + bnodnum = polylist->getNext() ? ( curnodnum + 1 ) : 0; + fprintf( fp, "%d: %d |0|%d|\n", curnodnum++, polylist->getId() + 1, bnodnum ); + } + } else { + //NOTE: + // nodes not containing polygons are not supported + // by the old ouput format! + fprintf( fp, "no polygon contained in node %d.", nodenumber ); + } + + } else { + + // print head node + fprintf( fp, "%d: ", nodenumber ); + if ( polygon != NULL ) + fprintf( fp, "%s %d ", BspFormat::_bspspec_polygon_str, polygon->getId() + 1 ); + if ( cnodnum != 0 ) + fprintf( fp, "%s %d ", BspFormat::_bspspec_frontlist_str, cnodnum ); + if ( bnodnum != 0 ) + fprintf( fp, "%s %d ", BspFormat::_bspspec_backlist_str, bnodnum ); + if ( lnodnum != 0 ) + fprintf( fp, "%s %d ", BspFormat::_bspspec_fronttree_str, lnodnum ); + if ( rnodnum != 0 ) + fprintf( fp, "%s %d ", BspFormat::_bspspec_backtree_str, rnodnum ); + if ( separatorplane != NULL ) { + Vector3 normal = separatorplane->getPlaneNormal(); + fprintf( fp, "%s %f %f %f %f ", BspFormat::_bspspec_plane_str, + normal.getX(), normal.getY(), normal.getZ(), + separatorplane->getPlaneOffset() ); + } + if ( boundingbox != NULL ) { + Vertex3 minvert = boundingbox->getMinVertex(); + Vertex3 maxvert = boundingbox->getMaxVertex(); + fprintf( fp, "%s %f %f %f %f %f %f ", BspFormat::_bspspec_boundingbox_str, + minvert.getX(), minvert.getY(), minvert.getZ(), + maxvert.getX(), maxvert.getY(), maxvert.getZ() ); + } + fprintf( fp, "\n" ); + + // print list of contained nodes (frontfacing) + if ( polygon != NULL ) { + curnodnum = cnodnum; + polylist = polygon; + while ( ( polylist = polylist->getNext() ) != NULL ) { + fprintf( fp, "%d: ", curnodnum ); + cnodnum = polylist->getNext() ? ++curnodnum : 0; + fprintf( fp, "%s %d ", BspFormat::_bspspec_polygon_str, polylist->getId() + 1 ); + if ( cnodnum != 0 ) + fprintf( fp, "%s %d", BspFormat::_bspspec_frontlist_str, cnodnum ); + fprintf( fp, "\n" ); + } + } + + // print list of contained nodes (backfacing) + curnodnum = bnodnum; + for ( polylist = backpolygon; polylist; polylist = polylist->getNext() ) { + fprintf( fp, "%d: ", curnodnum ); + bnodnum = polylist->getNext() ? ++curnodnum : 0; + fprintf( fp, "%s %d ", BspFormat::_bspspec_polygon_str, polylist->getId() + 1 ); + if ( bnodnum != 0 ) + fprintf( fp, "%s %d", BspFormat::_bspspec_backlist_str, bnodnum ); + fprintf( fp, "\n" ); + } + + } + + // write out front- and backsubtree recursively + if ( frontsubtree ) frontsubtree->WriteBSPTree( fp ); + if ( backsubtree ) backsubtree->WriteBSPTree( fp ); +} + + +// fetch pointer to polygon with given number contained in bsp tree ----------- +// +Polygon *BSPNode::FetchBSPPolygon( int polyno ) +{ + // search local node and contained list (frontfacing) + static Polygon *clist; + for ( clist = polygon; clist; clist = clist->getNext() ) { + if ( clist->getId() == polyno ) + return clist; + } + + // search list of contained backfacing polygons + for ( clist = backpolygon; clist; clist = clist->getNext() ) { + if ( clist->getId() == polyno ) + return clist; + } + + Polygon *search = NULL; + + if ( frontsubtree ) + search = frontsubtree->FetchBSPPolygon( polyno ); + if ( ( search == NULL ) && backsubtree ) + search = backsubtree->FetchBSPPolygon( polyno ); + + return search; +} + + +// fetch all polygon numbers contained in specific face ----------------------- +// +void BSPNode::FetchFacePolygons( int faceno, PolygonList& facepolylist ) +{ + // search local node and contained list (frontfacing) + static Polygon *clist; + for ( clist = polygon; clist; clist = clist->getNext() ) { + if ( clist->getFaceId() == faceno ) + facepolylist.InsertPolygon( new Polygon( NULL, clist->getId(), clist->getFaceId() ) ); + } + + // search list of contained backfacing polygons + for ( clist = backpolygon; clist; clist = clist->getNext() ) { + if ( clist->getFaceId() == faceno ) + facepolylist.InsertPolygon( new Polygon( NULL, clist->getId(), clist->getFaceId() ) ); + } + + // check children (subtrees) + if ( frontsubtree ) frontsubtree->FetchFacePolygons( faceno, facepolylist ); + if ( backsubtree ) backsubtree->FetchFacePolygons( faceno, facepolylist ); +} + + +// check edges for contained vertices and insert them as trace vertices ------- +// +void BSPNode::CheckEdges() +{ + // check list of frontfacing polygons + if ( polygon ) polygon->CheckEdges(); + + // check list of backfacing polygons + if ( backpolygon ) backpolygon->CheckEdges(); + + // check children (subtrees) + if ( frontsubtree ) frontsubtree->CheckEdges(); + if ( backsubtree ) backsubtree->CheckEdges(); +} + + +// grow this node's bounding box by another node's ---------------------------- +// +void BSPNode::GrowBoundingBox( BSPNode *othernode ) +{ + if ( othernode != NULL ) { + // ensure other node has a bounding box (calculate if not) + if ( othernode->boundingbox == NULL ) + othernode->CalcBoundingBoxes(); + static BoundingBox *otherbox; + otherbox = othernode->boundingbox; + + if ( boundingbox == NULL ) { + // if this node has no bounding box copy other node's + boundingbox = new BoundingBox( otherbox->getMinVertex(), otherbox->getMaxVertex() ); + } else { + // merge the two bounding boxes + boundingbox->GrowBoundingBox( otherbox ); + } + } +} + + +// calculate axial bounding box for this node and all children ---------------- +// +void BSPNode::CalcBoundingBoxes() +{ + if ( boundingbox == NULL ) { + + // if polygon(s) contained in this node calculate their bounding box + if ( polygon != NULL ) { + polygon->CalcBoundingBox( boundingbox ); + if ( backpolygon != NULL ) { + static BoundingBox *backbox; + backpolygon->CalcBoundingBox( backbox ); + boundingbox->GrowBoundingBox( backbox ); + delete backbox; + } + } + + // grow local bounding box by children's + GrowBoundingBox( frontsubtree ); + GrowBoundingBox( backsubtree ); + } +} + + +// calculate separator planes from polygons for entire bsp tree --------------- +// +void BSPNode::CalcSeparatorPlanes() +{ + if ( ( separatorplane == NULL ) && ( polygon != NULL ) ) { + separatorplane = new Plane( polygon->getFirstVertex(), + polygon->getSecondVertex(), + polygon->getThirdVertex() ); + } + + // check children (subtrees) + if ( frontsubtree ) frontsubtree->CalcSeparatorPlanes(); + if ( backsubtree ) backsubtree->CalcSeparatorPlanes(); +} + + +// format to use when writing bsp nodes to files ------------------------------ +// +int BSPNode::outputformat = BSPNode::OUTPUT_KEY_VALUE_STYLE; + + +// construct BSPNodeFlat ------------------------------------------------------ +// +BSPNodeFlat::BSPNodeFlat( int front, int back, Polygon *poly, int clist, int blist, Plane *sep, BoundingBox *box, int num ) +{ + frontsubtreeindx = front; + backsubtreeindx = back; + polygon = poly; + containedlistindx = clist; + backlistindx = blist; + separatorplane = sep; + boundingbox = box; + nodenumber = num; +} + + +// init BSPNodeFlat members --------------------------------------------------- +// +void BSPNodeFlat::InitNode( int front, int back, Polygon *poly, int clist, int blist, Plane *sep, BoundingBox *box, int num ) +{ + frontsubtreeindx = front; + backsubtreeindx = back; + polygon = poly; + containedlistindx = clist; + backlistindx = blist; + separatorplane = sep; + boundingbox = box; + nodenumber = num; +} + + +// apply scale factor to separator plane and bounding box if attached --------- +// +void BSPNodeFlat::ApplyScaleFactor( double sfac ) +{ + if ( separatorplane != NULL ) + separatorplane->ApplyScaleFactor( sfac ); + if ( boundingbox != NULL ) + boundingbox->ApplyScaleFactor( sfac ); +} + + +BSPLIB_NAMESPACE_END + +//----------------------------------------------------------------------------- |