1 files changed, 223 insertions, 0 deletions
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
+
+//-----------------------------------------------------------------------------