SkPolyUtils.cpp File Reference

#include "src/utils/SkPolyUtils.h"
#include "include/core/SkRect.h"
#include "include/core/SkTypes.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkFloatingPoint.h"
#include "include/private/base/SkMalloc.h"
#include "include/private/base/SkTArray.h"
#include "include/private/base/SkTDArray.h"
#include "include/private/base/SkTemplates.h"
#include "src/base/SkTDPQueue.h"
#include "src/base/SkTInternalLList.h"
#include "src/base/SkVx.h"
#include "src/core/SkPointPriv.h"
#include "src/core/SkRectPriv.h"
#include <algorithm>
#include <cstdint>
#include <limits>
#include <new>

Go to the source code of this file.

Classes
struct	OffsetSegment
struct	OffsetEdge
struct	Vertex
struct	ActiveEdge
class	ActiveEdgeList
struct	TriangulationVertex
class	ReflexHash

Enumerations
enum	VertexFlags { kPrevLeft_VertexFlag = 0x1 , kNextLeft_VertexFlag = 0x2 }

Functions
static int	compute_side (const SkPoint &p0, const SkVector &v, const SkPoint &p)
int	SkGetPolygonWinding (const SkPoint *polygonVerts, int polygonSize)
bool	compute_offset_vector (const SkPoint &p0, const SkPoint &p1, SkScalar offset, int side, SkPoint *vector)
static bool	outside_interval (SkScalar numer, SkScalar denom, bool denomPositive)
static bool	zero_length (const SkPoint &v, SkScalar vdotv)
static bool	compute_intersection (const OffsetSegment &s0, const OffsetSegment &s1, SkPoint *p, SkScalar *s, SkScalar *t)
bool	SkIsConvexPolygon (const SkPoint *polygonVerts, int polygonSize)
static void	remove_node (const OffsetEdge *node, OffsetEdge **head)
bool	SkInsetConvexPolygon (const SkPoint *inputPolygonVerts, int inputPolygonSize, SkScalar inset, SkTDArray< SkPoint > *insetPolygon)
bool	SkComputeRadialSteps (const SkVector &v1, const SkVector &v2, SkScalar offset, SkScalar *rotSin, SkScalar *rotCos, int *n)
static bool	left (const SkPoint &p0, const SkPoint &p1)
static bool	right (const SkPoint &p0, const SkPoint &p1)
bool	SkIsSimplePolygon (const SkPoint *polygon, int polygonSize)
static void	setup_offset_edge (OffsetEdge *currEdge, const SkPoint &endpoint0, const SkPoint &endpoint1, uint16_t startIndex, uint16_t endIndex)
static bool	is_reflex_vertex (const SkPoint *inputPolygonVerts, int winding, SkScalar offset, uint16_t prevIndex, uint16_t currIndex, uint16_t nextIndex)
bool	SkOffsetSimplePolygon (const SkPoint *inputPolygonVerts, int inputPolygonSize, const SkRect &bounds, SkScalar offset, SkTDArray< SkPoint > *offsetPolygon, SkTDArray< int > *polygonIndices)
static void	compute_triangle_bounds (const SkPoint &p0, const SkPoint &p1, const SkPoint &p2, SkRect *bounds)
static bool	point_in_triangle (const SkPoint &p0, const SkPoint &p1, const SkPoint &p2, const SkPoint &p)
static void	reclassify_vertex (TriangulationVertex *p, const SkPoint *polygonVerts, int winding, ReflexHash *reflexHash, SkTInternalLList< TriangulationVertex > *convexList)
bool	SkTriangulateSimplePolygon (const SkPoint *polygonVerts, uint16_t *indexMap, int polygonSize, SkTDArray< uint16_t > *triangleIndices)

Variables
constexpr SkScalar	kCrossTolerance = SK_ScalarNearlyZero * SK_ScalarNearlyZero

Enumeration Type Documentation

VertexFlags

enum VertexFlags

Enumerator
kPrevLeft_VertexFlag
kNextLeft_VertexFlag

Definition at line 549 of file SkPolyUtils.cpp.

                 {
    kPrevLeft_VertexFlag = 0x1,
    kNextLeft_VertexFlag = 0x2,
};

Function Documentation

compute_intersection()

static bool compute_intersection ( const OffsetSegment &  s0, const OffsetSegment &  s1, SkPoint *  p, SkScalar *  s, SkScalar *  t  )

static

Definition at line 106 of file SkPolyUtils.cpp.

                                                                       {
    const SkVector& v0 = s0.fV;
    const SkVector& v1 = s1.fV;
    SkVector w = s1.fP0 - s0.fP0;
    SkScalar denom = v0.cross(v1);
    bool denomPositive = (denom > 0);
    SkScalar sNumer, tNumer;
    if (SkScalarNearlyZero(denom, kCrossTolerance)) {
        // segments are parallel, but not collinear
        if (!SkScalarNearlyZero(w.cross(v0), kCrossTolerance) ||
            !SkScalarNearlyZero(w.cross(v1), kCrossTolerance)) {
            return false;
        }
 
        // Check for zero-length segments
        SkScalar v0dotv0 = v0.dot(v0);
        if (zero_length(v0, v0dotv0)) {
            // Both are zero-length
            SkScalar v1dotv1 = v1.dot(v1);
            if (zero_length(v1, v1dotv1)) {
                // Check if they're the same point
                if (!SkPointPriv::CanNormalize(w.fX, w.fY)) {
                    *p = s0.fP0;
                    *s = 0;
                    *t = 0;
                    return true;
                } else {
                    // Intersection is indeterminate
                    return false;
                }
            }
            // Otherwise project segment0's origin onto segment1
            tNumer = v1.dot(-w);
            denom = v1dotv1;
            if (outside_interval(tNumer, denom, true)) {
                return false;
            }
            sNumer = 0;
        } else {
            // Project segment1's endpoints onto segment0
            sNumer = v0.dot(w);
            denom = v0dotv0;
            tNumer = 0;
            if (outside_interval(sNumer, denom, true)) {
                // The first endpoint doesn't lie on segment0
                // If segment1 is degenerate, then there's no collision
                SkScalar v1dotv1 = v1.dot(v1);
                if (zero_length(v1, v1dotv1)) {
                    return false;
                }
 
                // Otherwise try the other one
                SkScalar oldSNumer = sNumer;
                sNumer = v0.dot(w + v1);
                tNumer = denom;
                if (outside_interval(sNumer, denom, true)) {
                    // it's possible that segment1's interval surrounds segment0
                    // this is false if params have the same signs, and in that case no collision
                    if (sNumer*oldSNumer > 0) {
                        return false;
                    }
                    // otherwise project segment0's endpoint onto segment1 instead
                    sNumer = 0;
                    tNumer = v1.dot(-w);
                    denom = v1dotv1;
                }
            }
        }
    } else {
        sNumer = w.cross(v1);
        if (outside_interval(sNumer, denom, denomPositive)) {
            return false;
        }
        tNumer = w.cross(v0);
        if (outside_interval(tNumer, denom, denomPositive)) {
            return false;
        }
    }
 
    SkScalar localS = sNumer/denom;
    SkScalar localT = tNumer/denom;
 
    *p = s0.fP0 + v0*localS;
    *s = localS;
    *t = localT;
 
    return true;
}

