SkScan_Path.cpp File Reference

#include "include/core/SkColor.h"
#include "include/core/SkPath.h"
#include "include/core/SkPathTypes.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/SkDebug.h"
#include "include/private/base/SkFixed.h"
#include "include/private/base/SkFloatingPoint.h"
#include "include/private/base/SkMacros.h"
#include "include/private/base/SkMath.h"
#include "include/private/base/SkPoint_impl.h"
#include "include/private/base/SkSafe32.h"
#include "src/base/SkTSort.h"
#include "src/core/SkBlitter.h"
#include "src/core/SkEdge.h"
#include "src/core/SkEdgeBuilder.h"
#include "src/core/SkFDot6.h"
#include "src/core/SkRasterClip.h"
#include "src/core/SkRectPriv.h"
#include "src/core/SkScan.h"
#include "src/core/SkScanPriv.h"
#include <algorithm>
#include <cmath>
#include <cstdint>

Go to the source code of this file.

Classes
class	InverseBlitter

Macros
#define	kEDGE_HEAD_Y   SK_MinS32
#define	kEDGE_TAIL_Y   SK_MaxS32
#define	validate_sort(edge)
#define	validate_edges_for_y(edge, curr_y)
#define	PREPOST_START   true
#define	PREPOST_END   false
#define	ASSERT_RETURN(cond)

Typedefs
typedef void(*	PrePostProc) (SkBlitter *blitter, int y, bool isStartOfScanline)

Functions
static void	insert_new_edges (SkEdge *newEdge, int curr_y)
static void	walk_edges (SkEdge *prevHead, SkPathFillType fillType, SkBlitter *blitter, int start_y, int stop_y, PrePostProc proc, int rightClip)
static bool	update_edge (SkEdge *edge, int last_y)
static void	walk_simple_edges (SkEdge *prevHead, SkBlitter *blitter, int start_y, int stop_y)
static void	PrePostInverseBlitterProc (SkBlitter *blitter, int y, bool isStart)
static bool	operator< (const SkEdge &a, const SkEdge &b)
static SkEdge *	sort_edges (SkEdge *list[], int count, SkEdge **last)
void	sk_fill_path (const SkPath &path, const SkIRect &clipRect, SkBlitter *blitter, int start_y, int stop_y, int shiftEdgesUp, bool pathContainedInClip)
void	sk_blit_above (SkBlitter *blitter, const SkIRect &ir, const SkRegion &clip)
void	sk_blit_below (SkBlitter *blitter, const SkIRect &ir, const SkRegion &clip)
static bool	clip_to_limit (const SkRegion &orig, SkRegion *reduced)
static int	round_down_to_int (SkScalar x)
static int	round_up_to_int (SkScalar x)
static SkIRect	conservative_round_to_int (const SkRect &src)
static int	build_tri_edges (SkEdge edge[], const SkPoint pts[], const SkIRect *clipRect, SkEdge *list[])
static void	sk_fill_triangle (const SkPoint pts[], const SkIRect *clipRect, SkBlitter *blitter, const SkIRect &ir)

Variables
static const double	kConservativeRoundBias = 0.5 + 1.5 / SK_FDot6One

Macro Definition Documentation

ASSERT_RETURN

#define ASSERT_RETURN

(

cond

)

Value:

    do {                                       \
        if (!(cond)) {                         \
            SkDEBUGFAILF("assert(%s)", #cond); \
            return;                            \
        }                                      \
    } while (0)

Definition at line 226 of file SkScan_Path.cpp.

kEDGE_HEAD_Y

#define kEDGE_HEAD_Y   SK_MinS32

Definition at line 38 of file SkScan_Path.cpp.

kEDGE_TAIL_Y

#define kEDGE_TAIL_Y   SK_MaxS32

Definition at line 39 of file SkScan_Path.cpp.

PREPOST_END

#define PREPOST_END   false

Definition at line 111 of file SkScan_Path.cpp.

PREPOST_START

#define PREPOST_START   true

Definition at line 110 of file SkScan_Path.cpp.

validate_edges_for_y

#define validate_edges_for_y	(		edge,
			curr_y
	)

Definition at line 101 of file SkScan_Path.cpp.

validate_sort

#define validate_sort

(

edge

)

Definition at line 54 of file SkScan_Path.cpp.

Typedef Documentation

PrePostProc

typedef void(* PrePostProc) (SkBlitter *blitter, int y, bool isStartOfScanline)

Definition at line 109 of file SkScan_Path.cpp.

