Implementing a 2D BSP Tree

To start, you'll create the simple BSPTree class shown in Listing 10.1. This class defines the data structure of the tree as nodes and leaves. As usual, this code is just a start, and you'll add more methods to it later.

Listing 10.1 BSPTree.java
package com.brackeen.javagamebook.bsp2D;
import java.awt.Rectangle;
import java.util.List;
/**
 The BSPTree class represents a 2D Binary Space Partitioned
 tree of polygons. The BSPTree is built using a BSPTreeBuilder
 class, and can be traversed using BSPTreeTraverser class.
*/
public class BSPTree {
 /**
 A Node of the tree. All children of the node are either
 to the front or back of the node's partition.
 */
 public static class Node {
 public Node front;
 public Node back;
 public BSPLine partition;
 public List polygons;
 }
 /**
 A Leaf of the tree. A leaf has no partition or front or
 back nodes.
 */
 public static class Leaf extends Node {
 public float floorHeight;
 public float ceilHeight;
 public Rectangle bounds;
 public boolean isBack;
 }
 private Node root;
 /**
 Creates a new BSPTree with the specified root node.
 */
 public BSPTree(Node root) {
 this.root = root;
 }
 /**
 Gets the root node of this tree.
 */
 public Node getRoot() {
 return root;
 }
}


The BSPTree class contains the inner class Node, which is a node in the tree. The node contains references to front and back nodes, a partition, and a list of polygons. The partition is a BSPLine, which we discuss in the next section. For nodes that aren't leaves, the list of polygons is a list of all the wall polygons collinear with the partition. For leaves (open spaces), this list contains floor and ceiling polygons. The inner class Leaf is a subclass of Node. It contains the height of the floor and ceiling, which you'll use later to keep the player and objects at the correct height. It also contains the rectangular bounds of the leaf, which you'll use to determine object visibility (in other words, if the leaf is visible, objects within its bounds are visible).

The BSP Line

The line you'll use for partitions (and a few other uses) is the BSPLine in Listing 10.2.

Listing 10.2 BSPLine.java
package com.brackeen.javagamebook.bsp2D;
import java.awt.geom.*;
import com.brackeen.javagamebook.math3D.*;
public class BSPLine extends Line2D.Float {
 /**
 X coordinate of the line normal.
 */
 public float nx;
 /**
 Y coordinate of the line normal.
 */
 public float ny;
}


The BSPLine is a subclass of Line2D.Float. The Line2D.Float class is part of the java.awt.geom package that has floating-point fields x1, y1, x2, and y2 that define a line segment. In BSPLine, you also include the values for the line's normal, or the direction perpendicular to the line. The normal points in the direction of the "front" of the partition. This class is just a start; you'll add a bunch of methods to BSPLine as you move forward.

Determining the Side of a Point Relative to a Line

