401 lines
17 KiB
C++
401 lines
17 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.h $*
|
|
* *
|
|
* $Author:: Naty_h $*
|
|
* *
|
|
* $Modtime:: 3/28/01 11:29a $*
|
|
* *
|
|
* $Revision:: 5 $*
|
|
* *
|
|
*---------------------------------------------------------------------------------------------*
|
|
* Functions: *
|
|
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
|
|
|
/*
|
|
|
|
Most of the functions of this class are inline functions and if you use them you will need
|
|
to include <intersec.inl>.
|
|
|
|
Exceptions to this are the functions most commonly used by render objects:
|
|
|
|
|
|
|
|
The constructors/destructors are inline & implemented here.
|
|
|
|
*/
|
|
|
|
#if defined(_MSC_VER)
|
|
#pragma once
|
|
#endif
|
|
|
|
#ifndef INTERSEC_H
|
|
#define INTERSEC_H
|
|
|
|
#include "always.h"
|
|
#include "matrix3d.h"
|
|
#include "layer.h"
|
|
#include "sphere.h"
|
|
|
|
|
|
class RenderObjClass;
|
|
typedef unsigned short POLYGONINDEX;
|
|
|
|
|
|
/*
|
|
**
|
|
*/
|
|
class IntersectionResultClass
|
|
{
|
|
public:
|
|
RenderObjClass * IntersectedRenderObject;
|
|
POLYGONINDEX IntersectedPolygon;
|
|
|
|
Matrix3D ModelMatrix; // this is required for transforming mesh normals from model coords
|
|
Vector3 ModelLocation; // ditto
|
|
Vector3 Intersection; // location of intersection is placed here
|
|
|
|
float Range; // distance from ray to point of intersection
|
|
float Alpha, Beta; // stored for use by Process_Intersection_Results() - used to interpolate normal across a polygon
|
|
bool Intersects; // could be in the intersection_type, but it is used in a number of bool operations
|
|
|
|
enum INTERSECTION_TYPE {
|
|
NONE = 0,
|
|
GENERIC,
|
|
POLYGON
|
|
} IntersectionType;
|
|
};
|
|
|
|
|
|
class IntersectionClass
|
|
{
|
|
// member data
|
|
|
|
public:
|
|
enum {
|
|
MAX_POLY_INTERSECTION_COUNT = 1000, // arbitrary size of stack array used for storing intersection results within Intersect_Mesh(). Non-recursive function.
|
|
MAX_HIERARCHY_NODE_COUNT = 256
|
|
};
|
|
|
|
// this structure is used to store all intersections on the stack for sorting before
|
|
// copying the nearest intersection to IntersectionClassObject->Result.
|
|
// note: the convex intersection functions return with the first intersection results.
|
|
|
|
Vector3 *RayLocation; // note: these pointers must be Set() to valid pointers by external code
|
|
Vector3 *RayDirection;
|
|
Vector3 *IntersectionNormal; // if non-zero then Process_Intersection_Results() will place the (perhaps vertex interpolated) surface normal here.
|
|
|
|
// 2d screen coordinates for use by Intersect_Screen_Point...() routines.
|
|
float ScreenX, ScreenY;
|
|
|
|
// if true, then interpolate the normal for a polygon intersection from the vertex normals.
|
|
// note: intersection routines below which take a FinalResult argument do not interpolate
|
|
// the normal since they are intended to be used to find the nearest of several intersections
|
|
// and interpolating the normal for intersections that are tossed would be wasteful.
|
|
// If you need the normal interpolated in that case anyways then call Interpolate_Normal().
|
|
bool InterpolateNormal;
|
|
|
|
// if true, then perform potentially much faster convex intersection test which will return
|
|
// the first valid intersection. Generally used for producing silhouettes.
|
|
// If true, all intersections will be convex tests. If false, test mode will be determined (generally)
|
|
// by the render object or whatever called the intersection functions and passes the Convex argument.
|
|
bool ConvexTest;
|
|
|
|
// do not consider intersections beyond this range as an intersection.
|
|
// Note: Get_Screen_Ray sets this to scene->zstop.
|
|
float MaxDistance;
|
|
|
|
// final intersection results are contained here
|
|
IntersectionResultClass Result;
|
|
|
|
//
|
|
// Implementation
|
|
//
|
|
|
|
// configures the member data to use the passed pointers
|
|
inline void Set(Vector3 *location, Vector3 *direction, Vector3 *intersection_normal, bool interpolate_normal, float max_distance, bool convex_test = false)
|
|
{
|
|
RayLocation = location;
|
|
RayDirection = direction;
|
|
IntersectionNormal = intersection_normal;
|
|
InterpolateNormal = interpolate_normal;
|
|
MaxDistance = max_distance;
|
|
ConvexTest = convex_test;
|
|
}
|
|
|
|
|
|
|
|
// this constructor uses static variables for the location/direction/normal variables
|
|
// so can be only used one thread at a time unless the Set() function is used to
|
|
// set them to private vector3's
|
|
inline IntersectionClass()
|
|
: ConvexTest(false)
|
|
{
|
|
RayLocation = &_RayLocation;
|
|
RayDirection = &_RayDirection;
|
|
IntersectionNormal = &_IntersectionNormal;
|
|
}
|
|
|
|
|
|
// This will be the most commonly used constructor
|
|
inline IntersectionClass(Vector3 *location, Vector3 *direction, Vector3 *intersection_normal, bool interpolate_normal = false, float max_distance = WWMATH_FLOAT_MAX, bool convex_test = false)
|
|
{
|
|
Set(location, direction, intersection_normal, interpolate_normal, max_distance, convex_test);
|
|
}
|
|
|
|
|
|
virtual ~IntersectionClass() {}
|
|
|
|
|
|
// this copy routine is used when the model coords are needed to be copied along with the other information.
|
|
inline void IntersectionClass::Copy_Results(IntersectionResultClass *Destination, IntersectionResultClass *Source) {
|
|
Destination->ModelMatrix = Source->ModelMatrix;
|
|
Destination->ModelLocation = Source->ModelLocation;
|
|
Copy_Partial_Results(Destination, Source);
|
|
Destination->IntersectedRenderObject = Source->IntersectedRenderObject;
|
|
}
|
|
|
|
|
|
inline void IntersectionClass::Copy_Results(IntersectionResultClass *Source) {
|
|
Copy_Results(&Result, Source);
|
|
}
|
|
|
|
|
|
// this is called only for the nearest intersection. If the request passes a Interpolated_Normal pointer then it will be calculated.
|
|
// otherwise the results are copied into the request structure.
|
|
// This does not copy the matrix or location members; it is intended to be used during poly testing
|
|
// where these values are identical between results, or as a completion function for Copy_Results()
|
|
inline void IntersectionClass::Copy_Partial_Results(IntersectionResultClass *Destination, IntersectionResultClass *Source)
|
|
{
|
|
Destination->IntersectedPolygon = Source->IntersectedPolygon;
|
|
Destination->Intersection = Source->Intersection;
|
|
Destination->Range = Source->Range;
|
|
Destination->Alpha = Source->Alpha;
|
|
Destination->Beta = Source->Beta;
|
|
Destination->Intersects = true;
|
|
Destination->IntersectionType = Source->IntersectionType;
|
|
}
|
|
|
|
|
|
// used for creating temporary copies
|
|
inline IntersectionClass(IntersectionClass *source)
|
|
{
|
|
*this = source;
|
|
}
|
|
|
|
|
|
inline IntersectionClass *operator =(IntersectionClass *source)
|
|
{
|
|
Set(source->RayLocation, source->RayDirection, source->IntersectionNormal, source->InterpolateNormal, source->MaxDistance, source->ConvexTest);
|
|
Copy_Results(&source->Result);
|
|
return this;
|
|
}
|
|
|
|
|
|
|
|
// find the range to the intersection of the ray and sphere (if any)
|
|
// note: Intersection_Request->RayDirection must be a unit vector
|
|
// To find the actual intersection location and perhaps the intersection normal, use Intersection_Sphere() instead.
|
|
// loosly based on code found in Graphics Gems I, p388
|
|
// this will only set the result's range if intersection occurs; it is intended to be used as a first pass intersection test
|
|
// before intersecting the mesh polygons itself.
|
|
// Note: Does NOT do Max_Distance testing
|
|
inline bool IntersectionClass::Intersect_Sphere_Quick(SphereClass &Sphere, IntersectionResultClass *FinalResult)
|
|
{
|
|
// make a unit vector from the ray origin to the sphere center
|
|
Vector3 sphere_vector(Sphere.Center - *RayLocation);
|
|
|
|
// get the dot product between the sphere_vector and the ray vector
|
|
FinalResult->Alpha = Vector3::Dot_Product(sphere_vector, *RayDirection);
|
|
|
|
FinalResult->Beta = Sphere.Radius * Sphere.Radius - (Vector3::Dot_Product(sphere_vector, sphere_vector) - FinalResult->Alpha * FinalResult->Alpha);
|
|
|
|
if(FinalResult->Beta < 0.0f) {
|
|
return FinalResult->Intersects = false;
|
|
}
|
|
return FinalResult->Intersects = true;
|
|
}
|
|
|
|
|
|
// this will find the intersection with the sphere and the intersection normal if needed.
|
|
inline bool IntersectionClass::Intersect_Sphere(SphereClass &Sphere, IntersectionResultClass *FinalResult)
|
|
{
|
|
if(!Intersect_Sphere_Quick(Sphere, FinalResult))
|
|
return false;
|
|
|
|
// determine range to intersection based on stored alpha/beta values
|
|
float d = sqrtf(FinalResult->Beta);
|
|
FinalResult->Range = FinalResult->Alpha - d;
|
|
|
|
if(FinalResult->Range > MaxDistance) return false;
|
|
|
|
FinalResult->Intersection = *RayLocation + FinalResult->Range * (*RayDirection);
|
|
|
|
if(IntersectionNormal != 0) {
|
|
(*IntersectionNormal) = FinalResult->Intersection - Sphere.Center;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
|
|
// inline declarations
|
|
// Usage of these functions requires including intersec.inl
|
|
|
|
// determine location & direction for projected screen coordinate ray
|
|
inline void Get_Screen_Ray(float ScreenX, float ScreenY, const LayerClass &Layer);
|
|
|
|
// uses the Result's range & the Ray_Direction to calculate the actual point of intersection.
|
|
inline void Calculate_Intersection(IntersectionResultClass *Result);
|
|
|
|
// interpolate the normal for a polygon intersection. Will ONLY work for polygon intersections,
|
|
// and the Results.Intersection_Data must refer to a polygon with a valid ->mesh pointer.
|
|
inline void Interpolate_Intersection_Normal(IntersectionResultClass *FinalResult);
|
|
|
|
// various methods for performing intersections.
|
|
inline bool Intersect_Plane(IntersectionResultClass *Result, Vector3 &Plane_Normal, Vector3 &Plane_Point);
|
|
inline bool Intersect_Plane_Quick(IntersectionResultClass *Result, Vector3 &Plane_Normal, Vector3 &Plane_Point);
|
|
inline bool Intersect_Polygon(IntersectionResultClass *Result, Vector3 &PolygonNormal, Vector3 &v1, Vector3 &v2, Vector3 &v3);
|
|
inline bool Intersect_Polygon(IntersectionResultClass *Result, Vector3 &v1, Vector3 &v2, Vector3 &v3);
|
|
inline bool Intersect_Polygon_Z(IntersectionResultClass *Result, Vector3 &PolygonNormal, Vector3 &v1, Vector3 &v2, Vector3 &v3);
|
|
|
|
/*
|
|
** This function will fill the passed array with the set of points & uv values that represent
|
|
** the boolean operation of the anding of the ClipPoints with the TrianglePoints. The UV values
|
|
** provided for the TrianglePoints triangle are used to generate accurate UV values for any
|
|
** new points created by this operation.
|
|
** The clipped points have Z values that make them sit on the ClipPoints triangle plane.
|
|
*/
|
|
static inline int _Intersect_Triangles_Z(
|
|
Vector3 ClipPoints[3],
|
|
Vector3 TrianglePoints[3],
|
|
Vector2 UV[3],
|
|
Vector3 ClippedPoints[6],
|
|
Vector2 ClippedUV[6]
|
|
);
|
|
|
|
/*
|
|
** This function will find the z elevation for the passed Vector3 whose x/y components
|
|
** are defined, using the specified vertex & surface normal to determine the correct value
|
|
*/
|
|
static inline float _Get_Z_Elevation(Vector3 &Point, Vector3 &PlanePoint, Vector3 &PlaneNormal);
|
|
|
|
|
|
// test a 2d screen area with the intersection's screen coords, assigning a GENERIC intersection
|
|
// to the specified object.
|
|
inline bool Intersect_Screen_Object(IntersectionResultClass *Final_Result, Vector4 &Area, RenderObjClass *obj = 0);
|
|
|
|
|
|
// non-inlined declarations
|
|
|
|
|
|
// accumulates an object array for passing into Intersect_ObjectArray
|
|
void Append_Object_Array(int MaxCount, int &CurrentCount, RenderObjClass **ObjectArray, RenderObjClass *Object);
|
|
|
|
// traverses an RenderObjClass object and adds it's subobjects, potentially performing
|
|
// a quick sphere intersection test before adding.
|
|
void Append_Hierarchy_Objects(int MaxCount, int &CurrentCount, RenderObjClass **ObjectArray, RenderObjClass *Heirarchy, bool Test_Bounding_Spheres, bool Convex);
|
|
|
|
// top level intersection routines, most store intersection results in the Intersection.Result
|
|
// member structure and perform normal interpolation as a final step if indicated in the member data.
|
|
|
|
bool Intersect_Object_Array(int ObjectCount, RenderObjClass **ObjectArray,IntersectionResultClass *FinalResult, bool Test_Bounding_Sphere, bool Convex);
|
|
bool Intersect_Object_Array(int ObjectCount, RenderObjClass **ObjectArray,IntersectionResultClass *FinalResult, IntersectionResultClass *TemporaryResults, bool Test_Bounding_Sphere, bool Convex);
|
|
bool Intersect_RenderObject(RenderObjClass *RObj, IntersectionResultClass *FinalResult = 0);
|
|
bool Intersect_Screen_Point_RenderObject(float screen_x, float screen_y, const LayerClass &Layer, RenderObjClass *RObj, IntersectionResultClass *FinalResult);
|
|
|
|
bool Intersect_Screen_Point_Layer_Range(float ScreenX, float ScreenY, const LayerClass &TopLayer, const LayerClass &BackLayer);
|
|
bool Intersect_Screen_Point_Layer(float ScreenX, float ScreenY, const LayerClass &Layer);
|
|
bool Intersect_Layer(const LayerClass &Layer, bool Test_All = true);
|
|
|
|
// the various intersection routines, all of which store their intersection results
|
|
// in the passed Intersection_Result strucuture.
|
|
bool Intersect_Box(Vector3 &Box_Min, Vector3 &Box_Max, IntersectionResultClass *FinalResult);
|
|
bool Intersect_Hierarchy(RenderObjClass *Hierarchy, IntersectionResultClass *FinalResult, bool Test_Bounding_Sphere = true, bool Convex = false);
|
|
bool Intersect_Hierarchy_Sphere(RenderObjClass *Hierarchy, IntersectionResultClass *FinalResult);
|
|
bool Intersect_Hierarchy_Sphere_Quick(RenderObjClass *Hierarchy, IntersectionResultClass *FinalResult);
|
|
|
|
/*
|
|
** Identifies exactly what sub object of a render object is under the screen space vector
|
|
*/
|
|
RenderObjClass *Intersect_Sub_Object(float screenx, float screeny, LayerClass &layer, RenderObjClass *robj, IntersectionResultClass *result);
|
|
|
|
|
|
/*
|
|
** Functions related to determining if a 3d point is within a triangle.
|
|
*/
|
|
static inline void _Find_Polygon_Dominant_Plane(Vector3 &Normal, int &Axis_1, int &Axis_2);
|
|
static inline int _Largest_Normal_Index(Vector3 &v);
|
|
static inline bool _Point_In_Polygon(IntersectionResultClass *FinalResult, Vector3 &Normal, Vector3 &loc1, Vector3 &loc2, Vector3 &loc3);
|
|
static inline bool _Point_In_Polygon(IntersectionResultClass *FinalResult, Vector3 &loc1, Vector3 &loc2, Vector3 &loc3, int axis_1, int axis_2);
|
|
static inline bool _Point_In_Polygon(Vector3 &Point, Vector3 &loc1, Vector3 &loc2, Vector3 &loc3, int axis_1, int axis_2,float &Alpha,float &Beta);
|
|
static inline bool _Point_In_Polygon_Z(Vector3 &Point, Vector3 Corners[3]);
|
|
static inline bool _Point_In_Polygon_Z(Vector3 &Point, Vector3 &Corner1, Vector3 &Corner2, Vector3 &Corner3);
|
|
|
|
protected:
|
|
|
|
/*
|
|
** Find the intersection between two lines and interpolate the UV values for the intersection.
|
|
** Designed for use with _Intersect_Triangles_Z.
|
|
*/
|
|
//static inline void _Intersect_Lines_Z(Vector3 &A, Vector3 &B, Vector2 &UVStart, Vector2 &UVEnd, Vector3 &C, Vector3 &D, Vector3 ClippedPoints[6], Vector2 ClippedUV[6], int &DestIndex);
|
|
static inline bool IntersectionClass::In_Front_Of_Line
|
|
(
|
|
const Vector3 & p, // point to test
|
|
const Vector3 & e0, // point on edge
|
|
const Vector3 & de // direction of edge
|
|
);
|
|
|
|
static inline float IntersectionClass::Intersect_Lines
|
|
(
|
|
const Vector3 & p0, // start of line segment
|
|
const Vector3 & p1, // end of line segment
|
|
const Vector3 & e0, // point on clipping edge
|
|
const Vector3 & de // direction of clipping edge
|
|
);
|
|
|
|
static inline int IntersectionClass::Clip_Triangle_To_LineXY(
|
|
int incount,
|
|
Vector3 * InPoints,
|
|
Vector2 * InUVs,
|
|
Vector3 * OutPoints,
|
|
Vector2 * OutUVs,
|
|
const Vector3 & edge_point0,
|
|
const Vector3 & edge_point1
|
|
);
|
|
|
|
|
|
|
|
inline float Plane_Z_Distance(Vector3 &PlaneNormal, Vector3 &PlanePoint);
|
|
inline void Transform_Model_To_World_Coords(IntersectionResultClass *FinalResult);
|
|
|
|
/*
|
|
** Static vars available for use by temporary intersection class objects.
|
|
*/
|
|
static Vector3 _RayLocation, _RayDirection, _IntersectionNormal;
|
|
|
|
};
|
|
|
|
|
|
#endif
|