New InstanceManager: Instancing done the right way

[dark_sylinc]

Hi all!

Some of you may remember a thread where I started going off topic with a new instancing system.
Well, here is the first (WIP) patch!

The system is not complete, but these are the major advantages over the current InstanceGeometry system:

• Individual instances are controlled through "InstancedEntity", which, from the outside, behave almost like a regular Entity. They're MovableObjects, so they're supposed to work with SceneNodes.
• Dynamic bounding box calculation. Takes into account which instances are currently in the scene (i.e. 1 out of 100 instances is attached to a scene node, shrink the bbox to enclose only that instance).
• Dynamic bbox calculation hides the whole batch if no entity is visible, even though all of them combined would appear to Ogre as if it were visible. This saves render calls (i.e. the camera is looking between A & B, a combined bbox would think there's something in the middle that should be visible. InstanceManager takes care of this situation)
• When using hardware skeletal animation (in the case of ShaderBased technique) the same vertex shader can be used for instanced and non-instanced entities! This makes possible switching between systems flawlessly.
• No need to worry about the 80 (or less) entities-per-batch-or-else-your-system-crashes problem. InstanceManager takes care automatically this for you.
• Setup the InstanceManager given a base Mesh once, then start requesting as many InstancedEntity(s) as you want, the system automatically handles creating and organizing more batches for you.
• Extensible system: By deriving from "InstanceBatch", other instancing systems can be supported. Currently there's only one implementaion (ShaderBased) which is the same InstancedGeometry uses.
• Less GPU VRAM usage since batches share the same vertex & index buffers.

There are a couple of known issues of course:

• Other techniques (including HW instancing) are planned, but not yet implemented
• Only the first sub mesh from the given base mesh is considered.
• Weird/rarely used features from meshes can cause the build process to fail (i.e. submeshes using "shared" vertex buffers from the mesh)
• No LOD support. Although this is somewhat useless because if you're using instancing, this means you have a CPU bottleneck, and LOD aims at GPU bottlenecks
• [s]16-bit indices are used, so watch out if vertexCount * numInstances exceeds 65535[/s] FIXED

Out of all those known issues, only the LOD is the one I don't inted to fix.

Differences between Entity and InstancedEntity:

1. Setting RenderQueueGroup and other Renderable stuff works at InstanceBatch level, not InstancedEntity. This is obviously a limitation from instancing in general, not this particular implementation

I am uploading the patch and a very simple test application which I've been using. So be patient if you don't see any link within the first 10 minutes this post was made

The test shows 10000 robot.mesh staying still in a scene with a very minimal shader, the ratio is 10 fps vs 20 fps (yahoo!!) and 540 fps for the VTF technique. I'll make a much more mind blowing sample (for inclusiong with the Sample tests) when the system is more mature. Besides the test will show the different instancing techniques, but so far only one is supported.

Cheers
Dark Sylinc

Edit: Here's the source code of instance test (Release mode binaries included)

Update 05/06/2011:
Ok, this was supposed to be experimental; but I haven't had more time to spend on it, and surprisingly it's working great. I post it here because there's a lot of people asking for this feature.
The code below shows how to create instance a mesh that contains multiple submeshes. Beware, it needs creating multiple instance managers, and it may be harmful for instancing if you don't understand the effects of having multiple submeshes.
The following technique has the advantage of consuming less RAM & resources than just creating the instance managers alone:

Code: Select all

//I load the mesh now to get the number of submeshes.
MeshPtr mesh = Ogre::MeshManager::getSingleton().load( "myMesh.mesh", Ogre::ResourceGroupManager::AUTODETECT_RESOURCE_GROUP_NAME )

//Create one instance mgr per submesh, managerNames contains unique random names
for( int i=0; i<mesh->getNumSubMeshes(); ++i )
{
   InstanceManager mgr = mSceneMgr->createInstanceManager( managerNames[i], "myMesh.mesh", ResourceGroupManager::AUTODETECT_RESOURCE_GROUP_NAME, technique, numInstancesPerBatch, IM_USEALL, i );
}

SceneNode *sceneNode; //I assume it's valid, create only ONE.
std::vector<InstancedEntity*> ents;
ents.reserve( mesh->getNumSubMeshes() );

//materialNames contains the names of the instancing materials for each sub mesh.
for( size_t j=0; j<mesh->getNumSubMeshes(); ++j )
{
   InstancedEntity *instEnt = mSceneMgr->createInstancedEntity( materialNames[j], managerNames[j] );
   sceneNode->attachObject( instEnt );
   ents.push_back( instEnt );

   //This function will tell the other entities to use the resources from the first entity. Saves RAM & CPU
   if( j != 0 )
   {
         if( !ents[j]->shareTransformWith( ents[0] ) )
         {
            //If we get here, the instanced entity doesn't have a skeleton to share or the technique selected doesn't support skeletal animation
         }
}

Not really pretty, I know; but it's the best I've got. Take in mind this is experimental, that's why I didn't even make a sample showing how to do it. It may not fully work.
If it's worth mentioning, I've been using it for 2 months and no problems so far (well, a few of them arose, but they were fixed).
It can't be that bad, as one user here figured out how to make it work on it's own

[syedhs]

Wow.. this is really great - I have been observing the instancing thread for quite some time. My comparison fps is also great - nearly about 100% fps increase (1110 against 600).
Many thanks for this.

Edit: Btw the robot is red because you forget to include robot material in your 7z file.
Edit2: No you don't need that material, I need to look at the patch first
Edit3: I can't get the hg patch imported to mine.. hmmm

[al2950]

Very good work..

I have not looked at the code yet but would it be easy to add something that would automatically create another batch when the number of vertexCount * numInstances exceeds 65535, or is this already covered in point 6?

[sparkprime]

I recently coded something similar. It is for vegetation, decals and skidmarks mainly. The difference is that when you lay down the polys, they stay pretty much static until it is time for them to be removed again. So rather than positioning them in the shader, I have a vertex buffer (triangle list, no index buffer) where unused space is at 0,0,0 and I 'allocate' triangles from this buffer. Therefore the number of vertexes in the buffer is a multiple of 3, and the number of used vertexes is also a multiple of 3. The buffer is rendered using vertexStart and vertexCount so that the minimal number of triangles are rendered. I haven't bothered with setting up a bounding box, I figure that the fact that a minimal number of triangles is rendered ought to be enough. I am wondering if it is worth the saving given it will take an iteration over all of the vertexes to calculate a new bounding box.

This is tricky bit is to avoid fragmentation in the buffer. Having a bigger buffer than you actually need is great, because you can set it up like a snake chasing its tail. As long as stuff is disappearing and reappearing at the same rate, that is. Unfortunately as the 'snake' reaches the end of hte buffer it needs to wrap around and then I either have to use 2 passes or render the whole buffer.

I am also considering using a classical malloc/free algorithm, e.g. zmalloc from doom. I'm not sure how much space those use though, and Ideally I'd like to fence off unused parts of the buffer to avoid rendering them.

Another interesting avenue is growing/shrinking the physical buffer as needed, like std::vector.

Here is some code:

http://gritengine.svn.sourceforge.net/v ... iew=markup
http://gritengine.svn.sourceforge.net/v ... iew=markup

[dark_sylinc]

Hi!

Thanks for all the replies.

Edit2: No you don't need that material, I need to look at the patch first

If the material isn't there, you'll see the robots white. That's why I made them red. To spot any Cg compilation errors quickly.
Edit: Furthermore the instancing test wouldn't work without it.
Btw it's defined in Bin\Data\ShaderInstancing.material

Edit3: I can't get the hg patch imported to mine.. hmmm

Seems Hg has 2 kind of patching methods (one as a *.hg file, another as a series of *.diff), I'll try uploading both.

I have not looked at the code yet but would it be easy to add something that would automatically create another batch when the number of vertexCount * numInstances exceeds 65535, or is this already covered in point 6?

I've already fixed that in my local copy. Indeed that was easy.

I recently coded something similar. It is for vegetation, decals and skidmarks mainly. The difference is that when you lay down the polys, they stay pretty much static until it is time for them to be removed again. So rather than positioning them in the shader, I have a vertex buffer (triangle list, no index buffer) where unused space is at 0,0,0 and I 'allocate' triangles from this buffer. Therefore the number of vertexes in the buffer is a multiple of 3, and the number of used vertexes is also a multiple of 3

Your method sounds more like a static buffer that is modified dynamically for new geometry and removing old geometry. Indeed would work great with relatively static stuff like vegetation.

The buffer is rendered using vertexStart and vertexCount so that the minimal number of triangles are rendered.

I admit I didn't thought of that! Currently because vertex declarations are being shared, so I can't do that without affecting the other batches.
But I should change it so that the vertex declarations are unique, but still sharing the same vertex & index buffers.

I haven't bothered with setting up a bounding box, I figure that the fact that a minimal number of triangles is rendered ought to be enough. I am wondering if it is worth the saving given it will take an iteration over all of the vertexes to calculate a new bounding box.

The thing is that I don't iterate over vertices/triangles, I iterate over objects. That's why it works

This is tricky bit is to avoid fragmentation in the buffer. Having a bigger buffer than you actually need is great, because you can set it up like a snake chasing its tail. As long as stuff is disappearing and reappearing at the same rate, that is. Unfortunately as the 'snake' reaches the end of hte buffer it needs to wrap around and then I either have to use 2 passes or render the whole buffer.

Yes, I have a similar problem I call "batch fragmenation" which is when, i.e., you have two batches of 60 instances each, and you're using 30 instances of each batch instead of using one batch of 60 instances.
However the system assumes it is used with more or less the same maximum ammount of instances. This means that the system assumes your instances count will be between (in this example) between 60 and 120; therefore eventually you'll have 2 batches the whole time.
On worst case scenario of randoms additions and deletions, the developer will need a way to reorganize it's instances to reduce this fragmenation; which I'm working on it. I'll add details for this later. Basically InstancedEntities will "reparent" with a new InstanceBatch. This will take CPU time but it's a downside the developer will take to account for if he has this specific scenario with his game.

Cheers
Dark Sylinc

[dark_sylinc]

I updated the patch!

I had to change the way the dynamically bbox works, unfortunately it's less flexible now, which means less shadow quality. I had to do it because it didn't scale well when there were massive ammounts of units in the scene.

I've added a new technique!: "TextureVTF"
This new technique uses VTF (Vertex Texture Fetch) to get the world matrices.
Results vary a lot depending on hardware. In the updated test there are now 10000 units in the scene.
Looking at all of them at the same time, I get the fastest fps (40fps) from all techniques. Using a Intel Core 2 Quad X9650 GeForce 8600 GTS
However when I went to the laptop (Intel Core 2 P7350, ATI HD Mobility Radeon 4650) was the poorest performing technique (was even beaten by non-instancing)

The advantage of VTF is that it supports massive ammounts of instances per batch, doesn't occupy constant registers, which doesn't restrict the ammounts of bones per instance.

Also if you play with the camera, you'll see you don't get such high FPS you get with the other techniques on close ups due to less CPU culling.

The disadvantages are the disparity results among hardware. GeForce 8+ works very nice, pre Geforce 7 I've heard it's crap. And I've got only 1 ATI and didn't throw nice results.
Another "disadvantage" is that VTF isn't as supported as the shader based method (the card needs SM 3.0+ and VTF support). It also requires more memory (VRAM and RAM)

I was hoping better results for VTF, but actually seeing that when the 10.000 robots are on screen I get a 400% fps boost on my NVIDIA card, I get a satisfaction feeling.

I've got the defragmentation function to make, and then I think it's time to make a nice sample test for the sample browser.

Cheers
Dark Sylinc

Edit: Tried again with the ATI HD Radeon, on some camera angles it works faster...

[Noman]

This is awesome. I hope to have a serious look at it soon. Hopefully it will make its way into Ogre, maybe as a component rather than just putting it into OgreMain...

[jonim8or]

Awesome that you're working on this. I'm looking forward to using this in my projects.

However I have one question about the following:

No LOD support. Although this is somewhat useless because if you're using instancing, this means you have a CPU bottleneck, and LOD aims at GPU bottlenecks

I don't totally agree with your statement, because it is also possible that both are a bottleneck. I imagine that one would want to use the instancemanager for all the static objects in the level (buildings, trees, grass, street signs, etc). In RTS games and flight simulators the huge amount of these objects would require both instancing and LOD.

This is not meant as critique, I'm rather trying to think along.
If you use any form of view-frustum culling (which you appear to do), can't you use the same part to switch between the LOD's? Then for a 3LOD mesh you will always have 3 InstancedEntities on each position, and based on the distance you mark 2 of them as "invisible".

[syedhs]

imagine that one would want to use the instancemanager for all the static objects in the level (buildings, trees, grass, street signs, etc). In RTS games and flight simulators the huge amount of these objects would require both instancing and LOD.

If I understand correctly, instancing is meant to be batching dynamic objects - ie robot that can move and animate and this is very useful for RTS games for an example. For static objects which don't move at all, better use StaticGeometry or something equivalent (eg Johnj's PagedGeometry)

[AshMcConnell]

Dark Sylinc,

Thanks very much for all your hard work. This is an area that needed a bit of improvement. It will be a great addition for Ogre!

I will read the thread carefully then try and use it for my suspension which weirdly started to disappear at high speed (I think due to problems with bounding box calculations).

Thanks again, much appreciated!
All the best,
Ash

PS. I didn't get quite as good results on my hardware for the demo (core 2 quad 6600 + ATI 5770): -

No Instancing
FPS: ~8fps
batch: 10010

ShaderInstancing
FPS: ~10fps
batch: 2510 (this seems high?)

VTF
FPS: 15.8fps
batch: 56

[dark_sylinc]

PS. I didn't get quite as good results on my hardware for the demo (core 2 quad 6600 + ATI 5770): -

No Instancing
FPS: ~8fps
batch: 10010

ShaderInstancing
FPS: ~10fps
batch: 2510 (this seems high?)

VTF
FPS: 15.8fps
batch: 56

Thanks for saying your hardware specs
According to NVPerfHUD the CPU is still a bottleneck with that many units (may be it's because of Ogre rather than render calls, must investigate). But I don't consider the results unimpressive since it's a 25% speed up with only 4 units per batch.

The particularity of this test is that it stresses a bad situation: skeletally animated meshes with 18 bones per mesh (and there are meshes out there that are even worse with their bone count!)
That's why the ShaderInstancing gets 2510 as batch count, it can only get up to 4 robots per batch.

I'm glad to see VTF is the best performing technique in your system, though it appears there's a big difference between ATI and NVIDIA since I get 40fps. Or may be bus bandwidth is the problem?

I don't totally agree with your statement, because it is also possible that both are a bottleneck. I imagine that one would want to use the instancemanager for all the static objects in the level (buildings, trees, grass, street signs, etc). In RTS games and flight simulators the huge amount of these objects would require both instancing and LOD.

Well can't say you're not right. However current instancing techniques don't use HW instancing, which means constructing the primary InstanceBatch requires a lot of GPU memory. Adding LOD would only make things worse.
Adding HW instancing would be cool. I'm thinking about how to do this. Probably I'll add two variables one in the vertex declaration setting an instancing flag to true, and then setting the frequency in the vertex buffer binding. Then modify both render systems to aknowledge this. As you may have guessed, this requires modifying other parts of Ogre code which I've been avoiding so far.
Once HW instancing is added to Ogre, the VTF technique would have an analogue VTF_HW technique which is the same but using HW instancing instead of building repeating geometry in a batch (which would save a lot of memory).
Also another technique would be born which wouldn't be able to use skinned animations, but would be great for lots of tiny objects like thousands of exploding debris (which require position, scale, and orientation, but not bones); and this technique would be theoretically the fastest one.

Just to clarify what's HW instancing (it's asked many times):
It's the ability of the GPU to repeat the same geometry multiple times, with different vertex source buffers repeating at different frequencies i.e. Buffer0 repeats 5000 vertices 10 times (= 50.000 vertices), and Buffer1 contains 10 vertices repeating each vertex 5000 times (= 50.000 vertices); instead of building a vertex buffer with 2 buffers of 50.000 vertices each. This saves a lot of GPU memory and bandwidth.
Furthermore building a batch of 100.000 vertices means you need to use 32-bit indices, while using 5000 vertices and repeating them 20 times and still use 16-bit indices.
The 2nd buffer can either contain the instance index (and use a ShaderBased technique) or it's own 3x4 matrix in the TEXCOORD semantics (or whatever else you can think of).

[AshMcConnell]

I found before that the ATI drivers are very slow (use more CPU) compared to the nvidia drivers. I moved from a 8800GT to a much more powerful ATI 5770 and my FPS actually went down in my game.

I have had a look at the sample code now and hoping to implement it in my code. Is it possible to use more than one mesh in an Instance? For example in my suspension I have 6 different meshes for each corner of the car (one representing each suspension rod), so 24 in total. In the previous Instance code it was possible to add a number of entities to the instance, build it then submit it as a single batch (while still being able to change the position of them independently). Is there any way that can be done with the new implementation, perhaps I have overlooked something?

All the best,
Ash

[dark_sylinc]

I have had a look at the sample code now and hoping to implement it in my code. Is it possible to use more than one mesh in an Instance? For example in my suspension I have 6 different meshes for each corner of the car (one representing each suspension rod), so 24 in total. In the previous Instance code it was possible to add a number of entities to the instance, build it then submit it as a single batch (while still being able to change the position of them independently). Is there any way that can be done with the new implementation, perhaps I have overlooked something?

I'm afraid not, I should consider a way of doing this. However if you're able to dynamically control them indepedently then internally it means they're most likely using one batch for each mesh (it's very hard otherwise).

