SkPolyUtils.cpp | Explore in Territory

/*
 * Copyright 2017 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#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>

usingnamespaceskia_private;

#if !defined(SK_ENABLE_OPTIMIZE_SIZE)

//////////////////////////////////////////////////////////////////////////////////
// Helper data structures and functions

struct OffsetSegment { … };

constexpr SkScalar kCrossTolerance = …;

// Computes perpDot for point p compared to segment defined by origin p0 and vector v.
// A positive value means the point is to the left of the segment,
// negative is to the right, 0 is collinear.
static int compute_side(const SkPoint& p0, const SkVector& v, const SkPoint& p) { … }

// Returns 1 for cw, -1 for ccw and 0 if zero signed area (either degenerate or self-intersecting)
int SkGetPolygonWinding(const SkPoint* polygonVerts, int polygonSize) { … }

// Compute difference vector to offset p0-p1 'offset' units in direction specified by 'side'
bool compute_offset_vector(const SkPoint& p0, const SkPoint& p1, SkScalar offset, int side,
                           SkPoint* vector) { … }

// check interval to see if intersection is in segment
static inline bool outside_interval(SkScalar numer, SkScalar denom, bool denomPositive) { … }

// special zero-length test when we're using vdotv as a denominator
static inline bool zero_length(const SkPoint& v, SkScalar vdotv) { … }

// Compute the intersection 'p' between segments s0 and s1, if any.
// 's' is the parametric value for the intersection along 's0' & 't' is the same for 's1'.
// Returns false if there is no intersection.
// If the length squared of a segment is 0, then we treat the segment as degenerate
// and use only the first endpoint for tests.
static bool compute_intersection(const OffsetSegment& s0, const OffsetSegment& s1,
                                 SkPoint* p, SkScalar* s, SkScalar* t) { … }

bool SkIsConvexPolygon(const SkPoint* polygonVerts, int polygonSize) { … }

struct OffsetEdge { … };

static void remove_node(const OffsetEdge* node, OffsetEdge** head) { … }

//////////////////////////////////////////////////////////////////////////////////

// The objective here is to inset all of the edges by the given distance, and then
// remove any invalid inset edges by detecting right-hand turns. In a ccw polygon,
// we should only be making left-hand turns (for cw polygons, we use the winding
// parameter to reverse this). We detect this by checking whether the second intersection
// on an edge is closer to its tail than the first one.
//
// We might also have the case that there is no intersection between two neighboring inset edges.
// In this case, one edge will lie to the right of the other and should be discarded along with
// its previous intersection (if any).
//
// Note: the assumption is that inputPolygon is convex and has no coincident points.
//
bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
                          SkScalar inset, SkTDArray<SkPoint>* insetPolygon) { … }

///////////////////////////////////////////////////////////////////////////////////////////

// compute the number of points needed for a circular join when offsetting a reflex vertex
bool SkComputeRadialSteps(const SkVector& v1, const SkVector& v2, SkScalar offset,
                          SkScalar* rotSin, SkScalar* rotCos, int* n) { … }

///////////////////////////////////////////////////////////////////////////////////////////

// a point is "left" to another if its x-coord is less, or if equal, its y-coord is greater
static bool left(const SkPoint& p0, const SkPoint& p1) { … }

// a point is "right" to another if its x-coord is greater, or if equal, its y-coord is less
static bool right(const SkPoint& p0, const SkPoint& p1) { … }

struct Vertex { … };

enum VertexFlags { … };

struct ActiveEdge { … };

class ActiveEdgeList { … };

// Here we implement a sweep line algorithm to determine whether the provided points
// represent a simple polygon, i.e., the polygon is non-self-intersecting.
// We first insert the vertices into a priority queue sorting horizontally from left to right.
// Then as we pop the vertices from the queue we generate events which indicate that an edge
// should be added or removed from an edge list. If any intersections are detected in the edge
// list, then we know the polygon is self-intersecting and hence not simple.
bool SkIsSimplePolygon(const SkPoint* polygon, int polygonSize) { … }

///////////////////////////////////////////////////////////////////////////////////////////

// helper function for SkOffsetSimplePolygon
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) { … }

//////////////////////////////////////////////////////////////////////////////////////////

struct TriangulationVertex { … };

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

// test to see if point p is in triangle p0p1p2.
// for now assuming strictly inside -- if on the edge it's outside
static bool point_in_triangle(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
                              const SkPoint& p) { … }

// Data structure to track reflex vertices and check whether any are inside a given triangle
class ReflexHash { … };

// Check to see if a reflex vertex has become a convex vertex after clipping an ear
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) { … }

#endif // !defined(SK_ENABLE_OPTIMIZE_SIZE)
chromium/third_party/skia/src/utils/SkPolyUtils.cpp
