/** * @file BSPTree.java * @author Robert S Laramee * Start Date Saturday, 07 November 1998 * "Finish" Date Friday, 13 November 1998 * * Description This file contains methods for maintaining a BSP. * "If you maintain a BSP tree of all objects currently in * the scene, the addition of a new object does not requie the complete * rebuild of the scene. Instead, you only need to take the new faces and add * them to the existing tree, by filtering them down through the tree * (splitting as needed) until their various parts reach a leaf position... * One polygon at a time is split and passed down through the entire tree." * * A BSPTree class is a Binary Space Partition Tree. */ import java.awt.*; // for Graphics class //import matrix.*; // for Point4 class public class BSPTree{ /** * 1 The root of the TREE (initialized to null) * 2 Let's give the tree a name (just for fun) * 3 The current number of nodes in the tree (maybe for debugging) * 4 The current number of front nodes in the tree (maybe for debugging) * 5 The current number of back nodes in the tree (maybe for debugging) * 6 The current number of back nodes in the tree (maybe for debugging) */ private BSPNode root; private String treeName; private int numNodes; private int numFrontNodes; private int numBackNodes; private int numSplitNodes; private int numCoinNodes; /** * constructor * @param newName -name of tree */ public BSPTree(String newName) { root = null; treeName = newName; numFrontNodes = 0; numBackNodes = 0; numSplitNodes = 0; numCoinNodes = 0; } /** * A method to get a hold of the root node * @return root */ public BSPNode getRoot() { return root; } /** * A method to get a hold of the tree * @return root */ public BSPTree getTree() { return this; } /** * a function to add face to a BSP Tree. * FOR the cube, the faces are added in the following order: * Front-Back ([0]-[1]), Left-Right ([2]-[3]), Bottom-Top([4]-[5]) * FOR the tetrahedron, the faces are added in the following order: * Front ([0]), Left-Right([1]-[2]) , Bottom ([3]) * @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 void addFace(String id, Face face) { BSPNode newNode = new BSPNode(id, face); int placement; if (root == null) { root = newNode; // System.out.print("Root: "); newNode.print(); return; } BSPNode currentNode = root; while (currentNode != null) { placement = currentNode.classifyPolygon(newNode); if (placement == Plane3d.IN_FRONT) { if (currentNode.getFront() == null) { // reached a leaf node numFrontNodes += currentNode.addToFront(newNode); break; } else { currentNode = currentNode.getFront(); } } else if (placement == Plane3d.IN_BACK) { if (currentNode.getBack() == null) { // reached a leaf node numBackNodes += currentNode.addToBack(newNode); break; } else { currentNode = currentNode.getBack(); } } else if (placement == Plane3d.SPANNING) { numSplitNodes += currentNode.splitPoly(getTree(), newNode); break; } else { // treat coincident polygons the same as IN_FRONT if (currentNode.getFront() == null) { // reached a leaf node numCoinNodes += currentNode.addToFront(newNode); break; } else { currentNode = currentNode.getFront(); } } } // end while() } /** * a function to add a node to a BSP Tree. * @param newNode -the new node to be added */ public void addNode(BSPNode newNode) { int placement; BSPNode currentNode = root; while (currentNode != null) { placement = currentNode.classifyPolygon(newNode); if (placement == Plane3d.IN_FRONT) { if (currentNode.getFront() == null) { // reached a leaf node numFrontNodes += currentNode.addToFront(newNode); break; } else { currentNode = currentNode.getFront(); } } else if (placement == Plane3d.IN_BACK) { if (currentNode.getBack() == null) { // reached a leaf node numBackNodes += currentNode.addToBack(newNode); break; } else { currentNode = currentNode.getBack(); } } else if (placement == Plane3d.SPANNING) { numSplitNodes += currentNode.splitPoly(getTree(), newNode); break; } else { // treat coincident polygons the same as IN_FRONT if (currentNode.getFront() == null) { // reached a leaf node numCoinNodes += currentNode.addToFront(newNode); break; } else { currentNode = currentNode.getFront(); } } } // end while() } /** * a function to traverse a BSP Tree. The order of the left and right * subtree processing (plus and minus) is determined dynamically by the * position of the eyepoint w.r.t. to the plane of the node. * * FOR EACH NODE [starting with the root] * We need to know which side of the plane the eyepoint is. This is * done by putting the (x,y,z) coordinates of the point in the equation * of the plane: * * IF Ax + By + Cz + D > 0 point is on the + side of plane * draw - subtree * draw node polygon * draw + subtree * ELSE * draw + subtree * draw node polygon * draw - subtree * END FOR * @param g -the graphics object * @param node -the node from which we are traversing * @param eyepoint -viewpoint */ public void displayTree(Graphics g, BSPNode root, Point4 eyePoint) { if (root == null) { return; } double distance = 0; // compute distance from eyepoint to the node's partition plane distance = root.getPartition().pointPlaneDistance(eyePoint); // viewpoint is IN_FRONT of the root node's partition plane if (distance > 0) { displayTree(g, root.getBack(), eyePoint); root.displayNode(g); displayTree(g, root.getFront(), eyePoint); // viewpoint is IN_BACK of (or COINCIDENT with) the root node's // partition plane } else { displayTree(g, root.getFront(), eyePoint); root.displayNode(g); displayTree(g, root.getBack(), eyePoint); } } /** * "The scene rotation introduces another complexity. * We only add a new object to the tree after it is transformed by the * inverse of the current rotation matrix into the same coordinates system * as the other objects - this is really the world coordinate system. * * The viewpoint, however, is in what we might call the viewing * coordinate system. We can only display the tree if we have the * viewpoint in the same coordinate system as the objects. Of course, we * could build the tree in the viewing coordinate system, but then we'd * have to rebuild it every time we change the scene rotation * specification. * * Instead we want to map the viewpoint into the world coordinate system. * That's pretty easy, though. Since our viewing specification is so * simple, the relationship of the viewpoint to the world is determined * only be the scene rotation matrix. Mapping the viewpoint to the world * is exactly the same as mapping the position box to the world -i.e. we * have to apply the inverse of the rotation matrxix to the viewpoint, * which is (0.5, 0.5, 1)." * * @param eyePoint -the current viewpoint * @return eyePoint -the transformed viewpoint */ public Point4 mapViewPoint(Point4 eyePoint) { if (root != null) { Matrix4 currentInverse = View.inverse(); return currentInverse.timesPoint(eyePoint); } else { return eyePoint; } } /** * a simple print function to help bob out */ public void print() { System.out.println("tree name = " + treeName); System.out.println("numFrontNodes = " + numFrontNodes + ", numBackNodes = " + numBackNodes + ", numSplitNodes = " + numSplitNodes + ", numCoinNodes = " + numCoinNodes); } }