Errata to _Graphics Gems_, first edition, edited by Andrew Glassner
Academic Press 1990. Code available online at http://www.graphicsgems.org/
compiled by Eric Haines (erich@acm.org) from author and reader contributions
version 1.32
date: 9/11/2008
-----
Errors in the text:
p. 3, bottom: The equation "N . P + c = 0" is better expressed as
"N . P - c = 0" in order to match Figure 1a. [also see p. 9 errata]
p. 5, V2 Perpendicular: change "N <- (-Vx, Vy)" to "N <- (-Vy, Vx)"
p. 5, V2 Reflect: change "N <- (-Vy, -Vx)" to "N <- (-Vx, -Vy)"
p. 6: change P1 and P2 lines to
P1 <- (( -b+sqrt(d) ) / 2a) * lv + lu
P2 <- (( -b-sqrt(d) ) / 2a) * lv + lu
i.e. the value computed is multiplied by the direction vector and the
line's origin is added to this new vector to get the intersection point.
p. 9-10, starting at bottom: If the equation on p. 3 is expressed as
"N . P - c = 0", then change all "+ c" references to "- c" and "l-sub-c"
to "- l-sub-c".
p. 10, for "if not l-normalized", the operation in the next line should divide
q by "( l-sub-n dot l-sub-n)", not "Length( l-sub-n )".
p. 11, bottom: change the lower bound of the sum (sigma) from i=1 to i=0.
p. 16, Product Relations. In the right hand parts of the equations the cosine
and sine functions should be applied only to the numerator, then the
division by 2 is done. Specifically:
sin(a)*sin(b) = cos(a-b)/2 - cos(a+b)/2
cos(a)*cos(b) = cos(a-b)/2 + cos(a+b)/2
sin(a)*cos(b) = sin(a+b)/2 + sin(a-b)/2
p. 105, last sentence of first paragraph: "ajacent" to "adjacent".
p. 216, caption for figure 2: "54" should read "45" to be consistent with
the figure (error in two places in caption).
p. 224, the Bit Width 23 mask is listed as 0x00400000, it should be
0x00420000.
p. 282, 5 and 7 lines from bottom: should read
"then PUSH(dadRx + 1, rx, pushlx, pushrx, y-dir, -dir )"
and
"then PUSH(lx, dadLx-1, pushlx, pushrx, y-dir, -dir )"
i.e. the final "dir" should be "-dir".
p. 283, 3 lines from bottom: add an "end" above the "else begin".
p. 284, 12 lines down: move "x <- x + 1;" to after the next "end" statement
(move it down only one line).
p. 299, bottom: P1 and P2 as shown are actually the distances along the line
from the line's origin (l.sub.U). Change the P1 and P2 lines to
t1 = (-b + sqrt(d)) / 2a
t2 = (-b - sqrt(d)) / 2a
P1 <- l.sub.U + t1 * l.sub.V
P2 <- l.sub.U + t2 * l.sub.V
p. 365, last line: "Kajia" to "Kajiya".
p. 375, "revlect v" to "reflect v".
p. 395, first paragraph: change "discussed by Haines (1989)" to "discussed by
Haines in Glassner (1989)".
p. 406, last equation: if q is negative, the same signs should be used for the
square root terms, i.e.
y^2 +- y sqrt(2z - p) + z +- sqrt(z^2 - r) = 0
p. 427, equation: the y/x was flipped, and the x not multiplied through. The
right hand side should read:
x + 1/2 x [y/x]^2 - 1/8 x [y/x]^4 + O x [y/x]^6
[from Ben St. John, 8/11/2004]
p. 448, last sentence of second paragraph: change "and now nearly as simple"
to "and not nearly as simple".
p. 463, second to last line: change "then alpha <- alpha + pi/2" to "then
alpha <- pi - alpha".
p. 479, Table 1: the number of Multiplies for rotation should be 16, not 12.
p. 495, equation 5: this should have an equal sign (=) before the
plus-or-minus (+/-).
p. 499, middle of page: change "and i,j,K" to "and i,j,k".
p. 503, last sentence: change "Let P' = Rot_(alpha, N) ..." to "Let P' =
Rot_(theta, N) ...".
p. 516, last paragraph: a reader notes an additional reference which
predates Berger and Salmon & Slater, namely "The Viewing Transformation,"
Technical Memo. no. 84, Alvy Ray Smith, Computer Graphics Project,
Lucasfilm, June 24, 1983 (rev. May 4, 1984).
p. 602, second paragraph: the matrix Tij should be:
[ 1 0 0 0 ]
[ 0 1/2 0 0 ]
[ 0 0 1/4 0 ]
[ 0 0 0 1/8 ]
p. 610: the binomial "( n-i [over] j )" should be "( n-1 [over] j )". This
error appears on the fifth line of the long derivation and within the
Zi,j definition.
p. 614: the equation "Bi,n(t) = (1-t)Bi-1,n-1 + tBi-1,n-1(t)" should be
"Bi,n(t) = (1-t)Bi,n-1(t) + tBi-1,n-1(t)"; the first right-hand side
term had an incorrect subscript and was missing a "(t)".
p. 809: the author of "Approximation of Sweep Surfaces by Tensor Product
B-Splines" is M. (not J.) Bloomenthal. The author is correctly
attributed in the text (page 569).
p. 814: 5th line from bottom. "Knuth 1981" should read "Knuth 1981b" and
"Vol. 2" should read "Vol. 1". The reference above this should be
"Knuth 1981a".
p. 820, 9th line from bottom: "D.P. Greenburg" should be "D.P. Greenberg".
-----
The following are errors in the code listings (corrected in the online code at
http://www.graphicsgems.org/).
Serious errors (ones your compiler cannot or may not catch):
p. 630: Delete FLOOR and CEILING macros (they're more like truncations).
Change ROUND macro to (i.e. add parentheses around "a"):
#define ROUND(a) ((a)>0 ? (int)((a)+0.5) : -(int)(0.5-(a)))
Change SGN macro to (i.e. change positive condition result to "1"):
#define SGN(a) (((a)<0) ? -1 : 1)
p. 632: procedure declarations for routines in the "2D and 2D Vector C
Library" (next pages) are missing from "GraphicsGems.h", e.g.
double V2SquaredLength() ;
double V2Length() ;
Vector2 *V2Negate() ;
...
p. 638, third line from bottom: in V3Combine change last "result->y" to
"result->z"
p. 640: V3MulPointByMatrix() does not work. A separate local Point3 (e.g.
"Point3 q ;") should be used in place of "p" for assignment and then
passed back.
p. 649, top: add "#include "
p. 655, top: add the code:
if ((px == qx) && (py == qy))
if ((tx == px) && (ty == py)) return 2;
else return 0;
in order to test for the special case where the line endpoints are
the same.
p. 656, line 23: change "return ((R->min.x * R->min.x) < Rad2);" to
"return ((R->min.x * R->min.x + R->max.y * R->max.y) < Rad2);"
p. 656, line 25: change
"return ((R->min.x * R->min.x + R->min.y + R->min.y) < Rad2);" to
"return ((R->min.x * R->min.x + R->min.y * R->min.y) < Rad2);"
(thanks to Ben Dawson)
p. 662, line 10: add "#include "
p. 665, line 1: change "FLOOR(...)" to "(floor((double)(...))".
p. 663, line 45: change first "+" to "="; should read
"VnextLeft = (Vleft=VnextLeft) + 1;"
p. 667, line 6: change "POLY_NMAX 8" to "POLY_NMAX 10" (for triangles and
quadrilaterals). Six clipping planes used on convex polygons gives
+6 potential extra vertices generated.
p. 670-673, throughout: change "int mask" declarations to "unsigned long
mask" declarations. This avoids an infinite loop occuring when the
highest bit is set.
p. 676, line 11: add the line "up = (double *)u;"
p. 671, line 1: add at top of page the following test (or make sure the
Poly_vert structure has <= 32 doubles at compilation time):
if (sizeof(Poly_vert)/sizeof(double) > 32) {
fprintf(stderr, "Poly_vert structure too big; must be <=32 doubles\n");
exit(1);
}
p. 687, line 8: Identical points cause two points to be drawn. Between the
first two plot() commands, add the line:
if ( pixels_left < 0 ) return ;
p. 714, line 20: the last "1" in "if (i + 1 < l * 1)" should be an "l"
p. 716, line 27: missing "/" at end of comment (if not fixed, code compiles
but is wrong)
p. 720, lines 3 and 6 from bottom: change "m+1>>1" to "(m+1)>>1" to establish
correct evaluation order.
p. 737, lines 19-24, from "if ((quadrant..." to "}", should read (and note
corrected indentations on "else" statement):
if (coord[i] < minB[i] || coord[i] > maxB[i])
return (FALSE);
} else {
coord[i] = candidatePlane[i];
}
p. 742, lines 18-24 should read:
coeffs[ 0 ] = z - u;
coeffs[ 1 ] = q < 0 ? -v : v;
coeffs[ 2 ] = 1;
num = SolveQuadric(coeffs, s);
coeffs[ 0 ]= z + u;
coeffs[ 1 ] = q < 0 ? v : -v;
coeffs[ 2 ] = 1;
The sign of "q" affects the sign of coeffs[1].
p. 744, line 6 reads:
double coef[MAX_ORDER];
and should read:
double coef[MAX_ORDER+1];
(thanks to Chaok Seok)
p. 745, throughout: delete references to "lx", which is set but not used
p. 748, line 22: change "negetive" to "negative"
p. 753, line 35: change "int n1, n2," to "int n1=0, n2=0," so that first
fprintf() error message has defined values
p. 756, line 15: "unsigned int *fi=&f;" to
"unsigned int *fi = (unsigned int *) &f;" for type
consistency, and some compilers think "=&" means "&="
p. 766, top: add '#include "GraphicsGems.h"' and '#include '
line 25: change "det = det4x4( out );" to "det = det4x4( in );"
throughout: change "matrix4" to "Matrix4"
p. 774, line 5: change "theta," to "theta = 0,"
pp. 793-794:
There seem to be errors in the ControlPolygonFlatEnough function in the
Graphics Gems book and the repository (NearestPoint.c). This function
is briefly described on p. 413 of the text, and appears on pages 793-794.
I see two main problems with it.
The idea is to find an upper bound for the error of approximating the x
intercept of the Bezier curve by the x intercept of the line through the
first and last control points. It is claimed on p. 413 that this error is
bounded by half of the difference between the intercepts of the bounding
box. I don't see why that should be true. The line joining the first and
last control points can be on one side of the bounding box, and the actual
curve can be near the opposite side, so the bound should be the difference
of the bounding box intercepts, not half of it.
Second, we come to the implementation. The values distance[i] computed in
the first loop are not actual distances, but squares of distances. I
realize that minimizing or maximizing the squares is equivalent to
minimizing or maximizing the distances. But when the code claims that
one of the sides of the bounding box has equation
a * x + b * y + c + max_distance_above, where max_distance_above is one of
those squared distances, that makes no sense to me.
I have appended my version of the function. If you apply my code to the
cubic Bezier curve used to test NearestPoint.c,
static Point2 bezCurve[4] = { / A cubic Bezier curve /
{ 0.0, 0.0 },
{ 1.0, 2.0 },
{ 3.0, 3.0 },
{ 4.0, 2.0 },
};
my code computes left_intercept = -3.0 and right_intercept = 0.0, which you
can verify by sketching a graph. The original code computes
left_intercept = 0.0 and right_intercept = 0.9. (from James Walker,
jw@jwwalker.com, 9/10/2008)
Revised code:
static int ControlPolygonFlatEnough(V, degree)
Point2 *V; /* Control points */
int degree; /* Degree of polynomial */
{
int i; /* Index variable */
double value;
double max_distance_above;
double max_distance_below;
double error; /* Precision of root */
double intercept_1,
intercept_2,
left_intercept,
right_intercept;
double a, b, c; /* Coefficients of implicit */
/* eqn for line from V[0]-V[deg]*/
double det, dInv;
double a1, b1, c1, a2, b2, c2;
/* Derive the implicit equation for line connecting first *'
/* and last control points */
a = V[0].y - V[degree].y;
b = V[degree].x - V[0].x;
c = V[0].x * V[degree].y - V[degree].x * V[0].y;
max_distance_above = max_distance_below = 0.0;
for (i = 1; i < degree; i++)
{
value = a * V[i].x + b * V[i].y + c;
if (value > max_distance_above)
{
max_distance_above = value;
}
else if (value < max_distance_below)
{
max_distance_below = value;
}
}
/* Implicit equation for zero line */
a1 = 0.0;
b1 = 1.0;
c1 = 0.0;
/* Implicit equation for "above" line */
a2 = a;
b2 = b;
c2 = c - max_distance_above;
det = a1 * b2 - a2 * b1;
dInv = 1.0/det;
intercept_1 = (b1 * c2 - b2 * c1) * dInv;
/* Implicit equation for "below" line */
a2 = a;
b2 = b;
c2 = c - max_distance_below;
det = a1 * b2 - a2 * b1;
dInv = 1.0/det;
intercept_2 = (b1 * c2 - b2 * c1) * dInv;
/* Compute intercepts of bounding box */
left_intercept = MIN(intercept_1, intercept_2);
right_intercept = MAX(intercept_1, intercept_2);
error = right_intercept - left_intercept;
return (error < EPSILON)? 1 : 0;
}
p. 799, line 32: add between first "DrawBezierCurve(...);" call and "return;":
free((void *)bezCurve);
p. 799, bottom and p. 800, line 11: add this pair of lines between
"DrawBezierCurve(...);" and "return;":
free((void *)u);
free((void *)bezCurve);
Also, see errata note at end of this file.
p. 800, line 5: an additional:
free((void *)bezCurve);
must be done before assigning bezCurve = GenerateBezier, to avoid a leak.
Also:
free((void *)uPrime);
must be added to the free list in the next correction.
(thanks to Wolfram Esser)
line 19: add this pair of lines before "tHatCenter = ...":
free((void *)u);
free((void *)bezCurve);
p. 801, 9 from the bottom: change
det_C0_X = C[0][0] * X[1] - C[0][1] * X[0];
to:
det_C0_X = C[0][0] * X[1] - C[1][0] * X[0];
Also in this code, it is better to set alpha_l and alpha_r to 0 if
the det_C0_C1 determinant is 0, to avoiding dividing by 0 when
C[0][0]*C[1][1] is 0 in the corrective code. Correction has been
made to the code itself. (thanks to Steve Anderson)
p. 802, line 2: Change " < 0.0" to " < 1.0e-6" in the alpha tests. Otherwise
you get coincident control points that lead to divide by zero in any
subsequent NewtonRaphsonRootFind() call. Further correction from
Steve Anderson of scaling the alpha_l and alpha_r < 1.0e-6 tests by
the distance between the first and last points. See code for corrections.
p. 803, line 5 from bottom: add
if (denominator == 0.0f) return u;
before uPrime is computed, to avoid division by zero.
(thanks to Steve Anderson)
Syntax errors (ones your compiler or lint will catch):
p. 633-642, throughout: replace "};" with "}" to make lint happy
p. 640, gcd(): the variable "k" is set but not used - remove it
p. 649, line 31: change "LengthVector3" to "V3Length"
p. 650, line 1: bad end-of comment; delete "/"
p. 651, throughout: Can't use "const" as a variable name, as it is a reserved
word in ANSI C. Use "liconst" instead.
p. 657, 659: make "nicenum" declarations match, i.e. use either "double
nicenum()" or "static double nicenum()" for both occurrences
p. 659: change "exp" to "expv", since "exp()" is a math library function.
p. 660, line 11: header missing end of comment "*/"
p. 662, line 13: change "SYBYRES" to "SUBYRES"
line 16: bad space after "MODRES"
line 42: change "XRmax" to "xRmax"
p. 665, line 15: missing semicolon after "int area"
line 27: change "O" to "0" in "if (partialArea>O)"
p. 666, line 13: change "O" to "0" in "rightMask = O;"
p. 670, top: add to make lint happy
static scanline();
static incrementalize_y();
static incrementalize_x();
static increment();
p. 671, line 35: missing "{" at end of "while (y" (or strings.h)
p. 727, line 11: remove ")" in "static double bigC,..." line
p. 728, lines 21-23: change "cal_q_msq" to "calc_q_msq"
lines 23,42: change "NULL" to "(double *)NULL" to make lint happy
line 26: change "con_const" to "cone_const" in
"bigC = m1sq + con_const * q1"
last line: add a "}" to end albers_project procedure
p. 730: missing inclusion of GraphicsGems.h.
p. 734, line 4: change "exit();" to "exit(1);"
p. 736, line 20: change "O" to "0" in "for (i=O;"
p. 739, line 12: change "else if (D > 0)" to "else", since at this point
D must be greater than 0; makes lint happy
p. 757, line 4: change "{" to "[" in "sqrttab{"
line 14: change "= &n" to "= (unsigned int *)&n"
line 21: change "*num & = 0x7fffff:" to "*num &= 0x7fffff;" to fit
ANSI C, and to fix error of ":" at end of line.
line 22: change "| =" to "|="
line 27: change ":" to ";"
p. 765, line 20,22: change "Matrix" to "Matrix4"
p. 766, line 29: change "exit();" to "exit(1);"
p. 774, line 2: missing ";" at end of "long *argx, *argy"
p. 775: P, Q, and M need to be declared as externs
p. 780, line 18: bad start of comment for "/ re-parameterization"
p. 785, line 1: bad start-of-comment
p. 789, lines 7,25: change both "NULL" to "(Point2 *)NULL" to make lint happy
in ConvertToBezierForm: "t" is not used, can be deleted
p. 791, line 24: remove "break;" after "return 0;"; unnecessary
p. 795, ComputeXIntercept: "T" and "Y" do not have to be computed, since
the result "Y" is not returned. Note that there are many
operations in this routine that are unnecessary (e.g. "0.0 - 0.0").
p. 797-807, throughout: change "V2ScaleII" to "V2ScaleIII" and "Bezier" to
"BezierII" in order to avoid name collisions with the code on pages
787-796 (i.e. the same subroutine names are used in both, but with
different argument types, etc). Important only if you link in both
of these subroutine libraries.
-----
The following are typographical errors in the comments:
p. 687, line 3: "plottted" to "plotted"
p. 701, line 26: change "interscetion" to "intersection"
p. 723, line 1: "tight" is not used in the strict mathematical sense
that the sphere generated is optimal (i.e. no smaller sphere could be
found), but rather meaning "near optimal".
p. 728, line 10: "latitute" to "latitude"
p. 729, line 8: "degress" to "degrees"
p. 724, line 38: "seperated" to "separated"
p. 725, lines 7-9: "componant" to "component"
p. 730, line 17: "minium" to "minimum"
p. 752, line 2: "positve" to "positive"
p. 760, line 5: "interger" to "integer"
p. 761, line 4: "preceed" to "precede"
p. 766, throughout (5 times): "determinent" to "determinant"
p. 781, lines 7,23: "demoninator" to "denominator"
-----
Addenda: There is additional code for Kelvin Thompson's "Rendering
Anti-Aliased Lines" gem in the online distribution of the code.
-----
Concerning page 799, Philip Schneider's Bezier code:
If you are operating in a dimensional system such that the desired error in
the fitting process is a fraction (e.g., 0.01 inches) rather than a whole
number (e.g., 2.0 pixels), then the line on page 799 reading
iterationError = error * error;
should be changed to
iterationError = ERRFACTOR * error;
where ERRFACTOR is #defined to some implementation-dependent value such as
4.0. If this is not done, then reparameterization will never occur. The
result is not an erroneous curve, but a suboptimal one; the algorithm will
always subdivide when the initial fit is too "loose."
(from Earl Boebert, boebert@SCTC.COM)