Edd Biddulph

Twitter | CV


October 2011
Updated April 2018
Pathtracing on CPU

Sponza with some spheres randomly positioned by a Lua script, and a directional light also implemented by a Lua shader

A single hexagonal piece mesh repeated and tiled by a Lua script

After writing a GPU-based brute-force (but highly parallel) pathtracer, I wrote a CPU-based one with greater support for complex scenes and most importantly, support of arbitrary triangle lists. It traces rays against instanced triangle meshes with any affine transformation. Instances are partitioned into a BIH (Bounding Interval Hierarchy) tree and a KD-tree is constructed for the triangles themselves, one for each mesh. A superset of the material parameters from my GPU implementation of pathtracing is provided and in fact they have turned out to be more numerous than I had planned, since mid-way through developing this pathtracer I started reading Physically Based Rendering. This is an excellent and informative book, and certainly I could have done things a lot better had I read it before embarking on this project. For that reason, in the future I think I will not make improvements to Beam where they are needed but begin afresh with a completely new renderer.

Extended lightsources, refraction, and diffuse inter-reflection

Probably the best thing about Beam is the explicit lightsourcing which alleviates slow convergence in the presence of small emissive surfaces, which is a well-known characteristic of brute-force pathtracing. Importance sampling is applied for these direct lightsources, and is also employed in the lambertian reflection of rays. The scene format is in plain text and provides what I hope is an intuitive interface with easily nestable transformations (similar to the OpenGL matrix stack). A number of commandline switches provide further interesting and useful features.

The core raytracing algorithm originally used mailboxing to improve efficiency by skipping repeated tests of rays against triangles. However this complicated the promotion to multi-threaded rendering, so mailboxing was dropped completely to allow a simple implementation and unlimited scalability with increasing processor cores. Mailboxing is the technique of assigning a unique ID to each ray, and allocating enough storage with each triangle to store a copy of one ray ID. An intersection test is only performed if the ray ID does not match the stored one, and once a test is done a copy is stored. This only makes sense where a triangle may be referenced by more than one voxel in the acceleration structure (as is typically done within a KD-tree).

Here is a psuedo-code example of mailboxing in action:

if(triangle.mailbox_ray_id != ray_id) { testRayVersusTriangle(); triangle.mailbox_ray_id = ray_id; }

This allows us to know that we have already performed a specific test, but also saves us from having to visit every triangle to reset each 'already tested' flag.

I started working on this some time before I started reading PBR. Having now read most of this book, I've realised some of the mistakes I made with Beam. I would like to produce a completely new version of Beam which would offer tangent-space normal vector textures to increase detail without increasing geometric complexity, a much better integration method like bidirectional pathtracing for example, and HDR formats (OpenEXR looks very useful). It would be interesting to allow custom shaders for surface appearance, and they may be achieved through dynamically-linked modules - this was already suggested and tested in Ingo Wald's PhD (linked below) which proposed the SaarCOR realtime global illumination engine. An alternative would be to allow source-text shader files which are parsed at runtime. JIT compilation is suitable here, especially if the shading language is designed so that parallelization through SIMD instructions is possible. Alternatively, the shader can be interpreted but this could be slow depending on the granularity of the shading language. At a basic level, this is a compromise between pre-compiled (fast) and extensible (slow).

Depth-of-field and sharp reflections

Caustics are producible with Beam, although convergence is extremely slow as caustics are only produced by emissive materials, and NOT by explicit light sources. I believe this would not be a problem if bidirectional pathtracing was used, or the newer energy redistribution pathtracing which seems to behave very well in the presence of LSDE paths (here I'm using the regexp style of path classification - see Paul S. Heckbert's "Adaptive Radiosity Textures for Bidirectional Ray Tracing" for more information).

I created a video using this tool, a Perl script, a bash shell on my laptop, and mencoder. At one point during the animation's generation, my laptop ground to a halt from what I can only assume was a depletion of resources. I was however able to resume processing from the last completed frame due to the fact that I was using a Perl script which created each frame as a separate image file and from a separate instance of the Beam executable. This made me very glad that I had not opted to link a video encoding library because this could have meant that the entire process would have to be restarted from the first frame. Perhaps this is a good example of doing things the Unix way.

