#define BEHIND -1
#define COINCIDING 0
#define IN_FRONT 1
#define EPSILON 1.0e-3f

// TAKES: a signed distance 'dist' to the plane
// RETURNS: integer indicating side of input distance
int plane3::classify(const float dist) const
{
    if (dist < -EPSILON)    { return BEHIND; }
    if (dist > EPSILON)     { return IN_FRONT; }
    return COINCIDING;
}

// TAKES: a polygon 'in', a clipped polygon 'out'
// RETURNS: number of vertices in polygon 'out'; clipped polygon 'out'
// MEMBERS: point on plane 'pos', normal of plane 'nor'
void plane3::clip(const array<vec3> &in, array<vec3> &out) const
{
    out.alloc(in.size() + 1); // make room for max number of out verts
    array<float> dist;
    array<int> side;
    dist.alloc(in.size());
    side.alloc(in.size());
    int numOut = 0;
    for (int i = 0; i < in.size(); ++i) {
        dist[i] = dot(in[i] - pos, nor);
        side[i] = classify(dist[i]);
        if (side[i] <= COINCIDING) { ++numOut; }
    }
    if (numOut == in.size()) { // all verts are either behind, or on, plane
        out.dealloc();
        return;
    }
    int numIn = 0;
    for (int i = 0, j = in.size() - 1; i < in.size(); j=i, ++i) {
        if ((side[i] < COINCIDING) == (side[j] >= COINCIDING)) {
            out[numIn++] = in[i] + (in[j] - in[i]) * (dist[i] / (dist[i] - dist[j]));
        }
        if (side[i] >= COINCIDING) {
            out[numIn++] = in[i];
        }
    }
    out.resize(numIn); // resize to actual size of output poly (numIn <= out.size())
}