compute_offset_vector()

bool compute_offset_vector	(	const SkPoint &	p0,
		const SkPoint &	p1,
		SkScalar	offset,
		int	side,
		SkPoint *	vector
	)

Definition at line 78 of file SkPolyUtils.cpp.

                                            {
    SkASSERT(side == -1 || side == 1);
    // if distances are equal, can just outset by the perpendicular
    SkVector perp = SkVector::Make(p0.fY - p1.fY, p1.fX - p0.fX);
    if (!perp.setLength(offset*side)) {
        return false;
    }
    *vector = perp;
    return true;
}

compute_side()

static int compute_side ( const SkPoint &  p0, const SkVector &  v, const SkPoint &  p  )

static

Definition at line 46 of file SkPolyUtils.cpp.

                                                                                {
    SkVector w = p - p0;
    SkScalar perpDot = v.cross(w);
    if (!SkScalarNearlyZero(perpDot, kCrossTolerance)) {
        return ((perpDot > 0) ? 1 : -1);
    }
 
    return 0;
}

compute_triangle_bounds()

static void compute_triangle_bounds ( const SkPoint &  p0, const SkPoint &  p1, const SkPoint &  p2, SkRect *  bounds  )

static

Definition at line 1484 of file SkPolyUtils.cpp.

                                                    {
    skvx::float4 min, max;
    min = max = skvx::float4(p0.fX, p0.fY, p0.fX, p0.fY);
    skvx::float4 xy(p1.fX, p1.fY, p2.fX, p2.fY);
    min = skvx::min(min, xy);
    max = skvx::max(max, xy);
    bounds->setLTRB(std::min(min[0], min[2]), std::min(min[1], min[3]),
                    std::max(max[0], max[2]), std::max(max[1], max[3]));
}

is_reflex_vertex()

static bool is_reflex_vertex ( const SkPoint *  inputPolygonVerts, int  winding, SkScalar  offset, uint16_t  prevIndex, uint16_t  currIndex, uint16_t  nextIndex  )

static

Definition at line 1186 of file SkPolyUtils.cpp.

                                                                                         {
    int side = compute_side(inputPolygonVerts[prevIndex],
                            inputPolygonVerts[currIndex] - inputPolygonVerts[prevIndex],
                            inputPolygonVerts[nextIndex]);
    // if reflex point, we need to add extra edges
    return (side*winding*offset < 0);
}

left()

static bool left ( const SkPoint &  p0, const SkPoint &  p1  )

static

Definition at line 527 of file SkPolyUtils.cpp.

                                                       {
    return p0.fX < p1.fX || (!(p0.fX > p1.fX) && p0.fY > p1.fY);
}

outside_interval()

static bool outside_interval ( SkScalar  numer, SkScalar  denom, bool  denomPositive  )

inlinestatic

Definition at line 91 of file SkPolyUtils.cpp.

                                                                                        {
    return (denomPositive && (numer < 0 || numer > denom)) ||
           (!denomPositive && (numer > 0 || numer < denom));
}

point_in_triangle()

static bool point_in_triangle ( const SkPoint &  p0, const SkPoint &  p1, const SkPoint &  p2, const SkPoint &  p  )

static

Definition at line 1497 of file SkPolyUtils.cpp.

                                                {
    SkVector v0 = p1 - p0;
    SkVector v1 = p2 - p1;
    SkScalar n = v0.cross(v1);
 
    SkVector w0 = p - p0;
    if (n*v0.cross(w0) < SK_ScalarNearlyZero) {
        return false;
    }
 
    SkVector w1 = p - p1;
    if (n*v1.cross(w1) < SK_ScalarNearlyZero) {
        return false;
    }
 
    SkVector v2 = p0 - p2;
    SkVector w2 = p - p2;
    if (n*v2.cross(w2) < SK_ScalarNearlyZero) {
        return false;
    }
 
    return true;
}

reclassify_vertex()

static void reclassify_vertex ( TriangulationVertex *  p, const SkPoint *  polygonVerts, int  winding, ReflexHash *  reflexHash, SkTInternalLList< TriangulationVertex > *  convexList  )

static

Definition at line 1617 of file SkPolyUtils.cpp.

                                                                                 {
    if (TriangulationVertex::VertexType::kReflex == p->fVertexType) {
        SkVector v0 = p->fPosition - polygonVerts[p->fPrevIndex];
        SkVector v1 = polygonVerts[p->fNextIndex] - p->fPosition;
        if (winding*v0.cross(v1) > SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
            p->fVertexType = TriangulationVertex::VertexType::kConvex;
            reflexHash->remove(p);
            p->fPrev = p->fNext = nullptr;
            convexList->addToTail(p);
        }
    }
}

