SkScan_Hairline.cpp File Reference

#include "include/core/SkPaint.h"
#include "include/core/SkPath.h"
#include "include/core/SkPoint.h"
#include "include/core/SkRect.h"
#include "include/core/SkRegion.h"
#include "include/core/SkScalar.h"
#include "include/private/base/SkAssert.h"
#include "include/private/base/SkFixed.h"
#include "include/private/base/SkFloatingPoint.h"
#include "include/private/base/SkMath.h"
#include "include/private/base/SkSafe32.h"
#include "src/base/SkMathPriv.h"
#include "src/base/SkUtils.h"
#include "src/base/SkVx.h"
#include "src/core/SkBlitter.h"
#include "src/core/SkFDot6.h"
#include "src/core/SkGeometry.h"
#include "src/core/SkLineClipper.h"
#include "src/core/SkPathPriv.h"
#include "src/core/SkRasterClip.h"
#include "src/core/SkScan.h"
#include <algorithm>
#include <array>
#include <cstdint>
#include <cstring>

Go to the source code of this file.

Macros
#define	kMaxCubicSubdivideLevel   9
#define	kMaxQuadSubdivideLevel   5

Typedefs
using	float2 = skvx::float2
using	mask2 = skvx::Vec< 2, uint32_t >

Functions
static void	horiline (int x, int stopx, SkFixed fy, SkFixed dy, SkBlitter *blitter)
static void	vertline (int y, int stopy, SkFixed fx, SkFixed dx, SkBlitter *blitter)
static uint32_t	compute_int_quad_dist (const SkPoint pts[3])
static void	hair_quad (const SkPoint pts[3], const SkRegion *clip, SkBlitter *blitter, int level, SkScan::HairRgnProc lineproc)
static SkRect	compute_nocheck_quad_bounds (const SkPoint pts[3])
static bool	is_inverted (const SkRect &r)
static bool	geometric_overlap (const SkRect &a, const SkRect &b)
static bool	geometric_contains (const SkRect &outer, const SkRect &inner)
static void	hairquad (const SkPoint pts[3], const SkRegion *clip, const SkRect *insetClip, const SkRect *outsetClip, SkBlitter *blitter, int level, SkScan::HairRgnProc lineproc)
static SkScalar	max_component (const float2 &value)
static int	compute_cubic_segs (const SkPoint pts[4])
static bool	lt_90 (SkPoint p0, SkPoint pivot, SkPoint p2)
static bool	quick_cubic_niceness_check (const SkPoint pts[4])
static mask2	float2_is_finite (const float2 &x)
static void	hair_cubic (const SkPoint pts[4], const SkRegion *clip, SkBlitter *blitter, SkScan::HairRgnProc lineproc)
static SkRect	compute_nocheck_cubic_bounds (const SkPoint pts[4])
static void	haircubic (const SkPoint pts[4], const SkRegion *clip, const SkRect *insetClip, const SkRect *outsetClip, SkBlitter *blitter, int level, SkScan::HairRgnProc lineproc)
static int	compute_quad_level (const SkPoint pts[3])
template<SkPaint::Cap capStyle>
void	extend_pts (SkPath::Verb prevVerb, SkPath::Verb nextVerb, SkPoint *pts, int ptCount)
template<SkPaint::Cap capStyle>
void	hair_path (const SkPath &path, const SkRasterClip &rclip, SkBlitter *blitter, SkScan::HairRgnProc lineproc)

Macro Definition Documentation

kMaxCubicSubdivideLevel

#define kMaxCubicSubdivideLevel   9

Definition at line 230 of file SkScan_Hairline.cpp.

kMaxQuadSubdivideLevel

#define kMaxQuadSubdivideLevel   5

Definition at line 231 of file SkScan_Hairline.cpp.

Typedef Documentation

float2

using float2 = skvx::float2

Definition at line 233 of file SkScan_Hairline.cpp.

mask2

using mask2 = skvx::Vec<2, uint32_t>

