Empty space cutoff back

(L) [2006/03/14] [Phantom] [Empty space cutoff] Wayback!

I was trying to fix my kd-tree compiler so it properly handles flat cells, so I kicked out all non-essential stuff. I was wondering: Should a 'perfect' SAH kd-tree compiler automatically cut off empty space? In other words, is the commonly used approach of cutting off empty space merely a way to speed up the compilation, or is it really required? I'm asking because my compiler (without empty space cutoff code) returns trees that render significantly slower... So should I look for a bug or is this normal?
_________________
--------------------------------------------------------------

Whatever

(L) [2006/03/14] [tbp] [Empty space cutoff] Wayback!

Your question is rather strange. A kd-tree partition space, as such an empty cells are the cheapest of all. And depending on view etc, most ray may only visit such cells. To convince yourself, step thru a typical traversal [SMILEY Wink]


edit: Copy & paste from the other thread, those are stats for building the Mengel sponge scene, with all those cubes.

build::build: 11.092 seconds for 1920000 tri, nodes 1349593, leaves 674797.

build::build: stats: max lvl 24, 2029534 items, 460030 empty leaves ( 68%), 12 max items per leaf.

flat::flatten: allocated 10.297MB for nodes and 7.742MB for triangle ids.


Note that empty leaves (space cut) represent 68% of all leaves in that tree.

(L) [2006/03/14] [Phantom] [Empty space cutoff] Wayback!

No no you don't get the problem.


What I was wondering is this: Is the spot where you do the empty space cutof also the best scoring spot if you would simply let SAH decide? I was not planning to leave empty space alone, I was wondering if a good SAH compiler would find it automatically, abeit at a higher processing cost than a special threathment.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/03/14] [tbp] [Empty space cutoff] Wayback!

Ah sorry, i'm tired [SMILEY Smile]


Still it doesn't make much sense, unless you're talking about empty space being in the middle of 2 triangle blobs.

Or i should refrain from posting tonite ehe.

(L) [2006/03/15] [craouette] [Empty space cutoff] Wayback!

from what i had experienced, this doesn't work; Empty space are not dected by SAH. The best split is found not far from ther, but including a few triangles...

remember, the split is between the median and the barycenter... empty space are on the borders!

(L) [2006/03/15] [Phantom] [Empty space cutoff] Wayback!

I read somewhere that empty space cut-off should start at 33.3% of the node, from either side, so you must be right: That can't possibly be between the median and barycenter. Thanks for clarifying. [SMILEY Smile]
_________________
--------------------------------------------------------------

Whatever

(L) [2006/03/15] [Phantom] [Empty space cutoff] Wayback!

Ah I found some very severe problems with my compiler. Basically, the empty space cut-off was saving my ass somewhat; yesterday I made several fixes that made it produce trees that render just as fast as the original version - But I didn't even put the empty space cut-off back... Compile times went down considerably, the code is much smaller, and I can handle flat cells now. I'm very short on spare time right now, but as soon as I put back the parts together I will post some new scores, and I will post the updated source code for the compiler.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/03/16] [fpsunflower] [Empty space cutoff] Wayback!

Here's what I did today: a little kdtree dump method which writes out the non-empty leaves as colored cubes into an obj. You can then load that up and explore with your favorite viewer.


[IMG #1 ]

[IMG #2 ]

[IMG #3 ]

(buddha kdtree was generated with a really high threshold for leaf creation to keep the number of nodes down)



I've already found one pretty major bug in my code thanks to this. I think its gonna make a great debugging tool. Once you have the dumping routine in place, its easy to add different filtering / coloring methods to view just what you care about.



But more on topic (I thought of this when I first saw my trees with this tool):


Your kd-tree code has a check at the top (or right before recursion) that goes something like:

---

[IMG #1]:
[IMG #2]:
[IMG #3]: