New InstanceManager: Instancing done the right way

[masterfalcon]

Ok, guess I hadn't really paid attention to it before. Still sounds like a good application of the extension though.

[Assaf Raman]

I agree, I don't see a different way to support bone animation with instancing without it.

[Mattan Furst]

So basically you suggest more flexibility with the option to use the same animation for different instanced entities, the price is a new 4x3 matrix in the vertex buffer (one per instance), and one more matrix multiplication in the shader. You can still use a one to one ratio of entities to animation - to get the current behavior.

There is an extra cost as the instance vertex buffer needs to be constantly updated with the world position of the entities. But the total bandwidth in most cases should still be lower. Plus there is a lot less cpu time because of the small amount skeletons which need to be updated.

I'm still not sure how to handle the defragmentation feature where entities are moved from one batch to the other. I need to investigate it a little bit better first. But everything else seems strait forward.

[Assaf Raman]

Can you reuse buffers? Use them in more then one batch to save memory?
Edit: I guess this is not a good idea for multi-viewports...

[Mattan Furst]

@assaf raman

Can you reuse buffers? Use them in more then one batch to save memory?

Do you mean as in seperating the instanced entities among several batches. Then using the same instanced vertex buffer among the batches?
I don't think it will be a good idea. That will mean I will need to update the buffer just before each batch is rendered. It will make the implementation for static objects with animation (i.e. windmills, waving flags, etc...). However I can reuse the vertex texture in some cases.

Question: Is separation of instanced entities among several batches a good idea in this case? In non hardware animation not doing so will generate huge buffers. However, with this look up table technique the size of the buffers is much much smaller. Maybe there is no need to seperate the entities in this case to multiple batches.

[Assaf Raman]

Here is an idea - If you have different level of detail of the same model with the same bones for all models, you can reuse the same animation vertex buffers to all all batches of the same model - for different level of details.

[Mattan Furst]

I checked in the first version bone matrix look up table implementation. (improved framerate through limited skeleton animations).
I cannot debug the OpenGL version of the shader as I don't have a graphics card which can support texture fetches in OpenGL. but as far as I can tell it should work.

Update:
This may not be final check-in but everything should still work. I have added the check-in for @mysterycoder who may shortly be working on this section of code for his summer of code dual quaternion project. If you find any problems please post them and I will fix them.

[Assaf Raman]

Kudos Mattan!
Amazing work, here are the FPS results for the new instancing sample - 2500 moving animated instances with shadow.
I have an NVIDIA GeForce GT 435M GPU.

Code: Select all

[b]FPS[/b]     | [b]Technique name[/b]
--------+---------------------------------------------------
25      | "Shader Based"
22      | "Vertex Texture Fetch (VTF)"
133     | "Hardware Instancing Basic" (no animation)
32      | "Hardware Instancing + VTF"
120     | "Limited Animation - Hardware Instancing + VTF"
17      | "No Instancing"

Meaning - Mattan made it - with his technique - he has 2500 moving instances with animation - with almost the same FPS as none animated instances.

Congratulation.


BTW: GL doesn't work for me for the new technique, only dx9.

[dark_sylinc]

Been absent for a week... and wow!!

Congratulations! Quite a good job you did there. I haven't tried it yet and will look at it with more insight later.
This will make a useful addition, specially to crowds and stuff where repeating animations can be affordable.

Cheers!!
Dark Sylinc

[dark_sylinc]

Guys... you seriously need a QA course. NewInstancing sample was really buggy. Fixed

