tetrees/Plugins/Wwise/Source/AkAudio/Classes/GTE/Mathematics/IntrAlignedBox3Cone3.h

// 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/AlignedBox.h>
#include <Mathematics/Cone.h>
#include <Mathematics/IntrRay3AlignedBox3.h>
#include <Mathematics/IntrSegment3AlignedBox3.h>

// Test for intersection of a box and a cone.  The cone can be infinite
//   0 <= minHeight < maxHeight = std::numeric_limits<Real>::max()
// or finite (cone frustum)
//   0 <= minHeight < maxHeight < std::numeric_limits<Real>::max().
// The algorithm is described in
//   https://www.geometrictools.com/Documentation/IntersectionBoxCone.pdf
// and reports an intersection only when the intersection set has positive
// volume.  For example, let the box be outside the cone.  If the box is
// below the minHeight plane at the cone vertex and just touches the cone
// vertex, no intersection is reported.  If the box is above the maxHeight
// plane and just touches the disk capping the cone, either at a single
// point, a line segment of points or a polygon of points, no intersection
// is reported.

// TODO: These queries were designed when an infinite cone was defined
// by choosing maxHeight of std::numeric_limits<Real>::max(). The Cone<N,Real>
// class has been redesigned not to use std::numeric_limits to allow for
// arithmetic systems that do not have representations for infinities
// (such as BSNumber and BSRational).  The intersection queries need to be
// rewritten for the new class design.  FOR NOW, the queries will work with
// float/double when you create a cone using the cone-frustum constructor
// Cone(ray, angle, minHeight, std::numeric_limits<Real>::max()).

namespace WwiseGTE
{
    template <typename Real>
    class TIQuery<Real, AlignedBox<3, Real>, Cone<3, Real>>
    {
    public:
        struct Result
        {
            bool intersect;
        };

