Archived

This topic is now archived and is closed to further replies.

thebigMuh

Extreme Raytracing

Recommended Posts

Hullo everybody! I''m still writing on my (very basic) raytracer. I''ve optimized hell out of it, but somehow it''s still not quite where I want it. I''ll give you the big picture, so you can see where I''m headed with this: The basic purpose behind this raytracer is to detect intersections. Given a point in space and a direction, I want to get if there is an intersection within a certain distance, and if there is, I want to get the distance to the intersection. Since this sampling is done multiple times per final pixel (think of 30-250 times), the number of sampled pixels is generally in the 640x480 to 2000x2000 range, and the scene complexity is somewhere between 50.000 to 5.000.000 faces, it should better be fast. I''ve implemented a bsp tree as acceleration structure. I''m using axis aligned planes (faster intersection calculation), and I''m using the linear voxel walking technique (determine closer half, walk this first, and only do second half if no intersection detected). The tree intersection routine is stack based (iterative), not recursive, as the constant push/pop/call/return flood took away quite a lot of performance. The triangle intersection routine is not implemented with Möller''s algorithm (without plane equation, using U/V coordinates), but with a barycentric approach (I have the reciprocal of the face''s area and the plane equation prestored for each tri - memory is not _that_ important) for various reasons. Now, here are some thoughts for further optimization, maybe you could tell me your ideas: 1.) Implementing a different triangle intersection scheme (Möller''s). The triangle intersection stuff makes about 50% of the total calculation time required in my tracer. I''m not sure if Möller''s approach would improve or worsen performance. The plane-equation approach gives me the distance to the (possible) intersection quite early on, which gives me quite a lot of early-outs (remember, I''m only tracing a certain distance within space!). Möller''s approach is faster in determining if a ray intersection lies within the triangle or not, but I would have to wait quite long within the routine to be able to calculate the distance to the intersection point. 2.) Implementing a different acceleration structure. The bsp tree is easy to implement, however to be able to reduce the face count / node considerably, I have to use tree depths of 15-30 levels. The tree walking part eats about 30-40% of my total calculation time. I''m quite sure that a hybrid grid acceleration structure would speed up things considerably, but it''s a lot to implement, so I would like to hear your oppinions beforehand. Also, this would need a good (and fast) triangle-box overlap testing function (and I don''t have one, nor do I have an idea how to go about writing one). 3.) Maybe something entirely different? I might really be missing something here, maybe one of you has a cool idea? Thank you for your participation Ciao, ¡muh!

Share this post


Link to post
Share on other sites
quote:

The bsp tree is easy to implement, however to be able to reduce the face count / node considerably, I have to use tree depths of 15-30 levels. The tree walking part eats about 30-40% of my total calculation time.



Instead of using a pointer implementation for you BSP, you could implement it as an array. Each node is an array element. For the n''th element, its children are the 2n+1 and 2n+2 elements. If your tree isn''t well balanced, you will use more memory than you actually need but parsing the array should be faster than using pointers deferencements.

Share this post


Link to post
Share on other sites