For now you can try:
Easy way: If you have many, many vehicles Create 6 instance managers. That will do.
Harder way: Manually create a new mesh, merge the vertices from all 6 meshes into one large buffer and pass this mesh to the instance manager. But the positions of the 6 meshes would be fixed to the offset you put when doing the merge.

[sparkprime]

I implemented vehicle parts just using bones and a skeleton, it's quite nice.

[AshMcConnell]

I implemented vehicle parts just using bones and a skeleton, it's quite nice.

Excellent, I haven't used bones / skeletons yet, I will do a bit of research and see if they will work for me. Currently I have the individual positions of the rod-ends from the physics model, I use them to calculate a position and orientation for the mesh representing the rod. I take it with bones you can render it all in one batch? So I could have a single batch for all the rods on each car.

Anyway, thanks for the tip (and for the skidmarks tip - something still on my todo list), i'll not take this thread off topic

All the best,
Ash

[AshMcConnell]

For now you can try:
Easy way: If you have many, many vehicles Create 6 instance managers. That will do.
Harder way: Manually create a new mesh, merge the vertices from all 6 meshes into one large buffer and pass this mesh to the instance manager. But the positions of the 6 meshes would be fixed to the offset you put when doing the merge.

Easy way: I think i'd have to have 24 instance managers as there are 4 corners and 6 rods in each corner, making 24 unique meshes. I'll probably have a max of 20-25 cars, not sure it would be much of a benefit.
Harder way: I definitely need to be able to change the position of the rods each frame, otherwise it could just be a static mesh.

