Optimizing static data for BIH back

(L) [2006/08/12] [Phantom] [Optimizing static data for BIH] Wayback!

I am playing with a little idea: For most games, a lot of data is static. For BIH, large triangles are bad, as they generate large nodes that receive many rays. The dynamic data (e.g., avatars, projectiles, vehicles, waving trees) typically consists of smaller triangles. A rather simple preprocessing step on the static data would improve BIH performance a great deal, while preserving the capability to change geometry on the fly.


Suppose the 'static' geometry is preprocessed so that any triangle in this set is not larger than 1/16 of the scene bounding box, on the x, y or z axis. Now let's suppose that all triangles have a 'next' ptr. This ptr is used to link the original triangle to it's first fragment, and to generate a linked list of fragments that make up the original polygon. The list is terminated by a null ptr. Using this simple data structure, it's easily possible to change the original polygon, should we decide to (even though this geometry was at first marked as 'static').


This simple preprocessing would greatly improve the performance for scenes like scene6 and Sponza, two scenes that perform really bad for me (i.e., (far) less than 50% of the kd/sah performance).


Of course, it would be even better if this static geometry isn't touched at all when the BIH is rebuild for the next frame...
_________________
--------------------------------------------------------------

Whatever

(L) [2006/08/13] [Phantom] [Optimizing static data for BIH] Wayback!

I did some tests to see how much difference it makes to massage the 'static' data. The triangles in the input scene are recursively cut in half if their size along an axis exceeds a preset maximum size, which is the largest side of the scene bbox divided by a number that needs to be tweaked for the scene at hand.


All timings use a fixed camera angle and a single light source. Shadow rays are (of course) somewhat cheaper than primary rays. Timings do not include hierarchy build time.


Sponza:

No preprocessing: 76k triangles, 2834kray/s;

Splitting at 1/25th of scene bbox: 136k triangles, 3653kray/s (a 29% improvement).


Scene6:

No preprocessing: <1k triangles, 7776kray/s;

Splitting doesn't help, whatever the setting.


Cloister:

No preprocessing: 81k triangles, 3166kray/s;

Splitting at 1/23rd of scene bbox: 138k triangles, 4156kray/s (a 31% improvement).


FairyForest:

No preprocessing: 174k triangles, 3220kray/s;

Splitting at 1/20th of scene bbox: 177k triangles, 3274krays/s (a 2% improvement).


It's clear that 'difficult' scenes (except the low-poly scene6) benefit; fairyforest already is OK for BIH so it barely helps.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/08/14] [Michael77] [Optimizing static data for BIH] Wayback!

What about a more easy approach: When creating a leaf during construction of the BIH, first cut off empty space and then simply do some additional splits with the two splitplanes always being identical where you don´t check against the center of a triangle but agains its edges, like in a kdtree. in fact this would mean, you simply create a kdtree for these triangles within the BIH. You wouldn´t need to change anything except the leaf creation. Of course, the only drawback would be on memory consumption, but I guess you could set an upper limit very easy (like a maximum of 3 additional subdivision steps).


Michael

(L) [2006/08/14] [Phantom] [Optimizing static data for BIH] Wayback!

The problem with that is that it makes the build more expensive. I wanted to do one-time only preprocessing of data that will generally be static. The scheme I tried allows for changes to the 'static' geometry, albeit at a slightly higher cost than 'dynamic' geometry. Suppose you have a Quake level with some large elevators: The level itself can safely be optimized, while the elevator mesh can be pre-split to make it more optimal during construction. The elevator is typically only translated, and perhaps transformed; for this splitting has no (negative) impact.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/08/14] [Michael77] [Optimizing static data for BIH] Wayback!

Ok, this of coures only works if you know something about your scene. For a arbitrary scene where everything can be animated you will probably achieve better results with my suggested approach. Also, I don´t think build times will be much higher, although you need to calculate splits with the splitting plane. However, the number of large polygons will probably be very small so this will not matter that much. But of course this is just a guess at the moment, need to find some time to test it.