www.nigels.com
Welcome Research Photos Software Graphics Links

RMIT Department of Computer Science
CS516 Advanced Computer Graphics
Assignment 2 - Raytracer

Nigel Stewart
9304105H

1995


Immersed in Raytracing "Immersed in Raytracing"

(1024x1024 True Color JPG - 356K)

(Scene description file - 25K)

This .html document, together with a print out of the source code forms my assignment submission for CS516. The raytracer has been called BART , and was going to use some BSP trees (BSP Tree Accelerated RayTracer). BART has been implemented in C++ the first sizable program I have written in this language. There are currently around 12,000 lines of code, including a yacc/lex parser. BART currently compiles under Linux, DOS, SunOS and Irix systems, although bugs and features vary across platforms.


Current features of BART

  • Geometric Primitives : Spheres, Planes, Polygons and Polygon Meshes.
  • Shading : Ambient, Diffuse, (Phong) Specular, Shadows.
  • Lighting : Point Light Sources.
  • Reflection
  • Texturing : Procedural and Texture Mapping.
  • Supersampling : Uniform Pixel Sampling and Random Pixel Sampling.
  • Adjustable Uniform Grid Acceleration.
  • Flexible Scene Description Language.
  • Graphic Display for X11, SVGALIB and Borland BGI.

Procedural Texture Background "Procedural Texture Background"

(640x480 True Color JPG - 35K)

Geometric Primitives

Objects such as spheres and planes inherit behaviour from the physical object class. All physical objects can intersect rays, have a surface normal at a given position, and may or may not be boundable. Physical objects have been implemented with object and material transforms. The object transform determines the position and orientation, while the material tranform is used for texturing. Transform objects are manipulated by pushing matrices for translation, scaling etc and inverse tranforms are automatically maintained.

Shading

Shadows and/or diffuse and specular lighting can be disabled to increase rendering speed. The diffuse, specular and ambient lighting components are specific for a certain material and any material can be applied to any object.

Lighting

The current implementation supports point light sources. Directional light sources (positioned at inifinity) have been implemented but are untested. An attenuated point light source has been implemented but also remains untested.

Reflection

Reflection rays are cast whenever the material has a non zero reflection component. Reflection rays can be disabled to increase rendering speed. Refraction rays have not been implemented, but the source code has been designed with this future extention in mind.

Jolt Temple "The Jolt Temple"

(600x600 True Color JPG - 83K)

(Scene description file - 1K)

Texturing

BART supports procedural and mapped texturing. Procedural mapping is defined over 3 dimensional space f(x,y,z) while spherical or tiled mapped texturing uses 2 dimensional images. The raytracer expects images to be in PPM format, but these can be compressed on Unix environments.

Super Sampling

Jagged object edges and noisy texturing can be smoothed by using supersampling. Two different algorithms are available: subdivide the pixel into a square grid and cast one ray per subdivision, or cast rays randomly withing the bounds of the pixel. The former, termed "Brute Force" works well, but is restricted to 4,9 or 16 samples per pixel, while "Random Sampling" can sample an arbitrary number of times.

I would have liked to have experimented with some dynamic approaches to supersampling, so that multiple rays are cast when they are needed, and not for every single pixel.

Acceleration - Using a Uniform Grid

Three dimensional space can be partitioned, and rather than testing each ray against all objects in the scene, we can traverse 3D pixels (voxels) and test against objects intersecting that voxel. Unbounded objects such as planes are not included in the uniform grid, and are tested for ray intersection separately.

In this implementation, the resolution of the grid must be specified by the user, and the program is rather relaxed about what passes as an intersection with the voxel. (For example, a voxel that is completely contained by a sphere still treats this as an intersection.) I consider false positives to be a non-critical issue, but removal of this redundancy would improve performance further.

The use of a uniform grid vastly improves performance, particularly for scenes with a large number of boundable objects.

Bucky Ball Nanostructure "A Bucky Ball Nanostructure"

(1024x1024 True Color JPG - 123K)

Acceleration - Ray Caching

Ray caching is useful in the context of uniform grid acceleration because it is common for a ray/object intersection to be repeated. Duplicate computation is avoided by keeping track of the last ray which has intersected each object. Runtime statistics have demonstrated that a large number of intersection calculations can be avoided by using ray caching:

# Spheres                                 :        153
# Sphere tests                            :     252326
# Sphere intersections                    :      19252
# Cached Sphere intersections             :      34751
# Planes                                  :         36
# Plane tests                             :     495870
# Plane intersections                     :     187038
# Cached plane intersections              :     112630
# Polygons                                :         32
# Polygon tests                           :     306752
# Polygon intersections                   :       1391
# Cached polygon intersections            :      17290

These results vary widely between scenes and raytracing parameters.

Scene Description Language

I've used the UNIX utilities flex and yacc to design and implement a POV-ray'ish scene description language. Here is an example scene description:

//
// Include some color definitions.
//
include "include/colors.inc"

//
// Define a point light source.
//
pointlight position <1,50, 30> color <1,1,1> 

//
// Specify some material properties that we can apply to
// multiple objects.
//
define BallRedM   	material { colored red diffuse 0.3 }
define BallGreenM 	material { colored green diffuse 0.3 }

