GrAAConvexTessellator.cpp | Explore in Territory

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

#include "src/gpu/ganesh/geometry/GrAAConvexTessellator.h"

#include "include/core/SkMatrix.h"
#include "include/core/SkPath.h"
#include "include/core/SkPoint.h"
#include "include/core/SkRect.h"
#include "include/private/base/SkAssert.h"
#include "include/private/base/SkFloatingPoint.h"
#include "include/private/base/SkTPin.h"
#include "src/core/SkPathPriv.h"
#include "src/gpu/ganesh/geometry/GrPathUtils.h"

#include <algorithm>

// Next steps:
//  add an interactive sample app slide
//  add debug check that all points are suitably far apart
//  test more degenerate cases

// The tolerance for fusing vertices and eliminating colinear lines (It is in device space).
static constexpr SkScalar kClose = …;
static constexpr SkScalar kCloseSqd = …;

// tesselation tolerance values, in device space pixels
static constexpr SkScalar kQuadTolerance = …;
static constexpr SkScalar kCubicTolerance = …;
static constexpr SkScalar kQuadToleranceSqd = …;
static constexpr SkScalar kCubicToleranceSqd = …;
static constexpr SkScalar kConicTolerance = …;

// dot product below which we use a round cap between curve segments
static constexpr SkScalar kRoundCapThreshold = …;

// dot product above which we consider two adjacent curves to be part of the "same" curve
static constexpr SkScalar kCurveConnectionThreshold = …;

static bool intersect(const SkPoint& p0, const SkPoint& n0,
                      const SkPoint& p1, const SkPoint& n1,
                      SkScalar* t) { … }

// This is a special case version of intersect where we have the vector
// perpendicular to the second line rather than the vector parallel to it.
static bool perp_intersect(const SkPoint& p0, const SkPoint& n0,
                           const SkPoint& p1, const SkPoint& perp,
                           SkScalar* t) { … }

static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) { … }

static bool points_are_colinear_and_b_is_middle(const SkPoint& a, const SkPoint& b,
                                                const SkPoint& c, float* accumError) { … }

int GrAAConvexTessellator::addPt(const SkPoint& pt,
                                 SkScalar depth,
                                 SkScalar coverage,
                                 bool movable,
                                 CurveState curve) { … }

void GrAAConvexTessellator::popLastPt() { … }

void GrAAConvexTessellator::popFirstPtShuffle() { … }

void GrAAConvexTessellator::updatePt(int index,
                                     const SkPoint& pt,
                                     SkScalar depth,
                                     SkScalar coverage) { … }

void GrAAConvexTessellator::addTri(int i0, int i1, int i2) { … }

void GrAAConvexTessellator::rewind() { … }

void GrAAConvexTessellator::computeNormals() { … }

void GrAAConvexTessellator::computeBisectors() { … }

// Create as many rings as we need to (up to a predefined limit) to reach the specified target
// depth. If we are in fill mode, the final ring will automatically be fanned.
bool GrAAConvexTessellator::createInsetRings(Ring& previousRing, SkScalar initialDepth,
                                             SkScalar initialCoverage, SkScalar targetDepth,
                                             SkScalar targetCoverage, Ring** finalRing) { … }

// The general idea here is to, conceptually, start with the original polygon and slide
// the vertices along the bisectors until the first intersection. At that
// point two of the edges collapse and the process repeats on the new polygon.
// The polygon state is captured in the Ring class while the GrAAConvexTessellator
// controls the iteration. The CandidateVerts holds the formative points for the
// next ring.
bool GrAAConvexTessellator::tessellate(const SkMatrix& m, const SkPath& path) { … }

SkScalar GrAAConvexTessellator::computeDepthFromEdge(int edgeIdx, const SkPoint& p) const { … }

// Find a point that is 'desiredDepth' away from the 'edgeIdx'-th edge and lies
// along the 'bisector' from the 'startIdx'-th point.
bool GrAAConvexTessellator::computePtAlongBisector(int startIdx,
                                                   const SkVector& bisector,
                                                   int edgeIdx,
                                                   SkScalar desiredDepth,
                                                   SkPoint* result) const { … }

bool GrAAConvexTessellator::extractFromPath(const SkMatrix& m, const SkPath& path) { … }

GrAAConvexTessellator::Ring* GrAAConvexTessellator::getNextRing(Ring* lastRing) { … }

void GrAAConvexTessellator::fanRing(const Ring& ring) { … }

void GrAAConvexTessellator::createOuterRing(const Ring& previousRing, SkScalar outset,
                                            SkScalar coverage, Ring* nextRing) { … }

// Something went wrong in the creation of the next ring. If we're filling the shape, just go ahead
// and fan it.
void GrAAConvexTessellator::terminate(const Ring& ring) { … }

static SkScalar compute_coverage(SkScalar depth, SkScalar initialDepth, SkScalar initialCoverage,
                                SkScalar targetDepth, SkScalar targetCoverage) { … }

// return true when processing is complete
bool GrAAConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing,
                                            SkScalar initialDepth, SkScalar initialCoverage,
                                            SkScalar targetDepth, SkScalar targetCoverage,
                                            bool forceNew) { … }

void GrAAConvexTessellator::validate() const { … }

//////////////////////////////////////////////////////////////////////////////
void GrAAConvexTessellator::Ring::init(const GrAAConvexTessellator& tess) { … }

void GrAAConvexTessellator::Ring::init(const SkTDArray<SkVector>& norms,
                                       const SkTDArray<SkVector>& bisectors) { … }

// Compute the outward facing normal at each vertex.
void GrAAConvexTessellator::Ring::computeNormals(const GrAAConvexTessellator& tess) { … }

void GrAAConvexTessellator::Ring::computeBisectors(const GrAAConvexTessellator& tess) { … }

