/*
 * pMap.java
 *
 * (C) 2005, Alex S.
 */
 
import java.util.*;

/**
 * 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();
            for (int f=0;f<brush.numFaces;f++) {
                faces.addElement(brush.faces[f]);
            }
        }
        bsp = buildBSP(faces);


        enum = brushes.elements();
        while (enum.hasMoreElements()) {
            pBrush brush = (pBrush)enum.nextElement();    
            addBrushToTree(bsp,brush); 
        }
    }

    /**
     * add brush to BSP tree
     */
    public static void addBrushToTree(pBSPNode bsp,pBrush b){
        if (bsp.type == pBSPNode.LEAFNODE) {
            bsp.brushes.addElement(b);
        } else {
            int e = bsp.plane.eval(b);
            if (e == pPlane.FRONT) {
                addBrushToTree(bsp.front,b);
            } else if (e == pPlane.BACK) {
                addBrushToTree(bsp.back,b);
            } else if (e == pPlane.SPAN) {
                addBrushToTree(bsp.front,b);
                addBrushToTree(bsp.back,b);
            }
        }
    }

    /**
     * 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 new pBSPNode(pBSPNode.LEAFNODE);

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


    /*
     * the below collision stuff is mostly lifted from 
     * Nathan Ostgard's (nostgard@lvcm.com) wonderful
     * tutorial ``Quake 3 BSP Collision Detection''
     * http://www.devmaster.net/articles/quake3collision/
     */

    public static final double EPSILON = 1.0 / 32.0;

    public double outputFraction = 0;
    public double[] outputEnd = {0,0,0,1};
    public boolean outputStartsOut = false;
    public boolean outputAllSolid = false;
    public pPlane outputPlane = new pPlane();

    public int traceType = 0;
    public static final int TT_RAY = 0;
    public static final int TT_SPHERE = 1;
    public static final int TT_BOX = 2;

    // params for trace types
    double traceRadius = 0;
    double[] traceMins = {0,0,0,1};
    double[] traceMaxs = {0,0,0,1};
    double[] traceExtents = {0,0,0,1};

    public void traceRay(double[] inputStart, double[] inputEnd){
        traceType = TT_RAY;
        trace( inputStart, inputEnd );
    }

    public void traceSphere(double[] inputStart,double[] inputEnd,double inputRadius){
        traceType = TT_SPHERE;
        traceRadius = inputRadius;
        trace( inputStart, inputEnd );
    }

    public void TraceBox(double[] inputStart,double[] inputEnd,double[] inputMins,double[] inputMaxs){
        if (inputMins[0] == 0 && inputMins[1] == 0 && inputMins[2] == 0 &&
            inputMaxs[0] == 0 && inputMaxs[1] == 0 && inputMaxs[2] == 0){       
            // the user traceBox, but this is actually a ray
            traceRay( inputStart, inputEnd );
        } else {        // setup for a box
            traceType = TT_BOX;
            traceMins = inputMins;
            traceMaxs = inputMaxs;
            traceExtents[0] = -traceMins[0] > traceMaxs[0] ? -traceMins[0] : traceMaxs[0];
            traceExtents[1] = -traceMins[1] > traceMaxs[1] ? -traceMins[1] : traceMaxs[1];
            traceExtents[2] = -traceMins[2] > traceMaxs[2] ? -traceMins[2] : traceMaxs[2];
            trace( inputStart, inputEnd );
        }
    }

    /**
     * traces a thing
     */
    public void trace(double[] inputStart, double[] inputEnd ) {
        outputStartsOut = true;
        outputAllSolid = false;
        outputFraction = 1.0f;

        // walk through the BSP tree
        checkNode( bsp, 0.0f, 1.0f, inputStart, inputEnd );

        if (outputFraction == 1.0f){       
            // nothing blocked the trace
            outputEnd = inputEnd;
        } else {       
            // collided with something 
            for (int i = 0; i < 3; i++) {
                outputEnd[i] = inputStart[i] + outputFraction * (inputEnd[i] - inputStart[i]);
            }
        }
    }

    /**
     * checks a node 
     */
    public void checkNode(pBSPNode node, double startFraction, double endFraction,double[] start,double[] end ){
        if (node.type == pBSPNode.LEAFNODE){       // this is a leaf
            for (int i = 0; i < node.brushes.size(); i++){
                pBrush brush = (pBrush)node.brushes.elementAt(i);
                if (brush.type == pBrush.SOLID){
                    checkBrush( brush, start, end );
                }
            }
            // don't have to do anything else for leaves
            return;
        }

        // this is a node

        pPlane plane = node.plane;
              
        double startDistance = 0, endDistance = 0, offset = 0;
        
        //startDistance = DotProduct( start, plane->normal ) - plane->distance;
        //endDistance = DotProduct( end, plane->normal ) - plane->distance;

        startDistance = plane.eval( start );
        endDistance = plane.eval( end );


        if (traceType == TT_RAY) {
            offset = 0;
        } else if (traceType == TT_SPHERE) {
            offset = traceRadius;
        } else if (traceType == TT_BOX) {
            // this is just a dot product, but we want the absolute values
            offset = (double)(Math.abs( traceExtents[0] * plane.p[0] ) +
                Math.abs( traceExtents[1] * plane.p[1] ) +
                Math.abs( traceExtents[2] * plane.p[2] ) );
        }

        if (startDistance >= offset && endDistance >= offset){
            // both points are in front of the plane
            // so check the front child
            checkNode( node.front, startFraction, endFraction, start, end );
        } else if (startDistance < -offset && endDistance < -offset) {
            // both points are behind the plane
            // so check the back child
            checkNode( node.back, startFraction, endFraction, start, end );
        } else {       
            // the line spans the splitting plane
            int side;
            double fraction1, fraction2, middleFraction;
            double[] middle = {0,0,0,1};

            // split the segment into two
            if (startDistance < endDistance) {
                side = 1; // back
                double inverseDistance = 1.0f / (startDistance - endDistance);
                fraction1 = (startDistance - offset + EPSILON) * inverseDistance;
                fraction2 = (startDistance + offset + EPSILON) * inverseDistance;
            } else if (endDistance < startDistance) {
                side = 0; // front
                double inverseDistance = 1.0f / (startDistance - endDistance);
                fraction1 = (startDistance + offset + EPSILON) * inverseDistance;
                fraction2 = (startDistance - offset - EPSILON) * inverseDistance;
            } else {
                side = 0; // front
                fraction1 = 1.0f;
                fraction2 = 0.0f;
            }

            // make sure the numbers are valid
            if (fraction1 < 0.0f) fraction1 = 0.0f;
            else if (fraction1 > 1.0f) fraction1 = 1.0f;
            if (fraction2 < 0.0f) fraction2 = 0.0f;
            else if (fraction2 > 1.0f) fraction2 = 1.0f;

            // calculate the middle point for the first side
            middleFraction = startFraction + (endFraction - startFraction) * fraction1;
            for (int i = 0; i < 3; i++)
                middle[i] = start[i] + fraction1 * (end[i] - start[i]);

            // check the first side
            if(side == 1){
                checkNode( node.back, startFraction, middleFraction, start, middle );
            }else if(side == 0){
                checkNode( node.front, startFraction, middleFraction, start, middle );
            }

            // calculate the middle point for the second side
            middleFraction = startFraction + (endFraction - startFraction) * fraction2;
            for (int i = 0; i < 3; i++)
                middle[i] = start[i] + fraction2 * (end[i] - start[i]);

            // check the second side
            if(side == 1){
                checkNode( node.front, middleFraction, endFraction, middle, end );
            }else if(side == 0){
                checkNode( node.back, middleFraction, endFraction, middle, end );
            }
        }
    }

    /**
     * checks brush
     */
    public void checkBrush(pBrush brush, double[] inputStart, double[] inputEnd ) {
        double startFraction = -1.0f;
        double endFraction = 1.0f;
        boolean startsOut = false;
        boolean endsOut = false;
        pPlane hitPlane = outputPlane;

        for (int i = 0; i < brush.numFaces; i++) {
            pFace brushside = brush.faces[i];
            pPlane plane = brushside.plane;

            double startDistance = 0, endDistance = 0;
            
            if (traceType == TT_RAY) {
                startDistance = plane.eval(inputStart);
                endDistance = plane.eval(inputEnd);
            } else if (traceType == TT_SPHERE) {
                startDistance = plane.eval( inputStart) - traceRadius;
                endDistance = plane.eval( inputEnd ) - traceRadius;
            } else if (traceType == TT_BOX) {
                double[] offset = {0,0,0,1};
                for (int j = 0; j < 3; j++){
                    if (plane.p[j] < 0)
                        offset[j] = traceMaxs[j];
                    else
                        offset[j] = traceMins[j];
                }

                startDistance = (inputStart[0] + offset[0]) * plane.p[0] +
                    (inputStart[1] + offset[1]) * plane.p[1] +
                    (inputStart[2] + offset[2]) * plane.p[2] + plane.p[3];
                endDistance = (inputEnd[0] + offset[0]) * plane.p[0] +
                    (inputEnd[1] + offset[1]) * plane.p[1] +
                    (inputEnd[2] + offset[2]) * plane.p[2] + plane.p[3];
            }

            if (startDistance > 0)
                startsOut = true;
            if (endDistance > 0)
                endsOut = true;

            // make sure the trace isn't completely on one side of the brush
            if (startDistance > 0 && endDistance > 0){   
                // both are in front of the plane, its outside of this brush
                return;
            }
            if (startDistance <= 0 && endDistance <= 0){   
                // both are behind this plane, it will get clipped by another one
                continue;
            }
            if (startDistance > endDistance){   
                // line is entering into the brush
                double fraction = (startDistance - EPSILON) / (startDistance - endDistance);
                if (fraction > startFraction){
                    startFraction = fraction;
                    hitPlane = plane;
                }
            } else {   
                // line is leaving the brush
                double fraction = (startDistance + EPSILON) / (startDistance - endDistance);
                if (fraction < endFraction){
                    endFraction = fraction;
                }
            }
        }

        if (startsOut == false){
            outputStartsOut = false;
            if (endsOut == false)
                outputAllSolid = true;
            return;
        }

        // was there some collision?
        if (startFraction < endFraction){
            if (startFraction > -1 && startFraction < outputFraction){
                if (startFraction < 0)
                    startFraction = 0;
                outputFraction = startFraction;
                outputPlane = hitPlane;
            }
        }
    }
}