New InstanceManager: Instancing done the right way

[Mattan Furst]

Hello dark_sylinc

I have ran some test on instancing system optimization. I have placed the code, as per your suggestion, in an Ogre fork https://bitbucket.org/mattan_f/ogre-instancing-opt-test.

Optimizations were performed along 2 lines:
- The removal of the SceneNodes as a must component for the placement of instanced entities - System can still use scene nodes in the same way but will gain performance without them.
- Removing calls referring to instanced entities' world bounding box. And opting for the faster though less accurate bounding sphere. This presents an improvements for both instanced entities using scene nodes and those not using scene nodes.

I have conducted performance test on the scenario of hardware vtf with matrix lut. The results of which are are summarized in the following table:

instancing opt.GIF

As you can see there is considerable improvement in most cases, especially for moving instanced entities. I would like your permission to check in the code to the main trunk or atleast allow me to make enough changes to the instancing system so I may develop the same code through inheritance.

P.S.
The code could be prettier, I'll fix it once you give the OK.

[dark_sylinc]

- The removal of the SceneNodes as a must component for the placement of instanced entities - System can still use scene nodes in the same way but will gain performance without them.

That's music for my ears. You managed to keep both? Excellent news. Lights work the same way (still work when attached to scene nodes, but can be attached to them for complex animations) so I consider it's still consistent.

Results are encouraging, but I'm afraid I can only look after Wednesday (hard exam coming) and sorry for the late reply, today's election day in my Country.

- Removing calls referring to instanced entities' world bounding box. And opting for the faster though less accurate bounding sphere. This presents an improvements for both instanced entities using scene nodes and those not using scene nodes.

I have no problem with that. In fact sounds better.

Quick glances:

• I really hate the mutable keyword **sigh**. Specially since current generation hardware has more disadvantage by evaluating "if(mNeedTransformUpdate)" than rather updating every time setPos() is called.(this is a controversial subject so leave it that way)
• I don't like how "NewInstancing" is looking. An up static cast. Ugly. Not even a comment we're doing that only for the sample. Random Generator isn't needed. Adds unnecessary code complexity. The idea wasn't to generate "true" randomness, but rather to show the algorithm isn't only strong when everything is facing the same direction with same animation offset. Comments in the code (around line 365 from NewInstancing.cpp) should be added explaining that instances can be controlled either through scene nodes or without them; but goes faster if you don't use them (oddly enough, C++ templates could be used to handle both cases in centralized code, but that adds complexity we don't want to show to a newcomer)
• You've made updateInstanceDataBuffer & _updateAnimation virtual but I don't see any piece of code later one taking advantage of it.

Those are quick glances by looking the code in my browser. Some of it may be wrong as I haven't downloaded, compiled, and tried it. I'll do that in the week.

Cheers
Dark Sylinc

[Mattan Furst]

Results are encouraging, but I'm afraid I can only look after Wednesday

Ok, I hoped to avoid some duplicate work but no matter, as long as the general principle is acceptable that's a big load off for me.

I really hate the mutable keyword **sigh**. Specially since current generation hardware has more disadvantage by evaluating "if(mNeedTransformUpdate)" than rather updating every time setPos() is called.(this is a controversial subject so leave it that way)

Ok will be fixed.

I don't like how "NewInstancing" is looking. An up static cast. Ugly. Not even a comment we're doing that only for the sample. Random Generator isn't needed. Adds unnecessary code complexity. The idea wasn't to generate "true" randomness, but rather to show the algorithm isn't only strong when everything is facing the same direction with same animation offset. Comments in the code (around line 365 from NewInstancing.cpp) should be added explaining that instances can be controlled either through scene nodes or without them; but goes faster if you don't use them (oddly enough, C++ templates could be used to handle both cases in centralized code, but that adds complexity we don't want to show to a newcomer)

I'll try to make a more understandable code. The reason for the random generator is that it was easier to use for me but I'll do something else instead of it.

You've made updateInstanceDataBuffer & _updateAnimation virtual but I don't see any piece of code later one taking advantage of it.

I think this refers to an update I did for the trunk to. This is for inheritance purpose in a private implementation I'm working on (The project I'm working on in my company). Do you find anything wrong with visualizing these functions?


I'll make the changes I specified someday late today or early tomorrow. And post a message once I check them in.
Good luck with your exam. And happy election day.

[Mattan Furst]

Forgot 2 things:

I really hate the mutable keyword **sigh**. Specially since current generation hardware has more disadvantage by evaluating "if(mNeedTransformUpdate)" than rather updating every time setPos() is called.(this is a controversial subject so leave it that way)

Just out of pure interest. Do you have links to documents depicting this problem?


On a different note. When adding the setPosition(), setOrientation(), etc... functions to the Instanced entity I though it might be better to inherit the InstancedEntity from a Limited version of Ogre::Node. Perhaps Ogre::Node can be split up further into a part that just takes care of world transforms and parent world transforms and an inheriting class which takes care of the rest (name, childrens, etc...). However, that would have meant dual inheritance which I hate and I wasn't completely sure how well this solution will integrate with the code.

[dark_sylinc]

Just out of pure interest. Do you have links to documents depicting this problem?

Here. It's controversial because it is argued Desktops PCs have good branch predictors and out of order execution to negate the problem and in some cases, take advantage of it. On the other hand, a simple profiler will tell you we get a lot of cache misses there.
It's typically discussed as "Data Oriented Design". I remember reading once someone very clever (don't remember where) saying that's this is all BS, since DOD is about how you layout the data in memory, and OOP is about how you write code; and they aren't mutually exclusive. The problem lies in that current languages (i.e. C++; but includes higher level ones like Python) don't allow to specify the compiler how we want to rearrange the data (other than a few align macros and something more advanced than rearranging the struct declaration order); therefore DOD is forcing us to write code in a different manner, when this shouldn't be needed.
I remember he proposed a mock up of language extension as an example of how the issue would be addressed, but I can't recall where I read does.