remove_node()

static void remove_node ( const OffsetEdge *  node, OffsetEdge **  head  )

static

Definition at line 315 of file SkPolyUtils.cpp.

                                                                   {
    // remove from linked list
    node->fPrev->fNext = node->fNext;
    node->fNext->fPrev = node->fPrev;
    if (node == *head) {
        *head = (node->fNext == node) ? nullptr : node->fNext;
    }
}

right()

static bool right ( const SkPoint &  p0, const SkPoint &  p1  )

static

Definition at line 532 of file SkPolyUtils.cpp.

                                                        {
    return p0.fX > p1.fX || (!(p0.fX < p1.fX) && p0.fY < p1.fY);
}

setup_offset_edge()

static void setup_offset_edge ( OffsetEdge *  currEdge, const SkPoint &  endpoint0, const SkPoint &  endpoint1, uint16_t  startIndex, uint16_t  endIndex  )

static

Definition at line 1178 of file SkPolyUtils.cpp.

                                                                      {
    currEdge->fOffset.fP0 = endpoint0;
    currEdge->fOffset.fV = endpoint1 - endpoint0;
    currEdge->init(startIndex, endIndex);
}

SkComputeRadialSteps()

bool SkComputeRadialSteps	(	const SkVector &	offset0,
		const SkVector &	offset1,
		SkScalar	offset,
		SkScalar *	rotSin,
		SkScalar *	rotCos,
		int *	n
	)

Compute the number of points needed for a circular join when offsetting a vertex. The lengths of offset0 and offset1 don't have to equal |offset| – only the direction matters. The segment lengths will be approximately four pixels.

Parameters

offset0	Starting offset vector direction.
offset1	Ending offset vector direction.
offset	Offset value (can be negative).
rotSin	Sine of rotation delta per step.
rotCos	Cosine of rotation delta per step.
n	Number of steps to fill out the arc.

Returns

true for success, false otherwise

Definition at line 490 of file SkPolyUtils.cpp.

                                                                      {
    const SkScalar kRecipPixelsPerArcSegment = 0.25f;
 
    SkScalar rCos = v1.dot(v2);
    if (!SkIsFinite(rCos)) {
        return false;
    }
    SkScalar rSin = v1.cross(v2);
    if (!SkIsFinite(rSin)) {
        return false;
    }
    SkScalar theta = SkScalarATan2(rSin, rCos);
 
    SkScalar floatSteps = SkScalarAbs(offset*theta*kRecipPixelsPerArcSegment);
    // limit the number of steps to at most max uint16_t (that's all we can index)
    // knock one value off the top to account for rounding
    if (floatSteps >= std::numeric_limits<uint16_t>::max()) {
        return false;
    }
    int steps = SkScalarRoundToInt(floatSteps);
 
    SkScalar dTheta = steps > 0 ? theta / steps : 0;
    *rotSin = SkScalarSin(dTheta);
    *rotCos = SkScalarCos(dTheta);
    // Our offset may be so large that we end up with a tiny dTheta, in which case we
    // lose precision when computing rotSin and rotCos.
    if (steps > 0 && (*rotSin == 0 || *rotCos == 1)) {
        return false;
    }
    *n = steps;
    return true;
}

SkGetPolygonWinding()

int SkGetPolygonWinding	(	const SkPoint *	polygonVerts,
		int	polygonSize
	)

Determine winding direction for a polygon. The input polygon must be simple or the result will be meaningless.

Parameters

polygonVerts	Array of points representing the vertices of the polygon.
polygonSize	Number of vertices in the polygon.

Returns

1 for cw, -1 for ccw, and 0 if zero signed area (either degenerate or self-intersecting). The y-axis is assumed to be pointing down.

Definition at line 57 of file SkPolyUtils.cpp.

                                                                      {
    if (polygonSize < 3) {
        return 0;
    }
 
    // compute area and use sign to determine winding
    SkScalar quadArea = 0;
    SkVector v0 = polygonVerts[1] - polygonVerts[0];
    for (int curr = 2; curr < polygonSize; ++curr) {
        SkVector v1 = polygonVerts[curr] - polygonVerts[0];
        quadArea += v0.cross(v1);
        v0 = v1;
    }
    if (SkScalarNearlyZero(quadArea, kCrossTolerance)) {
        return 0;
    }
    // 1 == ccw, -1 == cw
    return (quadArea > 0) ? 1 : -1;
}

SkInsetConvexPolygon()

bool SkInsetConvexPolygon	(	const SkPoint *	inputPolygonVerts,
		int	inputPolygonSize,
		SkScalar	inset,
		SkTDArray< SkPoint > *	insetPolygon
	)

Generates a polygon that is inset a constant from the boundary of a given convex polygon. The input polygon is expected to have values clamped to the nearest 1/16th.

Parameters

inputPolygonVerts	Array of points representing the vertices of the original polygon. It should be convex and have no coincident points.
inputPolygonSize	Number of vertices in the original polygon.
inset	How far we wish to inset the polygon. This should be a positive value.
insetPolygon	The resulting inset polygon, if any.

Returns

true if an inset polygon exists, false otherwise.

