![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
Part of Java Data Structures Tutorial.
Binary Trees are a very useful and powerful sorting and searching data structures. And since we can sort almost anything, why not sort the world?
Right now, I will stray away from Data Structures, and talk a little about Computer Graphics, and later, show how using some clever data structures, can resolve some complex computer graphics problems.
A very major problem in Computer Graphics is Hidden Surface Removal, or HSR. Think of a wire frame model...In a wire frame model, nobody can argue where's the front and where's the back... it may look many ways...
Now, think of a similar model, only with solid walls.... You automatically realize that now, the order of sides becomes important... (try imagining the "back" side of the model drawn as the front...)
No matter how you look at it, some sides cannot be seen. (some sides are behind other sides) Our mind, sorts it our for us, so that we see it "correctly."
A computer does not have a mind... It can't perceive which side is in front of which... It needs specific algorithms for everything.
There are many such HSR algorithms... One like Painter's Algorithm go trough every side, and compares it's coordinates with every other side in order to determine which one is to be draw first. All this comparing, can get quite complex and computationally expensive. Once everything is determined, you just write the farthest stuff first, and overwrite it with the closest. There also is a very popular Z-Buffering Algorithm which is a little easier to think of, but still pretty complex and can be computationally intensive. There is also Ray Tracing, which is relatively simple, but VERY computationally intensive... People have simplified it a lot by turning it into Ray Casting, the type of rendering used in Wolfestain 3D by id Software. That one, just shoots a ray (or sometimes 2 rays) across a tiled map, to determine if that tiled map has something there, if there is, it renders, it, if not, then continues with the ray... This can be very efficient, and fast, as demonstrated by Wolfenstain 3D running on my 80x286. Unfortunately, Ray Casting does not produce a "cool" looking world; most people, now a days, want to see something more than just a "blocky" world (everything in the world is made out of equal sized blocks).
To the rescue come the cool new graphics accelerators, (most of) which have Z-Buffering built in. They make the job a lot easier, and a lot faster. Eventually, when hardware becomes very advanced, nobody will even care about HSR. But at the moment, Z-Buffering hardware is only good for *a little* Z-Buffering, not a whole lot...
I mean, you would not dump dozens of thousands of polygons onto a hardware accelerator, and expect it to perform well.... you need some "higher" algorithms to remove hidden surfaces, and that's where Binary Space Partition, or BSP, comes into play.
Binary Space Partition Trees, are regular Binary Search Trees, only they sort and search space (not outer space, just virtual space). If you've read the Java Data Structures Tutorial from the beginning, you've already come across Binary Search Trees, only those were used to sort integers. The concept is almost exactly the same, only this time, instead of comparing integers, you're comparing lines or polygons. (with some *extra* partitioning. ;-)
It is important that you *understand* the structure, that way, you'll be able to use it
almost anywhere, & because I'd like to keep this explanation as simple as possible,
I'll limit the whole discussion to 2D. The same exact concepts are used in 3D, and
if you understand it in 2D, you should not have any problems with 3D (besides some weirdo
3D math of course...)
Ok, back to the ground. BSP trees are regular trees. The tree as a whole
represents all space (virtual one of course), and it's leaves (or children), represent
convex subspaces. Each node of the tree, stores information about the
"partitioning" (dividing) plane (or a line).
Now, consider a simple situation. A "viewer" is in 1 out of 2 convex rooms, in order for them to be able to draw everything correctly, they'll have to draw the other room first, then, draw the room they're in (overwriting some parts that have already been draw) (but that can be avoided with clever clipping) (or walking the BSP tree in another direction....)
So, you draw other convex space, then your own. And that's exactly what this whole BSP concept is doing. The space is sorted in a way, so that it's very easy for you to determine what is that "other" space to draw first, and what that space which should be draw last... to make everything look right.
I think I've made it look more complicated than it really is... sorry. If it helps, you can try reading the BSPFAQ available almost everywhere (and at http://www.geocities.com/SiliconValley/Way/7650 ) The BSPFAQ is not much clearer in their explanation, but at least, there, you're getting everything in proper terms... (besides, this is a Java Data Structures Tutorial, not a BSP Tree tutorial... so, least get back to Java programming...)
(a suggestion: To understand BSP Trees, there is no better way than to practice with them, go over the source, do a simulation on paper, try different combinations... It's not easy if you don't understand it at first, but once you get the concept, it will seem crystal clear.)
The first, and most important thing we need, is a point. Everything is useless in computer graphics, if you don't have the basic building blocks. So, lets write a point class.
/*
* @(#)pPoint2D.java Dec 30, 1997
*
* Copyright (c) 1997, Particle
*
* Sale of this "Software" is prohibited! Only FREE
* distribution is alowed.
*
* -- Particle --
*/
/**
* A pPoint2D
class is a very basic 2D point.
*
* It alows users to set and get values of a 2D point.
*
* @version 1.0 12/30/1997
* @author Particle
*/
public class pPoint2D{
/**
* A 2 element array, representing the X
* and Y coordinates.
*/
public double [] v = null;
/**
* Constructs a new pPoint2D.
*/
public pPoint2D(){
v = new double[2];
}
/**
* Constructs a new pPoint2D
object.
*
* @param x The X coordinate value
* @param y The Y coordinate value
*/
public pPoint2D(double x,double y){
v = new double[2];
setx(x);
sety(y);
}
/**
* Constructs a new pPoint2D
object.
*
* @param p A pPoint2D of which to make a copy
*/
public pPoint2D(pPoint2D p){
v = new double[2];
setx(p.getx());
sety(p.gety());
}
/**
* Gets X value of the point.
* @return An X value of the point.
*/
public double getx(){
return v[0];
}
/**
* Get Y value of the point.
* @return A Y value of the point.
*/
public double gety(){
return v[1];
}
/**
* Sets X value of the point.
* @param x An X coordinate value of the point.
*/
public void setx(double x){
v[0] = x;
}
/**
* Sets Y value of the point.
* @param y A Y coordinate value of the point.
*/
public void sety(double y){
v[1] = y;
}
/**
* The toString
method.
* @return a String
represending
* the pPoint2D
*/
public String toString(){
return new String("("+getx()+","+gety()+")");
}
}
As you can see, this is a very basic point class, it has method to get and set the point, a copy constructor, and that's it. Very simple. Some may argue the use of set and get functions for a simple point, where these functions could be an overkill, but, this code is meant to be "optimized" by the compiler, and the "-O" option in "javac" will make all these functions inline, thus, fixing the burden associated with function calls... (hew... after looking at this source for about a minute, I've realized that I can make it better ... will go rewrite it ;-) <well... Ok, I didn't actually go and rewrite it, I've left it as it is... because I am lazy... happy?>
What we need next in our 2D bsp tree sample is a line. The line consists of 2 points, the start and end. And here's a very self explanatory line class:
/*
* @(#)pLine2D.java Dec 31, 1997
*
* Copyright (c) 1997, Particle
*
* Sale of this "Software" is prohibited! Only FREE
* distribution is alowed.
*
* -- Particle --
*/
import pPoint2D;
import pPlane2D;
/**
* A pLine2D
class is a very basic 2D Line.
*
* It alows users to set and get values of a 2D Line.
*
* @version 1.0 12/31/1997
* @author Particle
*/
public class pLine2D{
/**
* A 2 element array of pPoint2D
objects,
* representing the 'start' and 'end' of the line.
*
* @see pPoint2D
*/
public pPoint2D [] v = null;
/**
* Constructs a pLine2D
object.
* @see pPoint2D
*/
public pLine2D(){
v = new pPoint2D[2];
setStart(new pPoint2D());
setEnd(new pPoint2D());
}
/**
* Constructs a pLine2D
object from
* a pLine2D object, (basically a copy constructor).
* @see pPoint2D
* @param l the pLine2d of which to make a copy of.
*/
public pLine2D(pLine2D l){
v = new pPoint2D[2];
setStart(new pPoint2D(l.getStart()));
setEnd(new pPoint2D(l.getEnd()));
}
/**
* Constructs a pLine2D
object from
* 2 pPoint2D objects. (the start pPoint2D
* and an end pPoint2D
* @param a the start of the line
* @param b the end of the line
*/
public pLine2D(pPoint2D a,pPoint2D b){
v = new pPoint2D[2];
setStart(new pPoint2D(a));
setEnd(new pPoint2D(b));
}
/**
* Gets the starting point of the line
*
* @return the starting point.
*/
public pPoint2D getStart(){
return v[0];
}
/**
* Gets the endint point of the line
*
* @return the ending point.
*/
public pPoint2D getEnd(){
return v[1];
}
/**
* Sets the start of the line
*
* @param s the starting point.
*/
public void setStart(pPoint2D s){
v[0] = new pPoint2D(s);
}
/**
* Sets the ending point of the line
*
* @param e the ending point of the line
*/
public void setEnd(pPoint2D e){
v[1] = new pPoint2D(e);
}
/**
* Gets the "plane" which this line is part of. Basically
* gets those "plane" methods for determining whether some
* point (or line) is in front of behind it, and an ability
* to split lines.
*
* @return the plane for that line
*/
public pPlane2D getPlane(){
return new pPlane2D(this);
}
/**
* standard toString()
method.
*
* @return the string representing that object.
*/
public String toString(){
return new String("pLine2D("+getStart()+","+getEnd()+");\n");
}
}
This class is very self explanatory, just read the source. The only "unusual" thing in it is that "getPlane()" method, it's a method to get the "plane" of the line. Of course, there is no plane of a line... but I just named it with reference to 3D. That plane is basically the line equation, (or a vector equation?) that can be used to determine if some point is on the right or left side of the line, or better yet, in front or behind the line.
If we have a line pointing right, then the front is the "up" of the line, and the back is anything that's "down" of the line.
front
-------------->
back
And now, is the best time to present that pPlane2D class...
/*
* @(#)pPlane2D.java Dec 31, 1997
*
* Copyright (c) 1997, Particle
*
* Sale of this "Software" is prohibited! Only FREE
* distribution is alowed.
*
* -- Particle --
*/
import pPoint2D;
import pLine2D;
/**
* A pPlane2D
class is a very basic 2D Plane.
*
* It alows users to set and get values of a 2D Plane,
* do some weird stuff with the plane, like split lines
* wiht it... etc...
*
* @version 1.0 12/31/1997
* @author Particle
*/
public class pPlane2D{
/**
* the Epsilon value to make this plane "thick"
*/
public final static double EPSILON = 0.001;
/**
* The statics to differentiate between front/back/spanning
* "evaluations" of a point...
*/
public final static int SPANNING = 0;
public final static int IN_FRONT = 1;
public final static int IN_BACK = 2;
public final static int COINCIDENT = 3;
/**
* The 2 element array, with first standing for the
* A, second standing for B, and third standing
* for C in the: Ax + By - C = 0
* line equation.
*/
public double [] v = null;
/**
* Constructs a new pPlane2D object
*/
public pPlane2D(){
v = new double[3];
}
/**
* Constructs a new pPlane2D object given a line.
*
* let Y1 stand for first y, let Y2 stand for second y,
* and so on... let FX stand for starting point X, and FY
* stand for starting point Y, and so on...
* than the equation of a line would be:
*
* A = -DY;
* B = DX;
* C = DY * FX - DX * FY;
*
* @param l the line of which to make the pPlane2D.
*/
public pPlane2D(pLine2D l){
v = new double[3];
double dx = (l.getEnd().getx() - l.getStart().getx());
double dy = (l.getEnd().gety() - l.getStart().gety());
A(-dy);
B(dx);
C(dy*l.getStart().getx()-dx*l.getStart().gety());
}
/**
* Constructs a pPlane2D object out of a pPlane2D object,
* (basically a copy constructor)
* @param l the plane to "copy"
*/
public pPlane2D(pPlane2D l){
v = new double[3];
A(l.A());
B(l.B());
C(l.C());
}
/**
* Sets A in the line equation:
* Ax + By - C
*/
public void A(double a){
v[0] = a;
}
/**
* Sets B in the line equation:
* Ax + By - C
*/
public void B(double b){
v[1] = b;
}
/**
* Sets C in the line equation:
* Ax + By - C
*/
public void C(double c){
v[2] = c;
}
/**
* Gets A in the line equation:
* Ax + By - C
*/
public double A(){
return v[0];
}
/**
* Gets B in the line equation:
* Ax + By - C
*/
public double B(){
return v[1];
}
/**
* Gets C in the line equation:
* Ax + By - C
*/
public double C(){
return v[2];
}
/**
* Function to evaluate whether a point (pPoint2D)
* is in "front" or "behind" the plane.
* also makes sure the plane is "thick"
*
* @param p the point to evaluate
* @return a condition, one of the statics like IN_FRONT, etc...
*/
public int eval(pPoint2D p){
double c = A()*p.getx() + B()*p.gety() + C();
if(c > pPlane2D.EPSILON){
return pPlane2D.IN_FRONT;
}else if(c < (-pPlane2D.EPSILON)){
return pPlane2D.IN_BACK;
}else{
return pPlane2D.SPANNING;
}
}
/**
* the function to evaluate a line in terms of this plane
*
* @return one of the "statics" like IN_FRONT, etc...
* @param l the line to evaluate
*/
public int eval(pLine2D l){
int a = eval(l.getStart());
int b = eval(l.getEnd());
if(a == pPlane2D.SPANNING)
if(b == pPlane2D.SPANNING)
return pPlane2D.COINCIDENT;
else return b;
if(b == pPlane2D.SPANNING)
if(a == pPlane2D.SPANNING)
return pPlane2D.COINCIDENT;
else return a;
if((a == pPlane2D.IN_FRONT)&&(b == pPlane2D.IN_BACK))
return SPANNING;
if((a == pPlane2D.IN_BACK)&&(b == pPlane2D.IN_FRONT))
return SPANNING;
return a; /* all on 1 side */
}
/**
* function to split a line with this plane.
*
* the "front" piece of the split becomes the
* first element in the returning array, the
* "back" piece of the split, becomes the
* second.
*
* there is an assumption, that "positive eval()"
* is front, and negative eval() is in back.
* @return a 2 element array, with front and back pieces of the line
* @param l the line to split.
* @see pLine2D
* @see pPoint2D
*/
public pLine2D [] split(pLine2D l){
pPlane2D p = new pPlane2D(l);
pLine2D [] q = new pLine2D[2];
double cross_x = 0, cross_y = 0;
double divider = A() * p.B() - B() * p.A();
if(divider == 0){ /* should never happen */
if(p.A() == 0){
cross_x = l.getStart().getx();
}
if(p.B() == 0){
cross_y = l.getStart().gety();
}
if(A() == 0){
cross_y = -B();
}
if(B() == 0){
cross_x = C();
}
}else{
cross_x = (-C()*p.B() + B()*p.C())/divider;
cross_y = (-A()*p.C() + C()*p.A())/divider;
}
int p1 = eval(l.getStart());
int p2 = eval(l.getEnd());
q[0] = new pLine2D(l);
q[1] = new pLine2D(l);
if((p1==pPlane2D.IN_BACK)&&(p2==pPlane2D.IN_FRONT)){
q[0].setStart(new pPoint2D(cross_x,cross_y));
q[0].setEnd(new pPoint2D(l.getEnd()));
q[1].setStart(new pPoint2D(l.getStart()));
q[1].setEnd(new pPoint2D(cross_x,cross_y));
}else if((p1==pPlane2D.IN_FRONT)&&(p2==pPlane2D.IN_BACK)){
q[0].setStart(new pPoint2D(l.getStart()));
q[0].setEnd(new pPoint2D(cross_x,cross_y));
q[1].setStart(new pPoint2D(cross_x,cross_y));
q[1].setEnd(new pPoint2D(l.getEnd()));
}else{
return null; /* trying to split a spanning line */
}
return q;
}
/**
* the standard toString
method
*/
public String toString(){
return new String("pPlane2D("+A()+","+B()+","+C()+");\n");
}
}
The plane is basically a class representing a line equation. The line equation "Ax + By = C". This class uses this equation to evaluate points in relation to that plane. There is an "eval()" function, which accepts a point, and the function returns whether the point is in front, back, or spanning of this line. There is also a similar function that accepts a line. Both of these functions use the EPSILON value to make the "plane" appear "think"... if the plane is "thin," we can get into into situations of splitting a line where it's not really needed and is not visually relevant... (what does 1/100 of a pixel do? nothing.)
The most important method in this class is the method to split the line into 2, and return the line which is in front and back of the plane. The "split()" function accepts a line as it's argument, and works by comparing the start and end of the line, in relation to the plane, (since this method should not be called if the split is not necessary, there is very minimal error checking to make sure we're splitting something that needs to be split.) It then finds the "crossing point" of the plane and the line, and sets the "front" and "back" line's coordinates, and returns and array of 2, where the first represents the "front" line and the second value in the array represents the "back" of the line.
This ability to split things, is the whole key of BSP engines, in 2D it's quite simple, in 3D, it involves a bit more math, but the idea still remains the same.
Now, since this is a Java BSP Tree Tutorial, lets write BSP classes.
First, as with a regular binary tree, we need a Node. The node should contain a partition plane, (which is pPlane2D object), and a list of lines which are spanning the plane of this node. There are many implementations of this where the lines don't necessarily span the partition plane of the node, and there are certain advantages and disadvantages to it... but this is a "simplest" tutorial, so... Anyway, where's the node class for the BSP Tree.
/*
* @(#)pBSPNode.java Dec 31, 1997
*
* Copyright (c) 1997, Particle
*
* Sale of this "Software" is prohibited! Only FREE
* distribution is alowed.
*
* -- Particle --
*/
import pPlane2D;
import pQueue;
/**
* A pBSPNode
class is a very basic Node with 2 children.
*
* This is basically a plain vanilla node, only it has 2 children, making
* it ideal for a binary tree.
*
* The data on the node is a pQueue
object, (kinda like a list)
* of stuff... and a partition plane. (a pPlane2D
object)
*
* @version 1.0 12/31/1997
* @author Particle
*/
public class pBSPNode{
/**
* the partion plane, (hey, it IS a BSP node...)
*/
public pPlane2D partition = null;
/**
* a queue of "lines" that are on the partition plane. This can also
* be a "list" (instead of a queue), I just like the queue better, and
* besides, that's how I return the "sorted" ones, so, why not use it...
*
* although, a simple List approach may be a bit faster...
*/
public pQueue lines = null;
/**
* the "next" node pointing to the "front" child
*/
public pBSPNode front = null;
/**
* the "next" node pointing to the "back" child
*/
public pBSPNode back = null;
/**
* Constructs a pBSPNode object, with default settings.
*/
public pBSPNode(){
partition = new pPlane2D();
lines = new pQueue();
}
/**
* a method to get the "back" child node...
* @return the back child
*/
public pBSPNode getback(){
return back;
}
/**
* a method to get the "front" child node...
* @return the front child
*/
public pBSPNode getfront(){
return front;
}
/**
* a method to set the back child node to a new value
* @param l the node to set "back" child to...
*/
public void setback(pBSPNode l){
back = l;
}
/**
* a method to set the front child node to a new value
* @param r the node to set "front" child to...
*/
public void setfront(pBSPNode r){
front = r;
}
/**
* a standard toString
method
*
* Note that this could easily be modified to "return" the whole
* tree structure...
*
* @return just the data in this node.
*/
public String toString(){
return new String(""+partition+"/"+lines);
}
}
As you can see, it's just like a regular Binary Tree node, with 2 children, one pointing to the "front" and the other pointing to the "back" children. (for an explanation of Binary Tree Node, check out the Java Data Structures Tutorial from the start)
Now, the heart of the whole thing, the BSP Tree class!
/* * @(#)pBSPTree.java Dec 31, 1997 * * Copyright (c) 1997, Particle * * Sale of this "Software" is prohibited! Only FREE * distribution is alowed. * * -- Particle -- */ import pQueue; import pBSPNode; import pLine2D; import pPlane2D; /** * A
method, returns the whole * tree in apBSPTree
class is a Binary Space Partition Tree! ** This method mostly works with Queues, inserting entire structures, * and sorting and returning entire structures as well... * * @version 1.0 12/31/1997 * @author Particle */ public class pBSPTree{ /** * The root of the TREE. (this node can take you anywhere.) */ public pBSPNode root; /** * the list of sorted lines, it's here, to speed things up, * and eliminate it's passing as a parameter to the sorting * function */ pQueue list; /** * the current eye position, it's passed to the sorting * function, which later sets this variable, so that * the recursive method won't have to pass it as a * parameter when it's sorting... */ pPoint2D eye; /** * Constructs a
pBSPTree
object, and initialized root to *null
*/ public pBSPTree() { root = null; } /** * a recurcive (& private) function to build a bsp * tree. Users should be calling a "friendly" function * below... * * @param tree the current node of the tree. * @param lines a pQueue of lines to examine. */ void pBuildBSPTree(pBSPNode tree, pQueue lines) { pLine2D current_line = (pLine2D)lines.remove(); tree.partition = current_line.getPlane(); tree.lines.insert(current_line); pQueue front_list = new pQueue(); pQueue back_list = new pQueue(); pLine2D line = null; while(!lines.empty()){ line = (pLine2D)lines.remove(); int result = tree.partition.eval(line); if(result==pPlane2D.IN_FRONT){ /* in front */ front_list.insert(line); }else if(result==pPlane2D.IN_BACK){ /* in back */ back_list.insert(line); }else if(result==pPlane2D.SPANNING){ /* spanning */ pLine2D [] split_line = null; split_line = tree.partition.split(line); if(split_line != null){ front_list.insert(split_line[0]); back_list.insert(split_line[1]); }else{ /* error here, (TODO: throw some Exception) */ } }else if(result==pPlane2D.COINCIDENT){ tree.lines.insert(line); } } if(!front_list.empty()){ tree.front = new pBSPNode(); pBuildBSPTree(tree.front,front_list); } if(!back_list.empty()){ tree.back = new pBSPNode(); pBuildBSPTree(tree.back,back_list); } } /** * a 'friendly' function for the user to construct a * BSP Tree. ** The pQueue parameter should have ALL the lines * which are to be inserted, if something is on the tree * previous to that, it will be overwritten by this new * insertion... * * @param lines a pQueue of lines to insert into the BSP Tree. * @see pQueue */ public void pBuildBSPTree(pQueue lines) { root = new pBSPNode(); pBuildBSPTree(root,lines); } /** * a function to get the sorted lines in relation * to the
this.eye
, the resulting sorted * list is stored inthis.list
** The user should call a "user friendly" function below. * * @param tree the currecnt pBSPNode in recursion. */ void pGetSortedLines(pBSPNode tree) { pLine2D tmp; if(tree == null) return; /* check for end */ int result = tree.partition.eval(eye); if(result == pPlane2D.IN_FRONT){ pGetSortedLines(tree.back); for(int i = 0;i
toString String
object. * * @return the whole tree in a String object. */ public String toString(){ list = new pQueue(); String s = new String(); if(root == null) return null; intrav(root); while(!list.empty()) s += (String)list.remove(); return (s+="\n"); } /** * a method used by the "toString" to get the list of * lines in an intrav order. * * @param p the current node in recursion */ public void intrav(pBSPNode p){ if(p == null) return; intrav(p.getback()); for(int i = 0;i < p.lines.number();i++) list.insert(p.lines.peek(i)); intrav(p.getfront()); } }
This class heavily relies of the pQueue.java class, which I've presented in the Java Data Structures Tutorial, and will give it again in this tutorial. Now thinking about it, it would actually make more sense to use the "Vector" class provided by the JDK. The way Vector organizes it's data, would actually make it faster than Queue, (even though it "doesn't" grow dynamically, it's "arraycopy()" would be insignificant to the insertion and removal of nodes.)
Anyway, back to the subject. The 2 most important methods in this class are definitely pBuildBSPTree, which accepts Queue of lines, and pGetSortedLines, which traverses the tree, and returns a Queue of sorted lines. Now, you understand why I needed to use the Queue, or some data structure which keeps the order of things on it.
The pBuildBSPTree, recursively builds a bsp tree, given a Queue of lines. It takes 1 line of the Queue, and makes it it's "current" line, finds it's "partition plane" and sticks that partition plane into that "current" node. Then, it separates the remaining lines on the Queue, into 2 piles, with relation to the partition plane. If some line somehow ends up being on both sides, it is split. It then recursively goes through those 2 piles... and that's the whole BSP...
There are methods to "optimize" BSP Trees, and smartly choosing the partition plane (thus choosing that "line" of the Queue), can be a real significant optimization. The demo provided, just picks the first one of the Queue, but some algorithms actually go through the Queue, searching for the best one to pick... The "best" has a very loose definition, since it all depends on what you're doing exactly... usually, you'd like to have a tree with as little "depth" as possible, so, generally, you should try to avoid choosing planes that would cause lots of splits.
The other most important method is pGetSortedLines, it returns a Queue, containing all the lines, but sorted in relation to the "eye" point, and in relation to each other.
Once we have the list, we'd like to be able to draw the "farthest" lines, and then overdraw that with the "closer" lines, thus, giving us a pretty good image. This is a "derivative" of the Painter's algorithm, and it's used so much, that a lot of the people just call it "Painter's algorithm" (without even thinking that true Painter's algorithm also refers to tons of math as well... ) Because we'd like to be able to just "draw" from back to front, we "walk" the tree in a special way to generate this special sort.
Having the "eye" point, we evaluate it in relation to the partition plane of the root node, if the eye is in "front" of the partition plane, we then recursively draw the "back" child of that node, then draw the "lines" on that partition plane, and then draw the front. If however the eye is in "back" of the partition plane, we draw the "front" child of the node (recursively), then draw the lines which span that node's partition plane, and then draw the "back" child of that node. < Ouch, even I am getting confused after reading this...>
If on the other hand, we'd like to be able to draw from "front to back", (using some clever clipping technique) (with 0 overdraw), we would "walk" the tree a little differently. Having the "eye" in the "front" of the partition plane, we would first recursively draw the front, then lines spanning partition plane, and then the back... Else if eye was in "back" of the partition plane, we'd first draw the "back", then the lines spanning partition plane, and then the "front". This approach is a little bit harder to accomplish because of the complex clipping involved, but it's generally faster, because there is no overdraw, and you don't even up drawing everything, (since a lot of the things will get clipped out.)
Some notes on optimizing all this: BSP tree's can also be used to do very quick clipping, using bounding boxes; if you determine that the "front" child's bounding box is not even visible, you can avoid that "front" child altogether, (and thus avoiding tons of it's children, which you'd do recursively ...) <as far as I know, that's the technique used in Quake to speed things up.>
The 2 most important functions talked about here, are not "very friendly" to the user, so, I've created a user friendly functions, which have nothing to do with the internals of the Tree. (the user doesn't have to know about pBSPNode class to use the BSP)
Now that you know how this whole thing works, how do you use it?... good question.
I've written a couple of simple application, and 2 applets that use all this, to display a small and badly designed "world" <if it can be called that...>
Here's the general class that's using all of the above to display (anywhere), this badly designed world...
/*
* @(#)dog.java Jan 1, 1998
*
* Copyright (c) 1998, Particle
*
* Sale of this "Software" is prohibited! Only FREE
* distribution is alowed.
*
*
* -- Particle --
*/
import java.io.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.BufferedImage;
import java.lang.Double;
import pQueue;
import pPoint2D;
import pLine2D;
import pPlane2D;
import pBSPTree;
/**
* A dog
class simply uses the pBSPTree
* class and renders a bunch of lines in a way, giving the appearance
* of a 3D room. (when in reality it's just 2D)
*
* This class must accept a pQueue
object containing
* lines, which it later inserts into the BSP, which sorts them,
* so that this dog
object can render them.
*
* I call it "Dog 3D"!
*
* @version 1.0 1/2/1998
* @author Particle
*/
public class dog extends Frame implements WindowListener,KeyListener{
/**
* the BSP tree object
*/
public pBSPTree myBSP = new pBSPTree();
/**
* a queue used to insert stuff onto tree, and
* retrieve sorted lines
*/
public pQueue myList = new pQueue();
/**
* the initial eye point, (or the position of a "player")
*/
public pPoint2D eye = new pPoint2D(220,220);
/**
* the eye point angle... (or the "direction" the "player" is facing)
*/
public double pangle = 0;
/**
* the drawable area width
*/
int screen_width = 320;
/**
* the drawable area height
*/
int screen_height = 240;
/**
* a buffered image, used for double buffering.
*/
BufferedImage double_buffer = null;
/**
* a graphics contect for the double buffer,
* (I think I am getting lazy... )
* this approach is VERY slow
*/
Graphics double_graphics = null;
/**
* method to setup the double buffer stuff...
*/
public void setup()
{
double_buffer = new BufferedImage(screen_width,
screen_height,BufferedImage.TYPE_INT_ARGB);
double_graphics = double_buffer.createGraphics();
}
/**
* Constructs and initializes some stuff, accepts a pQueue
* of lines, and inserts them onto the BSP Tree...
*/
public dog(pQueue lines)
{
super("Dog 3D");
setup();
setSize(screen_width+100,screen_height+100);
myList = lines;
myBSP.pBuildBSPTree(myList);
addWindowListener(this);
addKeyListener(this);
setResizable(false); /* can't resize window */
show();
repaint();
}
/**
* given a line, and a graphics context,
* (and a bunch of class variables), it transforms,
* rotates the line coordinates, and draws a
* 3D type version of the line onto the graphics
* context.
*
* NOTE: VERY VERY Buggy! (Needs LOTS of improvement)
*/
void _mydrawPoly(Graphics g,pLine2D tmp){
double x1=tmp.getEnd().getx();
double y1=tmp.getEnd().gety();
double x2=tmp.getStart().getx();
double y2=tmp.getStart().gety();
double pCos = Math.cos(pangle);
double pSin = Math.sin(pangle);
int [] x = new int[4];
int [] y = new int[4];
double pD=-pSin*eye.getx()+pCos*eye.gety();
double pDp=pCos*eye.getx()+pSin*eye.gety();
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)){
return;
}
rx1=pCos*y1-pSin*x1-pD;
rx2=pCos*y2-pSin*x2-pD;
double pTan = 0;
if((x2-x1) == 0){
pTan = Double.MAX_VALUE;
}else{
pTan = (y2-y1)/(x2-x1);
}
pTan = (pTan-Math.tan(pangle))/(1+(pTan*Math.tan(pangle)));
if(rz1 < 1){
rx1+=(1-rz1)*pTan;
rz1=1;
}
if(rz2 < 1){
rx2+=(1-rz2)*pTan;
rz2=1;
}
double z1 = screen_width/2/rz1;
double z2 = screen_width/2/rz2;
//get the pespective X coordinates on the screen...
Screen_x1=(int)(screen_width/2-rx1*z1);
Screen_x2=(int)(screen_width/2-rx2*z2);
//cliping...(can the wall be seen?)
if(Screen_x1>screen_width) return; //can not be seen...
if(Screen_x2<0) return;
//set the height...
int ph=40;
int wt=88;
int wb=-40;
Screen_y1=(double)screen_height/2-(double)wt*z1;
Screen_y4=(double)screen_height/2-(double)wb*z1;
Screen_y2=(double)screen_height/2-(double)wt*z2;
Screen_y3=(double)screen_height/2-(double)wb*z2;
if(Screen_x1<0){
Screen_y1+=(0-Screen_x1)*(Screen_y2-Screen_y1)/
(Screen_x2-Screen_x1);
Screen_y4+=(0-Screen_x1)*(Screen_y3-Screen_y4)/
(Screen_x2-Screen_x1);
Screen_x1=0;
}
if(Screen_x2>(screen_width)){
Screen_y2-=(Screen_x2-screen_width)*
(Screen_y2-Screen_y1)/
(Screen_x2-Screen_x1);
Screen_y3-=(Screen_x2-screen_width)*
(Screen_y3-Screen_y4)/
(Screen_x2-Screen_x1);
Screen_x2=screen_width;
}
if((Screen_x2-Screen_x1)==0) return;
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);
g.fillPolygon(x,y,4);
}
/**
* the method to get the sorted lines out of a BSP Tree, and
* call a function to render those lines in the order recieved
* from the BSP Tree...
*/
void pRender(Graphics g){
int i = 0;
pQueue q = myBSP.pGetSortedLines(eye);
g.setColor(Color.black);
g.fillRect(0,0,screen_width,screen_height);
pLine2D tmp;
while(!q.empty()){
i++;
tmp = (pLine2D)q.remove();
/* back face removal */
if(tmp.getPlane().eval(eye) == pPlane2D.IN_BACK)
continue;
/* just pick a unique color for this "line" */
g.setColor(new Color(i*1024+0x555555));
_mydrawPoly(g,tmp);
}
}
/**
* overriding standard "paint" method
*/
public void paint(Graphics g){
pRender(double_graphics);
g.drawImage(double_buffer,50,50,this);
}
/**
* overriding standard "update" method
*/
public void update(Graphics g){
paint(g);
}
/**
* catch window closing, and dispose of it.
*/
public void windowClosing(WindowEvent e)
{
e.getWindow().dispose();
System.exit(0);
}
public void windowOpened(WindowEvent e){}
public void windowClosed(WindowEvent e){}
public void windowIconified(WindowEvent e){}
public void windowDeiconified(WindowEvent e){}
public void windowActivated(WindowEvent e){}
public void windowDeactivated(WindowEvent e){}
public void keyTyped(KeyEvent e){}
/**
* get some primitive user input
* (the arrow keys)
*/
public void keyPressed(KeyEvent e)
{
if(e.getKeyCode() == KeyEvent.VK_UP){
eye.v[0] += Math.cos(pangle)*7;
eye.v[1] += Math.sin(pangle)*7;
}else if(e.getKeyCode() == KeyEvent.VK_DOWN){
eye.v[0] -= Math.cos(pangle)*7;
eye.v[1] -= Math.sin(pangle)*7;
}else if(e.getKeyCode() == KeyEvent.VK_LEFT){
pangle += 2*Math.PI/64;
}else if(e.getKeyCode() == KeyEvent.VK_RIGHT){
pangle -= 2*Math.PI/64;
}
repaint();
}
public void keyReleased(KeyEvent e){}
}
[dog.java]
This class assumes that the data has already been loaded, inserts it into the tree using the pBuildBSPTree method, and later, in a loop, gets the sorted lines, and draws them so that they appear "3D"... The class also handles user input... Requires the JDK 1.1 (because of it's JDK 1.1 event model)
Now, here's the application that loads the data, and initializes "dog" class, and makes... it's basically the "starter" class...
/*
* @(#)dog3dapplication.java Jan 1, 1998
*
* Copyright (c) 1998, Particle
*
* Sale of this "Software" is prohibited! Only FREE
* distribution is alowed.
*
*
* -- Particle --
*/
import java.io.*;
import pQueue;
import pLine2D;
import pPoint2D;
import dog;
/**
* A dog3dapplication
* is the application to start dog
.
*
* It basically gets the lines from the file, and
* passes them as a parameter to dog
*
* @version 1.0 1/2/1998
* @author Particle
*/
class dog3dapplication{
/**
* the lines queue.
*/
public pQueue myList = null;
/**
* function to load lines from a local file
*/
boolean load_data(){
FileReader fr = null;
pLine2D tmp = null;
int current;
String fileName = new String("testmap.txt");
try{
fr = new FileReader(fileName);
}catch(Exception e){
System.out.println(e);
}
StreamTokenizer st = new StreamTokenizer(fr);
st.eolIsSignificant(true);
st.slashStarComments(true);
st.ordinaryChar('\'');
try{
for(st.nextToken(),tmp = new pLine2D(),current=1;
st.ttype != StreamTokenizer.TT_EOF;
st.nextToken(),current++){
if(st.ttype == StreamTokenizer.TT_EOL){
if(tmp != null)
myList.insert(tmp);
tmp = new pLine2D();
current=0;
}else{
if(current == 1)
System.out.println("getting Line: "+st.nval);
else if(current == 2)
tmp.v[0].v[0] = st.nval;
else if(current == 3)
tmp.v[0].v[1] = st.nval;
else if(current == 4)
tmp.v[1].v[0] = st.nval;
else if(current == 5)
tmp.v[1].v[1] = st.nval;
}
}
}catch(IOException e){
return false;
}
return true;
}
/**
* constructs a dog2dapplication object, loads data, and creates
* a new dog
object.
*/
public dog3dapplication(){
myList = new pQueue();
load_data();
dog theapp = new dog(myList);
}
/**
* the static main method, (for calling it from command line)
*/
public static void main(String[] args){
dog3dapplication myapp = new dog3dapplication();
}
}
This class just loads the "testmap.txt" file (the map that's displayed), and creates a "dog" object to do the rest... Any applet or app can use that "dog" class, since it's quite "usable"... (I've even originally written an applet to use that as well, but realized that it's not compatible with Netscape browser, and will only with with Internet Explorer 4.
Here's an applet version of the "viewer" that uses the BSP tree... this version is NOT deprecated as of JDK 1.2, but is also not compatible with most browsers.
/*
* @(#)dog3dapplet.java Jan 2, 1998
*
* Copyright (c) 1998, Particle
*
* Sale of this "Software" is prohibited! Only FREE
* distribution is alowed.
*
*
* -- Particle --
*/
import java.awt.*;
import java.awt.event.*;
import java.awt.image.BufferedImage;
import java.lang.Double;
import pPlane2D;
import pBSPTree;
import java.io.*;
import java.applet.*;
import java.net.*;
import pQueue;
import pLine2D;
import pPoint2D;
/**
* A dog3dapplet
* is the applet to start dog
.
*
* It basically gets the lines from the file, and
* passes them as a parameter to dog
*
* @version 1.0 1/2/1998
* @author Particle
*/
public class dog3dapplet extends Applet implements KeyListener{
/**
* the BSP tree object
*/
public pBSPTree myBSP = new pBSPTree();
/**
* a queue used to insert stuff onto tree, and
* retrieve sorted lines
*/
public pQueue myList = new pQueue();
/**
* the initial eye point, (or the position of a "player")
*/
public pPoint2D eye = new pPoint2D(220,220);
/**
* the eye point angle... (or the "direction" the "player" is facing)
*/
public double pangle = 0;
/**
* the drawable area width
*/
int screen_width = 320;
/**
* the drawable area height
*/
int screen_height = 240;
/**
* a buffered image, used for double buffering.
*/
Image double_buffer = null;
/**
* a graphics contect for the double buffer,
* (I think I am getting lazy... )
* this approach is VERY slow
*/
Graphics double_graphics = null;
public boolean load_data(){
pLine2D tmp = null;
int current;
StreamTokenizer st = null;
try{
Reader r = new InputStreamReader(
(new URL(getDocumentBase(),"testmap.txt")).openStream());
st = new StreamTokenizer(r);
}catch(java.net.MalformedURLException e){
System.out.println(e);
e.printStackTrace();
}catch(IOException f){
System.out.println(f);
}
st.eolIsSignificant(true);
st.slashStarComments(true);
st.ordinaryChar('\'');
try{
for(st.nextToken(),tmp = new pLine2D(),current=1;
st.ttype != StreamTokenizer.TT_EOF;
st.nextToken(),current++){
if(st.ttype == StreamTokenizer.TT_EOL){
if(tmp != null)
myList.insert(tmp);
tmp = new pLine2D();
current=0;
}else{
if(current == 1)
System.out.println("getting Line: "+st.nval);
else if(current == 2)
tmp.v[0].v[0] = st.nval;
else if(current == 3)
tmp.v[0].v[1] = st.nval;
else if(current == 4)
tmp.v[1].v[0] = st.nval;
else if(current == 5)
tmp.v[1].v[1] = st.nval;
}
}
}catch(IOException e){
return false;
}
return true;
}
/**
* method to setup the double buffer stuff...
*/
public void setup()
{
double_buffer = createImage(screen_width,screen_height);
double_graphics = double_buffer.getGraphics();
}
/**
* given a line, and a graphics context,
* (and a bunch of class variables), it transforms,
* rotates the line coordinates, and draws a
* 3D type version of the line onto the graphics
* context.
*
* NOTE: VERY VERY Buggy! (Needs LOTS of improvement)
*/
void _mydrawPoly(Graphics g,pLine2D tmp){
double x1=tmp.getEnd().getx();
double y1=tmp.getEnd().gety();
double x2=tmp.getStart().getx();
double y2=tmp.getStart().gety();
double pCos = Math.cos(pangle);
double pSin = Math.sin(pangle);
int [] x = new int[4];
int [] y = new int[4];
double pD=-pSin*eye.getx()+pCos*eye.gety();
double pDp=pCos*eye.getx()+pSin*eye.gety();
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)){
return;
}
rx1=pCos*y1-pSin*x1-pD;
rx2=pCos*y2-pSin*x2-pD;
double pTan = 0;
if((x2-x1) == 0){
pTan = Double.MAX_VALUE;
}else{
pTan = (y2-y1)/(x2-x1);
}
pTan = (pTan-Math.tan(pangle))/(1+(pTan*Math.tan(pangle)));
if(rz1 < 1){
rx1+=(1-rz1)*pTan;
rz1=1;
}
if(rz2 < 1){
rx2+=(1-rz2)*pTan;
rz2=1;
}
double z1 = screen_width/2/rz1;
double z2 = screen_width/2/rz2;
//get the pespective X coordinates on the screen...
Screen_x1=(int)(screen_width/2-rx1*z1);
Screen_x2=(int)(screen_width/2-rx2*z2);
//cliping...(can the wall be seen?)
if(Screen_x1>screen_width) return; //can not be seen...
if(Screen_x2<0) return;
//set the height...
int ph=40;
int wt=88;
int wb=-40;
Screen_y1=(double)screen_height/2-(double)wt*z1;
Screen_y4=(double)screen_height/2-(double)wb*z1;
Screen_y2=(double)screen_height/2-(double)wt*z2;
Screen_y3=(double)screen_height/2-(double)wb*z2;
if(Screen_x1<0){
Screen_y1+=(0-Screen_x1)*(Screen_y2-Screen_y1)/
(Screen_x2-Screen_x1);
Screen_y4+=(0-Screen_x1)*(Screen_y3-Screen_y4)/
(Screen_x2-Screen_x1);
Screen_x1=0;
}
if(Screen_x2>(screen_width)){
Screen_y2-=(Screen_x2-screen_width)*
(Screen_y2-Screen_y1)/
(Screen_x2-Screen_x1);
Screen_y3-=(Screen_x2-screen_width)*
(Screen_y3-Screen_y4)/
(Screen_x2-Screen_x1);
Screen_x2=screen_width;
}
if((Screen_x2-Screen_x1)==0) return;
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);
g.fillPolygon(x,y,4);
}
/**
* the method to get the sorted lines out of a BSP Tree, and
* call a function to render those lines in the order recieved
* from the BSP Tree...
*/
void pRender(Graphics g){
int i = 0;
pQueue q = myBSP.pGetSortedLines(eye);
g.setColor(Color.black);
g.fillRect(0,0,screen_width,screen_height);
pLine2D tmp;
while(!q.empty()){
i++;
tmp = (pLine2D)q.remove();
/* back face removal */
if(tmp.getPlane().eval(eye) == pPlane2D.IN_BACK)
continue;
/* just pick a unique color for this "line" */
g.setColor(new Color(i*1024+0x555555));
_mydrawPoly(g,tmp);
}
}
/**
* overriding standard "paint" method
*/
public void paint(Graphics g){
pRender(double_graphics);
g.drawImage(double_buffer,0,0,this);
}
/**
* overriding standard "update" method
*/
public void update(Graphics g){
paint(g);
}
public void keyTyped(KeyEvent e){}
/**
* get some primitive user input
* (the arrow keys)
*/
public void keyPressed(KeyEvent e)
{
if(e.getKeyCode() == KeyEvent.VK_UP){
eye.v[0] += Math.cos(pangle)*7;
eye.v[1] += Math.sin(pangle)*7;
}else if(e.getKeyCode() == KeyEvent.VK_DOWN){
eye.v[0] -= Math.cos(pangle)*7;
eye.v[1] -= Math.sin(pangle)*7;
}else if(e.getKeyCode() == KeyEvent.VK_LEFT){
pangle += 2*Math.PI/64;
}else if(e.getKeyCode() == KeyEvent.VK_RIGHT){
pangle -= 2*Math.PI/64;
}
repaint();
}
public void keyReleased(KeyEvent e){}
/**
* the init method.... initializes and starts some stuff.
* also calls the method to get input
*/
public void init(){
myList = new pQueue();
load_data();
setup();
setSize(screen_width,screen_height);
myBSP.pBuildBSPTree(myList);
addKeyListener(this);
repaint();
}
/**
* some weird run method which we don't even need
*/
public void run(){}
}
And who would I be if I didn't provide the compatible version... This one is VERY portable (as far as I know, it runs on anything that has Java support; tested on Internet Explorer 3 & 4, and Netscape 3 & 4.) It is however deprecated, even as of JDK 1.1... Anyway, here it is:
/*
* @(#)dog3dapp.java Jan 3, 1998
*
* Copyright (c) 1998, Particle
*
* Sale of this "Software" is prohibited! Only FREE
* distribution is alowed.
*
*
* -- Particle --
*/
import java.awt.*;
import java.awt.event.*;
import java.lang.Double;
import pPlane2D;
import pBSPTree;
import java.io.*;
import java.applet.*;
import java.net.*;
import pQueue;
import pLine2D;
import pPoint2D;
/**
* A dog3dapp
* is the applet to start dog
.
*
* It basically gets the lines from the file, and
* passes them as a parameter to dog
*
* This is the DEPRECATED version, because it uses OLD
* stuff (to be compatible with earlier browsers &
* Netscape.) (come to think of it, I think it's JDK 1.0
* compatible...)
*
* @version 1.1 1/3/1998
* @author Particle
*/
public class dog3dapp extends Applet{
/**
* the BSP tree object
*/
public pBSPTree myBSP = new pBSPTree();
/**
* a queue used to insert stuff onto tree, and
* retrieve sorted lines
*/
public pQueue myList = new pQueue();
/**
* the initial eye point, (or the position of a "player")
*/
public pPoint2D eye = new pPoint2D(220,220);
/**
* the eye point angle... (or the "direction" the "player" is facing)
*/
public double pangle = 0;
/**
* the drawable area width
*/
int screen_width = 320;
/**
* the drawable area height
*/
int screen_height = 240;
/**
* a buffered image, used for double buffering.
*/
Image double_buffer = null;
/**
* a graphics contect for the double buffer,
* (I think I am getting lazy... )
* this approach is VERY slow
*/
Graphics double_graphics = null;
public boolean load_data(){
pLine2D tmp = null;
int current;
StreamTokenizer st = null;
try{
st = new StreamTokenizer(
(new URL(getDocumentBase(),
"testmap.txt")).openStream());
}catch(java.net.MalformedURLException e){
System.out.println(e);
}catch(IOException f){
System.out.println(f);
}
st.eolIsSignificant(true);
st.slashStarComments(true);
st.ordinaryChar('\'');
try{
for(st.nextToken(),tmp = new pLine2D(),current=1;
st.ttype != StreamTokenizer.TT_EOF;
st.nextToken(),current++){
if(st.ttype == StreamTokenizer.TT_EOL){
if(tmp != null)
myList.insert(tmp);
tmp = new pLine2D();
current=0;
}else{
if(current == 1)
System.out.println("getting Line: "+st.nval);
else if(current == 2)
tmp.v[0].v[0] = st.nval;
else if(current == 3)
tmp.v[0].v[1] = st.nval;
else if(current == 4)
tmp.v[1].v[0] = st.nval;
else if(current == 5)
tmp.v[1].v[1] = st.nval;
}
}
}catch(IOException e){
return false;
}
return true;
}
/**
* method to setup the double buffer stuff...
*/
public void setup()
{
double_buffer = createImage(screen_width,screen_height);
double_graphics = double_buffer.getGraphics();
}
/**
* given a line, and a graphics context,
* (and a bunch of class variables), it transforms,
* rotates the line coordinates, and draws a
* 3D type version of the line onto the graphics
* context.
*
* NOTE: VERY VERY Buggy! (Needs LOTS of improvement)
*/
void _mydrawPoly(Graphics g,pLine2D tmp){
double x1=tmp.getEnd().getx();
double y1=tmp.getEnd().gety();
double x2=tmp.getStart().getx();
double y2=tmp.getStart().gety();
double pCos = Math.cos(pangle);
double pSin = Math.sin(pangle);
int [] x = new int[4];
int [] y = new int[4];
double pD=-pSin*eye.getx()+pCos*eye.gety();
double pDp=pCos*eye.getx()+pSin*eye.gety();
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)){
return;
}
rx1=pCos*y1-pSin*x1-pD;
rx2=pCos*y2-pSin*x2-pD;
double pTan = 0;
if((x2-x1) == 0){
pTan = Double.MAX_VALUE;
}else{
pTan = (y2-y1)/(x2-x1);
}
pTan = (pTan-Math.tan(pangle))/(1+(pTan*Math.tan(pangle)));
if(rz1 < 1){
rx1+=(1-rz1)*pTan;
rz1=1;
}
if(rz2 < 1){
rx2+=(1-rz2)*pTan;
rz2=1;
}
double z1 = screen_width/2/rz1;
double z2 = screen_width/2/rz2;
//get the pespective X coordinates on the screen...
Screen_x1=(int)(screen_width/2-rx1*z1);
Screen_x2=(int)(screen_width/2-rx2*z2);
//cliping...(can the wall be seen?)
if(Screen_x1>screen_width) return; //can not be seen...
if(Screen_x2<0) return;
//set the height...
int ph=40;
int wt=88;
int wb=-40;
Screen_y1=(double)screen_height/2-(double)wt*z1;
Screen_y4=(double)screen_height/2-(double)wb*z1;
Screen_y2=(double)screen_height/2-(double)wt*z2;
Screen_y3=(double)screen_height/2-(double)wb*z2;
if(Screen_x1<0){
Screen_y1+=(0-Screen_x1)*(Screen_y2-Screen_y1)/
(Screen_x2-Screen_x1);
Screen_y4+=(0-Screen_x1)*(Screen_y3-Screen_y4)/
(Screen_x2-Screen_x1);
Screen_x1=0;
}
if(Screen_x2>(screen_width)){
Screen_y2-=(Screen_x2-screen_width)*
(Screen_y2-Screen_y1)/
(Screen_x2-Screen_x1);
Screen_y3-=(Screen_x2-screen_width)*
(Screen_y3-Screen_y4)/
(Screen_x2-Screen_x1);
Screen_x2=screen_width;
}
if((Screen_x2-Screen_x1)==0) return;
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);
g.fillPolygon(x,y,4);
}
/**
* the method to get the sorted lines out of a BSP Tree, and
* call a function to render those lines in the order recieved
* from the BSP Tree...
*/
void pRender(Graphics g){
int i = 0;
pQueue q = myBSP.pGetSortedLines(eye);
g.setColor(Color.black);
g.fillRect(0,0,screen_width,screen_height);
pLine2D tmp;
while(!q.empty()){
i++;
tmp = (pLine2D)q.remove();
/* back face removal */
if(tmp.getPlane().eval(eye) == pPlane2D.IN_BACK)
continue;
/* just pick a unique color for this "line" */
g.setColor(new Color(i*1024+0x555555));
_mydrawPoly(g,tmp);
}
}
/**
* overriding standard "paint" method
*/
public void paint(Graphics g){
pRender(double_graphics);
g.drawImage(double_buffer,0,0,this);
}
/**
* overriding standard "update" method
*/
public void update(Graphics g){
paint(g);
}
/**
* get some primitive user input
* (the arrow keys)
*/
public boolean keyDown(Event evt,int key)
{
if(key == Event.UP){
eye.v[0] += Math.cos(pangle)*7;
eye.v[1] += Math.sin(pangle)*7;
}else if(key == Event.DOWN){
eye.v[0] -= Math.cos(pangle)*7;
eye.v[1] -= Math.sin(pangle)*7;
}else if(key == Event.LEFT){
pangle += 2*Math.PI/64;
}else if(key == Event.RIGHT){
pangle -= 2*Math.PI/64;
}
repaint();
return true;
}
/**
* the init method.... initializes and starts some stuff.
* also calls the method to get input
*/
public void init(){
myList = new pQueue();
load_data();
setup();
resize(screen_width,screen_height);
myBSP.pBuildBSPTree(myList);
repaint();
}
/**
* some weird run method which we don't even need
*/
public void run(){}
}
To make it work, just place:
<applet code="dog3dapp.class" codebase="./" width="320" height="240"></applet>into your HTML... Oh, and you can view the demo HERE! And just to be complete, here's the input file for the thing...
1 100 800 100 500
2 200 500 200 400
3 400 800 100 800
4 400 700 400 800
5 500 700 400 700
6 500 800 500 700
7 800 800 500 800
8 800 500 800 800
9 700 500 800 500
10 700 400 700 500
11 800 400 700 400
12 800 100 800 400
13 500 100 800 100
14 500 200 500 100
15 400 200 500 200
16 400 100 400 200
17 100 100 400 100
18 100 400 100 100
19 200 400 100 400
20 100 500 200 500
21 300 400 300 500
22 400 400 300 400
23 400 300 400 400
24 500 300 400 300
25 500 400 500 300
26 600 400 500 400
27 600 500 600 400
28 500 500 600 500
29 500 600 500 500
30 400 600 500 600
31 400 500 400 600
32 300 500 400 500
Oh, and I think I've forgot to include the unnecessary Queue class... here it goes, along with it's required node class...
/*
* @(#)pNode.java Dec 31, 1997
*
* Copyright (c) 1997, Particle
*
* Sale of this "Software" is prohibited! Only FREE
* distribution is alowed.
*
* -- Particle --
*/
import java.lang.Object;
/**
* A pNode
class is a very basic Node.
*
* It alows users to set and get values of a Node.
*
* @version 1.0 12/31/1997
* @author Particle
*/
public class pNode{
/**
* the data
*/
protected Object data;
/**
* a "pointer" to the next node
*/
protected pNode next;
/**
* Creates a new pNode object. (basically sets the internals to null
*/
public pNode(){
next = null;
data = null;
}
/**
* Creates a pNode object, given data and a pointer to the next node.
*/
public pNode(Object data,pNode next){
this.data = data;
this.next = next;
}
/**
* sets the "next" node...
*
* @param next the next node in the list
*/
public void setnext(pNode next){
this.next = next;
}
/**
* sets the data field of the node.
*
* @param data the data of object type, thus, any object can be used
*/
public void setdata(Object data){
this.data = data;
}
/**
* gets the next node in the "list" ...
*
* @return the "next" node.
*/
public pNode getnext(){
return next;
}
/**
* gets the data field of the node.
*
* @return the data of type Object, most times, a cast is needed.
* @see Object
*/
public Object getdata(){
return data;
}
/**
* a standard toString
method
*/
public String toString(){
return new String((String)data);
}
}
/*
* @(#)pQueue.java Dec 31, 1997
*
* Copyright (c) 1997, Particle
*
* Sale of this "Software" is prohibited! Only FREE
* distribution is alowed.
*
* -- Particle --
*/
import pNode;
/**
* A pQueue
class is a very basic Queue.
*
* It alows uses to insert and remove stuff from the queue,
* it also alows the ability to "peek" into the queue, and
* to find out the number of items on the queue.
*
* Definately needs improment! A "good" queue should have
* 2 pointers, to the back and to the front. Nodes should also
* be doubly linked, to to make queue operations of the queue
* faster; as it is, it's the slowest possible implementation.
*
* @version 1.0 12/31/1997
* @author Particle
*/
public class pQueue{
/**
* this is the "header" node
*/
protected pNode list;
/**
* a counter to count how many items are on the queue
*/
int counter;
/**
* Constructs a pQueue, initialized header node to null, and counter to 0.
*/
public pQueue(){
counter = 0;
list = null;
}
/**
* returns whether or not the queue is empty.
* @return a boolean value of whether or not the queue is empty.
*/
public boolean empty(){
return (list == null);
}
/**
* gets the number of items in the queue.
* @return number of items in queue
*/
public int number(){
return counter;
}
/**
* removes everything from the queue.
*
* actually, thanks to java's gc, all we need to do is set list to null,
* but this method is "more re-ashuring" ;-)
*/
public void clear(){
while(!empty())
remove();
counter = 0;
}
/**
* a private method to insert an object onto the back of the queue,
* this is not a standard queue operation, thus, it's private.
*
* @param obj the object to insert
*/
void insertend(Object obj){
counter++;
list = new pNode(obj,list);
}
/**
* removes an object from the queue, a cast will uauslly be needed when
* calling this function, to convert Object
type into whatever
* type it's suppose to be... (an "instance of" can also be used)
*
* @return the object from the queue.
*/
public Object remove(){
if(empty()) return null;
counter--;
pNode tmp = new pNode(list.getdata(),list.getnext());
list = tmp.getnext();
return tmp.getdata();
}
/**
* inserts an Object
into the queue.
*
* @param obj the object to insert
*/
public void insert(Object obj){
if(list == null){
this.insertend(obj);
}else{
counter++;
pNode t = list;
while(t.getnext() != null)
t=t.getnext();
pNode tmp = new pNode(obj,t.getnext());
t.setnext(tmp);
}
}
/**
* removes an object from the end of the queue, not the
* "correct" way to remove stuff from the queue, thus, it's
* private.
*
* @return the object from the end of the queue
*/
Object removeend(){
if(empty()) return null;
if(list.getnext() == null) return this.remove();
counter--;
pNode t = list;
while(t.getnext().getnext() != null)
t = t.getnext();
Object obj = t.getnext().getdata();
t.setnext(t.getnext().getnext());
return obj;
}
/**
* peeks into the queue. You can use this method to
* see what's inside the queue, (searching the queue for
* for something, or just iterating it...
*
* @param pos a "position" (or count) of where to peek.
* @return the object at that position, or null on error.
*/
public Object peek(int peek_pos){
int i=0;
pNode tmp = list;
if(tmp == null || (peek_pos < 0)) return null;
while((i++ < peek_pos) && (tmp.getnext() != null))
tmp = tmp.getnext();
return tmp.getdata();
}
/**
* the standard toString()
method.
*/
public String toString(){
pNode n = list;
String s = new String();
while(n != null){
s+=n.getdata()+"\n";
n = n.getnext();
}
s += "\n";
return s;
}
}
Well... that's it folks. I'd appreciate any feedback you can give me, just e-mail me at bsptree@geocities.com
© 1997-1998, Particle