Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / Letters and Logs (for Thierry and others) Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Harmless

April 06, 1999, 09:25 PM

In response to Thierry's request I have started digging around through my correspondences looking for relevant information on portal engine variants on my page.

It'll take me some time to find other relevant emails or explanations on the subject, but I'll dig up what I can. I don't have the time that our friend the Phantom has to write a column on the subject but I wind up fielding a lot of questions anyways.

This letter in particular covers a lot of portal vs. BSP issues.

The rest of them are indexed here.

-Harmless

 
Thierry Tremblay

April 07, 1999, 11:59 AM

Harmless wrote:
>>In response to Thierry's request I have started digging around through my correspondences looking for relevant information on portal engine variants on my page.

Thanks a lot for thoses mails... They just confirmed what I was beginning to discover: pure portal ain't that cool. I was considering doing small BSPs for my cells (that would also contains detail polygons), and though: then why not use full BSPs then? But after reading the mails, I must say I really like the kdtree/bsp approach.

My original question was about beamtrees. From what I understand, they are a kind of 2D BSP to subdivide the screen. You render from front->back and know what as already been drawn. This also allow us to easily do hard shadows by rendering from the light source. Basically, they keep track of coverage regions. Am I right?

About the kdtree/BSP approach: since the BSP contains few polygons (

 
Harmless

April 07, 1999, 05:23 PM

Thierry Tremblay wrote:
>>Thanks a lot for thoses mails... They just confirmed what I was beginning to discover: pure portal ain't that cool. I was considering doing small BSPs for my cells (that would also contains detail polygons), and though: then why not use full BSPs then? But after reading the mails, I must say I really like the kdtree/bsp approach.

Thanks. I converged on that solution after trying over two dozen others in the main engine. It seems the least constrained of all my attempts. The octree variant can handle more dynamic geometry than the kd-tree version, primarily because the octree doesn't have to do kd-tree
computations to determine where it is best to split, it just checks the polygon count and divides. Then again the kd-tree can avoid a lot of unnecessary splits in a primarily static scene.

>>My original question was about beamtrees. From what I understand, they are a kind of 2D BSP to subdivide the screen. You render from front->back and know what as already been drawn. This also allow us to easily do hard shadows by rendering from the light source. Basically, they keep track of coverage regions. Am I right?

A beamtree, as I describe herein, should really be thought of as a 3 dimensional structure. It really is just a specialized form of BSP tree. In the beamtree all planes pass through the origin (the eye point). Other than that it subdivides the view as you walk from front to back through the scene into draw and not-drawn sections. Much like a solid BSP can divide between solid portions of the map and air. Since all planes pass through the origin, their 'd' component is always 0, which means you do not need to normalize the planes during beamtree generation, because when you use the distances from the plane for linear interpolation the magnitude of the
plane 'normal' is irrelevant and cancels itself out.

In short, the plane passing through two points in the scene is really just:
plane' = (v1-eye) cross (v2-eye)

then to get the side of that plane any point is on:

side = signof((vertex-eye) dot plane'

for a given viewpoint, the beamtree is used by putting in place 4 'slabs' representing
the left, right, top and bottom of the viewing fustrum.

giving you a degenerate tree like:

left
/
solid right
/
solid top
/
solid bottom
/
solid open

when you insert a polygon you walk down the beamtree with all points in your polygon visiting
each side that the points lie on. If you are doing this for shadow casting point lights you
also clip the polygon as you walk down, otherwise you may not need to if you are just flagging for visible or not visible. You do not need to define the leaf nodes generally. Anything that
opens to an empty 'left' child is solid anything opening to an empty 'right' child is open and unrendered. so think of left and right as 'drawn/not drawn' or vice versa.

when you recurse to a solid node you throw away that fragment because its occluded.
when you recurse to an open node you take all edges of the polygon that have a point that has
recursed this far, and insert those edges as solid planes, the consistency of your clockwise or counterclockwise winding will orient the plane to maintain the proper sidedness relationship.

Any polygon that contains a fragment that you add to the tree is visible.

If you are using this for lit poly fragment generation for a general shadow casting light source you need to clip as you walk down the tree and the clipped polygon is affected by the light source. on hardware if you start with a matte black pass you can render these fragments in using src+dest passes, then render the final texture over afterwards using src*dest or a mod2x pass.

It is possible, using more advanced techniques to improve this tree somewhat, you can collapse nodes that have become completely solid to shrink the tree much like a c-buffer. You can retain shearing matrices to shear dynamic objects onto the surface of the polygons that demark the outer boundaries of each so you can render shadows onto the surfaces by projecting using the projection/shear matrix onto the surface that caps that beamtree leaf any dynamic object that stands in the fustrum of that light source. if you render them solely into the zbuffer using a slight z bias before you render the actual lit poly fragment pass you can effectively 'shadow' one given light source using your zbuffer as a stencil.

Other notes, the beamtree itself doesn't solve vis, it merely is a way to take polygons from a pretty good guess of what is visible and determine if they are indeed visible. When combined with some on-the-fly gross culling/vis system like checking to see if the kd-tree face 'portals' are visible for each node as you walk outwards in the scene it can combine to give you reasonable performance in the face of dynamic geometry.

However, to play devil's advocate, for a purely static scene a PVS is still much better. =)

>>About the kdtree/BSP approach: since the BSP contains few polygons (

 
Conor Stokes

April 11, 1999, 12:14 AM



You guys are beginning to discover the algo the phantom and I have been working on ;-)
He is using the 2d BSP and finding the perfect set by non-filled spaces, and using a optimised
octree, And I am getting the perfect set using my own variation of the beamtree (I project
triangles through two points to the back plane of the frustum, which gets me perspective
projection and world rotation at the same time) and culling octree nodes. I also am using
the painters inside the octree nodes, with a little math to help solve the little painters
problems. I use the beamtree to find my overdraw.

A perfect set is maintainable in realtime with dynamic overdraw prone scenes using this method.

You can also mix in portals and such. I use the octree, as it can cull large sections of
the world much quicker than a BSP. Anyway, the method I do can easily have a lot of cool
side effects, like very quick dynamic shadows and such in real time. The octree is also great
for collision detection.

Also note, I don't store my stuff in a tree, because after culling nodes in the octree, and
culling polygons within nodes that intersect my planes, I can just move on to the next polygon.
So I just go through until there are no untouched nodes in my frustum ;-)

Conor Stokes (aKa DirtyPunk)

 
This thread contains 4 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.