tetrees/Plugins/Wwise/Source/AkAudio/Classes/GTE/Mathematics/SplitMeshByPlane.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/DistPoint3Plane3.h>
#include <Mathematics/EdgeKey.h>
#include <map>

// The algorithm for splitting a mesh by a plane is described in
// https://www.geometrictools.com/Documentation/ClipMesh.pdf
// Currently, the code here does not include generating a closed
// mesh (from the "positive" and "zero" vertices) by attaching
// triangulated faces to the mesh, where the those faces live in
// the splitting plane.  (TODO: Add this code.)

namespace WwiseGTE
{
    template <typename Real>
    class SplitMeshByPlane
    {
    public:
        // The 'indices' are lookups into the 'vertices' array.  The indices
        // represent a triangle mesh.  The number of indices must be a
        // multiple of 3, each triple representing a triangle.  If t is a
        // triangle index, then the triangle is formed by
        // vertices[indices[3 * t + i]] for 0 <= i <= 2.  The outputs
        // 'negIndices' and 'posIndices' are formatted similarly.
        void operator()(
            std::vector<Vector3<Real>> const& vertices,
            std::vector<int> const& indices,
            Plane3<Real> const& plane,
            std::vector<Vector3<Real>>& clipVertices,
            std::vector<int>& negIndices,
            std::vector<int>& posIndices)
        {
            mSignedDistances.resize(vertices.size());
            mEMap.clear();

            // Make a copy of the incoming vertices.  If the mesh intersects
            // the plane, new vertices must be generated.  These are appended
            // to the clipVertices array.
            clipVertices = vertices;

            ClassifyVertices(clipVertices, plane);
            ClassifyEdges(clipVertices, indices);
            ClassifyTriangles(indices, negIndices, posIndices);
        }

    private:
        void ClassifyVertices(std::vector<Vector3<Real>> const& clipVertices,
            Plane3<Real> const& plane)
        {
            DCPQuery<Real, Vector3<Real>, Plane3<Real>> query;
            for (size_t i = 0; i < clipVertices.size(); ++i)
            {
                mSignedDistances[i] = query(clipVertices[i], plane).signedDistance;
            }
        }

        void ClassifyEdges(std::vector<Vector3<Real>>& clipVertices,
            std::vector<int> const& indices)
        {
            int const numTriangles = static_cast<int>(indices.size() / 3);
            int nextIndex = static_cast<int>(clipVertices.size());
            for (int i = 0; i < numTriangles; ++i)
            {
                int v0 = indices[3 * i + 0];
                int v1 = indices[3 * i + 1];
                int v2 = indices[3 * i + 2];
                Real sDist0 = mSignedDistances[v0];
                Real sDist1 = mSignedDistances[v1];
                Real sDist2 = mSignedDistances[v2];

                EdgeKey<false> key;
                Real t;
                Vector3<Real> intr, diff;

                // The change-in-sign tests are structured this way to avoid
                // numerical round-off problems.  For example, sDist0 > 0 and
                // sDist1 < 0, but both are very small and sDist0 * sDist1 = 0
                // because of round-off errors.  The tests also guarantee
                // consistency between this function and ClassifyTriangles,
                // the latter function using sign tests only on the individual
                // sDist values.

                if ((sDist0 > (Real)0 && sDist1 < (Real)0)
                    || (sDist0 < (Real)0 && sDist1 >(Real)0))
                {
                    key = EdgeKey<false>(v0, v1);
                    if (mEMap.find(key) == mEMap.end())
                    {
                        t = sDist0 / (sDist0 - sDist1);
                        diff = clipVertices[v1] - clipVertices[v0];
                        intr = clipVertices[v0] + t * diff;
                        clipVertices.push_back(intr);
                        mEMap[key] = std::make_pair(intr, nextIndex);
                        ++nextIndex;
                    }
                }

                if ((sDist1 > (Real)0 && sDist2 < (Real)0)
                    || (sDist1 < (Real)0 && sDist2 >(Real)0))
                {
                    key = EdgeKey<false>(v1, v2);
                    if (mEMap.find(key) == mEMap.end())
                    {
                        t = sDist1 / (sDist1 - sDist2);
                        diff = clipVertices[v2] - clipVertices[v1];
                        intr = clipVertices[v1] + t * diff;
                        clipVertices.push_back(intr);
                        mEMap[key] = std::make_pair(intr, nextIndex);
                        ++nextIndex;
                    }
                }

                if ((sDist2 > (Real)0 && sDist0 < (Real)0)
                    || (sDist2 < (Real)0 && sDist0 >(Real)0))
                {
                    key = EdgeKey<false>(v2, v0);
                    if (mEMap.find(key) == mEMap.end())
                    {
                        t = sDist2 / (sDist2 - sDist0);
                        diff = clipVertices[v0] - clipVertices[v2];
                        intr = clipVertices[v2] + t * diff;
                        clipVertices.push_back(intr);
                        mEMap[key] = std::make_pair(intr, nextIndex);
                        ++nextIndex;
                    }
                }
            }
        }

