New idea?

(L) [2006/02/08] [Phantom] [New idea?] Wayback!

I've been toying with this idea in my head:

MLRTA only cuts off nodes before the first required branch (i.e., the highest common ancestor of all visited leafs). In some cases, this is great, in many other cases, it hardly matters. I'm really looking forward to tbp's EP search implementation, as I would like to know why mine sucks so hard. [SMILEY Smile]

Anyway, back to the topic: During EP-search, you do a kd-tree traversal, skipping any branch that can't be interesting (as it is outside the frustum). Suppose you would build an 'intermediate' kd-tree, with just the relevant nodes. In the end, you would have a small tree, only suitable for traversing rays inside the current frustum.

This has one immediate advantage: The intermediate tree is much smaller, and build while traversing, so nodes are in perfect memory locations (i.e., right next to eachother instead of kilobytes away).

But you could do more. Any traversal step that can only lead to the left node or the right node could be collapsed. That way, any traversal path will be reduced to a much smaller one. Problem is of course the t-near and t-far calculation, as this is typically calculated incrementally during traversal.

Perhaps the cache optimization alone is worth it... Need to think. [SMILEY Smile]

- Jacco.

(L) [2006/02/09] [tbp] [New idea?] Wayback!

Memory bandwidth is a scarce ressource on a PC, so when i read that i wince.

But if i remember the real storm guys said, in an obscure article i've lost ref to, they were doing all kind of runtime rewritals on their bsp trees. I remember i winced back then too. I can't remember details, but they were like really rewriting it on each frame or at least editing it etc... and it seems it worked somehow.

(L) [2006/02/10] [toxie] [New idea?] Wayback!

First of all: I follow your discussions here on a regular basis and its pretty interesting indeed!

I really appreciate seeing what other people achieve with their rtrt-engines!

About the rebuild per frame: I wrote a "plugin"-rtrt-renderer for Quake II (the original, not a selfmade thingie like the Saarbrücken-Quake III)

and it's no problem to rebuild the full(!) kD every frame actually (without using ANY pre-clipping done by the original QII-engine). You can check out the result in this talk (it's also features other interesting things, btw. [SMILEY Wink] ) held at the breakpoint2005-demoparty: [LINK http://breakpoint.untergrund.net/2005/download.php?dir=2005/after_the_party/seminars/&file=bp05_seminars_-_Prof_Dr_rer_nat_Alexander_Keller_-_To_trace_or_not_to_trace_-_that_is_the_question_-_xvid.avi xvid-links]

I'm afraid that i cannot release the source (or even the dll's) because of third-party-rights, so you need to trust the results in this video. [SMILEY Sad]

(i could also upload a realtime-screengrab of the game if you like)[/url]

(L) [2006/02/10] [toxie] [New idea?] Wayback!

There is no view-dependent stuff in the QII-kD-builder.. It's the EXACT same kD-code that i also use for my Global Illumination stuff or massive scenes..

The only trick we use is not to use expensive stuff such as SAH.. [SMILEY Wink]

And the geometry in QII (including ALL level-triangles, ALL enemies and other stuff) is about 20-50k tri's per frame (depending on level),

as I don't allow QII to do any pre-clipping (cause we defined some triangles refractive and/or reflective, so there's no

way to tell which geometry can be clipped away SAFELY)..

(L) [2006/02/10] [Phantom] [New idea?] Wayback!

Quite impressive stuff. 512x384 with shadows and reflections at 5-10fps is not bad at all, especially considering you're also building a tree in that time and the fact that this tree is far less optimal than the trees we're using. Are you using a 'normal' Wald-style packet ray tracer, or did you use significant other tricks to speed up the rendering?

(L) [2006/02/10] [toxie] [New idea?] Wayback!

I wouldn't say that the tree is less optimal.. Compared to Wald's numbers and especially the real-life

measured OpenRT-Performance (i d'loaded the non-commercial version) our

rtrt-renderer is 2x-3x as fast (using a simple primary-ray-only-shader) and uses only 1/2 to a 1/3 of the memory for the kD.

I don't use special tricks for the Shaders, just normal 2x2 (in QII it's actually 4x1 [SMILEY Wink] ) ray-packets.

I also tried to use the shaft-culling-paper (MPI: Faster Ray Tracing with SIMD Shaft Culling) but the results

weren't really what i expected (just some 10%-20% faster), which is especially shocking for QII (features HUGE triangles).

(L) [2006/02/10] [toxie] [New idea?] Wayback!

I never tried that one specifically, simply because i think that it is WAY too unflexible (think of global illumination or refraction).

As soon as your rays are not implicitly defined by a regular grid, the whole thing is doomed (=expensive to split the huge frustums into smaller ones if the rays are kinda "random" in that frustum).

(L) [2006/02/10] [Phantom] [New idea?] Wayback!

I agree that it doesn't fit too well on anything but primary rays. On the other hand, for primary rays it's quite good if it delivers what they claim (I'm very busy trying to reproduce their results). I think it's harder to get it to work for shadow rays (I believe they use a second pass over the entire screen to make it work somewhat), but for reflections it should be quite applicable. If you get a 2-3x speed increase on primary, reflection and refraction rays, I think you're doing quite well. Obviously it won't help GI but then again, you're not doing GI in the Q2 demo.

(L) [2006/02/11] [Phantom] [New idea?] Wayback!

Toxie: I just had a silly idea while smoking a sigarette: If you insist on bulding the kd-tree every frame, wouldn't it be an idea to do the kd-tree building 'on demand'? I mean, you do the first one or two splits always, but the other splits only when you actually traverse a node. So, when you encounter a leaf with more than x triangles, you subdivide and resume rendering.

(L) [2006/02/13] [Guest] [New idea?] Wayback!

fpsunflower: The paper was submitted last year and appeared recently in "Monte Carlo and Quasi-Monte Carlo Methods 2004". I'll try to make it available for download on our server soon.

As for the split point: I'm afraid that i'm not allowed to talk (yet) about that issue. [SMILEY Sad] But be sure that it will be released as a paper and/or my PhD "soon".

Phantom: Building the tree on demand surely helps. I already implemented that and it works wonders for huge scenes like the PowerPlant, but will not help the QII-Renderer (this beastie is bounded only by ray tracing/shading, the kD-tree builder alone (=no tracing/rendering) peaks at 80-90 rebuilds per second).

(L) [2006/02/21] [craouette] [New idea?] Wayback!

great video...

confort me in my idea that things should be rendered in layers:

first, the primary rays, no shadows, but only hit points with surface properties, and normals.

Then, for each light, for each hit points, shadowding (going from light to hit points should preserve as much as possible the coherence), then lighting.

I'm not sure yet if the reflection/refractions rays should be made in another pass or with the primary rays... will test.

craouette

(L) [2006/02/21] [Phantom] [New idea?] Wayback!

That's not what I do, I trace a packet (or single rays in some cases) and if they hit a triangle, I check lights. I see your point of better coherency by tracing primary rays first, but I'm a bit worried about the extra bookkeeping introduced by postponing secondary rays.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/02/21] [tbp] [New idea?] Wayback!

Doing deferred shooting/shading/etc might be worth the hassle and memory bandwidth cost if, for example, you expect a low coherency and you're trying to packetize. Or if running on a NUMA multi processor box (to avoid hitting the same spot from different cpu at the same time).

Like Jacco pointed out, that's likely to not be a win for primaries or even shadow rays.

New idea? back