// David Eberly, Geometric Tools, Redmond WA 98052
// Copyright (c) 1998-2020
// Distributed under the Boost Software License, Version 1.0.
// https://www.boost.org/LICENSE_1_0.txt
// https://www.geometrictools.com/License/Boost/LICENSE_1_0.txt
// Version: 4.0.2019.08.13
#pragma once
#include <Mathematics/FIQuery.h>
#include <Mathematics/TIQuery.h>
#include <array>
// The intervals are of the form [t0,t1], [t0,+infinity) or (-infinity,t1].
// Degenerate intervals are allowed (t0 = t1). The queries do not perform
// validation on the input intervals to test whether t0 <= t1.
namespace WwiseGTE
{
template <typename Real>
class TIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>
{
public:
// The query tests overlap, whether a single point or an entire
// interval.
struct Result
{
bool intersect;
// Dynamic queries (intervals moving with constant speeds). If
// 'intersect' is true, the contact times are valid and
// 0 <= firstTime <= lastTime, firstTime <= maxTime
// If 'intersect' is false, there are two cases reported. If the
// intervals will intersect at firstTime > maxTime, the contact
// times are reported just as when 'intersect' is true. However,
// if the intervals will not intersect, then firstTime and
// lastTime are both set to zero (invalid because 'intersect' is
// false).
Real firstTime, lastTime;
};
// Static query. The firstTime and lastTime values are invalid
// regardless of the value of 'intersect'.
Result operator()(std::array<Real, 2> const& interval0, std::array<Real, 2> const& interval1)
{
Result result;
result.intersect = (interval0[0] <= interval1[1] && interval0[1] >= interval1[0]);
result.firstTime = (Real)0;
result.lastTime = (Real)0;
return result;
}
// Static queries where at least one interval is semiinfinite. The
// two types of semiinfinite intervals are [a,+infinity), which I call
// a positive-infinite interval, and (-infinity,a], which I call a
// negative-infinite interval.
Result operator()(std::array<Real, 2> const& finite, Real const& a, bool isPositiveInfinite)
{
Result result;
result.firstTime = (Real)0;
result.lastTime = (Real)0;
if (isPositiveInfinite)
{
result.intersect = (finite[1] >= a);
}
else // is negative-infinite
{
result.intersect = (finite[0] <= a);
}
return result;
}
Result operator()(Real const& a0, bool isPositiveInfinite0,
Real const& a1, bool isPositiveInfinite1)
{
Result result;
result.firstTime = (Real)0;
result.lastTime = (Real)0;
if (isPositiveInfinite0)
{
if (isPositiveInfinite1)
{
result.intersect = true;
}
else // interval1 is negative-infinite
{
result.intersect = (a0 <= a1);
}
}
else // interval0 is negative-infinite
{
if (isPositiveInfinite1)
{
result.intersect = (a0 >= a1);
}
else // interval1 is negative-infinite
{
result.intersect = true;
}
}
return result;
}
// Dynamic query. Current time is 0, maxTime > 0 is required.
Result operator()(Real maxTime, std::array<Real, 2> const& interval0,
Real speed0, std::array<Real, 2> const& interval1, Real speed1)
{
Result result;
if (interval0[1] < interval1[0])
{
// interval0 initially to the left of interval1.
Real diffSpeed = speed0 - speed1;
if (diffSpeed > (Real)0)
{
// The intervals must move towards each other. 'intersect'
// is true when the intervals will intersect by maxTime.
Real diffPos = interval1[0] - interval0[1];
Real invDiffSpeed = (Real)1 / diffSpeed;
result.intersect = (diffPos <= maxTime * diffSpeed);
result.firstTime = diffPos * invDiffSpeed;
result.lastTime = (interval1[1] - interval0[0]) * invDiffSpeed;
return result;
}
}
else if (interval0[0] > interval1[1])
{
// interval0 initially to the right of interval1.
Real diffSpeed = speed1 - speed0;
if (diffSpeed > (Real)0)
{
// The intervals must move towards each other. 'intersect'
// is true when the intervals will intersect by maxTime.
Real diffPos = interval0[0] - interval1[1];
Real invDiffSpeed = (Real)1 / diffSpeed;
result.intersect = (diffPos <= maxTime * diffSpeed);
result.firstTime = diffPos * invDiffSpeed;
result.lastTime = (interval0[1] - interval1[0]) * invDiffSpeed;
return result;
}
}
else
{
// The intervals are initially intersecting.
result.intersect = true;
result.firstTime = (Real)0;
if (speed1 > speed0)
{
result.lastTime = (interval0[1] - interval1[0]) / (speed1 - speed0);
}
else if (speed1 < speed0)
{
result.lastTime = (interval1[1] - interval0[0]) / (speed0 - speed1);
}
else
{
result.lastTime = std::numeric_limits<Real>::max();
}
return result;
}
result.intersect = false;
result.firstTime = (Real)0;
result.lastTime = (Real)0;
return result;
}
};
template <typename Real>
class FIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>
{
public:
// The query finds overlap, whether a single point or an entire
// interval.
struct Result
{
Result()
:
intersect(false),
numIntersections(0),
overlap{ (Real)0, (Real)0 },
type(isEmpty),
firstTime((Real)0),
lastTime((Real)0)
{
}
bool intersect;
// Static queries (no motion of intervals over time). The number
// of number of intersections is 0 (no overlap), 1 (intervals are
// just touching), or 2 (intervals overlap in an interval). If
// 'intersect' is false, numIntersections is 0 and 'overlap' is
// set to [0,0]. If 'intersect' is true, numIntersections is
// 1 or 2. When 1, 'overlap' is set to [x,x], which is degenerate
// and represents the single intersection point x. When 2,
// 'overlap' is the interval of intersection.
int numIntersections;
std::array<Real, 2> overlap;
// No intersection.
static int const isEmpty = 0;
// Intervals touch at an endpoint, [t0,t0].
static int const isPoint = 1;
// Finite-length interval of intersection, [t0,t1].
static int const isFinite = 2;
// Smiinfinite interval of intersection, [t0,+infinity). The
// result.overlap[0] is t0 and result.overlap[1] is +1 as a
// message that the right endpoint is +infinity (you still need
// the result.type to know this interpretation).
static int const isPositiveInfinite = 3;
// Semiinfinite interval of intersection, (-infinity,t1]. The
// result.overlap[0] is =1 as a message that the left endpoint is
// -infinity (you still need the result.type to know this
// interpretation). The result.overlap[1] is t1.
static int const isNegativeInfinite = 4;
// The dynamic queries all set the type to isDynamicQuery because
// the queries look for time of first and last contact.
static int const isDynamicQuery = 5;
// The type is one of isEmpty, isPoint, isFinite,
// isPositiveInfinite, isNegativeInfinite or isDynamicQuery.
int type;
// Dynamic queries (intervals moving with constant speeds). If
// 'intersect' is true, the contact times are valid and
// 0 <= firstTime <= lastTime, firstTime <= maxTime
// If 'intersect' is false, there are two cases reported. If the
// intervals will intersect at firstTime > maxTime, the contact
// times are reported just as when 'intersect' is true. However,
// if the intervals will not intersect, then firstTime and
// lastTime are both set to zero (invalid because 'intersect' is
// false).
Real firstTime, lastTime;
};
// Static query.
Result operator()(std::array<Real, 2> const& interval0, std::array<Real, 2> const& interval1)
{
Result result;
if (interval0[1] < interval1[0] || interval0[0] > interval1[1])
{
result.numIntersections = 0;
result.overlap[0] = (Real)0;
result.overlap[1] = (Real)0;
result.type = Result::isEmpty;
}
else if (interval0[1] > interval1[0])
{
if (interval0[0] < interval1[1])
{
result.overlap[0] = (interval0[0] < interval1[0] ? interval1[0] : interval0[0]);
result.overlap[1] = (interval0[1] > interval1[1] ? interval1[1] : interval0[1]);
if (result.overlap[0] < result.overlap[1])
{
result.numIntersections = 2;
result.type = Result::isFinite;
}
else
{
result.numIntersections = 1;
result.type = Result::isPoint;
}
}
else // interval0[0] == interval1[1]
{
result.numIntersections = 1;
result.overlap[0] = interval0[0];
result.overlap[1] = result.overlap[0];
result.type = Result::isPoint;
}
}
else // interval0[1] == interval1[0]
{
result.numIntersections = 1;
result.overlap[0] = interval0[1];
result.overlap[1] = result.overlap[0];
result.type = Result::isPoint;
}
result.intersect = (result.numIntersections > 0);
return result;
}
// Static queries where at least one interval is semiinfinite. The
// two types of semiinfinite intervals are [a,+infinity), which I call
// a positive-infinite interval, and (-infinity,a], which I call a
// negative-infinite interval.
Result operator()(std::array<Real, 2> const& finite, Real const& a, bool isPositiveInfinite)
{
Result result;
if (isPositiveInfinite)
{
if (finite[1] > a)
{
result.overlap[0] = std::max(finite[0], a);
result.overlap[1] = finite[1];
if (result.overlap[0] < result.overlap[1])
{
result.numIntersections = 2;
result.type = Result::isFinite;
}
else
{
result.numIntersections = 1;
result.type = Result::isPoint;
}
}
else if (finite[1] == a)
{
result.numIntersections = 1;
result.overlap[0] = a;
result.overlap[1] = result.overlap[0];
result.type = Result::isPoint;
}
else
{
result.numIntersections = 0;
result.overlap[0] = (Real)0;
result.overlap[1] = (Real)0;
result.type = Result::isEmpty;
}
}
else // is negative-infinite
{
if (finite[0] < a)
{
result.overlap[0] = finite[0];
result.overlap[1] = std::min(finite[1], a);
if (result.overlap[0] < result.overlap[1])
{
result.numIntersections = 2;
result.type = Result::isFinite;
}
else
{
result.numIntersections = 1;
result.type = Result::isPoint;
}
}
else if (finite[0] == a)
{
result.numIntersections = 1;
result.overlap[0] = a;
result.overlap[1] = result.overlap[0];
result.type = Result::isPoint;
}
else
{
result.numIntersections = 0;
result.overlap[0] = (Real)0;
result.overlap[1] = (Real)0;
result.type = Result::isEmpty;
}
}
result.intersect = (result.numIntersections > 0);
return result;
}
Result operator()(Real const& a0, bool isPositiveInfinite0,
Real const& a1, bool isPositiveInfinite1)
{
Result result;
if (isPositiveInfinite0)
{
if (isPositiveInfinite1)
{
// overlap[1] is +infinity, but set it to +1 because Real
// might not have a representation for +infinity. The
// type indicates the interval is positive-infinite, so
// the +1 is a reminder that overlap[1] is +infinity.
result.numIntersections = 1;
result.overlap[0] = std::max(a0, a1);
result.overlap[1] = (Real)+1;
result.type = Result::isPositiveInfinite;
}
else // interval1 is negative-infinite
{
if (a0 > a1)
{
result.numIntersections = 0;
result.overlap[0] = (Real)0;
result.overlap[1] = (Real)0;
result.type = Result::isEmpty;
}
else if (a0 < a1)
{
result.numIntersections = 2;
result.overlap[0] = a0;
result.overlap[1] = a1;
result.type = Result::isFinite;
}
else // a0 == a1
{
result.numIntersections = 1;
result.overlap[0] = a0;
result.overlap[1] = result.overlap[0];
result.type = Result::isPoint;
}
}
}
else // interval0 is negative-infinite
{
if (isPositiveInfinite1)
{
if (a0 < a1)
{
result.numIntersections = 0;
result.overlap[0] = (Real)0;
result.overlap[1] = (Real)0;
result.type = Result::isEmpty;
}
else if (a0 > a1)
{
result.numIntersections = 2;
result.overlap[0] = a1;
result.overlap[1] = a0;
result.type = Result::isFinite;
}
else
{
result.numIntersections = 1;
result.overlap[0] = a1;
result.overlap[1] = result.overlap[0];
result.type = Result::isPoint;
}
result.intersect = (a0 >= a1);
}
else // interval1 is negative-infinite
{
// overlap[0] is -infinity, but set it to -1 because Real
// might not have a representation for -infinity. The
// type indicates the interval is negative-infinite, so
// the -1 is a reminder that overlap[0] is -infinity.
result.numIntersections = 1;
result.overlap[0] = (Real)-1;
result.overlap[1] = std::min(a0, a1);
result.type = Result::isNegativeInfinite;
}
}
result.intersect = (result.numIntersections > 0);
return result;
}
// Dynamic query. Current time is 0, maxTime > 0 is required.
Result operator()(Real maxTime, std::array<Real, 2> const& interval0,
Real speed0, std::array<Real, 2> const& interval1, Real speed1)
{
Result result;
result.type = Result::isDynamicQuery;
if (interval0[1] < interval1[0])
{
// interval0 initially to the left of interval1.
Real diffSpeed = speed0 - speed1;
if (diffSpeed > (Real)0)
{
// The intervals must move towards each other. 'intersect'
// is true when the intervals will intersect by maxTime.
Real diffPos = interval1[0] - interval0[1];
Real invDiffSpeed = (Real)1 / diffSpeed;
result.intersect = (diffPos <= maxTime * diffSpeed);
result.numIntersections = 1;
result.firstTime = diffPos * invDiffSpeed;
result.lastTime = (interval1[1] - interval0[0]) * invDiffSpeed;
result.overlap[0] = interval0[0] + result.firstTime * speed0;
result.overlap[1] = result.overlap[0];
return result;
}
}
else if (interval0[0] > interval1[1])
{
// interval0 initially to the right of interval1.
Real diffSpeed = speed1 - speed0;
if (diffSpeed > (Real)0)
{
// The intervals must move towards each other. 'intersect'
// is true when the intervals will intersect by maxTime.
Real diffPos = interval0[0] - interval1[1];
Real invDiffSpeed = (Real)1 / diffSpeed;
result.intersect = (diffPos <= maxTime * diffSpeed);
result.numIntersections = 1;
result.firstTime = diffPos * invDiffSpeed;
result.lastTime = (interval0[1] - interval1[0]) * invDiffSpeed;
result.overlap[0] = interval1[1] + result.firstTime * speed1;
result.overlap[1] = result.overlap[0];
return result;
}
}
else
{
// The intervals are initially intersecting.
result.intersect = true;
result.firstTime = (Real)0;
if (speed1 > speed0)
{
result.lastTime = (interval0[1] - interval1[0]) / (speed1 - speed0);
}
else if (speed1 < speed0)
{
result.lastTime = (interval1[1] - interval0[0]) / (speed0 - speed1);
}
else
{
result.lastTime = std::numeric_limits<Real>::max();
}
if (interval0[1] > interval1[0])
{
if (interval0[0] < interval1[1])
{
result.numIntersections = 2;
result.overlap[0] = (interval0[0] < interval1[0] ? interval1[0] : interval0[0]);
result.overlap[1] = (interval0[1] > interval1[1] ? interval1[1] : interval0[1]);
}
else // interval0[0] == interval1[1]
{
result.numIntersections = 1;
result.overlap[0] = interval0[0];
result.overlap[1] = result.overlap[0];
}
}
else // interval0[1] == interval1[0]
{
result.numIntersections = 1;
result.overlap[0] = interval0[1];
result.overlap[1] = result.overlap[0];
}
return result;
}
result.intersect = false;
result.numIntersections = 0;
result.overlap[0] = (Real)0;
result.overlap[1] = (Real)0;
result.firstTime = (Real)0;
result.lastTime = (Real)0;
return result;
}
};
// Template aliases for convenience.
template <typename Real>
using TIIntervalInterval = TIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>;
template <typename Real>
using FIIntervalInterval = FIQuery<Real, std::array<Real, 2>, std::array<Real, 2>>;
}