        TIQuery()
            :
            mNumCandidateEdges(0)
        {
            // An edge is { v0, v1 }, where v0 and v1 are relative to mVertices
            // with v0 < v1.
            mEdges[0] = { 0, 1 };
            mEdges[1] = { 1, 3 };
            mEdges[2] = { 2, 3 };
            mEdges[3] = { 0, 2 };
            mEdges[4] = { 4, 5 };
            mEdges[5] = { 5, 7 };
            mEdges[6] = { 6, 7 };
            mEdges[7] = { 4, 6 };
            mEdges[8] = { 0, 4 };
            mEdges[9] = { 1, 5 };
            mEdges[10] = { 3, 7 };
            mEdges[11] = { 2, 6 };

            // A face is { { v0, v1, v2, v3 }, { e0, e1, e2, e3 } }, where
            // { v0, v1, v2, v3 } are relative to mVertices with
            // v0 = min(v0,v1,v2,v3) and where { e0, e1, e2, e3 } are relative
            // to mEdges.  For example, mFaces[0] has vertices { 0, 4, 6, 2 }.
            // The edge { 0, 4 } is mEdges[8], the edge { 4, 6 } is mEdges[7],
            // the edge { 6, 2 } is mEdges[11] and the edge { 2, 0 } is
            // mEdges[3]; thus, the edge indices are { 8, 7, 11, 3 }.
            mFaces[0] = { { 0, 4, 6, 2 }, {  8,  7, 11,  3 } };
            mFaces[1] = { { 1, 3, 7, 5 }, {  1, 10,  5,  9 } };
            mFaces[2] = { { 0, 1, 5, 4 }, {  0,  9,  4,  8 } };
            mFaces[3] = { { 2, 6, 7, 3 }, { 11,  6, 10,  2 } };
            mFaces[4] = { { 0, 2, 3, 1 }, {  3,  2,  1,  0 } };
            mFaces[5] = { { 4, 5, 7, 6 }, {  4,  5,  6,  7 } };

            // Clear the edges.
            std::array<size_t, 2> ezero = { 0, 0 };
            mCandidateEdges.fill(ezero);
            for (size_t r = 0; r < MAX_VERTICES; ++r)
            {
                mAdjacencyMatrix[r].fill(0);
            }

            mConfiguration[0] = &TIQuery::NNNN_0;
            mConfiguration[1] = &TIQuery::NNNZ_1;
            mConfiguration[2] = &TIQuery::NNNP_2;
            mConfiguration[3] = &TIQuery::NNZN_3;
            mConfiguration[4] = &TIQuery::NNZZ_4;
            mConfiguration[5] = &TIQuery::NNZP_5;
            mConfiguration[6] = &TIQuery::NNPN_6;
            mConfiguration[7] = &TIQuery::NNPZ_7;
            mConfiguration[8] = &TIQuery::NNPP_8;
            mConfiguration[9] = &TIQuery::NZNN_9;
            mConfiguration[10] = &TIQuery::NZNZ_10;
            mConfiguration[11] = &TIQuery::NZNP_11;
            mConfiguration[12] = &TIQuery::NZZN_12;
            mConfiguration[13] = &TIQuery::NZZZ_13;
            mConfiguration[14] = &TIQuery::NZZP_14;
            mConfiguration[15] = &TIQuery::NZPN_15;
            mConfiguration[16] = &TIQuery::NZPZ_16;
            mConfiguration[17] = &TIQuery::NZPP_17;
            mConfiguration[18] = &TIQuery::NPNN_18;
            mConfiguration[19] = &TIQuery::NPNZ_19;
            mConfiguration[20] = &TIQuery::NPNP_20;
            mConfiguration[21] = &TIQuery::NPZN_21;
            mConfiguration[22] = &TIQuery::NPZZ_22;
            mConfiguration[23] = &TIQuery::NPZP_23;
            mConfiguration[24] = &TIQuery::NPPN_24;
            mConfiguration[25] = &TIQuery::NPPZ_25;
            mConfiguration[26] = &TIQuery::NPPP_26;
            mConfiguration[27] = &TIQuery::ZNNN_27;
            mConfiguration[28] = &TIQuery::ZNNZ_28;
            mConfiguration[29] = &TIQuery::ZNNP_29;
            mConfiguration[30] = &TIQuery::ZNZN_30;
            mConfiguration[31] = &TIQuery::ZNZZ_31;
            mConfiguration[32] = &TIQuery::ZNZP_32;
            mConfiguration[33] = &TIQuery::ZNPN_33;
            mConfiguration[34] = &TIQuery::ZNPZ_34;
            mConfiguration[35] = &TIQuery::ZNPP_35;
            mConfiguration[36] = &TIQuery::ZZNN_36;
            mConfiguration[37] = &TIQuery::ZZNZ_37;
            mConfiguration[38] = &TIQuery::ZZNP_38;
            mConfiguration[39] = &TIQuery::ZZZN_39;
            mConfiguration[40] = &TIQuery::ZZZZ_40;
            mConfiguration[41] = &TIQuery::ZZZP_41;
            mConfiguration[42] = &TIQuery::ZZPN_42;
            mConfiguration[43] = &TIQuery::ZZPZ_43;
            mConfiguration[44] = &TIQuery::ZZPP_44;
            mConfiguration[45] = &TIQuery::ZPNN_45;
            mConfiguration[46] = &TIQuery::ZPNZ_46;
            mConfiguration[47] = &TIQuery::ZPNP_47;
            mConfiguration[48] = &TIQuery::ZPZN_48;
            mConfiguration[49] = &TIQuery::ZPZZ_49;
            mConfiguration[50] = &TIQuery::ZPZP_50;
            mConfiguration[51] = &TIQuery::ZPPN_51;
            mConfiguration[52] = &TIQuery::ZPPZ_52;
            mConfiguration[53] = &TIQuery::ZPPP_53;
            mConfiguration[54] = &TIQuery::PNNN_54;
            mConfiguration[55] = &TIQuery::PNNZ_55;
            mConfiguration[56] = &TIQuery::PNNP_56;
            mConfiguration[57] = &TIQuery::PNZN_57;
            mConfiguration[58] = &TIQuery::PNZZ_58;
            mConfiguration[59] = &TIQuery::PNZP_59;
            mConfiguration[60] = &TIQuery::PNPN_60;
            mConfiguration[61] = &TIQuery::PNPZ_61;
            mConfiguration[62] = &TIQuery::PNPP_62;
            mConfiguration[63] = &TIQuery::PZNN_63;
            mConfiguration[64] = &TIQuery::PZNZ_64;
            mConfiguration[65] = &TIQuery::PZNP_65;
            mConfiguration[66] = &TIQuery::PZZN_66;
            mConfiguration[67] = &TIQuery::PZZZ_67;
            mConfiguration[68] = &TIQuery::PZZP_68;
            mConfiguration[69] = &TIQuery::PZPN_69;
            mConfiguration[70] = &TIQuery::PZPZ_70;
            mConfiguration[71] = &TIQuery::PZPP_71;
            mConfiguration[72] = &TIQuery::PPNN_72;
            mConfiguration[73] = &TIQuery::PPNZ_73;
            mConfiguration[74] = &TIQuery::PPNP_74;
            mConfiguration[75] = &TIQuery::PPZN_75;
            mConfiguration[76] = &TIQuery::PPZZ_76;
            mConfiguration[77] = &TIQuery::PPZP_77;
            mConfiguration[78] = &TIQuery::PPPN_78;
            mConfiguration[79] = &TIQuery::PPPZ_79;
            mConfiguration[80] = &TIQuery::PPPP_80;
        }

