/*
    Read

        http://z0b.kapsi.fi/snippets.php

    before using this code. Thank you.
*/

// ADDED ON 2017-03-11: This code might be broken. I tested it recently and it
// needed some changes that I didn't document (sorry :-( ). If this gives you
// weird results, take the generic polygon clipper (see below) and make it loop
// over multiple planes, the changes aren't big.

/*
    Clips a contex polygon against 1 or more hyperplanes, returning the fragment
    that was inside (on the front side) of all planes. Returns true if the final
    polygon is valid, false if not.
    'in' == source polygon (convex)
    'clip' == vector of clipping planes, front sides facing inside
    'out' == output polygon (convex), can be NULL (check the return value)
*/
bool clipPolyToPlanes(const std::vector<math::vec3> &in,
                      const std::vector<math::plane> &clip,
                      std::vector<math::vec3> *out,
                      const float epsilon = 0.001f)
{
    if (in.size() < 3 || clip.empty())
        return false;

    if (out)
        out->clear();

    std::vector<math::vec3> input(in), output;

    for (const math::plane &p : clip) {
        if (input.size() < 3)
            return false;

        const math::vec3 &vtxA = input[input.size() - 1];
        const float distA = p.distance(vtxA);

        for (size_t i = 0, j = input.size(); i < j; i++) {
            const math::vec3 &vtxB = input[i];
            const float distB = p.distance(vtxB);

            const math::vec3 d = vtxB - vtxA;

            if (distB < -epsilon) {
                // spans
                if (distA > epsilon)
                    output.push_back(vtxA + (d * -(distA / p.n.dot(d))));
            } else if (distB > epsilon) {
                // spans
                if (distA < -epsilon)
                    output.push_back(vtxA + (d * -(distA / p.n.dot(d))));

                output.push_back(vtxB);
            } else {
                // not spanning
                output.push_back(vtxB);
            }

            vtxA = vtxB;
            distA = distB;
        }

        // next plane
        input = output;
        output.clear();
    }

    if (out)
        *out = input;

    // something valid still left after all this clipping?
    return input.size() > 2;
}