Definition at line 338 of file SkPolyUtils.cpp.

                                                                            {
    if (inputPolygonSize < 3) {
        return false;
    }
 
    // restrict this to match other routines
    // practically we don't want anything bigger than this anyway
    if (inputPolygonSize > std::numeric_limits<uint16_t>::max()) {
        return false;
    }
 
    // can't inset by a negative or non-finite amount
    if (inset < -SK_ScalarNearlyZero || !SkIsFinite(inset)) {
        return false;
    }
 
    // insetting close to zero just returns the original poly
    if (inset <= SK_ScalarNearlyZero) {
        for (int i = 0; i < inputPolygonSize; ++i) {
            *insetPolygon->append() = inputPolygonVerts[i];
        }
        return true;
    }
 
    // get winding direction
    int winding = SkGetPolygonWinding(inputPolygonVerts, inputPolygonSize);
    if (0 == winding) {
        return false;
    }
 
    // set up
    AutoSTMalloc<64, OffsetEdge> edgeData(inputPolygonSize);
    int prev = inputPolygonSize - 1;
    for (int curr = 0; curr < inputPolygonSize; prev = curr, ++curr) {
        int next = (curr + 1) % inputPolygonSize;
        if (!inputPolygonVerts[curr].isFinite()) {
            return false;
        }
        // check for convexity just to be sure
        if (compute_side(inputPolygonVerts[prev], inputPolygonVerts[curr] - inputPolygonVerts[prev],
                         inputPolygonVerts[next])*winding < 0) {
            return false;
        }
        SkVector v = inputPolygonVerts[next] - inputPolygonVerts[curr];
        SkVector perp = SkVector::Make(-v.fY, v.fX);
        perp.setLength(inset*winding);
        edgeData[curr].fPrev = &edgeData[prev];
        edgeData[curr].fNext = &edgeData[next];
        edgeData[curr].fOffset.fP0 = inputPolygonVerts[curr] + perp;
        edgeData[curr].fOffset.fV = v;
        edgeData[curr].init();
    }
 
    OffsetEdge* head = &edgeData[0];
    OffsetEdge* currEdge = head;
    OffsetEdge* prevEdge = currEdge->fPrev;
    int insetVertexCount = inputPolygonSize;
    unsigned int iterations = 0;
    unsigned int maxIterations = inputPolygonSize * inputPolygonSize;
    while (head && prevEdge != currEdge) {
        ++iterations;
        // we should check each edge against each other edge at most once
        if (iterations > maxIterations) {
            return false;
        }
 
        SkScalar s, t;
        SkPoint intersection;
        if (compute_intersection(prevEdge->fOffset, currEdge->fOffset,
                                 &intersection, &s, &t)) {
            // if new intersection is further back on previous inset from the prior intersection
            if (s < prevEdge->fTValue) {
                // no point in considering this one again
                remove_node(prevEdge, &head);
                --insetVertexCount;
                // go back one segment
                prevEdge = prevEdge->fPrev;
            // we've already considered this intersection, we're done
            } else if (currEdge->fTValue > SK_ScalarMin &&
                       SkPointPriv::EqualsWithinTolerance(intersection,
                                                          currEdge->fIntersection,
                                                          1.0e-6f)) {
                break;
            } else {
                // add intersection
                currEdge->fIntersection = intersection;
                currEdge->fTValue = t;
 
                // go to next segment
                prevEdge = currEdge;
                currEdge = currEdge->fNext;
            }
        } else {
            // if prev to right side of curr
            int side = winding*compute_side(currEdge->fOffset.fP0,
                                            currEdge->fOffset.fV,
                                            prevEdge->fOffset.fP0);
            if (side < 0 &&
                side == winding*compute_side(currEdge->fOffset.fP0,
                                             currEdge->fOffset.fV,
                                             prevEdge->fOffset.fP0 + prevEdge->fOffset.fV)) {
                // no point in considering this one again
                remove_node(prevEdge, &head);
                --insetVertexCount;
                // go back one segment
                prevEdge = prevEdge->fPrev;
            } else {
                // move to next segment
                remove_node(currEdge, &head);
                --insetVertexCount;
                currEdge = currEdge->fNext;
            }
        }
    }
 
    // store all the valid intersections that aren't nearly coincident
    // TODO: look at the main algorithm and see if we can detect these better
    insetPolygon->reset();
    if (!head) {
        return false;
    }
 
    static constexpr SkScalar kCleanupTolerance = 0.01f;
    if (insetVertexCount >= 0) {
        insetPolygon->reserve(insetVertexCount);
    }
    int currIndex = 0;
    *insetPolygon->append() = head->fIntersection;
    currEdge = head->fNext;
    while (currEdge != head) {
        if (!SkPointPriv::EqualsWithinTolerance(currEdge->fIntersection,
                                                (*insetPolygon)[currIndex],
                                                kCleanupTolerance)) {
            *insetPolygon->append() = currEdge->fIntersection;
            currIndex++;
        }
        currEdge = currEdge->fNext;
    }
    // make sure the first and last points aren't coincident
    if (currIndex >= 1 &&
        SkPointPriv::EqualsWithinTolerance((*insetPolygon)[0], (*insetPolygon)[currIndex],
                                            kCleanupTolerance)) {
        insetPolygon->pop_back();
    }
 
    return SkIsConvexPolygon(insetPolygon->begin(), insetPolygon->size());
}

SkIsConvexPolygon()

bool SkIsConvexPolygon	(	const SkPoint *	polygonVerts,
		int	polygonSize
	)

Determine whether a polygon is convex or not.

Parameters

polygonVerts	Array of points representing the vertices of the polygon.
polygonSize	Number of vertices in the polygon.

Returns

true if the polygon is convex, false otherwise.

