PDA

View Full Version : (use_BSP || !use_BSP) && (BSP_rendering_tricks)



hunsoul
06-13-2003, 01:33 AM
Dear all!

I have some question and I would like to get some very good answer to them. Please!

1. What do You think, should I use BSP for an indoor engine or I should use other methods? (I would like to display large amount of polygons - huge buildings with lot of detailed objects)
2. I wrote a Quake3 BSP viewer but I don't found a fast way to display the polygons (I did'n find faster way on the internet too). At the moment, I render the BSP face by face, I use <glDrawArrays(GL_TRIANGLE_FAN, pFace->startVertIndex, pFace->numOfVerts);> for render a face so I think I don't be able to render the polygons (of a face) faster than this, but this is not a good solution that I render the BSP face by face. Don't you know any solution to rendre the BSP faster than this? Are there any gl extension which can handle a bitset (PVS) so with it i could render the whole thing with one gl command? How do you solved this problem? (I don't get a very good speed result)


----
Yes, I know, my English is poor - sorry

tfpsly
06-13-2003, 01:42 AM
1) go for portals
2) Flag your visible faces. Then group the visible faces according to the materials they use. Then for each used material, set it up then render all visible faces using it in a single call.

hunsoul
06-13-2003, 02:09 AM
Originally posted by tfpsly:
1) go for portals
2) Flag your visible faces. Then group the visible faces according to the materials they use. Then for each used material, set it up then render all visible faces using it in a single call.

Thank you for your answer!
1) The problem is with portals that I can hardly determine the portals (the user don't defines the rooms or any additional information for the portal generator)
2) Do you means that I shoul do that in every frame?

tfpsly
06-13-2003, 04:50 AM
1) yeah, portals are often placed by the graphists. There are ways to auto generate portals, I just don't know how well that performs.

2) Yep, definitely. You'll save much time if you call glDrawElements once per material (let's say around 100 calls/frame) instead of doing a material switch + a call to glDrawArray per triangles ( ~30 000 per frame).

knackered
06-13-2003, 04:56 AM
So you're advocating constructing vertex arrays every frame, and sending them across the bus every frame for your static level geometry? Or are you saying you should do this construction every time the viewpoint moves into a new portal?

[This message has been edited by knackered (edited 06-13-2003).]

tfpsly
06-13-2003, 07:33 AM
So you're advocating constructing...

Note that the vertex arrays may not be changed : you can only alter the index buffer, while the vertices stay in agp memory for example.

If possible, the array should be reused of course, and should be updated only when you change the current camera leaf in the Q3 bsp for example.
On the other hand, re-computing the indice array every frame does not take much time. =)

Oh, and if you compare that with the time he currently loses for nothing... :-P

Coriolis
06-13-2003, 10:56 AM
Use a portal renderer with manually placed portals. This will give you a good PVS for the current eye position; quake3 PVS is for an entire volume of space, so it will almost always be larger than the PVS from a portal renderer. The advantage of precomputed PVS is that it theoretically requires little designer intervention, but realistically the designer has to babysit it with detail brushes anyway.

Most geometry can be put into static vertex arrays based on material, and then you just memcpy the indices you need per-frame into a larger index buffer. Any geometry that isn't rigidly animated or that has a shader effect that changes vertex paramters over time cannot be optimized in this way (unless of course you translate those shader effects into a vertex or fragment program).

hunsoul
06-16-2003, 01:23 AM
Thank you for the posts!


Originally posted by Coriolis:
Use a portal renderer with manually placed portals. This will give you a good PVS for the current eye position; quake3 PVS is for an entire volume of space, so it will almost always be larger than the PVS from a portal renderer. The advantage of precomputed PVS is that it theoretically requires little designer intervention, but realistically the designer has to babysit it with detail brushes anyway.

Most geometry can be put into static vertex arrays based on material, and then you just memcpy the indices you need per-frame into a larger index buffer. Any geometry that isn't rigidly animated or that has a shader effect that changes vertex paramters over time cannot be optimized in this way (unless of course you translate those shader effects into a vertex or fragment program).


