Slic3r::Measure::RootsPolynomial Class Reference

#include <src/libslic3r/MeasureUtils.hpp>

Static Public Member Functions
static int32_t	Find (int32_t degree, const double *c, uint32_t maxIterations, double *roots)
static bool	Find (int32_t degree, const double *c, double tmin, double tmax, uint32_t maxIterations, double &root)
static int32_t	FindRecursive (int32_t degree, double const *c, double tmin, double tmax, uint32_t maxIterations, double *roots)
static double	Evaluate (int32_t degree, const double *c, double t)

Detailed Description

Member Function Documentation

Evaluate()

static double Slic3r::Measure::RootsPolynomial::Evaluate ( int32_t  degree, const double *  c, double  t  )

inlinestatic

    {
        int32_t i = degree;
        double result = c[i];
        while (--i >= 0) {
            result = t * result + c[i];
        }
        return result;
    }

Referenced by Find().

Here is the caller graph for this function:

Find() [1/2]

static bool Slic3r::Measure::RootsPolynomial::Find ( int32_t  degree, const double *  c, double  tmin, double  tmax, uint32_t  maxIterations, double &  root  )

inlinestatic

    {
        const double zero = 0.0;
        double pmin = Evaluate(degree, c, tmin);
        if (pmin == zero) {
            root = tmin;
            return true;
        }
        double pmax = Evaluate(degree, c, tmax);
        if (pmax == zero) {
            root = tmax;
            return true;
        }
 
        if (pmin * pmax > zero)
            // It is not known whether the interval bounds a root.
            return false;
 
        if (tmin >= tmax)
            // Invalid ordering of interval endpoitns. 
            return false;
 
        for (uint32_t i = 1; i <= maxIterations; ++i) {
            root = 0.5 * (tmin + tmax);
 
            // This test is designed for 'float' or 'double' when tmin
            // and tmax are consecutive floating-point numbers.
            if (root == tmin || root == tmax)
                break;
 
            const double p = Evaluate(degree, c, root);
            const double product = p * pmin;
            if (product < zero) {
                tmax = root;
                pmax = p;
            }
            else if (product > zero) {
                tmin = root;
                pmin = p;
            }
            else
                break;
        }
 
        return true;
    }

References Evaluate().

Here is the call graph for this function:

Find() [2/2]

static int32_t Slic3r::Measure::RootsPolynomial::Find ( int32_t  degree, const double *  c, uint32_t  maxIterations, double *  roots  )

inlinestatic

    {
        if (degree >= 0 && c != nullptr) {
            const double zero = 0.0;
            while (degree >= 0 && c[degree] == zero) {
                --degree;
            }
 
            if (degree > 0) {
                // Compute the Cauchy bound.
                const double one = 1.0;
                const double invLeading = one / c[degree];
                double maxValue = zero;
                for (int32_t i = 0; i < degree; ++i) {
                    const double value = std::fabs(c[i] * invLeading);
                    if (value > maxValue)
                        maxValue = value;
                }
                const double bound = one + maxValue;
 
                return FindRecursive(degree, c, -bound, bound, maxIterations, roots);
            }
            else if (degree == 0)
                // The polynomial is a nonzero constant.
                return 0;
            else {
                // The polynomial is identically zero.
                roots[0] = zero;
                return 1;
            }
        }
        else
            // Invalid degree or c.
            return 0;
    }

References FindRecursive().

Referenced by FindRecursive(), and Slic3r::Measure::get_measurement().

Here is the call graph for this function:

Here is the caller graph for this function:

FindRecursive()

static int32_t Slic3r::Measure::RootsPolynomial::FindRecursive ( int32_t  degree, double const *  c, double  tmin, double  tmax, uint32_t  maxIterations, double *  roots  )

inlinestatic

    {
        // The base of the recursion.
        const double zero = 0.0;
        double root = zero;
        if (degree == 1) {
            int32_t numRoots;
            if (c[1] != zero) {
                root = -c[0] / c[1];
                numRoots = 1;
            }
            else if (c[0] == zero) {
                root = zero;
                numRoots = 1;
            }
            else
                numRoots = 0;
 
            if (numRoots > 0 && tmin <= root && root <= tmax) {
                roots[0] = root;
                return 1;
            }
            return 0;
        }
 
        // Find the roots of the derivative polynomial scaled by 1/degree.
        // The scaling avoids the factorial growth in the coefficients;
        // for example, without the scaling, the high-order term x^d
        // becomes (d!)*x through multiple differentiations.  With the
        // scaling we instead get x.  This leads to better numerical
        // behavior of the root finder.
        const int32_t derivDegree = degree - 1;
        std::vector<double> derivCoeff(static_cast<size_t>(derivDegree) + 1);
        std::vector<double> derivRoots(derivDegree);
        for (int32_t i = 0, ip1 = 1; i <= derivDegree; ++i, ++ip1) {
            derivCoeff[i] = c[ip1] * (double)(ip1) / (double)degree;
        }
        const int32_t numDerivRoots = FindRecursive(degree - 1, &derivCoeff[0], tmin, tmax, maxIterations, &derivRoots[0]);
 
        int32_t numRoots = 0;
        if (numDerivRoots > 0) {
            // Find root on [tmin,derivRoots[0]].
            if (Find(degree, c, tmin, derivRoots[0], maxIterations, root))
                roots[numRoots++] = root;
 
            // Find root on [derivRoots[i],derivRoots[i+1]].
            for (int32_t i = 0, ip1 = 1; i <= numDerivRoots - 2; ++i, ++ip1) {
                if (Find(degree, c, derivRoots[i], derivRoots[ip1], maxIterations, root))
                    roots[numRoots++] = root;
            }
 
            // Find root on [derivRoots[numDerivRoots-1],tmax].
            if (Find(degree, c, derivRoots[static_cast<size_t>(numDerivRoots) - 1], tmax, maxIterations, root))
                roots[numRoots++] = root;
        }
        else {
            // The polynomial is monotone on [tmin,tmax], so has at most one root.
            if (Find(degree, c, tmin, tmax, maxIterations, root))
                roots[numRoots++] = root;
        }
        return numRoots;
    }

References Find(), and FindRecursive().

Referenced by Find(), and FindRecursive().

Here is the call graph for this function:

Here is the caller graph for this function:

---

The documentation for this class was generated from the following file:

• src/libslic3r/MeasureUtils.hpp