what is the best data structure for pretty-tracers?

(L) [2006/06/07] [greenhybrid] [what is the best data structure for pretty-tracers?] Wayback!

Hey there,

I have a problem: I just implemented a kd-tree in my glass++-tracer (at the moment, that tracer just got spheres, I was focused on the fx of gi the last days).

Here's the scene:

[IMG #1 ]

I have some small spheres on top (radius I think is 2.5), and a big one (radius 80 or somewhat). Putting them into a kd-tree does not bring better performance.

Rendering small spheres, each with a more or less equal size, and hundreds of them, is cool (just a few seconds), the kd-tree performs max.

But when the radius becomes above to average, it becomes a battle.

Now my question is: what teh solution for kd?

And for this disscussion: would nested grids or other schemata be better for "pretty-tracers" which include higher-level objects like julia-sets, spheres, boxes et cetera?

EDIT: the big sphere is the bottom, that's implicated due the current spheres-only natura of my tracer. I just wanted to explitice it for those who overflow my image [SMILEY Wink]
_________________
[LINK http://greenhybrid.net/] | [LINK mailto:root@greenhybrid.net root@greenhybrid.net]

[IMG #1]:Not scraped: https://web.archive.org/web/20061004023253im_/http://root-engine.net/greenhybrid/images/glasspp_log_0018.jpg

(L) [2006/06/08] [Lynx] [what is the best data structure for pretty-tracers?] Wayback!

Well, that putting some 13 spheres in a kd-tree doesn't give you much isn't too surprising, is it? [SMILEY Smile]

What do you mean with "radius becomes above to average"?

I don't know what your kd-tree features. Clipping could also be applied to spheres, with many spheres whose bounding boxes intersect but not the spheres themselves this could help quite a bit i think...

In my limited experience, a kd-tree without clipping is very vulnerable to overlapping primitive bounds. It just stores lots of primitives in leaves that don't even intersect the leaf, and splitting choices also suffer from it.

And without SAH i had trees easily eating up all your 32bit address space on things like grass/fur (lots of thin objects (triangles) intersecting each others bounds) where the clipping SAH tree merey takes some say 200MB...

(L) [2006/06/08] [Lynx] [what is the best data structure for pretty-tracers?] Wayback!

hm i'd say you only need to store a sphere in a leaf if its surface intersects the bound, not if its volume intersects...if the node bound is completely inside, a ray crossing it obviously can't intersect with the sphere surface inside the node bound...

othwise, a clipping SAH tree performing much worse than naive arithmetic average splitting? Dude, smells like something's seriously wrong [SMILEY Wink]

(L) [2006/06/14] [greenhybrid] [what is the best data structure for pretty-tracers?] Wayback!

DAMN, found the bug, forgot to setup the aabb in the child nodes ... DAMN11111

EDIT: just dammit!!1
_________________
[LINK http://greenhybrid.net/] | [LINK mailto:root@greenhybrid.net root@greenhybrid.net]

(L) [2006/06/14] [greenhybrid] [what is the best data structure for pretty-tracers?] Wayback!

[SMILEY Embarassed] [SMILEY Embarassed] [SMILEY Embarassed] [SMILEY Embarassed]
_________________
[LINK http://greenhybrid.net/] | [LINK mailto:root@greenhybrid.net root@greenhybrid.net]

(L) [2006/06/14] [Lynx] [what is the best data structure for pretty-tracers?] Wayback!

Oh i had funny mistakes too...for example i allocated triangle_t's instead of *triangle_t's to store the prim pointers and wondered why the hell my memory usage is so high...(although, it still was not much higher than the old yafray kd-tree...)

And some other stupid stuff i already forgot [SMILEY Smile]

what is the best data structure for pretty-tracers? back