/* ** 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 . */ /*********************************************************************************************** *** 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; }