100 points - Implemented by Steffen Lösch

Tracing a ray through a scene and finding the first primitive that is intersected by the ray is the main task in ray tracing and also the most time consuming action. Therefore, having a fast acceleration structure brings a significant speedup for the whole rendering procedure. A Bounding Volume Hierarchy (BVH), where the primitives are just split at the mean, was given by the chair. We extended this by a BVH where the splitting plane is determined by the Surface Area Heuristic (SAH). Furthermore, we implemented a KD-Tree in three different kinds: first by splitting at the spatial mean, second by using the SAH to find the splitting plane and third using SAH as well as by splitting primitives that overlap the splitting plane.

When you are able to see the effect of an acceleration structure in the scene, then this is a bad thing, because it is an error. Therefore no images are provided here, but a table. In this table you can compare times for building the acceleration structure and the actual rendering of the scene, for the different structures we implemented.

Scene name	BVH	BVH with SAH	KD-Tree	KD-Tree with SAH	KD-Tree with SAH and prim. splitting
small 800x600 14 Triangles	Build: 0 s, Render: 4.56 s	Build: 0 s, Render: 3.99 s	Build: 0.23 s, Render: 3.72 s	Build: 0 s, Render: 3.51 s	Build: 0.06 s, Render: 3.44 s
test 800x600 48086 Triangles	Build: 0.1 s, Render: 7.79 s	Build: 1.43 s, Render: 7.03 s	Build: 0.25 s, Render: 5.78 s	Build: 2.81 s, Render: 3.41 s	Build: 5.34 s, Render: 4.16 s
water 400x300 262168 Triangles	Build: 0.54 s, Render: 6.9 s	Build: 8.96 s, Render: 5.03 s	Build: 0.38 s, Render: 4.42 s	Build: 16.74 s, Render: 1.93 s	Build: 23.52 s, Render: 2.33 s
scene 400x300 1289781 Triangles	Build: 2.62 s, Render: 62.16 s	Build: 51.01 s, Render: 50.36 s	Build: 20.2 s, Render: 104.42 s	Build: 91.6 s, Render: 25.61 s	Build: 144.56 s, Render: 20.17 s

All scenes have been rendered without supersampling.

Each acceleration structure has its own class und implements a certain interface. There are basically two methods: the build method, where the structure is built from the given primitives and the intersect method, which finds the best intersection of a ray with the scene. The GeometryGroup class is also changed, such that it can handle the dynamic inheritance structure of the acceleration techniques.

• BVH with SAH class (sahbvh.h,sahbvh.cpp)
• KD-Tree class (kdtree.h, kdtree.cpp)
• KD-Tree with SAH class (sahkdtree.h, sahkdtree.cpp)
• KD-Tree with SAH and primitve splitting class (primsplitsahkdtree.h, primsplitsahkdtree.cpp)
• The changed geometry group (geometry_group.h, geometry_group.cpp)