Definition at line 371 of file SkScan_Hairline.cpp.

Function Documentation

compute_cubic_segs()

static int compute_cubic_segs ( const SkPoint  pts[4] )

inlinestatic

Definition at line 335 of file SkScan_Hairline.cpp.

                                                           {
    float2 p0 = from_point(pts[0]);
    float2 p1 = from_point(pts[1]);
    float2 p2 = from_point(pts[2]);
    float2 p3 = from_point(pts[3]);
 
    const float2 oneThird(1.0f / 3.0f);
    const float2 twoThird(2.0f / 3.0f);
 
    float2 p13 = oneThird * p3 + twoThird * p0;
    float2 p23 = oneThird * p0 + twoThird * p3;
 
    SkScalar diff = max_component(max(abs(p1 - p13), abs(p2 - p23)));
    SkScalar tol = SK_Scalar1 / 8;
 
    for (int i = 0; i < kMaxCubicSubdivideLevel; ++i) {
        if (diff < tol) {
            return 1 << i;
        }
        tol *= 4;
    }
    return 1 << kMaxCubicSubdivideLevel;
}

compute_int_quad_dist()

static uint32_t compute_int_quad_dist ( const SkPoint  pts[3] )

static

Definition at line 235 of file SkScan_Hairline.cpp.

                                                            {
    // compute the vector between the control point ([1]) and the middle of the
    // line connecting the start and end ([0] and [2])
    SkScalar dx = SkScalarHalf(pts[0].fX + pts[2].fX) - pts[1].fX;
    SkScalar dy = SkScalarHalf(pts[0].fY + pts[2].fY) - pts[1].fY;
    // we want everyone to be positive
    dx = SkScalarAbs(dx);
    dy = SkScalarAbs(dy);
    // convert to whole pixel values (use ceiling to be conservative).
    // assign to unsigned so we can safely add 1/2 of the smaller and still fit in
    // uint32_t, since SkScalarCeilToInt() returns 31 bits at most.
    uint32_t idx = SkScalarCeilToInt(dx);
    uint32_t idy = SkScalarCeilToInt(dy);
    // use the cheap approx for distance
    if (idx > idy) {
        return idx + (idy >> 1);
    } else {
        return idy + (idx >> 1);
    }
}

compute_nocheck_cubic_bounds()

static SkRect compute_nocheck_cubic_bounds ( const SkPoint  pts[4] )

static

Definition at line 414 of file SkScan_Hairline.cpp.

                                                                 {
    SkASSERT(SkIsFinite(&pts[0].fX, 8));
 
    float2 min = float2::Load(pts);
    float2 max = min;
    for (int i = 1; i < 4; ++i) {
        float2 pair = float2::Load(pts+i);
        min = skvx::min(min, pair);
        max = skvx::max(max, pair);
    }
    return { min[0], min[1], max[0], max[1] };
}

compute_nocheck_quad_bounds()

static SkRect compute_nocheck_quad_bounds ( const SkPoint  pts[3] )

static

Definition at line 281 of file SkScan_Hairline.cpp.

                                                                {
    SkASSERT(SkIsFinite(&pts[0].fX, 6));
 
    float2 min = float2::Load(pts);
    float2 max = min;
    for (int i = 1; i < 3; ++i) {
        float2 pair = float2::Load(pts+i);
        min = skvx::min(min, pair);
        max = skvx::max(max, pair);
    }
    return { min[0], min[1], max[0], max[1] };
}

compute_quad_level()

static int compute_quad_level ( const SkPoint  pts[3] )

static

Definition at line 452 of file SkScan_Hairline.cpp.

                                                    {
    uint32_t d = compute_int_quad_dist(pts);
    /*  quadratics approach the line connecting their start and end points
     4x closer with each subdivision, so we compute the number of
     subdivisions to be the minimum need to get that distance to be less
     than a pixel.
     */
    int level = (33 - SkCLZ(d)) >> 1;
    // safety check on level (from the previous version)
    if (level > kMaxQuadSubdivideLevel) {
        level = kMaxQuadSubdivideLevel;
    }
    return level;
}

