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

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

/*
class BodyNode {

    public Vector children;
    public pMatrix matrix;

    public BodyNode(){
        children = new Vector();
        matrix = new pMatrix();
    }
}
*/

public class PuppetApplet extends BufferedApplet {

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

    // points/colors that are rendered.
    Vector points = new Vector();
    Vector colors = new Vector();

    // for z sorting
    float[] avgz;
    int[] polyorder;

    // pre-computed points.	
    Vector cube = new Vector();

    // current rendering color
    Color currentColor = Color.red;

    // angle, mouse state
    private float 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;
    

    // screen rectangle
    int minx,maxx,miny,maxy;
   
    boolean[] keys;

    float[][][] globe;

    /**
     * make a globe sphere mesh
     *
     * @param m Horizontal splits.
     * @param m Vertical Splits.
     */
    public float[][][] globeMesh(int m,int n){
        float mesh[][][] = new float[m][n][3];
        for (int i = 0 ; i < m ; i++){
            for (int j = 0 ; j < n ; j++) {
                double u = i / (m - 1.0);
                double v = j / (n - 1.0);
                double theta = 2 * Math.PI * u;
                double phi = Math.PI * v - Math.PI/2;
                mesh[i][j][0] = (float)(Math.cos(theta) * Math.cos(phi));
                mesh[i][j][1] = (float)(Math.sin(theta) * Math.cos(phi));
                mesh[i][j][2] = (float)Math.sin(phi);
            }
        }
        return mesh;
    }

    /**
     * dumps phere to rendering pipeline
     */
    public void dumpGlobe(){
        int i,j;
        float[][][] mesh = globe;
        for(i=0;i<mesh.length-1;i++){
            for(j=0;j<mesh[i].length-1;j++){
            	addVertex(mesh[i][j][0],mesh[i][j][1],mesh[i][j][2]);
            	addVertex(mesh[i+1][j][0],mesh[i+1][j][1],mesh[i+1][j][2]);
            	addVertex(mesh[i+1][j+1][0],mesh[i+1][j+1][1],mesh[i+1][j+1][2]);
            	addVertex(mesh[i][j+1][0],mesh[i][j+1][1],mesh[i][j+1][2]);
            }
        }
    }

    /**
     * dumps phere to rendering pipeline
     */
    public void dumpCube(){
        int i,j;
        j=cube.size();
        for (i=0;i<j;i++) {
            float[] point = (float[])cube.elementAt(i);
            addVertex(point[0],point[1],point[2]);
        }
    }

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

        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;

