splitting polygons to make them fit into an octree

Hey folks,

While trying to decide who to combine portals, octrees and BSPs for my engine, i read in different places that people cut polygons to make them fit int oa portal or octree. The aim is to make a polygon be in only ONE octree or sector. ok but here are two thoughts:

• By doing a main polygon index you can check before drawing a polygon if it hasnt already been drawn. I’m thinking of the bitset the GameTutorials.com programmers applied on there BSP tut. This way, there is no polygon drawn twice.

• The other point is about vertex count : imagine a polygon that is symetric : each of the 2 sides have the same numbre of vertice. something like that :

http://www.ece.fr:8000/~miffre/public/tmp.jpg

the middle vertical line is the separation between the 2 octrees. If you cut the polygon, well you just add the 2 middle vertice, and you have a right and a left polygon

2 situations:

• first if you see only one of the two octrees :
  you’ll draw 6 verts if you cut polygons
  you’ll draw 8 if you dont
• if you see the 2 octrees :
  you’ll draw 12 verts if you cut the polys
  you’ll draw only 8 if you check your bitset before drawing

So is this a really good idea to split the polygons ? (well probably if so much people do that, so tell me why :D)

wizzo

Hi,

Splitting polygons isn’t usually worth the trouble unless they’re really big, in which case you might, for example, have too many lights affecting a single polygon.

I don’t like the idea of keeping track of drawn polygons either, as it’ll propably mean randomly reading and writing a largish buffer, which is quite an unnecessary slowdown.

The best way to deal with the problem is inserting the polygons into the octree in a way that each polygon belongs to one node only. You’ll have to expand the nodes’ bounding boxes a bit so that all the polygons fit in them. The only problem is, that too large polygons can make the bounding boxes too large, and thus hurt culling, so those you might want to split.

-Ilkka

The state changes will kill you. Consider using a Loose Octree (as JustHanging alluded too).
http://tulrich.com/geekstuff/partitioning.html

Googling for that term should lead to more info.

okay, so i looked at the link you provided and searched a little.
the advantages loose octree provide seem to be more evident for dynamic geometry

im gonna try it out and compare, because Ulrich said it himself “you’ll get more efficiency with ordinary quadtrees/octrees/kdtrees/what-have-you for static geometry.”

JustHanging you are right about the large buffer write/read, i didn’t thought it would slow down that much

Thanks to both of you for your answers,
wizzo

So is this a really good idea to split the polygons ? (well probably if so much people do that, so tell me why )
If you want some kind of precalculated visibility or portal rendering, then it will be hard to get around a few splits here and there (the very heart of BSP). But the idea is that all the splitting allows you come out ahead in the long run (think of all the cheap runtime culling you’ll get). This is one reason why BSPs are so popular (there are many others).

If you choose a good heuristic for your BSP construction, you should be able to keep splits to a minimum, while maintaining a good balance. And for objects like patches, or other huge triangle count models, a sort into the structural leaves of the tree, without splitting, might do the trick. In other words, there’s no need to split everything; base your BSP and visibility on the structural polygon world, and filter the rest into the leaves. You could even define a subset of the polygon world itself as being structural. You could also allow artist to define the structural parts of the world manually, and hand tailor optimal sector portals.

[rave]For complex maze-like worlds, it’s hard to beat good precalculated visibility. If the artists are careful when building the worlds, so that there are never more than a few visible areas from any camera location, you can get humongous culls, say upwards of 50-90% of the world culled instantly. This could allow you to have richly detailed worlds, albeit somewhat limited in view distance.[/rave]

All the vendors (except Intel) are saying “submit at least 1,000 polygons per draw call for best performance”.

Thus, I would cut the world geometry in chunks of some size (say, 20x20x20 meters) and push those chunks down the visibility hierarchy. If a chunk is visible, submit all of it; hopefully that’s at least 1,000 polys.

If you’re using portals, you should probably also cut on the portal boundaries, for optimal cell division.

You can do LOD by re-combining the chunks and running simplification on them, for more distant cells/chunks.

To reduce state changes, I’d also try to cram as much as possible into a single material; i e, for world geometry, I’d probably have one blend texture, four separate material textures, and a normal/bump map; that way, you can submit all of a single chunk in one go even if there’s different surface textures involved (stone, bricks, wood, etc).

I disagree a bit on the Quake3 like design Q proposes. I’ve been developing a game for such an engine lately, and I’m far from happy with it. The design basically makes the artist concentrate too much on the technical issues, which hurts, if not their work, at least the developement time. Also, this kind of design doesn’t scale optimally to highly detailed scenes, because the world gets splitted to too many small parts.