Unfortunately, I can't place portals manually and the automated portal generating is too complicated and not even as good.
To be more clear...I would like to make a Viewer which could diplay a huge geomerty base on a file exported from a CAD program. I would like to make a tool which will read the exported file, make the precalculation end save the result to an own file-type than the viewer will read in this file.
At first I thought that I should build up a BSP tree (and maybe generate lightmaps) but I am very interesten in Your opinions! I know that using portals would be more usefull (because of BSP increase the polygon number - which is huge already) but as I wrote I am just working on an exported file, and the whole proscess must be automated.

- Please write more ideas and solutions!

Thank you!

tfpsly
06-16-2003, 01:54 AM
I know that using portals would be more usefull (because of BSP increase the polygon number - which is huge already)

Not necessarily. To use your own example, Q3 does not split the polygons.

MickeyMouse
06-16-2003, 03:58 AM
Why do you think Q3 doesn't split polys?
How would they build BSP without cutting some faces?
I see no way to build BSP without increase of faces count, so that BSP is a _real_ BSP tree.

MickeyMouse
06-16-2003, 04:10 AM
Well, very recently in my semestry project I wrote a "BSP" tree generator which does the thing, that is doesn't increase actual number of polys of a scene.

What I do is to recursively split groups of polys like you normally do, but instead of cutting some faces which intersect with "best cutting plane", I do put such faces to both: front and back "bags" of polys, then repeating the same.

Such solution results in an increased number of polys' indices in "BSP" tree, but the actual number of faces stays the same - this has quite a big advantage over standard BSP, because you end with same number of faces, thus things requiring doing stuff "per face" (like ray-tracing, frustum-culling) stay almost same fast (you just add bit flag for every face and test whether it has already been processed).

Hope it helps.

davepermen
06-16-2003, 10:31 PM
how about an octree, a quadtree (there is a in-and-outdoor first person shooter engine floating around, with a quadtree! hehe, it rocks!), a kd-tree, an abtree, or what ever? there are much bether things for modern situations than just bsp and portals. both are definitely flawed for not-indoor-only situations, as about all games should be. even indoor games should not restrict them selfes..

kieranatwork
06-17-2003, 12:17 AM
Depending on your scene, it's perfectly reasonable to use a mix of quadtree and a portal+pvs within the same render frame - eg. portal+pvs for indoors, quadtree with adapaptive lod for terrain, BSP for indoor collision, quadtree for terrain collision.

I don't understand why you believe you have to choose just one method?

hunsoul
06-17-2003, 12:58 AM
Originally posted by kieranatwork:
Depending on your scene, it's perfectly reasonable to use a mix of quadtree and a portal+pvs within the same render frame - eg. portal+pvs for indoors, quadtree with adapaptive lod for terrain, BSP for indoor collision, quadtree for terrain collision.

I don't understand why you believe you have to choose just one method?

Why should I use more than one method? I just want to render only a huge building without any terrain. - but I would like to render it from inside and from outside too. So I think using BSP is resonable in this case. But I think the BSP is a little old method, not the best frend of the newest hardwares. So I just wondering if I could use a better technic...like portals but the problem is I can't generate portals without any information made by user but this tool must be automated.

Do you have any suggestion?

--- + (edited part)
Do you think that sould I use HP's occlusion extension (without BSP)? Do you have any experience with it?

[This message has been edited by hunsoul (edited 06-17-2003).]

hunsoul
06-18-2003, 12:12 AM
Any other idea? I think this topic can be interesting for a lot of people.

So the main question is:
How should I render (and what method worty to use) a huge building (or buildigns) with lot of polygons - to can be viewed from outside and inside - without adding additional informations (like defining portals) in the editor (automatic portal generation?).
Are there any better solution than using an old timer BSP? - which is not too "modern hardware" frendly.