However, that would have meant dual inheritance which I hate and I wasn't completely sure how well this solution will integrate with the code.

Agreed; furthermore it becomes more confusing since the entity is a node and it can be attached to a Node, which aren't the same. Worst, what happen if they try to use Entities as nodes and try to start adding children (enouraging/big potential for bad usage). Ugh, nightmare.

[Shtuka]

I didn't read the whole thread---how many instances of an entity do I have to have such that using the InstanceManager shows a performance improvement?

[Mattan Furst]

@dark_sylinc

Ok. I've updated the code.

I really hate the mutable keyword **sigh**. Specially since current generation hardware has more disadvantage by evaluating "if(mNeedTransformUpdate)" than rather updating every time setPos() is called.(this is a controversial subject so leave it that way)

Ok. I tried to implement it the way you wanted when I realized there is a problem with my architecture. The parent node doesn't inform the Instanced entity when it's position, scale or orientation changes. It only informs the entity that information when it gets updated (update() is called). In which case I can have a situation in which the node has changed but the movable object is unaware of this and it's derived transform position and maxScale parameters are not updated.

This is not as bad as it sounds in most cases functions (i.e. findVisible, getSquaredViewDepth, _updateAnimation) are called after the update function. The main problem is with functions using the mMaxScale value such as getBoundingRadius().

I've changed the code a bit so the the MaxScale data only keeps the local scale and checks the parent scale when called every time getMaxScaleCoef() is called(). I choose to ignore the problem requesting information from other functions before updating the Node. If you find this solution unacceptable please tell me to what to change it to and I'll do it.

I don't like how "NewInstancing" is looking. An up static cast. Ugly. Not even a comment we're doing that only for the sample. Random Generator isn't needed. Adds unnecessary code complexity.

I've removed the up static cast but I'm having problem with removing the random generator. The reason I need the generator is for performance tests. If I remove it most of the entities move in a specific direction. This influences my "Moving Entities" framerate tests as the amount of entities in front of the camera constantly increases or decreases changing the FPS.

During development I have encountered also 2 unrelated problems (Both are now sorted):

• I still had memory issue of vertex and index decelerations not being deleted. I believe I sorted them out to.
• I had a dum bug where I failed to update the size of the possible matrix LUT

I'm currently awaiting instructions from you on how to proceed (or not). No pressure.

@Shtuka
You can run the NewInstancing sample to test.
From what I've seen in the NewInstancing sample beyond 20 - 40 depending on your implementation. But this is very dependent on the type of "real" entity the instancing is meant to replace and what your doing with it.

[dark_sylinc]

@Shtuka
It also depends on the vertex count from those models. i.e. Thousands of instances from a 4-vertex cube vs hundreds of instances from a 120-vertex model.

@Mattan

I still had memory issue of vertex and index decelerations not being deleted. I believe I sorted them out to.

If you're having truoble I'll help you out as soon as I am done here. BTW you're getting memory leaks on exit, crashes on exit, or memory leaks while in game (i.e. destroyed instance manager but engine still kicking)?

