tiberium/CnC_Renegade
Archived
2
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
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/WWMath/colmathaabox.cpp

598 lines
26 KiB
C++
Raw Permalink Blame History

/*
** 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 : WWMath *
* *
* $Archive:: /Commando/Code/wwmath/colmathaabox.cpp $*
* *
* Author:: Greg Hjelstrom *
* *
* $Modtime:: 10/31/02 11:27a $*
* *
* $Revision:: 24 $*
* *
*---------------------------------------------------------------------------------------------*
* Functions: *
* CollisionMath::Intersection_Test -- Test intersection between two AABoxes *
* CollisionMath::Overlap_Test -- Tests overlap between an AABox and a sphere *
* CollisionMath::Overlap_Test -- Tests overlap between an AABox and a triangle *
* CollisionMath::Overlap_Test -- Tests overlap between an AABox and a line segment *
* CollisionMath::Collide -- Collision test for a moving AABox and a plane *
* aab_separation_test -- tests two AAB's for separation on an axis *
* CollisionMath::Collide -- Collision test for two moving AABoxes *
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
#include "colmath.h"
#include "colmathinlines.h"
#include "aaplane.h"
#include "plane.h"
#include "lineseg.h"
#include "tri.h"
#include "sphere.h"
#include "aabox.h"
#include "obbox.h"
#include "wwdebug.h"
/***********************************************************************************************
* CollisionMath::Intersection_Test -- Test intersection between two AABoxes *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 11/19/99 gth : Created. *
*=============================================================================================*/
bool CollisionMath::Intersection_Test(const AABoxClass & box,const AABoxClass & box2)
{
Vector3 dc = box2.Center - box.Center;
if (box.Extent.X + box2.Extent.X < WWMath::Fabs(dc.X)) return false;
if (box.Extent.Y + box2.Extent.Y < WWMath::Fabs(dc.Y)) return false;
if (box.Extent.Z + box2.Extent.Z < WWMath::Fabs(dc.Z)) return false;
return true;
}
/***********************************************************************************************
* CollisionMath::Overlap_Test -- Tests overlap between an AABox and a sphere *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 11/19/99 gth : Created. *
*=============================================================================================*/
CollisionMath::OverlapType CollisionMath::Overlap_Test(const AABoxClass & box,const SphereClass & sphere)
{
// TODO: this function seems incorrect. Not currently using it though
Vector3 dist = sphere.Center - box.Center;
Vector3 extent;
extent.X = box.Extent.X + sphere.Radius;
extent.Y = box.Extent.Y + sphere.Radius;
extent.Z = box.Extent.Z + sphere.Radius;
//
// Check to see if the sphere is completely outside the box
//
if (WWMath::Fabs(dist.X) > extent.X) return OUTSIDE;
if (WWMath::Fabs(dist.Y) > extent.Y) return OUTSIDE;
if (WWMath::Fabs(dist.Z) > extent.Z) return OUTSIDE;
return INSIDE;
}
/***********************************************************************************************
* CollisionMath::Overlap_Test -- Tests overlap between an AABox and a line segment *
* *
* This function uses separating axes to determine whether an AABox and a line segment overlap *
* I wrote it when we found that ray-casting was taking a huge amount of time in Renegade. *
* Here are some statistics comparing this function to the previous function which used the *
* same algorithm that Collide(box,ray) uses. *
* *
* collide algorithm (Gems) separating axis (this one) *
* ----------------------------------------------------------------------------------------- *
* number of tests 10000 10000 *
* avg cycles 641 464 *
* outside cycles 652 390 *
* overlap cycles 610 683 *
* *
* The idea for this test is that it will early-exit when it can while the old test can't. *
* When we are passing a ray down our culling trees, it is common to encounter boxes that *
* are not intersecting the ray. The faster we can reject these, the better! *
* *
* INPUT: *
* box - box to test *
* line - line to test *
* *
* OUTPUT: *
* overlap status of the line with respect to the box, either INSIDE, OUTSIDE, or OVERLAPPED *
* *
* WARNINGS: *
* *
* HISTORY: *
* 11/19/99 gth : Created. *
*=============================================================================================*/
CollisionMath::OverlapType CollisionMath::Overlap_Test(const AABoxClass & box,const LineSegClass & line)
{
// If both endpoints are in, return INSIDE
// If either was inside, return OVERLAPPED
int inside_point_count = 0;
if (CollisionMath::Overlap_Test(box,line.Get_P0()) == INSIDE) inside_point_count++;
if (CollisionMath::Overlap_Test(box,line.Get_P1()) == INSIDE) inside_point_count++;
if (inside_point_count == 2) {
return INSIDE;
} else if (inside_point_count == 1) {
return OVERLAPPED;
} else {
// Here I'm using the separating axis theorem to test if the line-segment
// and the box can be separated by a plane. Any two convex objects that are
// not intersecting can be separated by a plane defined by either a
// face normal from one of the objects or the cross-product of an edge from
// each object. In the case of an axis-aligned box and a line-segment, we
// have to check the three coordinate axes and the cross product between
// each and the direction vector of the line segment.
//
// Here is the general test for an arbitrary axis:
// -----------------------------------------------
// box_proj = fabs(extent.X*axis.X) + fabs(extent.Y*axis.Y) + fabs(extent.Z*axis.Z)
// p0_proj = fabs(dot_product(dp0,axis))
// dp_proj = fabs(dot_product(dp,axis))
// if (p0_proj > 0) {
// if (p0_proj > box_proj - WWMath::Min(dp_proj,0.0f)) return OUTSIDE;
// } else {
// if (-p0_proj > box_proj + WWMath::Max(dp_proj,0.0f)) return OUTSIDE;
// }
//
// In practice, there are optimizations you can make on each of the axes that
// we need to test (see below).
float box_proj,p0_proj,dp_proj;
Vector3 dp0;
Vector3::Subtract(line.Get_P0(),box.Center,&dp0);
// Project box and line onto the x-axis
// Since I know the axis is the x-axis, just take the x components of each
// vector instead of doing the dot-product. The projection of 'dp' is only
// counted if it points towards the center of the box (i.e. it decreases the
// chances of them being separated...)
box_proj = box.Extent.X;
p0_proj = dp0.X;
dp_proj = line.Get_DP().X;
if (p0_proj > 0) {
if (p0_proj > box_proj - WWMath::Min(dp_proj,0.0f)) return OUTSIDE;
} else {
if (-p0_proj > box_proj + WWMath::Max(dp_proj,0.0f)) return OUTSIDE;
}
// Project box and line onto the y-axis
box_proj = box.Extent.Y;
p0_proj = dp0.Y;
dp_proj = line.Get_DP().Y;
if (p0_proj > 0) {
if (p0_proj > box_proj - WWMath::Min(dp_proj,0.0f)) return OUTSIDE;
} else {
if (-p0_proj > box_proj + WWMath::Max(dp_proj,0.0f)) return OUTSIDE;
}
// Project box and line onto the z-axis
box_proj = box.Extent.Z;
p0_proj = dp0.Z;
dp_proj = line.Get_DP().Z;
if (p0_proj > 0) {
if (p0_proj > box_proj - WWMath::Min(dp_proj,0.0f)) return OUTSIDE;
} else {
if (-p0_proj > box_proj + WWMath::Max(dp_proj,0.0f)) return OUTSIDE;
}
// Project box and line onto (x cross line)
// I'm manually optimizing the cross-product and taking advantage of the fact
// that 'dp' will always project to zero for this axis.
Vector3 axis;
axis.Set(0,-line.Get_Dir().Z,line.Get_Dir().Y); // == (1,0,0) cross (x,y,z)
box_proj = WWMath::Fabs(axis.Y*box.Extent.Y) + WWMath::Fabs(axis.Z*box.Extent.Z);
p0_proj = Vector3::Dot_Product(axis,dp0);
if (WWMath::Fabs(p0_proj) > box_proj) return OUTSIDE;
// Project box and line onto (y cross line)
axis.Set(line.Get_Dir().Z,0,-line.Get_Dir().X); // == (0,1,0) cross (x,y,z)
box_proj = WWMath::Fabs(axis.X*box.Extent.X) + WWMath::Fabs(axis.Z*box.Extent.Z);
p0_proj = Vector3::Dot_Product(axis,dp0);
if (WWMath::Fabs(p0_proj) > box_proj) return OUTSIDE;
// Project box and line onto (z cross line)
axis.Set(-line.Get_Dir().Y,line.Get_Dir().X,0); // == (0,0,1) cross (x,y,z)
box_proj = WWMath::Fabs(axis.X*box.Extent.X) + WWMath::Fabs(axis.Y*box.Extent.Y);
p0_proj = Vector3::Dot_Product(axis,dp0);
if (WWMath::Fabs(p0_proj) > box_proj) return OUTSIDE;
}
return OVERLAPPED;
}
#if 0 // Alternate Overlap Test for AABox-Ray
CollisionMath::OverlapType CollisionMath::Overlap_Test(const AABoxClass & box,const LineSegClass & line)
{
// If both endpoints are in, return INSIDE
// If either was inside, return OVERLAPPED
int inside_point_count = 0;
if (CollisionMath::Overlap_Test(box,line.Get_P0()) == INSIDE) inside_point_count++;
if (CollisionMath::Overlap_Test(box,line.Get_P1()) == INSIDE) inside_point_count++;
if (inside_point_count == 2) {
return INSIDE;
} else if (inside_point_count == 1) {
return OVERLAPPED;
} else {
// Now we know that both points are outside of the box so we
// have to detect if the ray penetrates the box.
// I found this algorithm in one of the GEMS books...
Vector3 boxmin,boxmax;
Vector3::Subtract(box.Center,box.Extent,&boxmin);
Vector3::Add(box.Center,box.Extent,&boxmax);
float candidateplane[3]; // candidate intersection plane distance for each axis
float maxt[3]; // t value along the ray for each axis
Vector3 coord; // intersection point
const int BOX_SIDE_NEGATIVE = -1;
const int BOX_SIDE_MIDDLE = 0;
const int BOX_SIDE_POSITIVE = 1;
int quadrant[3];
for (int i=0; i<3; i++) {
if (line.Get_P0()[i] < boxmin[i]) {
quadrant[i] = BOX_SIDE_NEGATIVE;
candidateplane[i] = boxmin[i];
} else if (line.Get_P0()[i] > boxmax[i]) {
quadrant[i] = BOX_SIDE_POSITIVE;
candidateplane[i] = boxmax[i];
} else {
quadrant[i] = BOX_SIDE_MIDDLE;
}
}
// Calculate the 3 distances to the candidate planes
for (i=0; i<3; i++) {
if (quadrant[i] != BOX_SIDE_MIDDLE && line.Get_DP()[i] != 0.0f) {
maxt[i] = (candidateplane[i] - line.Get_P0()[i]) / line.Get_DP()[i];
} else {
maxt[i] = -1.0f;
}
}
// Get the largest of the maxt's for the final choice of intersection
int intersection_plane = 0;
for (i=1; i<3; i++) {
if (maxt[i] > maxt[intersection_plane]) {
intersection_plane = i;
}
}
// If the ray is "in front" of all of the planes, return
if (maxt[intersection_plane] < 0.0f) {
return OUTSIDE;
}
// If the intersection is beyond the end of the ray, return
if (maxt[intersection_plane] > 1.0f) {
return OUTSIDE;
}
// Check if the ray is inside the box, i.e. on the two planes which
// are not the intersection planes, the intersection point should
// be between the min and max of the box.
for (i=0; i<3; i++) {
if (intersection_plane != i) {
coord[i] = line.Get_P0()[i] + maxt[intersection_plane] * line.Get_DP()[i];
if ((coord[i] < boxmin[i]) || (coord[i] > boxmax[i])) {
return OUTSIDE; // ray is outside the box
}
} else {
coord[i] = candidateplane[i];
}
}
}
return OVERLAPPED;
}
#endif // Alternate Overlap Test for AABox-Ray
/***********************************************************************************************
* CollisionMath::Overlap_Test -- Tests overlap between an AABox and a triangle *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 11/19/99 gth : Created. *
*=============================================================================================*/
CollisionMath::OverlapType CollisionMath::Overlap_Test(const AABoxClass & box,const TriClass & tri)
{
CastResultStruct res;
CollisionMath::Collide(box,Vector3(0,0,0),tri,&res);
return eval_overlap_collision(res);
}
/***********************************************************************************************
* CollisionMath::Collide -- Collision test for a moving AABox and a plane *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 11/19/99 gth : Created. *
*=============================================================================================*/
bool CollisionMath::Collide
(
const AABoxClass & box,
const Vector3 & move_vector,
const PlaneClass & plane,
CastResultStruct * result
)
{
float frac;
float extent = box.Project_To_Axis(plane.N);
float dist = Vector3::Dot_Product(plane.N,box.Center) + plane.D;
float move = Vector3::Dot_Product(plane.N,move_vector);
if (dist > extent) {
if (dist + move > extent) {
// entire move ok!
frac = 1.0f;
} else {
// partial move allowed
frac = (extent - dist) / move;
}
} else if (dist < -extent) {
if (dist + move < -extent) {
// entire move ok!
frac = 1.0f;
} else {
// partial move allowed
frac = (-extent - dist) / move;
}
} else {
result->StartBad = true;
result->Normal = plane.N;
return true;
}
if (frac < result->Fraction) {
result->Fraction = frac;
result->Normal = plane.N;
if (result->ComputeContactPoint) {
Vector3 move_dir(move_vector);
move_dir.Normalize();
float move_extent = Vector3::Dot_Product(box.Extent,move_dir);
result->ContactPoint = box.Center + result->Fraction * move_vector + move_extent * move_dir;
}
return true;
}
return false;
}
/*
** AABCollisionStruct
** Contains all of the intermediate and temporary values used by
** the set of functions used in detecting collisions for aab's
*/
struct AABCollisionStruct
{
AABCollisionStruct(const AABoxClass &box0,const Vector3 &move0,const AABoxClass & box1,const Vector3 &move1) :
StartBad(true), // Startbad is true until one of the axes clears it
AxisId(-1), // AxisId will be the axis that allowed the longest move
MaxFrac(0.0f), // MaxFrac is the longest allowed move so far
Box0(box0),
Box1(box1)
{
Vector3::Subtract(box1.Center,box0.Center,&C); // vector from center of box0 to center of box1
Vector3::Subtract(move1,move0,&M); // move vector relative to stationary box0
}
bool StartBad; // Inital configuration is intersecting?
float MaxFrac; // Longest move allowed so far
int AxisId; // Last separating axis
int Side; // which side of the interval
Vector3 C; // Vector from the center0 to center1
Vector3 M; // Move vector relative to stationary box0
const AABoxClass & Box0;
const AABoxClass & Box1;
private:
//not implemented
AABCollisionStruct(const AABCollisionStruct&);
AABCollisionStruct & operator = (const AABCollisionStruct&);
};
/***********************************************************************************************
* aab_separation_test -- tests two AAB's for separation on an axis *
* *
* This function is very similar to the obb_separation_test. If a flaw is found in either, *
* we should update the other... *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 11/19/99 gth : Created. *
*=============================================================================================*/
static inline bool aab_separation_test
(
AABCollisionStruct & context,
int axis
)
{
// ra = box0 projection onto the axis
// rb = box1 projection onto the axis
// u0 = projected distance between the box centers at t0
// u1 = projected distance between the box centers at t1
float ra = context.Box0.Extent[axis];
float rb = context.Box1.Extent[axis];
float u0 = context.C[axis];
float u1 = u0 + context.M[axis];
float tmp;
float rsum = ra+rb;
if ( u0 + WWMATH_EPSILON > rsum ) {
context.StartBad = false;
if ( u1 > rsum ) {
context.MaxFrac = 1.0f;
return true;
} else {
tmp = (rsum-u0)/(u1-u0);
if ( tmp > context.MaxFrac ) {
context.MaxFrac = tmp;
context.AxisId = axis;
context.Side = +1;
}
}
} else if ( u0 - WWMATH_EPSILON < -rsum ) {
context.StartBad = false;
if ( u1 < -rsum ) {
context.MaxFrac = 1.0f;
return true;
} else {
tmp = (-rsum-u0)/(u1-u0);
if ( tmp > context.MaxFrac ) {
context.MaxFrac = tmp;
context.AxisId = axis;
context.Side = -1;
}
}
}
return false;
}
/***********************************************************************************************
* CollisionMath::Collide -- Collision test for two moving AABoxes *
* *
* this function sweeps two AABoxes and finds the first time of collision. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* currently there is no parateter for the movement of the second box. the internal code *
* can handle it though. *
* *
* HISTORY: *
* 11/19/99 gth : Created. *
*=============================================================================================*/
bool CollisionMath::Collide(const AABoxClass & box,const Vector3 & move,const AABoxClass & box2,CastResultStruct * result)
{
/*
** Test the X-axis
** ra = box projection onto the axis
** rb = box2 projection onto the axis
** u0 = projected distance between the box centers at t0
** u1 = projected distance between the box centers at t1
*/
AABCollisionStruct context(box,move,box2,Vector3(0,0,0));
if (aab_separation_test(context,0)) {
goto exit;
}
if (aab_separation_test(context,1)) {
goto exit;
}
if (aab_separation_test(context,2)) {
goto exit;
}
exit:
if (context.StartBad) {
result->StartBad = true;
result->Fraction = 0.0f;
return true;
}
if (context.MaxFrac < result->Fraction) {
result->Fraction = context.MaxFrac;
result->Normal.Set(0,0,0);
result->Normal[context.AxisId] = -context.Side;
if (result->ComputeContactPoint) {
//WWASSERT(0); // TODO
WWDEBUG_SAY(("AABox-AABox collision does not currently support contact point computation\r\n"));
}
return true;
}
return false;
}
Reference in a new issue View git blame Copy permalink