/*
 * PuppetApplet.java
 *
 * (C) 2004-2005, Alex S.
 */

import java.awt.*;
import java.util.*;

/**
 * winding class, represents points on a face
 */
class pWinding {
    public int size = 0;
    public double[] x = new double[128];
    public double[] y = new double[128];
    public double[] z = new double[128];

    public void average(double[] p){
        if(size <= 0)
            return;
        double x,y,z;
        x = y = z = 0.0;
        for(int i=0;i<size;i++){
            x += this.x[i];
            y += this.y[i];
            z += this.z[i];
        }
        p[0] = x / size;
        p[1] = y / size;
        p[2] = z / size;
    }

}

/**
 * represents a plaine. 
 * Ax + By + Cz + D = 0
 */
class pPlane {

    public final static int FRONT = 1;
    public final static int BACK = -1;
    public final static int SPAN = 0;
    public final static int INCID = 2;

    // Ax + By + Cz + D = 0
    public double[] p = new double[4];

    public double eval(double x,double y,double z){
        return x * p[0] + y * p[1] + z * p[2] + p[3];
    }

    /**
     * given a winding, evaluate it.
     */
    public int eval(pWinding w){
        double max,min;
        max = min = eval(w.x[0],w.y[0],w.z[0]);
        for(int i=1;i<w.size;i++){
            double e = eval(w.x[i],w.y[i],w.z[i]);
            if(max < e)
                max = e;
            if(min > e)
                min = e;
        }
        if(max > 0 && min < 0){        
            if(max - min < 0.1)
                return INCID;
            return SPAN;
        }
        if(max > 0)
            return FRONT;
        return BACK;
    }

    /**
     * evaluate a face
     */
    public int eval(pFace f){
        return eval(f.winding);
    }

    /**
     * cut a face
     */
    public boolean cut(pFace in,pFace front,pFace back){
        cut(in.winding,front.winding,back.winding);
        front.parent = in.parent == null ? in:in.parent;
        back.parent = in.parent == null ? in:in.parent;
        front.color = front.parent.color;
        back.color = back.parent.color;
        front.plane = front.parent.plane;
        back.plane = back.parent.plane;
        return true;
    }

    /**
     * cut a winding
     */
    public boolean cut(pWinding in,pWinding front,pWinding back){

        double[] ix = in.x;
        double[] iy = in.y;
        double[] iz = in.z;
        
        double[] fx = front.x;
        double[] fy = front.y;
        double[] fz = front.z;
        
        double[] bx = back.x;
        double[] by = back.y;
        double[] bz = back.z;
        
        int n = in.size;
    
        int p,s,flen,blen;
        double k,l,d1,d2;
        double x,y,z;
        flen = blen = 0;
        s = n - 1;
        for(p=0;p<n;p++){
            if( (k = eval(ix[p],iy[p],iz[p])) >= 0 ){    // p is front
                if( (l = eval(ix[s],iy[s],iz[s])) >= 0 ){  // s in font
                    fx[flen] = ix[p];
                    fy[flen] = iy[p];
                    fz[flen] = iz[p];
                    flen++;
                }else{
                    // find intersection
                    d1 = -l;
                    d2 = (d1 + k);     
                    x = ix[s] + d1/d2 * ( ix[p] - ix[s] );
                    y = iy[s] + d1/d2 * ( iy[p] - iy[s] );
                    z = iz[s] + d1/d2 * ( iz[p] - iz[s] );
                                   
                    bx[blen] = x;
                    by[blen] = y;
                    bz[blen] = z;
                    blen++;
                    // cut
                    fx[flen] = x;
                    fy[flen] = y;
                    fz[flen] = z;
                    flen++;
                    fx[flen] = ix[p];
                    fy[flen] = iy[p];
                    fz[flen] = iz[p];
                    flen++;
                }
            }else{
                if( (l = eval(ix[s],iy[s],iz[s])) >= 0 ){  // s in front
                    d1 = -k;
                    d2 = (d1 + l);
                    x = ix[p] + d1/d2 * ( ix[s] - ix[p] );
                    y = iy[p] + d1/d2 * ( iy[s] - iy[p] );
                    z = iz[p] + d1/d2 * ( iz[s] - iz[p] );

                    fx[flen] = x;
                    fy[flen] = y;
                    fz[flen] = z;
                    flen++;
                    // cut
                    bx[blen] = x;
                    by[blen] = y;
                    bz[blen] = z;
                    blen++;
                    bx[blen] = ix[p];
                    by[blen] = iy[p];
                    bz[blen] = iz[p];
                    blen++;
                }else{
                    // just save p.
                    bx[blen] = ix[p];
                    by[blen] = iy[p];
                    bz[blen] = iz[p];
                    blen++;
                }
            }
            s = p;
        }
        front.size = flen;
        back.size = blen;
        return true;
    }
}