Thanks for the tips, I'll have a think, hopefully the bones / skeleton approach will work for me.

All the best,
Ash

[Crashy]

Hello,
As the guy who made the original implementation(gosh, it was already 4 years ago , I was student), I find really, really interesting the improvements you've made to it

Myself I've finally not really used the original implemenation apart for some demos because of it's design problems, but sadly I never had the time to improve it.

[dark_sylinc]

A skeleton/bone approach looks like a very interesting idea!
You could manually control those bones and put all 24 meshes into one instance manager.

Still I find odd someone would use 24 different *.mesh files for something people usually doesn't pay that much attention. (IMHO)

I've been pointed out by a community member that the *.patch doesn't work when trying to apply through mercurial. Indeed I've been able to reproduce this, at one of the revisions it stucks at "unsolvable rejections".

However the Hg bundle does work. Go to "Hg Repository Explorer -> Synchronize -> Add Bundle...", select the new parent, right click "pull to here", then update.

I'm relatively new to Mercurial as you guys, I first looked to it when OGRE did the switch.

[AshMcConnell]

I can confirm that the Hg bundle does work on TortoiseHg

I am still on a bit of a learning curve and probably misled my artist on how to do the suspension. What would be "normal"? I haven't had a chance to play with skeletons yet .

Moving suspension is pretty important in an openwheeler (F1 / Indycar / GP2) style game, that's why I would definitely like to put it in (more efficiently this time)