Fair enough about the random function. Would be cool if it's moved to a different header and/or cpp file.

About the mutable thing I was expressing my opinion, but it's still probably best to keep the code as it was due to controversy (Ogre does this everywhere, anyway). If you find a way to reduce the amount of mutable variables, then great. If not, don't worry.

[Mattan Furst]

@dark_sylinc

Looking at your reply I think I didn't explain myself well enough in the previous post. Just to be clear:

If you're having trouble I'll help you out as soon as I am done here. BTW you're getting memory leaks on exit ...

No trouble. Memory leak is fixed and there are no crashes on exit.

Fair enough about the random function. Would be cool if it's moved to a different header and/or cpp file

Will do.

About the mutable thing I was expressing my opinion, but it's still probably best to keep the code as it was due to controversy

The instancing is your baby I'll defer to your opinion. In any case in the latest implementation I did as you asked and removed all mutable. The old version might have been more consistent with Ogre code but as far as performance and functionality is concerned I can't see any real difference. Just tell me which you prefer.

[dark_sylinc]

Hi! I went well in the exam I'm very happy yiipppiee!
I'll be reviewing the code tomorrow.

[Mattan Furst]

@dark_sylinc
I moved the random number generator and fixed another problem with not updating the batch's ancestor nodes.

[dark_sylinc]

Hi!

Ummm.... big no.

I'll tell you why, at least until that's fixed or we understand what caused it:

• I don't know what you did to cause it, but Shader-based & HW VTF are waaaaaaaay slower (with & without Scene Nodes). Even No Instancing is faster.
• VTF (not HW) is broken.
• Defragment Batches crashes.

Still digging. It may have been some stupid bug that is slowing things so much. The other two, well we'll have to analyze.

Edit: I saw in rev 2912 you fixed crashes for batches where there are no creators. There shouldn't be batches without creators, so what was causing the crash? (i.e. how to reproduce) or were you experimenting with something else?

Cheers
Dark Sylinc

[Mattan Furst]

wait till Monday, I'll check it myself. It was working ok 4 check-ins ago.haven't tested it completely in the last 2.

[dark_sylinc]

