// 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 #include #include #include // The queries consider the ellipsoid to be a solid. namespace WwiseGTE { template class TIQuery, Ellipsoid3> { public: struct Result { bool intersect; }; Result operator()(Segment3 const& segment, Ellipsoid3 const& ellipsoid) { // The ellipsoid is (X-K)^T*M*(X-K)-1 = 0 and the line is // X = P+t*D. Substitute the line equation into the ellipsoid // equation to obtain a quadratic equation // Q(t) = a2*t^2 + 2*a1*t + a0 = 0 // where a2 = D^T*M*D, a1 = D^T*M*(P-K) and // a0 = (P-K)^T*M*(P-K)-1. Result result; Vector3 segOrigin, segDirection; Real segExtent; segment.GetCenteredForm(segOrigin, segDirection, segExtent); Matrix3x3 M; ellipsoid.GetM(M); Vector3 diff = segOrigin - ellipsoid.center; Vector3 matDir = M * segDirection; Vector3 matDiff = M * diff; Real a2 = Dot(segDirection, matDir); Real a1 = Dot(segDirection, matDiff); Real a0 = Dot(diff, matDiff) - (Real)1; Real discr = a1 * a1 - a0 * a2; if (discr >= (Real)0) { // Test whether ray origin is inside ellipsoid. if (a0 <= (Real)0) { result.intersect = true; } else { // At this point, Q(0) = a0 > 0 and Q(t) has real roots. // It is also the case that a2 > 0, since M is positive // definite, implying that D^T*M*D > 0 for any nonzero // vector D. Real q, qder; if (a1 >= (Real)0) { // Roots are possible only on [-e,0], e is the segment // extent. At least one root occurs if Q(-e) <= 0 or // if Q(-e) > 0 and Q'(-e) < 0. q = a0 + segExtent * ((Real)-2 * a1 + a2 * segExtent); if (q <= (Real)0) { result.intersect = true; } else { qder = a1 - a2 * segExtent; result.intersect = (qder < (Real)0); } } else { // Roots are only possible on [0,e], e is the segment // extent. At least one root occurs if Q(e) <= 0 or // if Q(e) > 0 and Q'(e) > 0. q = a0 + segExtent * ((Real)2 * a1 + a2 * segExtent); if (q <= (Real)0.0) { result.intersect = true; } else { qder = a1 + a2 * segExtent; result.intersect = (qder < (Real)0); } } } } else { // No intersection if Q(t) has no real roots. result.intersect = false; } return result; } }; template class FIQuery, Ellipsoid3> : public FIQuery, Ellipsoid3> { public: struct Result : public FIQuery, Ellipsoid3>::Result { // No additional information to compute. }; Result operator()(Segment3 const& segment, Ellipsoid3 const& ellipsoid) { Vector3 segOrigin, segDirection; Real segExtent; segment.GetCenteredForm(segOrigin, segDirection, segExtent); Result result; DoQuery(segOrigin, segDirection, segExtent, ellipsoid, result); for (int i = 0; i < result.numIntersections; ++i) { result.point[i] = segOrigin + result.parameter[i] * segDirection; } return result; } protected: void DoQuery(Vector3 const& segOrigin, Vector3 const& segDirection, Real segExtent, Ellipsoid3 const& ellipsoid, Result& result) { FIQuery, Ellipsoid3>::DoQuery(segOrigin, segDirection, ellipsoid, result); if (result.intersect) { // The line containing the segment intersects the ellipsoid; // the t-interval is [t0,t1]. The segment intersects the // ellipsoid as long as [t0,t1] overlaps the segment // t-interval [-segExtent,+segExtent]. std::array segInterval = { -segExtent, segExtent }; FIQuery, std::array> iiQuery; auto iiResult = iiQuery(result.parameter, segInterval); if (iiResult.intersect) { result.numIntersections = iiResult.numIntersections; result.parameter = iiResult.overlap; } else { result.intersect = false; result.numIntersections = 0; } } } }; }