        Result operator()(AlignedBox<3, Real> const& box, Cone<3, Real> const& cone)
        {
            Result result;

            // Quick-rejectance test.  Determine whether the box is outside
            // the slab bounded by the minimum and maximum height planes.
            // When outside the slab, the box vertices are not required by the
            // cone-box intersection query, so the vertices are not yet
            // computed.
            Real boxMinHeight(0), boxMaxHeight(0);
            ComputeBoxHeightInterval(box, cone, boxMinHeight, boxMaxHeight);
            // TODO: See the comments at the beginning of this file.
            Real coneMaxHeight = (cone.IsFinite() ? cone.GetMaxHeight() : std::numeric_limits<Real>::max());
            if (boxMaxHeight <= cone.GetMinHeight() || boxMinHeight >= coneMaxHeight)
            {
                // There is no volumetric overlap of the box and the cone. The
                // box is clipped entirely.
                result.intersect = false;
                return result;
            }

            // Quick-acceptance test.  Determine whether the cone axis
            // intersects the box.
            if (ConeAxisIntersectsBox(box, cone))
            {
                result.intersect = true;
                return result;
            }

            // Test for box fully inside the slab.  When inside the slab, the
            // box vertices are required by the cone-box intersection query,
            // so they are computed here; they are also required in the
            // remaining cases.  Also when inside the slab, the box edges are
            // the candidates, so they are copied to mCandidateEdges.
            if (BoxFullyInConeSlab(box, boxMinHeight, boxMaxHeight, cone))
            {
                result.intersect = CandidatesHavePointInsideCone(cone);
                return result;
            }

            // Clear the candidates array and adjacency matrix.
            ClearCandidates();

            // The box intersects at least one plane.  Compute the box-plane
            // edge-interior intersection points.  Insert the box subedges into
            // the array of candidate edges.
            ComputeCandidatesOnBoxEdges(cone);

            // Insert any relevant box face-interior clipped edges into the array
            // of candidate edges.
            ComputeCandidatesOnBoxFaces();

            result.intersect = CandidatesHavePointInsideCone(cone);
            return result;
        }

    protected:
        // The constants here are described in the comments below.
        enum
        {
            NUM_BOX_VERTICES = 8,
            NUM_BOX_EDGES = 12,
            NUM_BOX_FACES = 6,
            MAX_VERTICES = 32,
            VERTEX_MIN_BASE = 8,
            VERTEX_MAX_BASE = 20,
            MAX_CANDIDATE_EDGES = 496,
            NUM_CONFIGURATIONS = 81
        };

        // The box topology is that of a cube whose vertices have components
        // in {0,1}.  The cube vertices are indexed by
        //   0: (0,0,0), 1: (1,0,0), 2: (1,1,0), 3: (0,1,0)
        //   4: (0,0,1), 5: (1,0,1), 6: (1,1,1), 7: (0,1,1)

        // The first 8 vertices are the box corners, the next 12 vertices are
        // reserved for hmin-edge points and the final 12 vertices are reserved
        // for the hmax-edge points.  The conservative upper bound of the number
        // of vertices is 8 + 12 + 12 = 32.
        std::array<Vector3<Real>, MAX_VERTICES> mVertices;

        // The box has 12 edges stored in mEdges.  An edge is mEdges[i] =
        // { v0, v1 }, where the indices v0 and v1 are relative to mVertices
        // with v0 < v1.
        std::array<std::array<size_t, 2>, NUM_BOX_EDGES> mEdges;

        // The box has 6 faces stored in mFaces.  A face is mFaces[i] =
        // { { v0, v1, v2, v3 }, { e0, e1, e2, e3 } }, where the face corner
        // vertices are { v0, v1, v2, v3 }.  These indices are relative to
        // mVertices.  The indices { e0, e1, e2, e3 } are relative to mEdges.
        // The index e0 refers to edge { v0, v1 }, the index e1 refers to edge
        // { v1, v2 }, the index e2 refers to edge { v2, v3 } and the index e3
        // refers to edge { v3, v0 }.  The ordering of vertices for the faces
        // is/ counterclockwise when viewed from outside the box.  The choice
        // of initial vertex affects how you implement the graph data
        // structure.  In this implementation, the initial vertex has minimum
        // index for all vertices of that face.  The faces themselves are
        // listed as -x face, +x face, -y face, +y face, -z face and +z face.
        struct Face
        {
            std::array<size_t, 4> v, e;
        };
        std::array<Face, NUM_BOX_FACES> mFaces;

