新建網頁 1
前面都提到了cAABB3類，它代表的是3D中的軸對齊矩形邊界框（AABB），這里給出類的完整定義和實現。
AABb3.h:
#ifndef AABB3_H
#define AABB3_H
#include "vector3.h"
class cMatrix4x3;
//---------------------------------------------------------------------------
// Implement a 3D axially aligned bounding box
//---------------------------------------------------------------------------
class cAABB3
{
public:
cVector3 min, max;
public:
// query for dimentions
cVector3 size() const { return max - min; }
float x_size() { return max.x - min.x; }
float y_size() { return max.y - min.y; }
float z_size() { return max.z - min.z; }
cVector3 center() const { return (min + max) * 0.5f; }
// fetch one of the eight corner points
cVector3 corner(int i) const;
// "Empty" the box, by setting the values to really large/small numbers.
void empty();
// add a point to the box
void add(const cVector3& p);
// add an AABB to the box
void add(const cAABB3& box);
// return true if the box is empty
bool is_empty() const;
// return true if the box contains a point
bool contains(const cVector3& p) const;
// transform the box and compute the new AABB
void set_to_transformed_box(const cAABB3& box, const cMatrix4x3& m);
// return the clostet point on this box to another point
cVector3 closest_point_to(const cVector3& p) const;
// return true if we intersect a sphere
bool intersect_sphere(const cVector3& center, float radius) const;
// Parametric intersection with a ray, returns >1 if no intresection.
float ray_intersect(const cVector3& ray_org, const cVector3& ray_delta, cVector3* return_normal) const;
// classify box as being on one side or the other side of a plane
int classify_plane(const cVector3& n, float d) const;
// dynamic intersection with plane
float intersect_plane(const cVector3& n, float plane_d, const cVector3& dir) const;
};
// Check if two AABBs intersect, and return true if so.
// Optionally return the AABB of their intersection if an intersection is dectected.
bool intersect_aabb(const cAABB3& box1, const cAABB3& box2, cAABB3* box_intersect);
// Return parametric point in time when a moving AABB collides with a stationary AABB.
// return value > 1 if no intersection.
float intersect_moving_aabb(const cAABB3& stationary_aabb, const cAABB3& moving_aabb, const cVector3& d);
#endif
AABB3.cpp:
#include <assert.h>
#include <stdlib.h>
#include "AABB3.h"
#include "Matrix4x3.h"
#include "CommonStuff.h"
const float NO_INTERSECTION = 1e30f; // We'll return this huge number if no intersection
//--------------------------------------------------------------------------------------
// Return one of the 8 corner points. The points are numbered as follows:
//
// 6 7
// ------------------------------
// /| /|
// / | / |
// / | / |
// / | / |
// / | / |
// / | / |
// / | / |
// / | / |
// / | / |
// 2 / | 3 / |
// /----------------------------/ |
// | | | |
// | | | | +Y
// | 4 | | |
// | |-----------------|----------| |
// | / | / 5 |
// | / | / | +Z
// | / | / |
// | / | / | /
// | / | / | /
// | / | / | /
// | / | / | /
// | / | / | /
// | / | / |/
// |/ |/ ----------------- +X
// ------------------------------
// 0 1
//
// Bit 0 selects min.x vs. max.x
// Bit 1 selects min.y vs. max.y
// Bit 2 selects min.z vs. max.z
//--------------------------------------------------------------------------------------
cVector3 cAABB3::corner(int i) const
{
assert(i >= 0 && i <= 7); // make sure index is in range
return cVector3((i & 1) ? max.x : min.x,
(i & 2) ? max.y : min.y,
(i & 4) ? max.z : min.z);
}
//---------------------------------------------------------------------------
// "Empty" the box, by setting the values to really large/small numbers.
//---------------------------------------------------------------------------
void cAABB3::empty()
{
const float big_number = 1e37f;
min.x = min.y = min.z = big_number;
max.x = max.y = max.z = -big_number;
}
//---------------------------------------------------------------------------
// Add a point to the box
//---------------------------------------------------------------------------
void cAABB3::add(const cVector3& p)
{
// expand the box as necessary to contain the point
if(p.x < min.x) min.x = p.x;
if(p.x > max.x) max.x = p.x;
if(p.y < min.y) min.y = p.y;
if(p.y > max.y) max.y = p.y;
if(p.z < min.z) min.z = p.z;
if(p.z > max.z) max.z = p.z;
}
//---------------------------------------------------------------------------
// Add an AABB to the box
//---------------------------------------------------------------------------
void cAABB3::add(const cAABB3& box)
{
// expand the box as necessary
if(box.min.x < min.x) min.x = box.min.x;
if(box.min.x > max.x) max.x = box.min.x;
if(box.min.y < min.y) min.y = box.min.y;
if(box.min.y > max.y) max.y = box.min.y;
if(box.min.z < min.z) min.z = box.min.z;
if(box.min.z > max.z) max.z = box.min.z;
}
//---------------------------------------------------------------------------
// Return true if the box is empty
//---------------------------------------------------------------------------
bool cAABB3::is_empty() const
{
// check if we're inverted on any axis
return (min.x > max.x) || (min.y > max.y) || (min.z > max.z);
}
//---------------------------------------------------------------------------
// Return true if the box contains a point
//---------------------------------------------------------------------------
bool cAABB3::contains(const cVector3& p) const
{
// check for overlap on each axis
return (p.x >= min.x) && (p.x <= max.x) &&
(p.y >= min.y) && (p.y <= max.y) &&
(p.z >= min.z) && (p.z <= max.z);
}
//---------------------------------------------------------------------------
// Transform the box and compute the new AABB. Remember, this always
// results in an AABB that is at least as big as the origin, and may be
// considerably bigger.
//---------------------------------------------------------------------------
void cAABB3::set_to_transformed_box(const cAABB3& box, const cMatrix4x3& m)
{
// if we're empty, then bail.
if(box.is_empty())
{
empty();
return;
}
// start with the translation portion
min = max = get_translation(m);
// examine each of the 9 matrix elements and compute the new AABB
if(m.m11 > 0.0f)
{
min.x += m.m11 * box.min.x;
max.x += m.m11 * box.max.x;
}
else
{
min.x += m.m11 * box.max.x;
max.x += m.m11 * box.min.x;
}
if(m.m21 > 0.0f)
{
min.x += m.m21 * box.min.y;
max.x += m.m21 * box.max.y;
}
else
{
min.x += m.m21 * box.max.y;
max.x += m.m21 * box.min.y;
}
if(m.m31 > 0.0f)
{
min.x += m.m31 * box.min.z;
max.x += m.m31 * box.max.z;
}
else
{
min.x += m.m31 * box.max.z;
max.x += m.m31 * box.min.z;
}
if(m.m12 > 0.0f)
{
min.y += m.m12 * box.min.x;
max.y += m.m12 * box.max.x;
}
else
{
min.y += m.m12 * box.max.x;
max.y += m.m12 * box.min.x;
}
if(m.m22 > 0.0f)
{
min.y += m.m22 * box.min.y;
max.y += m.m22 * box.max.y;
}
else
{
min.y += m.m22 * box.max.y;
max.y += m.m22 * box.min.y;
}
if(m.m32 > 0.0f)
{
min.y += m.m32 * box.min.z;
max.y += m.m32 * box.max.z;
}
else
{
min.y += m.m32 * box.max.z;
max.y += m.m32 * box.min.z;
}
if(m.m13 > 0.0f)
{
min.z += m.m13 * box.min.x;
max.z += m.m13 * box.max.x;
}
else
{
min.z += m.m13 * box.max.x;
max.z += m.m13 * box.min.x;
}
if(m.m23 > 0.0f)
{
min.z += m.m23 * box.min.y;
max.z += m.m23 * box.max.y;
}
else
{
min.z += m.m23 * box.max.y;
max.z += m.m23 * box.min.y;
}
if(m.m33 > 0.0f)
{
min.z += m.m33 * box.min.z;
max.z += m.m33 * box.max.z;
}
else
{
min.z += m.m33 * box.max.z;
max.z += m.m33 * box.min.z;
}
}
//---------------------------------------------------------------------------
// return the closest point on this box to another point
//---------------------------------------------------------------------------
cVector3 cAABB3::closest_point_to(const cVector3& p) const
{
// "push" p into the box, on each dimension.
cVector3 r;
if(p.x < min.x)
r.x = min.x;
else if(p.x > max.x)
r.x = max.x;
else
r.x = p.x;
if(p.y < min.y)
r.y = min.y;
else if(p.y > max.y)
r.y = max.y;
else
r.y = p.y;
if(p.z < min.z)
r.z = min.z;
else if(p.z > max.z)
r.z = max.z;
else
r.z = p.z;
return r;
}
//---------------------------------------------------------------------------
// Return true if we intersect a sphere, uses Arvo's algorithm.
//---------------------------------------------------------------------------
bool cAABB3::intersect_sphere(const cVector3& center, float radius) const
{
// find the closest point on box to the point
cVector3 closest_point = closest_point_to(center);
// check if it's within range
return distance_squared(center, closest_point) < radius * radius;
}
//---------------------------------------------------------------------------
// Parametric intersection with a ray. Returns parametric point
// of intsersection in range 0
1 or a really big number (>1) if no
// intersection.
//
// From "Fast Ray-Box Intersection," by Woo in Graphics Gems I, page 395.
//
// See 12.9.11
//---------------------------------------------------------------------------
float cAABB3::ray_intersect(const cVector3& ray_org, // origin of the ray
const cVector3& ray_delta, // length and direction of the ray
cVector3* return_normal) const // optionally, the normal is returned
{
// Check for point inside box, trivial reject, and determine parametric distance to each front face.
bool inside = true;
float xt, xn = 0.0f;
if (ray_org.x < min.x)
{
xt = min.x - ray_org.x;
if (xt > ray_delta.x)
return NO_INTERSECTION;
xt /= ray_delta.x;
inside = false;
xn = -1.0f;
}
else if (ray_org.x > max.x)
{
xt = max.x - ray_org.x;
if (xt < ray_delta.x)
return NO_INTERSECTION;
xt /= ray_delta.x;
inside = false;
xn = 1.0f;
}
else
xt = -1.0f;
float yt, yn = 0.0f;
if (ray_org.y < min.y)
{
yt = min.y - ray_org.y;
if (yt > ray_delta.y)
return NO_INTERSECTION;
yt /= ray_delta.y;
inside = false;
yn = -1.0f;
}
else if (ray_org.y > max.y)
{
yt = max.y - ray_org.y;
if (yt < ray_delta.y)
return NO_INTERSECTION;
yt /= ray_delta.y;
inside = false;
yn = 1.0f;
}
else
yt = -1.0f;
float zt, zn = 0.0f;
if (ray_org.z < min.z)
{
zt = min.z - ray_org.z;
if (zt > ray_delta.z)
return NO_INTERSECTION;
zt /= ray_delta.z;
inside = false;
zn = -1.0f;
}
else if (ray_org.z > max.z)
{
zt = max.z - ray_org.z;
if (zt < ray_delta.z)
return NO_INTERSECTION;
zt /= ray_delta.z;
inside = false;
zn = 1.0f;
}
else
zt = -1.0f;
// Inside box?
if (inside)
{
if (return_normal != NULL)
{
*return_normal = -ray_delta;
return_normal->normalize();
}
return 0.0f;
}
// Select farthest plane - this is the plane of intersection.
int which = 0;
float t = xt;
if (yt > t)
{
which = 1;
t = yt;
}
if (zt > t)
{
which = 2;
t = zt;
}
switch (which)
{
case 0: // intersect with yz plane
{
float y = ray_org.y + ray_delta.y * t;
if (y < min.y || y > max.y)
return NO_INTERSECTION;
float z = ray_org.z + ray_delta.z * t;
if (z < min.z || z > max.z)
return NO_INTERSECTION;
if (return_normal != NULL)
{
return_normal->x = xn;
return_normal->y = 0.0f;
return_normal->z = 0.0f;
}
}
break;
case 1: // intersect with xz plane
{
float x = ray_org.x + ray_delta.x * t;
if (x < min.x || x > max.x)
return NO_INTERSECTION;
float z = ray_org.z + ray_delta.z * t;
if (z < min.z || z > max.z)
return NO_INTERSECTION;
if (return_normal != NULL)
{
return_normal->x = 0.0f;
return_normal->y = yn;
return_normal->z = 0.0f;
}
}
break;
case 2: // intersect with xy plane
{
float x = ray_org.x + ray_delta.x * t;
if (x < min.x || x > max.x)
return NO_INTERSECTION;
float y = ray_org.y + ray_delta.y * t;
if (y < min.y || y > max.y)
return NO_INTERSECTION;
if (return_normal != NULL)
{
return_normal->x = 0.0f;
return_normal->y = 0.0f;
return_normal->z = zn;
}
}
break;
}
// Return parametric point of intersection
return t;
}
//---------------------------------------------------------------------------
// Perform static AABB-plane intersection test. Returns:
//
// <0 Box is completely on the BACK side of the plane
// >0 Box is completely on the FRONT side of the plane
// 0 Box intersects the plane
//---------------------------------------------------------------------------
int cAABB3::classify_plane(const cVector3& n, float d) const
{
// inspect the normal and compute the minimum and maximum d value
float min_d, max_d;
if (n.x > 0.0f)
{
min_d = n.x * min.x;
max_d = n.x * max.x;
}
else
{
min_d = n.x * max.x;
max_d = n.x * min.x;
}
if (n.y > 0.0f)
{
min_d += n.y * min.y;
max_d += n.y * max.y;
}
else
{
min_d += n.y * max.y;
max_d += n.y * min.y;
}
if (n.z > 0.0f)
{
min_d += n.z * min.z;
max_d += n.z * max.z;
}
else
{
min_d += n.z * max.z;
max_d += n.z * min.z;
}
// check if completely on the front side of the plane
if(min_d >= d)
return 1;
// check if completely on the back side of the plane
if(max_d <= d)
return -1;
// we straddle the plane
return 0;
}
//---------------------------------------------------------------------------
// Perform dynamic AABB-plane intersection test.
//
// n is the plane normal (assumed to be normalized)
// plane_d is the D value of the plane equation p.n = d
// dir dir is the direction of movement of the AABB.
//
// The plane is assumed to be stationary.
//
// Returns the parametric point of intersection - the distance traveled
// before an intersection occurs. If no intersection, a REALLY big
// number is returned. You must check against the length of the displacement.
//
// Only intersections with the front side of the plane are detected.
//---------------------------------------------------------------------------
float cAABB3::intersect_plane(const cVector3& n, float plane_d, const cVector3& dir) const
{
// make sure they are passing in normalized vectors
assert(fabs(n * n - 1.0) < 0.01);
assert(fabs(dir * dir - 1.0) < 0.01);
// compute glancing angle, make sure we are moving towards the front of the plane.
float dot = n * dir;
if(dot >= 0.0f)
return NO_INTERSECTION;
// inspect the normal and compute the minimum and maximum d values.
// min_d is the d value of the "frontmost" corner point.
float min_d, max_d;
if (n.x > 0.0f)
{
min_d = n.x * min.x;
max_d = n.x * max.x;
}
else
{
min_d = n.x * max.x;
max_d = n.x * min.x;
}
if (n.y > 0.0f)
{
min_d += n.y * min.y;
max_d += n.y * max.y;
}
else
{
min_d += n.y * max.y;
max_d += n.y * min.y;
}
if (n.z > 0.0f)
{
min_d += n.z * min.z;
max_d += n.z * max.z;
}
else
{
min_d += n.z * max.z;
max_d += n.z * min.z;
}
// check if we're already completely on the other side of the plane
if(max_d <= plane_d)
return NO_INTERSECTION;
// perform standard raytrace equation using the frontmost corner point
float t = (plane_d - min_d) / dot;
// Were we already penetrating?
if(t < 0.0f)
return 0.0f;
// Return it, if t > L, then we didn't hit in time.
// That's the condition that the caller should be checking for.
return t;
}
///////////////////////////////////// Global nonmember code ////////////////////////////////////////
//---------------------------------------------------------------------------
// Check if two AABBs intersect, and return true if so. Optionally return
// the AABB of their intersection if an intersection is detected.
//---------------------------------------------------------------------------
bool intersect_aabb(const cAABB3& box1, const cAABB3& box2, cAABB3* box_intersect)
{
// check for no overlap
if(box1.min.x > box2.max.x) return false;
if(box1.max.x < box2.min.x) return false;
if(box1.min.y > box2.max.y) return false;
if(box1.max.y < box2.min.y) return false;
if(box1.min.z > box2.max.z) return false;
if(box1.max.z < box2.min.z) return false;
// we have overlap, compute AABB of intersection, if they want it.
if(box_intersect != NULL)
{
box_intersect->min.x = max(box1.min.x, box2.min.x);
box_intersect->max.x = min(box1.max.x, box2.max.x);
box_intersect->min.y = max(box1.min.y, box2.min.y);
box_intersect->max.y = min(box1.max.y, box2.max.y);
box_intersect->min.z = max(box1.min.z, box2.min.z);
box_intersect->max.z = min(box1.max.z, box2.max.z);
}
return true;
}
//---------------------------------------------------------------------------
// Return parametric point in time when a moving AABB collides
// with a stationary AABB. Returns > 1 if no intersection.
//---------------------------------------------------------------------------
float intersect_moving_aabb(const cAABB3& stationary_aabb, const cAABB3& moving_aabb, const cVector3& d)
{
// initialize interval to contain all the time under consideration
float t_enter = 0.0f;
float t_leave = 1.0f;
// Compute interval of overlap on each dimension, and intersect this interval with the interval
// accumulated so far. As soon as an empty interval is detected, return a negative result
// (no intersection.) In each case, we have to be careful for an infinite of empty interval on
// each dimension.
// check x-axis
if(d.x == 0.0f)
{
// empty or infinite interval on x
if((stationary_aabb.min.x >= moving_aabb.max.x) || (stationary_aabb.max.x <= moving_aabb.min.x))
{
// empty time interval, so no intersection.
return NO_INTERSECTION;
}
// inifinite time interval - no update necessary.
}
else
{
float one_over_d = 1.0f / d.x; // divide once
// compute time value when they begin and end overlapping
float x_enter = (stationary_aabb.min.x - moving_aabb.max.x) * one_over_d;
float x_leave = (stationary_aabb.max.x - moving_aabb.min.x) * one_over_d;
// check for interval out of order
if(x_enter > x_leave)
swap(x_enter, x_leave);
// update interval
if(x_enter > t_enter) t_enter = x_enter;
if(x_leave > t_leave) t_leave = x_leave;
// check if this resulted in empty interval
if(t_enter > t_leave)
return NO_INTERSECTION;
}
// check y-axis
if(d.y == 0.0f)
{
// empty or infinite interval on y
if((stationary_aabb.min.y >= moving_aabb.max.y) || (stationary_aabb.max.y <= moving_aabb.min.y))
{
// empty time interval, so no intersection.
return NO_INTERSECTION;
}
// inifinite time interval - no update necessary.
}
else
{
float one_over_d = 1.0f / d.y; // divide once
// compute time value when they begin and end overlapping
float y_enter = (stationary_aabb.min.y - moving_aabb.max.y) * one_over_d;
float y_leave = (stationary_aabb.max.y - moving_aabb.min.y) * one_over_d;
// check for interval out of order
if(y_enter > y_leave)
swap(y_enter, y_leave);
// update interval
if(y_enter > t_enter) t_enter = y_enter;
if(y_leave > t_leave) t_leave = y_leave;
// check if this resulted in empty interval
if(t_enter > t_leave)
return NO_INTERSECTION;
}
// check z-axis
if(d.z == 0.0f)
{
// empty or infinite interval on z
if((stationary_aabb.min.z >= moving_aabb.max.z) || (stationary_aabb.max.z <= moving_aabb.min.z))
{
// empty time interval, so no intersection.
return NO_INTERSECTION;
}
// inifinite time interval - no update necessary.
}
else
{
float one_over_d = 1.0f / d.z; // divide once
// compute time value when they begin and end overlapping
float z_enter = (stationary_aabb.min.z - moving_aabb.max.z) * one_over_d;
float z_leave = (stationary_aabb.max.z - moving_aabb.min.z) * one_over_d;
// check for interval out of order
if(z_enter > z_leave)
swap(z_enter, z_leave);
// update interval
if(z_enter > t_enter) t_enter = z_enter;
if(z_leave > t_leave) t_leave = z_leave;
// check if this resulted in empty interval
if(t_enter > t_leave)
return NO_INTERSECTION;
}
// Ok, we have an intersection.
// Return the parametric point in time where the intersection occurs.
return t_enter;
}