One new bug was introduced (though, previously there was memory leak, so let's call it a tie )
Fortunately, these changes led me to an obscure bug when destroying an InstanceManager which had been tagged as dirty (Ogre would try later to update a dangling pointer).

Results are marvelous! In my case it's faster than HWInstanceBasic!
Running 2.500 instanced entities at 79 fps, Intel Core 2 Quad X9650 GeForce 8600 GTS 512MB

Update: Running 10.000 instanced entities at steady 30 fps

[Mattan Furst]

I am working as I mentioned now on adding texture atlas to the instancing. I have tried to add it to the ogre code. Unfortunately I can't think of a way to do it in a clean and generic manner. Not atleast without spending a lot of time on the code which I don't have allocation for. I will try to add it at a later time. I'll write a specific code for my company's use for now and try to add it in properly latter on my own time.

I just wanted to show\tell you that its not terribly hard once you understand the instancing code a little bit.

[Assaf Raman]

What does the image show?

[Mattan Furst]

It's an implementation of the texutre atlas feature.
If you look closely at the robots you can see that they share among themselves 4 different color schemes. each scheme is from a different texture in a texture atlas.

[Assaf Raman]

@dark_sylinc: Nice work, GL works.

[Assaf Raman]

@dark_sylinc: I talked with Mattan, he was able to convince me that the InstancedEntity class should not be the child of MovableObject, let me try to explain way.
First of all - there is no "is a" relationship between them (InstancedEntity is not a MovableObject) - the reason is that a big part of MovableObject functionality is not implemented\supported in InstancedEntity. Moreover - because InstancedEntity inheritances from MovableObject - you have to attach it to a Scene Node in order to place it in the scene - an overhead.
We feel that InstancedEntity should be a more compact class - small size with small complexity. Think about it - we can have 10000 instances of this class - unlike normal OGRE movable objects.
Removing the inheritance will reduce the size and complexity of the class significantly (see how many data members and virtual members it and its parents have...) - the price is only adding transformation data members and functions to it, not that big of a price compares to the benefits.

What do you think? Do we have your go this? Mattan started to implement this change on his local branch so you won't need to do any work on your side.

[Mattan Furst]

@dark_sylinc
There is another way in which I believe memory should be saved. Instanced entities should not hold the full information on their animation state. Only a pointer to it.

Currently each instanced entity holds several parameter concerning it's skeleton and animation state. Further more, when constructing an instanced entity (by default) or when an instanced entity is removed from the scene it is automatically assigned a unique animation. consider the situation in which a 1000 static entities are assigned a 1000 different animations. This is not just a memory waste but it also slows done the system when creating the entities.

I believe that the parameter concerning the skeleton and animation state should be replaced by a single pointer to an animation handling class (InstancedAnimationState??), and that by default if no animation was specified than no animation should be assigned.

[dark_sylinc]

First of all - there is no "is a" relationship between them (InstancedEntity is not a MovableObject) - the reason is that a big part of MovableObject functionality is not implemented\supported in InstancedEntity. Moreover - because InstancedEntity inheritances from MovableObject - you have to attach it to a Scene Node in order to place it in the scene - an overhead.

That's correct.

Design wise, I observed the old Instancing had "Entities" which wouldn't work with scene nodes. They had their own method of setPosition & Co.
This was unintuitive, badly executed (each setPosition triggered an update to the whole batch), and having SceneNode meant that an object shouldn't be visible until it's added to a SceneNode.

Furthermore this added a great level of abstraction, since you can deal with InstancedEntity and Entity the exact same way. You can even switch between them flawlessly (i.e. like in "New Instancing" sample). It's very handy to switch between them in order to profile which one favours you most.

Having now already talked about the wonderful advantages, yes it's plain overhead.
There's one more thing about the implementation, we use SceneNodes' & MovableObject's functionality in:

Code: Select all

InstancedEntity::findVisible
InstancedEntity::_notifyAttached
InstancedEntity::_notifyMoved

Not much of course, so it should be solvable. Note some techniques use a rudimentary (yet effective) form of CPU culling thanks to these.
Ideally MovableObject would be split into MovableObject and SceneNodeChild. Or add SceneNode->attachInstancedEntity() (I think that last one would add even more overhead for people who don't use Instancing at all)

Last but not least, are you sure this is an issue? AFAIK instancing is used in PCs (where there's enough RAM), not in handhelds, and consoles tend to be coded in lower level, meaning there's much less draw call overhead.
As for the "virtual", as long as most used functions aren't virtual, their overhead would be minimal.

@dark_sylinc
There is another way in which I believe memory should be saved. Instanced entities should not hold the full information on their animation state. Only a pointer to it.

Currently each instanced entity holds several parameter concerning it's skeleton and animation state. Further more, when constructing an instanced entity (by default) or when an instanced entity is removed from the scene it is automatically assigned a unique animation. consider the situation in which a 1000 static entities are assigned a 1000 different animations. This is not just a memory waste but it also slows done the system when creating the entities.

I believe that the parameter concerning the skeleton and animation state should be replaced by a single pointer to an animation handling class (InstancedAnimationState??), and that by default if no animation was specified than no animation should be assigned.

Huh? I get it for Limited animation method you've added, that makes sense. But the rest, I just don't get how; plus I didn't really understand you completely.


In a perfect world (Ogre 2.0) this would be done quite differently. Ogre assumes one MovableObject (i.e. the Entity) can have many Renderables (SubEntities, quieried through MovableObject::visitRenderables), but one Renderable (the InstanceBatch) can't have many MovableObjects (the instanced entities). I realized this when I was writing this instancing implementation; and it impeded me from using Ogre's traditional culling systems (i.e. OctreeSceneManager).

The day Ogre keeps by design the notion that one Renderable can have multiple MovableObjects, we could do wonders with it. Instancing could be implemented in such way that the user may not be even aware his Entities are being instanced (C++ side, a special shader still would be needed, but again, if RTSS is used, he could be completely unaware); it would be done automatically (most likely just a setting that would say "instance me") then Ogre would do the rest. InstancedEntities would get the same CPU culling benefits Entities currently enjoy.
In this kind of scenario the only reason not to use "auto-instancing" is GPU driver overhead (instancing is not entirely free, but scales quickly), entities that don't repeat at all or have all different materials, and supporting old cards or different architectures.

How? Well, Ogre currently iterates through MovableObjects attached starting from the root scene node. It sees the MovableObject whether it should be visible, and if so, ask him for Renderables which are added to the RenderQueue and then repeat with next MO.
How should be done with instancing?
MovableObjects should be tagged while iterating through InstancedEntities as "You're visible" and "you're not visible", instead of asking for their renderables (Sidenote: now that I think about it, we might hack this by setting a boolean when visitRenderables is called and not returning a single renderable to show, don't know if Ogre ).
When finished, iterate through all InstancedEntities/MovableObjects (grouped by mesh, material and renderqueue #) tagged as "you're visible" and add them to the same batch until it's full render them (an InstanceBatch is a Renderable, after all).

This kind of culling would be useful in HW instancing techniques, since although an InstanceBatch might be sent to the GPU because 3 out of his 100 instances are visible, the GPU doesn't lose time on the 93 instances (we just set RenderOperation::numberOfInstances to 3) we would only loose bandwidth in updating a vertex/texture buffer with 100 instances' matrices.

A system like that would be completely internal and the user wouldn't even need to know what's going on inside. He would just need to specify he wants instancing for the Entity he just created.

Currently we perform culling, which is much more rudimentary. It just consists in:
1) Iterate through InstanceBatch
2) Run a simple frustum check to all InstancedEntities from that batch.
3) Render visible InstancedEntities, skip the Batch if no entity is visible.

The disadvantage from this model is that if there are only 2 instanced entities from 2 different batches (which hold 100 inst. entities each) then both batches would be needed to render. Running defragmentBatches() periodically is supposed to minimize this.
Unfortunately when I started I made strong assumptions about an InstanceEntity belonging only to an InstanceBatch (besides HW instancing wasn't there yet; culling was hardly being considered).

Well, I diverged from the original question, but since we touched SceneNodes design, I remembered that I would love in Ogre 2.x (dunno when will that happen, if ever) to take consideration of having one Renderable with multiple MovableObjects.

Cheers
Dark Sylinc

[Mattan Furst]

@dark_sylinc
Just wanted to do a quick post on my progress. (I want be at work tomorrow so I won't work on it).
I've made the changes to the new instancing mechanism for testing purposes.
Changes included having instanced entity as a class on it's own and not as an inherited class from movable object, and moving the animation away from the instanced entity.

under the limited animation mechanism (100x100 entities) I got the following result:

Code: Select all

                   | Original Ogre      | After changes      |
--------------------------------------------------------------
Memory             |  4.0kb per entity  |  2.2kb per entity  |
Nothing changed    |  46-47             |  52-53             |
Animated entities  |  46-47             |  52-53             |
Moving entities    | [b] 28-29[/b]             |  [b]52-53[/b]             |

It would take me a while to analyze the results however:

1. Changes for saving memory in entities seem useless. The original entities don't take that much memory anyway.
2. I would agree that moving the animation to another class also now seems pointless. The only thing that really annoyed me is the automatic creation of animation states and I can fix that in another way.
3. All in all changing the new instancing architecture was in most probabilities a waist of time, at least for the original reasons.
4. What I didn't expect is the improvement in framerate. I'll have to analyze what I did but there is clearly room for improvement. I think I can get the original ogre implementation to almost the same framerate without changing the architecture.

I'll post updates as I progress.

[dark_sylinc]

Do they still use SceneNodes? that would explain the FPS increase with moving entities. Updating the SceneNodes is very branch predictor unfriendly. Furthermore traditionally created SceneNodes are iterated by the OctreeSceneManager.

There's a hack to improve framerates using SceneNodes & Instancing, like this code below:

Code: Select all

std::vector<Ogre::SceneNode>		m_instancedNodes; //Use an array of SceneNodes not created by Ogre
m_instancedNodes.resize( numberOfInstances, SceneNode( 0 ) ); //Create them

//Once per instance:
m_instancedNodes[i]->attachObject( instancedEntity );
m_instancedNodes[i]->_update( true, true ); //Needed after attach.

//Later when updating...
m_instancedNodes[i].setPosition( vPos );
m_instancedNodes[i].setOrientation( qRot );
m_instancedNodes[i]._update( true, true ); //This is needed

//When you're done with everything:
m_instancedNodes.clear();

Make sure the std::vector gets out of scope before OgreMain.dll gets unloaded or else it will get mad by trying to use an overloaded delete which is defined in an unloaded dll. If you can't fix the order of unloading, call the vector's destructor manually and make sure you won't ever be using it anymore (call "m_instancedNodes.~vector()", hacky)
I prefer using a vector, but you can use new & delete as well. You can use sceneManager->createSceneNode() as well (but don't parent it to the root scene node) but I prefer using an array of SceneNodes for cache locality.

Somewhat hacky but the performance improvement is worth it; and easily portable to non-instanced entities. It works because SceneNodes are, like Assaf said, only there to place it in the scene.

Using sceneManager->createSceneNode() works fine, improves speed and isn't 'hacky'. The vector array thing is for those who may want to take all the juice out of it.

[Mattan Furst]

@dark_sylinc
The following is a summery of a post I tried to do about a week ago but I guess I forgot to press the submit button or something (twice).

I have attempted to use the "scene nodes not attached to scene manager" performance enhancement technique. I failed to observe an improvement in framerate. Non-moving entities rendered at ~130fps, moving entities rendered at ~95fps.

I had tried to improve the framerate by removing the [SceneNode]->_update(true, true) line. To counter problems caused by this change I had switch to sphere based calculation instead of bounding box calculations in the _updateBounds() and findVisible() functions. Both moving and non-moving entities rendered at ~118fps. Framerate drop for non moving entities and gain for moving entities.

I hadn't tested the system under my old implementation of using simple objects and not inheriting from MovingObject and using SceneNode. However I believe that in those circumstances, due to previous test the frame rate should have been around 130 for both moving and non-moving entities.

I understand the reasoning behind the architecture you used. I no longer propose to change It. However in the name of performance I would recommend to slightly change the implementation of IntancedEntity and InstanceBatch... so that there is no direct access to nodes. In essence change all functions of the form of [InstancedEntity]->getParentNode()->[Some Function] to [InstancedEntity]->[Some Function]. This would allow specific implementation (though inheritance) of InstnacedEntity when needed. Implementation which will not use scene nodes and thereby might be much faster.

I will try to test this sort of model next week and will report and consult before making any changes to the actual code.

[dark_sylinc]

I had tried to improve the framerate by removing the [SceneNode]->_update(true, true) line. To counter problems caused by this change I had switch to sphere based calculation instead of bounding box calculations in the _updateBounds() and findVisible() functions. Both moving and non-moving entities rendered at ~118fps. Framerate drop for non moving entities and gain for moving entities.

That's interesting. Would need to see if there is some other bug we're missing consequence of not calling "_update". Also, I would need to see how that sphere based calculation is being done.

I no longer propose to change It. However in the name of performance I would recommend to slightly change the implementation of IntancedEntity and InstanceBatch... so that there is no direct access to nodes. In essence change all functions of the form of [InstancedEntity]->getParentNode()->[Some Function] to [InstancedEntity]->[Some Function]. This would allow specific implementation (though inheritance) of InstnacedEntity when needed. Implementation which will not use scene nodes and thereby might be much faster.

I will try to test this sort of model next week and will report and consult before making any changes to the actual code.

Ok sounds reasonable and I'm interested. Let me know how to get your changes (ie. a forked repo? a patch?) so I can see them

Cheers

[BTolputt]

Would love to hear your review/thoughts of the changes dark_sylinc. This thread has been an immense boon to my understanding of Ogre's rendering & how to speed up instancing using it. The experiments and code shown here is invaluable!

[andrei_radu]

Hi, I've recently needed to use instancing for my GSoC project, and had a couple of issues. First of all, I needed to manually render the instanced batches, so their respective entities weren't attached to any scene node, so for the time being I've commented the line that checks if an entity is in the scene. (OgreInstancedEntity.cpp, line 218 : bool retVal = isVisible() //& isInScene();). I'm sure there's a better way of doing this, but I'm not sure what the most efficient one would be.

Secondly, I need a simpler form of instancing than the current instanced batches perform. I get my world-space position from a texture that gets rendered into each frame, so the batch itself doesn't need to worry about it. The only thing I need in the shader is an instance ID(so I can derive my texcoords). This also means my batches are completely static, and no culling is performed. I've resorted to implementing a different kind of batch(I currently derive from InstanceBatchHW). Is that approach OK?

[dark_sylinc]

(OgreInstancedEntity.cpp, line 218 : bool retVal = isVisible() //& isInScene();). I'm sure there's a better way of doing this, but I'm not sure what the most efficient one would be.

I'll have to think about it. Your solution is inadmissible since that code is there to mimic/emulated normal entities behavior; in other words, to maintain consistency.

Secondly, I need a simpler form of instancing than the current instanced batches perform. I get my world-space position from a texture that gets rendered into each frame, so the batch itself doesn't need to worry about it. The only thing I need in the shader is an instance ID(so I can derive my texcoords). This also means my batches are completely static, and no culling is performed. I've resorted to implementing a different kind of batch(I currently derive from InstanceBatchHW). Is that approach OK?

Sounds the right way to do it. You may want to look at how InstanceBatchHW_VTF creates the vertex declaration.

By the way, are you using instancing to draw the light objects?

Since you're already overloading InstanceBatch*, you could solve the findVisible() problem by overloading the right function, in such way that findVisible() isn't called and the instance still added to the queue (i.e. for InstanceBatchHW, it's called InstanceBatchHW::updateVertexBuffer).

You may still want to do CPU culling though. I've done a deferred render for a client some time ago, and we used the lights to attach to units so we have a pretty dynamic lighting system. We were using the old instancing to render the light objects. Since it was an RTS, eventually units using lights from the same batch would become too separate apart.
That's one of the reasons I started to develop the new instancing. Now culling is possible and this drawback is no more. This is also why I added the notion of "defragmenting batches". You'll probably want to overload _updateRenderQueue to call an alternate updateVertexBuffer (since this function isn't virtual) and inside this alternate function you call a new function InstancedEntity::_findVisibleUnattached() where "isInScene()" isn't present.
Also by overloading you can tell your system which instances are being rendered to reduce bandwidth by filling less data into your texture.

Out of experience, by implementing deferred lighting algorithms, you definitely want to render dynamically moving lights. Otherwise other offline solutions like SH (or even simply baked lightmaps) become more attractive and relatively easy to implement.

Cheers
Dark Sylinc

[andrei_radu]

I'll have to think about it. Your solution is inadmissible since that code is there to mimic/emulated normal entities behavior; in other words, to maintain consistency.

I didn't mean leaving the code commented, since the reasons are pretty obvious, but overloading findVisible seems like a reasonable approach.

By the way, are you using instancing to draw the light objects?

Well...yes and no. They behave like regular lights, but their attributes are determined in the vertex shader, each frame. So visibility culling is pretty much out of the question. The data that is in the texture is generated anyway, in a separate render pass(actually during shadow map rendering), so that's actually pretty fast. The process goes like this:
For each light in the scene:
Render Shadowmaps with a custom shader(in order to output other parameters like normal and color)
Render Virtual Point Lights(using instancing) - the shadowmap is sampled to obtain the light's parameters


Thanks for the feedback