/**
 * face of an object (brush)
 * (has points, color, plane, etc.i
 *
 * TODO: add reference to parent object. (and remove ref to parent face)
 */
class pFace {
    public Color color = null;
    public pPlane plane = new pPlane();
    public pFace parent = null;
    public pWinding winding = new pWinding();

    public void average(double[] p){
        winding.average(p);
    }
}

/**
 * the `object'; has a bunch of faces.
 *
 * TODO: add collision detection with these things.
 */
class pBrush {
    public pBrush parent = null;
    public int numFaces = 0;
    public pFace[] faces = new pFace[128];
}

/**
 * the bsp tree node
 */
class pBSPNode {
    public pPlane plane = new pPlane();
    public pBSPNode front = null;
    public pBSPNode back = null;

    // faces that are on this node.
    public Vector faces = new Vector();
}

/**
 * general purpose map object (code to build bsp tree, and store map info)
 */
class pMap {
    public Vector brushes = new Vector();
    public pBSPNode bsp = null;

    /**
     * build bsp tree
     */
    public void buildBSP(){
        
        Vector faces = new Vector();
        // non-bsp renderer
        Enumeration enum = brushes.elements();
        while(enum.hasMoreElements()){
            pBrush brush = (pBrush)enum.nextElement();
            //System.out.println("\tbrush.numFaces: "+brush.numFaces);
            for(int f=0;f<brush.numFaces;f++){
                faces.addElement(brush.faces[f]);
            }
        }
        bsp = buildBSP(faces);
    }

    /**
     * use a more `intelligent' way to pick a face; (as opposed to just picking the first)
     */
    public static pFace pickFace(Vector faces){
        double[] avg = {0,0,0};
        double[] t = {0,0,0};
        pFace face;

        // find the average of the -whole- faces
        for(int i=0;i<faces.size();i++){
            face = (pFace)faces.elementAt(i);
            face.average(t);
            for(int j=0;j<3;j++){
                avg[j] += t[j];
            }
        }
        for(int j=0;j<3;j++){
            avg[j] /= faces.size();
        }

        // now that we have the average point, find the face whose average is closest to it.
        face = (pFace)faces.elementAt(0);
        face.average(t);
        int minindex = 0;
        double mindist = Math.sqrt(t[0]*t[0]+t[1]*t[1]+t[2]*t[2]);
        for(int i=1;i<faces.size();i++){
            face = (pFace)faces.elementAt(i);
            face.average(t);
            double d = Math.sqrt(t[0]*t[0]+t[1]*t[1]+t[2]*t[2]);
            if(mindist > d){
                mindist = d;
                minindex = i;
            }
        }
        face = (pFace)faces.elementAt(minindex);
        faces.removeElementAt(minindex);
        return face;
    }

    /**
     * build the bsp tree
     */
    public static pBSPNode buildBSP(Vector faces){
        if(faces.size() == 0)
            return null;

        pBSPNode node = new pBSPNode();
        Vector front = new Vector();
        Vector back = new Vector();

        // pick a plane
        pFace curr = pickFace(faces);
        pPlane plane = curr.plane;
        node.plane = plane;
        node.faces.addElement(curr);

        Enumeration enum = faces.elements();
        while(enum.hasMoreElements()){
            pFace face = (pFace)enum.nextElement();
            int e = plane.eval(face);
            if(e == plane.FRONT){
                front.addElement(face);
            }else if(e == plane.BACK){
                back.addElement(face);
            }else if(e == plane.INCID){
                node.faces.addElement(face); 
            }else{
                //cut
                pFace f = new pFace();
                pFace b = new pFace();
                if(plane.cut(face,f,b)){
                    front.addElement(f);
                    back.addElement(b);
                }
            }
        }
        node.front = buildBSP(front);
        node.back = buildBSP(back);
        return node;
    }

}