        void ClassifyTriangles(std::vector<int> const& indices,
            std::vector<int>& negIndices, std::vector<int>& posIndices)
        {
            int const numTriangles = static_cast<int>(indices.size() / 3);
            for (int i = 0; i < numTriangles; ++i)
            {
                int v0 = indices[3 * i + 0];
                int v1 = indices[3 * i + 1];
                int v2 = indices[3 * i + 2];
                Real sDist0 = mSignedDistances[v0];
                Real sDist1 = mSignedDistances[v1];
                Real sDist2 = mSignedDistances[v2];

                if (sDist0 > (Real)0)
                {
                    if (sDist1 > (Real)0)
                    {
                        if (sDist2 > (Real)0)
                        {
                            // +++
                            AppendTriangle(posIndices, v0, v1, v2);
                        }
                        else if (sDist2 < (Real)0)
                        {
                            // ++-
                            SplitTrianglePPM(negIndices, posIndices, v0, v1, v2);
                        }
                        else
                        {
                            // ++0
                            AppendTriangle(posIndices, v0, v1, v2);
                        }
                    }
                    else if (sDist1 < (Real)0)
                    {
                        if (sDist2 > (Real)0)
                        {
                            // +-+
                            SplitTrianglePPM(negIndices, posIndices, v2, v0, v1);
                        }
                        else if (sDist2 < (Real)0)
                        {
                            // +--
                            SplitTriangleMMP(negIndices, posIndices, v1, v2, v0);
                        }
                        else
                        {
                            // +-0
                            SplitTrianglePMZ(negIndices, posIndices, v0, v1, v2);
                        }
                    }
                    else
                    {
                        if (sDist2 > (Real)0)
                        {
                            // +0+
                            AppendTriangle(posIndices, v0, v1, v2);
                        }
                        else if (sDist2 < (Real)0)
                        {
                            // +0-
                            SplitTriangleMPZ(negIndices, posIndices, v2, v0, v1);
                        }
                        else
                        {
                            // +00
                            AppendTriangle(posIndices, v0, v1, v2);
                        }
                    }
                }
                else if (sDist0 < (Real)0)
                {
                    if (sDist1 > (Real)0)
                    {
                        if (sDist2 > (Real)0)
                        {
                            // -++
                            SplitTrianglePPM(negIndices, posIndices, v1, v2, v0);
                        }
                        else if (sDist2 < (Real)0)
                        {
                            // -+-
                            SplitTriangleMMP(negIndices, posIndices, v2, v0, v1);
                        }
                        else
                        {
                            // -+0
                            SplitTriangleMPZ(negIndices, posIndices, v0, v1, v2);
                        }
                    }
                    else if (sDist1 < (Real)0)
                    {
                        if (sDist2 > (Real)0)
                        {
                            // --+
                            SplitTriangleMMP(negIndices, posIndices, v0, v1, v2);
                        }
                        else if (sDist2 < (Real)0)
                        {
                            // ---
                            AppendTriangle(negIndices, v0, v1, v2);
                        }
                        else
                        {
                            // --0
                            AppendTriangle(negIndices, v0, v1, v2);
                        }
                    }
                    else
                    {
                        if (sDist2 > (Real)0)
                        {
                            // -0+
                            SplitTrianglePMZ(negIndices, posIndices, v2, v0, v1);
                        }
                        else if (sDist2 < (Real)0)
                        {
                            // -0-
                            AppendTriangle(negIndices, v0, v1, v2);
                        }
                        else
                        {
                            // -00
                            AppendTriangle(negIndices, v0, v1, v2);
                        }
                    }
                }
                else
                {
                    if (sDist1 > (Real)0)
                    {
                        if (sDist2 > (Real)0)
                        {
                            // 0++
                            AppendTriangle(posIndices, v0, v1, v2);
                        }
                        else if (sDist2 < (Real)0)
                        {
                            // 0+-
                            SplitTrianglePMZ(negIndices, posIndices, v1, v2, v0);
                        }
                        else
                        {
                            // 0+0
                            AppendTriangle(posIndices, v0, v1, v2);
                        }
                    }
                    else if (sDist1 < (Real)0)
                    {
                        if (sDist2 > (Real)0)
                        {
                            // 0-+
                            SplitTriangleMPZ(negIndices, posIndices, v1, v2, v0);
                        }
                        else if (sDist2 < (Real)0)
                        {
                            // 0--
                            AppendTriangle(negIndices, v0, v1, v2);
                        }
                        else
                        {
                            // 0-0
                            AppendTriangle(negIndices, v0, v1, v2);
                        }
                    }
                    else
                    {
                        if (sDist2 > (Real)0)
                        {
                            // 00+
                            AppendTriangle(posIndices, v0, v1, v2);
                        }
                        else if (sDist2 < (Real)0)
                        {
                            // 00-
                            AppendTriangle(negIndices, v0, v1, v2);
                        }
                        else
                        {
                            // 000, reject triangles lying in the plane
                        }
                    }
                }
            }
        }

