|
Solid Node BSP And Random Geometry Question submitted by (16 January 2002)  |
Return to The Archives |
 |
 |
|
|
I'm working on a BSP render, and I'm exporting the data from max, using
my "written in 15-mins polysoup exporter(tm) for MAX 4.2". Anyhow. There are, as you probably know a few limitations in the geometry you can feed the BSP compiler. (Which is why most FPS engine levels are build from boxes :) 1. Polygon planes must have the same normal or things go wrong. 2. Polygons can't intersect. The first problem is solved by grouping polygons according to the normal they share. The second, by performing a Boolean union on meshes that intersect. (BSP trees are great for this too) I was wondering, if you know of any other problematic cases, and good solutions to those and maybe the above problems? |
||
 |
 |
 |
|
|
|
This is going to be an unusually short response for me (it seems I
really, really, really, really, really like to type. :) Actually, I'm not aware of any limitations in the geometry that you can feed to a BSP compiler -- you should be able to feed it completely random polygons. As a matter of fact, this was one of the tests I gave my BSP compiler while developing it. You're correct about grouping polygons by plane (actually, this isn't absolutely necessary, but it can save some tree depth and a few headaches.) However, at least with a splitting BSP tree (I'm not sure of the other techniques) polygons can interpenetrate. In my experience with BSP trees (and I'll warn you, this experience is somewhat limited) the key to a successful BSP compiler is an accurate polygon clipper. Furthermore, the key to an accurate polygon clipper is to properly trap the vertices within epsilon distances to the splitting plane. Here's that last statement again, in cleartext: when clipping a polygon to a plane, you need to determine which side of the plane each vertex is on. In reality, a vertex can be on the front side, the back side or on the plane itself. And because of precision errors, you might determine two vertices are on opposite sides of the plane, when in reality, they're on the same side. To solve this problem, any vertex that is within an epsilon distance to the plane, should be considered on the plane. After classifying each vertex (as either in-front-of, behind or on the plane) I perform the actual clipping. This requires some slightly tricky logic, but the results are quite reliable. My experience with BSPs, as stated earlier, is rather limited. This experience is so limited, in fact, that it goes no further than a single implementation. To further limit this experience, the implementation bears little resemblance to any other BSP compiler. However, you're welcome to take a look at it if you like. It uses a technique I derived but never had an inclination to prove until I wrote FSRad (the radiosity processor.) Once implemented, the technique proved quite useful -- it produced trees for very complex datasets very quickly with very low tree depth and very few splits. The technique is explained in the article Fast BSP Tree Generation Using Binary Searches. Note that the trees generated are quite standard -- it's the generation technique that's different. The implementation can be found in FSRad, inside bsp.cpp. Hopefully, you'll find at least some of this useful. Response provided by Paul Nettle |
||
|
|
|
This article was originally an entry in flipCode's Ask Midnight, a Question and Answer column with Paul Nettle that's no longer active. |