/**
 * random map generator
 */
class pMapGen {

    /**
     * given 2 points, find their difference
     */
    private static void vectorSubtract (double[] va, double[] vb, double[] out){
        out[0] = va[0]-vb[0];
        out[1] = va[1]-vb[1];
        out[2] = va[2]-vb[2];
    }

    /**
     * cross product of two vectors
     */
    private static void crossProduct(double[] v1, double[] v2, double[] cross ) {
        cross[0] = v1[1]*v2[2] - v1[2]*v2[1];
        cross[1] = v1[2]*v2[0] - v1[0]*v2[2];
        cross[2] = v1[0]*v2[1] - v1[1]*v2[0];
    }

    /**
     * normalize
     */
    private static double vectorNormalize(double[] in, double[] out ) {
        double  length, ilength;
        length = (double)Math.sqrt(in[0]*in[0] + in[1]*in[1] + in[2]*in[2]);
        if (length == 0) {
            return 0;
        }
        ilength = (double)1.0/length;
        out[0] = in[0]*ilength;
        out[1] = in[1]*ilength;
        out[2] = in[2]*ilength;
        return length;
    }   

    /**
     * dot product
     */
    private static double dotProduct (double[] v1, double[] v2){
        return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2];
    }

    /**
     * gets plane equation from three points on plane
     * 
     * Plane is: Ax + By + Cx + D = 0
     */
    private static boolean planeFromPoints(double[] plane, 
                            double[] a, double[] b,double[] c,double[] d ){

        double[] d1 = new double[4];
        double[] d2 = new double[4];
        
        vectorSubtract( b, a, d1 );
        if (dotProduct(d1,d1) < (double)0.02) {
            vectorSubtract( c, a, d1 );
            vectorSubtract( d, a, d2 );
        } else {
            vectorSubtract( c, a, d2 );
            if (dotProduct(d2,d2) < (double)0.02) {
                vectorSubtract( d, a, d2 );
            }
        }
        crossProduct( d1, d2, plane );
        if ( vectorNormalize( plane, plane ) == 0 ) {
            return false;
        }
        plane[3] = -dotProduct( a, plane );

        return true;
    }

    /**
     * generates a random cube based `map'
     */
    public static pMap generateCubes(int n){

        Vector cube = new Vector();

        // initialize cube
        Vector v_points = new Vector();
        Vector v_faces = new Vector();
        v_points.addElement(new double[]{1,-1,1,1});
        v_points.addElement(new double[]{1,1,1,1});
        v_points.addElement(new double[]{-1,1,1,1});
        v_points.addElement(new double[]{-1,-1,1,1});
        v_points.addElement(new double[]{1,-1,-1,1});
        v_points.addElement(new double[]{1,1,-1,1});
        v_points.addElement(new double[]{-1,1,-1,1});
        v_points.addElement(new double[]{-1,-1,-1,1});
        v_faces.addElement(new int[]{0,1,2,3});
        v_faces.addElement(new int[]{4,7,6,5});
        v_faces.addElement(new int[]{0,4,5,1});
        v_faces.addElement(new int[]{7,3,2,6});
        v_faces.addElement(new int[]{1,5,6,2});
        v_faces.addElement(new int[]{0,3,7,4});

        pMap map = new pMap();

        pMatrix matrix = new pMatrix();
        double a,b,c;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<n;k++){
                    if((i ^ j ^ k) % 2 == 0){

                        //System.out.println("i:"+i+"; j:"+j+"; k:"+k);

                        matrix.push();
                        matrix.translate((i-n/2)*256,(j-n/2)*256,(k-n/2)*256);
                        matrix.scale(64);

                        matrix.rotatex(Math.random()*Math.PI*2);
                        matrix.rotatey(Math.random()*Math.PI*2);
                        matrix.rotatez(Math.random()*Math.PI*2);
                        

                        pBrush brush = new pBrush();

                        for (int f=0;f<v_faces.size();f++) {
                            int[] arr = (int[])v_faces.elementAt(f);
                            pFace face = new pFace();

                            pWinding winding = face.winding;
                            for (int p=0;p<4;p++) {
                                double[] point_ = (double[])v_points.elementAt(arr[p]);
                                double[] point = new double[point_.length];
                                System.arraycopy(point_,0,point,0,point_.length);
                                //System.out.print("\t\t\t("+point[0]+","+point[1]+","+point[2]+") => ");
                                point = matrix.mult(point);
                                //System.out.print("("+point[0]+","+point[1]+","+point[2]+") => ");
                                winding.x[p] = point[0];
                                winding.y[p] = point[1];
                                winding.z[p] = point[2];
                                //System.out.println("("+winding.x[p]+","+winding.y[p]+","+winding.z[p]+")");
                            
                            }
                            winding.size = 4;
                            double[] p0 = {winding.x[0],winding.y[0],winding.z[0],1};
                            double[] p1 = {winding.x[1],winding.y[1],winding.z[1],1};
                            double[] p2 = {winding.x[2],winding.y[2],winding.z[2],1};
                            double[] p3 = {winding.x[3],winding.y[3],winding.z[3],1};                            
                            planeFromPoints(face.plane.p,p0,p1,p2,p3);
                            face.color = new Color(
                                (int)(0xFF*i/(double)n),
                                (int)(0xFF*j/(double)n),
                                (int)(0xFF*k/(double)n)
                            );
                            brush.faces[brush.numFaces] = face;
                            brush.numFaces++;
                        }
                        matrix.pop();
                        map.brushes.addElement(brush);
                    }
                }
            }
        }
        return map;
    }
}