        globe = globeMesh(8,8);

        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);

        // initialize cube
        Vector v_points = new Vector();
        Vector v_faces = new Vector();

        v_points.addElement(new float[]{1,-1,1,1});
        v_points.addElement(new float[]{1,1,1,1});
        v_points.addElement(new float[]{-1,1,1,1});
        v_points.addElement(new float[]{-1,-1,1,1});

        v_points.addElement(new float[]{1,-1,-1,1});
        v_points.addElement(new float[]{1,1,-1,1});
        v_points.addElement(new float[]{-1,1,-1,1});
        v_points.addElement(new float[]{-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});

        for (int i=0;i<v_faces.size();i++) {
            int[] face = (int[])v_faces.elementAt(i);
            for (int j=0;j<4;j++) {
                cube.addElement(v_points.elementAt(face[j]));
            }
        }
        v_points.removeAllElements();
        v_faces.removeAllElements();
    }

    /**
     * similar to glVertex
     */
    private void addVertex(float x,float y,float z){
        points.addElement(matrix.mult(new float[]{x,y,z,1}));
        colors.addElement(currentColor);
    }

    public void dumpModel(){
        float a,b,c;

        // dump something interesting...
        /*
        matrix.push();
        matrix.scale(16);
        currentColor = null;
        dumpCube();
        matrix.pop();
        */

        float s = 4;

        a = -s * 4;
        for(int i=0;i<9;i++){
            b = -s * 4;
            for(int j=0;j<9;j++){
                c = -s * 4;
                for(int k=0;k<9;k++){
                    if((i ^ j ^ k) % 2 == 0){
                        currentColor = new Color((int)(0xFF*i/9.0),(int)(0xFF*j/9.0),(int)(0xFF*k/9.0));
                        matrix.push();
                        matrix.translate(a,b,c);
                        dumpCube();
                        //dumpGlobe();
                        matrix.pop();
                    } 
                    c += s;
                }
                b += s;
            }
            a += s;
        }
    }

    /**
     * sort via average z 
     */
    public void sort(){
        int i,j;
        int e1;
        float e2;
        for (i=1;i<polyorder.length;i++) {
            e1 = polyorder[i];
            e2 = avgz[i];

            for (j=i-1;j>=0 && avgz[j] > e2;j--) {
                avgz[j+1] = avgz[j];
                polyorder[j+1] = polyorder[j];
            }
            polyorder[j+1] = e1;
            avgz[j+1] = e2;
        }
    }

    pMatrix camera = new pMatrix();

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

    public void handleMotion(){

        long currentframe = System.currentTimeMillis();
        frametime = (currentframe - lastframe) / (float)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((float)Math.PI/100);
            nm.mult(camera);
            camera = nm;            
            damage = true;
        }
        if(keys[1025] || keys['e']){            // ins key
            pMatrix nm = new pMatrix();
            nm.rotatez((float)-Math.PI/100);
            nm.mult(camera);
            camera = nm;
            damage = true;
        }
        
        if(keys[1006] || keys['a']){            // left key
            pMatrix nm = new pMatrix();
            nm.rotatey((float)-Math.PI/100);
            nm.mult(camera);
            camera = nm;
            damage = true;
        }

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

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

        if(keys[1005] || keys['s']){            // down key
            pMatrix nm = new pMatrix();
            nm.rotatex((float)-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 = (float)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);
        float 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();
            float[] 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 - 10;
        int H = r.height - 10;
        int lines[][] = {
            {10,10,10,H},
            {10,H,W,H},
            {W,H,W,10},
            {W,10,10,10}
        };
        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;
        }

    }

    /**
     * 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);

            matrix.scale(64);
            

            dumpModel();

            // calculate average z for all points.
            avgz = new float[points.size() / 4];
            polyorder = new int[points.size() / 4];


            int k,i=0,j=points.size();
            float[] plane = new float[4];

            for (i=0;i<j;i+=4) {
                float sum = 0;
                for (k=0;k<4;k++) {
                    float[] point = (float[])points.elementAt(i+k);
                    sum += point[2];
                }
                avgz[i/4] = sum / 4;
                polyorder[i/4] = i/4;
            }
            sort(); // sort polyorder by avgz

            j = polyorder.length;
            for (i=0;i<j;i++) {
                int poly = polyorder[i] * 4;

                float[] p0 = (float[])points.elementAt(poly+0);
                float[] p1 = (float[])points.elementAt(poly+1);
                float[] p2 = (float[])points.elementAt(poly+2);
                float[] p3 = (float[])points.elementAt(poly+3);

                Color c = (Color)colors.elementAt(poly);

                planeFromPoints(plane,p0,p1,p2,p3);
                float d = plane[3];
                boolean allnegative = true,allpositive = true,alloutofrange = true,allinrange = true;

                if (d > 0) {
                    int clipz,n = 4;
                    for (k=0; k < n; k++) {
                        float[] point = (float[])points.elementAt(poly+k);
                        //point = pmatrix.mult(point);
                        x[k] = (int)(point[0]); // / point[3]);
                        y[k] = (int)(point[1]); // / point[3]);
                        z[k] = clipz = (int)(point[2]); // / point[3]);

                        // clipping
                        // trivial cases, all points have positive or all negative z
                        if (clipz > 0){
                            allnegative = false;
                        }else{
                            allpositive = false;
                            if(clipz > -1000){
                                alloutofrange = false;
                            }else{
                                allinrange = false;
                            }
                        }
                    }
                    // trivial rejection
                    if (allpositive)
                        continue;
                    if (alloutofrange)
                        continue;
                    if (!allnegative){
                        int[] arr = {0,0,-1,0};
                        n = SutherlandHodgmanPolygonClip3D(x,y,z,n,cx,cy,cz,arr);                    
                        if(n == 0)
                            continue;
                        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,1000};
                        int m = SutherlandHodgmanPolygonClip3D(x,y,z,n,cx,cy,cz,arr);
                        if(m == 0)
                            continue;
                        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++){
                        float[] 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)
                        continue;
                    n = SutherlandHodgmanPolygonClip(cx,cy,n,x,y,screen_edges[1]);
                    if (n == 0)
                        continue;
                    n = SutherlandHodgmanPolygonClip(x,y,n,cx,cy,screen_edges[2]);
                    if (n == 0)
                        continue;
                    n = SutherlandHodgmanPolygonClip(cx,cy,n,x,y,screen_edges[3]);
                    if (n == 0)
                        continue;
                    
                    g.setColor(c);
                    g.fillPolygon(x,y,n);
                    g.setColor(Color.black);
                    g.drawPolygon(x,y,n);
                }
            }

            avgz = null;
            polyorder = null;
            matrix.pop();
            points.removeAllElements();
            colors.removeAllElements();
        }
    }

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

    /**
     * cross product of two vectors
     */
    void crossProduct(float[] v1, float[] v2, float[] 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
     */
    float vectorNormalize(float[] in, float[] out ) {
        float  length, ilength;
        length = (float)Math.sqrt(in[0]*in[0] + in[1]*in[1] + in[2]*in[2]);
        if (length == 0) {
            return 0;
        }
        ilength = (float)1.0/length;
        out[0] = in[0]*ilength;
        out[1] = in[1]*ilength;
        out[2] = in[2]*ilength;
        return length;
    }   

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

    /**
     * gets plane equation from three points on plane
     */
    boolean planeFromPoints(float[] plane, 
                            float[] a, float[] b,float[] c,float[] d ){

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

    /**
     * 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 += (float)0.015 * (float)(x - m_mousex);
        m_anglex += (float)0.015 * (float)(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;
    }

}