reordering input set back

(L) [2006/04/21] [Phantom] [reordering input set] Wayback!

Just a little thought I had:

Suppose we would reorder the initial set of triangles based on a kd-tree. You could walk the tree, writing each triangle / triaccel structure that you encounter in the leaves to a fresh list, marking the ones that are processed so that you don't store the same one twice. Advantage would be that the set would be ordered according to proximity, and also ordered according to actual reference in the leaves, so that data locality would be improved. Even if you would animate this triangle data afterwards, it would still help (although you would have to make the changes everywhere, also in your mesh structures or whatever is used for the animation). Subsequent kd-tree builds might also be faster.


Could one of the compiler / cache guru's comment on this?
_________________
--------------------------------------------------------------

Whatever

(L) [2006/04/21] [tbp] [reordering input set] Wayback!

A year ago in my "let's give a try at post-processing the compiler output" experiment, i implemented a brain-dead naive exhaustive search for common sequences in the accumulated triangle lists found in leaves. It did the job in quadratic time, ouch, and more than squeezed in half the set generaly.

Wow. Impressive. The render time speedup was lost in the noise. Wow. Not impressive.

There was only one case were it offered a significant boost, at rendering time, when the whole triangle list crossed the magical line and approximately fitted the L2 cache.


I've concluded it was not worth the hassle of implementing that compression in an efficient fashion; note that i'm still a bit surprised that such a shrinkage of a blob of data we keep hammering when rendering doesn't help...


So, that's only part of your proposal and while i think re-ordering triangles should be a win, i won't say so only to be disproved by a Reality Check [SMILEY Wink]

(L) [2006/04/21] [Phantom] [reordering input set] Wayback!

I also tried that 'compression', but my idea is completely different: It attempts to keep triangles that are spatially close together close together in memory as well. That *should* help.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/04/21] [tbp] [reordering input set] Wayback!

I cited this example because that was the closest thing i've tried.


Thinking a bit more about that triangle locality concept, your structure is only going to reflect <hand waving> the spatial locality of those triangles, therefore it will heavily be scene dependant.

I imagine you'll get good results with scanned models (ie Stanford stuff, or toxie's clown) because there's no long spanning triangles that would end up being local to a lot of nodes.