        // Store the signed distances from the minimum and maximum height
        // planes for the cone to the projection of the box vertices onto the
        // cone axis.
        std::array<Real, NUM_BOX_VERTICES> mProjectionMin, mProjectionMax;

        // The mCandidateEdges array stores the edges of the clipped box that
        // are candidates for containing the optimizing point.  The maximum
        // number of candidate edges is 1 + 2 + ... + 31 = 496, which is a
        // conservative bound because not all pairs of vertices form edges on
        // box faces.  The candidate edges are stored as (v0,v1) with v0 < v1.
        // The implementation is designed so that during a single query, the
        // number of candidate edges can only grow.
        size_t mNumCandidateEdges;
        std::array<std::array<size_t, 2>, MAX_CANDIDATE_EDGES> mCandidateEdges;

        // The mAdjancencyMatrix is a simple representation of edges in the
        // graph G = (V,E) that represents the (wireframe) clipped box.  An
        // edge (r,c) does not exist when mAdjancencyMatrix[r][c] = 0.  If an
        // edge (r,c) does exist, it is appended to mCandidateEdges at index k
        // and the adjacency matrix is set to mAdjacencyMatrix[r][c] = 1.
        // This allows for a fast edge-in-graph test and a fast and efficient
        // clear of mCandidateEdges and mAdjacencyMatrix.
        std::array<std::array<size_t, MAX_VERTICES>, MAX_VERTICES> mAdjacencyMatrix;

        typedef void (TIQuery::* ConfigurationFunction)(size_t, Face const&);
        std::array<ConfigurationFunction, NUM_CONFIGURATIONS> mConfiguration;

        static void ComputeBoxHeightInterval(AlignedBox<3, Real> const& box, Cone<3, Real> const& cone,
            Real& boxMinHeight, Real& boxMaxHeight)
        {
            Vector<3, Real> C, e;
            box.GetCenteredForm(C, e);
            Vector<3, Real> const& V = cone.ray.origin;
            Vector<3, Real> const& U = cone.ray.direction;
            Vector<3, Real> CmV = C - V;
            Real DdCmV = Dot(U, CmV);
            Real radius = e[0] * std::abs(U[0]) + e[1] * std::abs(U[1]) + e[2] * std::abs(U[2]);
            boxMinHeight = DdCmV - radius;
            boxMaxHeight = DdCmV + radius;
        }

        static bool ConeAxisIntersectsBox(AlignedBox<3, Real> const& box, Cone<3, Real> const& cone)
        {
            if (cone.IsFinite())
            {
                Segment<3, Real> segment;
                segment.p[0] = cone.ray.origin + cone.GetMinHeight() * cone.ray.direction;
                segment.p[1] = cone.ray.origin + cone.GetMaxHeight() * cone.ray.direction;
                auto sbResult = TIQuery<Real, Segment<3, Real>, AlignedBox<3, Real>>()(segment, box);
                if (sbResult.intersect)
                {
                    return true;
                }
            }
            else
            {
                Ray<3, Real> ray;
                ray.origin = cone.ray.origin + cone.GetMinHeight() * cone.ray.direction;
                ray.direction = cone.ray.direction;
                auto rbResult = TIQuery<Real, Ray<3, Real>, AlignedBox<3, Real>>()(ray, box);
                if (rbResult.intersect)
                {
                    return true;
                }
            }
            return false;
        }

