From c068f22329d5cc722622a2183bbb22eef2093df7 Mon Sep 17 00:00:00 2001 From: Felix Morgner Date: Mon, 24 Aug 2026 11:16:07 +0200 Subject: initial import --- tool_src/BspLib/BoundingBox.cpp | 223 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 223 insertions(+) create mode 100644 tool_src/BspLib/BoundingBox.cpp (limited to 'tool_src/BspLib/BoundingBox.cpp') diff --git a/tool_src/BspLib/BoundingBox.cpp b/tool_src/BspLib/BoundingBox.cpp new file mode 100644 index 0000000..04008c2 --- /dev/null +++ b/tool_src/BspLib/BoundingBox.cpp @@ -0,0 +1,223 @@ +//----------------------------------------------------------------------------- +// BSPLIB MODULE: BoundingBox.cpp +// +// Copyright (c) 1997-1998 by Markus Hadwiger +// All Rights Reserved. +//----------------------------------------------------------------------------- + +// bsplib headers +#include "BoundingBox.h" +#include "ObjectBSPNode.h" +#include "Plane.h" + + +BSPLIB_NAMESPACE_BEGIN + + +// apply scale factor to bounding box ----------------------------------------- +// +void BoundingBox::ApplyScaleFactor( double sfac ) +{ + //NOTE: + // this will be needed if the attached object is scaled. + // the scale factor is applied to the space containing the + // bounding box, i.e. its midpoint will move. + + minvertex.setX( minvertex.getX() * sfac ); + minvertex.setY( minvertex.getY() * sfac ); + minvertex.setZ( minvertex.getZ() * sfac ); + + maxvertex.setX( maxvertex.getX() * sfac ); + maxvertex.setY( maxvertex.getY() * sfac ); + maxvertex.setZ( maxvertex.getZ() * sfac ); +} + + +// grow this bounding box by another one (maximum/minimum merge) -------------- +// +void BoundingBox::GrowBoundingBox( BoundingBox *otherbox ) +{ + if ( otherbox != NULL ) { + if ( otherbox->minvertex.getX() < minvertex.getX() ) + minvertex.setX( otherbox->minvertex.getX() ); + if ( otherbox->minvertex.getY() < minvertex.getY() ) + minvertex.setY( otherbox->minvertex.getY() ); + if ( otherbox->minvertex.getZ() < minvertex.getZ() ) + minvertex.setZ( otherbox->minvertex.getZ() ); + + if ( otherbox->maxvertex.getX() > maxvertex.getX() ) + maxvertex.setX( otherbox->maxvertex.getX() ); + if ( otherbox->maxvertex.getY() > maxvertex.getY() ) + maxvertex.setY( otherbox->maxvertex.getY() ); + if ( otherbox->maxvertex.getZ() > maxvertex.getZ() ) + maxvertex.setZ( otherbox->maxvertex.getZ() ); + } +} + + +// fill in bounding box as union of entire list ------------------------------- +// +void BoundingBox::BoundingBoxListUnion( BoundingBox& unionbox ) +{ + // init union box + delete unionbox.nextbox; + unionbox.nextbox = NULL; + unionbox.containedobject = NULL; + unionbox.minvertex = minvertex; + unionbox.maxvertex = maxvertex; + + // build union of entire list + for ( BoundingBox *curbox = nextbox; curbox; curbox = curbox->nextbox ) + unionbox.GrowBoundingBox( curbox ); +} + + +// partition list of bounding boxing boxes and build tree structure ----------- +// +ObjectBSPNode *BoundingBox::PartitionSpace() +{ + //NOTE: + // this function alters the link fields of the objects attached + // to bounding boxes. therefore, the original linked list of + // objects is invalid after this function! the objects themselves + // are only accessible via tree nodes afterwards. + + //NOTE: + // analogously to polygon bsp trees where the polygon list is dissolved + // in the process of bsp compilation, the list of bounding boxes is + // completely dissolved by this function! that is, the bounding box + // for which PartitionSpace() has been invoked should not be accessed + // directly anymore. all bounding boxes can then be accessed via the + // generated object-bsp-tree! + + // only one box in this subspace? + if ( nextbox == NULL ) { + // unlink tail of object list + containedobject->next = NULL; + // create ObjectBSPNode for this box (leaf!) + return new ObjectBSPNode( NULL, NULL, NULL, this ); + } + + // select a separating plane + Vector3 separatornormal( 1.0, 0.0, 0.0 ); + double separatoroffset = maxvertex.getX(); + int currentboundary = 0; + Plane *separator = new Plane( separatornormal, separatoroffset ); + BoundingBox *currentbox = this; + // scan all bounding boxes to find a suitable separating plane + for ( currentbox = this; ; ) { + + // check if plane separates bounding boxes cleanly + int cleanseparation = 1; + int membersofpos = 0; + int membersofneg = 0; + for ( BoundingBox *scan = this; scan; scan = scan->getNext() ) { + if ( !separator->PointInNegativeHalfspace( scan->getMinVertex() ) && + !separator->PointInNegativeHalfspace( scan->getMaxVertex() ) ) { + membersofpos++; + } else if ( !separator->PointInPositiveHalfspace( scan->getMinVertex() ) && + !separator->PointInPositiveHalfspace( scan->getMaxVertex() ) ) { + membersofneg++; + } else { + cleanseparation = 0; + break; + } + } + //NOTE: + // both halfspaces have to contain bounding boxes; separation of vacant + // space from inhabited space just makes the tree unnecessarily large. + // this does not influence if there is a clean separating plane or not! + if ( ( membersofpos > 0 ) && ( membersofneg > 0 ) && cleanseparation ) + break; + + // try next boundary plane + currentboundary = ( currentboundary + 1 ) % 6; + if ( currentboundary == 0 ) + currentbox = currentbox->getNext(); + + if ( currentbox != NULL ) { + switch ( currentboundary ) { + case 0: + separatornormal = Vector3( 1.0, 0.0, 0.0 ); + separatoroffset = currentbox->maxvertex.getX(); + break; + case 1: + separatornormal = Vector3( 0.0, 1.0, 0.0 ); + separatoroffset = currentbox->maxvertex.getY(); + break; + case 2: + separatornormal = Vector3( 0.0, 0.0, 1.0 ); + separatoroffset = currentbox->maxvertex.getZ(); + break; + case 3: + separatornormal = Vector3( -1.0, 0.0, 0.0 ); + separatoroffset = -currentbox->minvertex.getX(); + break; + case 4: + separatornormal = Vector3( 0.0, -1.0, 0.0 ); + separatoroffset = -currentbox->minvertex.getY(); + break; + case 5: + separatornormal = Vector3( 0.0, 0.0, -1.0 ); + separatoroffset = -currentbox->minvertex.getZ(); + break; + } + separator->setPlaneNormal( separatornormal ); + separator->setPlaneOffset( separatoroffset ); + } else { + break; + } + } + + BoundingBox *frontsubspace = NULL; + BoundingBox *backsubspace = NULL; + + if ( currentbox != NULL ) { + // partition space into two halfspaces (walk list of bounding boxes) + for ( currentbox = this; currentbox; ) { + if ( !separator->PointInNegativeHalfspace( currentbox->getMinVertex() ) && + !separator->PointInNegativeHalfspace( currentbox->getMaxVertex() ) ) { + // box contained in positive halfspace + BoundingBox *tmpbox = currentbox->getNext(); + currentbox->nextbox = frontsubspace; + frontsubspace = currentbox; + currentbox = tmpbox; + } else { + // box contained in negative halfspace + BoundingBox *tmpbox = currentbox->getNext(); + currentbox->nextbox = backsubspace; + backsubspace = currentbox; + currentbox = tmpbox; + } + } + } else { + // no suitable separating plane found: create list of unseparable objects + for ( currentbox = this; currentbox; currentbox = currentbox->getNext() ) { + currentbox->containedobject->next = + currentbox->getNext() ? currentbox->getNext()->containedobject : NULL; + } + // delete legacy bounding boxes + delete nextbox; + nextbox = NULL; + // create ObjectBSPNode for this box (leaf!) + return new ObjectBSPNode( NULL, NULL, NULL, this ); + + //NOTE: + // if bounding boxes cannot be separated cleanly, their corresponding objects + // are inserted into a linear list attached to a single bounding box. this + // bounding box, however, encompasses only the head of this list! + // for bsp compilation, the objects in these lists have to be explicitly merged + // into a single object. this is not done automatically! + // currently, only ObjectBSPNode::CreateObjectList() merges these objects. + } + + // allocate new root; partition halfspaces recursively and return root + ObjectBSPNode *front = frontsubspace ? frontsubspace->PartitionSpace() : NULL; + ObjectBSPNode *back = backsubspace ? backsubspace->PartitionSpace() : NULL; + return new ObjectBSPNode( front, back, separator, NULL ); +} + + +BSPLIB_NAMESPACE_END + +//----------------------------------------------------------------------------- -- cgit v1.2.3