Function Documentation

build_tri_edges()

static int build_tri_edges ( SkEdge  edge[], const SkPoint  pts[], const SkIRect *  clipRect, SkEdge *  list[]  )

static

Definition at line 695 of file SkScan_Path.cpp.

                                                                    {
    SkEdge** start = list;
 
    if (edge->setLine(pts[0], pts[1], clipRect, 0)) {
        *list++ = edge;
        edge = (SkEdge*)((char*)edge + sizeof(SkEdge));
    }
    if (edge->setLine(pts[1], pts[2], clipRect, 0)) {
        *list++ = edge;
        edge = (SkEdge*)((char*)edge + sizeof(SkEdge));
    }
    if (edge->setLine(pts[2], pts[0], clipRect, 0)) {
        *list++ = edge;
    }
    return (int)(list - start);
}

clip_to_limit()

static bool clip_to_limit ( const SkRegion &  orig, SkRegion *  reduced  )

static

Definition at line 561 of file SkScan_Path.cpp.

                                                                   {
    // need to limit coordinates such that the width/height of our rect can be represented
    // in SkFixed (16.16). See skbug.com/7998
    const int32_t limit = 32767 >> 1;
 
    SkIRect limitR;
    limitR.setLTRB(-limit, -limit, limit, limit);
    if (limitR.contains(orig.getBounds())) {
        return false;
    }
    reduced->op(orig, limitR, SkRegion::kIntersect_Op);
    return true;
}

conservative_round_to_int()

static SkIRect conservative_round_to_int ( const SkRect &  src )

static

Definition at line 616 of file SkScan_Path.cpp.

                                                            {
    return {
        round_down_to_int(src.fLeft),
        round_down_to_int(src.fTop),
        round_up_to_int(src.fRight),
        round_up_to_int(src.fBottom),
    };
}

insert_new_edges()

static void insert_new_edges ( SkEdge *  newEdge, int  curr_y  )

static

Definition at line 57 of file SkScan_Path.cpp.

                                                          {
    if (newEdge->fFirstY != curr_y) {
        return;
    }
    SkEdge* prev = newEdge->fPrev;
    if (prev->fX <= newEdge->fX) {
        return;
    }
    // find first x pos to insert
    SkEdge* start = backward_insert_start(prev, newEdge->fX);
    // insert the lot, fixing up the links as we go
    do {
        SkEdge* next = newEdge->fNext;
        do {
            if (start->fNext == newEdge) {
                goto nextEdge;
            }
            SkEdge* after = start->fNext;
            if (after->fX >= newEdge->fX) {
                break;
            }
            start = after;
        } while (true);
        remove_edge(newEdge);
        insert_edge_after(newEdge, start);
nextEdge:
        start = newEdge;
        newEdge = next;
    } while (newEdge->fFirstY == curr_y);
}

operator<()

static bool operator< ( const SkEdge &  a, const SkEdge &  b  )

static

Definition at line 378 of file SkScan_Path.cpp.

                                                        {
    int valuea = a.fFirstY;
    int valueb = b.fFirstY;
 
    if (valuea == valueb) {
        valuea = a.fX;
        valueb = b.fX;
    }
 
    return valuea < valueb;
}

PrePostInverseBlitterProc()

static void PrePostInverseBlitterProc ( SkBlitter *  blitter, int  y, bool  isStart  )

static

Definition at line 368 of file SkScan_Path.cpp.

                                                                               {
    ((InverseBlitter*)blitter)->prepost(y, isStart);
}

round_down_to_int()

static int round_down_to_int ( SkScalar  x )

inlinestatic

Round the value down. This is used to round the top and left of a rectangle, and corresponds to the way the scan converter treats the top and left edges. It has a slight bias to make the "rounded" int smaller than a normal round, to create a more conservative int-bounds (larger) from a float rect.

Definition at line 591 of file SkScan_Path.cpp.

                                                {
    double xx = x;
    xx -= kConservativeRoundBias;
    return sk_double_saturate2int(ceil(xx));
}

round_up_to_int()

static int round_up_to_int ( SkScalar  x )

inlinestatic

Round the value up. This is used to round the right and bottom of a rectangle. It has a slight bias to make the "rounded" int smaller than a normal round, to create a more conservative int-bounds (larger) from a float rect.

Definition at line 602 of file SkScan_Path.cpp.

                                              {
    double xx = x;
    xx += kConservativeRoundBias;
    return sk_double_saturate2int(floor(xx));
}

sk_blit_above()

