[applied] Vertex cache optimization

[hendu]

I've implemented Forsyth's algorithm for optimizing a mesh for the vertex cache.

The Stanford dragon (smallest one/res4, converted to obj since the ply loader was buggy) gains 15% fps, while the q3 level included has no noticable change. Time taken was 22ms for the Q3 level and 47ms for the dragon.


I suppose the right place would be the mesh manipulator. However, it's some 500 lines, do you still want it in the same file?

I thought of "createForsythOptimizedMesh" for the function name, but better ideas are welcome, that's a bit long

[hybrid]

Yes, size is not much of a problem. It's defintely the correct place.

[hendu]

Posted at
https://sourceforge.net/tracker/?func=d ... tid=540678

I noticed I wasn't packing the verts properly, fixing that slowed it down a bit, the dragon is now at 380ms. Well, it's a one-time event anyway.

[ACE247]

Nice work! nonetheless

[hendu]

Please share the numbers if you do a test.

[hendu]

I optimized the search with the RB tree, now the dragon is at 50ms. Not bad comparing to 47ms with the buggy implementation.

[hendu]

@hybrid

The patch _was_ against SVN, r4040 to be exact? It applies fine using GNU patch. (after line endings are corrected of course, the SVN checkout has a horrible mess of them by default)


On SVN, it's such a PITA to use ...

[hybrid]

The line ending was correct for me, but the patch format was not correct. Moreover, SVN has a different concept than GIT. You cannot use a single revision for all branches. You made your patch against branches/releases/1.7, while you should do such things against trunk/. Revisions are numbered increasingly over all branches. So yes, there's always something to learn

[hendu]

I mean, it was against trunk r4040. It applies against trunk, that revision, using GNU patch.

Google says SVN does not do its own patching, which tool had an issue? TortoiseSVN?

[hybrid]

No, the version was definitely not against SVN/trunk. We moved quite a lot of functions inside the mesh manipulator file. And these changes were not visible in the patch. And yes, I use Tortoise.

[fmx]

Good stuff hendu

[hendu]

Patch didn't complain, so it was definitely valid. YMMV.

Perhaps Tortoise is set to more strict behavior? Having a fuzz of a couple lines is hardly an issue.

[huntersh2014]

A little confused, where to call the createForsythOptimizedMesh()?

[REDDemon]

you have that method in mesh manipulator (should be present in irrlicht 1.7.3 and in last trunk).
have anyone tried to apply the algorithm for sort similiarly textured vertices? (similiar textcoordinates). in theory that should improve also performance.. or not?

[hybrid]

API changes only go into trunk, i.e. will show up in Irrlicht 1.8. This method was not integrated into the 1.7.x branch