/**
 *  This class implements 3D polygon clipping in homogeneous 
 *coordinates using the Sutherland-Hodgemann algorithm.
 */

public class Clipper {
    Vertex3D v[];
    Face f[];
    ColorPair c[];
    byte outCodes[];
    boolean vertexVisible[];
    boolean faceInvisible[];
    int indexPool[][];
    int vertices, faces;
    int newvertices, newfaces;
    int viewType;
    
    // outcodes for trivial rejection / acception
    public static final byte LEFT = 16;
    public static final byte RIGHT = 2;
    public static final byte UP = 4;
    public static final byte DOWN = 8;
    public static final byte NEAR = 1;
    public static final byte FAR = 32;
    
    
    PlaneEqn planeEqs[]; // plane equations defining the box to clip against

    /** 
     *  Default Constructor.
     */
    Clipper() {
    }
    
    /**
     *  Pass in a PolygonObject to be clipped.
     */
    Clipper(PolygonObject p, int viewType) 
    {
        v = p.viewList;
        f = p.faceList;
        vertices = p.vertices;
        faces = p.faces;
        c = p.vertColors;
        outCodes = p.outCodes;
        vertexVisible = p.vertexVisible;
        faceInvisible = p.faceInvisible;
        indexPool = p.indexPool;
        viewType = viewType;
        
        initViewVolumePlaneEqns(); // setup plane equations
        computeOutcodes(); // compute outcodes per vertex
    }
    
    /** 
     *  This computes the outcode for each vertex.  This can save time
     *  when clipping an object whose faces share many vertices.
     */
    void computeOutcodes() 
    {        
        for (int i=0; i < vertices; ++i) 
            computeOutcode(v, i);
    }

    byte all = LEFT | RIGHT | UP | DOWN | NEAR | FAR;
    
    /**
     *  Computes the outcode for one vertex.
     */
    void computeOutcode(Vertex3D v[], int i) 
    {
        byte out;
        out = 0;
        
        if (viewType == Constants.PERSPECTIVE) {
            if (v[i].w < 0.0f) {           
                if (Math.abs(v[i].w) < 0.001f) out = all;
                
                if (v[i].x > -v[i].w) out |= LEFT;
                else if (v[i].x < v[i].w) out |= RIGHT;
                if (v[i].y > -v[i].w) out |= UP;
                else if (v[i].y < v[i].w) out |= DOWN;
                if (v[i].z > -v[i].w) out |= NEAR;
                else if (v[i].z < v[i].w) out |= FAR;
                
            } else {
                if (Math.abs(v[i].w) < 0.001f) out = all;
     
                if (v[i].x < -v[i].w) out |= RIGHT;
                else if (v[i].x > v[i].w) out |= LEFT;
                if (v[i].y < -v[i].w) out |= DOWN;
                else if (v[i].y > v[i].w) out |= UP;
                if (v[i].z < -v[i].w) out |= FAR;
                else if (v[i].z > v[i].w) out |= NEAR;
            }
        } else if (viewType == Constants.ORTHOGRAPHIC) {
                if (v[i].x < -v[i].w) out |= LEFT;
                else if (v[i].x > v[i].w) out |= RIGHT;
                if (v[i].y < -v[i].w) out |= UP;
                else if (v[i].y > v[i].w) out |= DOWN;
                if (v[i].z < -v[i].w) out |= NEAR;
                else if (v[i].z > v[i].w) out |= FAR;
        
        }
        
        if (outCodes[i] != out) 
            outCodes[i] = out;
    }

    /** 
     *  Setup the canonical clipping volume plane equations.
     */
    void initViewVolumePlaneEqns() {
            planeEqs = new PlaneEqn[FAR + 1];
            planeEqs[LEFT] = new PlaneEqn(-1, 0, 0, -1);
            planeEqs[RIGHT] = new PlaneEqn(1, 0, 0, -1);
            planeEqs[UP] = new PlaneEqn(0, -1, 0, -1);
            planeEqs[DOWN] = new PlaneEqn(0, 1, 0, -1);
            planeEqs[NEAR] = new PlaneEqn(0, 0, -1, -1);
            planeEqs[FAR] = new PlaneEqn(0, 0, 1, -1);
    }
    
    /**
     *  Returns the number of faces in the clipped polygon object.
     */
    int getNewNumberFaces() {
        return newfaces;
    }

    /**
     *  Returns the number of vertices in the clipped polygon object.
     */
    int getNewNumberVertices() {
        return newvertices;
    }
    