void sk_blit_above	(	SkBlitter *	blitter,
		const SkIRect &	ir,
		const SkRegion &	clip
	)

Definition at line 487 of file SkScan_Path.cpp.

                                                                                {
    const SkIRect& cr = clip.getBounds();
    SkIRect tmp;
 
    tmp.fLeft = cr.fLeft;
    tmp.fRight = cr.fRight;
    tmp.fTop = cr.fTop;
    tmp.fBottom = ir.fTop;
    if (!tmp.isEmpty()) {
        blitter->blitRectRegion(tmp, clip);
    }
}

sk_blit_below()

void sk_blit_below	(	SkBlitter *	blitter,
		const SkIRect &	ir,
		const SkRegion &	clip
	)

Definition at line 500 of file SkScan_Path.cpp.

                                                                                {
    const SkIRect& cr = clip.getBounds();
    SkIRect tmp;
 
    tmp.fLeft = cr.fLeft;
    tmp.fRight = cr.fRight;
    tmp.fTop = ir.fBottom;
    tmp.fBottom = cr.fBottom;
    if (!tmp.isEmpty()) {
        blitter->blitRectRegion(tmp, clip);
    }
}

sk_fill_path()

void sk_fill_path	(	const SkPath &	path,
		const SkIRect &	clipRect,
		SkBlitter *	blitter,
		int	start_y,
		int	stop_y,
		int	shiftEdgesUp,
		bool	pathContainedInClip
	)

Definition at line 404 of file SkScan_Path.cpp.

                                                                                       {
    SkASSERT(blitter);
 
    SkIRect shiftedClip = clipRect;
    shiftedClip.fLeft = SkLeftShift(shiftedClip.fLeft, shiftEdgesUp);
    shiftedClip.fRight = SkLeftShift(shiftedClip.fRight, shiftEdgesUp);
    shiftedClip.fTop = SkLeftShift(shiftedClip.fTop, shiftEdgesUp);
    shiftedClip.fBottom = SkLeftShift(shiftedClip.fBottom, shiftEdgesUp);
 
    SkBasicEdgeBuilder builder(shiftEdgesUp);
    int count = builder.buildEdges(path, pathContainedInClip ? nullptr : &shiftedClip);
    SkEdge** list = builder.edgeList();
 
    if (0 == count) {
        if (path.isInverseFillType()) {
            /*
             *  Since we are in inverse-fill, our caller has already drawn above
             *  our top (start_y) and will draw below our bottom (stop_y). Thus
             *  we need to restrict our drawing to the intersection of the clip
             *  and those two limits.
             */
            SkIRect rect = clipRect;
            if (rect.fTop < start_y) {
                rect.fTop = start_y;
            }
            if (rect.fBottom > stop_y) {
                rect.fBottom = stop_y;
            }
            if (!rect.isEmpty()) {
                blitter->blitRect(rect.fLeft << shiftEdgesUp,
                                  rect.fTop << shiftEdgesUp,
                                  rect.width() << shiftEdgesUp,
                                  rect.height() << shiftEdgesUp);
            }
        }
        return;
    }
 
    SkEdge headEdge, tailEdge, *last;
    // this returns the first and last edge after they're sorted into a dlink list
    SkEdge* edge = sort_edges(list, count, &last);
 
    headEdge.fPrev = nullptr;
    headEdge.fNext = edge;
    headEdge.fFirstY = kEDGE_HEAD_Y;
    headEdge.fX = SK_MinS32;
    edge->fPrev = &headEdge;
 
    tailEdge.fPrev = last;
    tailEdge.fNext = nullptr;
    tailEdge.fFirstY = kEDGE_TAIL_Y;
    last->fNext = &tailEdge;
 
    // now edge is the head of the sorted linklist
 
    start_y = SkLeftShift(start_y, shiftEdgesUp);
    stop_y = SkLeftShift(stop_y, shiftEdgesUp);
    if (!pathContainedInClip && start_y < shiftedClip.fTop) {
        start_y = shiftedClip.fTop;
    }
    if (!pathContainedInClip && stop_y > shiftedClip.fBottom) {
        stop_y = shiftedClip.fBottom;
    }
 
    InverseBlitter  ib;
    PrePostProc     proc = nullptr;
 
    if (path.isInverseFillType()) {
        ib.setBlitter(blitter, clipRect, shiftEdgesUp);
        blitter = &ib;
        proc = PrePostInverseBlitterProc;
    }
 
    // count >= 2 is required as the convex walker does not handle missing right edges
    if (path.isConvex() && (nullptr == proc) && count >= 2) {
        walk_simple_edges(&headEdge, blitter, start_y, stop_y);
    } else {
        walk_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, proc,
                   shiftedClip.right());
    }
}

