SkEdgeClipper.cpp File Reference

#include "src/core/SkEdgeClipper.h"
#include "include/core/SkRect.h"
#include "include/core/SkTypes.h"
#include "include/private/base/SkMacros.h"
#include "src/core/SkGeometry.h"
#include "src/core/SkLineClipper.h"
#include "src/core/SkPathPriv.h"
#include <algorithm>
#include <cstring>

Go to the source code of this file.

Functions
static bool	quick_reject (const SkRect &bounds, const SkRect &clip)
static void	clamp_le (SkScalar &value, SkScalar max)
static void	clamp_ge (SkScalar &value, SkScalar min)
static bool	sort_increasing_Y (SkPoint dst[], const SkPoint src[], int count)
static bool	chopMonoQuadAt (SkScalar c0, SkScalar c1, SkScalar c2, SkScalar target, SkScalar *t)
static bool	chopMonoQuadAtY (SkPoint pts[3], SkScalar y, SkScalar *t)
static bool	chopMonoQuadAtX (SkPoint pts[3], SkScalar x, SkScalar *t)
static void	chop_quad_in_Y (SkPoint pts[3], const SkRect &clip)
static SkScalar	mono_cubic_closestT (const SkScalar src[], SkScalar x)
static void	chop_mono_cubic_at_y (SkPoint src[4], SkScalar y, SkPoint dst[7])
static void	chop_cubic_in_Y (SkPoint pts[4], const SkRect &clip)
static void	chop_mono_cubic_at_x (SkPoint src[4], SkScalar x, SkPoint dst[7])
static SkRect	compute_cubic_bounds (const SkPoint pts[4])
static bool	too_big_for_reliable_float_math (const SkRect &r)

Function Documentation

chop_cubic_in_Y()

static void chop_cubic_in_Y ( SkPoint  pts[4], const SkRect &  clip  )

static

Definition at line 288 of file SkEdgeClipper.cpp.

                                                                {
 
    // are we partially above
    if (pts[0].fY < clip.fTop) {
        SkPoint tmp[7];
        chop_mono_cubic_at_y(pts, clip.fTop, tmp);
 
        /*
         *  For a large range in the points, we can do a poor job of chopping, such that the t
         *  we computed resulted in the lower cubic still being partly above the clip.
         *
         *  If just the first or first 2 Y values are above the fTop, we can just smash them
         *  down. If the first 3 Ys are above fTop, we can't smash all 3, as that can really
         *  distort the cubic. In this case, we take the first output (tmp[3..6] and treat it as
         *  a guess, and re-chop against fTop. Then we fall through to checking if we need to
         *  smash the first 1 or 2 Y values.
         */
        if (tmp[3].fY < clip.fTop && tmp[4].fY < clip.fTop && tmp[5].fY < clip.fTop) {
            SkPoint tmp2[4];
            memcpy(tmp2, &tmp[3].fX, 4 * sizeof(SkPoint));
            chop_mono_cubic_at_y(tmp2, clip.fTop, tmp);
        }
 
        // tmp[3, 4].fY should all be to the below clip.fTop.
        // Since we can't trust the numerics of the chopper, we force those conditions now
        tmp[3].fY = clip.fTop;
        clamp_ge(tmp[4].fY, clip.fTop);
 
        pts[0] = tmp[3];
        pts[1] = tmp[4];
        pts[2] = tmp[5];
    }
 
    // are we partially below
    if (pts[3].fY > clip.fBottom) {
        SkPoint tmp[7];
        chop_mono_cubic_at_y(pts, clip.fBottom, tmp);
        tmp[3].fY = clip.fBottom;
        clamp_le(tmp[2].fY, clip.fBottom);
 
        pts[1] = tmp[1];
        pts[2] = tmp[2];
        pts[3] = tmp[3];
    }
}

chop_mono_cubic_at_x()

static void chop_mono_cubic_at_x ( SkPoint  src[4], SkScalar  x, SkPoint  dst[7]  )

static

Definition at line 334 of file SkEdgeClipper.cpp.

                                                                             {
    if (SkChopMonoCubicAtX(src, x, dst)) {
        return;
    }
    SkChopCubicAt(src, dst, mono_cubic_closestT(&src->fX, x));
}

chop_mono_cubic_at_y()

static void chop_mono_cubic_at_y ( SkPoint  src[4], SkScalar  y, SkPoint  dst[7]  )

static

Definition at line 280 of file SkEdgeClipper.cpp.

                                                                             {
    if (SkChopMonoCubicAtY(src, y, dst)) {
        return;
    }
    SkChopCubicAt(src, dst, mono_cubic_closestT(&src->fY, y));
}

chop_quad_in_Y()

static void chop_quad_in_Y ( SkPoint  pts[3], const SkRect &  clip  )

static

