fast kd-tree building

(L) [2006/04/04] [playmesumch00ns] [fast kd-tree building] Wayback!

Looks like a nice presentation on the algorithm, but I've never come across a more opaque pseudocode notation before! Can anyone translate one of the functions for me, or direct me to some reference?

Also, he mentions at the start that if a triangle is completely in the split plane, the correct solution is to have two empty cells, and one flat, nonempty cell. Does this mean from the original cell A, you have two children, B and C, then one of these children, e.g. B has one empty child, D, and one flat, non-empty child, E?

A

(L) [2006/04/04] [tbp] [fast kd-tree building] Wayback!

He insists on doing all 3 axis at once, for sure that doesn't simplify the process [SMILEY Wink]

If i remember correctly the case you're citing is really about a planar triangle sitting in the middle of 2 empty spaces, so if your space cut heuristic is doing its job you should end up with both voids being cut and that lonely triangle embedded in a split plane.

But that's just one of the many corner case you have to check (others prominent ones being flat cells, almost degenerated triangles vs small voxels etc).

If you want code, then Jacco provided one implementation on that forum. Even if it lacks some features it's better than nothing.

Then i'm going through my nth rewrital, if everything goes as planned it should cut the amount of work by ~2 and require a smaller working set (wrt what's presented in that paper); i couldn't find any obvious flaw but i'll wait to have a working implementation before i brag about it [SMILEY Smile]

(L) [2006/04/05] [toxie] [fast kd-tree building] Wayback!

@tbp: off topic, but i've just read your stuff on the openrt mailing list: VERY good answer (you wanted to have access to erw6, etc.), that saved my day! Been laughing for the last 2 minutes!

btw: anyone reading this forum coming to breakpoint demoparty [LINK http://breakpoint.untergrund.net/] next weekend?!

(L) [2006/04/05] [tbp] [fast kd-tree building] Wayback!

I'm used to look like a fool in public, but this time and despite re-reading those emails i fail to see what was funny there. I think i need to get a brain someday.

And i won't be able to make it to the party, it's been a long time since i last went to that kind of event sadly. You'll be there i guess?

(L) [2006/04/05] [tbp] [fast kd-tree building] Wayback!

Ah. Hmm. How embarassing it can be to have your own sarcasm fly way above your head a couple of month after the facts.

I must admit that we-publish-results-that-nobody-can-reproduce-for-lack-of-both-source-code-AND-data attitude is really getting on my nerves.

That's why i must thank you again for your efforts in that other thread. I wish i could move to that party if only to harass you a bit more and maybe get away with some more details about your tech [SMILEY Wink]

(L) [2006/04/06] [toxie] [fast kd-tree building] Wayback!

You can also catch me at buenzli [LINK http://buenz.li/], TUM [LINK http://tum-party.org/], GeekCamp [LINK http://www.geekcamp.net/]

and maybe X [LINK http://www.scs-trc.net/x2006] [SMILEY Wink]

(L) [2006/04/06] [toxie] [fast kd-tree building] Wayback!

and btw: i'd love to post even more info about our stuff here or feature cooler datasets, etc. , but unfortunately i'm not allowed. [SMILEY Sad]

so just wait some more months.. [SMILEY Wink]

(L) [2006/04/06] [tbp] [fast kd-tree building] Wayback!

Back on-topic, i got my segment/linked-box idea kinda working.

armadillo: 0.656s sort + 2.562s compilation.

buddha: 1.5s sort + 7.578s compilation.

That's with a 2.6ghz opteron allowing for straight comparison with the paper.

My splits are not completly perfect and i'm sorting via STL, so take those figures with a hefty grain of salt. Still, there's some hope.

(L) [2006/04/07] [tbp] [fast kd-tree building] Wayback!

The same idea i've been ranting about pretty much since the inception of this forum [SMILEY Smile]

Algorithmically speaking it's equivalent to all those n.log.n approaches, Havran, Wald... nothing new here (but then Wald's paper doesn't bring anything new either). It's all in the details.

Unlike Havran and Wald, i'm not massaging single triangle extramae (call them boundaries or events, it's all the same), but pairs. Or put another way, segments. Or put another way, boxen (when you put 3 such linked pairs/segments together). While treating them in isolation is simpler, you do lose some information in the process, well it's not lost but not easily accessible, and it also goes against data locality and introduce bloat.

I also think scoring all 3 axis at once is not wise because there's too much to track; like i've already said somewhere there's fundamentally 3 zones/intervals on each axis: < split, == split, > split. There's no need to re-evaluate unless you cross into another zone. That remark also holds when composing the left and right nodes out of a split.

Nothing ground breaking, but it all adds up.

(L) [2006/04/07] [Xela] [fast kd-tree building] Wayback!

Guys,

In addition to kd-trees, Ingo has placed 2 papers describing 'other' acceleration structures on his site ([LINK http://www.sci.utah.edu/~wald/Publications/]).

There are also references to used models as well.
_________________
[Xela]

(L) [2006/04/16] [Phantom] [fast kd-tree building] Wayback!

Stumbled upon this one while looking for Szecsi's kd-tree implementation:

[LINK http://www.fsz.bme.hu/public/staff/szecsi/dyph.pdf]

And an ancient implementation by Thatcher Ulrich:

[LINK http://cvs.sourceforge.net/viewcvs.py/tu-testbed/tu-testbed/geometry/kd_tree_dynamic.cpp?rev=1.11]

Did anyone else experience some problems while compilng Toxie's tilted kitchen scene? My compiler tends to recurse till it's max depth in some cases on this scene.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/04/17] [Phantom] [fast kd-tree building] Wayback!

I'm clipping all over the place, so that can't be the problem. I'm not so sure though what tbp meant by the phrase "there's lots of clipping in that scene"?

The problem seems to have something to do with epsilons (which I wasn't using at all so far). To cope with this scene I added a max tree depth (but that's a hack, obviously), and the epsilon for flat cell testing (anything < epsilon is considered flat now, instead of anything '== 0').

I don't do any tests yet to see if splitting didn't help (i.e., left and right count remains the same after a split, no empty space cut-off). Perhaps that should fix some nasty trails of identical cells. Still feels like a hack though.

My new compiler compiles all scenes in a reasonable amount of time (compared to earlier attempts [SMILEY Smile] ). Didn't try the Tai Statue yet, but even that should work, with some swapping probably. Replaced bubble sort with quicksort. And guess what? It improved performance. [SMILEY Wink]
_________________
--------------------------------------------------------------

Whatever

fast kd-tree building back