448 lines
15 KiB
C++
448 lines
15 KiB
C++
/*
|
|
** 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;
|
|
}
|
|
|