Return to Ray Tracing Assignment Overview
 

Just when you thought ray tracing was easy...you find that you can't render anything of any significance in your lifetime with a naive, brute force, ray tracer.  Here, I implement a hierarchal data structure based on bounding volumes to shorten render time of a large number of primitives.  After this code change, I can render a million spheres in under one minute where a brute force method would've taken hours to complete.

The images shown below are rendering of 100, 1000, 10,000, 100,000, and one million random spheres, respectively.  All spheres fit within the viewing space.  Lighting and shadows are still turned on.

All tests were done on a Dell desktop with an Intel Pentium 4 1.8 GHz processor with 1.0GB of RDRAM running Microsoft Windows XP.  Compilation was done with Microsoft Visual C++ Standard, Version 6.0 and the new Microsoft Visual C++ .NET Professional**.  Output size for each was 500x500 pixels.

For my classmates: I'm using STL's nth_element() to sort objects based on varying axes and only minor modifications to Pete's code.  Profiled code from VS.NET says that I spend 57% of runtime in box::hitbox() and 32% in bvhNode:hit.  Interestingly enough, the next most used function is fscanf() at 3.5%.

**Note: The standard version of VC++6 has no or little compiler optimizations. At the time of this writing, I've just obtained Visual Studio .NET.  VS.NET not only has an optimized compiler, but it can also optimize across .obj files for global optimization.  Note that the VC++.NET code is 38% faster than the VC++6 code for one million spheres.

100 Spheres
400x400 JPEG converted from 500x500 PPM output
 

File Parse: World Build: Render Scene: Write to File: Total:

VC++6 Standard 0.015 seconds 0.000 seconds 1.985 seconds 0.125 seconds 2.125 seconds

VC++.NET Pro w/opt 0.015 seconds 0.000 seconds 1.016 seconds 0.109 seconds 1.140 seconds

1000 Spheres
400x400 JPEG converted from 500x500 PPM output
 

File Parse: World Build: Render Scene: Write to File: Total:

VC++6 Standard 0.031 seconds 0.000 seconds 4.703 seconds 0.125 seconds 4.859 seconds

VC++.NET Pro w/opt 0.031 seconds 0.000 seconds 2.422 seconds 0.093 seconds 2.546 seconds

10,000 Spheres
400x400 JPEG converted from 500x500 PPM output
 

File Parse: World Build: Render Scene: Write to File: Total:

VC++6 Standard 0.187 seconds 0.031 seconds 10.297 seconds 0.125 seconds 10.640 seconds

VC++.NET Pro w/opt 0.187 seconds 0.031 seconds 5.391 seconds 0.109 seconds 5.718 seconds

100,000 Spheres
400x400 JPEG converted from 500x500 PPM output
 

File Parse: World Build: Render Scene: Write to File: Total:

VC++6 Standard 1.812 seconds 0.469 seconds 19.140 seconds 0.125 seconds 21.546 seconds

VC++.NET Pro w/opt 1.656 seconds 0.422 seconds 10.250 seconds 0.093 seconds 12.421 seconds

1 Million Spheres
400x400 JPEG converted from 500x500 PPM output
 

File Parse: World Build: Render Scene: Write to File: Total: Footprint:

VC++6 Standard 17.640 seconds 6.641 seconds 27.015 seconds 0.125 seconds 51.421 seconds 194 MB

VC++.NET Pro w/opt 16.031 seconds 5.937 seconds 15.094 seconds 0.094 seconds 37.171 seconds 194 MB

1 Million Spheres - Non Axis Aligned View Direction
400x400 JPEG converted from 500x500 PPM output
 

File Parse: World Build: Render Scene: Write to File: Total:

VC++6 Standard 17.671 seconds 6.829 seconds 58.046 seconds 0.125 seconds 82.671 seconds

VC++.NET Pro w/opt 16.093 seconds 5.938 seconds 32.906 seconds 0.094 seconds 55.031 seconds

Just for fun, I thought it would be interesting to see these million spheres at a higher resolution.  I ran the exact same file/parameters as the above image but with a file resolution of 5120x5120 pixels.  The image took almost 45 minutes to render (with VC++6 Standard) and had a footprint of 800 MB.  A 400x400 sample is shown below.

Crop of 1 Million Spheres
400x400 JPEG cropped from 5120x5120 PPM output