Inside the blob.c file, in the determination of the intersections,
there is the following suspicious lines:
(Sorry for the length of the quote, but I need some context)

    /*
     * Transform polynomial in a way that the interval boundaries are moved
     * to 0 and 1, i. e. the roots of interest are between 0 and 1. [DB 10/94]
     */

    l = intervals[i].bound;
    w = intervals[i+1].bound - l;

    newcoeffs[0] = coeffs[0] * w * w * w * w;
    newcoeffs[1] = (coeffs[1] + 4.0 * coeffs[0] * l) * w * w * w;
    newcoeffs[2] = (3.0 * l * (2.0 * coeffs[0] * l + coeffs[1]) + coeffs[2]) * w * w;
    newcoeffs[3] = (2.0 * l * (2.0 * l * (coeffs[0] * l + 0.75 * coeffs[1]) +
coeffs[2]) +
coeffs[3]) * w;
    newcoeffs[4] = l * (l * (l * (coeffs[0] * l + coeffs[1]) + coeffs[2]) + coeffs[3])
+
coeffs[4];

    /* Calculate coefficients of corresponding bezier curve. [DB 10/94] */

    dk[0] = newcoeffs[4];
    dk[1] = newcoeffs[4] + 0.25 * newcoeffs[3];
    dk[2] = newcoeffs[4] + 0.50 * (newcoeffs[3] + newcoeffs[2] / 12.0);
    dk[3] = newcoeffs[4] + 0.50 * (0.375 * newcoeffs[3] + newcoeffs[2] + 0.125 *
newcoeffs[1]);
    dk[4] = newcoeffs[4] + newcoeffs[3] + newcoeffs[2] + newcoeffs[1] + newcoeffs[0];

    /*
     * Skip this interval if the ray doesn't intersect the convex hull of the
     * bezier curve, because no valid intersection will be found. [DB 10/94]
     */

    if (((dk[0] >= 0.0) && (dk[1] >= 0.0) && (dk[2] >= 0.0) && (dk[3] >= 0.0) &&
(dk[4] >=
0.0)) ||
        ((dk[0] <= 0.0) && (dk[1] <= 0.0) && (dk[2] <= 0.0) && (dk[3] <= 0.0) &&
(dk[4] <=
0.0)))
    {
      continue;
    }


I now perfectly understand the l,w,newcoeffs part (it is as commented, a
transformation
to move the study interval from interval[i].bound,interval[i+1].bound to 0,1 .
I even checked the computation, and it is correct. 

I'm seeking information on the dk[] part.
dk[0] and dk[4] seems to be evaluation of the polynome at 0 and 1.
So far, so good.
But I do not understand the formulaes for dk[1,2 and 3].
It's look like some oversimplified evaluation of the polynom at some magic value,
dropping high coefficient. 
(polynom is newcoeffs[0].x^4 + newcoeffs[1].x^3 +.... + newcoeffs[4] )

Moreover, the test looks like a kind of Newton check, assuming that if all dk are from
the same sign, then the polynom has no root between 0 and 1.

This would be a valid assertion for a 1-polynom (linear form), 
with simply dk[0] and dk[4], but I cannot even find the justification for a 2-polynom,

and the worst part of it is that this code is dealing with just a 4-polynom, 
while the other dk are not even looking like any derivative or tangent 
(due to the constant being always there).

So, to keep my question simple: does anybody have the explanation for the formulae of
dk[1], dk[2] and dk[3] ? Any paper ? any hint ?

-- 
Non Sine Numine
http://grimbert.cjb.net/

Post a reply to this message