Something that has been bugging me for too long, so I had to start working on it.
Let's face it: Ray tracing is awesome :). Back in the day when I did my msc thesis my supervisor showed it to me: it was the first time I had really looked into it - I also saw OpenCL and GPU programming for the first time. I wrote a (judging with the knowledge I have today) crappy ray tracer for physics simulations for my thesis and passed.
But this christmas I wanted to redo it with what I've learned since then, and I wanted to do it for CG. Many articles I've read seem to point to one of the issues being: That it IS possible to use ray tracing as the primary rendering method for a somewhat simple but still interactive 3D game, but the cost of rebuilding the search trees/acceleration structures every frame is too high.
The overall cost of rendering a scene by rasterization is about O(n), where n is the number of objects/triangles/you name it. In ray tracing, supposedly, you should be able to achieve < O(n), but this is all broken because when scenes are animated/interactive, objects move and their acceleration structures must be rebuilt, supposedly every frame...If that rebuildling cost could be moved to <= O(n) while also keeping the tracing itself to < O(n), then ray tracing could possibly challange rasterization sometime in the future.
Given that this is a pretty heavily researched subject and that dozens/hundreds of smarter people than me are working on it daily (while I'm doing it when there's some extra spare time) it would be unwise to claim that the ideas I present here are new and revolutionary ;).
Insert question:
Why on earth would you want to rebuild the entire world's acceleration structure each frame?
Ok.......it's conceptually simple to code an implementation with just triangles and kd tree partitioning, or some general bvh method, whatever....what is to say that there is a universal super solution to everything - why should raw triangles in an acceleration structure be the key? (Just to make it clear I'll believe in voxel solution when I see a good one with shadows/reflections etc working decent in a dynamic game environment)
Ok. But anyway, let's propose a first method of solving the heavy acceleration structure rebuilds: Let's just have 2 acceleration structures which will be traversed in parrallel - One for dynamic objects and one for static (in all likelyhood, at least the first generation of ray traced games will have most of their scene's shapes static - like the majority of todays rasterized games!).
Another possible solution (which I've been experimenting with) is a simple variant of multi level acceleration structures: Top level structures enclosing instanced sub spaces/acceleration structures with their own rotated/translated/skewed/lalala coordinate systems.
Example: You have a top down game with for example a game like Diablo's POV. Imagine a coarse top level acceleration structure/grid which holds only references to models placed in it, and that each ray hitting a model then subsequently traverses the particular space/acceleration structure belonging to that model, with the transformations for this particular model instance. The second level structure may be of any kind (kd, grid, bvh etc), the ray initially only needs to know (e.g. in 1st pass for breadth first) that that particular sub space has to be traversed. One could add (e.g. for parts of models beloning to one bone in an animation skeleton) or remove levels as needed. Models could have pregenerated acceleration structures.
Also, I stumbled across some DAC(Divide and conquer) ideas for ray tracing, where acceleration structurs are built on demand, which would fit nicely into this, as you could generate coarse top level structures often and the lower level ones on demand (dynamic model complexity also comes to mind here)..
Anyway, all talk, here's my experiment in action:
http://www.youtube.com/watch?v=dSTfNg-uCqk
16 Stanford bunnies at 100 fps @ 1080p with shadows. OK that is actually a static scene with a single moving light source, but you'll have to trust me or just implement it yourself - that code uses a single bunny instanced 16 times in a coarse grid. The rays which intersect any models are transformed to that particular second level acceleration structure's coordiante system and continue from there.
The whole scene has about ~250k triangles, but is rather simple because most rays hit nothing at all.
Inga kommentarer:
Skicka en kommentar