/**
 * main class of the whole thing
 */
public class PuppetApplet extends BufferedApplet {

    pMatrix matrix = new pMatrix();
    pMatrix pmatrix = new pMatrix();

    pMap map; 

    // angle, mouse state
    private double m_anglex,m_angley;
    private int m_mousex,m_mousey;

    // used for java's fillpoly thingie... (and some quick & dirty clipping)
    private int[] x;
    private int[] y;
    private int[] z;

    // clippping ...
    private int[] cx;
    private int[] cy;
    private int[] cz;

    private int[][] screen_edges;
   
    boolean[] keys;


    /**
     * initialize things
     */
    public void init(){
        super.init();

        map = pMapGen.generateCubes(5);
        map.buildBSP();

        keys = new boolean[0x1000];
        for(int i=0;i<keys.length;i++)
            keys[i] = false;

        m_mousex = m_mousey = 0;
        m_anglex = m_angley = 0;

        x = new int[128];
        y = new int[128];
        z = new int[128];
        cx = new int[128];
        cy = new int[128];
        cz = new int[128];
        
        pmatrix.translate(bounds().width/2,bounds().height/2,0);
        pmatrix.perspective(bounds().width/2,1);

    }

    pMatrix camera = new pMatrix();

    double acceleration = 0;
    double friction = 0;
    double force = 0;
    double speed = 0;
    double frametime = 0;
    long lastframe = System.currentTimeMillis();

