Fastest AABB-ray test today?

Practical and theoretical implementation discussion.
Post Reply
toshiya
Posts: 22
Joined: Tue Apr 03, 2012 1:42 pm

Fastest AABB-ray test today?

Post by toshiya » Mon Jan 27, 2014 3:00 pm

I am currently using the "optimized version" of this method:

http://people.csail.mit.edu/amy/papers/box-jgt.pdf

but I started wondering if it sill is an efficient approach today because of the number of conditional branches. For example, I've tried to add some early-outs based on the distance along the ray found so far, but it's slower than the original version.

I am also curious how a SIMD implementation for single-AABB and single-ray performs. My experience is that, for single-AABB and single-ray, using SIMD is actually a bit slower due to horizontal ops, which apparently would be different with today's architectures.

I am thus not sure what would be "the" fastest approach today. Can someone share your wisdom and experience on it?

patrickwalz
Posts: 3
Joined: Tue Jan 28, 2014 7:14 pm

Re: Fastest AABB-ray test today?

Post by patrickwalz » Tue Jan 28, 2014 7:23 pm

While this isn't exactly a direct answer to your question (as it is not is not directly a RAY/AABB test), I assume you are using this with a tree structure. I recently came across the paper "Ray-Box Culling for Tree Structures" which claims to accelerate tree structures pretty well with just a simple modification. Hope this at least somewhat answers your question.

http://www.iis.sinica.edu.tw/page/jise/ ... 67-ERB.pdf

graphicsMan
Posts: 160
Joined: Mon Nov 28, 2011 7:28 pm

Re: Fastest AABB-ray test today?

Post by graphicsMan » Wed Jan 29, 2014 12:32 am

Hi Toshiya -

I found that the for loop version referenced here
http://tog.acm.org/resources/RTNews/htm ... .html#art7
(the one that Eric discussed with Solomon) was quite fast. I think I made some small tweaks to that version, but it was substantially the same. It turned out to be the fastest mono-ray mono-box test that I could find.

patrickwalz
Posts: 3
Joined: Tue Jan 28, 2014 7:14 pm

Re: Fastest AABB-ray test today?

Post by patrickwalz » Wed Jan 29, 2014 1:20 am

Have you by chance looked at the paper "Ray-Box Culling for Tree Structures"?
http://www.iis.sinica.edu.tw/page/jise/ ... 67-ERB.pdf

toxie
Posts: 118
Joined: Mon Nov 28, 2011 12:30 pm
Location: germany
Contact:

Re: Fastest AABB-ray test today?

Post by toxie » Wed Jan 29, 2014 10:33 am

The idea from the paper isn't so bad in itself (shift work from the tree construction to the actual traversal, and improve upon the number of intersection tests as a bonus), but the additional storage for the BBoxes of the triangles is a bummer.
Did anybody implement this already in a "modern" ray tracer (GPU or SIMD based)?
Better you leave here with your head still full of kitty cats and puppy dogs.

patrickwalz
Posts: 3
Joined: Tue Jan 28, 2014 7:14 pm

Re: Fastest AABB-ray test today?

Post by patrickwalz » Thu Jan 30, 2014 6:01 am

apologies for the double post - wasn't aware posts had to be approved and just couldnt figure out why nothing would go through

jbikker
Posts: 202
Joined: Mon Nov 28, 2011 8:18 am
Contact:

Re: Fastest AABB-ray test today?

Post by jbikker » Thu Jan 30, 2014 8:33 am

patrickwalz wrote:apologies for the double post - wasn't aware posts had to be approved and just couldnt figure out why nothing would go through
Just the first one or two posts, so the security will not bother you from now on. It's inconvenient, but it got the spam down to almost zero.

toshiya
Posts: 22
Joined: Tue Apr 03, 2012 1:42 pm

Re: Fastest AABB-ray test today?

Post by toshiya » Thu Jan 30, 2014 10:51 am

Thank you for the replies!

I managed to slightly speed up mine (whopping 2%...) by following this code:

http://tog.acm.org/resources/RTNews/htm ... .html#art9

which uses a fewer branches as I suspected it should be. The article posted by graphicsMan (which links to the above) concluded that one should not spend time on optimizing ray-AABB tests anymore, but in some renders that I wrote, ray-AABB tests end up taking non-negligible amount of computation time, so I really wanted to see if I can speed it up. Perhaps we need a completely different algorithm to achieve further speedup.

As for the paper pointed by patrickwalz, while I agree with toxie that the idea is good, I don't know if it improves the overall performance. It seems that the point of this paper is to make a tree with many triangles per leaf not that slow - we wouldn't use such a tree to begin with for static scenes. I am also curious if it does something with a more modern ray tracer, such as those based on HLBVH.

Post Reply