One thing you need to determine is whether polygons are in front of a line, in back of a line, or spanning a line. You do this just like you did polygon clipping in , "3D Graphics": one point at a time. For each point in a polygon, you determine whether the point is in front of or in back of the line. You also need to know whether a point is actually on a line (in other words, is collinear with a line). For example, a polygon might have some points collinear with a line and other points in front. In this case, the polygon would be considered in front of the line, even though parts of it are collinear. Finding whether a point is in front or back of a line is similar to how you determined whether a point was in front or in back of a polygon, only in 2D: Just find the dot product between the vector to the point and the normal of the line. If this value is less than 0, the point is in back; if it is greater than 0, the point is in front; and if it is equal to 0, the point is collinear. One problem is that, due to floating-point inaccuracy, it is pretty rare for a point to actually be collinear. (Even 64-bit doubles won't be accurate enough; you really need infinite precision to be accurate 100% of the time.) This can cause problems if, say, a collinear point is calculated as being in back of the line while other points in a polygon are in front. In this case, the polygon would be considered to be spanning the line, which is inaccurate. To fix this, you must sometimes treat lines as being "thick," as shown in Screenshot.

Screenshot Finding the side of point relative to a "thick" line.

Java graphics 10fig11.gif


In Screenshot, the actual line (shown as a dotted line) has both a "front" line and a "back" line. If a point is between these two lines, the point is considered collinear. This way, you create a collinear area and make up for floating-point inaccuracy. If you assume that the normal to the line is a unit normal (has a length of 1), we can easily "shift" the line forward and backward, and determine the side the point is on for both of these lines. If you want a 1-unit-wide line, shift the line by half of the length of the normal. This is shown in the getSideThick() method in Listing 10.3.

Listing 10.3 getSide() Methods of BSPLine.java
public static final int BACK = -1;
public static final int COLLINEAR = 0;
public static final int FRONT = 1;
public static final int SPANNING = 2;
...
/**
 Normalizes the normal of this line (make the normal's
 length 1).
*/
public void normalize() {
 float length = (float)Math.sqrt(nx * nx + ny * ny);
 nx/=length;
 ny/=length;
}
/**
 Gets the side of this line the specified point is on.
 Because of floating point inaccuracy, a collinear line
 will be rare. For this to work correctly, the normal of
 this line must be normalized, either by setting this line
 to a polygon or by calling normalize().
 Returns either FRONT, BACK, or COLLINEAR.
*/
public int getSideThin(float x, float y) {
 // dot product between vector to the point and the normal
 float side = (x - x1)*nx + (y - y1)*ny;
 return (side < 0)?BACK:(side > 0)?FRONT:COLLINEAR;
}
/**
 Gets the side of this line the specified point is on.
 This method treats the line as 1-unit thick, so points
 within this 1-unit border are considered collinear.
 For this to work correctly, the normal of this line
 must be normalized, either by setting this line to a
 polygon or by calling normalize().
 Returns either FRONT, BACK, or COLLINEAR.
*/
public int getSideThick(float x, float y) {
 int frontSide = getSideThin(x-nx/2, y-ny/2);
 if (frontSide == FRONT) {
 return FRONT;
 }
 else if (frontSide == BACK) {
 int backSide = getSideThin(x+nx/2, y+ny/2);
 if (backSide == BACK) {
 return BACK;
 }
 }
 return COLLINEAR;
}


The methods in Listing 10.3 are in the BSPLine class. The getSideThin() method treats the line normally, while getSideThick() treats the line as being 1 unit thick. Both methods return either FRONT, BACK, or COLLINEAR. Now that you have these methods, finding the side of another line or a polygon is trivial. These methods are shown in Listing 10.4.

Listing 10.4 More getSide() Methods of BSPLine.java
/**
 Gets the side of this line that the specified line segment
 is on. Returns either FRONT, BACK, COLLINEAR, or SPANNING.
*/
public int getSide(Line2D.Float segment) {
 if (this == segment) {
 return COLLINEAR;
 }
int p1Side = getSideThick(segment.x1, segment.y1);
 int p2Side = getSideThick(segment.x2, segment.y2);
 if (p1Side == p2Side) {
 return p1Side;
 }
 else if (p1Side == COLLINEAR) {
 return p2Side;
 }
 else if (p2Side == COLLINEAR) {
 return p1Side;
 }
 else {
 return SPANNING;
 }
}
/**
 Gets the side of this line that the specified polygon
 is on. Returns either FRONT, BACK, COLLINEAR, or SPANNING.
*/
public int getSide(BSPPolygon poly) {
 boolean onFront = false;
 boolean onBack = false;
 // check every point
 for (int i=0; i<poly.getNumVertices(); i++) {
 Vector3D v = poly.getVertex(i);
 int side = getSideThick(v.x, v.z);
 if (side == BSPLine.FRONT) {
 onFront = true;
 }
 else if (side == BSPLine.BACK) {
 onBack = true;
 }
 }
 // classify the polygon
 if (onFront && onBack) {
 return BSPLine.SPANNING;
 }
 else if (onFront) {
 return BSPLine.FRONT;
 }
 else if (onBack) {
 return BSPLine.BACK;
 }
 else {
 return BSPLine.COLLINEAR;
 }
}


The methods in Listing 10.4 are also in the BSPLine class. Both of these methods use "thick" lines. A polygon or line is considered to be SPANNING only if one point is front while another is in back. Later, you'll split spanning polygons in two so that one polygon is in front of the line and one is in back.

The BSP Polygon

In previous chapters, you used the TexturedPolygon3D class for all polygons. In this chapter, you extend this class for polygons within a BSP tree. This class, BSPPolygon in Listing 10.5, is a subclass of TexturedPolygon3D that contains information on whether the polygon is a floor/ceiling or a wall; if it's a wall, it contains a BSPLine that represents the wall. Also, it contains an ambient light intensity so that every polygon can have a different ambient light intensity.

Listing 10.5 BSPPolygon.java
package com.brackeen.javagamebook.bsp2D;
import com.brackeen.javagamebook.math3D.*;
/**
 A BSPPolygon is a TexturedPolygon3D with a type
 (TYPE_FLOOR, TYPE_WALL), an ambient light intensity value, and
 a BSPLine representation if the type is TYPE_WALL.
*/
public class BSPPolygon extends TexturedPolygon3D {
 public static final int TYPE_FLOOR = 0;
 public static final int TYPE_WALL = 1;
 private int type;
 private float ambientLightIntensity;
 private BSPLine line;
 ...
}


It's not shown here, but the BSPPolygon class also has the conventional get and set methods to get and set the type, ambient light intensity, and BSPLine.

Traversing a BSP Tree

You need two ways to traverse a BSP tree, just like you did for the 1D BSP tree example: in-order and front-to-back order. Sometimes you just need to traverse every polygon in the tree (such as during the building process), so you need something like an in-order traversal. When you're drawing, you need a front-to-back traversal. You'll create a BSPTreeTraverser class that actually performs traversals. First, though, you'll create a listener interface so that the BSPTreeTraverser can notify a listener when the polygons in a node are traversed. This BSPTreeTraverseListener interface, shown in Listing 10.6, typically is used for a polygon renderer and when working with all polygons in the tree.

Listing 10.6 BSPTreeTraverseListener.java
package com.brackeen.javagamebook.bsp2D;
/**
 A BSPTreeTraverseListener is an interface for a
 BSPTreeTraverser to signal visited polygons.
*/
public interface BSPTreeTraverseListener {
 /**
 Visits a BSP polygon. Called by a BSPTreeTraverer.
 If this method returns true, the BSPTreeTraverer will
 stop the current traversal. Otherwise, the BSPTreeTraverer
 will continue if there are polygons in the tree that
 have not yet been traversed.
 */
 public boolean visitPolygon(BSPPolygon poly,
 boolean isBackLeaf);
}


In Listing 10.6, the BSPTreeTraverseListener interface provides a visitPolygon() method that is called whenever a polygon is visited. If the implementation of this method returns true, the traversal stops. This way, you can stop a traversal at any time. When drawing, you don't need to continue traversing the tree after the screen is filled, so you can stop the traversal at that point. Of course, this method provides a polygon as a parameter, but in reality, you're traversing nodes. So, in BSPTreeTraverser, you provide a method to visit a node and visit every polygon in a node, as shown in Listing 10.7.

Listing 10.7 visitNode() Method of BSPTreeTraverser.java
private boolean traversing;
private BSPTreeTraverseListener listener;
private GameObjectManager objectManager;
...
/**
 Visits a node in the tree. The BSPTreeTraverseListener's
 visitPolygon() method is called for every polygon in
 the node.
*/
private void visitNode(BSPTree.Node node) {
 if (!traversing || node.polygons == null) {
 return;
 }
 boolean isBack = false;
 if (node instanceof BSPTree.Leaf) {
 BSPTree.Leaf leaf = (BSPTree.Leaf)node;
 isBack = leaf.isBack;
 // mark the bounds of this leaf as visible in
 // the game object manager.
 if (objectManager != null && leaf.bounds != null) {
 objectManager.markVisible(leaf.bounds);
 }
 }
 // visit every polygon
 for (int i=0; traversing && i<node.polygons.size(); i++) {
 BSPPolygon poly = (BSPPolygon)node.polygons.get(i);
 traversing = listener.visitPolygon(poly, isBack);
 }
}


This method just visits every polygon in a node. Also, if there is a GameObjectManager (from , "3D Objects"), this method notifies the manager that the objects within the leaf's bounds are visible. Now let's actually perform some traversals.

In-Order Traversal

First, do a simple in-order traversal, as shown in Listing 10.8.

Listing 10.8 In-Order traverse() Method of BSPTreeTraverser.java
/**
 Traverses a tree in-order.
*/
public void traverse(BSPTree tree) {
 traversing = true;
 traverseInOrder(tree.getRoot());
}
/**
 Traverses a node in-order.
*/
private void traverseInOrder(BSPTree.Node node) {
 if (traversing && node != null) {
 traverseInOrder(node.front);
 visitNode(node);
 traverseInOrder(node.back);
 }
}


There's nothing really new in these methods, except that the traversal stops if the traversing Boolean is set to false. As usual, you're using recursion to traverse the tree. If you're wondering about recursion speed, don't worry about it in this case. With binary trees traversal in Java, you won't see any significant speed improvement if you don't use recursion. Some people try to eliminate recursion because it adds extra overhead. For example, computing Fibonacci numbers is much faster if you don't use recursion because, without recursion, you can eliminate both method-calling overhead and stack overhead. For binary tree traversal, you can do without recursion by implementing your own stack. However, your stack probably won't be any faster than the VM's stack. So go ahead and use recursion in this case, to keep the code clean and more readable.

Front-to-Back Traversal

Next, you'll create a traverse method to traverse nodes in draw order, from front to back. This is just like the 1D BSP example and is shown in Listing 10.9.

Listing 10.9 Draw Order traverse() Method of BSPTreeTraverser.java
private float x;
private float z;
...
/**
 Traverses a tree in draw order (front to back) using
 the specified view location.
*/
public void traverse(BSPTree tree, Vector3D viewLocation) {
 x = viewLocation.x;
 z = viewLocation.z;
 traversing = true;
 traverseDrawOrder(tree.getRoot());
}
/**
 Traverses a node in draw order (front to back) using
 the current view location.
*/
private void traverseDrawOrder(BSPTree.Node node) {
 if (traversing && node != null) {
 if (node instanceof BSPTree.Leaf) {
 // no partition, just handle polygons
 visitNode(node);
 }
 else if (node.partition.getSideThin(x,z)==BSPLine.FRONT) {
 traverseDrawOrder(node.front);
 visitNode(node);
 traverseDrawOrder(node.back);
 }
 else {
 traverseDrawOrder(node.back);
 visitNode(node);
 traverseDrawOrder(node.front);
 }
 }
}


The traverse() method in Listing 10.9 traverses nodes from front to back relative to the specified location. For each node, visitNode() is called, which notifies the listener that a polygon was traversed. That's it for traversing. Of course, you need to implement a BSPTreeTraverseListener class and a few other things before you can actually draw any polygons. But first, let's take a step back and look at building a tree.

Building a Tree

Let's break down BSP tree building into two parts: building the tree and clipping a polygon to a line. Building a tree is a recursive process just like traversing the tree. The basic idea is to take a node with a list of polygons, choose a partition, build the front node using the polygons in front of the partition, and then build the back node using the polygons in back of the partition. This is shown in the BSPTreeBuilder class in Listing 10.10.

Listing 10.10 BSPTreeBuilder.java
/**
 Builds a BSP tree.
*/
public BSPTree build(List polygons) {
 currentTree = new BSPTree(createNewNode(polygons));
 buildNode(currentTree.getRoot());
 return currentTree;
}
/**
 Builds a node in the BSP tree.
*/
protected void buildNode(BSPTree.Node node) {
 // nothing to build if it's a leaf
 if (node instanceof BSPTree.Leaf) {
 return;
 }
 // classify all polygons relative to the partition
 // (front, back, or collinear)
 ArrayList collinearList = new ArrayList();
 ArrayList frontList = new ArrayList();
 ArrayList backList = new ArrayList();
 List allPolygons = node.polygons;
 node.polygons = null;
 for (int i=0; i<allPolygons.size(); i++) {
 BSPPolygon poly = (BSPPolygon)allPolygons.get(i);
 int side = node.partition.getSide(poly);
 if (side == BSPLine.COLLINEAR) {
 collinearList.add(poly);
 }
 else if (side == BSPLine.FRONT) {
 frontList.add(poly);
 }
 else if (side == BSPLine.BACK) {
 backList.add(poly);
 }
 else if (side == BSPLine.SPANNING) {
 BSPPolygon front = clipBack(poly, node.partition);
 BSPPolygon back = clipFront(poly, node.partition);
 if (front != null) {
 frontList.add(front);
 }
 if (back != null) {
 backList.add(back);
 }
 }
 }
 // clean and assign lists
 collinearList.trimToSize();
 frontList.trimToSize();
 backList.trimToSize();
 node.polygons = collinearList;
 node.front = createNewNode(frontList);
 node.back = createNewNode(backList);
 // build front and back nodes
 buildNode(node.front);
 buildNode(node.back);
 if (node.back instanceof BSPTree.Leaf) {
 ((BSPTree.Leaf)node.back).isBack = true;
 }
}
/**
 Creates a new node from a list of polygons. If none of
 the polygons are walls, a leaf is created.
*/
protected BSPTree.Node createNewNode(List polygons) {
 BSPLine partition = choosePartition(polygons);
 // no partition available, so it's a leaf
 if (partition == null) {
 BSPTree.Leaf leaf = new BSPTree.Leaf();
 leaf.polygons = polygons;
 buildLeaf(leaf);
 return leaf;
 }
 else {
 BSPTree.Node node = new BSPTree.Node();
 node.polygons = polygons;
 node.partition = partition;
 return node;
 }
}
/**
 Chooses a line from a list of polygons to use as a
 partition. This method just returns the line formed by
 the first vertical polygon, or null if none is found. A
 smarter method would choose a partition that minimizes
 polygon splits and provides a more balanced, complete tree.
*/
protected BSPLine choosePartition(List polygons) {
 for (int i=0; i<polygons.size(); i++) {
 BSPPolygon poly = (BSPPolygon)polygons.get(i);
 if (poly.isWall()) {
 return new BSPLine(poly);
 }
 }
 return null;
}
/**
 Builds a leaf in the tree, calculating extra information
 like leaf bounds, floor height, and ceiling height.
*/
protected void buildLeaf(BSPTree.Leaf leaf) {
 if (leaf.polygons.size() == 0) {
 // leaf represents an empty space
 leaf.ceilHeight = Float.MAX_VALUE;
 leaf.floorHeight = Float.MIN_VALUE;
 leaf.bounds = null;
 return;
 }
 float minX = Float.MAX_VALUE;
 float maxX = Float.MIN_VALUE;
 float minY = Float.MAX_VALUE;
 float maxY = Float.MIN_VALUE;
 float minZ = Float.MAX_VALUE;
 float maxZ = Float.MIN_VALUE;
 // find min y, max y, and bounds
 Iterator i = leaf.polygons.iterator();
 while (i.hasNext()) {
 BSPPolygon poly = (BSPPolygon)i.next();
 for (int j=0; j<poly.getNumVertices(); j++) {
 Vector3D v = poly.getVertex(j);
 minX = Math.min(minX, v.x);
 maxX = Math.max(maxX, v.x);
 minY = Math.min(minY, v.y);
 maxY = Math.max(maxY, v.y);
 minZ = Math.min(minZ, v.z);
 maxZ = Math.max(maxZ, v.z);
 }
 }
 // find any platform within the leaf
 i = leaf.polygons.iterator();
 while (i.hasNext()) {
 BSPPolygon poly = (BSPPolygon)i.next();
 // if a floor
 if (poly.getNormal().y == 1) {
 float y = poly.getVertex(0).y;
 if (y > minY && y < maxY) {
 minY = y;
 }
 }
 }
 // set the leaf values
 leaf.ceilHeight = maxY;
 leaf.floorHeight = minY;
 leaf.bounds = new Rectangle(
 (int)Math.floor(minX), (int)Math.floor(minZ),
 (int)Math.ceil(maxX-minX+1),
 (int)Math.ceil(maxZ-minZ+1));
}


In this code, the build() method creates a new node that contains every polygon. Note that this method takes only BSPPolygons; because you're using a 2D BSP tree, this way you can easily tell whether a polygon is a vertical wall or a horizontal floor/ceiling. The createNewNode() method creates a new node containing every polygon in the specified list. The buildNode() method builds a node based on the node's partition. This method classifies every polygon as being either in front, in back, spanning, or collinear with the node's partition. Then it puts each polygon in the proper child node. So, polygons to the front of the partition are placed in the node's "front" child node, and polygons in back of the partition are places in the node's "back" child node. Polygons that span the partition are split by using the clipFront() and clipBack() methods, which we discuss shortly. The choosePartition() method chooses a partition from a list of polygons. As mentioned earlier, you won't be making a "smart" decision about what to choose as a partition; instead, you'll just choose the first wall in the list as a partition. Optimizing this method can be an exercise for the reader. The buildLeaf() method simply calculates the floor height, ceiling height, and 2D bounds of the polygons within the leaf. That's actually the bulk of building a BSP tree right there. Next, you need to write the methods to clip a polygon to a line.

Finding the Intersection of Two Lines

When you clip a polygon to a line, you actually ignore the y component of the polygon to make it a 2D clip. The clip will be similar to how you did polygon clipping in , but you need to find the intersection of an edge of the polygon with a line. In other words, you need to find the intersection of two lines. The idea behind finding the intersection is shown in Screenshot.

Screenshot Finding the intersection of two lines.

Java graphics 10fig12.gif


In Screenshot, the point I is the intersection between the two lines. The value u is a fraction of the intersection within line A, so if the two line segments intersect, u will be between 0.0 and 1.0. The same thing applies for value v in line B. The equations in Screenshot are just the basic equations of a line, but you can use these formulas to get the intersection. If you solve for u, you get this:

numerator = (B2y–B1y)(A2x–A1x)–(B2x–B1x)(A2y–A1y)
denominator = (B2y–B1y)(A2x–A1x)–(B2x–B1x)(A2y–A1y)
u = numerator/denominator


Then, with u, you can find the intersection point:

x = A1x+u(A2x–A1x)
y = A1y+u(A2y–A1y)


We sum up these equations in the getIntersection() methods in BSPLine, as shown in Listing 10.11.

Listing 10.11 Intersection Methods of BSPLine.java
/**
 Returns the fraction of intersection along this line.
 Returns a value from 0 to 1 if the segments intersect.
 For example, a return value of 0 means the intersection
 occurs at point (x1, y1), 1 means the intersection
 occurs at point (x2, y2), and .5 means the intersection
 occurs halfway between the two endpoints of this line.
 Returns -1 if the lines are parallel.
*/
public float getIntersection(Line2D.Float line) {
 // The intersection point I, of two vectors, A1->A2 and
 // B1->B2, is:
 // I = A1 + u * (A2 - A1)
 // I = B1 + v * (B2 - B1)
 //
 // Solving for u gives us the following formula.
 // u is returned.
 float denominator = (line.y2 - line.y1) * (x2 - x1) -
 (line.x2 - line.x1) * (y2 - y1);
 // check if the two lines are parallel
 if (denominator == 0) {
 return -1;
 }
 float numerator = (line.x2 - line.x1) * (y1 - line.y1) -
 (line.y2 - line.y1) * (x1 - line.x1);
 return numerator / denominator;
}
/**
 Returns the intersection point of this line with the
 specified line.
*/
public Point2D.Float getIntersectionPoint(Line2D.Float line) {
 return getIntersectionPoint(line, null);
}
/**
 Returns the intersection of this line with the specified
 line. If intersection is null, a new point is created.
*/
public Point2D.Float getIntersectionPoint(Line2D.Float line,
 Point2D.Float intersection)
{
 if (intersection == null) {
 intersection = new Point2D.Float();
 }
 float fraction = getIntersection(line);
 intersection.setLocation(
 x1 + fraction * (x2 - x1),
 y1 + fraction * (y2 - y1));
 return intersection;
}


The getIntersection() method calculates u, or the fraction of intersection along the line. The getIntersectionPoint() method calculates the (x,y) values of the intersection and creates a new Point2D.Float if one isn't specified. If you were dealing with a 3D BSP tree, you would have to clip polygons to a plane rather than a line. This would involve clipping each edge of the polygon to the plane, so it could be accomplished with a line-to-plane intersection instead of a line-to-line intersection. Now that you can compute intersections, you can move on to clipping polygons.

Clipping Polygons by a Line

Clipping polygons to a line is similar to the clipping you did in and is a simple 2D clip. These methods, shown in Listing 10.12, just clip a polygon to a line, ignoring the y component of the polygon.

Listing 10.12 Clip Methods of BSPBuilder.java
/**
 Clips away the part of the polygon that lies in front
 of the specified line. The returned polygon is the part
 of the polygon in back of the line. Returns null if the
 line does not split the polygon. The original
 polygon is untouched.
*/
protected BSPPolygon clipFront(BSPPolygon poly, BSPLine line) {
 return clip(poly, line, BSPLine.FRONT);
}
/**
 Clips away the part of the polygon that lies in back
 of the specified line. The returned polygon is the part
 of the polygon in front of the line. Returns null if the
 line does not split the polygon. The original
 polygon is untouched.
*/
protected BSPPolygon clipBack(BSPPolygon poly, BSPLine line) {
 return clip(poly, line, BSPLine.BACK);
}
/**
 Clips a BSPPolygon so that the part of the polygon on the
 specified side (either BSPLine.FRONT or BSPLine.BACK)
 is removed, and returns the clipped polygon. Returns null
 if the line does not split the polygon. The original
 polygon is untouched.
*/
protected BSPPolygon clip(BSPPolygon poly, BSPLine line,
 int clipSide)
{
 ArrayList vertices = new ArrayList();
 BSPLine polyEdge = new BSPLine();
 // add vertices that aren't on the clip side
 Point2D.Float intersection = new Point2D.Float();
 for (int i=0; i<poly.getNumVertices(); i++) {
 int next = (i+1) % poly.getNumVertices();
 Vector3D v1 = poly.getVertex(i);
 Vector3D v2 = poly.getVertex(next);
 int side1 = line.getSideThin(v1.x, v1.z);
 int side2 = line.getSideThin(v2.x, v2.z);
 if (side1 != clipSide) {
 vertices.add(v1);
 }
 if ((side1 == BSPLine.FRONT && side2 == BSPLine.BACK) ||
 (side2 == BSPLine.FRONT && side1 == BSPLine.BACK))
 {
 // ensure v1.z < v2.z
 if (v1.z > v2.z) {
 Vector3D temp = v1;
 v1 = v2;
 v2 = temp;
 }
 polyEdge.setLine(v1.x, v1.z, v2.x, v2.z);
 float f = polyEdge.getIntersection(line);
 Vector3D tPoint = new Vector3D(
 v1.x + f * (v2.x - v1.x),
 v1.y + f * (v2.y - v1.y),
 v1.z + f * (v2.z - v1.z));
 vertices.add(tPoint);
 // remove any created t-junctions
 removeTJunctions(v1, v2, tPoint);
 }
 }
 // Remove adjacent equal vertices. (A->A) becomes (A)
 for (int i=0; i<vertices.size(); i++) {
 Vector3D v = (Vector3D)vertices.get(i);
 Vector3D next = (Vector3D)vertices.get(
 (i+1) % vertices.size());
 if (v.equals(next)) {
 vertices.remove(i);
 i--;
 }
 }
 if (vertices.size() < 3) {
 return null;
 }
 // make the polygon
 Vector3D[] array = new Vector3D[vertices.size()];
 vertices.toArray(array);
 return poly.clone(array);
}


A couple extra steps are needed when clipping a polygon. First, remove adjacent vertices that are equal. For example, if two vertices next to each other are the same, their edge will have a length of 0. One of these equal vertices is removed. Also remove any T-junctions that you create. What are T-junctions? Glad you asked! Let's talk about it.

Removing T-Junction Gaps

Screenshot shows an example T-junction gap. Due to floating-point inaccuracy, T-junctions can sometimes lead to gaps between polygons, sometimes only when viewed from certain angles. In this example, the large polygon has only three vertices. When the three polygons are transformed, a gap shows up between them. Most of the time, this gap isn't visible. However, occasionally, the gap appears as a missing pixel or two, or even a speckled line of missing pixels.

Screenshot The large polygon has only three vertices. Due to floating-point inaccuracy, T-junctions can sometimes lead to gaps between polygons, sometimes only when viewed from certain angles.

Java graphics 10fig13.gif


Unfortunately, this is another problem for which you need infinite floating-point precision to solve it correctly. But, as usual, there is a workaround! To eliminate the gap between the T-junctions, you can add another vertex to the spanning polygon at the point of intersection. This is shown in Screenshot.

Screenshot To eliminate T-junction gaps, the large polygon has a fourth vertex it shares with the other two polygons.

Java graphics 10fig14.gif


So, to eliminate T-junction gaps, the code inserts vertices into polygon edges whenever a polygon split occurs. This way, building the BSP tree never creates new T-junctions when it splits polygons. The idea is simple enough and is shown in the code in Listing 10.13.

Listing 10.13 T-Junction Removal Methods of BSPBuilder.java
/**
 Remove any T-Junctions from the current tree along the
 line specified by (v1, v2). Find all polygons with this
 edge and insert the T-intersection point between them.
*/
protected void removeTJunctions(final Vector3D v1,
 final Vector3D v2, final Vector3D tPoint)
{
 BSPTreeTraverser traverser = new BSPTreeTraverser(
 new BSPTreeTraverseListener() {
 public boolean visitPolygon(BSPPolygon poly,
 boolean isBackLeaf)
 {
 removeTJunctions(poly, v1, v2, tPoint);
 return true;
 }
 }
 );
 traverser.traverse(currentTree);
}
/**
 Remove any T-Junctions from the specified polygon. The
 T-intersection point is inserted between the points
 v1 and v2 if there are no other points between them.
*/
protected void removeTJunctions(BSPPolygon poly,
 Vector3D v1, Vector3D v2, Vector3D tPoint)
{
 for (int i=0; i<poly.getNumVertices(); i++) {
 int next = (i+1) % poly.getNumVertices();
 Vector3D p1 = poly.getVertex(i);
 Vector3D p2 = poly.getVertex(next);
 if ((p1.equals(v1) && p2.equals(v2)) ||
 (p1.equals(v2) && p2.equals(v1)))
 {
 poly.insertVertex(next, tPoint);
 return;
 }
 }
}


In Listing 10.13, you take the brute-force approach to finding matching T-junctions: Just check every edge of every polygon in the tree. Admittedly, this could be accomplished faster by just searching for polygons that share an edge with the line of the T-junction, but this works as well. Notice that the BSP tree building removes only T-junctions that are created from clipped polygons. In other words, it assumes that polygons passed to the BSP builder don't have any T-junctions. Taking a step back, you have everything you need for building: the building algorithm and polygon clipping. You also have BSP traversal, so let's make a short demo to try everything out.

Testing the BSP Tree

At this point, even though you can't draw polygons in the BSP tree in a 3D scene yet, you can create a test demo for the BSP tree. The BSPTest2D does this, drawing a bird's-eye view of a 3D scene just like in the previous examples and figures. Like in previous chapters, this demo extends the GameCore class, and its interesting methods are shown here in Listing 10.14.

Listing 10.14 BSP Building in BSPTest2D.java
public void createPolygons() {
 // The floor polygon
 BSPPolygon floor = new BSPPolygon(new Vector3D[] {
 new Vector3D(0,0,0), new Vector3D(0,0,600),
 new Vector3D(800,0,600), new Vector3D(800,0,0)
 }, BSPPolygon.TYPE_FLOOR);
 polygons.add(floor);
 // vertices defined from left to right as the viewer
 // looks at the wall
 BSPPolygon wallA = createPolygon(
 new BSPLine(0, 150, 500, 75), 0, 300);
 BSPPolygon wallB = createPolygon(
 new BSPLine(500, 75, 500, 300), 0, 300);
 BSPPolygon wallC = createPolygon(
 new BSPLine(500, 300, 800, 300), 0, 300);
 BSPPolygon wallD = createPolygon(
 new BSPLine(800, 450, 0, 450), 0, 300);
 polygons.add(wallA);
 polygons.add(wallB);
 polygons.add(wallC);
 polygons.add(wallD);
}
public BSPPolygon createPolygon(BSPLine line, float bottom,
 float top)
{
 return new BSPPolygon(new Vector3D[] {
 new Vector3D(line.x1, bottom, line.y1),
 new Vector3D(line.x2, bottom, line.y2),
 new Vector3D(line.x2, top, line.y2),
 new Vector3D(line.x1, top, line.y1)
 }, BSPPolygon.TYPE_WALL);
}
public void buildTree() {
 BSPTreeBuilder builder = new BSPTreeBuilder();
 bspTree = builder.build(polygons.subList(0, numWalls+1));
}


In Listing 10.14, BSPPolygons are created to match the previous floor plan example. One giant floor that covers the entire area is created, which is unrealistic in the real-world (you wouldn't want nonvisible floors that are behind walls), but this works well as an example. The rest of BSPTest2D draws the polygons from a bird's-eye perspective, as shown in the screenshot in Screenshot.

Screenshot Screenshot of BSPTest2D.

Java graphics 10fig15.gif


In Screenshot, the mouse represents the camera's location, and the numbers represent the order in which the polygons are drawn from the camera location. That's it! As you can see in the demo, building and traversal work great. Now you can move on to the goal of this chapter: actually drawing the polygons in the BSP tree.

Screenshot


   
Comments