    /**
     * crude motion handling
     */
    public void handleMotion(){

        long currentframe = System.currentTimeMillis();
        frametime = (currentframe - lastframe) / (double)1000.0;
        lastframe = currentframe;


        if(m_anglex != 0 || m_angley != 0){
            pMatrix nm = new pMatrix();
            nm.rotatex(m_anglex);
            nm.rotatey(m_angley);
            nm.mult(camera);
            camera = nm;
            m_anglex = m_angley = 0;
            damage = true;
        }
       
        if(keys[127] || keys['q']){            // del key
            pMatrix nm = new pMatrix();
            nm.rotatez((double)Math.PI/100);
            nm.mult(camera);
            camera = nm;            
            damage = true;
        }
        if(keys[1025] || keys['e']){            // ins key
            pMatrix nm = new pMatrix();
            nm.rotatez((double)-Math.PI/100);
            nm.mult(camera);
            camera = nm;
            damage = true;
        }
        
        if(keys[1006] || keys['a']){            // left key
            pMatrix nm = new pMatrix();
            nm.rotatey((double)-Math.PI/100);
            nm.mult(camera);
            camera = nm;
            damage = true;
        }

        if(keys[1007] || keys['d']){            // right key
            pMatrix nm = new pMatrix();
            nm.rotatey((double)Math.PI/100);
            nm.mult(camera);
            camera = nm;
            damage = true;
        }

        if(keys[1004] || keys['w']){            // up key
            pMatrix nm = new pMatrix();
            nm.rotatex((double)Math.PI/100);
            nm.mult(camera);
            camera = nm;
            damage = true;
        }

        if(keys[1005] || keys['s']){            // down key
            pMatrix nm = new pMatrix();
            nm.rotatex((double)-Math.PI/100);
            nm.mult(camera);
            camera = nm;
            damage = true;
        }

        if(keys['<'] || keys[','] || keys['z']){
            //System.out.println("< is pressed");
            force = 100;
        }else if(keys['>'] || keys['.'] || keys['x']){
            force = -70;
        }else{
            force = 0;
        }
            
        friction = (double)0.1;
        acceleration = acceleration + friction * (0 - acceleration);
        acceleration = Math.min(1000,acceleration + force); // should be force * direction vector
        speed = speed + friction * (0 - speed);
        speed = Math.min(200,speed + acceleration * frametime);
        speed = Math.max(speed,-100);
        double distance = Math.round(speed * frametime);
        
        if(distance != 0){
            pMatrix nm = new pMatrix();
            nm.translate(0,0,distance);
            nm.mult(camera);

            /* // todo: collision detection
            pMatrix inverse = camera.inverse();
            double[] vec = {0,0,0,1};
            vec = inverse.mult(vec);
            */

            camera = nm;
            damage = true;
        }

    }

    /**
     * recompute various things when screen size changes
     */
    public void recompute(Rectangle r){
        screen_edges = new int[4][3];
        int W = r.width-1;
        int H = r.height-1;
        int lines[][] = {
            {0,0,0,H},
            {0,H,W,H},
            {W,H,W,0},
            {W,0,0,0}
        };
        int x1 = 0;
        int y1 = 1;
        int x2 = 2;
        int y2 = 3;
        for(int i=0;i<screen_edges.length;i++){
            int dx = lines[i][x2] - lines[i][x1];
            int dy = lines[i][y2] - lines[i][y1];
            int A = dy;
            int B = -dx;
            int D = -(A * lines[i][x1] + B * lines[i][y1]);
            screen_edges[i][0] = A;
            screen_edges[i][1] = B;
            screen_edges[i][2] = D;
        }

    }