sk_fill_triangle()

static void sk_fill_triangle ( const SkPoint  pts[], const SkIRect *  clipRect, SkBlitter *  blitter, const SkIRect &  ir  )

static

Definition at line 714 of file SkScan_Path.cpp.

                                                                    {
    SkASSERT(pts && blitter);
 
    SkEdge edgeStorage[3];
    SkEdge* list[3];
 
    int count = build_tri_edges(edgeStorage, pts, clipRect, list);
    if (count < 2) {
        return;
    }
 
    SkEdge headEdge, tailEdge, *last;
 
    // this returns the first and last edge after they're sorted into a dlink list
    SkEdge* edge = sort_edges(list, count, &last);
 
    headEdge.fPrev = nullptr;
    headEdge.fNext = edge;
    headEdge.fFirstY = kEDGE_HEAD_Y;
    headEdge.fX = SK_MinS32;
    edge->fPrev = &headEdge;
 
    tailEdge.fPrev = last;
    tailEdge.fNext = nullptr;
    tailEdge.fFirstY = kEDGE_TAIL_Y;
    last->fNext = &tailEdge;
 
    // now edge is the head of the sorted linklist
    int stop_y = ir.fBottom;
    if (clipRect && stop_y > clipRect->fBottom) {
        stop_y = clipRect->fBottom;
    }
    int start_y = ir.fTop;
    if (clipRect && start_y < clipRect->fTop) {
        start_y = clipRect->fTop;
    }
    walk_simple_edges(&headEdge, blitter, start_y, stop_y);
}

sort_edges()

static SkEdge * sort_edges ( SkEdge *  list[], int  count, SkEdge **  last  )

static

Definition at line 390 of file SkScan_Path.cpp.

                                                                    {
    SkTQSort(list, list + count);
 
    // now make the edges linked in sorted order
    for (int i = 1; i < count; i++) {
        list[i - 1]->fNext = list[i];
        list[i]->fPrev = list[i - 1];
    }
 
    *last = list[count - 1];
    return list[0];
}

update_edge()

static bool update_edge ( SkEdge *  edge, int  last_y  )

static

Definition at line 206 of file SkScan_Path.cpp.

                                                  {
    SkASSERT(edge->fLastY >= last_y);
    if (last_y == edge->fLastY) {
        if (edge->fCurveCount < 0) {
            if (((SkCubicEdge*)edge)->updateCubic()) {
                SkASSERT(edge->fFirstY == last_y + 1);
                return true;
            }
        } else if (edge->fCurveCount > 0) {
            if (((SkQuadraticEdge*)edge)->updateQuadratic()) {
                SkASSERT(edge->fFirstY == last_y + 1);
                return true;
            }
        }
        return false;
    }
    return true;
}

walk_edges()

static void walk_edges ( SkEdge *  prevHead, SkPathFillType  fillType, SkBlitter *  blitter, int  start_y, int  stop_y, PrePostProc  proc, int  rightClip  )

static

