Renegade/Code/ww3d2/intersec.cpp

/*
**	Command & Conquer Renegade(tm)
**	Copyright 2025 Electronic Arts Inc.
**
**	This program is free software: you can redistribute it and/or modify
**	it under the terms of the GNU General Public License as published by
**	the Free Software Foundation, either version 3 of the License, or
**	(at your option) any later version.
**
**	This program is distributed in the hope that it will be useful,
**	but WITHOUT ANY WARRANTY; without even the implied warranty of
**	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
**	GNU General Public License for more details.
**
**	You should have received a copy of the GNU General Public License
**	along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

/***********************************************************************************************
 ***              C O N F I D E N T I A L  ---  W E S T W O O D  S T U D I O S               ***
 ***********************************************************************************************
 *                                                                                             *
 *                 Project Name : G                                                            *
 *                                                                                             *
 *                     $Archive:: /Commando/Code/ww3d2/intersec.cpp                           $*
 *                                                                                             *
 *                      $Author:: Greg_h                                                      $*
 *                                                                                             *
 *                     $Modtime:: 2/06/01 5:41p                                               $*
 *                                                                                             *
 *                    $Revision:: 3                                                           $*
 *                                                                                             *
 *---------------------------------------------------------------------------------------------*
 * Functions:                                                                                  *
 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */



#include "intersec.h"
#include "camera.h"
#include "scene.h"
#include "intersec.inl"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

// these statics are used for single-threaded use of the IntersectionClass ONLY
Vector3 IntersectionClass::_RayLocation(0,0,0);
Vector3 IntersectionClass::_RayDirection(0,0,0);
Vector3 IntersectionClass::_IntersectionNormal(0,0,0);


bool IntersectionClass::Intersect_Screen_Point_RenderObject(float screen_x, float screen_y, const LayerClass &Layer, RenderObjClass *RObj, IntersectionResultClass *FinalResult)
{
	Get_Screen_Ray(screen_x, screen_y, Layer);
	return Intersect_RenderObject(RObj, FinalResult);
}

bool IntersectionClass::Intersect_RenderObject(RenderObjClass *RObj, IntersectionResultClass *FinalResult)
{
	if(FinalResult == 0)
		FinalResult = &Result;

	return RObj->Intersect(this, FinalResult);
}
	
// iterate through the layers of a world, front to back, returning true if/when an intersection
// with an object occurs.
bool IntersectionClass::Intersect_Screen_Point_Layer_Range
(
	float screen_x,
	float screen_y, 
	const LayerClass &TopLayer, 
	const LayerClass &BackLayer
)
{

	// intersect from front layer to back layers. An intersection with an object
	// in any layer is assumed to be in front of any potential intersections in layers
	// below it.

	// find the last layer in the list
	const LayerClass *Layer = &TopLayer;

	// iterate through all layers in list
	while(Layer->Is_Valid()) {
		if(Intersect_Screen_Point_Layer(screen_x, screen_y, *Layer))
			return true;

		// if this is the back layer then that is all we need to test
		if(Layer == &BackLayer) 
			return false;

		Layer = Layer->Next();
	}
	return false;
}


bool IntersectionClass::Intersect_Screen_Point_Layer(float screen_x, float screen_y, const LayerClass &Layer)
{
	// mark this object as not intersecting yet
	Result.Intersects = false;

	// first, do a test to make sure the screen coords are within the rendering area for this layer.
	const ViewportClass &v = Layer.Camera->Get_Viewport();

	if((screen_x < v.Min.X) ||
		(screen_x > v.Max.X)  ||
		(screen_y < v.Min.Y) ||
		(screen_y > v.Max.Y))
		return false;

	Result.Range = Layer.Camera->Get_Depth(); //scene->depth * scene->zstop;

	// get the ray for these screen coordinates
	Get_Screen_Ray(screen_x, screen_y, Layer);

	return Intersect_Layer(Layer, false);
}