    /**
     * given a face, transform, clip and render
     */
    public void pRenderFace(pFace face,Graphics g){
        pWinding w = face.winding;

        //System.out.println("render face: "+w.size);

        boolean allnegative = true,allpositive = true,alloutofrange = true,allinrange = true;
        int clipz;
        int n = w.size;
        int k;

        //System.out.print("Points: ");

        for (int i=0;i<n; i++) { 
            
            double[] point = {w.x[i],w.y[i],w.z[i],1};
            point = matrix.mult(point);

            x[i] = (int)point[0];
            y[i] = (int)point[1];
            z[i] = clipz = (int)point[2];

            //System.out.print("("+x[i]+","+y[i]+","+z[i]+") ");

            // clipping
            // trivial cases, all points have positive or all negative z
            if (clipz > 0){
                allnegative = false;
            }else{
                allpositive = false;
                if(clipz > -10000){
                    alloutofrange = false;
                }else{
                    allinrange = false;
                }
            }
        }
        //System.out.println("");

        // trivial rejection
        if (allpositive){
            //System.out.println("\tall positive");
            return;            
        }
        if (alloutofrange){
            //System.out.println("\tall out of range.");
            return;
        }
        if (!allnegative){
            int[] arr = {0,0,-1,0};
            n = SutherlandHodgmanPolygonClip3D(x,y,z,n,cx,cy,cz,arr);                    
            if(n == 0){
                //System.out.println("all z clipped");
                return;
            }
            for(k=0;k<n;k++){
                x[k] = cx[k]; y[k] = cy[k]; z[k] = cz[k];
            }
        }
        if(!allinrange){
            int[] arr = {0,0,1,10000};
            int m = SutherlandHodgmanPolygonClip3D(x,y,z,n,cx,cy,cz,arr);
            if(m == 0){
                //System.out.println("all far clipped");
                return;
            }
            if(n != m){
                n = m;
                for(k=0;k<n;k++){
                    x[k] = cx[k]; y[k] = cy[k]; z[k] = cz[k];
                }
            }
        }

        // project face coordinates
        for(k=0;k<n;k++){
            double[] point = {x[k],y[k],z[k],1}; 
            point = pmatrix.mult(point);
            x[k] = (int)(point[0] / point[3]);
            y[k] = (int)(point[1] / point[3]);
        } 
        n = SutherlandHodgmanPolygonClip(x,y,n,cx,cy,screen_edges[0]);
        if (n == 0){
            //System.out.println("all screen clipped");
            return;
        }
        n = SutherlandHodgmanPolygonClip(cx,cy,n,x,y,screen_edges[1]);
        if (n == 0){
            //System.out.println("all screen clipped");
            return;
        }
        n = SutherlandHodgmanPolygonClip(x,y,n,cx,cy,screen_edges[2]);
        if (n == 0){
            //System.out.println("all screen clipped");
            return;
        }
        n = SutherlandHodgmanPolygonClip(cx,cy,n,x,y,screen_edges[3]);
        if (n == 0){
            //System.out.println("all screen clipped");
            return;
        } 
        g.setColor(face.color);
        g.fillPolygon(x,y,n);
        g.setColor(Color.black);
        g.drawPolygon(x,y,n);
    }

    /**
     * given a list of faces, loop, do back-face-culling, and call rendering func
     */
    public void pRenderFaces(double[] eye,Vector faces,Graphics g){
        Enumeration enum = faces.elements();
        while(enum.hasMoreElements()){
            pFace face = (pFace)enum.nextElement();
            if(face.plane.eval(eye[0],eye[1],eye[2]) > 0)
                pRenderFace(face,g);
        }
    }
    
    /**
     * render everything in a bsp tree using painter's algorithm (back to front)
     */
    public void pTreeRender(double[] eye,pBSPNode node,Graphics g){
        if(node == null)
            return;

        // just render everything here.

        if(node.plane.eval(eye[0],eye[1],eye[2]) >= 0){
            pTreeRender(eye,node.back,g);
            pRenderFaces(eye,node.faces,g);
            pTreeRender(eye,node.front,g);
        }else{
            pTreeRender(eye,node.front,g);
            pRenderFaces(eye,node.faces,g);
            pTreeRender(eye,node.back,g);
        }
    }

    /**
     * function that gets called whenever something needs to be
     * rendered.
     */
    public void render(Graphics g) {

        handleMotion();

        if (damage) {
            g.setColor(Color.lightGray);
            g.fillRect(0, 0, bounds().width, bounds().height);

            matrix.push();

            matrix.mult(camera);

            pMatrix inverse = camera.inverse();
            double[] eye = {0,0,0,1};
            eye = inverse.mult(eye);

            pTreeRender(eye,map.bsp,g);

            matrix.pop();

            //g.drawString("("+eye[0]+","+eye[1]+","+eye[2]+")",10,10);            
        }
    }

    /**
     * mouse event handler: let the user move things
     */
    public boolean mouseDown(Event evt, int x, int y){
        m_mousex = x;
        m_mousey = y;
        return true;
    }
    public boolean mouseUp(Event evt, int x, int y){
        return true;
    }

    /**
     * mouse event handler: let the user move things
     */
    public boolean mouseDrag(Event evt, int x, int y){
        m_angley += (double)0.015 * (double)(x - m_mousex);
        m_anglex += (double)0.015 * (double)(y - m_mousey);
        m_mousex = x;
        m_mousey = y;
        return true;
    }

    public boolean keyDown(Event evt,int key){
        //System.out.println("keyDown: "+key);
        if(key < 0x1000)
            keys[key] = true;
        return true;
    }

