Packet Based Ray Tracer

Project Proposal

SUMMARY

I will implement a ray tracing algorithm that uses packet-based traversal techniques and relies of high quality SAH-based bounding volume hierarchies.

BACKGROUND

Ray Tracing is a technique for generating an image by tracing the path of light through pixels in an image plane and simulating the effects of its encounters with virtual objects. Ray tracing is capable of simulating a wide variety of optical effects, such as reflection and refraction, but at a higher computational cost than other algorithms like rasterization.

Individual light rays are shot from the viewer (the eye, or the pixel ) into the scene. When a ray hits a surface, it can suffer up to three phenomena: reflection (the ray direction is changed so that it returns to the medium from which it originated, for example, for mirrors), refraction (the ray ‘bends’ due to a change in the medium it is traversing ) and or shadow. To further avoid tracing all rays in a scene, a shadow ray is used to test if a surface is visible to a light (trace a direct line to each light source and test intersection with opaque objects in the scene). In case it is, the light contributes to the object’s color and the reflected/refracted ray is recursively traced through the scene, otherwise the object is in shadow for that light source.

Since ray tracing follows the laws of physics, very photo-realistic images can be produced with it and there is increasing interest towards making the algorithm and the building of data structures it uses fast enough to be in interactive and real-time applications.

THE CHALLENGE

Packet Based Traversal

• Correctly modifying my existing ray-tracing code to use SIMD intrinsics for packet-based traversal. Debating about whether to use ISPC or directly using Intel’s provided instructions.
• Choosing a method to bunch rays together to create packets in a way that maximizes packet utilization.
• Divergence caused by different rays within a packet interacting with the scene in different ways could severely affect performance. Ray re-ordering within a packet could potentially help.

Fast BVH Build

• Working with the different amounts of parallelism available in different stages of the BVH build
• Tuning threshold to switch between horizontal (across triangles) and vertical (left and right child) work sharing

RESOURCES

My starting point will be the ray tracer I implemented in 15-462 (Fall 2015). I’ll be following suggestions for parallelizing an SAH-BVH build given in Wald’s On fast Construction of SAH-based Bounding Volume Hierarchies and Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies for packet-based ray traversal.

GOALS AND DELIVERABLES

Packet Based Traversal

• Compare the performance of different packet sizes.
• Compare the performance of different vector-widths (AVX, SSE, IMCI on the Phi).

Fast BVH Build

• Compare amount of time required to construct the BVH for different types of scenes.
• Compare speedup achieved with different number of cores.

Stretch Goals

• Ray re-ordering within a packet when unreasonable amount of divergence is detected.

PLATFORM CHOICE

I’ll be using the new Gates machines to test AVX (8 wide vectors) and SSE4 (4 wide vectors) vector instructions and the Xeon Phi on the latedays cluster to test IMCI (16 wide vectors). Since each individual core on the Xeon Phi is comparatively slower than the Intel Core i7’s in the new gates machines, I expect to observe a drop-off in performance for the BVH build part of the algorithm.

SCHEDULE