Definition at line 113 of file SkScan_Path.cpp.

                                                        {
    validate_sort(prevHead->fNext);
 
    int curr_y = start_y;
    int windingMask = SkPathFillType_IsEvenOdd(fillType) ? 1 : -1;
 
    for (;;) {
        int     w = 0;
        int     left SK_INIT_TO_AVOID_WARNING;
        SkEdge* currE = prevHead->fNext;
        SkFixed prevX = prevHead->fX;
 
        validate_edges_for_y(currE, curr_y);
 
        if (proc) {
            proc(blitter, curr_y, PREPOST_START);    // pre-proc
        }
 
        while (currE->fFirstY <= curr_y) {
            SkASSERT(currE->fLastY >= curr_y);
 
            int x = SkFixedRoundToInt(currE->fX);
 
            if ((w & windingMask) == 0) { // we're starting interval
                left = x;
            }
 
            w += currE->fWinding;
 
            if ((w & windingMask) == 0) { // we finished an interval
                int width = x - left;
                SkASSERT(width >= 0);
                if (width > 0) {
                    blitter->blitH(left, curr_y, width);
                }
            }
 
            SkEdge* next = currE->fNext;
            SkFixed newX;
 
            if (currE->fLastY == curr_y) {    // are we done with this edge?
                if (currE->fCurveCount > 0) {
                    if (((SkQuadraticEdge*)currE)->updateQuadratic()) {
                        newX = currE->fX;
                        goto NEXT_X;
                    }
                } else if (currE->fCurveCount < 0) {
                    if (((SkCubicEdge*)currE)->updateCubic()) {
                        SkASSERT(currE->fFirstY == curr_y + 1);
 
                        newX = currE->fX;
                        goto NEXT_X;
                    }
                }
                remove_edge(currE);
            } else {
                SkASSERT(currE->fLastY > curr_y);
                newX = currE->fX + currE->fDX;
                currE->fX = newX;
            NEXT_X:
                if (newX < prevX) { // ripple currE backwards until it is x-sorted
                    backward_insert_edge_based_on_x(currE);
                } else {
                    prevX = newX;
                }
            }
            currE = next;
            SkASSERT(currE);
        }
 
        if ((w & windingMask) != 0) { // was our right-edge culled away?
            int width = rightClip - left;
            if (width > 0) {
                blitter->blitH(left, curr_y, width);
            }
        }
 
        if (proc) {
            proc(blitter, curr_y, PREPOST_END);    // post-proc
        }
 
        curr_y += 1;
        if (curr_y >= stop_y) {
            break;
        }
        // now currE points to the first edge with a Yint larger than curr_y
        insert_new_edges(currE, curr_y);
    }
}

walk_simple_edges()

static void walk_simple_edges ( SkEdge *  prevHead, SkBlitter *  blitter, int  start_y, int  stop_y  )

static

Definition at line 235 of file SkScan_Path.cpp.

                                                                                             {
    validate_sort(prevHead->fNext);
 
    SkEdge* leftE = prevHead->fNext;
    SkEdge* riteE = leftE->fNext;
    SkEdge* currE = riteE->fNext;
 
    // our edge choppers for curves can result in the initial edges
    // not lining up, so we take the max.
    int local_top = std::max(leftE->fFirstY, riteE->fFirstY);
    ASSERT_RETURN(local_top >= start_y);
 
    while (local_top < stop_y) {
        SkASSERT(leftE->fFirstY <= stop_y);
        SkASSERT(riteE->fFirstY <= stop_y);
 
        int local_bot = std::min(leftE->fLastY, riteE->fLastY);
        local_bot = std::min(local_bot, stop_y - 1);
        ASSERT_RETURN(local_top <= local_bot);
 
        SkFixed left = leftE->fX;
        SkFixed dLeft = leftE->fDX;
        SkFixed rite = riteE->fX;
        SkFixed dRite = riteE->fDX;
        int count = local_bot - local_top;
        ASSERT_RETURN(count >= 0);
 
        if (0 == (dLeft | dRite)) {
            int L = SkFixedRoundToInt(left);
            int R = SkFixedRoundToInt(rite);
            if (L > R) {
                std::swap(L, R);
            }
            if (L < R) {
                count += 1;
                blitter->blitRect(L, local_top, R - L, count);
            }
            local_top = local_bot + 1;
        } else {
            do {
                int L = SkFixedRoundToInt(left);
                int R = SkFixedRoundToInt(rite);
                if (L > R) {
                    std::swap(L, R);
                }
                if (L < R) {
                    blitter->blitH(L, local_top, R - L);
                }
                // Either/both of these might overflow, since we perform this step even if
                // (later) we determine that we are done with the edge, and so the computed
                // left or rite edge will not be used (see update_edge). Use this helper to
                // silence UBSAN when we perform the add.
                left = Sk32_can_overflow_add(left, dLeft);
                rite = Sk32_can_overflow_add(rite, dRite);
                local_top += 1;
            } while (--count >= 0);
        }
 
        leftE->fX = left;
        riteE->fX = rite;
 
        if (!update_edge(leftE, local_bot)) {
            if (currE->fFirstY >= stop_y) {
                return; // we're done
            }
            leftE = currE;
            currE = currE->fNext;
            ASSERT_RETURN(leftE->fFirstY == local_top);
        }
        if (!update_edge(riteE, local_bot)) {
            if (currE->fFirstY >= stop_y) {
                return; // we're done
            }
            riteE = currE;
            currE = currE->fNext;
            ASSERT_RETURN(riteE->fFirstY == local_top);
        }
    }
}

Variable Documentation

kConservativeRoundBias

const double kConservativeRoundBias = 0.5 + 1.5 / SK_FDot6One

static

Definition at line 583 of file SkScan_Path.cpp.