Add to Favorites    Make Home Page 5210 Online  
 Language Categories  
 Our Services  

Java Data Structures - Contents

Binary Space Partition (BSP) Trees...


Search Projects & Source Codes:

    - Dog3D DEMO - (Click here to see the demo for this section)

    As mentioned previously, tree data structures are wonderful in some cases for certain purposes. One of these purposes is Hidden Surface Removal (HSR). HSR in graphics turns out to be quite a complicated problem. To paraphrase one book, "HSR is a thorn in a graphics programmer's back".

    Most graphics programmers today are more concerned with an efficient way of eliminating hidden (or unseen) surfaces, than with the inner workings of pixel plotting and/or texture mapping. Games like Wolfenstain 3D, DOOM, and Quake by id Software, are mostly reflections of innovations in the field of HSR. (and a bit of added processing power ;-)

    First, lets define HSR in a more understandable manner. Imagine you're standing in a room, you can only see the walls of the room you're in, and not the walls of other rooms (which are beside your room). The walls of your room cover up your view, so, you can't see anything else other than the walls of your room. This relatively simple concept turns out to be quite a bundle when it comes to computers. There are literally hundreds of different approaches to this, and they all have their advantages and disadvantages.

    One solution used in Wolfenstain 3D is ray casting. Ray casting simply passes a horizontal "ray" (or two rays) across a map (a map in such a case is simply a 2D array of values representing blocks); if a ray hits a "filled" block on the map, then a vertical scaled texture is drawn, if not, the ray continues on to the next block. This produces a pretty blocky world, evidenced by Wolfenstain 3D.

    Another solution is ray tracing, it's a bit more involved than ray casting (actually, ray casting came from simplifying ray tracing). In this, a ray is passed over all pixels on the screen, and when a ray hits an object in 3D space, that pixel is drawn having a texture color of that object. This sounds like a lot of work, and it is. Ray tracing, currently, is only good for high quality images, and not for real time games where images are generated on the fly. (it can easily take minutes or even hours to ray trace a scene)

    There are many others, like Z-Buffering, Painter's Algorithm, Portals, etc., and the one we're here to talk about is Binary Space Partition (BSP), BSP was used successfully in games like DOOM and Quake, and has the potential for a lot more. It is a process of recursively subdividing space, building a binary tree, and later traversing the tree, knowing what to draw and when.

    Imagine for example that you had to draw two rooms, one beside the other, with a small door in between. What you can do is draw the walls of the farther room, then draw the door, and draw the walls of the room you're in, overwriting parts of already drawn walls of the farther room. Now, how can you figure out where you're located (in which room), so that you can first draw the farther room, and then draw the room you're in? Easy, you create a binary tree of the world; then, given your point in space, you can easily determine your location relative to the world. Thus, you can determine what to draw first, and what to draw later. (to produce a nice, real looking 3D world)

    To understand this concept you need to be able to visualize the tree, and how you traverse it (have a solid understanding of the tree structure). First, you create a tree of the world, by selecting a line (or plane in 3D), adding that line (or plane) to this node; you later use that line (or plane), to sort the whole world into two. One side with lines (or planes) that are in "front" of that selected line (or plane), and the rest which are in the back. The front and back are determined from the line (or plane) equation, and the x, y, z parameters from the lines (or planes) being checked. If there comes a time where some line (or plane) is neither in front or in back (has points on both sides), it is split (partitioned) into two, one side goes in front, and the other side in back. The process recursively continues with each of these new subsets until there are no more lines to select.

    The result is a tree representing the world. To traverse it, you evaluate the player's location in relation to the root node, if it is in front, you recursively draw the back, and then the front, if it is in back, you recursively draw the front, and then the back. This simple procedure produces a nicely sorted list of "walls" to draw. The above describes a back to front traversal, you do totally the opposite for a front to back traversal, which seems to be getting more popular now a days.

    In a back to front traversal, you don't have to worry about clipping; everything looks perfect after drawing, since everything unwanted is overwritten (i.e.: Painter's Algorithm). In a front to back traversal, you've got quite a lot to worry about because of clipping. You need an efficient way of remembering which pixels have been drawn, etc. For now, we'll be mostly concerned with back to front traversal because of it's simple nature.

    In this type of a discussion, it helps to keep things simple; I will only describe how to do this type of a thing for a very primitive 2D case. We will take a bunch of line coordinates, create a binary space partition tree, and later traverse that tree, displaying a 3D looking world (which is actually 2D). Don't feel too bad. 2D is simple and lets you understand the structure. DOOM is totally 2D, and still looks really cool. 3D is full of math problems which will only complicate the matter at this point. Besides, once you understand the structure, writing your own 3D implementation shouldn't be a problem (if you can get through the 3D math ;-)

    Well, lets get to it. The first thing that we need for any kind of tree structure is a node. In our case, the node should contain the partition plane (in our case the line equation of a line dividing this node), and a list of lines currently spanning this node. Of course, it wouldn't be a tree node without at least two pointers to it's children; so, we'll include those too! Follows the source for this simple, yet useful node.