bool IntersectionClass::Intersect_Layer(const LayerClass &Layer, bool Test_All)
{
	IntersectionResultClass FinalResult;

	Result.Intersects = false;

	SceneIterator *it = Layer.Scene->Create_Iterator(!Test_All);

	// select the first object
	it->First();

	// loop through all render objects in this layer:
	while(!it->Is_Done()) {

		// get the render object
		RenderObjClass * robj = it->Current_Item();
		it->Next();

		// only intersect if it was visible or if we must test all in layer
		if((Test_All || robj->Is_Really_Visible()) && robj->Intersect(this, &FinalResult)) {
			if(FinalResult.Range < Result.Range) {
				Copy_Results(&FinalResult);
			}
		}
	}

	Layer.Scene->Destroy_Iterator(it);

	return Result.Intersects;
}


void IntersectionClass::Append_Object_Array(
	int MaxCount, 
	int &CurrentCount, 
	RenderObjClass **ObjectArray,
	RenderObjClass *Object)
{
	if(CurrentCount < MaxCount) {
		ObjectArray[CurrentCount] = Object;
		CurrentCount++;
		return;
	}
	WWDEBUG_SAY(("IntersectionClass::Append_Object_Array - Too many objects\n"));
}

// determines if specified plane-intersection point (co-planar with polygon) is within the the passed polygon.
// If Interpolated_Normal is specified, it will interpolate the normal for the intersection point
// note: Polygon normal MUST BE CORRECT

// this will return true if the ray intersects the specified box
// sets the point of intersection within the Request->Result.Intersection vector
bool IntersectionClass::Intersect_Box(Vector3 &Box_Min, Vector3 &Box_Max, IntersectionResultClass *FinalResult) {
	// Fast Ray-Box Intersection, modified from code written by Andrew Woo from "Graphics Gems", Academic Press, 1990

	enum {
		RIGHT = 0,
		LEFT,
		MIDDLE,
		PLANE_COUNT
	};

	bool inside = true;
	char quadrant[PLANE_COUNT];
	int counter;
	float distance[PLANE_COUNT];
	float candidate_plane[PLANE_COUNT];
	
	register Vector3 *intersection = &FinalResult->Intersection;
	
	// Find candidate planes and determine if the ray is outside the box
	for (counter = 0; counter < PLANE_COUNT; counter++) {
		if((*RayLocation)[counter] < Box_Min[counter]) {
			quadrant[counter] = LEFT;
			candidate_plane[counter] = Box_Min[counter];
			inside = false;
		} else {
			if ((*RayLocation)[counter] > Box_Max[counter]) {
				quadrant[counter] = RIGHT;
				candidate_plane[counter] = Box_Max[counter];
				inside = false;
			} else {
				quadrant[counter] = MIDDLE;
			}
		}
	}
	
	// check to see if the ray origin is inside bounding box
	if(inside)	{
		*intersection = *RayLocation;
		return FinalResult->Intersects = true;
	}
	
	// Calculate distances to candidate planes
	for (counter = 0; counter < PLANE_COUNT; counter++) {
		if ((quadrant[counter] != MIDDLE) && ((*RayDirection)[counter] != 0.0f))
			distance[counter] = (candidate_plane[counter] - (*RayLocation)[counter]) / (*RayDirection)[counter];
		else
			distance[counter] = -1.0f;
	}

	// get the largest of the distances for final choice of intersection
	int nearest_plane = 0;
	for (counter = 1; counter < PLANE_COUNT; counter++) {
		if (distance[nearest_plane] < distance[counter])
			nearest_plane = counter;
	}	

	// Check to make sure the nearest plane is not behind the ray (inside box tested above)
	if (distance[nearest_plane] < 0.0f) 
		return FinalResult->Intersects = false;

	for (counter = 0; counter < PLANE_COUNT; counter++) {
		if (nearest_plane != counter) {
			(*intersection)[counter] = (*RayLocation)[counter] + distance[nearest_plane] *(*RayDirection)[counter];
			if ((*intersection)[counter] < Box_Min[counter] || (*intersection)[counter] > Box_Max[counter])
				return FinalResult->Intersects = false;
		} else {
			(*intersection)[counter] = candidate_plane[counter];
		}
	}
	return FinalResult->Intersects = true; // ray hits box
}	