//
// Here are some spheres using globally available material
// definitions, as well as sphere with a unique material.
//
object { sphere position <0,0,-10> radius 3 material BallRedM }
object { sphere position <-1,0.5,-2> radius 0.1 material BallGreenM }
object { sphere position <2, 1, 7> radius 2.0 material { colored orange } }

//
// Define a plane, which is then scaled.
// It uses a procedural "checker" texture and includes 50% reflection.
//

object {
  plane position <0,-6.1,0> normal <0,1,0>
  scale <0.1,1,0.1>
  material { mapped scalecolor white checker reflectivity 0.5 ambient 0.4 }
}

I didn't see much point in documenting the language properly, since it has been subject to refinement.

Textured Polygon Sphere "Textured Polygon Sphere"

(600x600 True Color JPG - 50K)

Platform Specific Features and Bugs

The main development platform for BART has been the linux OS for the PC using the SVGALIB libraries for display. I have also had success compiling on the departments SunOS host yallara and in an Irix environment mega.

X11 is supported for unix environments, but will only display in greyscale.

BART will compile under Borland C++ V3.1 using BGI for graphic display. Due to the DOS 64K array limit, large images can not be produced in the DOS environment, although a few minor changes to the source code would allow display.

16 bit graphics capabilities are assumed when using SVGALIB, but X11 and BGI are assumed to be 8 bit and use greyscale. Doing something more clever with 8 bits of color would be interesting, but I didn't feel it was relevant to a raytracing assignment.

Viewing can be disabled using the command line option -D, and the image is always represented internally as an array of 32 bit int's, so display mode makes no difference to program output. A PPM format image is written to the current directory and the completion of execution. In UNIX environments the filename will be in the format outpid.ppm (where pid is the process ID of the BART session.) and dos will simply output a file out.ppm

PPM files are not compressed, so usually they should be compressed or turned into a jpeg:

#gzip -9 out.ppm		
#cjpeg -quality 95 -optimize -outfile picture.jpg out.ppm

The makefile contains a lot of options including debugging and optimisation. It also allows the use of an OSF/MOTIF user interface and OpenGL/MESA scene editor. These components are not fully functional at this stage. (They form an assignment in another subject.) The recommended configuration is:

yallara

 make ssun 

linux

 make slinux 

This is the complete list of compile options.

root@skynet ~/cs516 # make
---- Makefile for BART ----
 
make linux        If you are using Linux, and you             
                  have the SVGA, X11, OSF/MOTIF and MESA      
                  libraries.                                  
 
make slinux     If you are using Linux, and don't want all   
                 the MOTIF & MESA junk.                      
 
make irix         If you are using an SGI'ish machine         
                  with X11, OSF/MOTIF and OpenGL libaries.    
 
make sun          If you are using a SUN OS machine           
                  with X11 and OSF/MOTIF.                     
 
make ssun         If you are using SUN OS and you only need   
                  X11 support.                                
 
---- Good luck! ----

I have been having problems with certain texturing functions when compiling on yallara. These problems have not been fixed at this stage, but do not affect linux binaries.


Tiled Texture "A tiled texture"

(600x600 True Color JPG - 218K)

Known Bugs

Many components of a raytracer need to make floating point comparisons which are vulnerable to rounding errors. Fudge values (thresholds) have been set to values that seem to work.

Many aspects of the design of the object heirachy need serious revision, particularly those that I wrote when I hardly knew any C++.

Selecting an image size that exceeds the 64K array limit under DOS will caused undefined behaviour.

The raytracer is supposed to abort if parsing/initialisation fails. This is not always the case, especially with incorrect filenames for mesh models and textures.

Polygon texturing is not correct since all polygon transforms are copies of the mesh transform. The texturing looks OK as it is, so this problem has been given low priority.

The parsing module leaks memory.

Temporary files are sometimes left in /tmp when parsing is aborted by the user, or when the raytracer has a problem with the input file.

The physical object class uses a clone member function, which sould be replaced by a copy constructor.

The ability to use container objects, (ie. A generalisation of polygon meshes) has not been implemented.

The point inside box function has been relaxed so that intersections near the boundary of a voxel are not rejected. This would be better implemented by letting the voxels overlap slightly.

The use of Constructive Solid Geometry (CSG) was built into the design of this raytracer, but has not been implemented.

Due to an obscure bug in my gcc libraries, floating point numbers will crash i/o streams. The file real.c contains a work-around for this problem.

For every bug you know about, there's at least 10 more...


The Globe "The Globe"

(1024x1024 True Color JPG - 55K)

Acknowledgements

The 3 Dimensional scalar and vector noise functions are borrowed from the rayshade package.

The nanostructure and polygon models were provided by Geoff Leach , original sources unknown.

The sphere/box intersection test is based on an article in Graphics Gems.

My thanks to Antti Kuosmanen for his Jolt texture and inspiration!

I wish to thank my girlfriend Fiona who has put up with many of my bad moods and lack of sleep as a result of the development of this raytracer. Thanks Fi!


Nigel Stewart, 17th November 1995


A Nanostructure "A Nanostructure"

(1280x1280 True Color JPG - 209K)

(C) 1997-2004 Nigel Stewart
Last Updated: Nov 6th 2004