/* * Copyright 2015 Google Inc. * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #ifndef GrTriangulator_DEFINED #define GrTriangulator_DEFINED #if !defined(SK_ENABLE_OPTIMIZE_SIZE) #include "include/core/SkPath.h" #include "include/core/SkPoint.h" #include "include/core/SkScalar.h" #include "include/private/base/SkAssert.h" #include "src/base/SkArenaAlloc.h" #include "src/gpu/BufferWriter.h" #include <algorithm> #include <cmath> #include <cstdint> #include <tuple> class GrEagerVertexAllocator; enum class SkPathFillType; struct SkRect; #define TRIANGULATOR_LOGGING … #define TRIANGULATOR_WIREFRAME … /** * Provides utility functions for converting paths to a collection of triangles. */ class GrTriangulator { … }; /** * Vertices are used in three ways: first, the path contours are converted into a * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since * an individual Vertex from the path mesh may belong to multiple * MonotonePolys, so the original Vertices cannot be re-used. */ struct GrTriangulator::Vertex { … }; struct GrTriangulator::VertexList { … }; // A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line. struct GrTriangulator::Line { … }; /** * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf(). * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating * point). For speed, that case is only tested by the callers that require it (e.g., * rewind_if_necessary()). Edges also handle checking for intersection with other edges. * Currently, this converts the edges to the parametric form, in order to avoid doing a division * until an intersection has been confirmed. This is slightly slower in the "found" case, but * a lot faster in the "not found" case. * * The coefficients of the line equation stored in double precision to avoid catastrophic * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is * correct in float, since it's a polynomial of degree 2. The intersect() function, being * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of * this file). */ struct GrTriangulator::Edge { … }; struct GrTriangulator::EdgeList { … }; struct GrTriangulator::MonotonePoly { … }; struct GrTriangulator::Poly { … }; struct GrTriangulator::Comparator { … }; #endif // SK_ENABLE_OPTIMIZE_SIZE #endif // GrTriangulator_DEFINED
Codebase Browser
chromium