        bool BoxFullyInConeSlab(AlignedBox<3, Real> const& box, Real boxMinHeight, Real boxMaxHeight, Cone<3, Real> const& cone)
        {
            // Compute the box vertices relative to cone vertex as origin.
            mVertices[0] = { box.min[0], box.min[1], box.min[2] };
            mVertices[1] = { box.max[0], box.min[1], box.min[2] };
            mVertices[2] = { box.min[0], box.max[1], box.min[2] };
            mVertices[3] = { box.max[0], box.max[1], box.min[2] };
            mVertices[4] = { box.min[0], box.min[1], box.max[2] };
            mVertices[5] = { box.max[0], box.min[1], box.max[2] };
            mVertices[6] = { box.min[0], box.max[1], box.max[2] };
            mVertices[7] = { box.max[0], box.max[1], box.max[2] };
            for (int i = 0; i < NUM_BOX_VERTICES; ++i)
            {
                mVertices[i] -= cone.ray.origin;
            }

            Real coneMaxHeight = (cone.IsFinite() ? cone.GetMaxHeight() : std::numeric_limits<Real>::max());
            if (cone.GetMinHeight() <= boxMinHeight && boxMaxHeight <= coneMaxHeight)
            {
                // The box is fully inside, so no clipping is necessary.
                std::copy(mEdges.begin(), mEdges.end(), mCandidateEdges.begin());
                mNumCandidateEdges = 12;
                return true;
            }
            return false;
        }

        static bool HasPointInsideCone(Vector<3, Real> const& P0, Vector<3, Real> const& P1,
            Cone<3, Real> const& cone)
        {
            // Define F(X) = Dot(U,X - V)/|X - V|, where U is the unit-length
            // cone axis direction and V is the cone vertex.  The incoming
            // points P0 and P1 are relative to V; that is, the original
            // points are X0 = P0 + V and X1 = P1 + V.  The segment <P0,P1>
            // and cone intersect when a segment point X is inside the cone;
            // that is, when F(X) > cosAngle.  The comparison is converted to
            // an equivalent one that does not involve divisions in order to
            // avoid a division by zero if a vertex or edge contain (0,0,0).
            // The function is G(X) = Dot(U,X-V) - cosAngle*Length(X-V).
            Vector<3, Real> const& U = cone.ray.direction;

            // Test whether P0 or P1 is inside the cone.
            Real g = Dot(U, P0) - cone.cosAngle * Length(P0);
            if (g > (Real)0)
            {
                // X0 = P0 + V is inside the cone.
                return true;
            }

            g = Dot(U, P1) - cone.cosAngle * Length(P1);
            if (g > (Real)0)
            {
                // X1 = P1 + V is inside the cone.
                return true;
            }

            // Test whether an interior segment point is inside the cone.
            Vector<3, Real> E = P1 - P0;
            Vector<3, Real> crossP0U = Cross(P0, U);
            Vector<3, Real> crossP0E = Cross(P0, E);
            Real dphi0 = Dot(crossP0E, crossP0U);
            if (dphi0 > (Real)0)
            {
                Vector3<Real> crossP1U = Cross(P1, U);
                Real dphi1 = Dot(crossP0E, crossP1U);
                if (dphi1 < (Real)0)
                {
                    Real t = dphi0 / (dphi0 - dphi1);
                    Vector<3, Real> PMax = P0 + t * E;
                    g = Dot(U, PMax) - cone.cosAngle * Length(PMax);
                    if (g > (Real)0)
                    {
                        // The edge point XMax = Pmax + V is inside the cone.
                        return true;
                    }
                }
            }

            return false;
        }

        bool CandidatesHavePointInsideCone(Cone<3, Real> const& cone) const
        {
            for (size_t i = 0; i < mNumCandidateEdges; ++i)
            {
                auto const& edge = mCandidateEdges[i];
                Vector<3, Real> const& P0 = mVertices[edge[0]];
                Vector<3, Real> const& P1 = mVertices[edge[1]];
                if (HasPointInsideCone(P0, P1, cone))
                {
                    return true;
                }
            }
            return false;
        }

