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*GRemember 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*GIt 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 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/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':
- 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, where cpi and cpi+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...
In all cases I do not want to see any debugging statements to the output
streams. Please remove them before submitting.