Rocks in the Lake

Daniel Götzmann

You can view the animation by clicking on the image above.

In order to create this animation, I extended the last version of microTrace by implementing the following four topics:

Fractal Geometry

The entire scene (except for the water surface) has been generated by my implementation of Fractal Geometry.

First of all, a height field, which is a two-dimensional array of altitude values at regular intervals [1], is generated. The two dimensions of that array correspond to the x and z coordinates. For each point in that two-dimensional array its altitude (i.e. its y-coordinate) is computed by the terrain function that I implemented in the HeightField class, based on an algorithm presented in [1].

The height field thus corresponds to a set of 3D vertices. Three neighboring vertices build a triangle and the final object is comprised of all triangles defined by the height field. In order to obtain a smoothly looking object, vertex normals are computed for each vertex of the height field from the position of a vertex and its neighboring vertices.

The vertices, their normals and the triangles are then saved into a file in .obj format that is eventually imported into the ray tracer.

I tried to make the implementation as flexible as possible, i.e. the constructor of the HeightField class takes arguments that specify position, size, resolution, height as well as the roughness or smoothness of the object to be generated.

The scene of the animation consists of three different objects (i.e. rocks, hills and mountains) that have been generated with different parameters.

Source file

Procedural Shading

Procedural Shading is used to generate the texture for rocks, hills and mountains.

Without procedural shading, each of the three objects would have a uniform color unless they had some texture assigned to them. Procedural shading is used to compute the color of a given point on the object by computing the value of a three-dimensional noise function for that point.

In order to obtain a flexible solution, I added an abstract class ProceduralTexture to the ray tracer. I changed the implementation of the PhongShader such that it (optionally) accepts an additional argument (i.e. an object of a subclass of ProceduralTexture), which it will use to obtain the color for an intersection point of the ray with the object. More precisely, the Shade method of PhongShader will call the getColor method (with the intersection point as argument) of the given ProceduralTexture in order to obtain the color for that point. This implementation is flexible because it allows to create arbitrarily many procedural textures by adding another subclass of ProceduralTexture. In addition, other shaders could also easily be modified to obtain the color for a given point from a ProceduralTexture subclass.

For my scene I implemented three subclasses of ProceduralTexture, one for each of rocks, hills and mountains. All of them use a noise function that is based on a noise function presented in [1] in order to generate the procedural texture.

Source files:

Reflective and Refractive Transparency

This effect can be observed at the surface of the water.

Since water and air have different refractive indices, reflection and refraction take place when light moves from one medium into the other. Reflection and refraction are dependent on the incident angle. The amount of light that is reflected at the surface is computed according to the Fresnel term and the relationship between incident and refracted angle is described by Snell's law.

Hence, I implemented methods that compute for an incident ray intersecting the water surface how much of the incident light is reflected as well as the refractive angle based on Fresnel term and Snell's law as presented in [2]. Once a ray hits the water surface it is split into two rays, the reflected and the refracted ray (if there is total reflection only the reflected ray will be traced further). Adaptive termination is achieved by adding another attribute to the Ray class that stores the influence of a ray to the final pixel and not tracing a ray if that value becomes too small.

Example scene for refraction

Since the textures of the rocks have been generated procedurally and do not have a very regular pattern it is hard to actually perceive refraction in that scene. Hence, I provide the following images where a simple scene has been rendered from three different perspectives in order to show that the implementation of refraction works as desired.

Source files:

SAH KD Tree

I implementated the SAH KD Tree acceleration structure according to the O(n log n) algorithm explained in [3] (reusing some code from the implementation of the unoptimized KD Tree from the last version of microTrace). According to that algorithm, the tree is built as follows:

First of all, events are created for each primitive that describe where it starts and where it ends. More precisely, usually 6 events are generated for a triangle, two for each dimension that describe where a primitive starts and ends, respectively, in that dimension (If the primitive is planar, a planar event is generated instead of start and end events for that dimension). The event list is sorted as described in [3].

Then, the binary tree is built recursively as follows: For each event in the current node the cost of splitting the node at the split plane specified by that event is computed using the surface area heuristics. The split plane with the least cost is then used for splitting, provided that the cost of splitting at that plane does not exceed the cost of not splitting at all. By looking at the events it can easily be found out whether a primitive overlaps both halves or lies only on one side. In the latter case, the events for that primitive are propagated only into the corresponding child node of the tree. In the former case, new events have to be generated for the primitive as it must be clipped at the split plane. Those newly generated events are then merged into the event lists of the corresponding child node preserving the order of the list.

Performance:

The following table shows a comparison of my SAH KD Tree implementation with the KD Tree implementation of the last version of microTrace. It shows both how many seconds it took to build the trees and how many seconds it took to render a scene with low quality settings and small size. In those test scenes the SAH KD Tree implementation decreased the rendering time by a factor of two for small scenes. For larger scenes the speed up was even larger. Although building the SAH KD Tree takes significantly longer than building the unoptimized KD Tree it usually pays off to use a SAH KD Tree, especially since the time needed for rendering a scene increases with higher quality settings or increased image size but the time needed for building the acceleration structure remains constant. That building the SAH KD Tree for the lake scene takes less time than building it for the face scene is probably due to the regular structure of the objects based on a height field.

You can view the four test images on a separate page.

Source files:

References