        void ComputeCandidatesOnBoxEdges(Cone<3, Real> const& cone)
        {
            for (size_t i = 0; i < NUM_BOX_VERTICES; ++i)
            {
                Real h = Dot(cone.ray.direction, mVertices[i]);
                Real coneMaxHeight = (cone.IsFinite() ? cone.GetMaxHeight() : std::numeric_limits<Real>::max());
                mProjectionMin[i] = cone.GetMinHeight() - h;
                mProjectionMax[i] = h - coneMaxHeight;
            }

            size_t v0 = VERTEX_MIN_BASE, v1 = VERTEX_MAX_BASE;
            for (size_t i = 0; i < NUM_BOX_EDGES; ++i, ++v0, ++v1)
            {
                auto const& edge = mEdges[i];

                // In the next blocks, the sign comparisons can be expressed
                // instead as "s0 * s1 < 0". The multiplication could lead to
                // floating-point underflow where the product becomes 0, so I
                // avoid that approach.

                // Process the hmin-plane.
                Real p0Min = mProjectionMin[edge[0]];
                Real p1Min = mProjectionMin[edge[1]];
                bool clipMin = (p0Min < (Real)0 && p1Min >(Real)0) || (p0Min > (Real)0 && p1Min < (Real)0);
                if (clipMin)
                {
                    mVertices[v0] = (p1Min * mVertices[edge[0]] - p0Min * mVertices[edge[1]]) / (p1Min - p0Min);
                }

                // Process the hmax-plane.
                Real p0Max = mProjectionMax[edge[0]];
                Real p1Max = mProjectionMax[edge[1]];
                bool clipMax = (p0Max < (Real)0 && p1Max >(Real)0) || (p0Max > (Real)0 && p1Max < (Real)0);
                if (clipMax)
                {
                    mVertices[v1] = (p1Max * mVertices[edge[0]] - p0Max * mVertices[edge[1]]) / (p1Max - p0Max);
                }

                // Get the candidate edges that are contained by the box edges.
                if (clipMin)
                {
                    if (clipMax)
                    {
                        InsertEdge(v0, v1);
                    }
                    else
                    {
                        if (p0Min < (Real)0)
                        {
                            InsertEdge(edge[0], v0);
                        }
                        else  // p1Min < 0
                        {
                            InsertEdge(edge[1], v0);
                        }
                    }
                }
                else if (clipMax)
                {
                    if (p0Max < (Real)0)
                    {
                        InsertEdge(edge[0], v1);
                    }
                    else  // p1Max < 0
                    {
                        InsertEdge(edge[1], v1);
                    }
                }
                else
                {
                    // No clipping has occurred.  If the edge is inside the box,
                    // it is a candidate edge.  To be inside the box, the p*min
                    // and p*max values must be nonpositive.
                    if (p0Min <= (Real)0 && p1Min <= (Real)0 && p0Max <= (Real)0 && p1Max <= (Real)0)
                    {
                        InsertEdge(edge[0], edge[1]);
                    }
                }
            }
        }

        void ComputeCandidatesOnBoxFaces()
        {
            Real p0, p1, p2, p3;
            size_t b0, b1, b2, b3, index;
            for (size_t i = 0; i < NUM_BOX_FACES; ++i)
            {
                auto const& face = mFaces[i];

                // Process the hmin-plane.
                p0 = mProjectionMin[face.v[0]];
                p1 = mProjectionMin[face.v[1]];
                p2 = mProjectionMin[face.v[2]];
                p3 = mProjectionMin[face.v[3]];
                b0 = (p0 < (Real)0 ? 0 : (p0 > (Real)0 ? 2 : 1));
                b1 = (p1 < (Real)0 ? 0 : (p1 > (Real)0 ? 2 : 1));
                b2 = (p2 < (Real)0 ? 0 : (p2 > (Real)0 ? 2 : 1));
                b3 = (p3 < (Real)0 ? 0 : (p3 > (Real)0 ? 2 : 1));
                index = b3 + 3 * (b2 + 3 * (b1 + 3 * b0));
                (this->*mConfiguration[index])(VERTEX_MIN_BASE, face);

                // Process the hmax-plane.
                p0 = mProjectionMax[face.v[0]];
                p1 = mProjectionMax[face.v[1]];
                p2 = mProjectionMax[face.v[2]];
                p3 = mProjectionMax[face.v[3]];
                b0 = (p0 < (Real)0 ? 0 : (p0 > (Real)0 ? 2 : 1));
                b1 = (p1 < (Real)0 ? 0 : (p1 > (Real)0 ? 2 : 1));
                b2 = (p2 < (Real)0 ? 0 : (p2 > (Real)0 ? 2 : 1));
                b3 = (p3 < (Real)0 ? 0 : (p3 > (Real)0 ? 2 : 1));
                index = b3 + 3 * (b2 + 3 * (b1 + 3 * b0));
                (this->*mConfiguration[index])(VERTEX_MAX_BASE, face);
            }
        }

        void ClearCandidates()
        {
            for (size_t i = 0; i < mNumCandidateEdges; ++i)
            {
                auto const& edge = mCandidateEdges[i];
                mAdjacencyMatrix[edge[0]][edge[1]] = 0;
                mAdjacencyMatrix[edge[1]][edge[0]] = 0;
            }
            mNumCandidateEdges = 0;
        }

        void InsertEdge(size_t v0, size_t v1)
        {
            if (mAdjacencyMatrix[v0][v1] == 0)
            {
                mAdjacencyMatrix[v0][v1] = 1;
                mAdjacencyMatrix[v1][v0] = 1;
                mCandidateEdges[mNumCandidateEdges] = { v0, v1 };
                ++mNumCandidateEdges;
            }
        }

