namespace vml
{
namespace geo3d
{
namespace intersections
{
/////////////////////////////////////////////////////////////////////////////
// intersection between bounding boxes
static const unsigned int AABBOX_DISJOINT = 0;
static const unsigned int AABBOX_FIRST_INSIDE_SECOND = 1;
static const unsigned int AABBOX_SECOND_INSIDE_FIRST = 2;
static const unsigned int AABBOX_INTERSECTED = 3;
/////////////////////////////////////////////////////////////////////////////
// intersection between bounding boxe - sphere
static const unsigned int SPHERE_OUTSIDE_AABBOX = 0;
static const unsigned int SPHERE_INSIDE_AABBOX = 1;
static const unsigned int SPHERE_INTERSECTS_AABBOX = 2;
static const unsigned int AABBOX_INSIDE_SPHERE = 3;
/////////////////////////////////////////////////////////////////////////////
// checks if ray intersect an axis aligned bounding box
static const unsigned int AABBOX_RAY_OUTSIDE = 0;
static const unsigned int AABBOX_RAY_INTERSECTS = 1;
static const unsigned int AABBOX_RAY_INSIDEAABBOX = 2;
/////////////////////////////////////////////////////////////////////////////
// bounding boxe intersection tests
static unsigned int AABBoxVsAABBox(const glm::vec3 &bmin1, const glm::vec3 &bmax1, const glm::vec3 &bmin2, const glm::vec3 &bmax2)
{
// check if the first bounding box is entirely inside the second bounding box
if ((bmin1.x >= bmin2.x && bmax1.x <= bmax2.x) &&
(bmin1.y >= bmin2.y && bmax1.y <= bmax2.y) &&
(bmin1.z >= bmin2.z && bmax1.z <= bmax2.z))
return AABBOX_FIRST_INSIDE_SECOND;
// check if the second bounding box is entirely inside the first bounding box
if ((bmin2.x >= bmin1.x && bmax2.x <= bmax1.x) &&
(bmin2.y >= bmin1.y && bmax2.y <= bmax1.y) &&
(bmin2.z >= bmin1.z && bmax2.z <= bmax1.z))
return AABBOX_SECOND_INSIDE_FIRST;
// check if bounding box is out of second bounding box
if ((bmax2.x < bmin1.x || bmin2.x > bmax1.x) ||
(bmax2.y < bmin1.y || bmin2.y > bmax1.y) ||
(bmax2.z < bmin1.z || bmin2.z > bmax1.z))
return AABBOX_DISJOINT;
// if we get here bounding boxes are intersecting each ohter
return AABBOX_INTERSECTED;
}
/////////////////////////////////////////////////////////////////////////////
// intersection between sphere and bounding box
static int AABBoxVsSphere(const glm::vec3 &bmin, const glm::vec3 &bmax, const glm::vec3 &p0, const float radius)
{
// cache values
float uax = p0.x - bmin.x;
float uay = p0.y - bmin.y;
float uaz = p0.z - bmin.z;
float ubx = p0.x - bmax.x;
float uby = p0.y - bmax.y;
float ubz = p0.z - bmax.z;
// checks if sphere is totally inside the bounding box
if (uax + radius >= 0 && ubx + radius <= 0)
if (uax - radius >= 0 && ubx - radius <= 0)
if (uay + radius >= 0 && uby + radius <= 0)
if (uay - radius >= 0 && uby - radius <= 0)
if (uaz + radius >= 0 && ubz + radius <= 0)
if (uaz + radius >= 0 && ubz - radius <= 0)
return SPHERE_INSIDE_AABBOX;
// check if bounding box is totally inside the sphere
glm::vec3 v0;
float dax = uax * uax;
float day = uay * uay;
float daz = uaz * uaz;
float dbx = ubx * ubx;
float dby = uby * uby;
float dbz = ubz * ubz;
v0.x = bmin.x;
v0.y = bmin.y;
v0.z = bmin.z;
if (dbx >= dax) { v0.x = bmax.x; dax = dbx; }
if (dby >= day) { v0.y = bmax.y; day = dby; }
if (dbz >= daz) { v0.z = bmax.z; daz = dbz; }
if (dax + day + daz < radius * radius)
return SPHERE_INTERSECTS_AABBOX;
// check if sphere and bounding box are intersecting
// note that uax, uay,uaz,ubx,uby,ubz squared values
// must be recomputed since we come from the other
// step and values may get overwritten by the
// previous checks
float dmin = 0.0f;
if (uax < 0) dmin += uax * uax;
else if (ubx > 0) dmin += ubx * ubx;
if (uay < 0) dmin += uay * uay;
else if (uby > 0) dmin += uby * uby;
if (uaz < 0) dmin += uaz * uaz;
else if (ubz > 0) dmin += ubz * ubz;
if (dmin < radius * radius)
return AABBOX_INSIDE_SPHERE;
return SPHERE_OUTSIDE_AABBOX;
}
/////////////////////////////////////////////////////////////////////////////
// intersection between infinit ray and bouding box
// min is bounding box min
// max is bounding box max
// a is firt line point
// b is sencond line point
// p and q are intersection points
static unsigned int AABBoxVsRay(const glm::vec3 &min, const glm::vec3 &max,
const glm::vec3 &a, const glm::vec3 &b,
glm::vec3 &p, glm::vec3 &q,
float &tmin,float &tmax,
float eps = vml::math::EPSILON)
{
glm::vec3 d = b - a;
if (d.x > -eps && d.x < eps)
d.x = eps;
float txmin = (min.x - a.x) / d.x;
float txmax = (max.x - a.x) / d.x;
if (txmin > txmax)
{
float t = txmin;
txmin = txmax;
txmax = t;
}
if (d.y > -eps && d.y < eps)
d.y = eps;
float tymin = (min.y - a.y) / d.y;
float tymax = (max.y - a.y) / d.y;
if (tymin > tymax)
{
float t = tymin;
tymin = tymax;
tymax = t;
}
if ((txmin > tymax) || (tymin > txmax))
return AABBOX_RAY_OUTSIDE;
if (tymin > txmin)
txmin = tymin;
if (tymax < txmax)
txmax = tymax;
if (d.z > -eps && d.z < eps)
d.z = eps;
float tzmin = (min.z - a.z) / d.z;
float tzmax = (max.z - a.z) / d.z;
if (tzmin > tzmax)
{
float t = tzmin;
tzmin = tzmax;
tzmax = t;
}
if ((txmin > tzmax) || (tzmin > txmax))
return AABBOX_RAY_OUTSIDE;
if (tzmin > txmin)
txmin = tzmin;
if (tzmax < txmax)
txmax = tzmax;
tmin = txmin;
tmax = txmax;
p = a + tmin * d;
q = a + tmax * d;
return AABBOX_RAY_INTERSECTS;
}
/////////////////////////////////////////////////////////////////////////////
// intersection between infinit ray and bouding box
// min is bounding box min
// max is bounding box max
// a is firt line point
// b is sencond line point
// p and q are intersection points
static unsigned int AABBoxVsLine(const glm::vec3 &min, const glm::vec3 &max,
const glm::vec3 &a, const glm::vec3 &b,
glm::vec3 &p, glm::vec3 &q,
float &txmin, float &txmax,
float eps = vml::math::EPSILON)
{
// line bounding box
glm::vec3 rmin, rmax;
if (a.x < b.x) { rmin.x = a.x; rmax.x = b.x; } else { rmin.x = b.x; rmax.x = a.x; }
if (a.y < b.y) { rmin.y = a.y; rmax.y = b.y; } else { rmin.y = b.y; rmax.y = a.y; }
if (a.z < b.z) { rmin.z = a.z; rmax.z = b.z; } else { rmin.z = b.z; rmax.z = a.z; }
// chck if line is contained inside bbounding box
if ((rmin.x >= min.x && rmax.x <= max.x) &&
(rmin.y >= min.y && rmax.y <= max.y) &&
(rmin.z >= min.z && rmax.z <= max.z))
{
p = a;
q = b;
return AABBOX_RAY_INSIDEAABBOX;
}
// check if bounding box is out of second bounding box
if ((max.x < rmin.x || min.x > rmax.x) ||
(max.y < rmin.y || min.y > rmax.y) ||
(max.z < rmin.z || min.z > rmax.z))
return AABBOX_RAY_OUTSIDE;
// check for intersection
glm::vec3 d = b - a;
if (d.x > -eps && d.x < eps)
d.x = eps;
txmin = (min.x - a.x) / d.x;
txmax = (max.x - a.x) / d.x;
if (txmin > txmax)
{
float t = txmin;
txmin = txmax;
txmax = t;
}
if (d.y > -eps && d.y < eps)
d.y = eps;
float tymin = (min.y - a.y) / d.y;
float tymax = (max.y - a.y) / d.y;
if (tymin > tymax)
{
float t = tymin;
tymin = tymax;
tymax = t;
}
if ((txmin > tymax) || (tymin > txmax))
return AABBOX_RAY_OUTSIDE;
if (tymin > txmin)
txmin = tymin;
if (tymax < txmax)
txmax = tymax;
if (d.z > -eps && d.z < eps)
d.z = eps;
float tzmin = (min.z - a.z) / d.z;
float tzmax = (max.z - a.z) / d.z;
if (tzmin > tzmax)
{
float t = tzmin;
tzmin = tzmax;
tzmax = t;
}
if ((txmin > tzmax) || (tzmin > txmax))
return AABBOX_RAY_OUTSIDE;
if (tzmin > txmin)
txmin = tzmin;
if (tzmax < txmax)
txmax = tzmax;
if (txmin > txmax)
{
float t = txmin;
txmin = txmax;
txmax = t;
}
if (txmin < -eps) txmin = 0.0f;
if (txmax > 1.0f+eps) txmax = 1.0f;
p = a + txmin * d;
q = a + txmax * d;
return AABBOX_RAY_INTERSECTS;
}
static int AABoxVsSphereSAT(const glm::vec3 &s, float radius,
const glm::vec3 &c, const glm::vec3 &halfextents,
vml::geo3d::collisions::MTV &mtv)
{
// clean mtv data struct
mtv.Distance = 0.0f;
mtv.Normal = glm::vec3(0, 0, 0);
mtv.ContactPoint = glm::vec3(0, 0, 0);
mtv.SurfaceNormal = glm::vec3(0, 0, 0);
mtv.HasContactPoints = false;
// Find point p on OBB closest to sphere center
glm::vec3 p;
float dist;
glm::vec3 d = s - c;
// Start result at center of box; make steps from there
p = c;
// For each OBB axis...
// ...project d onto that axis to get the distance
// along the axis of d from the box center
// x axis
dist = d.x;
// If distance farther than the box extents, clamp to the box
if (dist > halfextents.x) dist = halfextents.x;
if (dist < -halfextents.x) dist = -halfextents.x;
// Step that distance along the axis to get world coordinate
p.x += dist;
// y axis
dist = d.y;
// If distance farther than the box extents, clamp to the box
if (dist > halfextents.y) dist = halfextents.y;
if (dist < -halfextents.y) dist = -halfextents.y;
// Step that distance along the axis to get world coordinate
p.y += dist;
// z axis
dist = d.z;
// If distance farther than the box extents, clamp to the box
if (dist > halfextents.z) dist = halfextents.z;
if (dist < -halfextents.z) dist = -halfextents.z;
// Step that distance along the axis to get world coordinate
p.z += dist;
// Sphere and OBB intersect if the (squared) distance from sphere
// center to point p is less than the (squared) sphere radius
glm::vec3 v = p - s;
float l0 = v.x*v.x + v.y*v.y + v.z*v.z;
// halfradius
float l = l0 - radius * radius * 0.25f;
if (l < 0)
{
mtv.Distance = (sqrtf(l0) - radius*0.5f) * 1.01f;
mtv.Normal = glm::normalize(v);
mtv.SurfaceNormal = mtv.Normal;
mtv.ContactPoint = p;
mtv.HasContactPoints = true;
return 1;
}
return 0;
}
} // end of intersections namespace
} // end of geo3d namespace
} // end of vml namespace