The Task

Module Structure

There are seven modules in this assignment: Physics, WorldBase, World, RayTracer, Renderer, PpmWriter and SceneParser. We will let you work out the module dependecies for yourself, but we will tell you that all modules import Physics (except Physics itself naturally.)

You will be defining functions in two modules: PpmWriter and World. The code in PpmWriter can be written (and tested) fairly independently of the other modules and we suggest you do this.

Bonus ONLY: For the bonus part, you need to define some functions in RayTrace.

A note on preconditions

A few of the functions below have pre-conditions that must be satisfied for them to work properly. Any function that is called with arguments that do not satisfy the pre-conditions will result in undefined behaviour. It is up to the user of such functions to ensure that they hold, and it is not strictly necessary for you to check whether they do or not.

However a common software engineering practice is to check for them anyway and signal an error if so. This can make it much easier to debug your program hence it may be useful for you to do this.

If you read the documentation for the Physics module you will see that some of these functions have pre-conditions as well. These are not checked.

Functions to define

module PpmWriter

type Size = (Int, Int)
type Image = (Size, [[Colour]])

writePpm :: FilePath -> Image -> IO ()

This function takes a FilePath and an Image. The image, which is a square area of colour values, is then written to disk in PPM format. Be aware that the Colour in an Image is not in the correct format for writing to the PPM file; hence, you need to convert it appropriately.

Here is a link to the PPM format.

Ray tracing may take quite a long time. You may wish to print to standard output (not the file!) some indication of progress being made. For instance, our implementation of this assignment prints the row number at the completion of each row. Another possibility would be to print a dot after each line. A dot for each pixel would probably be excessive.

module World

Functions are listed in approximate order of difficulty. It is also sometimes the case that earlier functions are useful in defining later ones.

getOctantIndex :: Point -> Voxel -> Int

Takes a Point and a Voxel and returns the index of the sub-octant the point is in. As mentioned in the section on OctTrees, octants are numbered as follows.

Front face	Back face
2 3 0 1	6 7 4 5

Be sure to take care on which points are and aren't inside a voxel. See the section on Points and Voxels.

getOctants :: Voxel -> [Voxel]

Takes a Voxel and returns a list containing eight voxels which sub-divide the voxel. The voxels should be in order of their index. The following equation should hold:

isInVoxel pt voxel == isInVoxel (getOctants voxel !! getOctantIndex pt voxel)

findMinSize :: OctTree -> Distance

findMinSize takes an OctTree and returns the size of the smallest leaf within it.

getLeafContaining :: Point -> Scene -> OctTree

This function takes a Point and a Scene and returns the leaf of the OctTree contained within the scene that contains the point.

mkOctTree :: Voxel -> [Object] -> OctTree

This functions takes a Voxel that contains the scene, a list of Objects and yields an OctTree. Each Leaf of the OctTree must contain at most maxObjects objects. You will need to recursively sub-divide each Node that contains more objects than this.

module RayTrace   Bonus ONLY!

intersectsInVoxel :: [Object] -> Voxel -> Ray -> [(Object, Time, Vector)]

Bonus ONLY: Takes a list of Objects, a Voxel and a Ray and yields a (possibly empty) list of ordered triples. Each triple contains an object, the time at which the ray intersected the object in the voxel and a unit normal vector at the point of intersection. The list is ordered such that the interesection with the smallest time value is first, followed by the next greatest time value and so on.

Be careful in detecting intersections with objects, particularly planes. It is quite possible that although part of the object will be inside the voxel the intersection actually occurs at a point outside the voxel. These should not be counted.

firstIntersect :: Scene -> OctTree -> Ray -> Maybe (Object, Time, Vector)

Bonus ONLY: Takes a Scene, a leaf, and a Ray (which passes through the leaf). Finds the first (non-zero and positive) intersection with an object, if one exists, and returns the object and the time at which the ray intersects the object.

This function checks if there are any intersections in the leaf. If not it will try the next leaf that ray passes through. This process terminates when an intersection is found or the ray passes out of the scene (i.e. leaves the Voxel containing the entire Scene). If no intersection exists Nothing is returned.

This function should not return a Time value of zero or a negative value. The reason for this is that this function will often be used to see whether a ray to a light source intersects with any objects in between. Since this ray originates at the surface of the object an intersection can often be detected at time equal to zero. Were it the case that floating-point arithmetic was exact this would not be problem, yet this is not the case. (In fact, this makes sense if you think about it, how can a continuous spectrum of numbers be represented in a finite amount of space if it is not approximate?) We also are not interested in intersections at negative times. Such intersection occur in the reverse direction of the ray which is not what we want at all.

Do not use the (==) from the Prelude. Instead use the (==*) from the Physics module which checks whether two Doubles are equal to within a small tolerance (defined as doubleRes in module Physics.)

Precondition: Ray passes through leaf.

checkShadowIntersect :: Scene -> Point -> Light -> Ray -> Bool

Bonus ONLY: Checks whether there is an intersection with another object before the light source. Takes a Scene, the point of intersection, a Light, and a Ray to that light as arguments. Precondition: The ray must actually point at the light.