NewtonTreeCollision is very slow in 2.18

[Yezide]

I recently changed lib version from 2.09 to 2.18 and have noticed a major slowdown when compiling the NewtonTreeCollision. With optimization 0ff (0) I get these times:

In 2.09:
tris: 46848 Time: 715ms (with optimize 1: 2050ms)
tris: 83640 Time: 1231ms (with optimize 1: 8027ms)

In 2.18:
tris: 46848 Time: 20513ms
tris: 83640 Time: 46539ms

This is something like a 30-40x drop in speed. Optimize off in 2.18 is even slower than optimize on in 2.09.

Any idea what could be wrong?

Also, what is the time complexity for compilation? O(N) or more like O(n^2) (or worse)?

[Julio Jerez]

This is correct,
I do no remember when, but in some version the construction of tree collision what change from top down to bottom up.
Your test show a linear time complexity for but I do not think this is correct.

Bottom up construction are approach optimal distributions of leave nodes but have the disadvantage that they are much slower because the complexity in O(n^2) while top down are O (n * log(n))
The payoff is that search are greatly reduce the log(k *n) time that take to perform a queries, because the queries does not have to visit to many unnecessary to modes than can lead to face that do not have any faces intersecting the queering shape. This is more dramatic when the tress are made of many face of relatively equal sizes

I can probably make some hybrid optimizations, like if a tree is very big, do a Top down and split into large trees, and then when they are sufficiently small switch to bottom up,
for example in the tree is say 20,000 face do a top down pass and have two group of 10000 more or less each, the maybe another and get 4 or 5000 each, and from there do 4 bottom up passes that will make 4 optimal trees. how does that sound?
It will never be as fast as a top down build, but is can be faster than what it is know.
It could also be possible that I can make some optimizations to the build proccess as it is now. But for that I need a mininful sample that I can try to test build time
There are many solutions to try, do you have a test I can try?

also do you use serialization?

[Yezide]

Thanks for the quick reply!

What I am doing is batching several meshes into larger bits, so it is easy for me to limit size to like 10k polys or similar. So there would be no need for you to do that internally.

What would be great though is to have a param, just like optimize, to set if top-down or bottom-up should be used. This would me extremely useful since then I would use the fast version for work versions and then use the slowcompiling (but fast ingame) for release. That would really be optimal for me since there is quite a big difference in compile times and it is very improtant to easily load new versions of the map!

Would that be easy for you to add?

[Julio Jerez]

Well I was thinking a way to make the bottom up build more efficient and I have an idea.
Fist I give a brief description how the tow Newton works in Newton

Top Down:
say you have a group of objects, they could be face or anything. these are the steps to make a tree.

1- make an array of AABB each one containing one object
2-calculate the center and the Standard deviation of all AABB
3-using the axis with the worse standard deviation and center, create tow new group of boxes.
4- add all boxes to one side of the splitting axis to one group, and all boxes to the other size to the other group
5- for each box straddling the axis, add it to the size that contain the largest percentage of that box volume.
6-create a Tree Node with these tow big gruops as childs.
7-if the number of AABB in each child gruop is bigger the max allowed,
go to step one and repeat the process until the entire group is divided into nodes with leaves that contain groups with a small number of boxes
8-return the root node.

As you can see this is a O (n * Log (n)) process, but it is very fast.

The problem with it is that each time you get boxes straddling the splitting plane you need to use a heuristic to decide to which side you will add that AABB, and this is what generate very Fat Trees that lead to queries with more AABB that necessary.

The second Method is even simpler but is slower, and it work like this.

1- make an array of AABB each one containing one object
2- pair each Box with the closest Box in the array. this will lead to a set of n/2 boxes.
3-for each pair make a node with and AABB to one side and other to the other size
4-nwo you have an array of n/2 boxes, and is can go to step one repeat teh prossess until you get 1 Box
5- in a post proccess I run few tree rotations passes to determine if some paris could be better, by rearraing teh leaves.
if a tree rottation generates a better pair, I continue tree rotations but it is very rare that tree rotation generate a change,
so this does nor slow the build prossess.
6-return this as the root node.

as you can see it is very simple and should be very fast, in fact it is an O(n * log (n)) algorithm, however step two is a very deceiving one.
this is because finding the closest AABB to one Box, is an O(n ^2 ) process for a randonly placed array of AABB,
it can be reduce to O(n * log(n)) by using sorting, but even by doing sorting the presses is very slow because.

My idea is to reduce the time to find the closet AABB to another AABB
is to make temporary Top Down AABB, that is not optimized at all,
For example not calculating standard deviation to get a good split plane, instead using the largest axis, and splint teh group at teh center.