extend_pts()

template<SkPaint::Cap capStyle>

void extend_pts	(	SkPath::Verb	prevVerb,
		SkPath::Verb	nextVerb,
		SkPoint *	pts,
		int	ptCount
	)

Definition at line 472 of file SkScan_Hairline.cpp.

                                                                                     {
    SkASSERT(SkPaint::kSquare_Cap == capStyle || SkPaint::kRound_Cap == capStyle);
    // The area of a circle is PI*R*R. For a unit circle, R=1/2, and the cap covers half of that.
    const SkScalar capOutset = SkPaint::kSquare_Cap == capStyle ? 0.5f : SK_ScalarPI / 8;
    if (SkPath::kMove_Verb == prevVerb) {
        SkPoint* first = pts;
        SkPoint* ctrl = first;
        int controls = ptCount - 1;
        SkVector tangent;
        do {
            tangent = *first - *++ctrl;
        } while (tangent.isZero() && --controls > 0);
        if (tangent.isZero()) {
            tangent.set(1, 0);
            controls = ptCount - 1;  // If all points are equal, move all but one
        } else {
            tangent.normalize();
        }
        do {    // If the end point and control points are equal, loop to move them in tandem.
            first->fX += tangent.fX * capOutset;
            first->fY += tangent.fY * capOutset;
            ++first;
        } while (++controls < ptCount);
    }
    if (SkPath::kMove_Verb == nextVerb || SkPath::kDone_Verb == nextVerb
            || SkPath::kClose_Verb == nextVerb) {
        SkPoint* last = &pts[ptCount - 1];
        SkPoint* ctrl = last;
        int controls = ptCount - 1;
        SkVector tangent;
        do {
            tangent = *last - *--ctrl;
        } while (tangent.isZero() && --controls > 0);
        if (tangent.isZero()) {
            tangent.set(-1, 0);
            controls = ptCount - 1;
        } else {
            tangent.normalize();
        }
        do {
            last->fX += tangent.fX * capOutset;
            last->fY += tangent.fY * capOutset;
            --last;
        } while (++controls < ptCount);
    }
}

float2_is_finite()

static mask2 float2_is_finite ( const float2 &  x )

inlinestatic

Definition at line 373 of file SkScan_Hairline.cpp.

                                                      {
    const mask2 exp_mask = mask2(0xFF << 23);
    return (sk_bit_cast<mask2>(x) & exp_mask) != exp_mask;
}

geometric_contains()

static bool geometric_contains ( const SkRect &  outer, const SkRect &  inner  )

static

Definition at line 308 of file SkScan_Hairline.cpp.

                                                                         {
    SkASSERT(!is_inverted(outer) && !is_inverted(inner));
    return inner.fRight <= outer.fRight && inner.fLeft >= outer.fLeft &&
            inner.fBottom <= outer.fBottom && inner.fTop >= outer.fTop;
}

geometric_overlap()

static bool geometric_overlap ( const SkRect &  a, const SkRect &  b  )

static

Definition at line 300 of file SkScan_Hairline.cpp.

                                                                {
    SkASSERT(!is_inverted(a) && !is_inverted(b));
    return a.fLeft < b.fRight && b.fLeft < a.fRight &&
            a.fTop < b.fBottom && b.fTop < a.fBottom;
}

hair_cubic()

static void hair_cubic ( const SkPoint  pts[4], const SkRegion *  clip, SkBlitter *  blitter, SkScan::HairRgnProc  lineproc  )

static

