(use_BSP || !use_BSP) && (BSP_rendering_tricks)

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

  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.

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?
  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).

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).]

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… :stuck_out_tongue:

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).

Thank you for the posts!

Originally posted by Coriolis:
[b]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).[/b]

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!

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.

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.

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.

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…

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?

Originally posted by kieranatwork:
[b]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?[/b]

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).]

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.

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.

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.

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

Any tutorials on this kind of usage of bsps? None of this is ringing any bells.

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.