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.h

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