Intersection.hpp

Go to the documentation of this file.

/*--------------------------------------------------------------------------------------------
Copyright (c) 2019, NDEVR LLC
tyler.parke@ndevr.org
  __    __   ____     _____ __     __  _______
 |  \  |  | |  __ \  |  ___|\ \   / / |   __  \
 |   \ |  | | |  \ \ | |___  \ \ / /  |  |__)  |
 |  . \|  | | |__/ / | |___   \ V /   |   _   /
 |  |\    |_|_____/__|_____|___\_/____|  | \  \
 |__| \__________________________________|  \__\
 
Subject to the terms of the Enterprise+ Agreement, NDEVR hereby grants 
Licensee a limited, non-exclusive, non-transferable, royalty-free license 
(without the right to sublicense) to use the API solely for the purpose of 
Licensee's internal development efforts to develop applications for which 
the API was provided.
 
The above copyright notice and this permission notice shall be included in all 
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
 
Library: Base
File: Intersection
Included in API: True
Author(s): Tyler Parke
 *-----------------------------------------------------------------------------------------**/
#pragma once
#include <NDEVR/Triangle.h>
#include <NDEVR/Bounds.h>
#include <NDEVR/LineSegment.h>
#include <NDEVR/Vector.h>
#include <NDEVR/Polygon.h>
#include <NDEVR/Plane.h>
namespace NDEVR
{
    /**
    \brief Dummy class for including intersection functions
    **/
    class Intersection
    {};
    constexpr fltp08 intersection_epsilon = 0.0001;
    /**
        
    \brief Given two bounds, returns the intersection between the two of them. If no intersection occurs,
        the returned bounds will be invalid.
    
    Author: Tyler Parke
    
    Date: 2017-11-19
    
    Parameters:
    bounds_1 -  The first bounds used for intersection
    bounds_2 -  The second bounds used for intersection
    
    \returns A Bounds&lt;t_dims,t_type,t_vertex&gt; representing the intersection of the two inputs.
        This value will be invalid if the bounds do not intersect.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    static Bounds<t_dims, t_type, t_vertex> intersection(const Bounds<t_dims, t_type, t_vertex>& bounds_1, const Bounds<t_dims, t_type, t_vertex>& bounds_2)
    {
        return Bounds<t_dims, t_type, t_vertex>(getMax(bounds_1[MIN], bounds_2[MIN]), getMin(bounds_1[MAX], bounds_2[MAX]));
    }
 
    
 
    /**
        
    Intersections.
    
    Author: Tyler Parke
    
    Date: 2017-11-19
    
    Parameters:
    bounds -    The bounds.
    line -      The line.
    
    \returns A LineSegment&lt;t_dims,t_type&gt;
 
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    static LineSegment<t_dims, t_type> intersection(const Bounds<t_dims, t_type, t_vertex>& bounds, const LineSegment<t_dims, t_type, t_vertex>& line)
    {
        LineSegment<t_dims, t_type> intersected_line = line;
        for (uint01 dim = 0; dim < t_dims; ++dim)
        {
            if (intersected_line.vertex(A)[dim] < bounds[MIN][dim])
            {
                if (intersected_line.vertex(B)[dim] < bounds[MIN][dim])
                    return Constant<LineSegment<t_dims, t_type>>::Invalid;
                else
                    intersected_line.vertex(A) = line.template pointAt<true>(bounds[MIN][dim], dim);
            }
            else if (intersected_line.vertex(B)[dim] < bounds[MIN][dim])
            {
                intersected_line.vertex(B) = line.template pointAt<true>(bounds[MIN][dim], dim);
            }
            if (intersected_line.vertex(A)[dim] > bounds[MAX][dim])
            {
                if (intersected_line.vertex(B)[dim] > bounds[MAX][dim])
                    return Constant<LineSegment<t_dims, t_type>>::Invalid;
                else
                    intersected_line.vertex(A) = line.template pointAt<true>(bounds[MAX][dim], dim);
            }
            else if (intersected_line.vertex(B)[dim] > bounds[MAX][dim])
            {
                intersected_line.vertex(B) = line.template pointAt<true>(bounds[MAX][dim], dim);
            }
        }
        return intersected_line;
    }
 
    /**
    
    Intersections.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    tri -       The triangle.
    line -      The line.
    epsilon -   (Optional) The epsilon.
 
    \returns A Vector&lt;t_dims,t_type&gt;
 
    **/
    template<uint01 t_dims, class t_type, class t_vertex>
    static t_vertex intersection(const Triangle<t_dims, t_type, t_vertex>& tri, const LineSegment<t_dims, t_type, t_vertex>& line, t_type epsilon = 0)
    {
        const t_vertex tri_edge_ab(tri.edge(A, B).ray());
        const t_vertex tri_edge_ca(tri.edge(A, C).ray());
        const t_vertex line_ray(line.ray().template normalized<t_type>());
        const t_vertex cross_line_tri = cross(line_ray, tri_edge_ca);
        const t_type determinant = dot(tri_edge_ab, cross_line_tri);
        if (abs(determinant) < epsilon)
            return Constant<t_vertex>::Invalid;
 
        const t_vertex t = line.vertex(A) - tri.vertex(A);
        const t_type u0 = dot(t, cross_line_tri) / determinant;
        if (u0 < cast<t_type>(0) || u0 > cast<t_type>(1))
            return Constant<t_vertex>::Invalid;
        const t_vertex q = cross(t, tri_edge_ab);
        const t_type v = dot(line_ray, q) / determinant;
        if (v < cast<t_type>(0) || u0 + v > cast<t_type>(1))
            return Constant<t_vertex>::Invalid;
        // At this stage we can compute t to find out where the intersection point is on the line.
        const t_type final_t = dot(tri_edge_ca, q) / determinant;
        if (final_t > epsilon && final_t * final_t < line.lengthSquared())
            return final_t * line_ray + line.vertex(A);
        else
            return Constant<t_vertex>::Invalid;// This means that there is a line intersection but not a segment intersection.
    }
    /**
    
    Given two triangles, returns the intersection between the two of them assuming that intesection is a line.
    If no intersection occurs, the returned line will be Invalid. if intersection occurs at a point that point
    will be returned. If the triangles are coplainer, Invalid is returned as this function is not designed to
    intersect coplainer triangles.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    tri_a -     The triangle a.
    tri_b -     The triangle b.
    epsilon -   (Optional) The epsilon.
 
    \returns A LineSegment&lt;t_dims,t_type,t_vertex&gt;
 
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    static LineSegment<t_dims, t_type, t_vertex> intersection(const Triangle<t_dims, t_type, t_vertex>& tri_a, const Triangle<t_dims, t_type, t_vertex>& tri_b, t_type epsilon = 0)
    {
        UNUSED(epsilon);
        const t_vertex normal_a = tri_a.template normal<true>();
        const t_vertex normal_b = tri_b.template normal<true>();
        if (normal_a == normal_b)
            return Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;//We fully intersect the plane, thus cannot produce a linesegment (edge case)
        const t_type dot_1a = dot(normal_b, tri_a.vertex(A) - tri_b.vertex(A));
        const t_type dot_1b = dot(normal_b, tri_a.vertex(B) - tri_b.vertex(A));
        const t_type dot_1c = dot(normal_b, tri_a.vertex(C) - tri_b.vertex(A));
        if ((dot_1a > 0 && dot_1b > 0 && dot_1c > 0) || (dot_1a < 0 && dot_1b < 0 && dot_1c < 0))
            return Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;
 
        if (dot_1a == 0 || dot_1b == 0 || dot_1c == 0)
        {
            return Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;
        }
        const t_type dot_2a = dot(normal_a, tri_b.vertex(A) - tri_a.vertex(A));
        const t_type dot_2b = dot(normal_a, tri_b.vertex(B) - tri_a.vertex(A));
        const t_type dot_2c = dot(normal_a, tri_b.vertex(C) - tri_a.vertex(A));
 
        if ((dot_2a > 0 && dot_2b > 0 && dot_2c > 0) || (dot_2a < 0 && dot_2b < 0 && dot_2c < 0))
            return Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;//No intersection
 
        if (dot_2a == 0 || dot_2b == 0 || dot_2c == 0)
            return Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;//We fully intersect the plane, thus cannot produce a linesegment (edge case)
 
        const t_vertex seg_a1(tri_a.vertex(A) + (tri_a.vertex(B) - tri_a.vertex(A)) * (dot_1a / (dot_1a - dot_1b)));
        const t_vertex seg_a2(tri_a.vertex(A) + (tri_a.vertex(C) - tri_a.vertex(A)) * (dot_1a / (dot_1a - dot_1c)));
 
        const t_vertex seg_b1(tri_b.vertex(A) + (tri_b.vertex(B) - tri_b.vertex(A)) * (dot_2a / (dot_2a - dot_2b)));
        const t_vertex seg_b2(tri_b.vertex(A) + (tri_b.vertex(C) - tri_b.vertex(A)) * (dot_2a / (dot_2a - dot_2c)));
 
        const t_vertex cross_normal = cross(normal_a, normal_b).template normalized<t_type>();
 
        const t_type tp13 = dot(seg_a2 - seg_a1, cross_normal);
        const t_type Ip1 = getMin(cast<t_type>(0), tp13);
        const t_type Ip2 = getMax(cast<t_type>(0), tp13);
 
        const t_type tq12 = dot(seg_b1 - seg_a1, cross_normal);
        const t_type tq13 = dot(seg_b2 - seg_a1, cross_normal);
 
        const t_type Iq1 = getMin(tq12, tq13);
        const t_type Iq2 = getMax(tq12, tq13);
 
 
        if (abs(Ip1 - Iq1) * 2 < ((Ip2 - Ip1) + (Iq2 - Iq1)))
        {
            t_type n_b = getMax(Ip1, Iq1);
            t_type n_a = getMin(Ip2, Iq2);
            if (n_a > n_b)
            {
                return LineSegment<t_dims, t_type, t_vertex>(seg_a1 + cross_normal * n_a, seg_a1 + cross_normal * n_b);
            }
        }
        return Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;
    }
 
    /**
    
    Given two triangles, returns the intersection between the two of them assuming that intesection is a line.
    If no intersection occurs, the returned line will be Invalid. if intersection occurs at a point that point
    will be returned. If the triangles are coplainer, Invalid is returned as this function is not designed to
    intersect coplainer triangles.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    tri_a -     The triangle a.
    tri_b -     The triangle b.
    epsilon -   (Optional) The epsilon.
 
    \returns A LineSegment&lt;t_dims,t_type,t_vertex&gt;
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    static LineSegment<t_dims, t_type, t_vertex> intersection(const Triangle<t_dims, t_type, t_vertex>& tri_a, const Plane<t_dims, t_type>& plane, t_type epsilon = 0)
    {
        UNUSED(epsilon);
        const t_type signed_dist_a = plane.distanceTo(tri_a.vertex(A));
        const t_type signed_dist_b = plane.distanceTo(tri_a.vertex(B));
        const t_type signed_dist_c = plane.distanceTo(tri_a.vertex(C));
        LineSegment<t_dims, t_type, t_vertex> seg = Constant<LineSegment<t_dims, t_type, t_vertex>>::Invalid;
        uint01 seg_location = 0;
 
        if (signed_dist_a == 0.0)
        {
            if (signed_dist_b == 0.0)
            {
                if (signed_dist_c != 0.0)
                {
                    seg[A] = tri_a.vertex(A);
                    seg[B] = tri_a.vertex(B);
                }//else is on same plane so return Invalid
                return seg;
            }
            else if (signed_dist_c == 0.0)
            {
                seg[A] = tri_a.vertex(A);
                seg[B] = tri_a.vertex(C);
                return seg;
            }
            else
            {
                seg[seg_location++] = tri_a.vertex(A);
            }
        }
        if (signed_dist_b == 0.0)
        {
            if (signed_dist_c == 0.0)
            {
                seg[A] = tri_a.vertex(B);
                seg[B] = tri_a.vertex(C);
                return seg;
            }
            seg[seg_location++] = tri_a.vertex(B);
        }
        if (signed_dist_c == 0.0)
        {
            seg[seg_location++] = tri_a.vertex(C);
        }
        if (signed_dist_a * signed_dist_b < 0)
        {
            t_type t = signed_dist_a / (signed_dist_a - signed_dist_b); // 'time' of intersection point on the segment
            seg[seg_location++] = tri_a.vertex(A) + t * (tri_a.vertex(B) - tri_a.vertex(A));
        }
        if (signed_dist_b * signed_dist_c < 0)
        {
            t_type t = signed_dist_b / (signed_dist_b - signed_dist_c); // 'time' of intersection point on the segment
            seg[seg_location++] = tri_a.vertex(B) + t * (tri_a.vertex(C) - tri_a.vertex(B));
        }
        if (signed_dist_c * signed_dist_a < 0)
        {
            t_type t = signed_dist_c / (signed_dist_c - signed_dist_a); // 'time' of intersection point on the segment
            seg[seg_location++] = tri_a.vertex(C) + t * (tri_a.vertex(A) - tri_a.vertex(C));
        }
        return seg;
    }
    template<uint01 t_dims, class t_type, class t_vertex>
    static LineSegment<t_dims, t_type, t_vertex> intersection(const Plane<t_dims, t_type>& plane, const Triangle<t_dims, t_type, t_vertex>& tri_a, t_type epsilon = 0)
    {
        return intersection(tri_a, plane, epsilon);
    }
 
 
//////////////////////////////VERTEX CLASSIFY//////////////////////////////////////////////
 
    template<uint01 t_dims, class t_type>
    IntersectionTypes classify(const Vector<t_dims, t_type>& v1, const Vector<t_dims, t_type>& v2)
    {
        if (v1 == v2)
            return mixed;
        return outside;
    }
 
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const t_vertex& point, const Triangle<t_dims, t_type, t_vertex>& tri)
    {
        if (tri.contains(point))
            return mixed;
        return outside;
    }
    /**
    
    Classifies.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    vertex -    The vertex.
    bounds -    The bounds.
 
    \returns The IntersectionTypes.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const t_vertex& vertex, const Bounds<t_dims, t_type, t_vertex>& bounds)
    {
        if (bounds.contains(vertex))
            return mixed;
        return outside;
    }
 
 
    /**
    
    Classifies.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    vector -    The vector.
    rad -       The radians.
 
    \returns The IntersectionTypes.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const t_vertex& vector, const RadialObject<t_dims, t_type, t_vertex>& rad)
    {
        if (rad.contains(vector))
            return mixed;
        return outside;
    }
 
    template<class t_type, class t_vertex>
    IntersectionTypes classify(const t_vertex& vector, const Polygon<t_type, t_vertex>& polygon)
    {
        if (polygon.contains(vector))
            return mixed;
        return outside;
    }
//////////////////////////////LINE SEGMENT CLASSIFY//////////////////////////////////////////////
 
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const LineSegment<t_dims, t_type, t_vertex>& line, const t_vertex& vertex)
    {
        if(distanceSquared(line, vertex) < intersection_epsilon)
            return inside;
        return outside;
    }
 
 
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const LineSegment<t_dims, t_type, t_vertex>& left, const LineSegment<t_dims, t_type, t_vertex>& right)
    {
        if (distanceSquared(left, right[A]) < intersection_epsilon)
        {
            if (distanceSquared(left, right[B]) < intersection_epsilon)
                return inside;
            else
                return mixed;
        }
        if (distanceSquared(left, right) < intersection_epsilon)
            return mixed;
        return outside;
    }
    /**
    
    Classifies.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    line -      The line.
    tri -       The triangle.
 
    \returns The IntersectionTypes.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const LineSegment<t_dims, t_type, t_vertex>& line, const Triangle<t_dims, t_type, t_vertex>& tri)
    {
        t_type epsilon = cast<t_type>(0.0000001);
        t_vertex edge_ba = tri.vertex(B) - tri.vertex(A);
        t_vertex edge_ca = tri.vertex(C) - tri.vertex(A);
        t_vertex dir = line.ray().template normalized<t_type>();
        t_vertex pvec(cross(dir, edge_ca));
        t_type det = dot(edge_ba, pvec);
 
        // ray and triangle are parallel if det is close to 0
        if (abs(det) < epsilon)
            return IntersectionTypes::outside;
        t_type invDet = cast<t_type>(1) / det;
 
        t_vertex tvec = line.vertex(A) - tri.vertex(A);
        t_type u = dot(tvec, pvec) * invDet;
        if (u < cast<t_type>(0) || u > cast<t_type>(1))
            return IntersectionTypes::outside;
 
        t_vertex qvec(cross(tvec, edge_ba));
        t_type v = dot(dir, qvec) * invDet;
        if (v < cast<t_type>(0) || u + v > cast<t_type>(1))
            return IntersectionTypes::outside;
 
        t_type t = dot(edge_ca, qvec) * invDet;
        if (t * t > line.lengthSquared())
            return IntersectionTypes::outside;
        return IntersectionTypes::mixed;
    }
    /**
    
    Classifies.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    line -      The line.
    bounds -    The bounds.
 
    \returns The IntersectionTypes.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const LineSegment<t_dims, t_type, t_vertex>& line, const Bounds<t_dims, t_type, t_vertex>& bounds)
    {
        return classify(bounds, line) == outside ? outside : mixed;
    }
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const LineSegment<t_dims, t_type, t_vertex>& line, const Polygon<t_type>& polygon)
    {
        return polygon.template contains<t_type>(line.template as<2, t_type>());
    }
 
////////////////////Plane Classify///////////////////////////////////////////////
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Plane<t_dims, t_type>& plane, const t_vertex& point)
    {
        if (plane.contains(point, cast<t_type>(0.0001)))
            return inside;
        return outside;
    }
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const t_vertex& point, const Plane<t_dims, t_type>& plane)
    {
        if (plane.contains(point, cast<t_type>(0.0001)))
            return mixed;
        return outside;
    }
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Plane<t_dims, t_type>& plane, const LineSegment<t_dims, t_type, t_vertex>& line)
    {
        const PlanePosition position_a = plane.planePosition(line.vertex(A));
        const PlanePosition position_b = plane.planePosition(line.vertex(B));
        if (position_a == position_b)
        {
            if (position_a == PlanePosition::e_on_plane)
                return inside;
            else
                return outside;
        }
        return mixed;
    }
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const LineSegment<t_dims, t_type, t_vertex>& line, const Plane<t_dims, t_type>& plane)
    {
        const PlanePosition position_a = plane.planePosition(line.vertex(A));
        const PlanePosition position_b = plane.planePosition(line.vertex(B));
        if (position_a == position_b)
        {
            if (position_a == PlanePosition::e_on_plane)
                return mixed;
            else
                return outside;
        }
        return mixed;
    }
 
 
////////////////////TRIANGLE Classify///////////////////////////////////////////////
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Triangle<t_dims, t_type, t_vertex>& tri, const t_vertex& point)
    {
        if (tri.contains(point))
            return inside;
        return outside;
    }
    /**
    
    Classifies.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    tri -       The triangle.
    line -      The line.
 
    \returns The IntersectionTypes.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Triangle<t_dims, t_type, t_vertex>& tri, const LineSegment<t_dims, t_type, t_vertex>& line)
    {
        if (IsInvalid(intersection(tri, line, cast<t_type>(intersection_epsilon))))
            return outside;
        return mixed;
    }
 
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Triangle<t_dims, t_type, t_vertex>& tri, const Polygon<t_type>& polygon)
    {
        return polygon.template contains<t_type>(tri.template as<2, t_type>());
    }
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Triangle<t_dims, t_type, t_vertex>& triangle, const Plane<t_dims, t_type>& plane)
    {
        const PlanePosition position_a = plane.planePosition(triangle.vertex(A));
        const PlanePosition position_b = plane.planePosition(triangle.vertex(B));
        const PlanePosition position_c = plane.planePosition(triangle.vertex(C));
        if (position_a == position_b && position_a == position_c)
        {
            if (position_a == PlanePosition::e_on_plane)
                return mixed;
            else
                return outside;
        }
        return mixed;
    }
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Plane<t_dims, t_type>& plane, const Triangle<t_dims, t_type, t_vertex>& triangle)
    {
        const PlanePosition position_a = plane.planePosition(triangle.vertex(A));
        const PlanePosition position_b = plane.planePosition(triangle.vertex(B));
        const PlanePosition position_c = plane.planePosition(triangle.vertex(C));
        if (position_a == position_b && position_a == position_c)
        {
            if (position_a == PlanePosition::e_on_plane)
                return inside;
            else
                return outside;
        }
        return mixed;
    }
 
/////////////////////////BOUNDS CLASSIFY//////////////////////////////////
 
    /**
    
    Classifies.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    bounds -    The bounds.
    vertex -    The vertex.
 
    \returns The IntersectionTypes.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& bounds, const t_vertex& vertex)
    {
        if (bounds.contains(vertex))
            return inside;
        return outside;
    }
 
    /**
    
    Classifies.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    bounds -    The bounds.
    line -      The line.
 
    \returns The IntersectionTypes.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& bounds, const LineSegment<t_dims, t_type, t_vertex>& line)
    {
        if (bounds.contains(line))
        {
            return inside;
        }
        const Vertex<t_dims, t_type> ray = line.ray();
        for (uint01 i = 0; i < t_dims; ++i)
        {
            if (bounds.doesIntersect(line.vertex(A)[i] - bounds[MIN][i], line.vertex(B)[i] - bounds[MIN][i], line.vertex(A), ray, i)
                || bounds.doesIntersect(line.vertex(A)[i] - bounds[MAX][i], line.vertex(B)[i] - bounds[MAX][i], line.vertex(A), ray, i))
                return mixed;
        }
        return outside;
    }
 
 
 
    /**
    
    Classifies.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    bounds -    The bounds.
    tri -       The triangle.
 
    \returns The IntersectionTypes.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& bounds, const Triangle<t_dims, t_type, t_vertex>& tri)
    {
        if (bounds.contains(tri))
            return inside;
        else
        {
            const t_vertex min = getMin(tri.vertex(A), tri.vertex(B), tri.vertex(C));
            const t_vertex max = getMax(tri.vertex(A), tri.vertex(B), tri.vertex(C));
            for (uint01 i = 0; i < t_dims; i++)
            {
                if (min[i] > bounds[MAX][i] || max[i] < bounds[MIN][i])
                    return outside;
            }
        }
 
        const t_vertex bounds_center(bounds.center());
        const Triangle<t_dims, t_type, t_vertex> centered_tri(
            t_vertex(tri.vertex(A) - bounds_center)
            , t_vertex(tri.vertex(B) - bounds_center)
            , t_vertex(tri.vertex(C) - bounds_center));
        const t_vertex half_span(bounds.span() / cast<t_type>(2));
        const t_vertex edge[3] = { centered_tri.edge(A, B).ray(), centered_tri.edge(B, C).ray(), centered_tri.edge(C, A).ray() };
        for (uint01 edge_index = 0; edge_index < 3; ++edge_index)
        {
            const t_vertex cur_edge = edge[edge_index];
            const t_vertex abs_edge = abs(edge[edge_index]);
            for (uint01 i = 0; i < 3; ++i)
            {
                t_type val_a;
                t_type val_b;
                t_type radius;
                switch (i)
                {
                case 0:
                    val_a = cur_edge[Z] * centered_tri.vertex(A)[Y] - cur_edge[Y] * centered_tri.vertex(A)[Z];
                    val_b = cur_edge[Z] * centered_tri.vertex(C)[Y] - cur_edge[Y] * centered_tri.vertex(C)[Z];
                    radius = abs_edge[Z] * half_span[Y] + abs_edge[Y] * half_span[Z];
                    break;
                case 1:
                    val_a = -cur_edge[Z] * centered_tri.vertex(A)[X] + cur_edge[X] * centered_tri.vertex(A)[Z];
                    val_b = -cur_edge[Z] * centered_tri.vertex(C)[X] + cur_edge[X] * centered_tri.vertex(C)[Z];
                    radius = abs_edge[Z] * half_span[X] + abs_edge[X] * half_span[Z];
                    break;
                case 2:
                default:
                    val_a = cur_edge[Y] * centered_tri.vertex(B)[X] - cur_edge[X] * centered_tri.vertex(B)[Y];
                    val_b = cur_edge[Y] * centered_tri.vertex(C)[X] - cur_edge[X] * centered_tri.vertex(C)[Y];
                    radius = abs_edge[Y] * half_span[X] + abs_edge[X] * half_span[Y];
                    break;
                }
                if (val_a < val_b)
                {
                    if (val_a > radius || val_b < -radius)
                        return outside;
                }
                else
                {
                    if (val_b > radius || val_a < -radius)
                        return outside;
                }
            }
        }
        const t_vertex normal = cross(edge[0], edge[1]);
        t_vertex vertex_min;
        t_vertex vertex_max;
        for (uint01 i = 0; i < 3; i++)
        {
            t_type vertex_a_val = centered_tri.vertex(A)[i];
            if (normal[i] > cast<t_type>(0))
            {
                vertex_min[i] = -half_span[i] - vertex_a_val;
                vertex_max[i] = half_span[i] - vertex_a_val;
            }
            else
            {
                vertex_min[i] = half_span[i] - vertex_a_val;
                vertex_max[i] = -half_span[i] - vertex_a_val;
            }
        }
        if (dot(normal, vertex_min) > cast<t_type>(0) || dot(normal, vertex_max) < cast<t_type>(0))
            return outside;
        return mixed;
    }
 
    /**
    
    Classifies.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    outside -   The outside.
    inside -    The inside.
 
    \returns The IntersectionTypes.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& left, const Bounds<t_dims, t_type, t_vertex>& right)
    {
        bool is_inside = true;
        for (uint01 dim = 0; dim < t_dims; ++dim)
        {
            if (!(right[MIN][dim] >= left[MIN][dim]))
            {
                if (!(right[MAX][dim] >= left[MIN][dim]))
                    return outside;
                is_inside = false;
            }
            if (!(right[MAX][dim] <= left[MAX][dim]))
            {
                if (!(right[MIN][dim] <= left[MAX][dim]))
                    return outside;
                is_inside = false;
            }
        }
        if (is_inside)
            return inside;
        return mixed;
    }
 
    /**
    
    Classifies.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    bounds -    The bounds.
    radial -    The radial.
 
    \returns The IntersectionTypes.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& bounds, const RadialObject<t_dims, t_type, t_vertex>& radial)
    {
        const t_vertex center = radial.center();
 
        uint01 inside_dims = 0;
        t_type sqr_dist = cast<t_type>(0);
 
        for (uint01 dim = 0; dim < t_dims; ++dim)
        {
            if (center[dim] < bounds[MIN][dim])
                sqr_dist += (bounds[MIN][dim] - center[dim]) * (bounds[MIN][dim] - center[dim]);
            else if (center[dim] > bounds[MAX][dim])
                sqr_dist += (center[dim] - bounds[MAX][dim]) * (center[dim] - bounds[MAX][dim]);
            else if (center[dim] >= bounds[MIN] + radial.radius() && center[dim] <= bounds[MAX][dim] - radial.radius())
                inside_dims++;
        }
        if (inside_dims == t_dims)
            return inside;
        if (sqr_dist > radial.radius() * radial.radius())
            return outside;
        return mixed;
    }
 
    
 
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& bounds, const Polygon<t_type>& polygon)
    {
        return polygon.template contains<t_type>(bounds.template as<2, t_type>());
    }
 
 
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Bounds<t_dims, t_type, t_vertex>& bounds, const Plane<t_dims, t_type>& plane)
    {
        t_vertex c = bounds.center(); // Compute AABB center
        t_vertex e = bounds[MAX] - c; // Compute positive extents
 
        // Compute the projection interval radius of b onto L(t) = b.c + t * p.n
        t_type r = (e * abs(plane.normal)).sum();
 
        // Compute distance of box center from plane
        t_type s = dot(plane.normal, c) - plane.d;
 
        // Intersection occurs when distance s falls within [-r,+r] interval
        if (abs(s) <= r)
            return IntersectionTypes::mixed;
        else
            return IntersectionTypes::outside;
    }
 
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Plane<t_dims, t_type>& plane, const Bounds<t_dims, t_type, t_vertex>& bounds)
    {
        return classify(bounds, plane);
    }
 
/////////////////////////RADIAL OBJECT CLASSIFY/////////////////////////////////////
    /**
    
    Classifies.
 
    Author: Tyler Parke
 
    Date: 2017-11-19
 
    Parameters:
    rad -       The radians.
    vector -    The vector.
 
    \returns The IntersectionTypes.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const RadialObject<t_dims, t_type, t_vertex>& rad, const t_vertex& vector)
    {
        if (rad.contains(vector))
            return inside;
        return outside;
    }
    /**
        
    Classifies.
    
    Author: Tyler Parke
    
    Date: 2017-11-19
    
    Parameters:
    radial -    The radial.
    bounds -    The bounds.
    
    \returns The IntersectionTypes.
     **/
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const RadialObject<t_dims, t_type, t_vertex>& radial, const Bounds<t_dims, t_type, t_vertex>& bounds)
    {
        t_type max_tot(0);
        t_type min_tot(0);
        for (uint01 i = 0; i < t_dims; i++)
        {
            const t_type cir_center = radial.center()[i];
            const t_type dist_max = (bounds[MAX][i] - cir_center) * (bounds[MAX][i] - cir_center);
            const t_type dist_min = (bounds[MIN][i] - cir_center) * (bounds[MIN][i] - cir_center);
            if (dist_max > dist_min)
            {
                max_tot += dist_max;
                if (cir_center < bounds[MIN][i])
                    min_tot += dist_min;
            }
            else
            {
                max_tot += dist_min;
                if (cir_center > bounds[MAX][i])
                    min_tot += dist_max;
            }
        }
        const t_type rad_squared = radial.radius() * radial.radius();
        if (max_tot < rad_squared)
            return inside;
        if (min_tot < rad_squared)
            return mixed;
        return outside;
    }
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const RadialObject<t_dims, t_type, t_vertex>& radial, const Plane<t_dims, t_type>& plane)
    {
        t_vertex c = radial.center(); // Compute AABB 
        if (radial.radius() >= plane.distanceTo(c))
            return mixed;
        else
            return outside;
    }
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Plane<t_dims, t_type>& plane, const RadialObject<t_dims, t_type, t_vertex>& radial)
    {
        return classify(radial, plane);
    }
    
    template<class t_type, class t_vertex>
    IntersectionTypes classify(const Polygon<t_type, t_vertex>& polygon, const t_vertex& vector)
    {
        if (polygon.contains(vector))
            return inside;
        return outside;
    }
 
    
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Polygon<t_type>& polygon, const Bounds<t_dims, t_type, t_vertex>& bounds)
    {
        return polygon.template contains<t_type>(bounds.template as<2, t_type>());
    }
 
    
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Polygon<t_type>& polygon, const Triangle<t_dims, t_type, t_vertex>& tri)
    {
        return polygon.template contains<t_type>(tri.template as<2, t_type>());
    }
 
    
    template<uint01 t_dims, class t_type, class t_vertex>
    IntersectionTypes classify(const Polygon<t_type>& polygon, const LineSegment<t_dims, t_type, t_vertex>& line)
    {
        return polygon.template contains<t_type>(line.template as<2, t_type>());
    }
 
    
    
}