Friday Nov 20

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:
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 plugs o+td into x2+y2+z2-1=0 and then solves the ensuing quadratic equation. In jgl There are classes for solving equations in roots.h, documentation is in ~tigges/html/jgl.

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 called jRay exists in jgl.
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.

Friday Nov 6

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 B and geometry matrix G (please consult Foley et al for construction of G) subsititute some constant 0..1 for t and form the product:

p = [x y z] = [t3 t2 t 1]*B*G
Remember that this sets up a system of cubic equations parameterized on t, one each for x, y, and z.  To compute the first derivative of those equations is trivial, just take the first derivative of the components of the parameterization:
t = [dx dy dz] = [3t2 2t 1 0]*B*G
It is important to realize that this is a displacement vector, p is a point, t is a vector. The tangent on the curve described by B*G at p has direction t.  That is p+kt lies on the tangent line of the curve at point p. (For some scalar k.)

In jgl there are no 3D homogeneous vectors, multiplication with a 4x4 matrix uses an assumed value of 1 for the homogeneous coordinate.  Therefore forming a jVec3 for  [3t2 2t 1 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 given t over a given G for 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 vector t' sampled on the curve compute the angular difference between t and t' around both the x axis and the y axis. Consider the following picture:

If you rotate n and b by the rotation matrix which rotates t into t' then you will have n' and b'  which will form a basis for the curve at the point for which t' is a tangent (in the above case rotate first about x by alpha and then about y by 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 t in 0..1 returns a point and a tangent on the curve.  Not some segment, but the entire curve.  This means given that t you must figure out which segment it is in and remap the t to 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
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/ex2 and ~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 at least one 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.