CS488 A5 – A ray-tracer with a focus on various material properties

Originally published July 26, 2011. Last edited September 16, 2015 (adapted for this website's layout).

Topics/Keywords

  • Backward ray-tracing
  • Texture, specular, opacity maps
  • Simple (naive) reflection and refraction
  • Bump mapping
  • Real-time user interaction considerations
  • Primitive intersection
  • Naive lighting (point lighting) and an examination of area lighting techniques
  • Glossy reflections

Contents

Introduction

For the final project of CS488 offered by the University of Waterloo, the students are instructed to set 10 computer graphics related objectives they need to achieve. The instructor and TAs review this objective list and interact with the students to determine if it is sufficiently difficult enough to implement. I'll discuss the objectives I chose here, those I accomplished, those I could not, and those I chose not to implement and why.

I should mention, for full disclosure, I'm a student of Computer Graphics for no more than 4 months as of writing this. As such, as a reader, you should be doubtful of any material you see here. I do aim for correctness, but unfortunately cannot guarantee it. If you'd like to e-mail me at [email protected] I'd be glad to respond to any concerns regarding accuracy.

Initial Vision

You can view my initial proposal here, and an edited version with my final objectives here. For purposes of this report, I'll focus on those objectives I did accomplish, as well as provide some discussion as to how those I did not implement might be attained.

I wanted to continue to explore various ray-tracing technologies, potential efficiency gains, and advanced rendering effects such as reflection, refraction, textures, bump mapping, and potentially radiosity-based global illumination techniques. The goal is to allow a user to create a realistic rendition of a scene, while still allowing the user to control the viewing angle and modify material properties without having to alter a script file and/or wait an absurd amount of time to see the final (potentially undesirable) rendition of the scene.

The focus is on simulating material properties and their effects on light with respect to simple surfaces/objects, expanding to more complex surfaces if time permits.

This project was designed in mind to alleviate my original frustrations with A4 – waiting inordinate amounts of time to see I had rendered a scene with no objects in it (poor camera placement), constant annoyance with tweaking small parameters that might be better tweaked in visual space to obtain a visually pleasing scene, and immediate user feedback with respect to rendering.

Objectives

  1. Shadows, both hard and soft
  2. Reflections, various degrees of reflectivity possible
  3. Glossy surfaces
  4. Refraction, physically based according to differing indices of refraction
  5. Texture mapping
  6. Bump mapping
  7. Uniform spatial subdivision to speed up rendering
  8. Able to re-position camera in "real-time" to expedite scene creation
  9. Progressive refinement via radiosity
  10. Unique final scene

Technical Outline

Shadows

Shadows are one of the first extensions someone creating a ray-tracer might implement. On their basic level, shadows are very simple and highly intuitive, and can be explained with an oft-used concept in CG called a "shadow ray": We wish to know the contribution of shadows to the shading of a certain point of an object. So, we cast a ray from said point towards the light(s) in the scene. If there are multiple lights, there are multiple shadow rays. If a shadow ray intersects with an object that is not the light, then we know that the effect of that light is being modulated by this object.

Hard Shadows

The following are hard shadow schemes. They are characterized by discrete lines which look very much like dark flat projections of the occluding object onto the occluded object. This is because, essentially, that's exactly what they are – projections.

  • Binary modulation: If there is a hit in the intersection test, then we simply say that the contribution from that light is shadowed; the point in question cannot see the light on this direct path, and its diffuse and specular contributions are nullified. To avoid complete darkness, we might add a naive ambient term or use a more sophisticated global illumination technique. This produces the effect of hard shadows – there is no penumbra, it yields only a solid umbra with a very obvious and sharp line.

  • Naive opacity modulation: What if the blocking material is transparent or translucent? The binary modulation does not suffice as it would yield thick dark shadows, even if the occluding object is 100% transparent! A naive fix would be to modulate the effect of the shadow depending on the material properties of the occluding object. In the binary scheme, no hit was essentially a "do nothing" operation to the contribution of the light, whereas a hit was equivalently a "multiple by 0" the contribution of the light. In the naive opacity modulation scheme, we can look up the opacity (we'll call this alpha) of the occluder by examining its material, and vary the contribution of the light accordingly.

    Opacity ranges from [0..1], 0 being completely opaque, 1 being completely transparent.

    We can define the light contribution as follows:

    light_coeff = light_coeff * alpha_of_occluder

    Where light_coeff represents the intensity of the light (after falloff / attenuation). Thus, the contribution of light occluded by a completely opaque object is 0, and the contribution occluded by a completely transparent object is 1*light_coeff (unchanged).

    This still yields hard shadows, but it alleviates the problem of glassy, mostly transparent objects leaving behind thick dark shadows, which is highly unrealistic. For its highly easy implementation, this modulation scheme produces a very good effect. I employed this scheme when creating my final scenes, applying the modulation to the diffuse Phong coefficient.

  • Recursive opacity modulation: What happens when an object is transparent in only certain parts, but opaque in others? An example of this in reality would be an etched glass object. Under most lighting conditions, the etched (opaque) sections of the glass will leave a shadow on an object, whilst the clear glass will leave a much lighter shadow. A step in the right direction would be to consult the opacity map of the object at the point in question (rather than querying it's global object opacity, as in the previous scheme).

    However, we must also consider the exiting side of the shadow ray: we would only cast shadows properly if we considered the light transmitted through the occluding object as well. The contribution of shadows from the light-facing side of the shadow ray would be ignored without a recursive step. Additionally, this recursive approach lends itself nicely to the generation of shadows where many transparent objects are between the light source and the point in question.

    How do we combine the modulating effects of this recursive shadow ray? There are some considerations we must take into account:

    1. If, after passing through multiple transparent objects, the shadow ray hits a completely opaque object, the modulation factor should be 0 (as in the binary scheme above). We can stop the recursion after this point.
    2. Passing through multiple transparent materials should be additive with respect to the darkness of the shadow. Example: 2 identical transparent objects will contribute a darker shadow to a surface than light passing through just 1 of these transparent object. I propose that we might simply multiply their alphas recursively as we go about.

    We can satisfy these considerations with the simple recursive formulation:

    shadowTest(Ray r, double alpha):
    if (r.hits(any_object)) then
    {
    beta := consult opacity map of the closest hit object at the intersection point
    alpha = alpha * beta * shadowTest(Ray towardsLight, alpha)
    }
    return alpha
    

    and should be called with an initial alpha value of 1.0. After passing through 3 objects of 0.9 opacity, the final alpha value would be 0.9^3 == 0.729, which is still mostly transparent as we would expect and desire.

    In this recursive calculation (as in the ray tracer), I consult first the closest hit object – this is important! This is to prevent considering the negative intersections in the hit testing code (negative t, if you're using the parametric equation of the line), and allows us to consider each transparent object contribution to the final alpha only once. Are the performance optimizations possible? As we scan intersections to find the closest one, we can check to see if any of them have a material with alpha==0 (totally opaque), and return 0 immediately. If we don't refract the shadow rays, maybe unrolling the recursion and doing it iteratively would be a better equivalent idea.

    This method does NOT take into account the distance throughout the medium travelled. This is important for at least the following reason: ten glass planes, each 1 cm thick, yield 2 contributions each to the recursive alpha formulation above. If each were 0.9 in opacity, the final alpha value returned would be (0.9^2)^10 == 0.121577. Realistically, we might think (and rightfully so?) that one glass plane, 10 cm thick and 0.9 in opacity should have roughly the same, or at least visually undifferentialiable, as the ten 1 cm plates. However, in this latter case, the alpha would be 0.9^2 == 0.81. This is quite a difference in alpha contribution!

    If we are to approximate the opacity of objects with a surface function, it is clear we must take into account the distance through the medium. The extent of the difference in value in this hypothetical situation might be alleviated by scaling our multiplication by the distance between the previous and current hit point in our recursive formulation.

    The will yield a fairly good approximation to shadows of objects with different levels of transparency on their surfaces (a 2D transparency map), but will not work, for example, on an object with an opaque core (this would be in implementation a 3D transparency map), for example. You might be able to derive a formulation for your 3D transparency function that takes a ray as a parameter (perhaps some kind of sequential multiplier). For example, if you used a deterministic noise function Additionally, the effects of transparency with respect to the distance through the medium should be considered, as well as varying indices of refraction (internal to each object). This is definitely an area for future research, and is perhaps leading us towards more complicated models such as sub-surface scattering, and to an extent, BRDF (which I acknowledge I don't know nearly enough about to discuss here).

    This transparency handling schemes for hard shadows I have discussed above should be taken only as a crude approximation to transparent objects, useful in rendering only very simple scenes. They might be useful in creating images that are visually appealing but I must stress it is hardly physically based!

    I think if we were to also perform refraction calculations on the shadow rays in the recursive scheme, and we were to sample the surfaces many times when shading, it might lead to the generation of caustics in the images. This seems prohibitive with respect to time, so I'll point the reader to the keywords “photon maps” and “global illumination” for this purpose.

Soft shadows

A beginner technique is to jitter the shadow ray's direction by a random amount. If we sample this many times, and average it, we have an alright approximation of the umbra and penumbra and an overall softer shadow. For objects that are highly occluded (deep in the umbra), all these jittered rays will still hit the occluding object, and the average alpha will be 0. For those in the penumbra, some of the jittered rays will hit the occluding object, whilst others will not, and as such its average will vary, producing a smoother gradient of alpha values near the extents of the penumbra. Thus, even with a point light, with this technique we can still simulate an area light and soft shadows. I believe, however, that point lights should always return hard shadows.

Better yet, instead of totally random jittering, we might produce a random jitter that adheres to a 3D cosine distribution. We could estimate this effective cone by using trigonometry and taking the half angle of the triangle formed with the area light source and the point in question

I thought this method was pretty hackish, and chose not to implement it for presentation time. I wanted to examine radiosity methods or other global illumination methods, but found their respective complexity levels were too high for me at my current understanding of physics, optics, and mathematics.

Textures

For every primitive, a UV map is consulted. This converts the 3D surface in question to a rectangular 2D representation in the range [0..1]x[0..1]. For this project, I only considered spheres as their 3D point > UV conversion is fairly straightforward.

Point2D Sphere::get_UV(Point3D point_in_space_on_sphere)
{
Vector3D wrtSphere = (point_in_space_on_sphere - sphere_origin); // get the point wrt the sphere
wrtSphere.normalize(); // consider the unit sphere for simplicity, it is equivalent
u = atan2(wrtSphere.x, wrtSphere.z) / (PI * 2.0);
v = acos(wrtSphere.y) / PI;
u += 1.0; // since u is -0.5..0.5 after atan2 and scale by 2PI
return Point2D(u,v);
}

The above is pseudocode for purely illustrative purposes; I have no Point2D class in my code. Also to note, is that the C functions atan2 and acos work in radians.

After UV co-ordinates are obtained, we can shade by performing a look-up. Bilinear interpolation might be used in the texture map to reduce the aliasing due to lower textures, but this yields a blurrier look. I chose to instead zoom out to sufficient distances for texture considerations. Notably, I encountered a very noisy looking moon when zoomed out very far, which I presume to be aliasing due to lack of level-of-detail code. In the future, mip-maps might be used for the various texture maps.

We can use the U and V to index into the texture map's X and Y co-ordinates respectively. Small consideration needs to be taken to avoid under/overflowing the boundaries of the image.

I used the Image class provided in A4 to implement the various maps for this project. Oddly, I needed to use the indices {0,2,3} when indexing the pixels RGB channels, instead of using the intuitive and correct indices {0,1,2}. It would seem this would use the colour channel of a different pixel! However, {0,1,2} while correct, looked terribly wrong, so I went with the empirical approach. Perhaps this is an artifact of converting a JPG to a PNG, or some kind of sRGB vs. RGB colour profile, or another unknown colour setting that I'm not aware of.

2D Procedural Textures

The UV co-ordinates can be used for more than just consulting a map of pixels! Here's a simple code that draws a checkerboard on the object in question:

// checkerboard
if (((int)(u * 20) + (int)(v * 10)) % 2 == 0)
{
return Colour(0,0,0);
}
else {
return Colour(1,1,1);
}

Alternatively, we can use some noise to spice things up. Here's the code that generates the red swirly ball seen in the Gallery

double noiseCoef;
for (int level = 1; level < 10; level ++)
{
noiseCoef +=  (1.0f / level)
  * fabsf(double(noise(u*10*level,
                        v*10*level,
                        v)));
}
// noiseCoef = 0.5f * sinf( (u + v) * 0.05f + noiseCoef) + 0.5f; // optional for spiciness
return noiseCoef * m_kd;

It's highly based off of the code seen here.

3D Procedural Textures

If we aren't especially careful, or if we don't use some kind of mirrored texture, we might run into discontinuities in our 2D texture. Additionally, should we ever want to render Constructive Solid Geometry (CSG), when we begin slicing away a cube using another cube, our final textue won't look right, let alone the difficulties we'd have trying to get the UV co-ordinates of such complicated objects. Instead, we might use UVW co-ordinates (which is basically the same 3D point, but object agnostic in that a certain point on the object will be the same UVW point regardless of the object's orientation, scale, or position). Unfortunately, my UVW generating code isn't the greatest, but it is a useful concept.

Getting the UVW is useful because it allows us to refer to the same portion of 3D space when we're addressing our 3D texture generation function. For example, instead of using random points in world-coordinate system space (WCS), we're always using object-local points. Thus, if we're using a pseudo-noisy function to model turbulence, swirls, or any other manner of thing (see Ken Perlin's early SIGGRAPH slides, or Demystifying perlin noise), we can be sure to get that same texture, even if it were to animate through space.

After this, it's just a matter of consulting our procedural 3D texture generator. Care should be taken with the pseudo-noisy functions to remember your seed per texture.

Here's the code for the line-y marble texture seen in the gallery:

Colour PhongMaterial::getColour(Point3D at, Primitive* p)
{
if (m_proc_texture == "marble"){
double noiseCoef;
//at = p->get_UVW(at); // temporarily disabled pending investigation
for (int level = 1; level < 10; level ++)
{
noiseCoef +=  (1.0f / level)
      * fabsf(float(noise(level * 0.05 * at[0],
                          level * 0.05 * at[1],
                          level * 0.05 * at[2])));
};
noiseCoef = 0.5f * sinf( (at[0] + at[1]) * 0.05f + noiseCoef) + 0.5f;
// noiseCoef = 0.5f * sinf( (at[1]) * 0.05f + noiseCoef) + 0.5f; // alternative line to the above line, also pretty
return noiseCoef * m_kd;
}
...

It's highly based off of the code seen here.

Specular Maps

In the same vein as a standard texture map, we can alter the Phong specularity coefficient by a multiplier of [0..1] in a specular map to achieve certain effects. For example, in modeling the earth we might want to make it so the water is more reflective than the land. In the ray-tracing step, before applying the Phong specularity term to the final colour, I first modulate the Phong specularity coefficient by the value returned by the specularity map (if it exists). A bilinear or greater interpolation might be needed here; we see some noise with regards to the small islands on the earth. This might also be alleviated by using a specularity map with a smoother gradient of colour (rather than binary). Additionally, since it's a black and white image, I simply use the pixel's red channel, ignoring the other channels.

Opacity and Refraction

I moved onto implementing simple opacity. An object has an opacity value, [0..1], where 0 represents perfect opaque and 1 represent perfect transparency. In calculating the shading at a certain point, after we've done our Phong diffuse & specular, after we've calculated shadow contribution, we then consider opacity. The colour at that point will be:

final = ((1 - opacity) * final) + (opacity * rayColor(transmittedRay));

This is a naive scheme, but it works well as first-approximation to transparent objects.

The transmittedRay will be along the same ray as the original ray, only shifted along, provided there is no refraction. If there is refraction, a few more preliminary steps must be taken to calculate the direction of the transmittedRay before shading.

Opacity Maps

The next logical step would be to implement opacity/transparency maps. I tend to throw around both terms, but I'm always referring to the same thing. Opacity maps modulate the global opacity term of an object. For instance, if the global opacity of an object is 0.8, it may never become fully opaque with an opacity map. In this situation, the object would be locked between [0 .. 0.8]. Since opacity maps are grayscale, I just used the image's red channel, ignoring blue and green.

Bump Maps

Height maps are used to implement bump maps. An image, where white is high, and black is low, is used. Again, as it was grayscale, only the red channel was used.

A differential in both the U and V directions is obtained, which is to be used in perturbing the normals. Intuitively, we perturb the normal by 2 vectors bitangent to the surface at the normal's point. material.cpp demonstrates this calculation.

The good pseudocode might be something like,

Vector3D applyBumpMap(Point2D uv, Vector3D normal)
{
  // values used for indexing heightmap
  maxX = heightmap.width()
  maxY = heightmap.height()
  // calulate differential
  Fu = heightmap(((int)u*maxX) + 1) - heightmap((int)u*maxX)
  Fv = heightmap(((int)v*maxX) + 1) - heightmap((int)v*maxY)
  // calculate tangent vector, ellided, see material.cpp
  // calculate other tangent vector by cross product of first with current normal
  // call them vv, vu
  normal = normal 
            + (scale * Fu * vu)
            + (scale * Fv * vv)
  return normal
}

Interesting to note, I have no guarantee that these two vectors are always pointing in the same direction. However, it doesn't seem to make a difference for the appearance of bumps in the final image.

Glossy Surfaces

Perturb the surface normal by a small random amount, super-sampling all the while. I also thought this was insufficient, and didn't really desire to implement (for the same reason as naive soft shadows). I would rather implement a BRDF model, however, that is beyond the project's scope, and I'm not convinced BRDF is the best way to go about these things. Examining them in greater depth, however, should bring about enlightenment.

Uniform Spatial Subdivision

I deemed this unnecessary as I got caught up in rendering material properties. I was less and less interested in rendering many objects and more interested in rendering just a few well. This is definitely something to pursue in the future if my object count > #subdivisions^2.

Pixel-plane scanline algo for efficiency

A series of 4 matrix multiplications, a trig function, at least 4 double multiplications, and a few vector normalizations were required to generate each eye>pixel ray in A4. I was able to speed things up dramatically when I realized that I could just calculate 3 eye>pixels (2 vectors), and use these in a scanline fashion to calculate all the others (as each pixel is equally spaced as well as coplanar). It was found that the distance between both methods was approximately < 1e-6

In practice, without the optimization, the final scene rendered 1024x1024 supersampling took real 1m57.595s as opposed to real 1m14.619s with the optimization.

To note: The scanline algorithm is always used if supersampling is enabled. Imagine how slow it would be had I not hard-coded that in! Supersampling represents an additional 4 sub-pixel points being generated with the classic method.

Turning this function on and off be done in the lua script, and is documented in scene.lua.

Radiosity, and using it for progressive refinement

Way too hard for the time-frame and scope of project; read some of the papers! Very difficult for me to implement, let alone write about. I'd attempt to do both caustics and radiosity-based in the same global illumination pass, though. I tried hard to understand it, but I couldn't figure out a good implementation strategy.

Real-time concerns

I wanted to, but found it prohibitive to implement my real-time user interactivity objective. Many questions arose, namely, would I still use my ray-tracer for the real-time stage? Coding a faster and simple OpenGL shader for interactivity, then switching to my ray-tracer when the user is done moving things around seemed like one possible approach, but there are many hazards with that approach (visual synchronization mainly, as I predict that it'd be hard to get both to attain the equivalent projection).

The other option was to render the image at a very low resolution, upscale that to the viewer program's resolution, then progressively refine the same image as the user doesn't interact with the program. A 128x128 resolution image of the same final scene can be rendered at real 0m1.131s which yields an image at a somewhat acceptable resolution to discern some details. We can achieve 1FPS at 64x64 with times like real 0m0.861s. Clearly, further optimization is required! It is a naive estimate that 2FPS would be possible simply disabling reflections & bump mapping from the ray-tracing step, then adding them back later. A stochastic importance sampling might yield results that converge faster, so that is one area to look to.

Code Map

a4.cpp: Stores the main recursive ray-tracing functions, code to determine the closest intersection between a primitive and a ray, super sampling anti-aliasing code, final image generation, as well as eye-pixel projection and its equivalent scanline efficiency enhancement.

material.cpp: Returns Colour values for 2D and 3D materials with respect to a point, consulting perlin.c (stolen from here which, as far as I can tell, is just a cleaned up version of Perlin's original noise code). The Material returns values to the ray-tracer at its request by consulting specularity maps and transparency maps, and contains the code that determines the perturbation of surface normals in bump mapping.

scene.cpp: A largely useless file, I must admit, as I don't support hierarchical object modeling with this ray-tracer. It does, however, handle the polymorphism of the various objects that implement the Primitive class and their intersection, associates useful properties to Intersections (such as the material, the primitive, and the name of the hit object involved), and perturbs the normal if the material defines a height map.

algebra.hpp: Contains useful 2D and 3D classes and functions for vectors, points, and matrices. The Ray class is defined here, as well as the randomized vector perturbation function I initially tested glossy reflections with.

scene.lua: Defines a sample scene, please consult this file for instruction on how to use the extended scripting language given to us in A4.

primitive.cpp: Defines ray-object intersection tests for various primitives, and methods for determining UV and UVW points (the 3D equivalent of the UV map) given an point on the object.

perlin.c: A simplified port of Perlin's original C code, taken from here.

References & Acknowledgements

Not all of the following were used directly in the implementation of the project, but they were definitely of use to me (I saved them to disk). I'd like to thank these authors for their great work, and apologize to anyone I forgot to mention here. Most of these are definitely areas for future research for myself.

Papers

  • Agu, E., Hill Jr., F S. (2003). A simple method for ray tracing diffraction.
  • Blinn, J F. (1978). Simulation of wrinkled surfaces. ACM SIGGRAPH Computer Graphics, 12(3).
  • Cabeleira, J. Combining rasterization and ray tracing techniques to approximate global illumination in real-time.
  • Christensen, P H. (2010). Point-based global illumination for movie production. SIGGRAPH 2010 Course, Retrieved from http://graphics.pixar.com/library/PointBasedGlobalIlluminationForMovieProduction/paper.pdf
  • Green, R. (2003). Spherical harmonic lighting: the gritty details. Sony Computer Entertainment America technical memo.
  • Gritz, L. and Hahn, J K. BMRT: a global illumination implementation of the RenderMan standard. Journal of Graphics Tools, Vol. 1, No. 3, pp. 29-47 (1996).
  • Gustavson, S. (2005, March 22). Simplex noise demystified.
  • Peercy, M., Airey, J., & Cabral, B. Efficient bump mapping hardware.
  • Walter, B., Marschner, S R., Hongsong, L., & Torrance, K E. (2007). Microfacet models for refraction through rough surfaces. Eurographics Symposium on Rendering (2007).

Web References