Task 089: Efficient sphereflake for RT

Your task is to implement new fractal solid into our ray-tracer. The Sphereflake is recommended. You have to implement efficient ray-solid intersection algorithm, use reasonable speed-up technique.

Basis

Project 048rtmontecarlo-script (or 048rtmontecarlo) from the grcis repository will be used as a template. There is a form application able to select scene from a list-box, set various ray-tracing options, super-sampling, multi-thread comutation, etc.
If you want to define R-T scene using CSharpScript, please use the 048rtmontecarlo-script project and put your scene definition into a new .cs file (be inspired by builtin scenes in the directory data/rtscenes/). Scripts have access to the text parameter Param: as well.

Details

Relevant interfaces and classes:

ISolid - general interface for solids (intersectable objects used in leaf nodes of the scene graph). It is able to compute intersections with rays.
Sphere - example of a concrete solid, you can take ideas of what needs to be implemented in your new solid there. In addition to it Sphere itself will be used in your recursive fractal in leaf nodes..

What to change

You have to take MonteCarloRT.cs file, create a new class in it, for example public class SphereFlake : DefaultSceneNode, ISolid and use it for implementation of your Sphereflake.
Insert the Sphereflake in to the scene definition (CustomScene), you might need to change camera and light position as well.

You have to implement some speed-up algorithm efficient enough to handle fractal solid up to 5-7 levels of recursion. You can use bounding volume hierarchy or a space-division technique.
See materials for speed-up techniques - from this course or from 2D graphics course.

Ideas

If your fractal is assembled from triangles, it is a good idea to consider data structures like KD-tree, R-tree (BVH) or Octree. Duplicit triangles are used in KD-tree and Octree, R-tree does not need duplicity. Use "bucket option", i.e. leaves can contain at most N objects, 2 <= N <= 8 (you might want to experiment with this constant).

In case you will be implementing "Sphereflake", a recursive descent with sytnetic bounding spheres might be sufficient.. Consider not actually storing all the spheres and bounding spheres, you can generate them "as needed".

Attention: your code must be re-entrant, because it will be executed in a multi-thread environment. Shared global data should be constant (e.g. pre-computed in the static class construction).

Geometric support

The Geometry class contains some useful functions: RayTriangleIntersection(), RayBoxIntersection() resp. RayBoxIntersectionInv(). You should use these functions for intersection individual triangles and bounding boxes (AABB).
Do not forget to increment counters CSGInnerNode.countBoundingBoxes resp. CSGInnerNode.countTriangles (bounding-box intersections resp. triangle intersections).

References

Not only for advanced readers:

R-tree (Wikipedia entry)
Vlastimil Havran: Heuristic Ray Shooting Algorithms (PhD thesis)
Ingo Wald, Vlastimil Havran: On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N)

What to hand in

You must send the modified file MonteCarloRT.cs, optionally a couple of rendered images.

There is an option to define your scene in a CS-script file (see the 048rtmontecarlo-script project), you have to hand in a script file together with your source file. Script format: see the data/rtscenes/ directory in the repository.

Deadline

Hand in the assignment until: 9. 6. 2019

Points

Basis: 25 points (minimum - Sphereflake with reasonably fast computation),
bonus point for different fractal made of triangles with a general hierarchic system (R-tree, KD-tree, octree).

Project

Visual Studio project: 048rtmontecarlo-script or 048rtmontecarlo

Source file

Modify and hand in the source file: MonteCarloRT.cs
Edit your name in the InitializeScenes() function!