/**
 * @file            BSPNode.java
 * @author          Robert S Laramee
 * Start Date       Saturday, 07 November 1998
 * "Finish" Date    Friday,   13 November 1998
 * 
 * Description      This file contains methods for BSP nodes.  
 *                  Each BSPNode has essentially
 *                  1. an associated plane with it, the partition plane, 
 *                     defined by the equation: Ax + By + Cz + D = 0
 *                  2. a parent node
 *                  3. a front child node
 *                  4. a back child node
 */

import java.awt.*;   // for Graphics, Color class
import java.util.*;  // for Vector class
//import matrix.*;     // for Point4 class

public class BSPNode{

    /** 
     * let's give the node some sort of ID (for fun and debugging)
     * the partition plane, face, and normal vector
     */
    private String  id;
    private Plane3d partition   = null;
    private Face    face        = null;
    private double  darkenRatio;

    /**
     * the "parent" node (so it's like a doubly-linked list)
     * the "next" node pointing to the "front" child
     * the "next" node pointing to the "back" child
     */
    private BSPNode parent = null;
    private BSPNode front  = null;
    private BSPNode back   = null;

    /** 
     * Constructs a BSPNode object
     * For the cube, the faces (and hence nodes) are added in the following
     * order:
     * Front-Back ([0]-[1]),  Left-Right([2]-[3]),  Bottom-Top([4]-[5])
     * We'll have the BSPNode constructor set it up. i.e. compute the
     * associated plane and normal vector
     *
     * @param id   -a name for the node (of no use to the user, just bob)
     * @param face -the new face to make a node for
     */
    public BSPNode(String name, Face f){
              
	id          = name;
        face        = f;
	partition   = new Plane3d(f);       // call the plane constructor
	darkenRatio = 1.0;
    }

    /**
     * methods to get the front, back, and parent nodes and the partition
     * plane
     * @return the front, back, or parent node
     */
    public BSPNode getFront()      {  return front;      }
    public BSPNode getBack()       {  return back;       }
    public BSPNode getParent()     {  return parent;     }
    public Plane3d getPartition()  {  return partition;  }
    public Face    getFace()       {  return face;       }

    /**
     * methods to set the front and back child nodes to a new value
     * @param newNode -new node to set front or back child to 
     */
    public void setFront(BSPNode right)  {  front = right;  }
    public void setBack(BSPNode left)    {  back = left;    }
    public void setParent(BSPNode p)     {  parent = p;     }