I have also begun work on a Python module which would bind Beam natively, but it has a pretty low priority at the time of writing.

http://openmp.org/wp/ - Supported by most modern compilers, OpenMP is the multithreading API which was used to make Beam scale on multicore processors.

http://www.pbrt.org/ - Brilliant fully-featured physically-based rendering system. Luxrender is an open-source project which began as a branch of the pbrt codebase.

http://www.sci.utah.edu/~wald/PhD/index.html - Ingo Wald. Fascinating discussion on adapting global illumination to realtime application. Also introduces OpenRT, which is an API designed to be similar to OpenGL with the purpose being to ease a transition from forward rendering (such as rasterization, which is still prevalent in videogames at the time of writing) to raytracing.

An Ugly Problem, and a Performance Deficiency

Some of the images produced with Beam appear to have very bright specular highlights on glossy surfaces. This may be an issue of BRDF design - it is possible to create physically implausible reflectance functions which do not conserve energy. This can be considered an oversight of the interface design, and is easily accounted for when writing scene files. Something that may be nice to add to my future efforts is a testing suite for BRDFs - reciprocity and stability being important properties to ensure.

Shown here are high amounts of noise produced by LSDS?E paths

The multithreading in Beam could be better, as the screen is divided into a horizontal tile for each thread. When a thread completes it's assigned task then it does not take on more work. This results in most threads waiting idle by the end of the rendering. A better approach would be to divide the screen into more tiles than there are threads, and have a thread take an unallocated tile when it has finished one.

Antialiasing is performed, however only one type of filter is available - the box filter. It is currently not adjustable.

Lua Integration (new since April 2018)

Scene descriptions and shaders can be defined by Lua scripts. A shader in Beam is a single Lua function with one formal parameter, which returns a table holding the reflective colour (the "albedo"), the emissive colour, and the BRDF of the surface being shaded. This function forms a callback which the Beam renderer calls when a surface is intersected by a ray. The following C++ functions are exposed to the Lua shader script as globals:
The Lua math library is also included by default.

The shader function is given a table, called the shading context, with the following fields:

Here are some examples of the Lua integration being used to create shaders and scenes:

This example shows how the diffuse colour of the surface can be defined by a mathematical function.
It also shows how a multi-layer material can be created by stochastically selecting either diffuse or mirror reflection.
This is done by calling random which is a function provided by Beam.

function RainbowCube(shadingContext) p = shadingContext.op ecol = { 0, 0, 0 } -- Select either diffuse or mirror reflection based on a random value. if random() < 0.6 then col = { math.sin(p.x/10) * .5 + .5, math.sin(p.y/10) * .5 + .5, math.sin(p.z/10) * .5 + .5 } return { albedo = col, brdf = lambert, emission = ecol } else col = { 1, 1, 1 } return { albedo = col, brdf = mirrorBRDF, emission = ecol } end end function mirrorBRDF(normal, outgoing, u, v) d = (normal.x * outgoing.x + normal.y * outgoing.y + normal.z * outgoing.z) * 2 return { x = -outgoing.x + normal.x * d, y = -outgoing.y + normal.y * d, z = -outgoing.z + normal.z * d } end
A BRDF can be completely defined from within the shader code.
In this case a glossy BRDF is defined, and the glossiness value is stored in a lambda function which is returned by the shader.

