1. BSP tree
For those of you working on 3-D modelers/raycasters, etc... I'm almost
completed with a simple Binary Space Partition Tree .e file. Currently,
I'm assuming you're doing work in 2D (or 2 1/2D), but the code is modular,
so it should be easy to move it to any number of dimensions you wish to
use.
The current system takes a sequence of lines in the form {{X1,Y1},{X2,Y2}},
then creates a BSP tree out of them. For those of you not familiar with a
BSP tree, it's a more general case of a binary search tree. Each node
represents a line that divides space into two sections. The left child is
all the line segments in 'front,' and the right child is all the line
segments in 'back.' Since all of your walls are static, you'll never
have to resort them. (You may have to resort your moving objects, though).
Once we have the tree sorted, we can sort a viewpoint into it. Once the
location of the viewpoint is known in the tree, we can traverse the tree,
first, the branch we are in, then the branch we are not in. In this way,
all the lines are returned in 'closest-first' order.
Now, you can do clipping on the line to determine if it's visible. Also,
since this is 2 1/2D, you only need to keep track of 320 points to know
if a screen column has been drawn into (assuming 320 pixels wide). Thus,
you can start drawing walls on the screen, skipping already colored
columns. When all the columns are filled, you're done with the frame,
nothing else will be visible, so no need to keep drawing.
This will massively cut down on the number of 'wall detections' needed
in a standard raycaster. If you use some version of ememcopy, you can
easily use the fast texture map routines to map your wall to a buffer, then
draw on the main screen buffer in only the empty (i.e, 0) spots.
Bang! Zoom! Zippy fast!
--
Ryan Zerby, Senior Programmer ryanz at netrex.com
"to create out of his own imagination the beauty of his wild forebears
--a mythology he cannot inherit." -- Allen Ginsberg 'Wild Orphan'