    /**
     * The method will classify a polygon w.r.t. a partition plane
     * The polygon is either IN_FRONT, IN_BACK, SPANNING, or COINCIDENT
     * with the partition plane
     * The basic algorithm is:
     * FOR EACH vertex in the polygons face
     *    IF each vertex is on the plane               THEN  COINCIDENT
     *    IF each vertex is on the front side of plane THEN  IN_FRONT
     *    IF each vertex is on the back side of plane  THEN  IN_BACK
     *    ELSE vertices are on different sides of planes     SPANNING
     *
     * @return int -the polygon's classification
     */
    public int classifyPolygon(BSPNode newNode) {
	
	double[] points = new double[newNode.face._verts.length];
	double prevPoint = 0;
	double nextPoint = 0;

	for (int i = 0; i < newNode.face._verts.length; i++) {

	    points[i] = 
		this.partition.pointPlaneDistance(newNode.face._verts[i]);
	}
	for (int i = 0; i < points.length; i++) {

	    if (i == 0) {  prevPoint = points[0];  } 
	    else {

		nextPoint = points[i]; 
		
		if ( ((prevPoint >  Plane3d.EPSILON) &&     // check for a
		      (nextPoint < -Plane3d.EPSILON)) ||    // spanning
		     ((prevPoint < -Plane3d.EPSILON)  &&    // polygon
		      (nextPoint >  Plane3d.EPSILON))   ) {
		    
		    return Plane3d.SPANNING;
		}
		prevPoint = nextPoint;
	    }
	} // end for

	for (int i = 0; i < points.length; i++) {
	    if (points[i] > Plane3d.EPSILON)  {  return Plane3d.IN_FRONT; }
	}
	for (int i = 0; i < points.length; i++) {
	    if (points[i] < -Plane3d.EPSILON)   {  return Plane3d.IN_BACK; }
	}
	return Plane3d.COINCIDENT;
    }
    /**
     * This method splits a polygon into two parts.  The calling node has the
     * partition we are splitting across.  The newNode has the polygon that
     * is getting split.
     *
     * Unfortunately, the order in which the vertices are added to the new
     * faces matters.
     *
     * @param  tree    -a reference to the tree
     * @param  newNode -the new node whose face is being split (ouch)
     * @return int     -add 1 the number of split polygons
     */
    public int splitPoly(BSPTree tree, BSPNode newNode) {
	
	int      numVertices   = newNode.face._verts.length;
	double   prevDistance  = 0;
	double   nextDistance  = 0;
	double[] distances     = new double[numVertices];
	Point4   intersect;
        Vector   plusVertices  = new Vector();
        Vector   minusVertices = new Vector();

	prevDistance = distances[0] = 
	    this.partition.pointPlaneDistance(newNode.face._verts[0]);

	this.addToNewFace(newNode.face._verts[0], distances[0], 
			  plusVertices, minusVertices);

	for (int i = 1; i < numVertices; i++) {

	    nextDistance = distances[i] = 
		this.partition.pointPlaneDistance(newNode.face._verts[i]);

	    if ( ((prevDistance >  Plane3d.EPSILON) &&    // if points on
		  (nextDistance < -Plane3d.EPSILON)) ||   // opposite sides
	         ((prevDistance < -Plane3d.EPSILON) &&    // of partition
		  (nextDistance >  Plane3d.EPSILON))   ) { // plane
		    
		// compute intersection point
		intersect = 
		    this.partition.linePlaneIntersect(newNode.face._verts[i-1],
				                      newNode.face._verts[i]);

		this.addToNewFace(intersect, 0.0, plusVertices, minusVertices);
	    }
	    this.addToNewFace(newNode.face._verts[i], distances[i],
			      plusVertices, minusVertices);

	    prevDistance = nextDistance;
	} // end for

	/** check for intersection between first and last vertices */
	prevDistance =
	 this.partition.pointPlaneDistance(newNode.face._verts[numVertices-1]);
	nextDistance =
	  this.partition.pointPlaneDistance(newNode.face._verts[0]);

	if ( ((prevDistance >  Plane3d.EPSILON) &&     // if points on
	      (nextDistance < -Plane3d.EPSILON)) ||    // opposite sides
	     ((prevDistance < -Plane3d.EPSILON) &&     // of partition
	      (nextDistance >  Plane3d.EPSILON))   ) { // plane
		    
	    // compute intersection point
	    intersect = 
	  this.partition.linePlaneIntersect(newNode.face._verts[numVertices-1],
					    newNode.face._verts[0]);

	    this.addToNewFace(intersect, 0.0, plusVertices, minusVertices);
	}
		
	// we're done gathering points for 2 new polygons so add them to tree
	this.createPolygons(tree, plusVertices, minusVertices);
	return 1;
    }
    /**
     * This method will take a point and add it to the appropriate set
     * of points, either on the plus side or the minus side of the calling
     * polygon
     * @param point         -point being added
     * @param distance      -distance between the point and the calling
     *                       polygon's partition plane
     * @param plusVertices  -set of vertices for a new polygon on the plus 
     *                       side of the calling polygon's partition plane
     * @param minusVertices -set of vertices for a new polygon on the minus 
     *                       side of the calling polygon's partition plane
     */
    public void addToNewFace(Point4 point, double distance, 
			     Vector plusVertices, Vector minusVertices) {
	
	if (distance > Plane3d.EPSILON) {           // plus side
	    plusVertices.addElement(point);
	} else if (distance < -Plane3d.EPSILON) {   // minus side
	    minusVertices.addElement(point);
	} else {                                    // coincident so add the
	    plusVertices.addElement(point);         // point to both polygons
	    minusVertices.addElement(point);
	}
    }
    /**
     * This method takes two sets of vertices and creates 2 new nodes
     * (with 2 new Faces, and partition planes) out of them
     */
    public void createPolygons(BSPTree tree, Vector plusVertices, 
			                     Vector minusVertices) {

	Face    plusFace, minusFace;
	BSPNode plusNode, minusNode;
	Color   rgb = face.getColor();

	if (plusVertices.size() < 3) {
	   System.out.println("** Error: BSPNode::createPolygons(), " +
			      "less than 3 (plus) vertices.");
	   return;
	}
	plusFace = new Face(rgb, darkenRatio -= 0.1, plusVertices); 
	plusNode = new BSPNode(new String("plus_face"), plusFace);
	tree.addNode(plusNode);

	if (minusVertices.size() < 3) {
	   System.out.println("** Error: BSPNode::createPolygons(), " +
			      "less than 3 (minus) vertices.");
	   return;
	}
	minusFace = new Face(rgb, darkenRatio -= 0.1, minusVertices) ;
	minusNode = new BSPNode(new String("minus_face"), minusFace);
	tree.addNode(minusNode);
    }
    /**
     * This method adds the node passed to it to the IN_FRONT list of the 
     * calling node
     * @param newNode -the node to add to the IN_FRONT list
     * @return 1      -add 1 to the number of front nodes
     */
    public int addToFront(BSPNode newNode) {

	this.setFront(newNode);
	newNode.setParent(this);
	return 1;
    }
    /**
     * This method adds the node passed to it to the IN_BACK list of the 
     * calling node
     * @param newNode -the node to add to the IN_BACK list
     * @return 1      -add 1 to the number of front nodes
     */
    public int addToBack(BSPNode newNode) {

	this.setBack(newNode);
	newNode.setParent(this);
	return 1;
    }
    /**
     * A method to display a node
     * @param g   -the graphics object
     */
    public void displayNode(Graphics g) {

	this.face.draw(g, (new Matrix4()));
    } 
    /**
     * print info about a node like:
     * 1  "name"
     * 2  vertices of it's face
     * 3  normal
     * 4  partition plane equation
     */
    public void print() {

	System.out.println("\n Node: " + id);
	System.out.println(face.toString());      // vertices and normal
	System.out.println(partition.toString()); // plane equation
    }
}