307 lines
14 KiB
C
307 lines
14 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 : WWMath *
|
||
|
|
* *
|
||
|
|
* $Archive:: /Commando/Code/wwmath/tri.h $*
|
||
|
|
* *
|
||
|
|
* Author:: Greg_h *
|
||
|
|
* *
|
||
|
|
* $Modtime:: 5/04/01 8:35p $*
|
||
|
|
* *
|
||
|
|
* $Revision:: 14 $*
|
||
|
|
* *
|
||
|
|
*---------------------------------------------------------------------------------------------*
|
||
|
|
* Functions: *
|
||
|
|
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
||
|
|
|
||
|
|
|
||
|
|
#if defined(_MSC_VER)
|
||
|
|
#pragma once
|
||
|
|
#endif
|
||
|
|
|
||
|
|
#ifndef TRI_H
|
||
|
|
#define TRI_H
|
||
|
|
|
||
|
|
#include "always.h"
|
||
|
|
#include "vector4.h"
|
||
|
|
#include "vector3.h"
|
||
|
|
#include "vector2.h"
|
||
|
|
#include <assert.h>
|
||
|
|
|
||
|
|
|
||
|
|
/**
|
||
|
|
** TriClass
|
||
|
|
** When the math library needs to deal with triangles, this will be the form used.
|
||
|
|
** The initial reason for this class is for Commando's collision detection code. Initially
|
||
|
|
** I wrote custom code inside the render object for the terrain to perform collision
|
||
|
|
** detection. Moving the low-level geometrical collision code into the math library makes it
|
||
|
|
** more re-useable and independent from changes in the rendering code.
|
||
|
|
*/
|
||
|
|
class TriClass
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
|
||
|
|
const Vector3 * N;
|
||
|
|
const Vector3 * V[3];
|
||
|
|
|
||
|
|
void Compute_Normal()
|
||
|
|
{
|
||
|
|
assert(N);
|
||
|
|
assert(V[0]);
|
||
|
|
assert(V[1]);
|
||
|
|
assert(V[2]);
|
||
|
|
|
||
|
|
Vector3::Cross_Product(*(V[1])-*(V[0]),*(V[2])-*(V[0]),(Vector3 *)N);
|
||
|
|
((Vector3 *)N)->Normalize();
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
bool Contains_Point(const Vector3 & ipoint) const;
|
||
|
|
void Find_Dominant_Plane(int * axis1,int * axis2) const;
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Utility functions:
|
||
|
|
** Functions which have to do with triangles but not neccessarily with TriClass - usually used
|
||
|
|
** by TriClass but also available for use elsewhere.
|
||
|
|
*/
|
||
|
|
|
||
|
|
// Enums for raycast flags (currently used only for semi-infinite axis-aligned rays)
|
||
|
|
enum
|
||
|
|
{
|
||
|
|
TRI_RAYCAST_FLAG_NONE = 0x00,
|
||
|
|
TRI_RAYCAST_FLAG_HIT_EDGE = 0x01,
|
||
|
|
TRI_RAYCAST_FLAG_START_IN_TRI = 0x02
|
||
|
|
};
|
||
|
|
|
||
|
|
// This function does a pure 2D point-in-triangle test. We pass in 3D points both for the
|
||
|
|
// triangle and test points, but we also pass in the two axes to use (the third axis is ignored,
|
||
|
|
// so we are actually testing the projection of the four points onto one of the axis planes). The
|
||
|
|
// triangle points are not assumed to be in any particular winding order (that is checked for
|
||
|
|
// internally). It is used internally by TriClass::Contains_Point(), and may be used elsewhere.
|
||
|
|
// If the ray intersects the camera at an edge we also count it as an intersection. We set a bit
|
||
|
|
// in 'flags' to true in this case (some users of this function need this extra information and
|
||
|
|
// it is very cheap to compute). We do not modify 'flags' if no edges are hit, so it must be
|
||
|
|
// initialized outside this function if its value is to be used.
|
||
|
|
inline bool Point_In_Triangle_2D(const Vector3 &tri_point0, const Vector3 &tri_point1,
|
||
|
|
const Vector3 &tri_point2, const Vector3 &test_point, int axis_1, int axis_2,
|
||
|
|
unsigned char &flags)
|
||
|
|
{
|
||
|
|
// The function is based on checking signs of determinants, or in a more visually intuitive
|
||
|
|
// sense, checking on which side of a line a point lies. For example, if the points run in
|
||
|
|
// counter-clockwise order, the interior of the triangle is the intersection of the three
|
||
|
|
// half-planes to the left of the directed infinite lines along P0 to P1, P1 to P2, P2 to P0.
|
||
|
|
// Therefore the test point is in the triangle iff it is to the left of all three lines (if
|
||
|
|
// the points are in clockwise order, we check if it is to the right of the lines).
|
||
|
|
Vector2 p0p1(tri_point1[axis_1] - tri_point0[axis_1], tri_point1[axis_2] - tri_point0[axis_2]);
|
||
|
|
Vector2 p1p2(tri_point2[axis_1] - tri_point1[axis_1], tri_point2[axis_2] - tri_point1[axis_2]);
|
||
|
|
Vector2 p2p0(tri_point0[axis_1] - tri_point2[axis_1], tri_point0[axis_2] - tri_point2[axis_2]);
|
||
|
|
|
||
|
|
// Check which side P2 is relative to P0P1. The sign of this test must equal the sign of all
|
||
|
|
// three tests between the lines and the test point for the test point to be inside the
|
||
|
|
// triangle. (this test will also tell us if the three points are colinear - if the triangle
|
||
|
|
// is degenerate).
|
||
|
|
Vector2 p0p2(tri_point2[axis_1] - tri_point0[axis_1], tri_point2[axis_2] - tri_point0[axis_2]);
|
||
|
|
float p0p1p2 = Vector2::Perp_Dot_Product(p0p1, p0p2);
|
||
|
|
if (p0p1p2 != 0.0f) {
|
||
|
|
|
||
|
|
// The triangle is not degenerate - test three sides
|
||
|
|
float side_factor = p0p1p2 > 0.0f ? 1.0f : -1.0f;
|
||
|
|
float factors[3];
|
||
|
|
|
||
|
|
// Now perform tests
|
||
|
|
Vector2 p0pT(test_point[axis_1] - tri_point0[axis_1], test_point[axis_2] - tri_point0[axis_2]);
|
||
|
|
factors[0] = Vector2::Perp_Dot_Product(p0p1, p0pT);
|
||
|
|
if (factors[0] * side_factor < 0.0f) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
Vector2 p1pT(test_point[axis_1] - tri_point1[axis_1], test_point[axis_2] - tri_point1[axis_2]);
|
||
|
|
factors[1] = Vector2::Perp_Dot_Product(p1p2, p1pT);
|
||
|
|
if (factors[1] * side_factor < 0.0f) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
Vector2 p2pT(test_point[axis_1] - tri_point2[axis_1], test_point[axis_2] - tri_point2[axis_2]);
|
||
|
|
factors[2] = Vector2::Perp_Dot_Product(p2p0, p2pT);
|
||
|
|
if (factors[2] * side_factor < 0.0f) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
if ((factors[0] == 0.0f) || (factors[1] == 0.0f) || (factors[2] == 0.0f)) flags |= TRI_RAYCAST_FLAG_HIT_EDGE;
|
||
|
|
return true;
|
||
|
|
|
||
|
|
} else {
|
||
|
|
|
||
|
|
// The triangle is degenerate. This should be a rare case, so it does not matter much if it
|
||
|
|
// is a little slower than the non-colinear case.
|
||
|
|
|
||
|
|
// Find the two outer points along the triangle's line ('start' and 'end' points)
|
||
|
|
float p0p1dist2 = p0p1.Length2();
|
||
|
|
float p1p2dist2 = p1p2.Length2();
|
||
|
|
float p2p0dist2 = p1p2.Length2();
|
||
|
|
float max_dist2;
|
||
|
|
Vector2 pSpE, pSpT; // 'end' point, test point - both in 'start' points' frame
|
||
|
|
if (p0p1dist2 > p1p2dist2) {
|
||
|
|
if (p0p1dist2 > p2p0dist2) {
|
||
|
|
// points 0 and 1 are the 'outer' points. 0 is 'start' and 1 is 'end'.
|
||
|
|
pSpE = p0p1;
|
||
|
|
pSpT.Set(test_point[axis_1] - tri_point0[axis_1], test_point[axis_2] - tri_point0[axis_2]);
|
||
|
|
max_dist2 = p0p1dist2;
|
||
|
|
} else {
|
||
|
|
// points 0 and 2 are the 'outer' points. 2 is 'start' and 0 is 'end'.
|
||
|
|
pSpE = p2p0;
|
||
|
|
pSpT.Set(test_point[axis_1] - tri_point2[axis_1], test_point[axis_2] - tri_point2[axis_2]);
|
||
|
|
max_dist2 = p2p0dist2;
|
||
|
|
}
|
||
|
|
} else {
|
||
|
|
if (p1p2dist2 > p2p0dist2) {
|
||
|
|
// points 1 and 2 are the 'outer' points. 1 is 'start' and 2 is 'end'.
|
||
|
|
pSpE = p1p2;
|
||
|
|
pSpT.Set(test_point[axis_1] - tri_point1[axis_1], test_point[axis_2] - tri_point1[axis_2]);
|
||
|
|
max_dist2 = p1p2dist2;
|
||
|
|
} else {
|
||
|
|
// points 0 and 2 are the 'outer' points. 2 is 'start' and 0 is 'end'.
|
||
|
|
pSpE = p2p0;
|
||
|
|
pSpT.Set(test_point[axis_1] - tri_point2[axis_1], test_point[axis_2] - tri_point2[axis_2]);
|
||
|
|
max_dist2 = p2p0dist2;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
if (max_dist2 != 0.0f) {
|
||
|
|
// Triangle is line segment, check if test point is colinear with it
|
||
|
|
if (Vector2::Perp_Dot_Product(pSpE, pSpT)) {
|
||
|
|
// Not colinear
|
||
|
|
return false;
|
||
|
|
} else {
|
||
|
|
// Colinear - is test point's distance from start and end <= segment length?
|
||
|
|
Vector2 pEpT = pSpT - pSpE;
|
||
|
|
if (pSpT.Length2() <= max_dist2 && pEpT.Length2() <= max_dist2) {
|
||
|
|
flags |= TRI_RAYCAST_FLAG_HIT_EDGE;
|
||
|
|
return true;
|
||
|
|
} else {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
} else {
|
||
|
|
// All triangle points coincide, check if test point coincides with them
|
||
|
|
if (pSpT.Length2() == 0.0f) {
|
||
|
|
flags |= TRI_RAYCAST_FLAG_HIT_EDGE;
|
||
|
|
return true;
|
||
|
|
} else {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
// This function tests a semi-infinite axis-aligned ray vs. a triangle.
|
||
|
|
// The inputs are blah blah blah
|
||
|
|
inline bool Cast_Semi_Infinite_Axis_Aligned_Ray_To_Triangle(const Vector3 &tri_point0,
|
||
|
|
const Vector3 &tri_point1, const Vector3 &tri_point2, const Vector4 &tri_plane,
|
||
|
|
const Vector3 &ray_start, int axis_r, int axis_1, int axis_2, int direction,
|
||
|
|
unsigned char & flags)
|
||
|
|
{
|
||
|
|
bool retval = false;
|
||
|
|
|
||
|
|
// First check infinite ray vs. triangle (2D check)
|
||
|
|
unsigned char flags_2d = TRI_RAYCAST_FLAG_NONE;
|
||
|
|
if (Point_In_Triangle_2D(tri_point0, tri_point1, tri_point2, ray_start, axis_1, axis_2, flags_2d)) {
|
||
|
|
|
||
|
|
// NOTE: SR plane equations, unlike WWMath's PlaneClass, use the Ax+By+Cz+D = 0
|
||
|
|
// representation. It can also be viewed as C0x+C1y+C2z+C3 = dist where dist is the
|
||
|
|
// signed distance from the plane (and therefore the plane is defined as those points
|
||
|
|
// where dist = 0). Now that we know that the projection along the ray is inside the
|
||
|
|
// triangle, determining whether the ray hits the triangle is a matter of determining
|
||
|
|
// whether the start point is on the triangle plane's "anti-rayward side" (the side
|
||
|
|
// which the ray points away from).
|
||
|
|
// To determine this, we will use C[axis_r] (the plane coefficient of the ray axis).
|
||
|
|
// This coefficient is positive if the positive direction of the ray axis points into
|
||
|
|
// the planes' positive halfspace and negative if it points into the planes' negative
|
||
|
|
// halfspace (it is zero if the ray axis is parallel to the triangle plane). If we
|
||
|
|
// multiply this by 'sign' which is defined to be -1.0 if 'direction' equals 0 and
|
||
|
|
// 1.0 if 'direction' equals 1, we will get a number which is positive or negative
|
||
|
|
// depending on which halfspace the ray itself (as opposed to the rays axis) points
|
||
|
|
// towards. If we further multiply this by dist(start point) - the result of plugging
|
||
|
|
// the start point into the plane equation - we will get a number which is positive
|
||
|
|
// if the start point is on the 'rayward side' (ray does not intersect the triangle)
|
||
|
|
// and is negative if the start point is on the 'anti-rayward side' (ray does
|
||
|
|
// intersect triangle). In either of these two cases we are done.
|
||
|
|
// (see below for what happens when the result is zero - more checks need to be made).
|
||
|
|
static const float sign[2] = {-1.0f, 1.0f };
|
||
|
|
float result = tri_plane[axis_r] * sign[direction] * (tri_plane.X * ray_start.X +
|
||
|
|
tri_plane.Y * ray_start.Y + tri_plane.Z * ray_start.Z + tri_plane.W);
|
||
|
|
if (result < 0.0f) {
|
||
|
|
// Intersection!
|
||
|
|
flags |= (flags_2d & TRI_RAYCAST_FLAG_HIT_EDGE);
|
||
|
|
retval = true;
|
||
|
|
} else {
|
||
|
|
if (result == 0.0f) {
|
||
|
|
// If the result is 0, this means either the ray is parallel to the triangle
|
||
|
|
// plane or the start point is embedded in the triangle plane. Note that since
|
||
|
|
// the start point passed the 2D check, then if the ray is parallel the start
|
||
|
|
// point must also be embedded in the triangle plane. This leaves us with two
|
||
|
|
// cases:
|
||
|
|
// A) The ray is not parallel to the plane - in this case the start point is
|
||
|
|
// embedded in the triangle. We report an intersection, bitwise OR the edge
|
||
|
|
// result from the 2D check into the 'edge hit' flag and set the 'start in tri'
|
||
|
|
// flag.
|
||
|
|
// B) The ray is parallel to the plane. In this case the result of the 2D test
|
||
|
|
// tells us that the infinite line intersects the triangle (actually is
|
||
|
|
// embedded in the triangle along part of its length), but we do not know
|
||
|
|
// whether the semi-infinite ray also does so. We simplify things by not
|
||
|
|
// counting such an 'intersection'. There are four reasons behind this:
|
||
|
|
// 1. It differs from a 'normal' intersection (which has one intersecting
|
||
|
|
// point) - there are infinitely many intersecting points.
|
||
|
|
// 2. Moving the plane by an infinitesimally small amount to either side will
|
||
|
|
// cause the ray to no longer touch the plane.
|
||
|
|
// 3. This will not affect results for the known uses of this function.
|
||
|
|
// 4. By doing so we avoid having to code up a bunch of complex tests.
|
||
|
|
// Therefore in case B) we just report no intersection. We still need to find
|
||
|
|
// out whether the point is embedded in the triangle (for setting the flag) so
|
||
|
|
// we do another simple 2D test on the dominant plane.
|
||
|
|
if (tri_plane[axis_r]) {
|
||
|
|
// Case A)
|
||
|
|
flags |= (flags_2d & TRI_RAYCAST_FLAG_HIT_EDGE);
|
||
|
|
flags |= TRI_RAYCAST_FLAG_START_IN_TRI;
|
||
|
|
retval = true;
|
||
|
|
} else {
|
||
|
|
// Case B) - test if point in tri (we know it is in plane, so we can use
|
||
|
|
// TriClass function)
|
||
|
|
TriClass tri;
|
||
|
|
tri.V[0] = &tri_point0;
|
||
|
|
tri.V[1] = &tri_point1;
|
||
|
|
tri.V[2] = &tri_point2;
|
||
|
|
tri.N = (Vector3*)&tri_plane;
|
||
|
|
if (tri.Contains_Point(ray_start)) {
|
||
|
|
flags |= TRI_RAYCAST_FLAG_START_IN_TRI;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
} // if (result == 0.0f)
|
||
|
|
} // else (result < 0.0f)
|
||
|
|
} // if Point_In_Triangle_2D()
|
||
|
|
|
||
|
|
return retval;
|
||
|
|
}
|
||
|
|
|
||
|
|
#endif
|