// simply returns true if a ray hits the bounding sphere of any node in a hierarchy
// note: Result will only contain range, not the intersection point/normal.
bool IntersectionClass::Intersect_Hierarchy_Sphere_Quick(RenderObjClass *Hierarchy, IntersectionResultClass *FinalResult) 
{
	
	int counter = Hierarchy->Get_Num_Sub_Objects();
	while(counter--) {
		RenderObjClass *obj = Hierarchy->Get_Sub_Object(counter);
		obj->Release_Ref(); // you already own a reference to this object indirectly..
		if(obj->Intersect_Sphere_Quick(this, FinalResult))
			return true;
	}
	return false;
}

// returns true if a ray hits the bounding sphere of any node in a hierarchy
// note: Result will contain range and the intersection point/normal.
bool IntersectionClass::Intersect_Hierarchy_Sphere(RenderObjClass *Hierarchy, IntersectionResultClass *FinalResult) {
	
	int counter = Hierarchy->Get_Num_Sub_Objects();
	while(counter--) {
		RenderObjClass *obj = Hierarchy->Get_Sub_Object(counter);
		obj->Release_Ref(); // you already own a reference to this object indirectly..
		if(obj->Intersect_Sphere(this, FinalResult))
			return true;
	}
	return false;
}

void IntersectionClass::Append_Hierarchy_Objects(
	int MaxCount, 
	int &CurrentCount, 
	RenderObjClass **ObjectArray, 
	RenderObjClass *Hierarchy,
	bool Test_Bounding_Sphere,
	bool Convex)
{
	IntersectionResultClass result;

	// first check the bounding spheres for hits (if specified)
	int counter = Hierarchy->Get_Num_Sub_Objects();
	if(Test_Bounding_Sphere) {
		while(counter--) {
			RenderObjClass *obj = Hierarchy->Get_Sub_Object(counter);
			obj->Release_Ref();	// you already own a reference to the object indirectly
			if(obj->Intersect_Sphere_Quick(this, &result)) {
				Append_Object_Array(MaxCount, CurrentCount, ObjectArray, obj);
//				OutputDebugString("o"); // this shows one o per sphere intersection
			} else {
//				OutputDebugString("."); // this shows one . per sphere miss
			}
		}

	} else {
		// simply copy the pointers into the array
		while(counter--) {
			RenderObjClass *obj = Hierarchy->Get_Sub_Object(counter);
			Append_Object_Array(MaxCount, CurrentCount, ObjectArray, obj);
			obj->Release_Ref(); // you already own a reference to this object indirectly..
		}
	}
}

bool IntersectionClass::Intersect_Hierarchy(RenderObjClass *Hierarchy, IntersectionResultClass *FinalResult, bool Test_Bounding_Sphere, bool Convex ) {

//	OutputDebugString("\n");
//	return FinalResult->Intersects = false;

	RenderObjClass *candidate_objects[MAX_HIERARCHY_NODE_COUNT];
	int candidate_count =  0;

	Append_Hierarchy_Objects(MAX_HIERARCHY_NODE_COUNT, candidate_count, candidate_objects, Hierarchy, Test_Bounding_Sphere, Convex);

	// make sure there's at least one sphere hit before continuing to more expensive tests below..
	if(candidate_count == 0) {
	//			OutputDebugString("/"); // no sphere intersections
		return FinalResult->Intersects = false; 
	}

	// note: Test_Bounding_Sphere argument is false because the Append_Hierarchy_Objects will have
	// already performed that test if indicated.
	if(Intersect_Object_Array(candidate_count, candidate_objects, FinalResult, false, Convex)) {
		return true;
	}
	return false;
}