Definition at line 196 of file SkPolyUtils.cpp.

                                                                     {
    if (polygonSize < 3) {
        return false;
    }
 
    SkScalar lastPerpDot = 0;
    int xSignChangeCount = 0;
    int ySignChangeCount = 0;
 
    int prevIndex = polygonSize - 1;
    int currIndex = 0;
    int nextIndex = 1;
    SkVector v0 = polygonVerts[currIndex] - polygonVerts[prevIndex];
    SkScalar lastVx = v0.fX;
    SkScalar lastVy = v0.fY;
    SkVector v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
    for (int i = 0; i < polygonSize; ++i) {
        if (!polygonVerts[i].isFinite()) {
            return false;
        }
 
        // Check that winding direction is always the same (otherwise we have a reflex vertex)
        SkScalar perpDot = v0.cross(v1);
        if (lastPerpDot*perpDot < 0) {
            return false;
        }
        if (0 != perpDot) {
            lastPerpDot = perpDot;
        }
 
        // Check that the signs of the edge vectors don't change more than twice per coordinate
        if (lastVx*v1.fX < 0) {
            xSignChangeCount++;
        }
        if (lastVy*v1.fY < 0) {
            ySignChangeCount++;
        }
        if (xSignChangeCount > 2 || ySignChangeCount > 2) {
            return false;
        }
        prevIndex = currIndex;
        currIndex = nextIndex;
        nextIndex = (currIndex + 1) % polygonSize;
        if (v1.fX != 0) {
            lastVx = v1.fX;
        }
        if (v1.fY != 0) {
            lastVy = v1.fY;
        }
        v0 = v1;
        v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
    }
 
    return true;
}

SkIsSimplePolygon()

bool SkIsSimplePolygon	(	const SkPoint *	polygonVerts,
		int	polygonSize
	)

Determine whether a polygon is simple (i.e., not self-intersecting) or not. The input polygon must have no coincident vertices or the test will fail. The polygon is also expected to have values clamped to the nearest 1/16th.

Parameters

polygonVerts	Array of points representing the vertices of the polygon.
polygonSize	Number of vertices in the polygon.

Returns

true if the polygon is simple, false otherwise.

Definition at line 1092 of file SkPolyUtils.cpp.

                                                                {
    if (polygonSize < 3) {
        return false;
    }
 
    // If it's convex, it's simple
    if (SkIsConvexPolygon(polygon, polygonSize)) {
        return true;
    }
 
    // practically speaking, it takes too long to process large polygons
    if (polygonSize > 2048) {
        return false;
    }
 
    SkTDPQueue <Vertex, Vertex::Left> vertexQueue(polygonSize);
    for (int i = 0; i < polygonSize; ++i) {
        Vertex newVertex;
        if (!polygon[i].isFinite()) {
            return false;
        }
        newVertex.fPosition = polygon[i];
        newVertex.fIndex = i;
        newVertex.fPrevIndex = (i - 1 + polygonSize) % polygonSize;
        newVertex.fNextIndex = (i + 1) % polygonSize;
        newVertex.fFlags = 0;
        // The two edges adjacent to this vertex are the same, so polygon is not simple
        if (polygon[newVertex.fPrevIndex] == polygon[newVertex.fNextIndex]) {
            return false;
        }
        if (left(polygon[newVertex.fPrevIndex], polygon[i])) {
            newVertex.fFlags |= kPrevLeft_VertexFlag;
        }
        if (left(polygon[newVertex.fNextIndex], polygon[i])) {
            newVertex.fFlags |= kNextLeft_VertexFlag;
        }
        vertexQueue.insert(newVertex);
    }
 
    // pop each vertex from the queue and generate events depending on
    // where it lies relative to its neighboring edges
    ActiveEdgeList sweepLine(polygonSize);
    while (vertexQueue.count() > 0) {
        const Vertex& v = vertexQueue.peek();
 
        // both to the right -- insert both
        if (v.fFlags == 0) {
            if (!sweepLine.insert(v.fPosition, polygon[v.fPrevIndex], v.fIndex, v.fPrevIndex)) {
                break;
            }
            if (!sweepLine.insert(v.fPosition, polygon[v.fNextIndex], v.fIndex, v.fNextIndex)) {
                break;
            }
        // both to the left -- remove both
        } else if (v.fFlags == (kPrevLeft_VertexFlag | kNextLeft_VertexFlag)) {
            if (!sweepLine.remove(polygon[v.fPrevIndex], v.fPosition, v.fPrevIndex, v.fIndex)) {
                break;
            }
            if (!sweepLine.remove(polygon[v.fNextIndex], v.fPosition, v.fNextIndex, v.fIndex)) {
                break;
            }
        // one to left and right -- replace one with another
        } else {
            if (v.fFlags & kPrevLeft_VertexFlag) {
                if (!sweepLine.replace(polygon[v.fPrevIndex], v.fPosition, polygon[v.fNextIndex],
                                       v.fPrevIndex, v.fIndex, v.fNextIndex)) {
                    break;
                }
            } else {
                SkASSERT(v.fFlags & kNextLeft_VertexFlag);
                if (!sweepLine.replace(polygon[v.fNextIndex], v.fPosition, polygon[v.fPrevIndex],
                                       v.fNextIndex, v.fIndex, v.fPrevIndex)) {
                    break;
                }
            }
        }
 
        vertexQueue.pop();
    }
 
    return (vertexQueue.count() == 0);
}

SkOffsetSimplePolygon()

bool SkOffsetSimplePolygon	(	const SkPoint *	inputPolygonVerts,
		int	inputPolygonSize,
		const SkRect &	bounds,
		SkScalar	offset,
		SkTDArray< SkPoint > *	offsetPolygon,
		SkTDArray< int > *	polygonIndices = nullptr
	)

Generates a simple polygon (if possible) that is offset a constant distance from the boundary of a given simple polygon. The input polygon must be simple, have no coincident vertices or collinear edges, and have values clamped to the nearest 1/16th.

Parameters

inputPolygonVerts	Array of points representing the vertices of the original polygon.
inputPolygonSize	Number of vertices in the original polygon.
bounds	Bounding rectangle for the original polygon.
offset	How far we wish to offset the polygon. Positive values indicate insetting, negative values outsetting.
offsetPolgon	The resulting offset polygon, if any.
polygonIndices	The indices of the original polygon that map to the new one.

Returns

true if an offset simple polygon exists, false otherwise.