Definition at line 378 of file SkScan_Hairline.cpp.

                                                   {
    const int lines = compute_cubic_segs(pts);
    SkASSERT(lines > 0);
    if (1 == lines) {
        SkPoint tmp[2] = { pts[0], pts[3] };
        lineproc(tmp, 2, clip, blitter);
        return;
    }
 
    SkCubicCoeff coeff(pts);
 
    const float2 dt(SK_Scalar1 / lines);
    float2 t(0);
 
    SkPoint tmp[(1 << kMaxCubicSubdivideLevel) + 1];
    SkASSERT((unsigned)lines < std::size(tmp));
 
    tmp[0] = pts[0];
    float2 A = coeff.fA;
    float2 B = coeff.fB;
    float2 C = coeff.fC;
    float2 D = coeff.fD;
    mask2 is_finite(~0);   // start out as true
    for (int i = 1; i < lines; ++i) {
        t = t + dt;
        float2 p = ((A * t + B) * t + C) * t + D;
        is_finite &= float2_is_finite(p);
        p.store(&tmp[i]);
    }
    if (all(is_finite)) {
        tmp[lines] = pts[3];
        lineproc(tmp, lines + 1, clip, blitter);
    } // else some point(s) are non-finite, so don't draw
}

hair_path()

template<SkPaint::Cap capStyle>

void hair_path	(	const SkPath &	path,
		const SkRasterClip &	rclip,
		SkBlitter *	blitter,
		SkScan::HairRgnProc	lineproc
	)