        // The 81 possible configurations for a box face.  The N stands for a
        // '-', the Z stands for '0' and the P stands for '+'.  These are
        // listed in the order that maps to the array mConfiguration.  Thus,
        // NNNN maps to mConfiguration[0], NNNZ maps to mConfiguration[1], and
        // so on.
        void NNNN_0(size_t, Face const&)
        {
        }

        void NNNZ_1(size_t, Face const&)
        {
        }

        void NNNP_2(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[2], base + face.e[3]);
        }

        void NNZN_3(size_t, Face const&)
        {
        }

        void NNZZ_4(size_t, Face const&)
        {
        }

        void NNZP_5(size_t base, Face const& face)
        {
            InsertEdge(face.v[2], base + face.e[3]);
        }

        void NNPN_6(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[1], base + face.e[2]);
        }

        void NNPZ_7(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[1], face.v[3]);
        }

        void NNPP_8(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[1], base + face.e[3]);
        }

        void NZNN_9(size_t, Face const&)
        {
        }

        void NZNZ_10(size_t, Face const&)
        {
        }

        void NZNP_11(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[2], face.v[3]);
            InsertEdge(base + face.e[3], face.v[3]);
        }

        void NZZN_12(size_t, Face const&)
        {
        }

        void NZZZ_13(size_t, Face const&)
        {
        }

        void NZZP_14(size_t base, Face const& face)
        {
            InsertEdge(face.v[2], face.v[3]);
            InsertEdge(base + face.e[3], face.v[3]);
        }

        void NZPN_15(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[2], face.v[1]);
        }

        void NZPZ_16(size_t, Face const& face)
        {
            InsertEdge(face.v[1], face.v[3]);
        }

        void NZPP_17(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[3], face.v[1]);
        }

        void NPNN_18(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[0], base + face.e[1]);
        }

        void NPNZ_19(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[0], face.v[1]);
            InsertEdge(base + face.e[1], face.v[1]);
        }

        void NPNP_20(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[0], face.v[1]);
            InsertEdge(base + face.e[1], face.v[1]);
            InsertEdge(base + face.e[2], face.v[3]);
            InsertEdge(base + face.e[3], face.v[3]);
        }

        void NPZN_21(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[0], face.v[2]);
        }

        void NPZZ_22(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[0], face.v[1]);
            InsertEdge(face.v[1], face.v[2]);
        }

        void NPZP_23(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[0], face.v[1]);
            InsertEdge(face.v[1], face.v[2]);
            InsertEdge(base + face.e[3], face.v[2]);
            InsertEdge(face.v[2], face.v[3]);
        }

        void NPPN_24(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[0], base + face.e[2]);
        }

        void NPPZ_25(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[0], face.v[3]);
        }

        void NPPP_26(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[0], base + face.e[3]);
        }

        void ZNNN_27(size_t, Face const&)
        {
        }

        void ZNNZ_28(size_t, Face const&)
        {
        }

        void ZNNP_29(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[2], face.v[0]);
        }

        void ZNZN_30(size_t, Face const&)
        {
        }

        void ZNZZ_31(size_t, Face const&)
        {
        }

        void ZNZP_32(size_t, Face const& face)
        {
            InsertEdge(face.v[0], face.v[2]);
        }

        void ZNPN_33(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[1], face.v[2]);
            InsertEdge(base + face.e[2], face.v[2]);
        }

        void ZNPZ_34(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[1], face.v[2]);
            InsertEdge(face.v[2], face.v[3]);
        }

        void ZNPP_35(size_t base, Face const& face)
        {
            InsertEdge(face.v[0], base + face.e[1]);
        }

        void ZZNN_36(size_t, Face const&)
        {
        }

        void ZZNZ_37(size_t, Face const&)
        {
        }

        void ZZNP_38(size_t base, Face const& face)
        {
            InsertEdge(face.v[0], face.v[3]);
            InsertEdge(face.v[3], base + face.e[2]);
        }

        void ZZZN_39(size_t, Face const&)
        {
        }

        void ZZZZ_40(size_t, Face const&)
        {
        }

        void ZZZP_41(size_t, Face const& face)
        {
            InsertEdge(face.v[0], face.v[3]);
            InsertEdge(face.v[3], face.v[2]);
        }

        void ZZPN_42(size_t base, Face const& face)
        {
            InsertEdge(face.v[1], face.v[2]);
            InsertEdge(face.v[2], base + face.e[2]);
        }

        void ZZPZ_43(size_t, Face const& face)
        {
            InsertEdge(face.v[1], face.v[2]);
            InsertEdge(face.v[2], face.v[3]);
        }

        void ZZPP_44(size_t, Face const&)
        {
        }

        void ZPNN_45(size_t base, Face const& face)
        {
            InsertEdge(face.v[0], base + face.e[1]);
        }

        void ZPNZ_46(size_t base, Face const& face)
        {
            InsertEdge(face.v[0], face.v[1]);
            InsertEdge(face.v[1], base + face.e[1]);
        }

        void ZPNP_47(size_t base, Face const& face)
        {
            InsertEdge(face.v[0], face.v[1]);
            InsertEdge(face.v[1], base + face.e[1]);
            InsertEdge(base + face.e[2], face.v[3]);
            InsertEdge(face.v[3], face.v[0]);
        }

        void ZPZN_48(size_t, Face const& face)
        {
            InsertEdge(face.v[0], face.v[2]);
        }

        void ZPZZ_49(size_t, Face const& face)
        {
            InsertEdge(face.v[0], face.v[1]);
            InsertEdge(face.v[1], face.v[2]);
        }

        void ZPZP_50(size_t, Face const&)
        {
        }

        void ZPPN_51(size_t base, Face const& face)
        {
            InsertEdge(face.v[0], base + face.e[2]);
        }

        void ZPPZ_52(size_t, Face const&)
        {
        }

        void ZPPP_53(size_t, Face const&)
        {
        }

        void PNNN_54(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[3], base + face.e[0]);
        }

        void PNNZ_55(size_t base, Face const& face)
        {
            InsertEdge(face.v[3], base + face.e[0]);
        }

        void PNNP_56(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[2], base + face.e[0]);
        }

        void PNZN_57(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[3], face.v[0]);
            InsertEdge(face.v[0], base + face.e[0]);
        }

        void PNZZ_58(size_t base, Face const& face)
        {
            InsertEdge(face.v[3], face.v[0]);
            InsertEdge(face.v[0], base + face.e[0]);
        }

        void PNZP_59(size_t base, Face const& face)
        {
            InsertEdge(face.v[2], base + face.e[0]);
        }

        void PNPN_60(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[3], face.v[0]);
            InsertEdge(face.v[0], base + face.e[0]);
            InsertEdge(base + face.e[1], face.v[2]);
            InsertEdge(face.v[2], base + face.e[2]);
        }

        void PNPZ_61(size_t base, Face const& face)
        {
            InsertEdge(face.v[3], face.v[0]);
            InsertEdge(face.v[0], base + face.e[0]);
            InsertEdge(base + face.e[1], face.v[2]);
            InsertEdge(face.v[2], face.v[3]);
        }

        void PNPP_62(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[0], base + face.e[1]);
        }

        void PZNN_63(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[3], face.v[1]);
        }

        void PZNZ_64(size_t, Face const& face)
        {
            InsertEdge(face.v[3], face.v[1]);
        }

        void PZNP_65(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[2], face.v[1]);
        }

        void PZZN_66(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[3], face.v[0]);
            InsertEdge(face.v[0], face.v[1]);
        }

        void PZZZ_67(size_t, Face const&)
        {
        }

        void PZZP_68(size_t, Face const&)
        {
        }

        void PZPN_69(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[3], face.v[0]);
            InsertEdge(face.v[0], face.v[1]);
            InsertEdge(face.v[1], face.v[2]);
            InsertEdge(face.v[2], base + face.e[2]);
        }

        void PZPZ_70(size_t, Face const&)
        {
        }

        void PZPP_71(size_t, Face const&)
        {
        }

        void PPNN_72(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[3], base + face.e[1]);
        }

        void PPNZ_73(size_t base, Face const& face)
        {
            InsertEdge(face.v[3], base + face.e[1]);
        }

        void PPNP_74(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[2], base + face.e[1]);
        }

        void PPZN_75(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[2], face.v[2]);
        }

        void PPZZ_76(size_t, Face const&)
        {
        }

        void PPZP_77(size_t, Face const&)
        {
        }

        void PPPN_78(size_t base, Face const& face)
        {
            InsertEdge(base + face.e[3], base + face.e[2]);
        }

        void PPPZ_79(size_t, Face const&)
        {
        }

        void PPPP_80(size_t, Face const&)
        {
        }
    };

    // Template alias for convenience.
    template <typename Real>
    using TIAlignedBox3Cone3 = TIQuery<Real, AlignedBox<3, Real>, Cone<3, Real>>;
}