If you're reading this letter, it means that I'm dead. No, wait, I'm still typing. Silly me, this is
the part where I'm supposed to talk about Constructive Solid Geometry. Note to self: more drugs. No,
that can't be right...Ahem I think I'll try again.
If you've made it this far I certainly hope you have a firm, two handed grip on BSPs (I reccomend a
half-nelson and scissorhold combo). Why? Because now were are getting into some seriously dark
mojo, that mysterious realm known as Constructive Solid Geometry (CSG). CSG is the process of
performing regularized boolean set operations on geometric primitives in order to obtain more
complicated models. For example, two square could be added together to form a star-like shape.
a small cube could be subtracted from a large "wall" to create a window or a door. And so on.
So: we've got 2 large sets of polygons that form closed volumes and the two sets may or may not
intersect. Gee, there's got to be an easy way to figure out if and where. But what could it be...
hmm... how about... the BSP trees? Why, how convenient!
I want to make sure you don't get the wrong impression: CSG does not have to be performed with
BSP trees. But it's a lot easier. On a mostly unrelated topic, I want to make sure you get the right
impression: at the time I'm writing these words, this page is the ONLY online source for CSG
information. I had to figure it out myself and (of course) it was only after that I met some people
who had succeeded in figuring it out. So don't thank me for putting this here, just tell all your
friends about it. (=
There are four basic types of operations: addition, subtraction, intersection and difference. Given
that we have a really simple case like two squares A and
B:
Then the four operations would have the following results (respectively):
(The darkened portion remains after each operation)
Now let's see if there's a pattern in these CSG operations that will help us break down the problem
into something we can code. Take a good look at addition. Notice anything special? The part that
remains is the the sum of all of A that was outside of
B and all of B that was outside
of A! So how do we code it?
- Take every polygon in A and "push" it through the BSP tree of
B.
- If a polygon being pushed through the tree is coplanar with a node plane, test the polygon normal
so see if it matches the plane normal. If they match, push it down the inside. If they don't, push
it down the outside.
- Any polygon "remnants" that end on an outside leaf are stored.
- Any polygons remnants that end on an inside leaf are deleted.
- Repeat the process with every polygon in B against the BSP
tree A.
Similar patterns can be found for the other 3 operations:
- Subtraction: All B inside
A FLIPPED and all A outside
B.
- Intersecion: All A inside
B and all B inside
A.
- Difference: A subtract
B and B subtract
A.
Note: When I say 'flipped' I mean that the polygons have to have their normals inverted and (unless you
have some really fancy engine) the polygons' point order will have to be inverted.
Ok everyone, take a minute to let that sink in, work it on a piece of paper until you believe what I'm
saying and do not go further until you are sure you understand what I just wrote or you will
fall into a pit who's bottom does not exist in this reality but rather a very hot place where little
accountants stick you in the ass with pitchforks to see if you're cooked through.
Right, now how do we find which bits are inside or outside the BSP? Once again, a recursive function
comes to our aide!
/* CSGClipPolygon( cPolygon *pPoly, int side )
* Returns a linked list of all the "fragments"
* left over after clipping pPoly to this node.
* side=ZV_NODE_FRONT - delete all inside fragments
* side=ZV_NODE_BACK - delete all outside fragments
* This method is designed to work with node-based
* BSPs, it wouldn't take much effort to convert.
*/
cPolygon *cNode::CSGClipPolygon(
cPolygon *pPoly, int side ) {
int test;
// pPlane is a member of cNode
test = pPoly->TestAgainstPlane( pPlane );
if( test == ZV_PLANE_COPLANAR_FRONT
|| test == ZV_PLANE_COPLANAR_BACK ) test = side;
switch( test ) {
case ZV_PLANE_FRONT:
if( pInside )
return pInside->CSGClipPolygon( pPoly, side );
if( side == ZV_PLANE_FRONT ) delete pPoly;
return pPoly;
break;
case ZV_PLANE_BACK:
if( pOutside )
return pOutside->CSGClipPolygon( pPoly, side );
if( side == ZV_PLANE_BACK ) delete pPoly;
return pPoly;
break;
case ZV_PLANE_SPLIT:
cPolygon *pIn, *pOut, *pRetIn, *pRetOut;
int loss;
loss = 0;
pTest->Split( pPlane, & pIn, & pOut );
// check to make sure Split succeeded
pRetIn = NULL;
if( pInside ) {
pRetIn = pInside->CSGClipPolygon( pIn, side );
if( pRetIn != pIn ) loss = 1;
} else if( side == ZV_PLANE_FRONT ) {
delete pIn;
loss = 1;
} else pRetIn = pIn;
pRetOut = NULL;
if( pOutside ) {
pRetOut = pOutside->CSGClipPolygon( pOut, side );
if( pRetOut != pOut ) loss = 1;
} else if( side == ZV_PLANE_BACK ) {
delete pOut;
loss = 1;
} else pRetOut = pOut;
if( loss ) {
delete pIn;
delete pOut;
return pPoly;
} else {
delete pPoly;
// link all pIn and pOut fragments
// into a linked list and return them.
}
break;
}
return NULL;
}
The real beauty of the above system is loss. Can you see what it does? If a polygon fragment
is split but neither half is deleted, the original polygon fragment is kept. This minimizes the total
number of polygons in the world and really saves us a lot of work. Still, after you use CSG
operations to build a world there will probably be a number of unnecessary splits. To fix this, go
back through the polygons and merge all the appropriate polygons. Which ones are those? We'll cover
that next.
Wow, you're still reading. That or you've gone blind staring at your screen and now the orderly reads
to you (when he's not giving your sponge bath).
By now you've successfully finished CSG and you're building all kinds of complicated levels with
twisting hallways, staircases and neat archways. Feel like you're the only one that cares? Don't
worry, it's just because the little people are so fickle, they don't realize the blood sweat and tears
you put into reading my page - I mean, writing your engine (doh!) As you fly around the models you're
probably noticing that a) Things could and should be a lot faster and b) There are all these funny
little gaps all over the place that are really friggin' ugly. How did they get rid of them in
all those other 3D engines?
I'm going to tackle that first part last and explain why later. Sub-pixel gaps are a result of
splitting polygons, so both BSP building and CSG are to blame. Sub-pixel gaps will be unavoidable as
long as there's a finite number of decimal places in computer calculations. What's happening is that
there are edges that just barely fail to match up at T-junctions, as depicted.
The solution is to search for all these gaps and close them by adding that last point to the adjacent
polygon. Of course, you have to search the entire model. When you're done, though, all the gaps
should be closed.
The slowing down, on the other hand, is a lot more complicated. As more and more CSG operations are
done, more and more polygons are created as bits and pieces are removed. Although the loss
method I showed you does a great job of cutting down the total number of unnecessary fragments there
will still be a signifigant number when the model is finished. The really annoying part is that you
can't delete all these little pieces or there will be "holes" in the model. The answer is to try and
merge together as many as possible. Which ones are good candidates for merging? Well, they have to
be polygons that...
- ...Are on the same node.
- ...Are coplanar.
- ...Have the same texture
- ...Have a shared edge.
- ...Have textures that are aligned and scaled the same ammount.
- ...Are convex forming.
"Not so bad, I can do that ...What the hell? Convex forming!? Aw, crap!" He he he, you're absolutely
right, it was no fun. I'll give you a hint though: If you do all the tests in the order I listed
them, you should be able to prove convexivity (huh?) with two subtractions, a cross product, a
vector normalization and a single if() for each
end of the shared edge. Remember, you're looking for angles of a particular value. By the way:
the reason I explained T-junction removal first is because if the edges are not the same length or
have a different number of points then it makes finding matching edges really really annoying.
One last optimization before we get out of this hell-hole called CSG. Search for all polygons that
share two consecutive edges with another polygon. If the two edges are colinear (they form a straight
line) then you can remove the point in the middle. One less point, one less thing for the final stage
rasterizer to worry about.
Unfortunately, there aren't many ways to hunt down bugs in CSG. All I can suggest is, as usual, start
with the simplest test cases you can think up and then work your way up. It will probably help to
trace the direction polygon fragments travel through the test tree, it will give you some idea of
where things go bad. Asides from that, all you can do is cross your fingers.
SO. We've covered Constructive Solid Geometry. We've looked at some methods of optimizing the model
when we're done building. We laughed. We cried. We became better people. It took me four months to
invent my CSG routines (having no resource to draw from). It was another 6 months before I realized
that my first version was a total screw-up. Two more week to rewrite the new version. Nine and
a half hours to write this page. So don't be suprised if it takes you a while to get the hang of this
stuff. But when you do, "Oh, the places you'll go!"1 Take, for example, the next section.
Portals are a world of adventure and fun just waiting for you! You can build an entire engine on
nothing but portals like Duke Nukem' 3D and when you add them to
a BSP engine you can do some really cool things. Like Mirrors. And reducing raster overdraw to
nothing. And more. Stay tuned.
Back to the top
PREV: Binary Space Partitioning
NEXT: Portals
|
