/*
	Lan Wars.
	Copyright (c) 2009, Darragh Coy.
	All rights reserved.
	Original work(s), source code & author(s) details available at: http://www.darraghcoy.com

	Redistribution and use in source and binary forms, with or without modification, are permitted 
	provided that the following conditions are met:

		* 	Redistributions of source code must retain the above copyright notice, this list of 
			conditions and the following disclaimer.
		* 	Redistributions in binary form must reproduce the above copyright notice, this list of 
			conditions and the following disclaimer in the documentation.
		* 	Neither the name of the author nor the names of contributors may be used to endorse or 
			promote products derived from this software without specific prior written permission.
		* 	The use of any third party libraries, modules or data files provided with the source 
			form of the program must follow and respect the individual licensing terms of these 
			components. You do not have permission to modify or circumvent the licensing terms for 
			provided third party components unless the third party licenses specifically allow this. 
			If you do not agree to the terms of provided third party components then you do not have 
			permission to use them in your derived work(s).
		* 	The terms of this license do not apply to separate (but related) distributions if supplied 
			by the author(s), only to the contents of this source distribution, derived works, and the 
			binaries produced by either modified or unmodified versions of the source code. The terms 
			of this license do not also apply to any third party libraries or components provided with 
			the source distribution. Such third party elements are licensed under their own separate 
			agreements.

	THIS SOFTWARE IS PROVIDED BY DARRAGH COY ''AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, 
	BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
	ARE DISCLAIMED. IN NO EVENT SHALL DARRAGH COY BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 
	EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 
	OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 
	OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 
	IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

//=====================================================================================================================
/// @brief		This helper class performs collision testing with the level. 
//=====================================================================================================================

#include "Precompiled.h"
#include "Doom/DoomCollision.h"
#include "Doom/DoomLevel.h"
#include "Game/GameCore.h"

using namespace Game;

//=====================================================================================================================
/// @brief		Creates the collision helper with the given doom level
/// @param		level - this is the level we are colliding with
/// @pre		Given level cannot be null
/// @pre		Given level must have BSP tree nodes
//=====================================================================================================================

DoomCollision::DoomCollision( DoomLevel * level )
{
	// Make sure ok:
	
	ENSURE( level != 0				, "Given level cannot be null"				)
	ENSURE( level->HasRootNode()	, "Given level must have BSP tree nodes"	)
	
	// Save:
	
	m_level = level;

	// Get the two stacks from the game

	m_stack				= &GameCore::GetSingleton()->GetStack();
	m_secondary_stack	= &GameCore::GetSingleton()->GetSecondaryStack();
}

//=====================================================================================================================
/// @brief		Does a raycast against the level
/// @param		from - this is the point we are raycasting from
/// @param		to - this is the point we are raycasting to
/// @returns	The result of the raycast
//=====================================================================================================================

DoomCollision::RaycastResult DoomCollision::Raycast( const Vec3f & from , const Vec3f & to ) const
{
	// Store the result here:
	
	RaycastResult result;
	
	// Save this info:
	
	result.m_start_point = from;
	
	// Get the current subsector we are in:
	
	const DoomGLSubsectorV2 * subsector = m_level->GetSubsector(from);
	
	// If there was no subsector then we cannot register a hit:
	
	if ( subsector != 0 )
	{
		// Get the direction of the ray we are casting:
		
		Vec3f dir = to - from; float len = dir.Normalize();
		
		// If the length is zero then return no result:
		
		if ( len > 0 )
		{
			// Right: continue until we are done
			
			bool done = false;
			
			// This is the seg we previously crossed: we use this to avoid the fringe case of an infinite loop
			
			const DoomPPSeg * prev_seg = 0;
			
			// Do the casting: go from subsector to subsector until we register a hit
			
			while ( done == false )
			{			
				// See if we hit any segs:
				
				const DoomPPSeg * hit_seg = GetCrossingSeg(*subsector,from,to);
				
				// See if there was a hit:
				
				if ( hit_seg )
				{
					// Hit a seg: make sure it isn't the previous. Do this to avoid an infinite loop in fringe cases.
					
					if ( hit_seg != prev_seg )
					{				
						// Need to do an intersect with this wall:
						
						result.m_hit_point = WallIntersect(dir,from,*hit_seg);
						
						// See if we could have hit the floor first:
						
						if ( result.m_hit_point.y <= hit_seg->m_floor_height )
						{
							// Hit the floor: need to figure out where
							
							done					= true;
							result.m_hit			= true;
							result.m_hit_point		= FloorIntersect(dir,from,hit_seg->m_floor_height);
							result.m_hit_seg		= 0;
							result.m_hit_subsector	= subsector;
						}
						else if ( result.m_hit_point.y >= hit_seg->m_ceiling_height ) 
						{
							// Hit the ceiling: need to figure out where
							
							done					= true;
							result.m_hit			= true;
							result.m_hit_point		= CeilingIntersect(dir,from,hit_seg->m_ceiling_height);
							result.m_hit_seg		= 0;
							result.m_hit_subsector	= subsector;							
						}
						else
						{
							// Hit neither the floor nor the ceiling: see what type of seg this is
							
							switch ( hit_seg->m_type )
							{
								/// Hitting against a non-solid linedef. Ignore.
							
								case DoomPPSeg::SEG_TYPE_NO_WALL:
								{
									// No hit: non solid wall. Move onto the next subsector.									
									
									prev_seg = hit_seg; subsector = hit_seg->m_opposite_seg->m_subsector;

								}	break;
								
								/// Hitting against a solid wall: there is definitely an intersection.
								
								case DoomPPSeg::SEG_TYPE_FULL_WALL:
								{
									// There definitely is a crossing. Figure out where.
									
									done					= true;
									result.m_hit			= true;
									result.m_hit_subsector	= 0;
									result.m_hit_seg		= hit_seg;														
								
								}	break;
								
								/// Hitting against the lower wall potentially
								
								case DoomPPSeg::SEG_TYPE_LOWER_WALL:
								{
									// Get the interesection point:
									
									result.m_hit_point = WallIntersect(dir,from,*hit_seg);
									
									// See if at the right height:
									
									if ( result.m_hit_point.y < hit_seg->m_lower_height )
									{
										// Bingo: result
										
										done					= true;
										result.m_hit			= true;
										result.m_hit_subsector	= 0;
										result.m_hit_seg		= hit_seg;						
									}
									else
									{
										// No hit: Move onto the next subsector.
										
										prev_seg = hit_seg; subsector = hit_seg->m_opposite_seg->m_subsector;	
									}
								
								}	break;
								
								/// Hitting against the upper wall potentially
								
								case DoomPPSeg::SEG_TYPE_UPPER_WALL:
								{
									// See if at the right height:
									
									if ( result.m_hit_point.y > hit_seg->m_upper_height )
									{
										// Bingo: result
										
										done					= true;
										result.m_hit			= true;
										result.m_hit_subsector	= 0;
										result.m_hit_seg		= hit_seg;							
									}
									else
									{
										// No hit: Move onto the next subsector.
										
										prev_seg = hit_seg; subsector = hit_seg->m_opposite_seg->m_subsector;			
									}
								
								}	break;
								
								/// Potentially hitting either the upper or lower wall
								
								case DoomPPSeg::SEG_TYPE_LOWER_UPPER_WALL:
								{
									// See if at the right height:
									
									if ( result.m_hit_point.y < hit_seg->m_lower_height || result.m_hit_point.y > hit_seg->m_upper_height )
									{
										// Bingo: result! Hit off either the top or bottom walls
										
										done					= true;
										result.m_hit			= true;
										result.m_hit_subsector	= 0;
										result.m_hit_seg		= hit_seg;		
									}
									else
									{
										// No hit: Move onto the next subsector.
										
										prev_seg = hit_seg; subsector = hit_seg->m_opposite_seg->m_subsector;
									}
								
								}	break;
								
							}	// end switch seg type						
						}
					}
					else
					{
						//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
						// Ray must be almost a single point between a seg. It is crossing back and forth. Return no result.
						// In reality this case should never happen- ever. But floating point precision always makes it a
						// posibile in in any case.
						//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
						
						done					= true;
						result.m_hit			= false;
						result.m_hit_point		= to;
						result.m_hit_seg		= 0;
						result.m_hit_subsector	= 0;							
					}
				}
				else
				{
					// Couldn't be hitting any segs. Might hit the floor or ceiling. Get the sector we are in:
						
					const DoomSector & sector = m_level->GetSector(*subsector);
					
					// Get the floor and ceiling height:
					
					float fh = sector.m_floor_y;
					float ch = sector.m_ceiling_y;
					
					// See if the ray crosses the floor/ceiling plane:
				
					if ( to.y > ch )
					{
						// Hit the ceiling: need to figure out where
						
						done					= true;
						result.m_hit			= true;
						result.m_hit_point		= CeilingIntersect(dir,from,ch);
						result.m_hit_seg		= 0;
						result.m_hit_subsector	= subsector;
					}
					else if ( to.y < fh )
					{
						// Hit the floor: need to figure out where
						
						done					= true;
						result.m_hit			= true;
						result.m_hit_point		= FloorIntersect(dir,from,fh);
						result.m_hit_seg		= 0;
						result.m_hit_subsector	= subsector;					
					}
					else
					{
						// No crossing: we are done here
						
						done					= true;		
						result.m_hit			= false;
						result.m_hit_point		= to;
						result.m_hit_seg		= 0;
						result.m_hit_subsector	= 0;							
					}
					
				}	// end else of if we hit a seg
				
			}	// end while not done
			
		}
		else
		{
			// Zero length ray. Cannot do collision detection.
			
			result.m_hit			= false;
			result.m_hit_point		= to;
			result.m_hit_seg		= 0;
			result.m_hit_subsector	= 0;			
		}
	}
	else
	{
		// No subsector. Cannot do collision detection.
	
		result.m_hit			= false;
		result.m_hit_point		= to;
		result.m_hit_seg		= 0;
		result.m_hit_subsector	= 0;
	}
	
	// Return the result
	
	return result;
}

//=====================================================================================================================
/// @brief		Does a 2D raycast against the level: ignores lower and upper walls and floors/ceilings.
/// @param		from - this is the point we are raycasting from
/// @param		to - this is the point we are raycasting to
/// @returns	The result of the raycast
//=====================================================================================================================

DoomCollision::RaycastResult DoomCollision::Raycast2D( const Vec3f & from , const Vec3f & to ) const
{
	// Store the result here:
	
	RaycastResult result;
	
	// Save this info:
	
	result.m_start_point = from;
	
	// Get the current subsector we are in:
	
	const DoomGLSubsectorV2 * subsector = m_level->GetSubsector(from);
	
	// If there was no subsector then we cannot register a hit:
	
	if ( subsector != 0 )
	{
		// Get the direction of the ray we are casting:
		
		Vec3f dir = to - from; float len = dir.Normalize();
		
		// If the length is zero then return no result:
		
		if ( len > 0 )
		{
			// Right: continue until we are done
			
			bool done = false;
			
			// This is the seg we previously crossed: we use this to avoid the fringe case of an infinite loop
			
			const DoomPPSeg * prev_seg = 0;
			
			// Do the casting: go from subsector to subsector until we register a hit
			
			while ( done == false )
			{			
				// See if we hit any segs:
				
				const DoomPPSeg * hit_seg = GetCrossingSeg(*subsector,from,to);
				
				// See if there was a hit:
				
				if ( hit_seg )
				{
					// Hit a seg: make sure it isn't the previous. Do this to avoid an infinite loop in fringe cases.
					
					if ( hit_seg != prev_seg )
					{				
						// See what type of seg this is:
						
						switch ( hit_seg->m_type )
						{	
							/// Hitting against a solid wall: there is definitely an intersection.
							
							case DoomPPSeg::SEG_TYPE_FULL_WALL:
							{
								// There definitely is a crossing. Figure out where.
								
								done					= true;
								result.m_hit			= true;
								result.m_hit_subsector	= 0;
								result.m_hit_seg		= hit_seg;
								result.m_hit_point		= WallIntersect(dir,from,*hit_seg);
							
							}	break;
							
							/// Potentially hitting either the upper or lower wall. Ignore collision.
							
							case DoomPPSeg::SEG_TYPE_NO_WALL:
							case DoomPPSeg::SEG_TYPE_LOWER_WALL:
							case DoomPPSeg::SEG_TYPE_UPPER_WALL:
							case DoomPPSeg::SEG_TYPE_LOWER_UPPER_WALL:
							{
								// No hit: non solid wall. Move onto the next subsector.
								
								prev_seg = hit_seg; subsector = hit_seg->m_opposite_seg->m_subsector;
							
							}	break;
							
						}	// end switch seg type
					}
					else
					{
						//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
						// Ray must be almost a single point between a seg. It is crossing back and forth. Return no result.
						// In reality this case should never happen- ever. But floating point precision always makes it a
						// posibile in in any case.
						//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
						
						done					= true;
						result.m_hit			= false;
						result.m_hit_point		= to;
						result.m_hit_seg		= 0;
						result.m_hit_subsector	= 0;							
					}
				}
				else
				{
					// Couldn't be hitting any segs. Since we can't collide with the floor or ceiling do not register a hit.
					
					done					= true;
					result.m_hit			= false;
					result.m_hit_point		= to;
					result.m_hit_seg		= 0;
					result.m_hit_subsector	= 0;	
					
				}	// end else of if we hit a seg
				
			}	// end while not done
			
		}
		else
		{
			// Zero length ray. Cannot do collision detection.
			
			result.m_hit			= false;
			result.m_hit_point		= to;
			result.m_hit_seg		= 0;
			result.m_hit_subsector	= 0;			
		}
	}
	else
	{
		// No subsector. Cannot do collision detection.
	
		result.m_hit			= false;
		result.m_hit_point		= to;
		result.m_hit_seg		= 0;
		result.m_hit_subsector	= 0;
	}
	
	// Return the result
	
	return result;
}

//=====================================================================================================================
/// @brief		Gets which seg in a subsector the given line crosses, if any
/// @param		subsector - subsector we are checking from
/// @param		from - this is the position we are casting from
/// @param		to - this is the position we are casting to
/// @remarks	This function ignores backface segs. So it will ingore the segs the line crossed in order to reach this
///				seg. 
/// @pre		The given subsector must have segs
//=====================================================================================================================

const DoomPPSeg * DoomCollision::GetCrossingSeg( const DoomGLSubsectorV2 & subsector , const Vec3f & from , const Vec3f & to ) const
{
	// Make sure ok:
	
	ENSURE( subsector.m_count > 0 , "The given subsector must have segs" )
	
	// Run through all the segs:
	
	for ( unsigned i = 0 ; i < subsector.m_count ; ++i )
	{
		// Get this seg:
		
		const DoomPPSeg & seg = m_level->GetSeg( subsector.m_first_seg + i );
			
		// See what side of the plane the first point is on: it must be on the right side of the plane for us to consider it
		
		float dot1 = seg.m_minus_n_dot_p + from.Dot( seg.m_normal_3d );
		
		// Allow this for floating point inprecision
		
		#define EPISILON 0.0000001f
		
		// Only if the dot is positive:
		
		if ( dot1 >= - EPISILON )
		{
			// Good: now see if the second point is on the OPPOSITE side of the plane. If so then there could be a crossing
			
			float dot2 = seg.m_minus_n_dot_p + to.Dot( seg.m_normal_3d );
			
			// See if this is the case:
			
			if ( dot2 < EPISILON )
			{
				// If there is an edge intersect then this is the correct line:
				
				if ( EdgeIntersect(from,to,seg) )
				{
					return &seg;
				}
			}
		}
	}
	
	// Did not find any overlapping seg
	
	return 0;
}

//=====================================================================================================================
/// @brief		Finds the intersection of the given ray with the given wall plane and returns it:
/// @param		dir - direction the ray is being cast in
/// @param		start - starting point of the ray
/// @param		seg - segment whose plane we will be intersecting with
/// @returns	The hit point
//=====================================================================================================================

Vec3f DoomCollision::WallIntersect( const Vec3f & dir , const Vec3f & start , const DoomPPSeg & seg ) const
{
	// Calculate the dot of the plane normal with the direction
	
	float vdotn = dir.Dot(seg.m_normal_3d);
	
	// If this is zero then the line is colinear to the plane: what can we do in this case but return the midpoint of the seg ?
	
	if ( vdotn != 0 )
	{
		// Good: need to calculate the 'time' of intersection along the ray
		
		float t = ( -seg.m_normal_3d.Dot(start) - seg.m_minus_n_dot_p ) / vdotn;
		
		// Return the intersect point
		
		return start + ( dir * t );
	}
	else
	{
		// This should never happen in reality: return the midpoint of the seg
		
		return Vec3f
		( 
			( seg.m_start.x + seg.m_end.x ) * 0.5f , 
			( seg.m_floor_height + seg.m_ceiling_height ) * 0.5f ,
			( seg.m_start.y + seg.m_end.y ) * 0.5f 
		);
	}
}

//=====================================================================================================================
/// @brief		Finds the intersection of the given ray with the given floor plane and returns it:
/// @param		dir - direction of the ray
/// @param		start - start point of the ray
/// @param		floor_height - height of the floor
/// @remarks	This function assumes that we already know there's an intersection with the floor plane
//=====================================================================================================================

Vec3f DoomCollision::FloorIntersect( const Vec3f & dir , const Vec3f & start , float floor_height ) const
{
	// Calculate the dot of the plane normal with the direction
	
	float vdotn = dir.y;
	
	// If this is zero then the line is colinear to the plane: what can we do in this case but return the midpoint of the seg ?
	
	if ( vdotn != 0 )
	{
		// Good: need to calculate the 'time' of intersection along the ray
		
		float t = ( - start.y + floor_height ) / vdotn;
		
		// Return the intersect point
		
		return start + ( dir * t );
	}
	else
	{
		// This should never happen in reality: return the midpoint of the seg
		
		return Vec3f::Zero();
	}
}

//=====================================================================================================================
/// @brief		Finds the intersection of the given ray with the given ceiling plane and returns it:
/// @param		dir - direction of the ray
/// @param		start - start point of the ray
/// @param		ceiling_height - height of the ceiling
/// @remarks	This function assumes that we already know there's an intersection with the ceiling plane
//=====================================================================================================================

Vec3f DoomCollision::CeilingIntersect( const Vec3f & dir , const Vec3f & start , float ceiling_height ) const
{
	// Calculate the dot of the plane normal with the direction
	
	float vdotn = -dir.y;
	
	// If this is zero then the line is colinear to the plane: what can we do in this case but return the midpoint of the seg ?
	
	if ( vdotn != 0 )
	{
		// Good: need to calculate the 'time' of intersection along the ray
		
		float t = ( start.y - ceiling_height ) / vdotn;
		
		// Return the intersect point
		
		return start + ( dir * t );
	}
	else
	{
		// This should never happen in reality: return 0,0
		
		return Vec3f::Zero();
	}	
}

//=====================================================================================================================
/// @brief		Tells if the two edges intersect. This function takes two points and a line segment.
/// @param		p1 - point 1 of edge 1
/// @param		p2 - point 2 of edge 1
/// @param		seg - line segment which represents edge 2
/// @returns	True if there is an intersection.
/// @remarks	The intersection is done in 2D only
//=====================================================================================================================

bool DoomCollision::EdgeIntersect( const Vec3f & p1 , const Vec3f & p2 , const DoomPPSeg & seg ) const
{
    //-----------------------------------------------------------------------------------------------------------------
    // This method of line intersection is followed from mathworld.com:
    // Using determinants the x and y intersection point can be found as:
    //
    // x = | | x1 y1 | , x1 - x2 |            | x1 - x2  , y1 - y2 |
    //     | | x2 y2 |           |            |                    |
    //     |                     | divided by |                    |
    //     | | x3 y3 | , x3 - x4 |            | x3 - x4  , y3 - y4 |
    //     | | x4 y4 |           |            |                    |
    //
    // y = | | x1 y1 | , y1 - y2 |            | x1 - x2  , y1 - y2 |
    //     | | x2 y2 |           |            |                    |
    //     |                     | divided by |                    |
    //     | | x3 y3 | , y3 - y4 |            | x3 - x4  , y3 - y4 |
    //     | | x4 y4 |           |            |                    |
    //
    // shortening these expressions:
    //
    // x = | a , c | divided by | c , e |
    //     | b , d |            | d , f |
    //
    // y = | a , e | divided by | c , e |
    //     | b , f |            | d , f |
    //
    //
    // shortening further:
    //
    // x = det1 / det2
    // y = det3 / det2
    //
    // Note that if det2 = 0 then there is no solution
    //
    //-----------------------------------------------------------------------------------------------------------------

    // Original ordering
    //
    // float a = edge1P1[0] * edge1P2[1] - edge1P1[1] * edge1P2[0];
    // float b = edge2P1[0] * edge2P2[1] - edge2P1[1] * edge2P2[0];
    // float c = edge1P1[0] - edge1P2[0];
    // float d = edge2P1[0] - edge2P2[0];
    // float e = edge1P1[1] - edge1P2[1];
    // float f = edge2P1[1] - edge2P2[1];

    // Reverse the ordering of p1 and p2 to save a few calculations further on: doesn't affect result

    float a = p2.x * p1.z - p2.z * p1.x;
    float b = seg.m_end.x * seg.m_start.y - seg.m_end.y * seg.m_start.x;
    float c = p2.x - p1.x;
    float d = seg.m_end.x - seg.m_start.x;
    float e = p2.z - p1.z;
    float f = seg.m_end.y - seg.m_start.y;

    float det1 = a * d - c * b;
    float det2 = c * f - e * d;
    float det3 = a * f - e * b;

    // If det2 there is no solution: return false

    if ( det2 == 0 ) return false;

    // Solve for x and y:

    float x = det1 / det2;
    float y = det3 / det2;

    //-----------------------------------------------------------------------------------------------------------------
    // Now that we have the intersection point, see if it is on both lines:
    //-----------------------------------------------------------------------------------------------------------------

    // Calculate the time value along edge1 the intersection occurs at:

    {
        //-------------------------------------------------------------------------------------------------------------
        // Get the edge1 in the form r = s + tv : ray form
        //-------------------------------------------------------------------------------------------------------------

        // float s[2] = { edge1P1[0]        , edge1P1[1]        };
        // float v[2] = { edge1P2[0] - s[0] , edge1P2[1] - s[1] };

        // Look above: v[0] is actually c , and v[1] is actually e :

        //-------------------------------------------------------------------------------------------------------------
        // Get the largest v component and decide whether to solve for t using
        // the x or y coordinate of the intersection point on the line. Using
        // the most significant component will increase the accuracy of the test
        //-------------------------------------------------------------------------------------------------------------

        // if ( fabs(c) >= fabs(e) ) slow way of doing this - look below for the integer replacement:

        if ( ((unsigned&)(c)) << 1 > ((unsigned&)(e)) << 1 )
        {
            // Solve for t using the x components of the edge ray and intersection point:

            float t = ( x - p1.x ) / (c);

            //---------------------------------------------------------------------------------------------------------
            // If t is < 0 or > 1 then intersection point is beyond the end of
            // this line segment and the intersection cannot occur:
            //---------------------------------------------------------------------------------------------------------

            //if ( t < 0 || t > 1 ) return false;

            // This is a faster integer based way of determining t > 1 || t < 0: Works only for IEEE single precision floats !

            if ( (unsigned&) t > 0x3F800000 ) return false;
        }
        else
        {
            // Solve for t using the y components of the edge ray and intersection point:

            float t = ( y - p1.z ) / (e);

            //---------------------------------------------------------------------------------------------------------
            // If t is < 0 or > 1 then intersection point is beyond the end of
            // this line segment and the intersection cannot occur:
            //---------------------------------------------------------------------------------------------------------

            //if ( t < 0 || t > 1 ) return false;

            // This is a faster integer based way of determining t > 1 || t < 0: Works only for IEEE single precision floats !

            if ( (unsigned&) t > 0x3F800000 ) return false;
        }
    }

    // Calculate the time value along edge2 the intersection occurs at:

    {
        //-------------------------------------------------------------------------------------------------------------
        // Get the edge2 in the form r = s + tv : ray form
        //-------------------------------------------------------------------------------------------------------------

        // float s[2] = { edge2P1[0]        , edge2P1[1]        };
        // float v[2] = { edge2P2[0] - s[0] , edge2P2[1] - s[1] };

        // Look above: v[0] is actually d , and v[1] is actually f :

        //-------------------------------------------------------------------------------------------------------------
        // Get the largest v component and decide whether to solve for t using
        // the x or y coordinate of the intersection point on the line. Using
        // the most significant component will increase the accuracy of the test
        //-------------------------------------------------------------------------------------------------------------

        // if ( fabs(d) >= fabs(f) ) slow way of doing this - look below for the integer replacement:

        if ( ((unsigned&)(d)) << 1 > ((unsigned&)(f)) << 1 )
        {
            // Solve for t using the x components of the edge ray and intersection point:

            float t = ( x - seg.m_start.x ) / (d);

            //---------------------------------------------------------------------------------------------------------
            // If t is < 0 or > 1 then intersection point is beyond the end of
            // this line segment and the intersection cannot occur:
            //---------------------------------------------------------------------------------------------------------

            // if ( t < 0 || t > 1 ) return false;

            // This is a faster integer based way of determining the above expression: Works only for IEEE single precision floats !

            if ( (unsigned&) t > 0x3F800000 ) return false;
        }
        else
        {
            // Solve for t using the y components of the edge ray and intersection point:

            float t = ( y - seg.m_start.y ) / (f);

            //---------------------------------------------------------------------------------------------------------
            // If t is < 0 or > 1 then intersection point is beyond the end of
            // this line segment and the intersection cannot occur:
            //---------------------------------------------------------------------------------------------------------

            // if ( t < 0 || t > 1 ) return false;

            // This is a faster integer based way of determining the above expression: Works only for IEEE single precision floats !

            if ( (unsigned&) t > 0x3F800000 ) return false;
        }
    }

    //-----------------------------------------------------------------------------------------------------------------
    // If this point has been reach then the two lines cross: return true
    //-----------------------------------------------------------------------------------------------------------------

    // Return true

    return true;	
}

//=====================================================================================================================
/// @brief		Collides the given thing with the level: returns it's output position thereafter
/// @param		pos - position of the point after movement
/// @param		radius - radius of the object's bounding sphere
/// @param		height - half dimensions from the cetner to of the object to it's top/bottom.
/// @post		The position of the two stacks used by the collision object must be the same afterwards
//=====================================================================================================================

Vec3f DoomCollision::Collide( const Vec3f & pos , float radius , float height ) const
{ 
	// Debug only:
	
	#ifdef DEBUG
	
		void * s1_pos = m_stack->GetPointer();
		void * s2_pos = m_secondary_stack->GetPointer();
	
	#endif

	// Build a list of potential colliders and save them in the stack:

	unsigned num_colliders = BuildCollisionSubsectorsRecursive
	( 
		m_level->GetRootNode()	,
		pos						,
		radius
	);	

	// If there are no colliders then just return th position given:

	if ( num_colliders == 0 )
	{
		// Not colliding with anything:

		return pos;
	}
	else
	{
		// Store the output position here:
		
		Vec3f output_pos = pos;

		// Do planar collision with all objects. Ignore points.

		for ( unsigned i = 0 ; i < num_colliders ; i++ )
		{
			// Get this subsector

			DoomGLSubsectorV2 & subsector = * ( m_stack->Pop<DoomGLSubsectorV2*>() );
			
			// Put it into the secondary stack for later edge collision.
			
			m_secondary_stack->Push(&subsector);

			// Collide with this subsector: do only plane collisions
				
			output_pos = SubsectorPlaneCollide(subsector,output_pos,radius,height);
		}
		
		// Do planar collision with all objects. Ignore points.

		for ( unsigned i = 0 ; i < num_colliders ; i++ )
		{
			// Get this subsector

			DoomGLSubsectorV2 & subsector = * ( m_secondary_stack->Pop<DoomGLSubsectorV2*>() );
			
			// Put it into the stack for later point collision.
			
			m_stack->Push(&subsector);

			// Collide with this subsector: do only plane collisions
				
			output_pos = SubsectorEdgeCollide(subsector,output_pos,radius,height);
		}
		
		// Do point collision with all objects: ingore planes
		
		for ( unsigned i = 0 ; i < num_colliders ; i++ )
		{
			// Get this subsector

			DoomGLSubsectorV2 & subsector = * ( m_stack->Pop<DoomGLSubsectorV2*>() );

			for ( unsigned j = 0 ; j < subsector.m_count ; ++j )
			{
				// Collide with this subsector: do only point collisions
				
				output_pos = SubsectorPointCollide(subsector,output_pos,radius,height);
			}
		}
		
		// Get the current subsector the player is in:
		
		const DoomGLSubsectorV2 * subsector = m_level->GetSubsector(output_pos);
		
		// See if we are in one:
		
		if ( subsector )
		{
			// Get the sector this subsector is in
			
			const DoomSector & sector = m_level->GetSector(*subsector);
			
			// We can't exceed the ceiling/floor height positions of the subsector:
		
			if ( output_pos.y - height < sector.m_floor_y   ){ output_pos.y = sector.m_floor_y   + height; }
			if ( output_pos.y + height > sector.m_ceiling_y ){ output_pos.y = sector.m_ceiling_y - height; }
		}	
		
		// Debug only:
		
		#ifdef DEBUG
		
			ENSURE( s1_pos == m_stack->GetPointer()				, "The position of the two stacks used by the collision object must be the same afterwards" )
			ENSURE( s2_pos == m_secondary_stack->GetPointer()	, "The position of the two stacks used by the collision object must be the same afterwards" )
		
		#endif		
		
		// Return the output position
		
		return output_pos;

	}	// end if colliders count not equal to zero
}

//=====================================================================================================================
/// @brief		Performs collision with the given subsector. Only performs planar collisions only.
/// @param		subsector - the subsector to collide with
/// @param		pos - this is the current position of the object
/// @param		radius - this is the radius of the bounding circle for the object
/// @param		height - this is the height of the object
/// @returns	The position of the object after collision.
//=====================================================================================================================

Vec3f DoomCollision::SubsectorPlaneCollide( const DoomGLSubsectorV2 & subsector, const Vec3f & pos , float radius , float height ) const
{
	// Store the output position here:
	
	Vec3f output_pos = pos;

	// Run through all the segs in the subsector:
	
	for ( unsigned i = 0 ; i < subsector.m_count ; i++ )
	{
		// Get this seg:
		
		const DoomPPSeg & seg = m_level->GetSeg(subsector.m_first_seg+i);
		
		// If it is not collideable then ignore
		
		switch ( seg.m_type )
		{
			// Full wall: just do normal collisions with it:
			
			case DoomPPSeg::SEG_TYPE_FULL_WALL:
			{
				// Get our distance to the wall:
				
				float pdist = seg.m_minus_n_dot_p + output_pos.Dot(seg.m_normal_3d);
				
				// Get our distance along the plane direction: we can only collide when our position lies along the plane line
				
				float hdist = seg.m_minus_d_dot_p + output_pos.Dot(seg.m_direction_3d);
				
				// See if we are in range to collide:
				
				if ( pdist > 0 && pdist < radius && hdist >= 0 && hdist <= seg.m_length )
				{
					// Move back along the plane normal
					
					output_pos += seg.m_normal_3d * ( radius - pdist );
				}
			
			}	break;
			
			// Lower wall:
			
			case DoomPPSeg::SEG_TYPE_LOWER_WALL:
			{
				// Only if we are in range for a collision:
				
				if ( output_pos.y < seg.m_lower_height )
				{			
					// Get our distance to the wall:
					
					float pdist = seg.m_minus_n_dot_p + output_pos.Dot(seg.m_normal_3d);
					
					// Get our distance along the plane direction: we can only collide when our position lies along the plane line
					
					float hdist = seg.m_minus_d_dot_p + output_pos.Dot(seg.m_direction_3d);
					
					// See if we are in range to collide:
					
					if ( pdist > 0 && pdist < radius && hdist >= 0 && hdist <= seg.m_length )
					{				
						// Move back along the plane normal
						
						output_pos += seg.m_normal_3d * ( radius - pdist );
					}
				}
			
			}	break;
			
			// upper wall:
			
			case DoomPPSeg::SEG_TYPE_UPPER_WALL:
			{
				// Only if we are in range for a collision:
				
				if ( output_pos.y > seg.m_upper_height - height )
				{			
					// Get our distance to the wall:
					
					float pdist = seg.m_minus_n_dot_p + output_pos.Dot(seg.m_normal_3d);
					
					// Get our distance along the plane direction: we can only collide when our position lies along the plane line
					
					float hdist = seg.m_minus_d_dot_p + output_pos.Dot(seg.m_direction_3d);
					
					// See if we are in range to collide:
					
					if ( pdist > 0 && pdist < radius && hdist >= 0 && hdist <= seg.m_length )
					{				
						// Move back along the plane normal
						
						output_pos += seg.m_normal_3d * ( radius - pdist );
					}
				}
			
			}	break;
			
			// lower and upper wall:
			
			case DoomPPSeg::SEG_TYPE_LOWER_UPPER_WALL:
			{
				// Only if we are in range for a collision:
				
				if ( output_pos.y < seg.m_lower_height || output_pos.y > seg.m_upper_height - height )
				{			
					// Get our distance to the wall:
					
					float pdist = seg.m_minus_n_dot_p + output_pos.Dot(seg.m_normal_3d);
					
					// Get our distance along the plane direction: we can only collide when our position lies along the plane line
					
					float hdist = seg.m_minus_d_dot_p + output_pos.Dot(seg.m_direction_3d);
					
					// See if we are in range to collide:
					
					if ( pdist > 0 && pdist < radius && hdist >= 0 && hdist <= seg.m_length )
					{				
						// Move back along the plane normal
						
						output_pos += seg.m_normal_3d * ( radius - pdist );
					}
				}
			
			}	break;
		}
	}
	
	// Return the output
	
	return output_pos;
}

//=====================================================================================================================
/// @brief		Performs edge collisions with the given subsector
/// @param		subsector - subsector to collide with
/// @param		pos - this is the current position of the object
/// @param		radius - this is the radius of the bounding circle for the object
/// @param		height - this is the height of the object
/// @returns	The position of the object after collision.
//=====================================================================================================================

Vec3f DoomCollision::SubsectorEdgeCollide( const DoomGLSubsectorV2 & subsector, const Vec3f & pos , float radius , float height ) const
{
	// Store the output position here:
	
	Vec3f output_pos = pos;
	
	// Get the square radius
	
	float sq_radius = radius * radius;
	
	// Calculate the scaling required on the y axis to make the bounding ellipsoid into a bounding sphere: this scaling simplies the problem
	
	float yscale = radius / height;
	
	// This un-do's the previous scaling:
	
	float yinvscale = 1.0f / yscale;
	
	// Run through all the segs in the subsector:
	
	for ( unsigned i = 0 ; i < subsector.m_count ; i++ )
	{
		// Get this seg:
		
		const DoomPPSeg & seg = m_level->GetSeg(subsector.m_first_seg+i);
		
		// If it is not collideable then ignore
		
		switch ( seg.m_type )
		{
			/// Lower wall: see if we can collide with the points:
			
			case DoomPPSeg::SEG_TYPE_LOWER_WALL:
			{
				// See if the point can collide with the lower edge of the wall:
				
				if ( pos.y < seg.m_lower_height + height && pos.y > seg.m_lower_height )
				{
					// See if the point is along the length of the line
					
					float pdist = seg.m_minus_n_dot_p + output_pos.Dot( seg.m_normal_3d		);
					float hdist = seg.m_minus_d_dot_p + output_pos.Dot( seg.m_direction_3d	);
					
					// See if it's along the line:
					
					if ( pdist > 0 && pdist < radius && hdist >= 0 && hdist <= seg.m_length )
					{
						// Along the line. Get the point along the edge we are colliding with:
						
						Vec3f p1 = Vec3f( seg.m_start.x , seg.m_lower_height , seg.m_start.y );
						
							p1 += seg.m_direction_3d * hdist;
							
						// Scale the point so the ellipsoid acts a sphere
							
						p1.y *= yscale;
				
						// Scale the starting point
						
						Vec3f p2 = output_pos; p2.y *= yscale;
						
						// Collide with it:
						
						if ( PointCollide(p2,p1,radius,sq_radius) )
						{
							// Undo the scaling:
							
							p2.y *= yinvscale; output_pos = p2;
						}
					}	
				}
				
			}	break;			
			
			/// Upper and lower wall: see if we can collide with the points:
			
			case DoomPPSeg::SEG_TYPE_LOWER_UPPER_WALL:
			{
				// See if the point can collide with the lower edge of the wall:
				
				if ( pos.y < seg.m_lower_height + height && pos.y > seg.m_lower_height )
				{
					// See if the point is along the length of the line
					
					float pdist = seg.m_minus_n_dot_p + output_pos.Dot( seg.m_normal_3d		);
					float hdist = seg.m_minus_d_dot_p + output_pos.Dot( seg.m_direction_3d	);
					
					// See if it's along the line:
					
					if ( pdist > 0 && pdist < radius && hdist >= 0 && hdist <= seg.m_length )
					{
						// Along the line. Get the point along the edge we are colliding with:
						
						Vec3f p1 = Vec3f( seg.m_start.x , seg.m_lower_height , seg.m_start.y );
						
							p1 += seg.m_direction_3d * hdist;
							
						// Scale the point so the ellipsoid acts a sphere
							
						p1.y *= yscale;
				
						// Scale the starting point
						
						Vec3f p2 = output_pos; p2.y *= yscale;
						
						// Collide with it:
						
						if ( PointCollide(p2,p1,radius,sq_radius) )
						{
							// Undo the scaling:
							
							p2.y *= yinvscale; output_pos = p2;
						}
					}	
				}					
								
			}	break;			
		}
	}
	
	// Return the output
	
	return output_pos;		
}

//=====================================================================================================================
/// @brief		Performs point collisions with the given subsector
/// @param		subsector - the subsector to collide with
/// @param		pos - this is the current position of the object
/// @param		radius - this is the radius of the bounding circle for the object
/// @param		height - this is the height of the object
/// @returns	The position of the object after collision.
//=====================================================================================================================

Vec3f DoomCollision::SubsectorPointCollide( const DoomGLSubsectorV2 & subsector, const Vec3f & pos , float radius , float height ) const
{
	// Store the output position here:
	
	Vec3f output_pos = pos;
	
	// Get the square radius
	
	float sq_radius = radius * radius;
	
	// Calculate the scaling required on the y axis to make the bounding ellipsoid into a bounding sphere: this scaling simplies the problem
	
	float yscale = radius / height;
	
	// This un-do's the previous scaling:
	
	float yinvscale = 1.0f / yscale;

	// Run through all the segs in the subsector:
	
	for ( unsigned i = 0 ; i < subsector.m_count ; i++ )
	{
		// Get this seg:
		
		const DoomPPSeg & seg = m_level->GetSeg(subsector.m_first_seg+i);
		
		// If it is not collideable then ignore
		
		switch ( seg.m_type )
		{
			// Full wall: just do normal collisions with it:
			
			case DoomPPSeg::SEG_TYPE_FULL_WALL:
			{
				// Scale the first and second points so that the bounding ellipse becomes a bounding sphere
				
				Vec3f p1 = Vec3f( seg.m_start.x	, output_pos.y	,	seg.m_start.y	);	
				Vec3f p2 = Vec3f( seg.m_end.x	, output_pos.y	,	seg.m_end.y		);
								
				p1.y *= yscale;
				p2.y *= yscale;
				
				// Scale the starting point
				
				Vec3f p = output_pos; p.y *= yscale;
				
				// Collide with these two points:
				
				bool collision = PointCollide(p,p1,radius,sq_radius); collision = collision || PointCollide(p,p2,radius,sq_radius);
				
				// Unscale the position of our point if there was a collision and save the result:
				
				if ( collision ){ p.y *= yinvscale; output_pos = p; }
			
			}	break;
			
			/// Lower wall: see if we can collide with the points:
			
			case DoomPPSeg::SEG_TYPE_LOWER_WALL:
			{
				// Check and see:
				
				if ( output_pos.y < seg.m_lower_height + height )
				{
					// See if we are below the wall: if so then treat the y position of the point as the camera y
					
					if ( output_pos.y > seg.m_lower_height )
					{				
						// Scale the first and second points so that the bounding ellipse becomes a bounding sphere
						
						Vec3f p1 = Vec3f( seg.m_start.x	, seg.m_lower_height	,	seg.m_start.y	);	
						Vec3f p2 = Vec3f( seg.m_end.x	, seg.m_lower_height	,	seg.m_end.y		);
										
						p1.y *= yscale;
						p2.y *= yscale;
						
						// Scale the starting point
						
						Vec3f p = output_pos; p.y *= yscale;
						
						// Collide with these two points:
						
						bool collision = PointCollide(p,p1,radius,sq_radius); collision = collision || PointCollide(p,p2,radius,sq_radius);
						
						// Unscale the position of our point if there was a collision and save the result:
						
						if ( collision ){ p.y *= yinvscale; output_pos = p; }
					}
					else
					{
						// Scale the first and second points so that the bounding ellipse becomes a bounding sphere
						
						Vec3f p1 = Vec3f( seg.m_start.x	, output_pos.y	,	seg.m_start.y	);	
						Vec3f p2 = Vec3f( seg.m_end.x	, output_pos.y	,	seg.m_end.y		);
										
						p1.y *= yscale;
						p2.y *= yscale;
						
						// Scale the starting point
						
						Vec3f p = output_pos; p.y *= yscale;
						
						// Collide with these two points:
						
						bool collision = PointCollide(p,p1,radius,sq_radius); collision = collision || PointCollide(p,p2,radius,sq_radius);
						
						// Unscale the position of our point if there was a collision and save the result:
						
						if ( collision ){ p.y *= yinvscale; output_pos = p; }
					}				
				}				
			}
			
			/// Upper wall: see if we can collide with the points:
			
			case DoomPPSeg::SEG_TYPE_UPPER_WALL:
			{
				// Check and see:
				
				if ( output_pos.y > seg.m_upper_height - height )
				{
					// Scale the first and second points so that the bounding ellipse becomes a bounding sphere
					
					Vec3f p1 = Vec3f( seg.m_start.x	, output_pos.y	,	seg.m_start.y	);	
					Vec3f p2 = Vec3f( seg.m_end.x	, output_pos.y	,	seg.m_end.y		);
									
					p1.y *= yscale;
					p2.y *= yscale;
					
					// Scale the starting point
					
					Vec3f p = output_pos; p.y *= yscale;
					
					// Collide with these two points:
					
					bool collision = PointCollide(p,p1,radius,sq_radius); collision = collision || PointCollide(p,p2,radius,sq_radius);
					
					// Unscale the position of our point if there was a collision and save the result:
					
					if ( collision ){ p.y *= yinvscale; output_pos = p; }
				}				
			}
			
			/// Upper wall: see if we can collide with the points:
			
			case DoomPPSeg::SEG_TYPE_LOWER_UPPER_WALL:
			{
				// Check and see:
				
				if ( output_pos.y < seg.m_lower_height + height )
				{
					// See if we are below the wall: if so then treat the y position of the point as the camera y
					
					if ( output_pos.y > seg.m_lower_height )
					{				
						// Scale the first and second points so that the bounding ellipse becomes a bounding sphere
						
						Vec3f p1 = Vec3f( seg.m_start.x	, seg.m_lower_height	,	seg.m_start.y	);	
						Vec3f p2 = Vec3f( seg.m_end.x	, seg.m_lower_height	,	seg.m_end.y		);
										
						p1.y *= yscale;
						p2.y *= yscale;
						
						// Scale the starting point
						
						Vec3f p = output_pos; p.y *= yscale;
						
						// Collide with these two points:
						
						bool collision = PointCollide(p,p1,radius,sq_radius); collision = collision || PointCollide(p,p2,radius,sq_radius);
						
						// Unscale the position of our point if there was a collision and save the result:
						
						if ( collision ){ p.y *= yinvscale; output_pos = p; }
					}
					else
					{
						// Scale the first and second points so that the bounding ellipse becomes a bounding sphere
						
						Vec3f p1 = Vec3f( seg.m_start.x	, output_pos.y	,	seg.m_start.y	);	
						Vec3f p2 = Vec3f( seg.m_end.x	, output_pos.y	,	seg.m_end.y		);
										
						p1.y *= yscale;
						p2.y *= yscale;
						
						// Scale the starting point
						
						Vec3f p = output_pos; p.y *= yscale;
						
						// Collide with these two points:
						
						bool collision = PointCollide(p,p1,radius,sq_radius); collision = collision || PointCollide(p,p2,radius,sq_radius);
						
						// Unscale the position of our point if there was a collision and save the result:
						
						if ( collision ){ p.y *= yinvscale; output_pos = p; }					
					}				
				}
				
				// Check against the upper wall:
				
				if ( output_pos.y > seg.m_upper_height - height )
				{
					// Scale the first and second points so that the bounding ellipse becomes a bounding sphere
					
					Vec3f p1 = Vec3f( seg.m_start.x	, output_pos.y	,	seg.m_start.y	);	
					Vec3f p2 = Vec3f( seg.m_end.x	, output_pos.y	,	seg.m_end.y		);
									
					p1.y *= yscale;
					p2.y *= yscale;
					
					// Scale the starting point
					
					Vec3f p = output_pos; p.y *= yscale;
					
					// Collide with these two points:
					
					bool collision = PointCollide(p,p1,radius,sq_radius); collision = collision || PointCollide(p,p2,radius,sq_radius);
					
					// Unscale the position of our point if there was a collision and save the result:
					
					if ( collision ){ p.y *= yinvscale; output_pos = p; }
				}
			}		
		}
	}

	// Return the output
	
	return output_pos;
}

//=====================================================================================================================
/// @brief		Tells if the given point is within the given subsector
/// @param		subsector - subsector to check
/// @param		pos - position to check that is in the subsector
/// @returns	True if the point is within the subsector
//=====================================================================================================================

bool DoomCollision::WithinSubsector( const DoomGLSubsectorV2 & subsector, const Vec3f & pos ) const
{
	// Run through all the segs in the subsector and make sure we are on the right position of them:
	
	for ( unsigned i = 0 ; i < subsector.m_count ; ++i )
	{
		// Get this seg:
		
		const DoomPPSeg & seg = m_level->GetSeg(subsector.m_first_seg+i);
		
		// See if we are on the left side of it: if so then we are not in the subsector
		
		if ( seg.m_minus_n_dot_p + pos.Dot(seg.m_normal_3d) < 0 ) return false;
	}
	
	// If we got to there then we are within the subsector: return true
	
	return true;
}

//=====================================================================================================================
/// @brief		Recursively builds a list of subsectors that the given point is in or touching. Used for bounding 
///				sphere collision. The subsectors are stored in the main stack as pointers.
/// @param		pos - position of the point
/// @param		radius - bounding circle radius of the object
/// @returns	The number of potential collideers at the given tree node there is
//=====================================================================================================================

unsigned DoomCollision::BuildCollisionSubsectorsRecursive( const DoomPPNode & node , const Vec3f & pos , float radius ) const
{
	// Store the number of subsectors that we will do collisions for here

	unsigned subsector_count = 0;

	// See what side the point is on in relation to the plane- also, how far!

	float dot = node.m_minus_n_dot_p + pos.Dot(node.m_normal_3d);

	// See what side of the plane we are on:

	if ( dot >= 0 )
	{
		// See if we have a right subsector child

		if ( node.m_right_child )
		{
			// Intersecting/touching the right side also: add these subsectors to the subsector count

			subsector_count += BuildCollisionSubsectorsRecursive( * node.m_right_child, pos, radius );			
		}
		else if ( node.m_right_subsector )
		{
			// Got a right subsector: add this to the list of subsectors to be collided with

			m_stack->Push(node.m_right_subsector);

			// Increment the number of items added to the stack

			subsector_count++;
		}	
	
		// On the right side of the plane: see if we are intersecting the left also

		if ( dot < radius )
		{
			// Only if there is a left child:

			if ( node.m_left_child )
			{
				// Intersecting/touching the left side also: add these subsectors to the subsector count

				subsector_count += BuildCollisionSubsectorsRecursive( * node.m_left_child, pos, radius );
			}
			else if ( node.m_left_subsector )
			{
				// Got a left subsector: add this to the list of subsectors to be collided with

				m_stack->Push(node.m_left_subsector);

				// Increment the number of items added to the stack

				subsector_count++;
			}
		}
	}
	else
	{
		// See if we have a left subsector child

		if ( node.m_left_child )
		{
			// Intersecting/touching the left side also: add these subsectors to the subsector count

			subsector_count += BuildCollisionSubsectorsRecursive( * node.m_left_child, pos, radius );			
		}
		else if ( node.m_left_subsector )
		{
			// Got a left subsector: add this to the list of subsectors to be collided with

			m_stack->Push(node.m_left_subsector);

			// Increment the number of items added to the stack

			subsector_count++;
		}
			
		// On the left side of the plane: see if we are intersecting the right also

		if ( dot >= -radius )
		{
			// Only if there is a right child:

			if ( node.m_right_child )
			{
				// Intersecting/touching the right side also: add these subsectors to the subsector count

				subsector_count += BuildCollisionSubsectorsRecursive( * node.m_right_child, pos, radius );
			}
			else if ( node.m_right_subsector )
			{
				// Got a left subsector: add this to the list of subsectors to be collided with

				m_stack->Push(node.m_right_subsector);

				// Increment the number of items added to the stack

				subsector_count++;
			}
		}
	}

	// Return the number of subsectors where we might have a collision

	return subsector_count;
}

//=====================================================================================================================
/// @brief		Tells if one sector is potentially visible from another
/// @param		from - sector we are checking from
/// @param		to - sector we are checking that is visible from 'from'
/// @returns	True if 'to' is visible from 'from'
/// @pre		The lookup must not overflow the reject map
//=====================================================================================================================

bool DoomCollision::IsPotentiallyVisible( const DoomSector & from , const DoomSector & to ) const
{
	// Get the numbers of the two sectors:

	unsigned from_sec_num	= m_level->GetSectorNumber(from);
	unsigned to_sec_num		= m_level->GetSectorNumber(to);

	// Get the number of sectors in the level:

	unsigned sector_count	= m_level->GetSectorCount();

	// Calculate the index of the bit we are interested in from the reject map:

	unsigned bit_num = ( from_sec_num * sector_count ) + to_sec_num;

	// Get the index of the byte we are interested in:

	unsigned byte_num = bit_num / 8;

	// Clamp bit number:

	bit_num &= 7;

	// Now lookup the reject map for this bit:

	bool visible = ((*( m_level->GetRejectMap() + byte_num )) & ( 1 << bit_num )) != 0 ? false : true;

	// Return if visible

	return visible;
}