    public boolean keyUp(Event evt,int key){
        //System.out.println("keyUp: "+key);
        if(key < 0x1000)
            keys[key] = false;
        return true;
    }

    /**
     * edge is in Ax + By + D = 0 format.
     *
     * dx = x2 - x1;
     * dy = y2 - y1;
     * A = dy
     * B = -dx
     * D = -(A * x1 + B * y1)
     */
    private int SutherlandHodgmanPolygonClip(int[] ix,int[] iy,int n,int[] ox,int[] oy,int[] edge){
        int A,B,D,p,s,k,l,olen,x,y;
        long d1,d2; // these -need- to be long (some of these values get -very- large.
        A = edge[0];
        B = edge[1];
        D = edge[2];
        olen = 0;
        s = n - 1;
        for(p=0;p<n;p++){
            if( (k = ix[p] * A + iy[p] * B + D) >= 0 ){    // p is inside
                if( (l = ix[s] * A + iy[s] * B + D) >= 0 ){  // s in inside
                    ox[olen] = ix[p];
                    oy[olen] = iy[p];
                    olen++;
                }else{
                    // find intersection
                    d1 = -l;
                    d2 = (d1 + k);
                    ox[olen] = (int)(ix[s] + ( d1 * ( ix[p] - ix[s] ) ) / d2);
                    oy[olen] = (int)(iy[s] + ( d1 * ( iy[p] - iy[s] ) ) / d2);
                    olen++;
                    ox[olen] = ix[p];
                    oy[olen] = iy[p];
                    olen++;
                }
            }else{
                if( (l = ix[s] * A + iy[s] * B + D) >= 0 ){  // s in inside
                    d1 = -k;
                    d2 = (d1 + l);
                    ox[olen] = (int)(ix[p] + ( d1 * ( ix[s] - ix[p] ) ) / d2);
                    oy[olen] = (int)(iy[p] + ( d1 * ( iy[s] - iy[p] ) ) / d2);
                    olen++;
                }
            }
            s = p;
        }
        return olen;
    }

    /**
     * edge is Ax + By + Cz + D = 0
     */
    private int SutherlandHodgmanPolygonClip3D(int[] ix,int[] iy,int[] iz,int n,int[] ox,int[] oy,int[] oz,int[] edge){
        int A,B,C,D,p,s,k,l,olen,x,y;
        long d1,d2; // these -need- to be long (some of these values get -very- large.
        A = edge[0];
        B = edge[1];
        C = edge[2];
        D = edge[3];
        olen = 0;
        s = n - 1;
        for(p=0;p<n;p++){
            if( (k = ix[p] * A + iy[p] * B + iz[p] * C + D) >= 0 ){    // p is inside
                if( (l = ix[s] * A + iy[s] * B + iz[s] * C + D) >= 0 ){  // s in inside
                    ox[olen] = ix[p];
                    oy[olen] = iy[p];
                    oz[olen] = iz[p];
                    olen++;
                }else{
                    // find intersection
                    d1 = -l;
                    d2 = (d1 + k);
                    ox[olen] = (int)(ix[s] + ( d1 * ( ix[p] - ix[s] ) ) / d2);
                    oy[olen] = (int)(iy[s] + ( d1 * ( iy[p] - iy[s] ) ) / d2);
                    oz[olen] = (int)(iz[s] + ( d1 * ( iz[p] - iz[s] ) ) / d2);
                    olen++;
                    ox[olen] = ix[p];
                    oy[olen] = iy[p];
                    oz[olen] = iz[p];
                    olen++;
                }
            }else{
                if( (l = ix[s] * A + iy[s] * B + iz[s] * C + D) >= 0 ){  // s in inside
                    d1 = -k;
                    d2 = (d1 + l);
                    ox[olen] = (int)(ix[p] + ( d1 * ( ix[s] - ix[p] ) ) / d2);
                    oy[olen] = (int)(iy[p] + ( d1 * ( iy[s] - iy[p] ) ) / d2);
                    oz[olen] = (int)(iz[p] + ( d1 * ( iz[s] - iz[p] ) ) / d2);
                    olen++;
                }
            }
            s = p;
        }
        return olen;
    }
}