Definition at line 520 of file SkScan_Hairline.cpp.

                                                  {
    if (path.isEmpty()) {
        return;
    }
 
    SkAAClipBlitterWrapper wrap;
    const SkRegion* clip = nullptr;
    SkRect insetStorage, outsetStorage;
    const SkRect* insetClip = nullptr;
    const SkRect* outsetClip = nullptr;
 
    {
        const int capOut = SkPaint::kButt_Cap == capStyle ? 1 : 2;
        const SkIRect ibounds = path.getBounds().roundOut().makeOutset(capOut, capOut);
        if (rclip.quickReject(ibounds)) {
            return;
        }
        if (!rclip.quickContains(ibounds)) {
            if (rclip.isBW()) {
                clip = &rclip.bwRgn();
            } else {
                wrap.init(rclip, blitter);
                blitter = wrap.getBlitter();
                clip = &wrap.getRgn();
            }
 
            /*
             *  We now cache two scalar rects, to use for culling per-segment (e.g. cubic).
             *  Since we're hairlining, the "bounds" of the control points isn't necessairly the
             *  limit of where a segment can draw (it might draw up to 1 pixel beyond in aa-hairs).
             *
             *  Compute the pt-bounds per segment is easy, so we do that, and then inversely adjust
             *  the culling bounds so we can just do a straight compare per segment.
             *
             *  insetClip is use for quick-accept (i.e. the segment is not clipped), so we inset
             *  it from the clip-bounds (since segment bounds can be off by 1).
             *
             *  outsetClip is used for quick-reject (i.e. the segment is entirely outside), so we
             *  outset it from the clip-bounds.
             */
            insetStorage.set(clip->getBounds());
            outsetStorage = insetStorage.makeOutset(1, 1);
            insetStorage.inset(1, 1);
            if (is_inverted(insetStorage)) {
                /*
                 *  our bounds checks assume the rects are never inverted. If insetting has
                 *  created that, we assume that the area is too small to safely perform a
                 *  quick-accept, so we just mark the rect as empty (so the quick-accept check
                 *  will always fail.
                 */
                insetStorage.setEmpty();    // just so we don't pass an inverted rect
            }
            if (rclip.isRect()) {
                insetClip = &insetStorage;
            }
            outsetClip = &outsetStorage;
        }
    }
 
    SkPathPriv::RangeIter iter = SkPathPriv::Iterate(path).begin();
    SkPathPriv::RangeIter end = SkPathPriv::Iterate(path).end();
    SkPoint               pts[4], firstPt, lastPt;
    SkPath::Verb          prevVerb;
    SkAutoConicToQuads    converter;
 
    if (SkPaint::kButt_Cap != capStyle) {
        prevVerb = SkPath::kDone_Verb;
    }
    while (iter != end) {
        auto [pathVerb, pathPts, w] = *iter++;
        SkPath::Verb verb = (SkPath::Verb)pathVerb;
        SkPath::Verb nextVerb = (iter != end) ? (SkPath::Verb)iter.peekVerb() : SkPath::kDone_Verb;
        memcpy(pts, pathPts, SkPathPriv::PtsInIter(verb) * sizeof(SkPoint));
        switch (verb) {
            case SkPath::kMove_Verb:
                firstPt = lastPt = pts[0];
                break;
            case SkPath::kLine_Verb:
                if (SkPaint::kButt_Cap != capStyle) {
                    extend_pts<capStyle>(prevVerb, nextVerb, pts, 2);
                }
                lineproc(pts, 2, clip, blitter);
                lastPt = pts[1];
                break;
            case SkPath::kQuad_Verb:
                if (SkPaint::kButt_Cap != capStyle) {
                    extend_pts<capStyle>(prevVerb, nextVerb, pts, 3);
                }
                hairquad(pts, clip, insetClip, outsetClip, blitter, compute_quad_level(pts), lineproc);
                lastPt = pts[2];
                break;
            case SkPath::kConic_Verb: {
                if (SkPaint::kButt_Cap != capStyle) {
                    extend_pts<capStyle>(prevVerb, nextVerb, pts, 3);
                }
                // how close should the quads be to the original conic?
                const SkScalar tol = SK_Scalar1 / 4;
                const SkPoint* quadPts = converter.computeQuads(pts, *w, tol);
                for (int i = 0; i < converter.countQuads(); ++i) {
                    int level = compute_quad_level(quadPts);
                    hairquad(quadPts, clip, insetClip, outsetClip, blitter, level, lineproc);
                    quadPts += 2;
                }
                lastPt = pts[2];
                break;
            }
            case SkPath::kCubic_Verb: {
                if (SkPaint::kButt_Cap != capStyle) {
                    extend_pts<capStyle>(prevVerb, nextVerb, pts, 4);
                }
                haircubic(pts, clip, insetClip, outsetClip, blitter, kMaxCubicSubdivideLevel, lineproc);
                lastPt = pts[3];
            } break;
            case SkPath::kClose_Verb:
                pts[0] = lastPt;
                pts[1] = firstPt;
                if (SkPaint::kButt_Cap != capStyle && prevVerb == SkPath::kMove_Verb) {
                    // cap moveTo/close to match svg expectations for degenerate segments
                    extend_pts<capStyle>(prevVerb, nextVerb, pts, 2);
                }
                lineproc(pts, 2, clip, blitter);
                break;
            case SkPath::kDone_Verb:
                break;
        }
        if (SkPaint::kButt_Cap != capStyle) {
            if (prevVerb == SkPath::kMove_Verb &&
                    verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) {
                firstPt = pts[0];  // the curve moved the initial point, so close to it instead
            }
            prevVerb = verb;
        }
    }
}

hair_quad()

static void hair_quad ( const SkPoint  pts[3], const SkRegion *  clip, SkBlitter *  blitter, int  level, SkScan::HairRgnProc  lineproc  )

static

Definition at line 256 of file SkScan_Hairline.cpp.

                                                                                {
    SkASSERT(level <= kMaxQuadSubdivideLevel);
 
    SkQuadCoeff coeff(pts);
 
    const int lines = 1 << level;
    float2 t(0);
    float2 dt(SK_Scalar1 / lines);
 
    SkPoint tmp[(1 << kMaxQuadSubdivideLevel) + 1];
    SkASSERT((unsigned)lines < std::size(tmp));
 
    tmp[0] = pts[0];
    float2 A = coeff.fA;
    float2 B = coeff.fB;
    float2 C = coeff.fC;
    for (int i = 1; i < lines; ++i) {
        t = t + dt;
        ((A * t + B) * t + C).store(&tmp[i]);
    }
    tmp[lines] = pts[2];
    lineproc(tmp, lines + 1, clip, blitter);
}