Slowdown started in Rev. 2915 (beware the rng didn't have index = 0 initialized thus it will crash without fixing it back)
VTF seems to have stopped working in Rev. 2912

All rev. # are from the fork

[Mattan Furst]

VTF seems to have stopped working in Rev. 2912

I was attempting to fix a problem I had in hw_vtf and I wrongly assumed the same problem exists in vtf as well. The problem was that I had a model in which the position element was bound to a source 3 after the indices and weight's source which was 2. After calling the closeGaps() function for the vertex declaration the vertex deceleration would indicate that the position was bound to source 2 (the old source of the now removed indices and weights) while the actual vertex buffer of the position element was still bound to source 3. The code attempts to close the bounds both for the vertex decleration and the vertex buffer bindings.

In the vtf technique there are no actual buffers bound at this point which is why the exception occurs.

This is a fix I have performed both on the optimized branch and the main branch. I have committed a changeset which reverts the vtf technique to it's older code which works just fine. Sorry for the mistake.

The performance issue will take me a while longer.

[Mattan Furst]

Update on scene node optimized branch code

I believe I found the performance hit. It was caused because I had a flag which told whether the position of the entity has been updated in the animation. This flag was never reset to say that the animation has been updated. I committed the fix

As for "Defragment Batches crashes" bug, I can't seem to find this bug. Does this occur in the latest version of my branch? Can you give me more direcions on how to reproduce it?

[dark_sylinc]

This is a fix I have performed both on the optimized branch and the main branch. I have committed a changeset which reverts the vtf technique to it's older code which works just fine. Sorry for the mistake.

It's ok. A QA advice: just to make sure you don't make such big mistakes (small in code, catastrophic in feature), hitting spacebar switches between techniques in the sample. Run the sample and hit it until you've ran past the techniques twice (or more).

That way you'll know if you've broken a technique and that there aren't bugs when destroying then creating again a manager of the same technique.

As for "Defragment Batches crashes" bug, I can't seem to find this bug. Does this occur in the latest version of my branch? Can you give me more direcions on how to reproduce it?

Sorry. I just tried ShaderBased right after I start the sample, and hit defragm. batches. It crashes right away.

I'm downloading the changes now.

Cheers
Dark Sylinc

Edit: Garrgh! 503 error from the server. Seems bitbucket is down temporarily.

[dark_sylinc]

Just tried your changes. It's working now. There's a significant performance gain in the major techniques, therefore it's worth checking it in.

There are though two outstanding issues before doing that:

• [s]Defragment batches crashes (at least) in ShaderBased technique, when NOT using scene nodes (debug version is compiling, my guess it's a null pointer)[/s] See "edit 4" down below
• [s]In VTF (non-HW), there's a giant robot that pop ups when looking from a certain distance[/s] See "edit 3" down below

Uploaded with ImageShack.us

Say hi to the funny giant.
The original mesh is scaled by 0.01 IIRC, I guess this entity is getting an identity transform.
So, somehow, either:

• An entity got an identity transform (or just a wrong one) instead of the right one to be applied
• An unused entity (i.e. not in scene) got a non-null transform.

Edit: It happens in ShaderBased too when you select a robot count that is not a multiple of 4 (the amount of instances per batch available for that mesh in that technique) for example when N = 7x7
Obviously, unused instances are not returning a null transform. This isn't needed in HW versions because we can control how many instances are drawn for a given batch dynamically; as a result they won't show the bug.

Edit 2: Note that when we had SceneNodes, it was a clear assumption that an instance that hadn't been requested through createInstancedEntity would not have a SceneNode attached. Therefore checking for a SceneNode attachment would just solve it. Now this assumption is no more. Make sure you've taken that into consideration

Edit 3: Got it. You've created the mInUse variable. In functions getTransforms & getTransforms3x4 you need to change line 161 & 196 respectively, the following:

Code: Select all

if( isVisible() )

By this:

Code: Select all

if( isVisible() && isInScene() )

Also, since isInScene() does nothing more than just returning the content of a variable, move the function definition to OgreInstancedEntity.h so the compiler can inline it better (It's a virtual function, so chances of getting inlined are slim, but there a few exceptions when lots of requirements are met).
Also put a comment after mInUse like this one:

Code: Select all

bool mInUse; //Set when an unused instance is requested or removed, in InstanceBatch::createInstancedEntity()

Edit 4: Change InstanceBatch::defragmentBatchDoCull() with this, basically I've just removed all calls to getParentNode():

Code: Select all

void InstanceBatch::defragmentBatchDoCull( InstancedEntityVec &usedEntities )
{
	//Get the the entity closest to the minimum bbox edge and put into "first"
	InstancedEntityVec::const_iterator itor	= usedEntities.begin();
	InstancedEntityVec::const_iterator end	= usedEntities.end();

	Vector3 vMinPos = Vector3::ZERO, firstPos = Vector3::ZERO;
	InstancedEntity *first = 0;

	if( !usedEntities.empty() )
	{
		first		= *usedEntities.begin();
		firstPos	= first->_getDerivedPosition();
		vMinPos		= first->_getDerivedPosition();
	}

	while( itor != end )
	{
		const Vector3 &vPos		= (*itor)->_getDerivedPosition();

		vMinPos.x = std::min( vMinPos.x, vPos.x );
		vMinPos.y = std::min( vMinPos.y, vPos.y );
		vMinPos.z = std::min( vMinPos.z, vPos.z );

		if( vMinPos.squaredDistance( vPos ) < vMinPos.squaredDistance( firstPos ) )
		{
			firstPos	= vPos;
		}

		++itor;
	}

	//Now collect entities closest to 'first'
	while( !usedEntities.empty() && mInstancedEntities.size() < mInstancesPerBatch )
	{
		InstancedEntityVec::iterator closest	= usedEntities.begin();
		InstancedEntityVec::iterator it         = usedEntities.begin();
		InstancedEntityVec::iterator e          = usedEntities.end();

		Vector3 closestPos;
		closestPos = (*closest)->_getDerivedPosition();

		while( it != e )
		{
			const Vector3 &vPos	= (*it)->_getDerivedPosition();

			if( firstPos.squaredDistance( vPos ) < firstPos.squaredDistance( closestPos ) )
			{
				closest		= it;
				closestPos	= vPos;
			}

			++it;
		}

		mInstancedEntities.push_back( *closest );

		//Remove 'closest' from usedEntities using swap and pop_back trick
		*closest = *(usedEntities.end() - 1);
		usedEntities.pop_back();
	}
}

Now, after all these changes you're free to integrate it into the main trunk version
Congratulations .
I'm very happy with the changes you've made. As a friendly advise make more overall testing before committing code. I know this is open source, we're not getting paid, and the base code wasn't yours, but the amount of bugs I've discovered in the first 15 seconds of opening the application is disturbing (that so could anyone else due to how easy they were to reproduce), it gives the feeling you check in what has just compiled without trying it. This has happened twice so far (previously was when you introduced the LUT).
Of course, this is a development Hg branch, and you've requested feedback. My point is the bugs were just too easy to reproduce.

This isn't a reproach; but a constructive critic. I can see your C++ coding skills are good, which is something hard to find; but writing code that doesn't make an app crash is important too (in fact, more important).

Completely unrelated, I have a question about LUT: Is it possible to have (i.e.) 100 instances in a batch, 50 of them playing animation "A", while other 30 playing anim. "B", and the last 20 playing anim. "C"? Since it's LUT, it's not important the animation time at which they are; however which entity is playing which animation is important. Can your implementation deal with such situation? Is it also possible for instance 'X' to switch from animation "A" to animation "B" at any time? Is there any limit we should be aware of?
It would be very useful for crowd animations (i.e. think Assassin's Creed crowds), since not everyone is doing the same, and they often change into doing something else. Nevertheless the quality of the animation (i.e. the time) isn't very important.
Thanks

[Mattan Furst]

I am thoroughly ashamed of the amount of bugs you discovered in my code . believe it or not, where I work am considered quite good at producing relativity bug free code. It should have never been this bad.

Is it possible to have (i.e.) 100 instances in a batch, 50 of them playing...

Should be. The only real limitation on LUT implementation is that you need to define in advance the amount of animation sets you intend to work with as that sets the size of the vertex texture.

Nevertheless the quality of the animation (i.e. the time) isn't very important

I'm not sure which situation your talking about but you usually do need some time variances. If you, for instance, use a single "walk" animation on all the people in a scene they will all be synchronized and will look like they are on a military march.

[amigoface]

I am thoroughly ashamed of the amount of bugs you discovered in my code . believe it or not, where I work am considered quite good at producing relativity bug free code. It should have never been this bad.

you are human, right ? humans make bugs ... believe me

[dark_sylinc]

I am thoroughly ashamed of the amount of bugs you discovered in my code . believe it or not, where I work am considered quite good at producing relativity bug free code. It should have never been this bad.

Good to hear then. We all have our moments. May be you've focused so much on LUT that the rest got overlooked, which explains why everything involving LUT wasn't buggy.

Should be. The only real limitation on LUT implementation is that you need to define in advance the amount of animation sets you intend to work with as that sets the size of the vertex texture.

Cool, I'll may give it a try in a month or so in a real world scenario. I may not if I happen to be too tight on schedule.

I'm not sure which situation your talking about but you usually do need some time variances. If you, for instance, use a single "walk" animation on all the people in a scene they will all be synchronized and will look like they are on a military march.

Of course. What I meant was that I wasn't picky if character X was at time 0.13 instead of 0.18 and character Y is at time 2.0 instead of 1.2; as long as it doesn't become obvious that we're reusing animations.
What it is important, is that if character X is playing animation A, I don't want him playing animation B (while at the same time I want character Y to play animation C, not A)

Cheers
Dark Sylinc

[Mattan Furst]

@dark_sylinc

Just wanted to keep you up to date.

I haven't forgotten about checking-in the instancing optimized version. I want to first check-in Mysterycoder's summer of code project (http://www.ogre3d.org/forums/viewtopic.php?f=13&t=63952), then I'll merge my code. Mysterycoder's code is a lot more complex and I'm less fluent in it so I wanted to do it first.

I'll most probably merge his code on Sunday and merge the optimized instancing version a week later

[Syphorlate]

Hey there. I am new to ogre (forgive my newbish) and I plan to write my own vegetation system for it. I'd like to use this VertexTexture Instancing but I don't know if it is yet availabe in ogre?
Can I download some working code somewhere? Right now I just have the prebuilt SDK 1.7.2 so probably I need to get the trunk and build ogre myself. So maybe someon can help me out so that
I can get started already working with the new instancing system instead of the old one?

Thanks guys!

[spacegaier]

It is all described in the wiki. There are articles on how to get the latest Ogre source and how to use/build it.

[Syphorlate]

Yes, yes. I know. That shouldnt be a problem. But from what Mattan wrote it seems this new instancing system is not yet part of the trunk. So I was wondering whether I could get the code before it becomes part of the trunk so that I can already work with this system before it gets officially released so that I have something to do now