    /**
     *  Implementation of the Sutherland-Hodgemann 3D polygon clipping 
     *  algorithm.
     */
    void sutherlandHodgeman() 
    {
        int i, n, pool;
        int index[], newindex[] = null;
        byte CODE = 1;
        byte j, k, num, newnum=0;
        boolean flag;
        boolean changed = false;
        newfaces = faces;
        newvertices = vertices;
        
        for (i=0, pool=0; i < faces; ++i) {
            if (faceInvisible[i]) continue;
            changed = false;
            num = (byte)f[i].num;
            index = f[i].index;
            if (newindex == null) newindex = indexPool[pool++];
            
            // trivial accept
            // check if all vertices are inside
            for (flag=false, j=0; j < num; ++j) {
                if (outCodes[index[j]] != 0) {
                    flag = true;
                    break;
                }
            }
            if (!flag) continue; // if so we're done
            
            // trivial reject
            // check if all vertices are outside any plane
            for (flag=false,CODE = 1; CODE < 33; CODE <<= 1) {
                for (j=0,k=0; j < num; ++j) {
                    if ((outCodes[index[j]] & CODE) != 0) ++k;     
                }
                if (k == num) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                faceInvisible[i] = true;
                continue; // if so we're done
            }
            
            
            // else we'll need to clip
            for (j=0, CODE = 1; j < 6; ++j, CODE <<= 1) {
                newnum = sutherlandHodgemanPlane(index, num, newindex, v, CODE);
                if (newnum == -1) continue;
                if (newnum == 0) {
                    faceInvisible[i] = true;
                    break;
                } else {
                    changed = true;
                    num = newnum;
                    index = newindex;
                    newindex = indexPool[pool++]; 
                } 
            }
            if (changed) {
                // this adds new faces onto the end of the faceList
                // the new faces are broken into triangles
                faceInvisible[i] = true;
                faceInvisible[newfaces] = false;
                f[newfaces].init(3, index, v);
                f[newfaces].setShadedColor(f[i].rgbLit);
                f[newfaces].setSurface(f[i].surface);
                newfaces++;
                for (j=1; j < num-2; ++j) {
                    // break into triangles
                    newindex = indexPool[pool++];
                    newindex[0] = index[0];
                    newindex[1] = index[j+1];
                    newindex[2] = index[j+2];
                    faceInvisible[newfaces] = false;
                    f[newfaces].init(3, newindex, v);
                    
                    // same characteristics as pre-clipped face
                    f[newfaces].setShadedColor(f[i].rgbLit);
                    f[newfaces].setSurface(f[i].surface);
                    
                    newfaces++;
                    newindex = null;
                }
                
            }
        }    
    }
    
    
    /**
     *  This clips a polygon against a single plane.
     */
    byte sutherlandHodgemanPlane(int index[], byte num, int newindex[], Vertex3D v[], byte plane) 
    {
        byte i,j,k;
        boolean changed = false;
        
        for (i=0,j=1,k=0; i < num; ++i, ++j) {
            if (j == num) j = 0;
            
            if ((outCodes[index[i]] & plane) == 0) {      
                if ((outCodes[index[j]] & plane) == 0) {  
                    // 1st inside, 2nd inside
                    newindex[k++] = index[j];
                } else {                    
                    // 1st inside, 2nd outside
                    intersectVertex(index[i], index[j], newvertices, plane);
                    newindex[k++] = newvertices++;
                    if (!changed) changed = true;
                }
            } else {                        
                if ((outCodes[index[j]] & plane) == 0) {  
                    // 1st outside, 2nd inside
                    intersectVertex(index[i], index[j], newvertices, plane);
                    newindex[k++] = newvertices++;
                    newindex[k++] = index[j];
                    if (!changed) changed = true;
                } else {                    
                    // 1st outside, 2nd outside
                    if (!changed) changed = true;
                }
            }
        }
        if (!changed) 
            return -1;
        else 
            return k;
    }


    Vertex3D p = new Vertex3D();
    Vertex3D q = new Vertex3D();
    Vector3D diffA = new Vector3D();
    Vector3D diffC = new Vector3D();
    Vector3D diffN = new Vector3D();
    Vector3D diffP = new Vector3D();

    /** 
     *  This will linearly interpolate characteristics between two vertices.
     */
    void intersectVertex(int i, int j, int k, byte plane) {
        float Hp, Hq, t;        
        p = v[i];
        q = v[j];
        
        Hp = planeEqs[plane].evaluate(p);
        Hq = planeEqs[plane].evaluate(q);
        t = Hp / (Hp - Hq);
        diffA.subtract(q, p);
        diffC.subtract(c[j].rgbLit, c[i].rgbLit);        
        diffN.subtract(q.n, p.n);
        diffP.subtract(q.p, p.p);
        v[k].addScaled(p, diffA, t);
        v[k].w = p.w + (q.w - p.w) * t;
        c[k].rgbLit.addScaled(c[i].rgbLit, diffC, t);
        v[k].n.addScaled(p.n, diffN, t);
        v[k].p.addScaled(p.p, diffP, t);
        v[k].s = p.s;
        v[k].u = p.u + (q.u - p.u) * t;
        v[k].v = p.v + (q.v - p.v) * t;
 
        computeOutcode(v, k);

        vertexVisible[k] = true;
    }
}