RMIT Department of Computer Science
CS516 Advanced Computer Graphics
Assignment 2 - Raytracer
Nigel Stewart
9304105H
1995
"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"
(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.
"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.
"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"
(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.
"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"
(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"
(1280x1280 True Color JPG - 209K)
|