haircubic()

static void haircubic ( const SkPoint  pts[4], const SkRegion *  clip, const SkRect *  insetClip, const SkRect *  outsetClip, SkBlitter *  blitter, int  level, SkScan::HairRgnProc  lineproc  )

inlinestatic

Definition at line 427 of file SkScan_Hairline.cpp.

                                                                                 {
    if (insetClip) {
        SkASSERT(outsetClip);
        SkRect bounds = compute_nocheck_cubic_bounds(pts);
        if (!geometric_overlap(*outsetClip, bounds)) {
            return;
        } else if (geometric_contains(*insetClip, bounds)) {
            clip = nullptr;
        }
    }
 
    if (quick_cubic_niceness_check(pts)) {
        hair_cubic(pts, clip, blitter, lineproc);
    } else {
        SkPoint  tmp[13];
        SkScalar tValues[3];
 
        int count = SkChopCubicAtMaxCurvature(pts, tmp, tValues);
        for (int i = 0; i < count; i++) {
            hair_cubic(&tmp[i * 3], clip, blitter, lineproc);
        }
    }
}

hairquad()

static void hairquad ( const SkPoint  pts[3], const SkRegion *  clip, const SkRect *  insetClip, const SkRect *  outsetClip, SkBlitter *  blitter, int  level, SkScan::HairRgnProc  lineproc  )

inlinestatic

Definition at line 314 of file SkScan_Hairline.cpp.

                                                               {
    if (insetClip) {
        SkASSERT(outsetClip);
        SkRect bounds = compute_nocheck_quad_bounds(pts);
        if (!geometric_overlap(*outsetClip, bounds)) {
            return;
        } else if (geometric_contains(*insetClip, bounds)) {
            clip = nullptr;
        }
    }
 
    hair_quad(pts, clip, blitter, level, lineproc);
}

horiline()

static void horiline ( int  x, int  stopx, SkFixed  fy, SkFixed  dy, SkBlitter *  blitter  )

static

Definition at line 35 of file SkScan_Hairline.cpp.

                                         {
    SkASSERT(x < stopx);
 
    do {
        blitter->blitH(x, fy >> 16, 1);
        fy += dy;
    } while (++x < stopx);
}

is_inverted()

static bool is_inverted ( const SkRect &  r )

static

Definition at line 294 of file SkScan_Hairline.cpp.

                                         {
    return r.fLeft > r.fRight || r.fTop > r.fBottom;
}

lt_90()

static bool lt_90 ( SkPoint  p0, SkPoint  pivot, SkPoint  p2  )

static

Definition at line 359 of file SkScan_Hairline.cpp.

                                                         {
    return SkVector::DotProduct(p0 - pivot, p2 - pivot) >= 0;
}

max_component()

static SkScalar max_component ( const float2 &  value )

inlinestatic

Definition at line 329 of file SkScan_Hairline.cpp.

                                                          {
    SkScalar components[2];
    value.store(components);
    return std::max(components[0], components[1]);
}

quick_cubic_niceness_check()

static bool quick_cubic_niceness_check ( const SkPoint  pts[4] )

static

Definition at line 364 of file SkScan_Hairline.cpp.

                                                             {
    return lt_90(pts[1], pts[0], pts[3]) &&
           lt_90(pts[2], pts[0], pts[3]) &&
           lt_90(pts[1], pts[3], pts[0]) &&
           lt_90(pts[2], pts[3], pts[0]);
}

vertline()

static void vertline ( int  y, int  stopy, SkFixed  fx, SkFixed  dx, SkBlitter *  blitter  )

static

Definition at line 45 of file SkScan_Hairline.cpp.

                                         {
    SkASSERT(y < stopy);
 
    do {
        blitter->blitH(fx >> 16, y, 1);
        fx += dx;
    } while (++y < stopy);
}