This repository has been archived on 2025-02-27. You can view files and clone it, but cannot push or open issues or pull requests.
CnC_Renegade/Code/ww3d2/intersec.cpp

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;
}