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.



Project 048montecarlo 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.


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.


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 many 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).


Not only for advanced readers:

What to hand in

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


Hand in the assignment until: 14. 5. 2017


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).


Visual Studio project: 048montecarlo.

Source file

Modify and hand in the source file: MonteCarloRT.cs
As a comment in the first line, please include your name!

Copyright (C) 2016-2017 J.Pelikán, last change: 2017-04-10 00:03:40 +0200 (Mon, 10 Apr 2017)