A basic scenegraph with artist created portals results in a more comfortable workflow, and a reasonably efficent culling system. The portals will take care of occlusion culling where it’s useful, and the rest of the world gets drawn without the occlusion culling overhead. It’s easy to control the culling from the editor, as things like grouping nearby objects, splitting large objects and creating portals at doorways are simple and intuitive tasks, as opposed to controlling an automatic vis job. The objects will also come automatically in large chuncs sorted by material.

Just make sure the scene graph supports instancing and LOD, and you have an efficent and flexible engine.

-Ilkka

well my objective was in fact not to do a maze-like engine, because otherwise, i agree with you Q, precompiled PVS is the best, even though JustHanging’s point on detailled level is quite right.

On another point, i’d like to let technical issue far from the artist (because i dont have any is the one reason )

Recombining chunks to perform LOD seems to be a good idea, but i’m not getting into this right now, i keep the idea =)

In the end i guess i’m going to go for :
- Portal for large culling (cause without being a mazelike world, it wont be openspace).
- inside each portal, perform frustum culling with octrees.
- perform collision detection in each octree with a basic bsp system.

I think one of the most important thing is to avoid computation time for low poly count region, so i’ll have to make sur i’ll have about 1000 polys in each chunk.

If someone already tried something like that and ended up with a crapy engine, please warn me =)

oh and jwatte could you explain what you mean by “cut on the portal boundaries”, plz ?

Thanks again for your contributions
wizzo

Do you really need bsp for collision? I’m no expert in collision detection techniques, but as far as I know, if you already have an octree, it should serve you just as well. Also, you might want to consider using an external physics package like ODE, which can handle the collisions and a lot more for quite little effort.

-Ilkka

Hum well about the bsp, i’m still wondering :
the thing is that i want to sort polygons in a way that when i go through the level, the first collision i found is the first collision in time so i can stop checking. I dont know if there is any convenient way to do that;

more than a bsp, i was thinking of storing polygons following each of the 3 axis, so that when i want to check collision, i’d do something like that :

• the movement goes from big x values to small x values, so i pick the right set of polygons
• i test collision : if i found one, this is the first in time

Otherwise, when talking about performance, the octree partitionning is just good.

I’m gonna take a look at ODE, but in fact, i’d like to handle collision & physic all by myself, because I find it interesting.

wizzo

Also, this kind of design doesn’t scale optimally to highly detailed scenes, because the world gets splitted to too many small parts.
This is not true. As I said, there’s no need to split everything; a minimal occlusion boundary would suffice, but it’s up to you to decide what that might be. In fact this method scales better than anything I know of, but not with out a price. The preprocessing time can be considerable (there are Quake3 maps that took days to compile, but that’s with lighting, etc. too).

A basic scenegraph with artist created portals results in a more comfortable workflow, and a reasonably efficent culling system.
This is a viable alternative to a PVS (potentially visible set). Unreal uses the idea of zone portals (portals that bound a leaf cluster) to great effect. This technique trades preprocessing time for runtime performance. But the artist is still burdened with the task of defining the portals, perhaps even more so than in the case of a PVS. Also, the runtime performance will depend entirely on the placement of these user defined portals. Whereas with a PVS, you will likely see a vast improvement without the help of an artist. If anything, the PVS approach is far more autonomous than that of zone portal rendring.

It’s easy to control the culling from the editor, as things like grouping nearby objects, splitting large objects and creating portals at doorways are simple and intuitive tasks, as opposed to controlling an automatic vis job.
Curious, you’re listing more chores the artist has to do, the very thing you cited as a grievance with a PVS.

You don’t control an automatic vis job; it’s automatic. The preprocessor handles all the details. The only thing the artist need do is give the preprocessor hints, like the doorway portals you mentioned, but this is not strictly neccessary.

Also, you might want to consider using an external physics package like ODE, which can handle the collisions and a lot more for quite little effort.
Even with ODE, or any other physics/collision engine, you will still need to organize your world intelligently. BSP zones and leaves make ideal candidates for ODE spaces, for example.

As far as batching goes, creating lists of 1000 triangles or more is easy, especially in the case of a PVS, since for any point in the map, you have the all visible leaves and zones for a simple table lookup. You can sort the materials in each leaf in preprocessing, even merge leaf materials by zone, depending on the granularity desired and draw order requirements.

LOD will be difficult, if not impossible, on the occlusion BSP itself. But you could certainly LOD the contents of the occlusion hulls quite handily.

Again, for a maze-like worlds, I know of nothing better than a good PVS for sheer runtime speed.

I just wish games would stop looking like they’re mazes – you can only crawl so many sewers before it becomes a bit trite

