We discussed in detail the material covered in Birthing a ray tracer. This material contained in that paper is self explanatory and should provide you with the understanding of the mathematics required to complete this assignment.

## Assignment 3 deliverables.

I don't have the assignment in front of me so bear with me. The assignment asks you to implement a ray tracer with has the ability to intersect a mesh. A mesh means a set of triangles defined by a set of vertices and a set of edges. The file format for the mesh file will arrive shortly. I do not recommend doing only this. I will likely take you longer than if you write a ray tracer to do only spheres, and then extend it to polygons. For this reason, one of the bonus points will be changed from sphere,cylinder,cone, to just cylinder and cone. (Besides once you have a sphere, cylinders and cones are trivial.) The first four bonus points will be one point extra, the fifth (bounding boxes and subdivision of space) will be worth five. I don't know yet how much the assignment will be graded out of, but suffice it to say a perfect assignment (full marks and full bonus) will get in the neighbourhood of 110% to 115%.

## Data Structures for a Ray Tracer

We didn't discuss this but I want to say a few words to reduce the number of questions. There are several fundamental data structures endemic to a ray tracer:

`Object`

The base class for all geometric objects. It has virtual functions for asking for the distance along a ray to the intersection with the object, and for returning the normal given an intersection point. These two functions do nothing but transform the given ray or point into object space (using the transformation matrices for the object) and deferring to higher level intersection routines.For example a

`Sphere`

class inherits from`Object`

and implements intersect and normal routines. The first thing it does is defer to`Object::intersect`

to provide the object space ray, then it plugso +td into x ^{2}+y^{2}+z^{2}-1=0 and then solves the ensuing quadratic equation. InjglThere are classes for solving equations inroots.h, documentation is in~tigges/html/jgl.`Ray`

This class is nothing more than a point in space and a unit vector direction. It is used to represent an infinitisimal ray in space for computing intersections. A class calledjRayexists injgl.`Material`

This class holds the illumination routine and stores material parameters for an object. Every object has an instance of this class to define its surface reflectance characteristics.There are many other classes that you can write to help make the implementation easier but these are the basics. You may want to consider`Camera`

,`Light`

,`BoundingBox`

.

I had hoped more people would show up so that we could have a discussion on how to make the labs more useful. Alas, the people who don't find them useful didn't come to voice their concerns. Blob and I have decided that this page should be here to allow students to check what might have happened during a particular lab, I will outline the discussion that took place and the material that was covered. I will also make public any answers that I gave to an individual or group regarding the course and assignments. This is to dispell any chance of chagrin and complaint from people claiming to not have had the same oppurtunity for discovery of such things.## Computing a tangent vector to a spline

There are two ways to handle this problem, numerically and analytically. The analytic method is preferred simply for accuracy. It is not subject to instability at portions of the curve where the curvature is high.To compute a point on a single segment of a spline with basis

Band geometry matrixG(please consult Foley et al for construction ofG) subsititute some constant 0..1 fortand form the product:Remember that this sets up a system of cubic equations parameterized onp =[x y z] = [t^{3}t^{2 }t1]*B*Gt, one each forx,y, andz. To compute the first derivative of those equations is trivial, just take the first derivative of the components of the parameterization:It is important to realize that this is a displacement vector,t= [dx dy dz] = [3t^{2}2t1 0]*B*Gpis a point,tis a vector. The tangent on the curve described byB*Gatphas directiont. That isp+ktlies on the tangent line of the curve at pointp. (For some scalark.)In

jglthere are no 3D homogeneous vectors, multiplication with a 4x4 matrix uses an assumed value of 1 for the homogeneous coordinate. Therefore forming ajVec3for [3t^{2}2t1 0] is impossible. To do this you should use the jVec3::hmult function. The following function returns the point on the curve and a normal vector for a giventover a givenGfor a b-spline curve.void bspline( const jMat4& G, jFlt t, jVec3& p, jNorm3& t ) { jFlt t2 = t*t; jFlt t3 = t2*t; jFlt w = 0; jMat4 P(B*G); p = jVec3(t3,t2,t)*P; t = jVec3(3*t2,2*t,1).hmult(P,w); }## Alternative method for forming a basis