        void AppendTriangle(std::vector<int>& indices, int v0, int v1, int v2)
        {
            indices.push_back(v0);
            indices.push_back(v1);
            indices.push_back(v2);
        }

        void SplitTrianglePPM(std::vector<int>& negIndices,
            std::vector<int>& posIndices, int v0, int v1, int v2)
        {
            int v12 = mEMap[EdgeKey<false>(v1, v2)].second;
            int v20 = mEMap[EdgeKey<false>(v2, v0)].second;
            posIndices.push_back(v0);
            posIndices.push_back(v1);
            posIndices.push_back(v12);
            posIndices.push_back(v0);
            posIndices.push_back(v12);
            posIndices.push_back(v20);
            negIndices.push_back(v2);
            negIndices.push_back(v20);
            negIndices.push_back(v12);
        }

        void SplitTriangleMMP(std::vector<int>& negIndices,
            std::vector<int>& posIndices, int v0, int v1, int v2)
        {
            int v12 = mEMap[EdgeKey<false>(v1, v2)].second;
            int v20 = mEMap[EdgeKey<false>(v2, v0)].second;
            negIndices.push_back(v0);
            negIndices.push_back(v1);
            negIndices.push_back(v12);
            negIndices.push_back(v0);
            negIndices.push_back(v12);
            negIndices.push_back(v20);
            posIndices.push_back(v2);
            posIndices.push_back(v20);
            posIndices.push_back(v12);
        }

        void SplitTrianglePMZ(std::vector<int>& negIndices,
            std::vector<int>& posIndices, int v0, int v1, int v2)
        {
            int v01 = mEMap[EdgeKey<false>(v0, v1)].second;
            posIndices.push_back(v2);
            posIndices.push_back(v0);
            posIndices.push_back(v01);
            negIndices.push_back(v2);
            negIndices.push_back(v01);
            negIndices.push_back(v1);
        }

        void SplitTriangleMPZ(std::vector<int>& negIndices,
            std::vector<int>& posIndices, int v0, int v1, int v2)
        {
            int v01 = mEMap[EdgeKey<false>(v0, v1)].second;
            negIndices.push_back(v2);
            negIndices.push_back(v0);
            negIndices.push_back(v01);
            posIndices.push_back(v2);
            posIndices.push_back(v01);
            posIndices.push_back(v1);
        }

        // Stores the signed distances from the vertices to the plane.
        std::vector<Real> mSignedDistances;

        // Stores the edges whose vertices are on opposite sides of the
        // plane.  The key is a pair of indices into the vertex array.
        // The value is the point of intersection of the edge with the
        // plane and an index into m_kVertices (the index is larger or
        // equal to the number of vertices of incoming rkVertices).
        std::map<EdgeKey<false>, std::pair<Vector3<Real>, int>> mEMap;
    };
}