Definition at line 1195 of file SkPolyUtils.cpp.

                                                                                              {
    if (inputPolygonSize < 3) {
        return false;
    }
 
    // need to be able to represent all the vertices in the 16-bit indices
    if (inputPolygonSize >= std::numeric_limits<uint16_t>::max()) {
        return false;
    }
 
    if (!SkIsFinite(offset)) {
        return false;
    }
 
    // can't inset more than the half bounds of the polygon
    if (offset > std::min(SkTAbs(SkRectPriv::HalfWidth(bounds)),
                          SkTAbs(SkRectPriv::HalfHeight(bounds)))) {
        return false;
    }
 
    // offsetting close to zero just returns the original poly
    if (SkScalarNearlyZero(offset)) {
        for (int i = 0; i < inputPolygonSize; ++i) {
            *offsetPolygon->append() = inputPolygonVerts[i];
            if (polygonIndices) {
                *polygonIndices->append() = i;
            }
        }
        return true;
    }
 
    // get winding direction
    int winding = SkGetPolygonWinding(inputPolygonVerts, inputPolygonSize);
    if (0 == winding) {
        return false;
    }
 
    // build normals
    AutoSTMalloc<64, SkVector> normals(inputPolygonSize);
    unsigned int numEdges = 0;
    for (int currIndex = 0, prevIndex = inputPolygonSize - 1;
         currIndex < inputPolygonSize;
         prevIndex = currIndex, ++currIndex) {
        if (!inputPolygonVerts[currIndex].isFinite()) {
            return false;
        }
        int nextIndex = (currIndex + 1) % inputPolygonSize;
        if (!compute_offset_vector(inputPolygonVerts[currIndex], inputPolygonVerts[nextIndex],
                                   offset, winding, &normals[currIndex])) {
            return false;
        }
        if (currIndex > 0) {
            // if reflex point, we need to add extra edges
            if (is_reflex_vertex(inputPolygonVerts, winding, offset,
                                 prevIndex, currIndex, nextIndex)) {
                SkScalar rotSin, rotCos;
                int numSteps;
                if (!SkComputeRadialSteps(normals[prevIndex], normals[currIndex], offset,
                                          &rotSin, &rotCos, &numSteps)) {
                    return false;
                }
                numEdges += std::max(numSteps, 1);
            }
        }
        numEdges++;
    }
    // finish up the edge counting
    if (is_reflex_vertex(inputPolygonVerts, winding, offset, inputPolygonSize-1, 0, 1)) {
        SkScalar rotSin, rotCos;
        int numSteps;
        if (!SkComputeRadialSteps(normals[inputPolygonSize-1], normals[0], offset,
                                  &rotSin, &rotCos, &numSteps)) {
            return false;
        }
        numEdges += std::max(numSteps, 1);
    }
 
    // Make sure we don't overflow the max array count.
    // We shouldn't overflow numEdges, as SkComputeRadialSteps returns a max of 2^16-1,
    // and we have a max of 2^16-1 original vertices.
    if (numEdges > (unsigned int)std::numeric_limits<int32_t>::max()) {
        return false;
    }
 
    // build initial offset edge list
    STArray<64, OffsetEdge> edgeData(numEdges);
    OffsetEdge* prevEdge = nullptr;
    for (int currIndex = 0, prevIndex = inputPolygonSize - 1;
         currIndex < inputPolygonSize;
         prevIndex = currIndex, ++currIndex) {
        int nextIndex = (currIndex + 1) % inputPolygonSize;
        // if reflex point, fill in curve
        if (is_reflex_vertex(inputPolygonVerts, winding, offset,
                             prevIndex, currIndex, nextIndex)) {
            SkScalar rotSin, rotCos;
            int numSteps;
            SkVector prevNormal = normals[prevIndex];
            if (!SkComputeRadialSteps(prevNormal, normals[currIndex], offset,
                                      &rotSin, &rotCos, &numSteps)) {
                return false;
            }
            auto currEdge = edgeData.push_back_n(std::max(numSteps, 1));
            for (int i = 0; i < numSteps - 1; ++i) {
                SkVector currNormal = SkVector::Make(prevNormal.fX*rotCos - prevNormal.fY*rotSin,
                                                     prevNormal.fY*rotCos + prevNormal.fX*rotSin);
                setup_offset_edge(currEdge,
                                  inputPolygonVerts[currIndex] + prevNormal,
                                  inputPolygonVerts[currIndex] + currNormal,
                                  currIndex, currIndex);
                prevNormal = currNormal;
                currEdge->fPrev = prevEdge;
                if (prevEdge) {
                    prevEdge->fNext = currEdge;
                }
                prevEdge = currEdge;
                ++currEdge;
            }
            setup_offset_edge(currEdge,
                              inputPolygonVerts[currIndex] + prevNormal,
                              inputPolygonVerts[currIndex] + normals[currIndex],
                              currIndex, currIndex);
            currEdge->fPrev = prevEdge;
            if (prevEdge) {
                prevEdge->fNext = currEdge;
            }
            prevEdge = currEdge;
        }
 
        // Add the edge
        auto currEdge = edgeData.push_back_n(1);
        setup_offset_edge(currEdge,
                          inputPolygonVerts[currIndex] + normals[currIndex],
                          inputPolygonVerts[nextIndex] + normals[currIndex],
                          currIndex, nextIndex);
        currEdge->fPrev = prevEdge;
        if (prevEdge) {
            prevEdge->fNext = currEdge;
        }
        prevEdge = currEdge;
    }
    // close up the linked list
    SkASSERT(prevEdge);
    prevEdge->fNext = &edgeData[0];
    edgeData[0].fPrev = prevEdge;
 
    // now clip edges
    SkASSERT(edgeData.size() == (int)numEdges);
    auto head = &edgeData[0];
    auto currEdge = head;
    unsigned int offsetVertexCount = numEdges;
    unsigned long long iterations = 0;
    unsigned long long maxIterations = (unsigned long long)(numEdges) * numEdges;
    while (head && prevEdge != currEdge && offsetVertexCount > 0) {
        ++iterations;
        // we should check each edge against each other edge at most once
        if (iterations > maxIterations) {
            return false;
        }
 
        SkScalar s, t;
        SkPoint intersection;
        if (prevEdge->checkIntersection(currEdge, &intersection, &s, &t)) {
            // if new intersection is further back on previous inset from the prior intersection
            if (s < prevEdge->fTValue) {
                // no point in considering this one again
                remove_node(prevEdge, &head);
                --offsetVertexCount;
                // go back one segment
                prevEdge = prevEdge->fPrev;
                // we've already considered this intersection, we're done
            } else if (currEdge->fTValue > SK_ScalarMin &&
                       SkPointPriv::EqualsWithinTolerance(intersection,
                                                          currEdge->fIntersection,
                                                          1.0e-6f)) {
                break;
            } else {
                // add intersection
                currEdge->fIntersection = intersection;
                currEdge->fTValue = t;
                currEdge->fIndex = prevEdge->fEnd;
 
                // go to next segment
                prevEdge = currEdge;
                currEdge = currEdge->fNext;
            }
        } else {
            // If there is no intersection, we want to minimize the distance between
            // the point where the segment lines cross and the segments themselves.
            OffsetEdge* prevPrevEdge = prevEdge->fPrev;
            OffsetEdge* currNextEdge = currEdge->fNext;
            SkScalar dist0 = currEdge->computeCrossingDistance(prevPrevEdge);
            SkScalar dist1 = prevEdge->computeCrossingDistance(currNextEdge);
            // if both lead to direct collision
            if (dist0 < 0 && dist1 < 0) {
                // check first to see if either represent parts of one contour
                SkPoint p1 = prevPrevEdge->fOffset.fP0 + prevPrevEdge->fOffset.fV;
                bool prevSameContour = SkPointPriv::EqualsWithinTolerance(p1,
                                                                          prevEdge->fOffset.fP0);
                p1 = currEdge->fOffset.fP0 + currEdge->fOffset.fV;
                bool currSameContour = SkPointPriv::EqualsWithinTolerance(p1,
                                                                         currNextEdge->fOffset.fP0);
 
                // want to step along contour to find intersections rather than jump to new one
                if (currSameContour && !prevSameContour) {
                    remove_node(currEdge, &head);
                    currEdge = currNextEdge;
                    --offsetVertexCount;
                    continue;
                } else if (prevSameContour && !currSameContour) {
                    remove_node(prevEdge, &head);
                    prevEdge = prevPrevEdge;
                    --offsetVertexCount;
                    continue;
                }
            }
 
            // otherwise minimize collision distance along segment
            if (dist0 < dist1) {
                remove_node(prevEdge, &head);
                prevEdge = prevPrevEdge;
            } else {
                remove_node(currEdge, &head);
                currEdge = currNextEdge;
            }
            --offsetVertexCount;
        }
    }
 
    // store all the valid intersections that aren't nearly coincident
    // TODO: look at the main algorithm and see if we can detect these better
    offsetPolygon->reset();
    if (!head || offsetVertexCount == 0 ||
        offsetVertexCount >= std::numeric_limits<uint16_t>::max()) {
        return false;
    }
 
    static constexpr SkScalar kCleanupTolerance = 0.01f;
    offsetPolygon->reserve(offsetVertexCount);
    int currIndex = 0;
    *offsetPolygon->append() = head->fIntersection;
    if (polygonIndices) {
        *polygonIndices->append() = head->fIndex;
    }
    currEdge = head->fNext;
    while (currEdge != head) {
        if (!SkPointPriv::EqualsWithinTolerance(currEdge->fIntersection,
                                                (*offsetPolygon)[currIndex],
                                                kCleanupTolerance)) {
            *offsetPolygon->append() = currEdge->fIntersection;
            if (polygonIndices) {
                *polygonIndices->append() = currEdge->fIndex;
            }
            currIndex++;
        }
        currEdge = currEdge->fNext;
    }
    // make sure the first and last points aren't coincident
    if (currIndex >= 1 &&
        SkPointPriv::EqualsWithinTolerance((*offsetPolygon)[0], (*offsetPolygon)[currIndex],
                                            kCleanupTolerance)) {
        offsetPolygon->pop_back();
        if (polygonIndices) {
            polygonIndices->pop_back();
        }
    }
 
    // check winding of offset polygon (it should be same as the original polygon)
    SkScalar offsetWinding = SkGetPolygonWinding(offsetPolygon->begin(), offsetPolygon->size());
 
    return (winding*offsetWinding > 0 &&
            SkIsSimplePolygon(offsetPolygon->begin(), offsetPolygon->size()));
}

