PDA

View Full Version : Beam trees



redknite
09-04-2000, 06:59 PM
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

skw|d
09-05-2000, 09:56 PM
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.

/skw|d

redknite
09-06-2000, 05:00 AM
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?

skw|d
09-06-2000, 07:31 AM
What method do you use to clip the view frustum with. Octree, BSP, Portals?

redknite
09-06-2000, 12:00 PM
I use an Octree at the moment.

skw|d
09-06-2000, 02:37 PM
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...
/skw|d

redknite
09-06-2000, 05:41 PM
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.

fenris
09-06-2000, 06:24 PM
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. http://www.opengl.org/discussion_boards/ubb/frown.gif

redknite
09-06-2000, 07:56 PM
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.

fenris
09-07-2000, 02:50 AM
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.

redknite
09-07-2000, 04:36 AM
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?

fenris
09-07-2000, 02:52 PM
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.

redknite
09-07-2000, 07:41 PM
Do you have any info on the map format? there brushes defined by planes rather then polygons really confuses me.

fenris
09-08-2000, 03:34 AM
here ya go:
http://www.planetquake.com/qref/bsps/index.html

redknite
09-08-2000, 04:13 PM
Thanks for your help. Finally got everything working.

fenris
09-09-2000, 06:14 AM
Kick ass! http://www.opengl.org/discussion_boards/ubb/biggrin.gif Glad I could help!

Bruno
09-10-2000, 08:23 AM
Hi
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?

thanks
Bruno

Bruno
09-10-2000, 08:30 AM
Hi
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?

thanks
Bruno

skw|d
09-10-2000, 10:08 AM
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.

/skw|d

Chiguire
09-12-2000, 12:47 PM
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)

skw|d
09-12-2000, 10:11 PM
Occlusion Culling is a test to see what objects can be eliminated from being sent through the pipeline that are in the view frustum, but are not in the final rendered view.

What I was describing was Portal Culling, which has a similiar goal, but is done in a different way and is used with walls. Where occlusion culling is usualy done with objects.

QHULL is a well known program that finds the convex hull of a set of points,
http://www.geom.umn.edu/software/qhull/ . Though all you need to get portal culling to work is to have the world defined as a set of convex hulls, complex objects can create many splits which can hamper performance. The goal of the algorithm that I am trying to develop is not just to find the convex hulls of a room, but to find the convex hulls of a room with the smallest ammount of splits.

/skw|d

Chiguire
09-13-2000, 11:06 AM
You can cheat QHULL!, if you take all your data, preprocess the high polycount objects, and the aproximate them by a few polygons (not making a mesh reduction, but rather faking it with some simple mesh, or even removing it, if it's not a wall), you can cheat QHULL to make very simple convex hulls... http://www.opengl.org/discussion_boards/ubb/smile.gif