Definition at line 100 of file SkEdgeClipper.cpp.

                                                               {
    SkScalar t;
    SkPoint tmp[5]; // for SkChopQuadAt
 
    // are we partially above
    if (pts[0].fY < clip.fTop) {
        if (chopMonoQuadAtY(pts, clip.fTop, &t)) {
            // take the 2nd chopped quad
            SkChopQuadAt(pts, tmp, t);
            // clamp to clean up imprecise numerics in the chop
            tmp[2].fY = clip.fTop;
            clamp_ge(tmp[3].fY, clip.fTop);
 
            pts[0] = tmp[2];
            pts[1] = tmp[3];
        } else {
            // if chopMonoQuadAtY failed, then we may have hit inexact numerics
            // so we just clamp against the top
            for (int i = 0; i < 3; i++) {
                if (pts[i].fY < clip.fTop) {
                    pts[i].fY = clip.fTop;
                }
            }
        }
    }
 
    // are we partially below
    if (pts[2].fY > clip.fBottom) {
        if (chopMonoQuadAtY(pts, clip.fBottom, &t)) {
            SkChopQuadAt(pts, tmp, t);
            // clamp to clean up imprecise numerics in the chop
            clamp_le(tmp[1].fY, clip.fBottom);
            tmp[2].fY = clip.fBottom;
 
            pts[1] = tmp[1];
            pts[2] = tmp[2];
        } else {
            // if chopMonoQuadAtY failed, then we may have hit inexact numerics
            // so we just clamp against the bottom
            for (int i = 0; i < 3; i++) {
                if (pts[i].fY > clip.fBottom) {
                    pts[i].fY = clip.fBottom;
                }
            }
        }
    }
}

chopMonoQuadAt()

static bool chopMonoQuadAt ( SkScalar  c0, SkScalar  c1, SkScalar  c2, SkScalar  target, SkScalar *  t  )

static

Definition at line 72 of file SkEdgeClipper.cpp.

                                                         {
    /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2
     *  We solve for t, using quadratic equation, hence we have to rearrange
     * our cooefficents to look like At^2 + Bt + C
     */
    SkScalar A = c0 - c1 - c1 + c2;
    SkScalar B = 2*(c1 - c0);
    SkScalar C = c0 - target;
 
    SkScalar roots[2];  // we only expect one, but make room for 2 for safety
    int count = SkFindUnitQuadRoots(A, B, C, roots);
    if (count) {
        *t = roots[0];
        return true;
    }
    return false;
}

chopMonoQuadAtX()

static bool chopMonoQuadAtX ( SkPoint  pts[3], SkScalar  x, SkScalar *  t  )

static

Definition at line 95 of file SkEdgeClipper.cpp.

                                                                     {
    return chopMonoQuadAt(pts[0].fX, pts[1].fX, pts[2].fX, x, t);
}

chopMonoQuadAtY()

static bool chopMonoQuadAtY ( SkPoint  pts[3], SkScalar  y, SkScalar *  t  )

static

Definition at line 91 of file SkEdgeClipper.cpp.

                                                                     {
    return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t);
}

clamp_ge()

static void clamp_ge ( SkScalar &  value, SkScalar  min  )

inlinestatic

Definition at line 30 of file SkEdgeClipper.cpp.

                                                           {
    if (value < min) {
        value = min;
    }
}

clamp_le()

static void clamp_le ( SkScalar &  value, SkScalar  max  )

inlinestatic

Definition at line 24 of file SkEdgeClipper.cpp.

                                                           {
    if (value > max) {
        value = max;
    }
}

compute_cubic_bounds()

static SkRect compute_cubic_bounds ( const SkPoint  pts[4] )

static

Definition at line 405 of file SkEdgeClipper.cpp.

                                                         {
    SkRect r;
    r.setBounds(pts, 4);
    return r;
}

mono_cubic_closestT()

static SkScalar mono_cubic_closestT ( const SkScalar  src[], SkScalar  x  )

static

Definition at line 255 of file SkEdgeClipper.cpp.

                                                                      {
    SkScalar t = 0.5f;
    SkScalar lastT;
    SkScalar bestT  SK_INIT_TO_AVOID_WARNING;
    SkScalar step = 0.25f;
    SkScalar D = src[0];
    SkScalar A = src[6] + 3*(src[2] - src[4]) - D;
    SkScalar B = 3*(src[4] - src[2] - src[2] + D);
    SkScalar C = 3*(src[2] - D);
    x -= D;
    SkScalar closest = SK_ScalarMax;
    do {
        SkScalar loc = ((A * t + B) * t + C) * t;
        SkScalar dist = SkScalarAbs(loc - x);
        if (closest > dist) {
            closest = dist;
            bestT = t;
        }
        lastT = t;
        t += loc < x ? step : -step;
        step *= 0.5f;
    } while (closest > 0.25f && lastT != t);
    return bestT;
}

quick_reject()

static bool quick_reject ( const SkRect &  bounds, const SkRect &  clip  )

static

Definition at line 20 of file SkEdgeClipper.cpp.

                                                                   {
    return bounds.fTop >= clip.fBottom || bounds.fBottom <= clip.fTop;
}

sort_increasing_Y()

static bool sort_increasing_Y ( SkPoint  dst[], const SkPoint  src[], int  count  )

static

Definition at line 40 of file SkEdgeClipper.cpp.

                                                                             {
    // we need the data to be monotonically increasing in Y
    if (src[0].fY > src[count - 1].fY) {
        for (int i = 0; i < count; i++) {
            dst[i] = src[count - i - 1];
        }
        return true;
    } else {
        memcpy(dst, src, count * sizeof(SkPoint));
        return false;
    }
}

too_big_for_reliable_float_math()

static bool too_big_for_reliable_float_math ( const SkRect &  r )

static

Definition at line 411 of file SkEdgeClipper.cpp.

                                                             {
    // limit set as the largest float value for which we can still reliably compute things like
    // - chopping at XY extrema
    // - chopping at Y or X values for clipping
    //
    // Current value chosen just by experiment. Larger (and still succeeds) is always better.
    //
    const SkScalar limit = 1 << 22;
    return r.fLeft < -limit || r.fTop < -limit || r.fRight > limit || r.fBottom > limit;
}