sorting scene

Quote:

Original post by patrrr It would be easy if I rendered all the geometry in a loop, where one iteration means one object, but that's not the way I do it.

Thats usually how its done, so when you ask 'how do we do it', I think most of us probably do it this way.
We add objects in any order to a render-queue which is basically a big list (it could be an array, a linked-list or something more sophisticated - its all good), we sort all objects by their materials, after sorting we find that all the objects are grouped by their materials (like if they have the same texture then theyre close together) this means that we dont need to switch back and forth needlessly between different colours/textures/alpha, so all the oqaque objects will be grouped together at the top of the list, but all the semi-transparent ones will have sunk to the bottom and be in back-to-front order.
Now all we do is iterate the list from top to bottom and render each object.

Quote:

I have one big global vertex buffer that contains all the vertices in the scene

Thats ok, provided your scene will fit into such a buffer, this is certainly an easy way of doing things [smile]

Quote:

and one index buffer per collection of material properties (like texture, alpha blend, color, etc.). All objects that share the same material properties share index buffer.

Can you elaborate on this?
Maybe its just me, but I dont understand why.
Your colours, tex-coords etc are all stored with your vertices right? Why do you need different index buffers?
Perhaps an example would help if you could think of an easy one.

Without fully understanding your existing system its hard to compare both methods. I can say that *usually* (read: your mileage may vary) you want to avoid reading/writing to index/vertex buffers any more than you have to.

Quick question: Does your system still work efficiently with animated meshes? have you thought that far ahead?

It might be that you're over demonising draw calls. Yes, the general consensus is to reduce them where possible but there is a point when it goes too far. You're effectively moving the overhead to resource modification - in sorting your data you'll have to change the index buffer data and in general resource modification is something you probably want to avoid. Even with a bounded-buffer approach you can introduce significant synchronization issues by modifying resources. The net result is that you don't really improve performance at all!!

If I were you, implement a sorting algorithm that can do f2b and b2f sorting that is temporal-aware. This was one of the most significant wins in an application of mine a few years ago - the f2b/b2f order doesn't change significantly unless you have fast moving objects or a fast moving camera; the order stays roughly the same on a frame-to-frame basis.

Render all opaque geometry in f2b (to take advantage of early-z) and then render all semi-transparent geometry in b2f. Stick with foreach(object){...} until your performance profiler tells you otherwise.

hth
Jack

Thanks for your reply!

To clarify, this is just for level rendering; it is not intended to be used for objects like power-ups and enemies. In a level there are lots of small objects all over the place which would result in lots of calls to DrawPrimitive, and I don't think that would do the performance any good.

Quote:

Original post by dmatter Thats usually how its done, so when you ask 'how do we do it', I think most of us probably do it this way. We add objects in any order to a render-queue which is basically a big list (it could be an array, a linked-list or something more sophisticated - its all good), we sort all objects by their materials, after sorting we find that all the objects are grouped by their materials (like if they have the same texture then theyre close together) this means that we dont need to switch back and forth needlessly between different colours/textures/alpha, so all the oqaque objects will be grouped together at the top of the list, but all the semi-transparent ones will have sunk to the bottom and be in back-to-front order. Now all we do is iterate the list from top to bottom and render each object.

That's what I'm going to do with larger objects that animate and move about.


This is how my system is initialized (cool pseudo-code):

    vertexbuffer vertices = file.ReadVertices(); // per vertex: xyz, rgba, st, normal     object levelobjects[] = file.ReadObjects(); // per object: material reference, primitive indices    material materials[] = file.ReadMaterials();  // per material: texture, color, alphablend    renderable renderables[];    foreach (mat in materials)    {        renderable newRend = new renderable(mat, vertices);  // create one renderable per material, use the global vertex buffer        renderables.add(newRend);        scene.add(newRend);    }    foreach (obj in levelobjects)    {        renderable rend = renderables.getByMaterial(obj.material);        rend.addIndices(obj.indices);    }    foreach (rend in renderables)     {         rend.indexbuffer = CreateIndexBuffer(rend.indices);    }

Grouping indices per material makes rendering fast; I render all the objects that share material in one call. No need for sorting when rendering - if there are no alpha blended objects.
Rendering is easy, just loop through all the renderables in the scene, select vertex buffer and index buffer, and then draw the primitive. I use index buffers because it saves space and I can share vertices between objects and materials.