SkTriangulateSimplePolygon()

bool SkTriangulateSimplePolygon	(	const SkPoint *	polygonVerts,
		uint16_t *	indexMap,
		int	polygonSize,
		SkTDArray< uint16_t > *	triangleIndices
	)

Compute indices to triangulate the given polygon. The input polygon must be simple (i.e. it is not self-intersecting) and have no coincident vertices or collinear edges.

Parameters

polygonVerts	Array of points representing the vertices of the polygon.
indexMap	Mapping from index in the given array to the final index in the triangulation.
polygonSize	Number of vertices in the polygon.
triangleIndices	Indices of the resulting triangulation.

Returns

true if successful, false otherwise.

Definition at line 1632 of file SkPolyUtils.cpp.

                                                                      {
    if (polygonSize < 3) {
        return false;
    }
    // need to be able to represent all the vertices in the 16-bit indices
    if (polygonSize >= std::numeric_limits<uint16_t>::max()) {
        return false;
    }
 
    // get bounds
    SkRect bounds;
    if (!bounds.setBoundsCheck(polygonVerts, polygonSize)) {
        return false;
    }
    // get winding direction
    // TODO: we do this for all the polygon routines -- might be better to have the client
    // compute it and pass it in
    int winding = SkGetPolygonWinding(polygonVerts, polygonSize);
    if (0 == winding) {
        return false;
    }
 
    // Set up vertices
    AutoSTArray<64, TriangulationVertex> triangulationVertices(polygonSize);
    int prevIndex = polygonSize - 1;
    SkVector v0 = polygonVerts[0] - polygonVerts[prevIndex];
    for (int currIndex = 0; currIndex < polygonSize; ++currIndex) {
        int nextIndex = (currIndex + 1) % polygonSize;
 
        triangulationVertices[currIndex] = TriangulationVertex{};
        triangulationVertices[currIndex].fPosition = polygonVerts[currIndex];
        triangulationVertices[currIndex].fIndex = currIndex;
        triangulationVertices[currIndex].fPrevIndex = prevIndex;
        triangulationVertices[currIndex].fNextIndex = nextIndex;
        SkVector v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
        if (winding*v0.cross(v1) > SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
            triangulationVertices[currIndex].fVertexType = TriangulationVertex::VertexType::kConvex;
        } else {
            triangulationVertices[currIndex].fVertexType = TriangulationVertex::VertexType::kReflex;
        }
 
        prevIndex = currIndex;
        v0 = v1;
    }
 
    // Classify initial vertices into a list of convex vertices and a hash of reflex vertices
    // TODO: possibly sort the convexList in some way to get better triangles
    SkTInternalLList<TriangulationVertex> convexList;
    ReflexHash reflexHash;
    if (!reflexHash.init(bounds, polygonSize)) {
        return false;
    }
    prevIndex = polygonSize - 1;
    for (int currIndex = 0; currIndex < polygonSize; prevIndex = currIndex, ++currIndex) {
        TriangulationVertex::VertexType currType = triangulationVertices[currIndex].fVertexType;
        if (TriangulationVertex::VertexType::kConvex == currType) {
            int nextIndex = (currIndex + 1) % polygonSize;
            TriangulationVertex::VertexType prevType = triangulationVertices[prevIndex].fVertexType;
            TriangulationVertex::VertexType nextType = triangulationVertices[nextIndex].fVertexType;
            // We prioritize clipping vertices with neighboring reflex vertices.
            // The intent here is that it will cull reflex vertices more quickly.
            if (TriangulationVertex::VertexType::kReflex == prevType ||
                TriangulationVertex::VertexType::kReflex == nextType) {
                convexList.addToHead(&triangulationVertices[currIndex]);
            } else {
                convexList.addToTail(&triangulationVertices[currIndex]);
            }
        } else {
            // We treat near collinear vertices as reflex
            reflexHash.add(&triangulationVertices[currIndex]);
        }
    }
 
    // The general concept: We are trying to find three neighboring vertices where
    // no other vertex lies inside the triangle (an "ear"). If we find one, we clip
    // that ear off, and then repeat on the new polygon. Once we get down to three vertices
    // we have triangulated the entire polygon.
    // In the worst case this is an n^2 algorithm. We can cut down the search space somewhat by
    // noting that only convex vertices can be potential ears, and we only need to check whether
    // any reflex vertices lie inside the ear.
    triangleIndices->reserve(triangleIndices->size() + 3 * (polygonSize - 2));
    int vertexCount = polygonSize;
    while (vertexCount > 3) {
        bool success = false;
        TriangulationVertex* earVertex = nullptr;
        TriangulationVertex* p0 = nullptr;
        TriangulationVertex* p2 = nullptr;
        // find a convex vertex to clip
        for (SkTInternalLList<TriangulationVertex>::Iter convexIter = convexList.begin();
             convexIter != convexList.end(); ++convexIter) {
            earVertex = *convexIter;
            SkASSERT(TriangulationVertex::VertexType::kReflex != earVertex->fVertexType);
 
            p0 = &triangulationVertices[earVertex->fPrevIndex];
            p2 = &triangulationVertices[earVertex->fNextIndex];
 
            // see if any reflex vertices are inside the ear
            bool failed = reflexHash.checkTriangle(p0->fPosition, earVertex->fPosition,
                                                   p2->fPosition, p0->fIndex, p2->fIndex);
            if (failed) {
                continue;
            }
 
            // found one we can clip
            success = true;
            break;
        }
        // If we can't find any ears to clip, this probably isn't a simple polygon
        if (!success) {
            return false;
        }
 
        // add indices
        auto indices = triangleIndices->append(3);
        indices[0] = indexMap[p0->fIndex];
        indices[1] = indexMap[earVertex->fIndex];
        indices[2] = indexMap[p2->fIndex];
 
        // clip the ear
        convexList.remove(earVertex);
        --vertexCount;
 
        // reclassify reflex verts
        p0->fNextIndex = earVertex->fNextIndex;
        reclassify_vertex(p0, polygonVerts, winding, &reflexHash, &convexList);
 
        p2->fPrevIndex = earVertex->fPrevIndex;
        reclassify_vertex(p2, polygonVerts, winding, &reflexHash, &convexList);
    }
 
    // output indices
    for (SkTInternalLList<TriangulationVertex>::Iter vertexIter = convexList.begin();
         vertexIter != convexList.end(); ++vertexIter) {
        TriangulationVertex* vertex = *vertexIter;
        *triangleIndices->append() = indexMap[vertex->fIndex];
    }
 
    return true;
}

zero_length()

static bool zero_length ( const SkPoint &  v, SkScalar  vdotv  )

inlinestatic

Definition at line 97 of file SkPolyUtils.cpp.

                                                                 {
    return !(SkIsFinite(v.fX, v.fY) && vdotv);
}

Variable Documentation

kCrossTolerance

constexpr SkScalar kCrossTolerance = SK_ScalarNearlyZero * SK_ScalarNearlyZero

constexpr

Definition at line 41 of file SkPolyUtils.cpp.