Thanks again for your help!
All the best,
Ash

[sparkprime]

I don't have any screenshots for using bones in vehicles but I do for planes (more complicated but very similar). Check out these: http://spark.woaf.net/grit/blender_bones/

The basic idea is to use bones to separate the moving parts, and the positions in the skeleton are then used to shoot the rays from. So the artist can control some physical aspects, like ray shoot point and suspension length from the modeller, essentially. This also allows 'stretching' of parts since you can use blend weights to e.g. fix one end of a spring to the car and the other end to the wheel, and have it compress properly. The downside is there is more vertex shader work and the vertexes are heavier in GPU memory and on disk. Also the artist has to understand bones and skeletons, and has to be able to position things accurately enough that the car actually drives in a straight line. Usually only character riggers have to worry about that kind of thing, but it's not too hard.

The alternative is to use different mesh files, and link movable objects together with scene nodes. This you can do in the modeller just by creating several objects and positioning them appropriately, but you'll need a custom exporter to export the whole lot. You will also spend more draw calls on the car, e.g. 30 instead of 2 or something like that.

Converting cars comprised of detached objects into boned cars is not that hard, you just merge, select the parts, assign bones, etc.

You can have a look at the blend files here:

e.g.

http://gritengine.svn.sourceforge.net/v ... /vehicles/
http://gritengine.svn.sourceforge.net/v ... vision=957
http://gritengine.svn.sourceforge.net/v ... vision=522

