The Lathe Shape


The Lathe Curve

LatheCurve takes two arrays of x- and y-values as input, and creates two new arrays of x- and y-values representing the curve. The difference between the two pairs of arrays is the addition of interpolated points in the second group to represent curve segments. This change is illustrated by Figure 17-9, where the input arrays have 3 points, but the lathe curve arrays have 13.

Figure 17-9. Interpolating curves


If all the input points became the starting and ending coordinates for curve segments, then the size of the output arrays would be (<number of points> - 1)*(<STEP> + 1) + 1, where STEP is the number of introduced interpolation points.

Unfortunately, the sizes of the output arrays is a more complicated matter since points connected by straight lines don't require any additional points. The size calculation is implemented in countVerts( ), which checks the sign of each x value in the input array (xsIn[]) to decide on the number of output points:

     private int countVerts(double xsIn[], int num)     {       int numOutVerts = 1;       for(int i=0; i < num-1; i++) {         if (xsIn[i] < 0)   // straight line starts here           numOutVerts++;         else    // curve segment starts here           numOutVerts += (STEP+1);       }       return numOutVerts;     }

Specifying Curve Segments

A crucial problem is how to interpolate the curve segment. Possible methods include Bezier interpolation and B-splines. I use Hermite curves: a curve segment is derived from the positions and tangents of its two endpoints. Hermite curves are simple to calculate and can be generated with minimal input from the user. For a given curve segment, four vectors are required:

P0 The starting point of the curve segment

T0 The tangent at P0, analogous to the direction and speed of the curve at that position

P1 The endpoint of the curve segment

T1 The tangent at P1

Figure 17-10 illustrates the points and vectors for a typical curve.

Figure 17-10. Hermite curve data


The longer a tangent vector, the more the curve is "pulled" in the direction of the vector before it begins to move towards the endpoint. Figure 17-11 shows this effect as tangent T0 is made longer.

Four blending functions control the interpolations:

  • fh1(t) = 2t3 - 3t2 + 1

  • fh2(t) = -2t3 + 3t2

  • fh3(t) = t3 - 2t2 + t

  • fh4(t) = t3 - t2

Blending functions specify how the intervening points and tangents between the starting and ending points and tangents are calculated as functions of an independent variable t. As t varies from 0 to 1, fh1(t) and fh2(t) control the transition from P0 to P1;

Figure 17-11. How lengthening the tangent vector T0 affects a curve


fh3(t) and fh4(t) manage the transition from T0 to T1. The resulting x- and y-values are calculated like so:

  • x = fh1(t)*P0.x + fh2(t)*P1.x + fh3(t)*T0.x + fh4(t)*T1.x

  • y = fh1(t)*P0.y + fh2(t)*P1.y + fh3(t)*T0.y + fh4(t)*T1.y

Blending Functions and Hermite Curves

You may be wondering where the blending functions come from. The math is straightforward and can be found in any good computer graphics textbook, for example, Foley and Van Dam (Addison-Wesley). I don't discuss it here as this is meant to be a jovial gaming pandect rather than a graphics tome.

A good online explanation on Hermite curve interpolation can be found at http://www.cubic.org/~submissive/sourcerer/hermite.htm, written by Nils Pipenbrinck. A Java applet, coded by Lee Holmes, allows the user to play with natural splines, Bezier curves, and Hermite curves and is located at http://www.leeholmes.com/projects/grapher/.


Implementation

The Hermite curve interpolation points are calculated in makeHermite( ) in LatheCurve. The points are placed in xs[] and ys[], starting at index position startPosn. The P0 value is represented by x0 and y0, P1 by x1 and y1. The tangents are two Point2d objects, t0 and t1:

     private void makeHermite(double[] xs, double[] ys, int startPosn,                 double x0, double y0, double x1, double y1,                 Point2d t0, Point2d t1)     {       double xCoord, yCoord;       double tStep = 1.0/(STEP+1);       double t;       if (x1 < 0)     // next point is negative to draw a line, make it         x1 = -x1;     // +ve while making the curve       for(int i=0; i < STEP; i++) {         t = tStep * (i+1);         xCoord = (fh1(t) * x0) + (fh2(t) * x1) +                  (fh3(t) * t0.x) + (fh4(t) * t1.x);         xs[startPosn+i] = xCoord;         yCoord = (fh1(t) * y0) + (fh2(t) * y1) +                  (fh3(t) * t0.y) + (fh4(t) * t1.y);         ys[startPosn+i] = yCoord;       }       xs[startPosn+STEP] = x1;       ys[startPosn+STEP] = y1;     }

The loop increments the variable t in steps of 1/(STEP+1), where STEP is the number of interpolated points to be added between P0 and P1. The division is by (STEP+1) since the increment must include P1. The loop does not add P0 to the arrays since it will have been added as the endpoint of the previous curve segment or straight line.

The Java equivalents of the blending functions are shown here:

     private double fh1(double t)     {  return (2.0)*Math.pow(t,3) - (3.0*t*t) + 1;  }     private double fh2(double t)     {  return (-2.0)*Math.pow(t,3) + (3.0*t*t); }     private double fh3(double t)     {  return Math.pow(t,3) - (2.0*t*t) + t; }     private double fh4(double t)     {  return Math.pow(t,3) - (t*t);  }

All this code allows me to flesh out the data points supplied by the user, but it requires each data point to have an associated tangent. Where do these tangents come from?

Calculating the Tangents

A tangent is required for each point in the input sequence. The aim is to reduce the burden on the user as much as possible, so LatheCurve is capable of generating all the tangents by itself.

The first and last tangents of a curve are obtained by making some assumptions about a typical shape. The primary aim is to make limb-like shapes, which are defined by curves starting at the origin, curving out to the right and up, and ending by curving back to the left to finish on the y-axis. This kind of shape is convex, with its starting tangent pointing to the right and the last tangent going to the left.

Both tangents should have a large magnitude to ensure the curve is suitably rounded at the bottom and top. These assumptions are illustrated in Figure 17-12.

Figure 17-12. Typical lathe curve with tangents


The code that handles all of this is located in LatheCurve's constructor:

     Point2d startTangent =       new Point2d((Math.abs(xsIn[1]) - Math.abs(xsIn[0]))*2, 0);     Point2d endTangent =       new Point2d((Math.abs(xsIn[numVerts-1]) -                    Math.abs(xsIn[numVerts-2]))*2, 0);

The xsIn[] array stores the user's x-values, and numVerts is the size of the array. The use of Math.abs( ) around the x-values is to ignore any negative signs due to the points being used to draw straight lines. The tangents are then each multiplied by 2 to pull the curve outwards making it more rounded.

The intermediate tangents can be interpolated from the data points, using the Catmull-Rom spline equation:

     Ti= 0.5 * (Pi+1 - Pi-1)

This grandiose equation obtains a tangent at point i by combining the data points on either side of it, at points i-1 and i+1. setTangent( ) implements this:

     private void setTangent(Point2d tangent, double xsIn[], double ysIn[], int i)     {       double xLen = Math.abs(xsIn[i+1]) - Math.abs(xsIn[i-1]);       double yLen = ysIn[i+1] - ysIn[i-1];       tangent.set(xLen/2, yLen/2);     }

Building the Entire Curve

The for loop in makeCurve( ) iterates through the input points (stored in xsIn[] and ysIn[]) building new arrays (xs[] and ys[]) for the resulting curve:

     private void makeCurve(double xsIn[], double ysIn[],                 Point2d startTangent, Point2d endTangent)     {       int numInVerts = xsIn.length;       int numOutVerts = countVerts(xsIn, numInVerts);       xs = new double[numOutVerts];    // seq after adding extra pts       ys = new double[numOutVerts];       xs[0] = Math.abs(xsIn[0]);    // start of curve is initialised       ys[0] = ysIn[0];       int startPosn = 1;       // tangents for the current curve segment between two points       Point2d t0 = new Point2d( );       Point2d t1 = new Point2d( );       for (int i=0; i < numInVerts-1; i++) {         if (i == 0)           t0.set( startTangent.x, startTangent.y);         else   // use previous t1 tangent           t0.set(t1.x, t1.y);         if (i == numInVerts-2)    // next point is the last one           t1.set( endTangent.x, endTangent.y);         else           setTangent(t1, xsIn, ysIn, i+1);   // tangent at pt i+1         // if xsIn[i] < 0 then use a line to link (x,y) to next pt         if (xsIn[i] < 0) {           xs[startPosn] = Math.abs(xsIn[i+1]);           ys[startPosn] = ysIn[i+1];           startPosn++;         }         else {   // make a Hermite curve           makeHermite(xs, ys, startPosn, xsIn[i], ysIn[i],                                   xsIn[i+1], ysIn[i+1], t0, t1);           startPosn += (STEP+1);         }       }     }  // end of makeCurve( )

The loop responds differently if the current x-value is positive or negative. If it's negative, the coordinates will be copied over to the output arrays unchanged (to represent a straight line). If the x-value is positive, then makeHermite( ) will be called to generate a series of interpolated points for the curve. This is the place where the negative number hack is implemented: if a coordinate has a negative x-value, then a straight line will be drawn from it to the next point in the sequence; otherwise, a curve will be created.

The two tangents, t0 and t1, are set for each coordinate. Initially, t0 will be the starting tangent, and then it will be the t1 value from each previous calculation. At the end, t1 will be assigned the endpoint tangent.

The new arrays of points, and the maximum height (largest y-value), are made accessible through public methods:

     public double[] getXs( )     {  return xs;  }     public double[] getYs( )     {  return ys;  }     public double getHeight( )     {  return height;  }



Killer Game Programming in Java
Killer Game Programming in Java
ISBN: 0596007302
EAN: 2147483647
Year: 2006
Pages: 340

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net