RenderObjClass *IntersectionClass::Intersect_Sub_Object(float screenx, float screeny, LayerClass &layer, RenderObjClass *robj, IntersectionResultClass *result)
{
	if (robj->Get_Num_Sub_Objects()) {
		for (int lp = 0; lp < robj->Get_Num_Sub_Objects(); lp++) {
			RenderObjClass *sub = robj->Get_Sub_Object(lp);
			RenderObjClass *retval = Intersect_Sub_Object(screenx, screeny, layer, sub, result);
			sub->Release_Ref();
			if (retval) return retval;
		}
	}
	if (Intersect_Screen_Point_RenderObject(screenx, screeny, layer, robj, result)) {
		return robj;
	}
	return NULL;
}

// finds the intersection of the nearest object in the array.
// This will usually be the last stage after determining potential intersections
// using Intersect_Sphere_Quick() and adding hits to the array for this
// more accurate test, as done in Intersect_Heirarchy().
bool IntersectionClass::Intersect_Object_Array(
	int Object_Count,
	RenderObjClass **ObjectArray,
	IntersectionResultClass *FinalResult, 
	bool Test_Bounding_Sphere, 
	bool Convex
	)
{
	IntersectionResultClass TemporaryResults[MAX_HIERARCHY_NODE_COUNT];
	assert(Object_Count <= MAX_HIERARCHY_NODE_COUNT);
	return Intersect_Object_Array(Object_Count, ObjectArray, FinalResult, TemporaryResults, Test_Bounding_Sphere, Convex);
}

bool IntersectionClass::Intersect_Object_Array(
	int Object_Count,
	RenderObjClass **ObjectArray,
	IntersectionResultClass *FinalResult, 
	IntersectionResultClass *TemporaryResults,
	bool Test_Bounding_Sphere, 
	bool Convex
	)
{
	//  Determine ranges for all intersections
	IntersectionClass temp(this);
	int counter = Object_Count;
	bool hit = false;

	// if it's a convex hierarchy (ie a control panel) then find the first hit otherwise use the more expensive exact intersection routine
	// for use with potentially concave hierarchies.
	int nearest_index = -1;
	if(ConvexTest || Convex) {
		if(Test_Bounding_Sphere) {
			while(counter--) {
				if(ObjectArray[counter]->Intersect_Sphere_Quick(this, &TemporaryResults[counter])) {
					hit = ObjectArray[counter]->Intersect(this, FinalResult);
				}
				if(hit) {
					nearest_index = counter;
					counter = 0;
				}
			}		
		} else {
			while(counter--) {
				hit = ObjectArray[counter]->Intersect(this, FinalResult);
				if(hit) {
					nearest_index = counter;
					counter = 0;
				}
			}		
		}
	} else {
		if(Test_Bounding_Sphere) {
			while(counter--) {
				if(ObjectArray[counter]->Intersect_Sphere_Quick(this, &TemporaryResults[counter])) {
					hit |= ObjectArray[counter]->Intersect(this, &TemporaryResults[counter]);
				}
			}
		} else {
			while(counter--) {
				hit |= ObjectArray[counter]->Intersect(this, &TemporaryResults[counter]);
			}		
		}
	}
	// test to see if anything actually hit a mesh
	if( ! hit ) {
//		OutputDebugString("!"); // no mesh intersections 
		return FinalResult->Intersects = false; 
	}

	if(! (Convex || ConvexTest)) {
		// now find the nearest of the actual hits
		float nearest_range = (float) (2<<28);
		counter = Object_Count;
		while(counter--) {
			if(TemporaryResults[counter].Intersects && (nearest_range > TemporaryResults[counter].Range)) {
				nearest_index = counter;
				nearest_range = TemporaryResults[counter].Range;
			}
		}
		Copy_Results(FinalResult, &TemporaryResults[nearest_index]);
	}
//	OutputDebugString("+");	
//	Debug.Print("Mesh ", Object_Array[nearest_index]);
//	Intersection_Node = candidate_indices[nearest_index];
	return true;
}