Note that I do not own the copyright on either of these, the license is different for both too. Check copyright.txt in the dirs concerned.

[ahmadi]

Hi
First i must say thank you to "Dark Sylinc" for this patch.
What is best solution for instancing 7 types of meshes?, consider that we have 7 types of meshes with different materials, but no LOD, no animation
We want make ~80 instances from them(for example 10 instances for each of them), but attention that they are dynamic and every frame we must set position of them , InstancedGeometry::InstancedObject must know type of mesh
+Creating 7 InstancedObject for managing them is one idea, but with Ogre 1.7.1 it have runtime error.Im not sure is ok with this patch or not.
+Creating 1 InstancedObject for managing them is another idea , and so ...

Thank you for your attention.
H.Ahmadi

[ahmadi]

As i understand the current version of this implementation don't have pre-build shader that support mesh material (i mean texture+lighting+...).
Its very useful if a hero write one of them

Edited:
Just as an idea i must say Ogre keep some of memory for each SceneNode and Entity in SceneManager, even they don't render! And also keeping them in SceneManager have CPU overhead .
When we are instancing 10000 mesh, for example for particle/dynamic object/ ... Its very effective if we found a way to remove this CPU overhead and memory usage .

[AshMcConnell]

Thanks for the info sparkprime. I'll try to get something working soon

[volca]

I am also considering using a classical malloc/free algorithm, e.g. zmalloc from doom. I'm not sure how much space those use though, and Ideally I'd like to fence off unused parts of the buffer to avoid rendering them.

I am quite interested with what you'll come up with. I implemented something similar, with the exception that the usage is quite static most of the time (here and here - used for level geometry, the movement between buffers would most likely only mean some thing changed a material). Anyway - I think you could get decent results with the ordinary "Best Fit" allocation scheme (i.e. have a linked list of free space ordered from smallest, coalesce free space when possible, try to allocate space with the least waste).

[sparkprime]

There is a strange heuristic though. You want to avoid fragmentation generally, i.e. if there is a gap from 0 to 63 and you have 64 vertexes then that would be OK. However you also want to avoid having large gaps, so if all the other vertexes are concentrated at the far end of the buffer, that would be bad as the triangle count of the draw call would be maximised. I think you're right about a free list type approach though. One property that this system would have under normal use is that typically lots of things of the same size will be added and removed from it, so they should fill the old gaps nicely.