This will build very bad but very fast tree, that I can use ast searching database to find the closest AABB to another AABB,
so basically all I need is a way to do search and remove from the temp AABB tree to speed up the construction of the more efficient Bottom up tree.

I can also do what you sugeted and have tow build, Bottom up and to down, but this is somethong I woudl consider as last option,
I am guessing tha the first idea can make then fast enought that we will not nee that.

[Yezide]

I think first building a tree and then using that to decide closest boxes seems like a good appraoch.

I do something similar with pathnodes of AI where I first divide everything into grid and then use that grid when trying to find the closest nodes. Every grid node as a top number of nodes, so this limits the amount of nodes that are searched per node. Pathnodes are much simpler since they are points, so I guess the best for you is to do a tree (kd-tree is what thing u use now sounds like). It should be pretty easy to find a good heuristic in order to do a fast pairing operation.

[Dave Gravel]

Yes, new version is a little bit slower to load mesh data...

[JernejL]

I don't mind slower trimesh building speed if that makes runtime calculations more efficient.

Plus all of you should be using serialized meshes, from what i understand, this doesn't affect serialized meshes?

[Yezide]

Plus all of you should be using serialized meshes, from what i understand, this doesn't affect serialized meshes?

I have just started on it now!

However, the creation code must be faster, because waiting 30 minutes every time I load a map with changes simply does not work

[Julio Jerez]

30 minutes?
46539ms is about 46 secunds, did I read it wrong

[JernejL]

Plus all of you should be using serialized meshes, from what i understand, this doesn't affect serialized meshes?

I have just started on it now!

However, the creation code must be faster, because waiting 30 minutes every time I load a map with changes simply does not work

This is usually a preprocessing step of the editor that happens only whenever a section of map changes, it's not needed to rebuild everything if just a desk was moved..

[Yezide]

Code: Select all

30 minutes?
46539ms is about 46 secunds, did I read it wrong

46 secs = for one batch, which I have >30 of in certain levels.

This is usually a preprocessing step of the editor that happens only whenever a section of map changes, it's not needed to rebuild everything if just a desk was moved..

Because of the way I batch maps, it is very hard to exclude areas that need rebuilding. When making a tree that is used to put all in batches, one moved object can radically changed how the tree is built. Even if I did add some algos to check this, they would quickly breakdown when smaller changes where made all over the map, something that is very common.

They way the editor* works, it is crucial to quickly change and test.

*If interested, have a looky here: http://www.youtube.com/watch?v=0XojVUZJPmc

[Julio Jerez]

do you make tree iterativally at editor time?
anyway this saturday I will work on optimizing the build process, I beleive I can get to be at least as efficient as it was in 2009.
we can always have the the Top Down algorithm as the yard stick.

to clarify you said that a normal mesh of around 80,000 faces was processed in around 1 secund with optimization off.

tris: 83640 Time: 1231ms (with optimize 1: 8027ms)

that figure sound to fast to me, are you sure this is acurate?

[Yezide]

do you make tree iterativally at editor time?

Oh, no I explained that incorrectly No physics generated at run time! But whenever we test the map, physics is regenerated, and the workflow is:
1) build level for while
2) check in game to make sure all is right (this needs rebuild of physics)
3) go to 1

So in order to be able to check changes easily ingame (which is needed even if editor uses same engine as game), we need to load the map as fast as possible.

anyway this saturday I will work on optimizing the build process, I beleive I can get to be at least as efficient as it was in 2009.
we can always have the the Top Down algorithm as the yard stick.

Excellent!

to clarify you said that a normal mesh of around 80,000 faces was processed in around 1 secund with optimization off.

Oops, it is supposed to be indices count, not tris! Otherwise that is correct.

that figure sound to fast to me, are you sure this is acurate?

As said, I wrote bad there too, it is not tris, but indices, so divide by 3 to get triangle count (~25k).
But apart from that I think that it is accurate. 25k polys in 1200ms is not that fast right? (I have a slow n old comp)

[Julio Jerez]

Before I start I run a test jus to make sure I was no crazy, thsi si what I did

I take one of my simpel mesh and tesselated to until if containt 30,000 quads.

I them laod it in my system and it take abut 20 secudn to load teh compleiet mesh, but 9 of those are consume by loading the file in collada.
The collsion tree build process takes 11 secunds.

My systm is a Intel Icore7 2.93 GHZ, so thsi may explain why is not as slow as othe people said.
what are the spect of the systm you are using to run these test?

tomorrow I will run teh same test on a 2.4 pentium 4 mayeb this will be more representative of what people are using.

[Yezide]

My system is:
AMD Athlon 64 3200+ (2.0 Ghz)
1024 Mb RAM