function GlossyCube(shadingContext) -- Modulate glossiness based on the localspace position of the shading point glossiness = mix(0.1, 0.5, step(fract(shadingContext.op.y / 30), 0.5)) result = { albedo = { 1, 1, 1 }, emission = { 0, 0, 0 } } -- Use a lambda function to store the glossiness along with the BRDF function reference result.brdf = function(normal, outgoing, u, v) return glossyBRDF(normal, outgoing, u, v, glossiness) end return result end function glossyBRDF(normal, outgoing, u, v, glossiness) v0 = mirrorBRDF(normal, outgoing, u, v) v1 = lambert(normal, outgoing, u, v) return { x = mix(v0.x, v1.x, glossiness), y = mix(v0.y, v1.y, glossiness), z = mix(v0.z, v1.z, glossiness) } end function mirrorBRDF(normal, outgoing, u, v) d = (normal.x * outgoing.x + normal.y * outgoing.y + normal.z * outgoing.z) * 2 return { x = -outgoing.x + normal.x * d, y = -outgoing.y + normal.y * d, z = -outgoing.z + normal.z * d } end
The built-in shadow function can be used to implement an ambient occlusion effect completely in Lua.

function AmbientOcclusionCube(shadingContext) point = shadingContext.wp normal = shadingContext.wn a = 0 sampleCount = 4 radius = 2 for i = 0, sampleCount do d = lambert(normal, normal, random(), random()) d.x = point.x + d.x * radius d.y = point.y + d.y * radius d.z = point.z + d.z * radius if not shadow(point, d) then a = a + 1 end end lightAmount = a / sampleCount col = { 0, 0, 0 } ecol = { lightAmount, lightAmount, lightAmount } return { albedo = col, brdf = lambert, emission = ecol } end
Markers are points in the scene which can be defined in the scene description and labelled with a name.
The marker function can be used to retrieve a point. Here a point is used to cast a shadow, as if from a point light source.

function CustomPointLightCube(shadingContext) col = { .2, .2, .2 } ecol = { 0, 0, 0 } if not shadow(shadingContext.wp, marker("mypointlight")) then ecol = { 1, 1, 1 } end return { albedo = col, brdf = lambert, emission = ecol } ends
A scene description can also be generated by a Lua script. Here a set of nested for-loops is used to create instances of
the mesh object. The rest of the scene is described using the custom format, through which the script can be
executed using the execute command.

push() scale({ 0.25, 0.25, 0.25 }) for x = 0, 3 do for y = 0, 3 do for z = 0, 3 do push() translate({ x * 200 - 200, y * 200 - 200, z * 200 - 200 }) scale({ 0.9, 0.9, 0.9 }) instance("roundedcube", "white") pop() end end end pop()

How to use Beam

What follows is all of the information required to use Beam to create images from a scene description using any meshes and images you want (so long as they are in a supported format!).

Commandline switches:

s Sets the sample count (required) h Sets the viewport height (required) w Sets the viewport width (required) o Specifies the output file name (required) i Specifies the input file name (required) r Specifies the range of pixel components in the image a Generates an alpha mask image for primary rays. Useful for compositing. p Specifies a maximum number of passes to make. Good for automation. m Specifies a (scalar) factor to apply to the image's colours before clamping and quantization q Supresses the printing of continous progress update messages t Sets the tiling strategy, which determines how the image is divided up amongst threads d Sets the maximum number of threads to use b Sets the maximum number of ray bounces per pixel

For example:

Beam -i my_scene.txt -o my_image.ppm -w 800 -h 600 -s 16 -a my_image_alpha.ppm -p 10 -m 2

This will generate an 800x600 image my_image.ppm from scene description my_scene.txt. Each pixel will be sampled 16 times per pass, and there will be 10 passes made (each pass is averaged, and the entire image is written ONLY immediately after the end of each pass). The colour values of this image will be multiplied by 2. In addition, an image my_image_alpha.ppm wil be generated and will contain the anti-aliased alpha mask.

You can select different types of output image by changing the filename extension of the output image file. PPM is supported, and a text file containing float values in ASCII is obtained by using a TXT extension. This does not apply for the alpha mask output, which is always in PPM format.

Information on the plaintext scene file format:

The following commands may be used in the scene file:

point_light position, colour
Creates a point light and positions it according to the current matrix. It is translated in local space by position.

