Ray Tracing News v23 n1 is out

July 20, 2010 in Miscellaneous by Eric | 2 comments

Just in time for SIGGRAPH (so I wouldn’t get those “when’s the next issue coming out?” questions), here it is.

Tags:

  1. Shadow007’s avatar

    Shadow007 on July 21, 2010 at 5:35 am

    Hi Eric,
    Just had a quick read at RTNews v23 (will do a more in depth later though) …

    Regarding your Branch Predictions idea, it must be a coincidence (or a fluke who knows), because I had that passing idea a few days ago too, but didn’t go as far as you did, and had thought about tracking the count of going each way at each split, which would have been way too complicated/difficult especially with multiple threads/cores.

    Regarding the “flattened hierarchy” limitation, you could get around that by finding an astray bit somewhere in the node and using it to store whether the children are inversed or not.
    If no astray space is found in the nodes structure, we can imagine an “inversion” map, storing that inversion bit for each node.

    We could also imagine each thread/core having its own “inversion” map, getting rid of their “competition”, but which would also lose any “cooperation” between them.

    However, what I realized this morning is that you could also optimize at the leaf level, by bubbling (swapping them with the previous one in the leaf) the primitives which are hit by a ray. Using this, highly “occluding” primitives will be stored (and tested) first in their leaf, which may improve shadow ray tests(by simply diminishing the number of intersections), and marginally other rays on platforms (CPU) where a distance based early out is used.

  2. Eric’s avatar

    Eric on July 21, 2010 at 7:05 am

    Thanks for the comment – I’m glad to see someone’s reading my random ideas.

    Great minds think alike (and so do ours ;-> – nobody likes that joke, I really should stop using it): you can definitely ‘bubble’ at the leaf level, too, and that’s true for *any* efficiency scheme where there is a list of objects per leaf/cell/etc. – whatever got hit, put it first (what you do with multiple hits in a list is up to you). I actually tried this out long ago in the early 90′s, but it was mostly a wash, for some reason (I think I “swapped with first” on any object intersected, so maybe that was too many swaps) – I guess that’s why I never mentioned it in the RT News (or maybe I did, but can’t find it now). Swapping pointers is quick enough, though doing this seems problematic in a multiprocessing context, as the whole list has to be locked to reading by other processors while you do the swap. Which is why I like the binary nature of most BVH schemes: swapping the first and second child box is a nice atomic operation, just flipping a bit. Plus it percolates up the hierarchy, so something like a large occluder will eventually be the very first real object you test, i.e., it’ll be the first thing found in the hieararchy.

    Flattening the hierarchy (to my mind) is just that, you basically put jumps in (“if this box is missed, jump past its contents to the next box on the list”), so I’m not sure how you would get past this list-like structure. A list saves time by avoiding any need for recursion: you’re alway just going to the next element or jumping further down the list, never pushing or popping. Lists mean you can’t really do any decision about which child to test first, since it’s locked down. I guess you could have a list with more jump “commands” – “always jump here next” – so that you could do swaps, but that seems to lose the efficiency of the list itself.

    It’s interesting to have each core keep its own inversion map, that would get rid of any locking problems. However, it comes at the cost of (a lot of, I think) memory, always a bad thing.

    For more hierarchy ideas, I like my old and little-known “Efficiency Improvements for Hierarchy Traversal in Ray Tracing” in Graphics Gems II, mostly summarized here http://tog.acm.org/resources/RTNews/html/rtnews9a.html#art5. Things like making a single candidate list for all eye rays seems like a win no matter what. A candidate list is the idea of taking a point in the environment, i.e., the eye’s location, and opening up whatever boxes it’s inside in advance, once, making a list of all the objects and boxes left to test, perhaps sorted by distance. A very basic use of coherence, and many researchers have done much more elaborate eye-ray acceleration schemes, but it is easy to implement.

    This is all fun to think about; the costly part is sitting down and testing these ideas to see if they actually help. And of course everyone’s mileage varies. Anyway, feel free to email me if you want to continue to chat.