Beam trees

Is there any information on these? discription of some sort of an implementation preferred. Ive looked for a while with little to know success. any help is appretiated. thanks

~ chris

You will not find much information here. Beam trees were used in software rendering engines like Doom where one has control over the rendering of a scanline. With OpenGL you control graphical primitives and the rendering is done somewhere else like on a hardware card.


Alright, but then does anyone have any idea depth clipping, i have frustum clipping already, but im still rendering 2000+ polys a frame because the level goes down the z axis. any ideas?

What method do you use to clip the view frustum with. Octree, BSP, Portals?

I use an Octree at the moment.

Depth clipping, do you mean hidden surface removal? The “quick to implement” way would be to enable the zbuffer as you render the scene. Otherwise you might want to add some more information like a BSP into each leaf of the quadtree so that you can draw from the bottom up of the BSP tree and just write to the z-buffer.

Maybe I didn’t understand the question…

Isnt the z buffer just for depth sorting? By depth clipping i mean removing polygons that arent seen(hidden surface removal) Like this

  • | | || || || |

if you have a scene like that, where the * is the player(viewport) and the lines are the polygons, youd only want to render the first one, as the others would fall in the first polygons shadow. Thats the problem i have, my level is very deep on the axis, so frustum culling helps, but not much.

I saw an article not too long ago (probably on flipcode) on shadow volume clipping. You could probably depth sort the polys to be rendered, then for the nearest poly calculate the shadow volume and clip polys behind it. Then just render what’s still visible. Sorry I couldn’t be much help.

That sounds like it will work, assumming theres not a huge overhead. Any documents on it? I looked around flipcode and didnt seem to find anything unless its hidden away somewhere. thanks.

I looked around for it, without any luck as well. If I may, I would suggest using your octree approach strictly for collision detection, and a portal based system for geometry. With frustum clipping/portals you can get little or no overdraw, and they are rather easy to implement.

Would i have develop some kind of a level editor and have to hand place the portals? Or would there be a feasable way to generate then from the level data?

That’s the one drawback to portal renderers. You have to manualy place the portals to separate sectors (and place them wisely =). I’ve not seen anything on algo’s to determine optimal portal placement. It’s in the hands of a map designer who knows what he/she is doing. One trick could be to use Worldcraft or Q3Radiant to make a map, and a polygon with a certain designated texture assigned to it is treated as a portal. This is my idea, and seems to work well enough for me.

Do you have any info on the map format? there brushes defined by planes rather then polygons really confuses me.

here ya go:

Thanks for your help. Finally got everything working.

Kick ass! Glad I could help!

There is another way to build the portals, without the editor…, because quake’s make that with the qbsp utility…
Anyone knows how they do that?


I know that quake’s do build the portals out of the editor, i think it’s in the qbsp utility. Do you guys have any ideia how to build portals trough code?


A portalization algorithm takes given world data and constructs a set of convex hulls and the portals connecting them. Many people construct them by hand because there is no good algorithm yet and a human can do a better job of selecting where the cells go.

I think that a solution to the splitting problem might be an anti-portal. Imagine a cubical room with a cube floating in the middle. This would require six cells with four portals per cell. Or, you could have only one cell, with six anti-portals (the faces of the cube in the middle.)

I am trying to develop this algorithm now, and if I have any luck I will post it.


The process you’re trying to describe is an oclussion culling algorithm (if your geometry is very open, i mean, if you don’t have a closed area) and it’s meant in a per-object basis, there are ways to do this very fast in closed geometry (Quake levels and so)and i’ve heard a lot of methods to do it (including poralization). I think, but don’t believe me, that there’s a method to find optimal convex hulls, i once had a library that made it (i don’t remember the name), but it was open source (you could find it in sourceforge)