I am waiting any idea and experience. http://www.opengl.org/discussion_boards/ubb/smile.gif

roffe
06-18-2003, 01:07 AM
Originally posted by hunsoul:
Why should I use more than one method?

Just because one method doesn't always solve the problem.

I'm no expert but I have some simple rules of thumb I follow when writing scene graphs.
Maybe they'll help you.

1. Pick tree structure,nbr of children per node/divide rules, depending on polygon density(polygons/unit volume). Example, for the "world", choose octree. Dense model, choose bsp.
2. Do NOT subdivide too far. Keep your batches fairly big >300 polys/batch.You can have the best tree structure in the world, if your batches are too small it will kill performance.

John Pollard
06-19-2003, 01:14 AM
I don't understand why BSP's have this stigma attached to them. A BSP tree is just a space partitioner, that subdivides space along arbitrary boundries. It does exactly what an octree does, but it isn't restricted to fixed, axial aligned planes. You don't even need to use your original geometry to build a BSP. You can even use fixed boundries, and it will act like any other space partition system. So for indoor areas, use planes that closely match the structural geometry. For outdoor areas, use fake planes to simulate an octree.

Q3 built a BSP tree from the geometry, then built a PVS from that. It then pushed the original geometry down the BSP, then remembered which leaves each face touched. For each face fragment what was pushed into an empty leaf, it took the convex area of these visible faces (like wrapping a rubberband around the fragments), and used those for rendering. It was actually quite cool, because it used the BSP to reduce overdraw without increasing triangle counts all that much. There is all sorts of cool things you can do with a BSP.

So as you can see, this was a *real* BSP that was used, and the faces were cut by the BSP, but not in a way most people are used to. It cut them in a way, that only increasded triangle count by about 5-10%. But this increase was probably as fast, or faster because of the reduced overdraw. It could have just left the faces uncut as well. It was a compromise.

jebus
06-19-2003, 04:46 AM
that is how i do my BSP also. automatic portal generation isn't that complex...in fact that part of the code looks almost identical as building the BSP tree itself. the data structures can get rather bloated during PVS creation but that's only once during level compilation. once it's stored to disk, it's just file i/o.

jebus

KuriousOrange
06-19-2003, 04:50 AM
Any tutorials on this kind of usage of bsps? None of this is ringing any bells.

lxnyce
06-19-2003, 06:24 AM
Wouldn't this make a great personal competition. If someone can provide a decent complex building (1 million plus polys) like hunsoul is proposing, we can all duke it out to see which algorithm is best to render it with. The model should be just a set of raw polygons, but complicated enough that we just can't push the entire thing to the graphics card to render it (or stick in a display list). Preferably not just triangles, but in its original format. The model shouldn't have any visibility information whatsoever or even textures for that matter (though it would be nice). Then we can all put our algorithm to the test to see who can come up with the best visibility system to work for arbitrary meshes. Ok, I guess arbitrary wouldn't exactly fit this, since we are tailoring the algorithm for the building mesh, but you get the point. We can take a look at preprocessing time, indoor rendering speed, outdoor rendering speed, etc... to see if this algorithm really scales well. I'd be willing to at least try, just need a model to try it on. Talk is great, but prototyping is better.
As for the argument on BSP & PVS, I have nothing against it. I think they are both a great thing, but I don't like the constraints that PVS places on your geometry, especially for large landscape type environments. If you can get away with it for a first person shooter, all the best to you. BSP really has nothing to do with PVS (just for the record), and you can use PVS even with octrees or quadtrees. From the days when I started coding 3d without hardware, BSP was initially just a method used for perfect back to front traversal (think painters algorithm). Over the years its usage has grown vastly, as has most algorithms. Its not the only algorithm out there for visibility though, and I think thats why alot of developers have that grudge against it.

knackered
06-19-2003, 01:43 PM
Originally posted by lxnyce:
Wouldn't this make a great personal competition.

Err, no.
Have you got nothing better to do, lxnyce?

