Run tests with barcelona file. With the master it rendered in 1min 14sec using 1052MB, with the patch it's rendered in 58sec and used 1118MB on GTX1080.

I didn't have time yet to review the code. But it would be cool if we could avoid duplicating the code between CPU and GPU and volume and non-volume cases, with all these special cases it becomes difficult to maintain. Could all these ideas be combined into a single algorithm that works on CPU and GPU?

Out of order shader evaluation could work well on the CPU too. Depending on the scene it might be faster than the sorting we do now, if a shader evaluation returns an opaque result and BVH traversal can be terminated early. For example texture mapped tree leaves could be 75% opaque and you'd get a 75% probability of being able to terminate on the first intersection.

And perhaps that could be combined with the second idea, doing immediate shader evaluation for surfaces while recording volume intersections to be evaluated afterwards or as soon as complete volume segments are found? That would let you skip volume shading if an surface shader evaluates to opaque first.

It's not always ideal though, the failure case for immediate shader evaluation is if you have e.g. a character with transparent fur next to an opaque wall. In that case it can be better to wait with shading until the opaque intersection has been found.

Even if we do need different algorithm on CPU and GPU, perhaps the bvh_shadow_all kernel can be replaced by this callback kernel + a callback function?

Nice speedup. Is there a technical reason why it's done only for CUDA?

@Brecht Van Lommel (brecht), the duplicated code is indeed annoying, but i don't really see how can we avoid duplication between CPU and GPU.

From the performance point of view, on CPU it might be faster to record all intersections at once (from a single BVH traversal) and then deal with that rather than doing things from a callback which can't be inlined. Note: we can easily avoid qsort()on CPU if we know there is no volumes in the scenes.

Now, annoying part continues on GPU as well. There callback-based approach is some reasonable percent (around ~5% AFAIR) slower than recording all intersections (well, limited amount of intersections, the ones we limited to 16 atm). So this part we might re-iterate on GPU as well and always do things like shadow_blocked_transparent_volume_all_static when having few transparent bounces.

OpenCL is even more tricky. I didn't check specs in details, but just trying to compile callback-based BVH traversal crashes my video driver on linux. So here we can't do much at this moment i'm afraid.

So the only way to avoid much duplication i see is to have some #include'ed "template" several times with different define flags. That way we can avoid duplication of shadow_blocked_transparent_volume_all_static() and CPU's shadow_blocked() at least. And also should be possible to avoid duplication of shadow_blocked_transparent() when not having callback BVH traversal and shadow_blocked_transparent_volume(). Sounds a bit tricky, but in practice should be rather straightforward implementation.

@mathieu menuet (bliblubli), CPU is already close to ideal performance here, OpenCL does not callback functions, so the ideas implemented in this patch do not apply here as well.

Perhaps we can record the first N intersection on the GPU, and then do a second/third/.. intersection in the hopefully rare case it's needed? That could also share most code with the CPU, the difference just would be the limit on the max number of intersection to store.

I don't think the memory usage increase would be too bad even if you store e.g. 32 intersections (32*6*4 = 768 bytes). If you compare that to other memory usage (D2023#46333), it's not that much, and we can with that back elsewhere with optimizations like D2023.

Just run some quick tests with D2249 applied and had same render time speedup but overall had 100MB improvement in memory usage (improvement comparing to master branch). So ti is a win-win actually.

With D2247 applied the improvement can be even more on Maxwell, but for some reason that BVH change brings nothing to Pascal.

Now, as for the moving forward.

Surely it is annoying to have memory bump, but we can use lower stack storage on GPU. Having 32 stack intersections will bring us to the same memory bump as adding extra BVH traversal.

And being evil: this patch gives nice transparent shadows speedup (at least on Pascal, i still didn't hear anything from Maxwell benchmarks, but 32sec vs 1min33sec i've got here is cool). So we can just accept few % slowdown in D2247 and one of the closure patches (surely we cant' apply both of them, which one we use to move forward i don't care that much. whatever looks less crappy).

Thoughts? :)

Results are mixed here with Linux and CUDA 7.5, excellent speedup in the Koro scene but also some slowdowns in others. I'll try to narrow down where the issue is.

I have experimented in the same direction. My code was using shared memory, which should in theory be faster than global/local memory. As Brecht mentions, moving through shadow in steps of N intersections at a time could make this work for arbitrary shadow depths. One would need to find the N closest intersections then, which I would try by keeping the intersections in a sorted heap (similar to Jensen's photon mapping code). Then sorting and volumes should also be doable.

This is getting interesting. Tracing additional PATH_RAY_SHADOW_OPAQUE ray and testing whether intersection is transparent or not prior to call of shadow_blocked_all() seems to solve the majority of the slowdown on classroom scene (there still might be barely measurable one here).

Here is a quick patch for that:

Yet the patch is still making koro.blend really faster.

Now, why is it so:

• First guess was that it's the order of switch() and for() in the traversal functions (bvh_traversal does loop inside of a case, shadow_all does it other way around). But applying updated version of D830 (to minimize amount of duplicated code) and swapping order of switch() and for() did not change anything . D830 on it's own seemd to not give any measurable difference here in fact.

• Second guess was that it's the difference in the way how we invoke traversals. For some reason, scene_intersect foes not check for kernel_data.bvh.have_instancing on GPU and always uses bvh_intersect_instancing() if __INSTANCING__ is defined. Changing this for scene_intersect_shadow_all() again did not give any measurable; speed difference.

Running out of ideas here what could be a reason why extra ray cast makes things faster here and wouldn't mind having second pair of eyes here.

It seems that there is a difference between CPU and CUDA currently, and this patch fixes it.

CPU	CUDA before	CUDA after

I'm still seeing a slowdown in the classroom scene though.

@Brecht Van Lommel (brecht), indeed there's something with shadows on CUDA. I think it's because of the ray is pushed too far away at some point when doing stepped traversal.

What was the GPU you've tested performance? Did you apply snipped from my comment above?

The above times are without the snippet above. With the snippet I can confirm the slowdown is gone on the other scenes, but Koro renders wrong. This is using GTX 1080 on Linux.

Getting quite interesting. Definitely i had no such a bug. Having similar setup (1080 on Linux). Will dig deeper next week!