class javadata_dog3dBSPNode{
    public float[] partition = null;
    public Object[] lines = null;
    public javadata_dog3dBSPNode front = null;
    public javadata_dog3dBSPNode back = null;

    As you can see, there is nothing tricky or hard to the piece of code above. Right now is a good time to figure out the conventions used in this program. A point is represented by a two element integer array. A line is represented by a five element integer array; the first four are for the starting point and ending point respectively, and the last is for the color. A partition plane (line equation) is represented by a three element floating point array. Because our partition planes are not normalized, we could as well used an integer array, but I doubt the several floating point calculations would have made much difference (even for a below-Pentium system!).

    You'll also notice that the class above is not public, that's because all the Dog 3D classes are contained within one file ( in case you're interested). (this program is not very modular, and separate parts make little sense outside of the program)

    What we need next is our Binary Space Partition Tree to manipulate the nodes we've just created. The tree should be able to accept a list of lines, and build itself. It should also be able to traverse itself (in our case render itself). And lastly, it should contain (or have access to) all the necessary methods for working with points and lines (i.e.: comparison functions, splitting functions, etc.). The source for the Binary Space Partition Tree follows:

class javadata_dog3dBSPTree{
    private javadata_dog3dBSPNode root;
    public int eye_x,eye_y;
    public double eye_angle;
    private javadata_dog3d theParent = null;

    private final static int SPANNING = 0;
    private final static int IN_FRONT = 1;
    private final static int IN_BACK = 2;
    private final static int COINCIDENT = 3;

    public javadata_dog3dBSPTree(javadata_dog3d p){
        root = null;
        eye_x = eye_y = 0;
        eye_angle = 0.0;
        theParent = p;

    private float[] getLineEquation(int[] line){
        float[] equation = new float[3];
        int dx = line[2] - line[0];
        int dy = line[3] - line[1];
        equation[0] = -dy;
        equation[1] = dx;
        equation[2] = dy*line[0] - dx*line[1];
        return equation;

    private int evalPoint(int x,int y,float[] p){
        double c = p[0]*x + p[1]*y + p[2];
        if(c > 0)
            return IN_FRONT;
        else if(c < 0)
            return IN_BACK;
        else return SPANNING;

    private int evalLine(int[] line,float[] partition){
        int a = evalPoint(line[0],line[1],partition);
        int b = evalPoint(line[2],line[3],partition);
        if(a == SPANNING){
            if(b == SPANNING)
                return COINCIDENT;
            else return b;
        }if(b == SPANNING){
            if(a == SPANNING)
                return COINCIDENT;
            else return a;
        }if((a == IN_FRONT) && (b == IN_BACK))
            return SPANNING;
        if((a == IN_BACK) && (b == IN_FRONT))
            return SPANNING;
        return a;

    public int[][] splitLine(int[] l,float[] p){
        int[][] q = new int[2][5];
        q[0][4] = q[1][4] = l[4];
        int cross_x = 0,cross_y = 0;
        float[] lEq = getLineEquation(l);
        double divider = p[0] * lEq[1] - p[1] * lEq[0];
        if(divider == 0){
            if(lEq[0] == 0)
                cross_x = l[0];
            if(lEq[1] == 0)
                cross_y = l[1];
            if(p[0] == 0)
                cross_y = (int)-p[1];
            if(p[1] == 0)
                cross_x = (int)p[2];
            cross_x = (int)((-p[2]*lEq[1] + p[1]*lEq[2])/divider);
            cross_y = (int)((-p[0]*lEq[2] + p[2]*lEq[0])/divider);
        int p1 = evalPoint(l[0],l[1],p);
        int p2 = evalPoint(l[2],l[3],p);
        if((p1 == IN_BACK) && (p2 == IN_FRONT)){
            q[0][0] = cross_x;  q[0][1] = cross_y;
            q[0][2] = l[2];     q[0][3] = l[3];
            q[1][0] = l[0];     q[1][1] = l[1];
            q[1][2] = cross_x;  q[1][3] = cross_y;
        }else if((p1 == IN_FRONT) && (p2 == IN_BACK)){
            q[0][0] = l[0];     q[0][1] = l[1];
            q[0][2] = cross_x;  q[0][3] = cross_y;
            q[1][0] = cross_x;  q[1][1] = cross_y;
            q[1][2] = l[2];     q[1][3] = l[3];
            return null;
        return q;

    private void build(javadata_dog3dBSPNode tree,Vector lines){
        int[] current_line = null;
        Enumeration enum = lines.elements();
            current_line = (int[])enum.nextElement();
        tree.partition = getLineEquation(current_line);
        Vector _lines = new Vector();

        Vector front_list = new Vector();
        Vector back_list = new Vector();
        int[] line = null;
            line = (int[])enum.nextElement();
            int result = evalLine(line,tree.partition);
            if(result == IN_FRONT)          /* in front */
            else if(result == IN_BACK)      /* in back */
            else if(result == SPANNING){    /* spanning */
                int[][] split_line = splitLine(line,tree.partition);
                if(split_line != null){
                    /* error here! */
            }else if(result == COINCIDENT)
            tree.front = new javadata_dog3dBSPNode();
            tree.back = new javadata_dog3dBSPNode();
        tree.lines = new Object[_lines.size()];

    public void build(Vector lines){
        if(root == null)
            root = new javadata_dog3dBSPNode();

    private void renderTree(javadata_dog3dBSPNode tree){
        int[] tmp = null;
        if(tree == null)
            return; /* check for end */
        int i,j = tree.lines.length;
        int result = evalPoint(eye_x,eye_y,tree.partition);
        if(result == IN_FRONT){
                tmp = (int[])tree.lines[i];
                if(evalPoint(eye_x,eye_y,getLineEquation(tmp)) == IN_FRONT)
        }else if(result == IN_BACK){
                tmp = (int[])tree.lines[i];
                if(evalPoint(eye_x,eye_y,getLineEquation(tmp)) == IN_FRONT)
        }else{   /* the eye is on the partition plane */

    public void renderTree(){

    The above might look intimidating, but it's actually really simple. The are a lot of data members; some familiar, some are not. The root data member is obvious, it's the root of the tree! The next several are the eye's current position. We need this since we don't want to pass them as a parameter every time we render. The next data member is theParent, which is a reference back to the original applet. This member is used during the rendering process (not very modular). The last data members are constants for the point and line comparison functions.

    The constructor takes the parent applet as it's parameter, and initializes theParent and other data members. The actual insertion of data into the tree is accomplished with the build(java.util.Vector) method. This method calls a more complicated method of the same name, but with more parameters. The build() method goes through the given java.util.Vector. It first selects the first line in the list to be the splitting plane (for the current node). It then goes through the rest of the list, sorting the lines in relation to that splitting plane. If a line is in front (determined by the evaluation functions) then it's added to the front list. If a line is in back, it's added to the back list. If a line is spanning the splitting node (has end points on both sides of the splitting node), then that line is split by a splitLine() function; one part goes in front, and the other into the back. If some line is actually coincident with the splitting plane, then it's added to the list of the current node. After all that, we end up with two lists of lines; one list for the back, and one list for the front. We then recursively go through the two lists.

    The process described above is fairly hard to describe (an oxymoron?). If you want a more formal (maybe better?) description, you can search the Internet for the "BSPFAQ." It is a document thoroughly describing BSP trees in a more formal way.

    Once the tree is built, you are ready to traverse it! The traversing is accomplished by calling the renderTree() method. What it does is first evaluate the eye's position in relation to the current splitting plane of the node. If it's in front, we recursively render the back child, if it's in back, we recursively render the front child. The rendering itself is accomplished by looping through the lines of the current node and drawing them. The evaluation function call inside that loop is doing back-face-culling (back-face-removal). It is a process of making sure that we're not drawing lines (walls) which are not facing us. The drawing is done by calling renderLine() method of theParent (which is a reference back to the original applet).

    If you've survived this far, you're in good shape. The remaining part of this applet is simply the initialization and rendering, which is not really related to data structures. Anyway, here we go again, diving into some source before explaining it...

public class javadata_dog3d extends Applet implements Runnable{
    private Thread m_dog3d = null;
    private String m_map = "javadata_dog3dmap.txt";
    private int m_width,m_height;
    private int m_mousex = 0,m_mousey = 0;
    private Vector initial_map = null;
    private javadata_dog3dBSPTree theTree = null;
    private Image double_image = null;
    private Graphics double_graphics = null;
    public int eye_x = 220,eye_y = 220;
    public double eye_angle = 0;
    private boolean KEYUP=false,KEYDOWN=false,
    private boolean MOUSEUP=true;

    public void renderLine(int[] l){
        double x1=l[2];
        double y1=l[3];
        double x2=l[0];
        double y2=l[1];
        double pCos = Math.cos(eye_angle);
        double pSin = Math.sin(eye_angle);
        int[] x = new int[4];
        int[] y = new int[4];
        double pD=-pSin*eye_x+pCos*eye_y;
        double pDp=pCos*eye_x+pSin*eye_y;
        double rz1,rz2,rx1,rx2;
        int Screen_x1=0,Screen_x2=0;
        double Screen_y1,Screen_y2,Screen_y3,Screen_y4;
        rz1=pCos*x1+pSin*y1-pDp;     //perpendicular line to the players
        rz2=pCos*x2+pSin*y2-pDp;     //view point
        if((rz1<1) && (rz2<1))
        double pTan = 0;
        if((x2-x1) == 0)
            pTan = Double.MAX_VALUE;
            pTan = (y2-y1)/(x2-x1);
        pTan = (pTan-Math.tan(eye_angle))/(1+
        if(rz1 < 1){
        }if(rz2 < 1){
        double z1 = m_width/2/rz1;
        double z2 = m_width/2/rz2;
        if(Screen_x1 > m_width)
        int wt=88;
        int wb=-40;
        if(Screen_x1 < 0){
        }if(Screen_x2 > (m_width)){
        }if((Screen_x2-Screen_x1) == 0)
        x[0] = (int)Screen_x1;
        y[0] = (int)(Screen_y1);
        x[1] = (int)Screen_x2;
        y[1] = (int)(Screen_y2);
        x[2] = (int)Screen_x2;
        y[2] = (int)(Screen_y3);
        x[3] = (int)Screen_x1;
        y[3] = (int)(Screen_y4);
        double_graphics.setColor(new Color(l[4]));

    private void loadInputMap(){
        initial_map = new Vector();
        int[] tmp = null;
        int current;
        StreamTokenizer st = null;
            st = new StreamTokenizer(
                (new URL(getDocumentBase(),m_map)).openStream());
        }catch( e){
        }catch(IOException f){
            for(st.nextToken(),tmp = new int[5],current=1;
            st.ttype != StreamTokenizer.TT_EOF;
                if(st.ttype == StreamTokenizer.TT_EOL){
                    if(tmp != null)
                    tmp = null; tmp = new int[5];
                    if(current == 1)
                        System.out.println("getting: "+st.nval);
                    else if(current == 2)
                        tmp[0] = (int)st.nval;
                    else if(current == 3)
                        tmp[1] = (int)st.nval;
                    else if(current == 4)
                        tmp[2] = (int)st.nval;
                    else if(current == 5)
                        tmp[3] = (int)st.nval;
                    else if(current == 6)
                        tmp[4] = (int)Integer.parseInt(st.sval,0x10);
        }catch(IOException e){

    public void init(){
        String param;
        param = getParameter("map");
        if (param != null)
            m_map = param;
        m_width = size().width;
        m_height = size().height;


        double_image = createImage(m_width,m_height);
        double_graphics = double_image.getGraphics();

        theTree = new javadata_dog3dBSPTree(this);;

        theTree.eye_x = eye_x;
        theTree.eye_y = eye_y;
        theTree.eye_angle = eye_angle;


    public void paint(Graphics g){

    public void update(Graphics g){

    public void start(){
        if(m_dog3d == null){
            m_dog3d = new Thread(this);

    public void run(){
        boolean call_update;
            call_update = false;
                    eye_x += (int)(Math.cos(eye_angle)*10);
                    eye_y += (int)(Math.sin(eye_angle)*10);
                    call_update = true;
                    eye_x -= (int)(Math.cos(eye_angle)*10);
                    eye_y -= (int)(Math.sin(eye_angle)*10);
                    call_update = true;
                    eye_angle += Math.PI/45;
                    call_update = true;
                    eye_angle -= Math.PI/45;
                    call_update = true;
                    theTree.eye_x = eye_x;
                    theTree.eye_y = eye_y;
                    theTree.eye_angle = eye_angle;
            }catch(java.lang.InterruptedException e){

    public boolean keyUp(Event evt,int key){
        if(key == Event.UP){
            KEYUP = false;
        }else if(key == Event.DOWN){
            KEYDOWN = false;
        }else if(key == Event.LEFT){
            KEYLEFT = false;
        }else if(key == Event.RIGHT){
            KEYRIGHT = false;
        return true;

    public boolean keyDown(Event evt,int key){
        if(key == Event.UP){
            KEYUP = true;
        }else if(key == Event.DOWN){
            KEYDOWN = true;
        }else if(key == Event.LEFT){
            KEYLEFT = true;
        }else if(key == Event.RIGHT){
            KEYRIGHT = true;
        return true;

    public boolean mouseDown(Event evt, int x, int y){
        MOUSEUP = false;
        m_mousex = x;
        m_mousey = y;
        return true;

    public boolean mouseUp(Event evt, int x, int y){
        MOUSEUP = true;
        m_mousex = x;
        m_mousey = y;
        return true;

    public boolean mouseDrag(Event evt, int x, int y){
        if(m_mousey > y){
            eye_x += (int)(Math.cos(eye_angle)*(7));
            eye_y += (int)(Math.sin(eye_angle)*(7));
        if(m_mousey < y){
            eye_x -= (int)(Math.cos(eye_angle)*(7));
            eye_y -= (int)(Math.sin(eye_angle)*(7));
        if(m_mousex > x){
            eye_angle += Math.PI/32;
        if(m_mousex < x){
            eye_angle -= Math.PI/32;
        theTree.eye_x = eye_x;
        theTree.eye_y = eye_y;
        theTree.eye_angle = eye_angle;
        m_mousex = x;
        m_mousey = y;
        return true;

    The above should be quite easy (if you've ever written an applet). I will not explain the IO nor the threading in this code. The code starts up by getting the map file and loading it. The format of the map file is shown below:

1  100 800 100 500 "FFFFFF"
2  200 500 200 400 "FFFF00"
3  400 800 100 800 "FF00FF"
4  400 700 400 800 "00FFFF"
5  500 700 400 700 "FF0000"
6  500 800 500 700 "0000FF"
7  800 800 500 800 "FFFF00"
8  800 500 800 800 "FF00FF"
9  700 500 800 500 "00FFFF"
10  700 400 700 500 "FF00FF"
11  800 400 700 400 "00FF00"
12  800 100 800 400 "FF00FF"
13  500 100 800 100 "00FF00"
14  500 200 500 100 "FFFF00"
15  400 200 500 200 "FF00FF"
16  400 100 400 200 "00FFFF"
17  100 100 400 100 "FF0000"
18  100 400 100 100 "0000FF"
19  200 400 100 400 "00FF00"
20  100 500 200 500 "0000FF"
21  300 400 300 500 "FFFF00"
22  400 400 300 400 "00FFFF"
23  400 300 400 400 "FF00FF"
24  500 300 400 300 "FFFFFF"
25  500 400 500 300 "FFFF00"
26  600 400 500 400 "FF00FF"
27  600 500 600 400 "00FFFF"
28  500 500 600 500 "FFFFFF"
29  500 600 500 500 "FF00FF"
30  400 600 500 600 "FFFFFF"
31  400 500 400 600 "00FF00"
32  300 500 400 500 "FF00FF"

    With first column being the number of the line (wall), the second column being the x coordinate of the starting point of the line. The third column being the y coordinate of the starting point of the line. The forth column being the x coordinate of the ending point of the line. The fifth column being the y coordinate of the ending point of the line. And lastly, the sixth column is the color of the line (wall) in RGB format (similar to the way color is represented in documents).

    Once the map is loaded, we create the tree. Once that's done, we create a double buffer surface to draw into. All that action inside the init() method of the applet! After that, we simply fall into the main loop (the run() method), and render the tree! The main loop checks to see if there are arrow keys pressed, if they are, then the eye's position is updated and redraw() method is called. The redraw() method effectively calls the update() method, which clears the double buffer surface, and call's tree's method to render the tree. It then calls the paint() method to paint the double buffer surface to the screen area of the applet.

    The renderLine() method, referred to earlier, is not the best that it could be (it even has lots of bugs!). It is badly written, and is not very efficient. But still, it does a rather satisfactory job at rendering a perspective representation of the line onto the double buffer surface. (besides, this is not even the subject of this section)

    You can see the whole thing in action by clicking here!

    Well, that's mostly it for Binary Space Partition Trees. What I'd suggest you do is expand on the above applet. Start by improving the renderLine() method. Then, try to do a front to back tree traversal instead of the easy back to front traversal approach taken in this tutorial. Anyway, I guess you get the picture: Trees are wonderful data structures, and there are TONS of useful algorithms that use them.

    Doing a bit more: This part is added some time after I've initially written this section. Just to show what exactly can be done with VERY minimal effort. You can easily implement lighting! You already have the Z distance of each line, so, all you'll have to do is brighten or darken up the color, and you're done! For example, placing the following lines at the end of renderLine() would do the trick:

double light = (z1 + z2) / 3;
int R = (R=(int)(light*((l[4] & 0xff0000)>>16))) > 0xFF ? 0xFF:R;
int G = (G=(int)(light*((l[4] & 0x00ff00)>>8))) > 0xFF ? 0xFF:G;
int B = (B=(int)(light*(l[4] & 0x0000ff))) > 0xFF ? 0xFF:B;
double_graphics.setColor(new Color(R,G,B));

    This might be an over-simplified approach (and will probably suck too much for anything professional), but for our little applet, it's just perfect! Click here to see this new version. I will not include the sources for this modified version in this document, however, they are available inside the ZIP file linked on top.

Back to Table of Contents


Google Groups Subscribe to SourceCodesWorld - Techies Talk

Free eBook - Interview Questions: Get over 1,000 Interview Questions in an eBook for free when you join JobsAssist. Just click on the button below to join JobsAssist and you will immediately receive the Free eBook with thousands of Interview Questions in an ebook when you join.


Google Search


is a part of Vyom Network.

Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Interview Questions | Jobs, Discussions | Placement Papers | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | Arabic, French, German | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Software Testing | Google Logo Maker | Freshers Jobs

Sitemap | Privacy Policy | Terms and Conditions | Important Websites
Copyright ©2003-2024, All Rights Reserved.
Page URL: /articles/java/java-data-structures/Binary_Space_Partition_Trees.asp

Download Yahoo Messenger | Placement Papers | Free SMS | C Interview Questions | C++ Interview Questions | Quick2Host Review