quad_light position, colour, width, height
Creates a light-emitting quadrilateral with dimensions width by height and positions and orientates it according to the current matrix. It is translated in local space by position. Light is only emitted from one side, and this is the side that points towards negative Z (in the light's local space).

rotate angle, axis
Rotates about the given 3D vector axis by angle radians.

camera distance, radius, angle
Sets the camera's focal distance (any object at exactly this distance from the viewing plane will be in perfect focus), circle of confusion, and field-of-view. A higher radius will increase the amount of blur applied to objects beyond or behind the focal distance.

environment colour
Sets the colour to be used for rays which escape the scene. This will show up in reflections, or in areas of the rendered image where no object is present. If an environment cube is set, then this colour modulates the texels from that cube.

translate vector
Appends a translation by the given vector to the current matrix.

scale vector
Appends a scaling by the given factors to the current matrix.

material_refractive name, surface_colour, specular_colour, reflectivity, glossiness, inner, outer
Creates a refractive material. Inner is the refractive index inside the mesh, and outer is the refractive index outside the mesh. Windings must match the notions of inside and outside. NULL is a reserved material name.

material name, diffuse_colour, specular_colour, emissive_colour, reflectivity, glossiness
Creates a non-refractive material with lambertian reflectance and a specular / jittered specular component. NULL is a reserved material name.

Push the current matrix onto the matrix stack.

Restore a matrix state from the matrix stack and remove it from the stack. The current matrix is replaced by the one restored from the stack.

Replace the current matrix with the identity matrix, which means that there is effectively no transformation applied.

texture name, filtering_mode, filename
Loads the specified texture file and assigns it the given name. The available filtering modes are "cubic", "linear", and "nearest". Texture files must be in 3-channel binary (raw) PPM format.

environment_cube <6 textures>
Creates a cube map with the 6 referenced textures as follows: 1st - negative x, 2nd - positive x, 3rd - negative y, 4th - positive y, 5th - negative z, 6th - positive z. It is oriented according to the current matrix. Note that the texture references must be names and not filenames.

mesh name, filename
Loads the file and assigns it the given name.

instance mesh, material
Creates an instance of the given mesh with the given material applied. This instance is given the orientation, position, and scale represented by the current matrix. If material is NULL then the mesh's internally-configured materials will be used. There are built-in meshes that can be used: "cube" which is a cube with a diagonal from { -1.0 -1.0 -1.0 } to { +1.0 +1.0 +1.0 }.

compose_texture name, filtering_mode, width, height, operation, source0, source1
Creates a new texture by composing two others. The new texture has the given dimensions and filtering mode. Texels are produced by applying the binary (diadic) operation to the corresponding texels from each of the source textures. The following operators are available: '+' (sum), '*' (product), '-' (difference). The operation argument must be a single character and not contain quotes. See texture for a list of available filtering modes.

set_material_texture material, type, texture
Sets a texture for a material. The type can be "diffuse", "specular", or "emission".

mesh_heightfield name, texture
Creates a mesh which is a grid of vertices, the X and Z coordinates being defined by the grid position, and the Y coordinate being sampled from a texture which is mapped over the grid. Texture coordinates are also generated, which match the coordinates used to sample the heightfield texture. Note that the red channel R is used as the height value.

shader_module name, filename
Loads a Lua script file for use as a set of shader functions.

material_shader name, module
Creates a new material which is defined by a function from the given shader module. The new material has the same name as the selected function.

marker name
Creates a new marker with the given name. The marker simply stores the worldspace position of the point at the origin of the current local space. The point coordinates can be retrieved by a Lua script. This allows points in the scene to be more easily addressed by a Lua shader function.

environment_shader name, module
Specifies that the given shader function from the given shader module should be used for determining the colour and brightness of the environment. Basically it allows for the creation of procedural environment maps implemented in Lua.

execute filename
Executes the given file as a Lua script.

If anything else appears on a line, the scene file is considered invalid and will not be loaded.
If you are interested in finding out more about how these commands are used or how they work, please see either the example scenes or SceneFile.cpp.

Download (Last Updated: 14th December 2018) - Includes source, build and render shellscripts, example scenes, example Lua shaders. Source code is licensed under the zlib license.