When polygonizing the cylinder you need to form orthonormal bases at points along the curve. Typically this is done by rotating the previous basis by the angular difference between neighbouring samples of the tangent vector.An alternative method is to define a canonical basis, (for example

t=[0,0,1],n=[0,1,0],b=[1,0,0], for tangent normal and bivector). Now, for every tangent vectort'sampled on the curve compute the angular difference betweentandt'around both thexaxis and theyaxis. Consider the following picture:

If you rotatenandbby the rotation matrix which rotatestintot'then you will haven'andb'which will form a basis for the curve at the point for whicht'is a tangent (in the above case rotate first aboutxby alpha and then aboutyby beta). Since this method does not rely on any cross products the nature of the tangent to the curve (meaning above or below from inflection points) is irrelevant.

## Data structures

A few people have asked me to describe how I might set up data structures and algorithms to solve this problem. Not everybody, but some. To avoid backlash, I will place my thoughts on this question here.First design a class which maintains a list of control points. The main purpose of this class is to abstract out the segments of a b-spline. I would have a function which given a

tin 0..1 returns a point and a tangent on the curve. Not some segment, but the entire curve. This means given thattyou must figure out which segment it is in and remap thetto the 0..1 of that segment. For instance, if you have two segments than the global curve parameters' domain of 0..0.5 maps to the 0..1 domain of the first segment and 0.5..1.0 of the second segment. This allows you to forget about the notion of segments and all the nastiness there involved and concentrate on polygonization.I would also design a class which given a curve (as described above) would hold a sequence (linked list or array) of sequences of points. This is a set of samples on the curve, and for each sample a set of points which approximate a circle lieing in the plane whose normal is colinear with the tangent of the curve at that point.

Both of these classes should have a draw function. The first class draws a curve using GL_LINE_STRIP. The second draws a series of polygons using GL_TRIANGLE_STRIP. For documentation on how to use these parameters see the glBegin documentation at http://www.hp.com/unixwork/products/grfx/OpenGL/Web/Reference.html.

Don't forget to specify normals (correctly, ie unit length) for the vertices of your triangles.My preference is for a program which allows editing of the spline curve and allows the user to specify that a curve should be polygonized (ie through a glut menu). When the user makes that choice, the polygons are computed and stored in a large data structure, the 3D window is told to redraw itself (using the data structure). The 3D window merely draws the polygons in the data structure and does not compute the triangulation itself.

## What do I expect?

This is a good question and previously if somebody didn't ask it they subsquently got upset. Oh well. So, the assignment is to draw a generalized cylinder constructed by sweeping a circle around a b-spline, using OpenGL lighting of polygons. To accomplish this you should provide an interactive facility for editing the control points. The bare minimum is to append a control point to a list of control points and be able to move all of them. The curve may be constrained to any plane you like (if it is the Frenet frames are sufficient to avoid discontinuities in the frame computations). You have example code (~tigges/src/555/ex2and~tigges/src/555/ex3) which is in my opinion more than adequate to solve this problem.For groups I expect more. This should be assumed. Here are some suggestions for what you could do to satisfy 'more':

I would expect to see

- Do not constrain the curve to a single plane. There are two issues involved, a) you must provide a suitable interface for editing all 3 dimensions of each control point (I suggest a 2D view of each axis plane), b) you must solve the discontinuities that will result when polygonizing the curve. This second problem has been dealt with extensively in the notes, on the exam in the tutorials and now here on this page.
- A very nice interface. This means I can insert points in at least both ends of the curve, preferrably in the middle as well. The curve is redrawn in the 2D window(s)
as I move control points, this is important to being able to design a desired curve. I can double up control points, wherecpand_{i}cp_{i+1 }share a common position. This allows me to remove continuity of higher derivatives. [Note: A very nice interface also means as little menu selection and clicking as possible. ]- Allow viewing of the generalized cylinder in wireframe, polygons, and just the curve and the computed bases for sample points on the curve. (You may want to do the latter regardless, to facilitate debugging.)
- Sweep an arbitrary curve around the spline, not just a circle. This requires another interface facility for specifying the curve to be swept. Also it makes it considerably more difficult to find the normals on the surface of the generalized cylinder. (It isn't difficult, but compared to the trivial nature with the circle case it is more difficult.)
- Anything that you can think of...
at leastone of the above for a group assignment. I would recommend doing two of them.In all cases I do not want to see any debugging statements to the output streams. Please remove them before submitting.