hunsoul
06-20-2003, 01:44 AM
Originally posted by lxnyce:
Wouldn't this make a great personal competition.

Yeah, maybe I could make a homepage for this competition.


Originally posted by lxnyce:
If someone can provide a decent complex building (1 million plus polys) like hunsoul is proposing, we can all duke it out to see which algorithm is best to render it with. The model should be just a set of raw polygons, but complicated enough that we just can't push the entire thing to the graphics card to render it (or stick in a display list). Preferably not just triangles, but in its original format. The model shouldn't have any visibility information whatsoever or even textures for that matter (though it would be nice).

I could provide a very complex building - no problem. Maybe more than one, so we could test the algoritms not on one sample. The input file format could be - what I can provide - very simple. I can save the model in file format in which we a agree or .3ds file format (or maybe .ase or milkshape file format) but I think the .3ds file format is simple enough. I can save into the file only triangles or big polygons (convex, concav and holed polygons). Maybe I could put on the website of the models more than one version.
The competitors could push the advantage of the modern hardwares so the programs could be made for GeForce3 too but not for GeForceFX - only because I haven't got GeForce4 so I couln't test that programs on my machine. http://www.opengl.org/discussion_boards/ubb/smile.gif

What do you think? http://www.opengl.org/discussion_boards/ubb/smile.gif I think it would be funny and very instuctive!

nystep
06-20-2003, 03:58 AM
hmm i think such competition can be interresting, however, there are many things to think about.

1. is preprocessing data allowed?

2. how much max RAM may the program use?

3. how long can the preprocesing be?

4. LOD should be forbidden: too easy to get high framerates. http://www.opengl.org/discussion_boards/ubb/wink.gif

that's all i have in mind at the moment...
1M triangle sounds quite little however..

lxnyce
06-20-2003, 06:19 AM
Glad to see that other people don't think this is a waste of time.

"1. is preprocessing data allowed?"
Sure. The objective is to see who can come up with the best generic algorithm for arbitrary building meshes. You can save the preprocess information, but I think that to be fare, everything should be run from scratch on any model given. There should be a general program skeleton to take in an input file and render it.
Kin dof like :
MyProgram.exe -input "Bulding1.txt"

"3. how long can the preprocesing be?"
As long as it needs to be, though I don't think I or anyone else would sit 30 minutes or more waiting on a building to be preprocessed by your algorithm.

"2. how much max RAM may the program use?"
As much as you need to, but I think that will most likely be watched to see if the algorithm is usable or not for larger worlds (not just 1 but hundreds of buildings).

"4. LOD should be forbidden: too easy to get high framerates. "
If you can find a way to arbitrarily apply LOD onto a building of that size, I would say more props to you. Remember, the building is going to be just raw polygons or triangles. Each one of these is not guaranteed to have the same texture. All can possible use a different unique texture for all we know.

"that's all i have in mind at the moment...
1M triangle sounds quite little however.. "

If 1 Million is too little, then bump it up to 20 million. It all depends on the model we get. We just need a model we can't shove as a display list or push to the hardware straight and get good frame rates. The model should also be tailored towards outdoor and indoor rendering, not like quake levels we often see. Think like a 100 story office building with offices on each floor, items in each room, etc...

As for the sources, I don't think it should be mandatory to give it out unless the author wants to. However, I think that the algorithm should at least be gone over in full so that we can all benefit and judge for ourselves whether or not this method deserves any recognition.

I don't want to give timelines or anything, because this is for fun. Since it is a competition (for bragging rights I guess), I feel that there will be some speed in seeing who can come up with something decent. So as to not sound like I am just trying to rip of someones algorithm, I plan on trying myself, even if my entry might suck (which I doubt).

To me this is fun. I love 3D/OpenGL, and visibility algorithms have always interested me. There is nothing to gain from this but experience and intellectual knowledge. If you don't feel like doing it, then don't, but please don't knock the other people who like to do it for fun.