vwemirror/TeslaRel410
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
TeslaRel410/CODE/RP/MUNGA/BOXTREE.CPP
T
CydandClaude Fable 5 fdd9ac9d97 Initial import: Tesla Release 4.10 (Tesla:BattleTech & Tesla:Red Planet) 
Archival snapshot of the Virtual World Entertainment Tesla cockpit
software, 1994-1996: MUNGA engine and L4 pod layer source (Borland
C++ 5.0), BT/RP game code, and game content (models, audio, maps,
gauges, Division renderer data). Includes third-party libraries:
Division dVS/DPL graphics, HMI SOS audio, WATTCP networking.

Files are preserved byte-for-byte (.gitattributes disables all
line-ending conversion). README.md documents the layout, target
hardware, and toolchain.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
2026-07-02 13:21:58 -05:00

1366 lines
37 KiB
C++
Raw Permalink Blame History

//===========================================================================//
// File: boxtree.cc //
// Project: MUNGA Brick: Spatializer Library //
// Contents: Implementation details of bounding-box based spatialization //
//---------------------------------------------------------------------------//
// Date Who Modification //
// -------- --- ---------------------------------------------------------- //
// 01/08/95 JMA Initial port back to C++ //
//---------------------------------------------------------------------------//
// Copyright (C) 1993-1995, Virtual World Entertainment, Inc. //
// All Rights reserved worldwide //
// This unpublished sourcecode is PROPRIETARY and CONFIDENTIAL //
//===========================================================================//
#include <munga.hpp>
#pragma hdrstop
#if !defined(BOXTREE_HPP)
# include <boxtree.hpp>
#endif
#if !defined(POINT3D_HPP)
# include <point3d.hpp>
#endif
#if !defined(LINE_HPP)
# include <line.hpp>
#endif
//#############################################################################
//######################### BoundingBoxTreeNode #########################
//#############################################################################
MemoryBlock
BoundingBoxTreeNode::AllocatedMemory(
sizeof(BoundingBoxTreeNode),
500,
50,
"BoundingBoxTree Nodes"
);
int
BoundingBoxTreeNode::TraversalOrder[6]={4,5,0,1,2,3};
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
void
BoundingBoxTreeNode::SetTraversalOrder(
int first,
int second,
int third
)
{
Verify((unsigned)first <= Z_Axis && first != second);
Verify((unsigned)second <= Z_Axis && second != third);
Verify((unsigned)third <= Z_Axis && third != first);
TraversalOrder[0] = first << 1;
TraversalOrder[1] = TraversalOrder[0] + 1;
TraversalOrder[2] = second << 1;
TraversalOrder[3] = TraversalOrder[2] + 1;
TraversalOrder[4] = third << 1;
TraversalOrder[5] = TraversalOrder[4] + 1;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
BoundingBoxTreeNode::BoundingBoxTreeNode(
BoundingBox *volume,
const ExtentBox &extents
)
{
Check_Pointer(this);
Check(&extents);
nodeExtents = extents;
staticContents = volume;
innerNode = NULL;
for (int i=0; i<ELEMENTS(nodeBranches); ++i)
{
nodeBranches[i] = NULL;
}
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
BoundingBoxTreeNode::~BoundingBoxTreeNode()
{
Check(this);
//
//----------------------------
// Delete our extent subspaces
//----------------------------
//
for (int i=0; i<ELEMENTS(nodeBranches); ++i)
{
if (nodeBranches[i])
{
Unregister_Object(nodeBranches[i]);
delete nodeBranches[i];
}
}
//
//---------------------------------------
// Delete the inner subspace if it exists
//---------------------------------------
//
if (innerNode)
{
Unregister_Object(innerNode);
delete innerNode;
}
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
void
BoundingBoxTreeNode::Add(
BoundingBox *volume,
const ExtentBox &extents
)
{
Check(this);
Check(volume);
Check(&extents);
//
//---------------------------------------------------
// Make our copy of the new box for clipping purposes
//---------------------------------------------------
//
ExtentBox clipped_box(extents);
//
//------------------------------------------------------------------------
// Check along each of the six faces, separately clipping off elements of
// the new box which do not lie within this voxel
//------------------------------------------------------------------------
//
for (int i=0; i<6; ++i)
{
int
is_clipped;
Scalar
save;
//
//------------------------------------------------------------------
// Handle testing the maximum value side of the box. Make sure that
// volumes actually extend into the current voxel before they are
// clipped, preventing insertion of zero-thickness voxels
//------------------------------------------------------------------
//
int face = TraversalOrder[i];
int opp_face = face^1;
if (face&1)
{
if (clipped_box[face] > nodeExtents[face])
{
is_clipped = clipped_box[opp_face] < nodeExtents[face];
}
else
{
continue;
}
}
//
//-------------------------------------------------
// Handle testing the minimum value side of the box
//-------------------------------------------------
//
else
{
if (clipped_box[face] < nodeExtents[face])
{
is_clipped = clipped_box[opp_face] > nodeExtents[face];
}
else
{
continue;
}
}
//
//---------------------------------------------------------------------
// If the new box is to be clipped, save the old value for the opposite
// face and replace it with this space's bounding face
//---------------------------------------------------------------------
//
if (is_clipped)
{
save = clipped_box[opp_face];
clipped_box[opp_face] = nodeExtents[face];
}
//
//-----------------------------------------------------------------------
// Make sure that we are not registering an empty slice of the new volume
//-----------------------------------------------------------------------
//
if (volume->IntersectsBounded(clipped_box))
{
//
//--------------------------------------------------------------------
// If no spaces have been defined within the facing voxel, construct
// a new one out of the clipped box, otherwise call this routine again
// with the given voxel and the clipped box
//--------------------------------------------------------------------
//
if (!nodeBranches[face])
{
nodeBranches[face] =
new BoundingBoxTreeNode(volume, clipped_box);
Register_Object(nodeBranches[face]);
}
else
{
Check(nodeBranches[face]);
nodeBranches[face]->Add(volume, clipped_box);
}
}
//
//---------------------------------------------------------------------
// If no clipping was necessary for this voxel, then no portion of
// the box remains to be tested, so abort the loop. Otherwise, restore
// the opposing face of the new box, and clip the newly created
// voxel out of the new box
//---------------------------------------------------------------------
//
if (!is_clipped)
return;
clipped_box[opp_face] = save;
clipped_box[face] = nodeExtents[face];
}
//-----------------------------------------------------------------------
// Make sure that we are not registering an empty slice of the new volume
//-----------------------------------------------------------------------
//
if (volume->IntersectsBounded(clipped_box))
{
//
//----------------------------------------------------------------------
// The remaining portion of the box is inside our current space, so link
// it there
//----------------------------------------------------------------------
//
if (!innerNode)
{
innerNode = new BoundingBoxTreeNode(volume, clipped_box);
Register_Object(innerNode);
}
else
{
Check(innerNode);
innerNode->Add(volume, clipped_box);
}
}
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
void
BoundingBoxTreeNode::Remove(
BoundingBox *volume,
const ExtentBox &extents
)
{
Check(this);
Check(volume);
Check(&extents);
//
//----------------------------------------------------------------------
// If this node contains the desired volume, immediately NULL it out and
// return
//----------------------------------------------------------------------
//
if (staticContents == volume)
{
staticContents = NULL;
return;
}
//
//---------------------------------------------------
// Make our copy of the new box for clipping purposes
//---------------------------------------------------
//
ExtentBox clipped_box(extents);
//
//------------------------------------------------------------------------
// Check along each of the six faces, separately clipping off elements of
// the new box which do not lie within this voxel
//------------------------------------------------------------------------
//
for (int i=0; i<6; ++i)
{
int
is_clipped;
Scalar
save;
//
//------------------------------------------------------------------
// Handle testing the maximum value side of the box. Make sure that
// volumes actually extend into the current voxel before they are
// clipped, preventing insertion of zero-thickness voxels
//------------------------------------------------------------------
//
int face = TraversalOrder[i];
int opp_face = face^1;
if (face&1)
{
if (clipped_box[face] > nodeExtents[face])
{
is_clipped = clipped_box[opp_face] < nodeExtents[face];
}
else
{
continue;
}
}
//
//-------------------------------------------------
// Handle testing the minimum value side of the box
//-------------------------------------------------
//
else
{
if (clipped_box[face] < nodeExtents[face])
{
is_clipped = clipped_box[opp_face] > nodeExtents[face];
}
else
{
continue;
}
}
//
//---------------------------------------------------------------------
// If the new box is to be clipped, save the old value for the opposite
// face and replace it with this space's bounding face
//---------------------------------------------------------------------
//
if (is_clipped)
{
save = clipped_box[opp_face];
clipped_box[opp_face] = nodeExtents[face];
}
//
//---------------------------------------------------------------------
// Because the volume has already been added, branches must exist along
// all faces it gets clipped by unless it was an empty slice
//---------------------------------------------------------------------
//
if (volume->IntersectsBounded(clipped_box))
{
Check(nodeBranches[face]);
nodeBranches[face]->Remove(volume, clipped_box);
}
//
//---------------------------------------------------------------------
// If no clipping was necessary for this voxel, then no portion of
// the box remains to be tested, so abort the loop. Otherwise, restore
// the opposing face of the new box, and clip the newly created
// voxel out of the new box
//---------------------------------------------------------------------
//
if (!is_clipped)
return;
clipped_box[opp_face] = save;
clipped_box[face] = nodeExtents[face];
}
//
//--------------------------------------------------------------------------
// If we are not dealing with an empty slice of the volume, the remaining
// slice of the extents must have been entered as internal subspacing
//--------------------------------------------------------------------------
//
if (volume->IntersectsBounded(clipped_box))
{
Check(innerNode);
innerNode->Remove(volume, clipped_box);
}
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
BoundingBoxTreeNode*
BoundingBoxTreeNode::FindSmallestNodeContaining(
const ExtentBox &extents,
BoundingBoxTreeNode *parent
)
{
Check(&extents);
//
//------------------------------------------------------------------------
// Check along each of the six faces to see if this volume cuts any of the
// planes of the node,
//------------------------------------------------------------------------
//
BoundingBoxTreeNode *branch = this;
Check_Node:
Check(branch);
for (int i=0; i<6; ++i)
{
//
//-------------------------------------------------
// Handle testing the maximum value side of the box
//-------------------------------------------------
//
int face = TraversalOrder[i];
int opp_face = face^1;
if (face&1)
{
if (extents[face] > branch->nodeExtents[face])
{
if (extents[opp_face] <= branch->nodeExtents[face])
{
return (parent) ? parent : branch;
}
}
else
{
continue;
}
}
//
//-------------------------------------------------
// Handle testing the minimum value side of the box
//-------------------------------------------------
//
else
{
if (extents[face] < branch->nodeExtents[face])
{
if (extents[opp_face] >= branch->nodeExtents[face])
{
return (parent) ? parent : branch;
}
}
else
{
continue;
}
}
//
//----------------------------------------------------
// If no branch exists, then this is the smallest node
//----------------------------------------------------
//
if (!branch->nodeBranches[face])
{
return (parent) ? parent : branch;
}
branch = branch->nodeBranches[face];
Check(branch);
goto Check_Node;
}
//
//---------------------------------------------------------
// If no inner space exists, then this is the smallest node
//---------------------------------------------------------
//
if (!branch->innerNode)
{
return branch;
}
//
//-------------------------------------------------------------------------
// Once we cross into an innerspace, we have to modify the behaviour of the
// previous, as a volume which is enclosed by the node could itself enclose
// the innerspace node, meaning that the parent node should be reported as
// the smallest node
//-------------------------------------------------------------------------
//
parent = branch;
branch = branch->innerNode;
Check(branch);
goto Check_Node;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
BoundingBoxTreeNode*
BoundingBoxTreeNode::FindSmallestNodeContainingColumn(
const ExtentBox &extents
)
{
Check(&extents);
//
//------------------------------------------------------------------------
// Check along each of the six faces to see if this volume cuts any of the
// planes of the node,
//------------------------------------------------------------------------
//
BoundingBoxTreeNode *branch = this;
Check_Node:
Check(this);
for (int i=0; i<4; ++i)
{
//
//-------------------------------------------------
// Handle testing the maximum value side of the box
//-------------------------------------------------
//
int face = TraversalOrder[i];
int opp_face = face^1;
if (face&1)
{
if (extents[face] > branch->nodeExtents[face])
{
if (extents[opp_face] <= branch->nodeExtents[face])
{
return branch;
}
}
else
{
continue;
}
}
//
//-------------------------------------------------
// Handle testing the minimum value side of the box
//-------------------------------------------------
//
else
{
if (extents[face] < branch->nodeExtents[face])
{
if (extents[opp_face] >= branch->nodeExtents[face])
{
return branch;
}
}
else
{
continue;
}
}
//
//----------------------------------------------------
// If no branch exists, then this is the smallest node
//----------------------------------------------------
//
if (!branch->nodeBranches[face])
{
return branch;
}
branch = branch->nodeBranches[face];
Check(branch);
goto Check_Node;
}
return branch;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
BoundingBox*
BoundingBoxTreeNode::FindBoundingBoxContaining(
const Point3D &point,
BoundingBox *parent
)
{
Check(this);
Check(&point);
//
//----------------------------------------------------
// Set the content pointer to point at this root voxel
//----------------------------------------------------
//
BoundingBoxTreeNode
*branch = this;
//
//-------------------------------------------------------------------------
// Keep checking our voxel branches until the point lies inside the current
// voxel
//-------------------------------------------------------------------------
//
Check_Node:
Check(branch);
for (int i=0; i<6; ++i)
{
//
//-------------------------------------------------------
// Keep looking if the point is not beyond a given extent
//-------------------------------------------------------
//
int face = TraversalOrder[i];
int axis = face >> 1;
if (face&1)
{
if (point[axis] <= branch->nodeExtents[face])
{
continue;
}
}
else if (point[axis] >= branch->nodeExtents[face])
{
continue;
}
//
//-----------------------------------------------------------------------
// The point lies in a side's subspace, so make sure that the subspace on
// that side exists. If not, no voxel will contain the point so return
// the parent. If a facing subspace exists, set the branch pointer to
// that subspace, then check to see where the point is relative to that
// subspace
//-----------------------------------------------------------------------
//
if (!branch->nodeBranches[face])
{
return parent;
}
branch = branch->nodeBranches[face];
goto Check_Node;
}
//
//-------------------------------------------------------------------------
// Since we exited the loop, we have to check inside the node to see if it
// has been subspaced. If so, restart the function again on the internal
// subspace, using the contents of this subspace as the new parent solid.
//
// Note that negative space will not be correctly handled for cases where
// the space being carved out does not fully occupy the zones it is in such
// as with a cylinder
//-------------------------------------------------------------------------
//
if (branch->innerNode)
{
if (branch->staticContents)
{
Check(branch->staticContents);
if (branch->staticContents->ContainsBounded(point))
{
parent = branch->staticContents;
}
}
else
{
parent = NULL;
}
branch = branch->innerNode;
goto Check_Node;
}
//
//----------------------------------------------------------------------
// If our content pointer is NULL, then this node is considered negative
// space, and thus empty
//----------------------------------------------------------------------
//
if (!branch->staticContents)
{
return NULL;
}
//
//--------------------------------------------------------------------------
// We are pointing at a real solid, so if it does in fact contain our point,
// go ahead a return the volume, otherwise return our parent volume
//--------------------------------------------------------------------------
//
Check(branch->staticContents);
if (branch->staticContents->ContainsBounded(point))
{
parent = branch->staticContents;
}
return parent;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
void
BoundingBoxTreeNode::FindBoundingBoxesContaining(
BoundingBox *volume,
const ExtentBox &slice,
BoundingBoxCollisionList &list
)
{
Check(this);
Check(volume);
Check(&slice);
Check(&list);
Verify(list.collisionsLeft>0);
//
//---------------------------------------------------------------------
// Check along each of the six faces, to see if any portion of the test
// volume lies within any of the subspace partitions
//---------------------------------------------------------------------
//
ExtentBox clipped_box = slice;
for (int i=0; i<6; ++i)
{
int
is_clipped;
Scalar
save;
//
//-----------------------------------------------------------------------
// Figure out the opposing face, then check to see if we are testing
// against a maximum face. If so, check to see if some part of the test
// volume protrudes into the defined subspace. If it does, figure out if
// some portion of the test volume remains to be checked, otherwise keep
// checking faces
//-----------------------------------------------------------------------
//
int face = TraversalOrder[i];
int opp_face = face ^ 1;
if (face&1)
{
if (clipped_box[face] > nodeExtents[face])
{
is_clipped = clipped_box[opp_face] <= nodeExtents[face];
}
else
{
continue;
}
}
//
//-----------------------------------------------------------------------
// Otherwise, we are testing against a maximum face. If so, check to see
// if some part of the test volume protrudes into the defined subspace.
// If it does, figure out if some portion of the test volume remains to
// be checked, otherwise keep checking faces
//-----------------------------------------------------------------------
//
else
{
if (clipped_box[face] < nodeExtents[face])
{
is_clipped = clipped_box[opp_face] >= nodeExtents[face];
}
else
{
continue;
}
}
//
//-------------------------------------------------------------------
// If the test volume needs to be clipped, save the old value for the
// opposite face and replace it with this space's bounding face
//-------------------------------------------------------------------
//
if (is_clipped)
{
save = clipped_box[opp_face];
clipped_box[opp_face] = nodeExtents[face];
}
//
//----------------------------------------------------------------------
// If a facing node exists, call this routine again with it and the part
// of the test volume we just trimmed off
//----------------------------------------------------------------------
//
if (nodeBranches[face])
{
Check(nodeBranches[face]);
nodeBranches[face]->FindBoundingBoxesContaining(
volume,
clipped_box,
list
);
}
//
//-----------------------------------------------------------------------
// If no clipping was necessary for this subspace, or we found no entries
// remain in the collision list, we are done checking, so just return
//-----------------------------------------------------------------------
//
if (!is_clipped || !list.collisionsLeft)
{
return;
}
//
//------------------------------------------------------------------
// Otherwise, restore the opposing face of the new box, and clip the
// already tested slice out of the test volume
//------------------------------------------------------------------
//
clipped_box[opp_face] = save;
clipped_box[face] = nodeExtents[face];
}
//
//-------------------------------------------------------------------------
// If we exited the loop, then we have to check inside the node. If this
// node is not a hole, make sure that it collides against the slice. If it
// doesn't, don't override the parent setting, otherwise do override it
//-------------------------------------------------------------------------
//
BoundingBox *hit = NULL;
if (staticContents)
{
Check(staticContents);
if (staticContents->IntersectsBounded(clipped_box))
{
hit = staticContents;
}
}
//
//------------------------------------------------------------------
// If the solid has been subspaced, have it check against collisions
//------------------------------------------------------------------
//
if (innerNode)
{
Check(innerNode);
innerNode->FindBoundingBoxesContaining(
volume,
clipped_box,
list
);
}
//
//-------------------------------------------------------------------------
// Otherwise, if the volume this node points to is not a hole, go ahead and
// add it to the list
//-------------------------------------------------------------------------
//
if (hit && list.collisionsLeft)
{
Check(hit);
list.AddCollisionToList(hit, clipped_box);
}
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
BoundingBox*
BoundingBoxTreeNode::FindBoundingBoxUnder(
const Point3D &point,
Scalar* height
)
{
Check(this);
Check(&point);
Check_Pointer(height);
Verify((TraversalOrder[4]>>1) == Y_Axis)
BoundingBoxTreeNode *branch = this;
BoundingBox *floor;
//
//--------------------------------------------------------------------------
// Check along each of the faces to see if the point lies within any of
// these subspaces. Note the change in the comparison resulting in only the
// first four coordinates (for X and Z) being checked, as the Y coordinate
// needs special treatment
//--------------------------------------------------------------------------
//
Find_Column:
Check(branch);
for (int i=0; i<4; ++i)
{
int face = TraversalOrder[i];
int axis = face >> 1;
if (face&1)
{
if (point[axis] <= branch->nodeExtents[face])
{
continue;
}
}
else if (point[axis] >= branch->nodeExtents[face])
{
continue;
}
//
//---------------------------------------------------------------------
// If a facing subspace exists, start this routine again with the given
// subspace and the point. If it doesn't exist, nothing will be hit
//---------------------------------------------------------------------
//
if (branch->nodeBranches[face])
{
branch = branch->nodeBranches[face];
goto Find_Column;
}
else
{
*height = -1.0f;
return NULL;
}
}
//
//-------------------------------------------------------------------------
// We now know that the object has a presence along the line defined by the
// projection of the point unto the XZ plane. If the point lies above the
// object, and other objects exist in the maxZ subspace, and they are able
// to determine the height, return the height they returned
//-------------------------------------------------------------------------
//
if (point.y > branch->nodeExtents.maxY && branch->nodeBranches[3])
{
Check(branch->nodeBranches[3]);
floor = branch->nodeBranches[3]->FindBoundingBoxUnder(point, height);
if (floor)
{
return floor;
}
}
//
//--------------------------------------------------------------------------
// Handle processing the ray internal to this solid if we need to project
// the ray into our solid. If we are negative space, allow the ray to
// project through the node unhindered.
//
// Note that this code will not properly handle going through negative space
// if the negative space does not completely bore through solids
//--------------------------------------------------------------------------
//
if (point.y >= branch->nodeExtents.minY)
{
if (branch->staticContents)
{
Check(branch->staticContents);
floor = branch->staticContents;
*height = branch->staticContents->FindDistanceBelowBounded(point);
if (*height == -1.0f || point.y - *height < branch->nodeExtents.minY)
{
goto Missed_Us;
}
}
else
{
Missed_Us:
floor = NULL;
*height = -1.0f;
}
//
//-----------------------------------------------------------------------
// If there is internal space defined, we will rely upon it to return the
// proper value if it supersedes this node's height value
//-----------------------------------------------------------------------
//
if (branch->innerNode)
{
Check(branch->innerNode);
Scalar height_2;
BoundingBox *floor_2;
floor_2 = branch->innerNode->FindBoundingBoxUnder(point, &height_2);
if (floor_2 && (height_2 < *height || !floor))
{
*height = height_2;
floor = floor_2;
}
}
//
//--------------------------------------------------
// If something was struck, return that as the floor
//--------------------------------------------------
//
if (floor)
{
return floor;
}
}
//
//--------------------------------------------------------------------------
// We now know that the projection went through our bounding box without
// intersecting our solid. If any objects exist in our Min_Z subspace, have
// them try and return the height
//--------------------------------------------------------------------------
//
if (branch->nodeBranches[2])
{
Check(branch->nodeBranches[2]);
return branch->nodeBranches[2]->FindBoundingBoxUnder(point, height);
}
//
//--------------------------------------------------------------
// Since there is nothing below this bounding box, return no hit
//--------------------------------------------------------------
//
else
{
*height = -1.0f;
return NULL;
}
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
BoundingBox*
BoundingBoxTreeNode::FindBoundingBoxHitBy(Line *line)
{
Check(this);
Check(line);
int
test_queue[7];
Scalar
enter = 0.0f,
leave = 0.0f,
perpendicular,
drift,
distance;
BoundingBox
*result;
//
//--------------------
// Set up for the test
//--------------------
//
int first = 0;
int last = 6;
Logical entered = False;
Logical left = False;
int i;
for (i=0; i<6; ++i)
{
//
//--------------------------------------------------------------------
// Figure out what axis we are dealing with, then based upon the
// direction of the face, find out the distance from the origin to the
// place against the normal, and find out how fast the perpendicular
// distance changes with a unit movement along the line
//--------------------------------------------------------------------
//
int face = TraversalOrder[i];
int axis = face >> 1;
if (face&1)
{
perpendicular = line->origin[axis] - nodeExtents[face];
drift = line->direction[axis];
}
else
{
perpendicular = nodeExtents[face] - line->origin[axis];
drift = -line->direction[axis];
}
//
//----------------------------------------------------------------------
// If the line is parallel to the face, figure out whether or not the
// line origin lies within the face's half-space. If not, put it in the
// list and abort the loop
//----------------------------------------------------------------------
//
if (Small_Enough(drift))
{
if (perpendicular > 0.0f)
{
if (nodeBranches[face])
{
test_queue[first++] = face;
}
break;
}
else
{
continue;
}
}
//
//--------------------------------------------------------------------
// If the drift is towards the plane's halfspace, this plane is one of
// the one through which the line could enter the node
//--------------------------------------------------------------------
//
distance = -perpendicular / drift;
if (drift < 0.0f)
{
if (!entered)
{
entered = True;
enter = distance;
}
else if (distance > enter)
{
enter = distance;
}
//
//--------------------------------------------------------------------
// Queue up the node branch if the origin lies outside of this plane's
// halfspace. If the line cannot reach the plane, abort any more
// testing
//--------------------------------------------------------------------
//
if (perpendicular >= 0.0f)
{
if (nodeBranches[face])
{
test_queue[first++] = face;
}
if (distance > line->length || left && enter > leave)
{
break;
}
}
}
//
//--------------------------------------------------------------------
// If the drift is towards the plane's halfspace, this plane is one of
// the one through which the line could enter the node
//--------------------------------------------------------------------
//
else
{
if (!left)
{
left = True;
leave = distance;
}
else if (distance < leave)
{
leave = distance;
}
//
//--------------------------------------------------------------------
// Queue up the node branch if the origin lies outside of this plane's
// halfspace, and stop further testing. If the origin is inside the
// halfspace, register this branch if the line will reach the plane
//--------------------------------------------------------------------
//
if (perpendicular >= 0.0f)
{
if (nodeBranches[face])
{
test_queue[last--] = face;
}
break;
}
if (distance <= line->length)
{
if (nodeBranches[face])
{
test_queue[last--] = face;
}
}
if (entered && leave < enter)
{
break;
}
}
}
//
//-------------------------------------------------------------------------
// If the loop exited normally, check to see if the bounding box was struck
// by the ray. If it was, then the interior of the voxel must be checked.
// We know that the box was hit if the farthest face opposing the ray
// direction is not farther than the nearest face not opposing the ray
//-------------------------------------------------------------------------
//
if (i == 6)
{
test_queue[last--] = 6;
}
//
//-------------------------------------------------------------------------
// Step through the queue, checking in each of the identified regions to be
// processed first. If a hit is found in one of these, immediately return
// the result
//-------------------------------------------------------------------------
//
for (i=0; i<first; ++i)
{
Check(nodeBranches[test_queue[i]]);
result = nodeBranches[test_queue[i]]->FindBoundingBoxHitBy(line);
if (result)
{
Check(result);
return result;
}
}
//
//-----------------------------------
// Process the interior if it's there
//-----------------------------------
//
if (last<6 && test_queue[last+1] == 6)
{
result = NULL;
if (!staticContents)
{
if (innerNode)
{
Check(innerNode);
result = innerNode->FindBoundingBoxHitBy(line);
}
}
else
{
Check(staticContents);
if (staticContents->HitByBounded(line, enter, leave))
{
result = staticContents;
}
if (innerNode)
{
Check(innerNode);
BoundingBox
*result2 = innerNode->FindBoundingBoxHitBy(line);
if (result2)
{
result = result2;
}
}
}
//
//---------------------------------------------------------------------
// If the ray hit something, return the result, otherwise increment the
// last pointer so that we don't process this subspace again
//---------------------------------------------------------------------
//
if (result)
{
Check(result);
return result;
}
last++;
}
//
//-------------------------------------------------------------------------
// Step through the queue, checking in each of the identified regions to be
// processed last. If a hit is found, immediately return the result
//-------------------------------------------------------------------------
//
for (i=last+1; i<7; ++i)
{
Check(nodeBranches[test_queue[i]]);
result = nodeBranches[test_queue[i]]->FindBoundingBoxHitBy(line);
if (result)
{
Check(result);
return result;
}
}
//
//----------------------------------------------------------
// The ray hit nothing in this voxel, so return the sentinel
//----------------------------------------------------------
//
return NULL;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
Logical
BoundingBoxTreeNode::TestInstance() const
{
return True;
}
//#############################################################################
//########################### BoundingBoxTree ###########################
//#############################################################################
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
void
BoundingBoxTree::Add(
BoundingBox* volume,
const ExtentBox &slice
)
{
Check(this);
Check(volume);
if (!root)
{
root = new BoundingBoxTreeNode(volume, slice);
Register_Object(root);
}
else
{
Check(root);
root->Add(volume, slice);
}
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
void
BoundingBoxTree::EraseTree()
{
if (root)
{
Unregister_Object(root);
delete root;
}
root = NULL;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
BoundingBox*
BoundingBoxTree::FindBoundingBoxHitBy(Line *line)
{
Check(this);
Check(line);
Check(root);
Point3D line_end;
line->FindEnd(&line_end);
ExtentBox line_volume(line->origin, line_end);
return
root->FindSmallestNodeContaining(line_volume, NULL)
->FindBoundingBoxHitBy(line);
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
Logical
BoundingBoxTree::TestInstance() const
{
return True;
}
Reference in New Issue View Git Blame Copy Permalink