I think this is a good method for rendering static level objects (just split the buffers if they get too big). Alpha blended objects, LOD-objects and billboards are exceptions, and that's the original question.
Another problem with my system is if you want to cull areas based on where the camera is positioned, you'll have to update all the buffers. This could probably be solved by storing index buffers per area per material. Well, I'm rambling. I hope I cleared it up a bit.

Quote:

Original post by jollyjeffers Render all opaque geometry in f2b (to take advantage of early-z) and then render all semi-transparent geometry in b2f. Stick with foreach(object){...} until your performance profiler tells you otherwise.

I tried the foreach-method at first but it was too slow. That might have been because I had one index buffer per object though, I'll have to do some more experimenting to see if that's the case.
Keep in mind that this is mostly static level data, and lumping all the static data together wouldn't be such a bad idea, would it? I could pick out the transparent objects and render them separately.

Thanks!

I've done some experimenting with the foreach-method for static level objects, and the results: drawing 1800 small primitives per frame is more than 10 times slower than my method (where you draw ~50 huge primitives), even if you sort objects per material at rendering.
In fact, sorting the objects per material seems to make no difference at all. Probably because the 1800 draw primitive calls make the app cpu-bound. (I've checked with a sampler, and the app is using 100% CPU)

Some numbers: The biggest primitive is 252 indices, the global index buffer is 61.68 KB, the global vertex buffer is 373.38 KB.

[Edited by - patrrr on July 26, 2007 6:25:25 PM]

With static geometry there is little excuse not to pre-process your geometry into suitably large, material sorted batches ideally using some sort of spatial partitioning.

Modern graphics cards require large batches to operate efficiently, try not to starve your gfx card with each call to draw primitive, 1800 tiny batches is certainly a good way to to get unimpressive results.

Using 100% CPU usage according the task manager isnt necessarily a bad thing by the way, its quite missleading actually.

Quote:

Original post by dmatter With static geometry there is little excuse not to pre-process your geometry into suitably large, material sorted batches ideally using some sort of spatial partitioning.

Exactly, and that's what my statistics say as well.
You say spatial partitioning, do you mean like a grid or an octree? To implement that, would you let each node have a list of index buffers, where one buffer maps to one material?
That's what I'm interpreting "material sorted batches" as anyway, a batch is an index buffer, right? And you can't change material mid-batch.

Yes you could have one fat vertex buffer and many batch-sized index buffers at leaf nodes of your spatial partitioning structure (which may be an octree, could also be a BSPtree or ABTree for example). You would need an index buffer per material type.

I think you're more likely to get better performance with a vertex buffer per leaf node and then have individual index buffers per material, but the principal remains the same.

dmatter: "I think you're more likely to get better performance with a vertex buffer per leaf node and then have individual index buffers per material, but the principal remains the same."

If memory serves, the common wisdom about vertex buffers used to be that you should make fat buffers to minimize vertex buffer changes. This was like years ago. Have things changed since then?

-- Jani

Yes and no, large batches are a good thing but theres a limit to this where suddenly the gfx card will choke.
Its true that switching a vertex buffer is less expensive than it may have once been but relatively speaking its still an expensive operation.

If your entire scene fits into one vertex buffer then thatd be more efficient, if your entire scene is very large then use one (big) VB per leaf node to prevent killing your performance.

Thanks. I like to think big, so designing an engine I'd automatically assume all geometry won't fit to video memory. Is it worthwhile to implement my own vertex caching scheme which takes a fixed size vertex buffer and manages its contents according to what geometry is currently needed? (I remember Yann explaining such a scheme over here back in the day.) Or is it better to just use multiple vertex buffers and leave caching for the driver to take care of?

-- Jani

Whether its worthwhile or not partly depends on the actual amount of geometry you have to push through the pipeline, on the extension/implementation you use (VBO, VAR, D3D vertex-buffers etc) and on your drivers.

Say we want to shove our entire very large scene into several very big vertex buffers and just let the drivers manage them, the problem with this is that not all the geometry will fit into VRAM at once (remember firstly its limited space and secondly it does have to store other GPU resources like textures too), the drivers will most likely decide to uncache the geometry from the VRAM and reload it later when needed from the system-side shadow copy (you know, like a default managed D3D buffer). This in itself is fine, however because of the sheer size of our scene all weve done is move the problem onto the system RAM, again for very very big scenes not all the geometry may even fit into the systems RAM so the OS may start paging geometry out to the harddrive (which we can assume wont fill up and if it did then we're screwed in general). Now at-worst case scenario when we try to bind a vertex buffer we find that not only is it not currently cached in VRAM its not even resident in the system-side RAM and we have to wait for the OS to schedule for paging the chunk back in to RAM (and possibly paging something else back out)..welcome to a world of low performance [smile].

If we are dealing with such vast scenes, which Yann surely was, then building a slot system is a good plan. The idea is to allow only several large VBs to exist at one time and each VB is slotted up into smaller chunks that more finely correspond to the actual size of individual world geometry, having only a few VBs means minimising the number of bind calls.

What Yann then did was through performance testing and profiling he came up with a suitable balance between the number and size of VBs to create (and a VB as a whole can be managed by the drivers) and the number of slots and slot granularities to subdivide each VB up into. The drivers are unaware of the slot system so we need to manage them ourselves.

The possibility this opens up is that now that a fixed number of VBs exist at one time (and the hope is that the drivers can efficiently manage them however it sees fit), we can now write our own paging system to load geometry in from the harddrive or CD/DVD/Bluray when our own level-streaming heurisitics decide its a good time instead of relying on the OS to page it in when its told to which will usually be whenever we try to bind a VB (which is at render-time).

Edit:

Quote:

You would need an index buffer per material type.

Or just one index buffer and make several render primitive calls using the same bound index and vertex buffer.

[Edited by - dmatter on July 27, 2007 6:57:54 AM]

Thanks!

I was wondering whether it would be possible to find an optimal number of smaller VBs (i.e. an optimal size) which would trump the advantages of the slot system. I mean with smaller VBs the driver would have much more fine grained control over which vertices are in VRAM at a given time (something you're taking care of yourself when using the slot system). The driver would then maintain the working subset of geometry in VRAM with VB-size granularity.

Like dmatter said, if a large world is divided up into just a couple very large VBs it's obviously going to be a nightmare.

How about many small VBs each containing a small part of the world? Is the cost of changing VBs so high that it's not possible to achieve the performance of Yann's slot system?

UPDATE: Well, obviously if the VB size is too small the GPU's work is going to get interrupted more often and there's cost associated to that..

-- Jani

I think the biggest issue is that its all driver dependant.
In theory I think that drivers managing many small VBs could out perform the slot system but in-practice I believe they just arent aware of enough to make such optimal decisions.
Its the same argument why people write their own memory managers rather than let the OS handle it.. because the program knows what its doing better than the generic memory manager model does.

I dredged this up from my bookmarks, take a look, in particular at posts by phantom and Yann.

Edit: Note aswell that when Yann designed the slot system it was originally a sliding slot system, to get the equivalent behaviour (behaviour not performance) by trying to use many small VBs you'd have to destroy and re-create VBs yourself since the driver is unlikely going to analyse VB usage and reallocate them to suite.. such behaviour is very specific and the drivers memory management model is a generic one.

[Edited by - dmatter on July 27, 2007 9:50:30 AM]

Quote:

Original post by dmatter I think you're more likely to get better performance with a vertex buffer per leaf node and then have individual index buffers per material, but the principal remains the same.

Thanks, but the question remains - how should I treat objects that need to be sorted? A list per leaf with all the objects that need sorting in that node?
I'm still not sure why you shouldn't update index buffers when sorting, yes I know it creates a synchronization point, but particle systems usually do it this way don't they?
I have a hard time letting go of this, sorry [smile]

For static geometry sorting by material is a pre-process, you can do it offline then store them sequentially within a node for the run-time.

With a properly constructed render-pipeline all geometry (static or dynamic) goes through the same rendering process and it all gets dynamically sorted.
Certain types of material need dynamic sorting even if the geometry is static (like alpha objects need sorting based on where the camera is). In this case when they are added to the render-queue they will be sorted back to front.

The fact that the static geometry is pre-sorted by material makes the run-time sorting faster and slightly closer to a linear iteration over renderable objects.

As for not editing index-buffers, its usually better to leave them alone just like vertex buffes, if you change them they need to be transferred from the grpahics card and back again which is slow and costly and this cost inreases as the size of the buffer increases.
Techniques do exist for LOD and particle systems that do involve editing the indices or vertices and these equally incur the overhead of mapping index-buffers. However for rendering, modifying the index buffer is not necessary, especially if the geometry is static, in this case the only reason to touch the contents of either a vertexbuffer or index buffer is if you had to un-cache it to make space for some other object previously.