Note that “PVS” is a very loose term. You seem to be using it synonymously with “BSP” which I don’t feel is fair. A portal system is another system that maintains a “PVS” of surfaces. If anything, a BSP lets you know the “AVS” – Actual Visible Set – of all geometry in the tree.

I just wish games would stop looking like they’re mazes – you can only crawl so many sewers before it becomes a bit trite
Tired of the sewer crawling are you? I’ve crawled through so many sewers that I have virtual trench foot ;-).

I actually use the term “maze” here to describe the conditions under which precalculated vis truly shines. This is not to say it wouldn’t be useful elsewhere. A maze, in this context, could be anything from a typical Quake level, to an hilly outdoor area, where the canyons form the “hallways”. PVS works best when most of the world is trivially occluded from any given point.

Note that “PVS” is a very loose term. You seem to be using it synonymously with “BSP” which I don’t feel is fair.
I use the term “PVS” in tandem with “BSP” because my PVS is derived explicitly from my BSP tree. It’s really from the Quake parlance; I didn’t invent it (rats).

A portal system is another system that maintains a “PVS” of surfaces.
I’m not sure what you mean by this. I define PVS to mean an explicit array, or matrix, of leaf visibility. There is no such thing inherent in a portal; it must be calculated, or otherwise made available. In other words, to determine if leaf A can “see” leaf B, you could do a lookup like

if( vis[A][b] == true )
leaves A and B can “see” each other through their respective portals;
else
leaves A and B cannot “see” each other;

If anything, a BSP lets you know the “AVS” – Actual Visible Set – of all geometry in the tree.
The reason it’s termed a PVS, and not an AVS, is becuse of the nature of BSP leaves and portals. Suppose you have a nonsolid leaf the camera is in. This leaf could have any number of portals bounding its convex hull. Couple this with the freedom of the camera to move about the leaf to any position and you get multiple visible leaf lists, depending on where the camera is. So the PVS for a single leaf is made to represent the worst case scenario; it’s a collection of all potentially visible leaves from anywhere within given leaf. Each leaf’s PVS constitutes a row in the final matrix.

The bsp/pvs sure has it’s places, as history has showed us, but I still don’t think it’s the best possible choice for a modern engine. Think of a forest scene, there’ll only be overhead from bsp and pvs. In scenes like that all you need is raw drawing power, and a scene graph can deliver that, basically just sorting visible objects by material and drawing them, without accessing the geometry on a sub-object level. Add LOD and data reuse through instancing, and you can draw lots of scenery fast.

Of course the amount of work these techniques require from the artist depends on the tools, perhaps the ones I’ve been using just aren’t quite there. In my experience it takes a lot of thinking and testing to get good vis results using the quake3 tools. The three things I mentioned are all easy to understand and don’t take much time to perform. Actually the two first ones can be made automatic, but I’m not sure it’s even worth it. Unfortunately there are cases in which this method becomes troublesome too, in particular large cityscapes, where placing the portals becomes unintuitive.

-Ilkka

The bsp/pvs sure has it’s places, as history has showed us, but I still don’t think it’s the best possible choice for a modern engine.
From where I sit, there is no best choice for a modern engine. The choice depends on the type of world, among other things.

Think of a forest scene, there’ll only be overhead from bsp and pvs.
Perhaps your forest scene will not benefit from vis. I wouldn’t recommend vis for packman or pong either. It’s for a certain type of world, for sure.

What overhead?

In scenes like that all you need is raw drawing power, and a scene graph can deliver that, basically just sorting visible objects by material and drawing them, without accessing the geometry on a sub-object level. Add LOD and data reuse through instancing, and you can draw lots of scenery fast.
Why can’t you do these things with a PVS? At runtime, all the PVS is going to cost you is a table lookup. You are, of course, free to dispence with the PVS at any point you see fit. It’s there when you need it, when it makes sense to use it.

In my experience it takes a lot of thinking and testing to get good vis results using the quake3 tools.
Hmmm. Everyone I know (including myself) that has tinkered with the Quake3 tools say they work like gangbusters right out of the box. Maybe you got a bad batch, or something.

The three things I mentioned are all easy to understand and don’t take much time to perform.
The only difference between the 3 things you mentioned and vis is the PVS preprocessor. The fundamental difference between zone portal rendering and vis is the PVS cache. In fact, you can achieve the equivalent of zone portal rendering with a PVS, by merging zone leaves. You’ll likely have some overdraw, but you won’t need any runtime zone frustum clipping/culling.

One compelling argument against the use of vis is the preprocessing time. This can cerainly be a show stopper for many engine designs. More research in the area of BSP/PVS preprocessing is certainly called for. If it could made fast, I’m sure most everyone with like engine designs would use it, at least to some extent.