Here’s a quick post about how visible surface detection works, in particular when there are things that move around. Firstly, say you have a bunch of polygons you want to draw, and some obscure the view of others. It’s easy to demonstrate that you can’t simply sort all the polygons into some magical order, then draw them, one after the other, in that order, drawing over anything on the canvas that was previously there. Think about the bottom of a cardboard box. There are 4 rectangles, each partially on top of the other (this drove me crazy when I was a kid). Since the last polygon you draw must be completely visible since there is nothing to obscure it, there can be no last polygon drawn, so simply sorting all the polygons will not suffice.
Enter Binary Space Partition Trees. A BSP Tree is a binary tree like data structure used for visible surface detection. To generate a BSP Tree, start with an empty binary tree, and insert polygons in the following way:
insert(p, node) if the node is empty then store p in node else if p is entirely behind the node’s polygon insert(p, right subtree of node) else if p is entirely in front of the node’s polygon insert(p, left subtree of node) else split p into pfront and pbehind such that pfront is entirely in front of the node’s polygon and pbehind is entirely behind it insert(pfront, left subtree of node) insert(pbehind, right subtree of node)
Now, for our purposes, the polygons we are going to draw all face the view point, so the view point is always in front of every polygon. Suffice it to say (and wikipedia BSP Trees if you want to know more), that in this special case, if you draw all the polygons in the right subtree by this method, then draw the root node’s polygon, then draw all the polygons in the left subtree by the same method, the correct parts of all polygons are visible.
Sounds cool - what's the catch?
The whole “splitting polygons in two” deal turns out to be a bit of a problem. Since it can occur at every stage of every polygon insertion, the total number of polygons gets really big, which slows down the drawing process, and since that is something that happens at every frame, his is bad news. The order in which polygons are inserted affects the resulting tree. In practice, to generate a “good” tree, where little splitting occurs, many trees are generated with randomized orders if polygon insertion, and the best tree is taken, stored, and just loaded when the program is run.
So far, for this program, I generated the tree on paper and hard coded it into the XML file storing the world. If the following labels are applied to walls…