//////////////////////////////////////////////////////////////////////////////
#ifdef SK_DEBUG
// Is this ring convex?
bool GrAAConvexTessellator::Ring::isConvex(const GrAAConvexTessellator& tess) const { … }

#endif

void GrAAConvexTessellator::lineTo(const SkPoint& p, CurveState curve) { … }

void GrAAConvexTessellator::lineTo(const SkMatrix& m, const SkPoint& p, CurveState curve) { … }

void GrAAConvexTessellator::quadTo(const SkPoint pts[3]) { … }

void GrAAConvexTessellator::quadTo(const SkMatrix& m, const SkPoint srcPts[3]) { … }

void GrAAConvexTessellator::cubicTo(const SkMatrix& m, const SkPoint srcPts[4]) { … }

// include down here to avoid compilation errors caused by "-" overload in SkGeometry.h
#include "src/core/SkGeometry.h"

void GrAAConvexTessellator::conicTo(const SkMatrix& m, const SkPoint srcPts[3], SkScalar w) { … }

//////////////////////////////////////////////////////////////////////////////
#if GR_AA_CONVEX_TESSELLATOR_VIZ
static const SkScalar kPointRadius = 0.02f;
static const SkScalar kArrowStrokeWidth = 0.0f;
static const SkScalar kArrowLength = 0.2f;
static const SkScalar kEdgeTextSize = 0.1f;
static const SkScalar kPointTextSize = 0.02f;

static void draw_point(SkCanvas* canvas, const SkPoint& p, SkScalar paramValue, bool stroke) {
    SkPaint paint;
    SkASSERT(paramValue <= 1.0f);
    int gs = int(255*paramValue);
    paint.setARGB(255, gs, gs, gs);

    canvas->drawCircle(p.fX, p.fY, kPointRadius, paint);

    if (stroke) {
        SkPaint stroke;
        stroke.setColor(SK_ColorYELLOW);
        stroke.setStyle(SkPaint::kStroke_Style);
        stroke.setStrokeWidth(kPointRadius/3.0f);
        canvas->drawCircle(p.fX, p.fY, kPointRadius, stroke);
    }
}

static void draw_line(SkCanvas* canvas, const SkPoint& p0, const SkPoint& p1, SkColor color) {
    SkPaint p;
    p.setColor(color);

    canvas->drawLine(p0.fX, p0.fY, p1.fX, p1.fY, p);
}

static void draw_arrow(SkCanvas*canvas, const SkPoint& p, const SkPoint &n,
                       SkScalar len, SkColor color) {
    SkPaint paint;
    paint.setColor(color);
    paint.setStrokeWidth(kArrowStrokeWidth);
    paint.setStyle(SkPaint::kStroke_Style);

    canvas->drawLine(p.fX, p.fY,
                     p.fX + len * n.fX, p.fY + len * n.fY,
                     paint);
}

void GrAAConvexTessellator::Ring::draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const {
    SkPaint paint;
    paint.setTextSize(kEdgeTextSize);

    for (int cur = 0; cur < fPts.count(); ++cur) {
        int next = (cur + 1) % fPts.count();

        draw_line(canvas,
                  tess.point(fPts[cur].fIndex),
                  tess.point(fPts[next].fIndex),
                  SK_ColorGREEN);

        SkPoint mid = tess.point(fPts[cur].fIndex) + tess.point(fPts[next].fIndex);
        mid.scale(0.5f);

        if (fPts.count()) {
            draw_arrow(canvas, mid, fPts[cur].fNorm, kArrowLength, SK_ColorRED);
            mid.fX += (kArrowLength/2) * fPts[cur].fNorm.fX;
            mid.fY += (kArrowLength/2) * fPts[cur].fNorm.fY;
        }

        SkString num;
        num.printf("%d", this->origEdgeID(cur));
        canvas->drawString(num, mid.fX, mid.fY, paint);

        if (fPts.count()) {
            draw_arrow(canvas, tess.point(fPts[cur].fIndex), fPts[cur].fBisector,
                       kArrowLength, SK_ColorBLUE);
        }
    }
}

void GrAAConvexTessellator::draw(SkCanvas* canvas) const {
    for (int i = 0; i < fIndices.count(); i += 3) {
        SkASSERT(fIndices[i] < this->numPts()) ;
        SkASSERT(fIndices[i+1] < this->numPts()) ;
        SkASSERT(fIndices[i+2] < this->numPts()) ;

        draw_line(canvas,
                  this->point(this->fIndices[i]), this->point(this->fIndices[i+1]),
                  SK_ColorBLACK);
        draw_line(canvas,
                  this->point(this->fIndices[i+1]), this->point(this->fIndices[i+2]),
                  SK_ColorBLACK);
        draw_line(canvas,
                  this->point(this->fIndices[i+2]), this->point(this->fIndices[i]),
                  SK_ColorBLACK);
    }

    fInitialRing.draw(canvas, *this);
    for (int i = 0; i < fRings.count(); ++i) {
        fRings[i]->draw(canvas, *this);
    }

    for (int i = 0; i < this->numPts(); ++i) {
        draw_point(canvas,
                   this->point(i), 0.5f + (this->depth(i)/(2 * kAntialiasingRadius)),
                   !this->movable(i));

        SkPaint paint;
        paint.setTextSize(kPointTextSize);
        if (this->depth(i) <= -kAntialiasingRadius) {
            paint.setColor(SK_ColorWHITE);
        }

        SkString num;
        num.printf("%d", i);
        canvas->drawString(num,
                         this->point(i).fX, this->point(i).fY+(kPointRadius/2.0f),
                         paint);
    }
}

#endif
chromium/third_party/skia/src/gpu/ganesh/geometry/GrAAConvexTessellator.cpp
