GrTriangulator::Edge Struct Reference

#include <GrTriangulator.h>

Public Member Functions
	Edge (Vertex *top, Vertex *bottom, int winding, EdgeType type)
double	dist (const SkPoint &p) const
bool	isRightOf (const Vertex &v) const
bool	isLeftOf (const Vertex &v) const
void	recompute ()
void	insertAbove (Vertex *, const Comparator &)
void	insertBelow (Vertex *, const Comparator &)
void	disconnect ()
bool	intersect (const Edge &other, SkPoint *p, uint8_t *alpha=nullptr) const

Public Attributes
int	fWinding
Vertex *	fTop
Vertex *	fBottom
EdgeType	fType
Edge *	fLeft
Edge *	fRight
Edge *	fPrevEdgeAbove
Edge *	fNextEdgeAbove
Edge *	fPrevEdgeBelow
Edge *	fNextEdgeBelow
Poly *	fLeftPoly
Poly *	fRightPoly
Edge *	fLeftPolyPrev
Edge *	fLeftPolyNext
Edge *	fRightPolyPrev
Edge *	fRightPolyNext
bool	fUsedInLeftPoly
bool	fUsedInRightPoly
Line	fLine

Detailed Description

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).

Definition at line 406 of file GrTriangulator.h.

Constructor & Destructor Documentation

Edge()

GrTriangulator::Edge::Edge ( Vertex *  top, Vertex *  bottom, int  winding, EdgeType  type  )

inline

Definition at line 407 of file GrTriangulator.h.

        : fWinding(winding)
        , fTop(top)
        , fBottom(bottom)
        , fType(type)
        , fLeft(nullptr)
        , fRight(nullptr)
        , fPrevEdgeAbove(nullptr)
        , fNextEdgeAbove(nullptr)
        , fPrevEdgeBelow(nullptr)
        , fNextEdgeBelow(nullptr)
        , fLeftPoly(nullptr)
        , fRightPoly(nullptr)
        , fLeftPolyPrev(nullptr)
        , fLeftPolyNext(nullptr)
        , fRightPolyPrev(nullptr)
        , fRightPolyNext(nullptr)
        , fUsedInLeftPoly(false)
        , fUsedInRightPoly(false)
        , fLine(top, bottom) {
        }

Member Function Documentation

disconnect()

void GrTriangulator::Edge::disconnect

(

)

Definition at line 740 of file GrTriangulator.cpp.

                                    {
    remove_edge_above(this);
    remove_edge_below(this);
}

dist()

double GrTriangulator::Edge::dist ( const SkPoint &  p ) const

inline

Definition at line 448 of file GrTriangulator.h.

                                        {
        // Coerce points coincident with the vertices to have dist = 0, since converting from
        // a double intersection point back to float storage might construct a point that's no
        // longer on the ideal line.
        return (p == fTop->fPoint || p == fBottom->fPoint) ? 0.0 : fLine.dist(p);
    }

insertAbove()

void GrTriangulator::Edge::insertAbove	(	Vertex *	v,
		const Comparator &	c
	)

Definition at line 688 of file GrTriangulator.cpp.

                                                                   {
    if (fTop->fPoint == fBottom->fPoint ||
        c.sweep_lt(fBottom->fPoint, fTop->fPoint)) {
        return;
    }
    TESS_LOG("insert edge (%g -> %g) above vertex %g\n", fTop->fID, fBottom->fID, v->fID);
    Edge* prev = nullptr;
    Edge* next;
    for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) {
        if (next->isRightOf(*fTop)) {
            break;
        }
        prev = next;
    }
    list_insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
        this, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
}

insertBelow()

void GrTriangulator::Edge::insertBelow	(	Vertex *	v,
		const Comparator &	c
	)

Definition at line 706 of file GrTriangulator.cpp.

                                                                   {
    if (fTop->fPoint == fBottom->fPoint ||
        c.sweep_lt(fBottom->fPoint, fTop->fPoint)) {
        return;
    }
    TESS_LOG("insert edge (%g -> %g) below vertex %g\n", fTop->fID, fBottom->fID, v->fID);
    Edge* prev = nullptr;
    Edge* next;
    for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) {
        if (next->isRightOf(*fBottom)) {
            break;
        }
        prev = next;
    }
    list_insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
        this, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);
}

intersect()

bool GrTriangulator::Edge::intersect	(	const Edge &	other,
		SkPoint *	p,
		uint8_t *	alpha = nullptr
	)		const

Definition at line 265 of file GrTriangulator.cpp.

                                                                                      {
    TESS_LOG("intersecting %g -> %g with %g -> %g\n",
             fTop->fID, fBottom->fID, other.fTop->fID, other.fBottom->fID);
    if (fTop == other.fTop || fBottom == other.fBottom ||
        fTop == other.fBottom || fBottom == other.fTop) {
        // If the two edges share a vertex by construction, they have already been split and
        // shouldn't be considered "intersecting" anymore.
        return false;
    }
 
    double s, t; // needed to interpolate vertex alpha
    const bool intersects = recursive_edge_intersect(
            fLine, fTop->fPoint, fBottom->fPoint,
            other.fLine, other.fTop->fPoint, other.fBottom->fPoint,
            p, &s, &t);
    if (!intersects) {
        return false;
    }
 
    if (alpha) {
        if (fType == EdgeType::kInner || other.fType == EdgeType::kInner) {
            // If the intersection is on any interior edge, it needs to stay fully opaque or later
            // triangulation could leech transparency into the inner fill region.
            *alpha = 255;
        } else if (fType == EdgeType::kOuter && other.fType == EdgeType::kOuter) {
            // Trivially, the intersection will be fully transparent since since it is by
            // construction on the outer edge.
            *alpha = 0;
        } else {
            // Could be two connectors crossing, or a connector crossing an outer edge.
            // Take the max interpolated alpha
            SkASSERT(fType == EdgeType::kConnector || other.fType == EdgeType::kConnector);
            *alpha = std::max((1.0 - s) * fTop->fAlpha + s * fBottom->fAlpha,
                              (1.0 - t) * other.fTop->fAlpha + t * other.fBottom->fAlpha);
        }
    }
    return true;
}

isLeftOf()

bool GrTriangulator::Edge::isLeftOf ( const Vertex &  v ) const

inline

Definition at line 455 of file GrTriangulator.h.

{ return this->dist(v.fPoint) > 0.0; }

isRightOf()

bool GrTriangulator::Edge::isRightOf ( const Vertex &  v ) const

inline

Definition at line 454 of file GrTriangulator.h.

{ return this->dist(v.fPoint) < 0.0; }

recompute()

void GrTriangulator::Edge::recompute ( )

inline

Definition at line 456 of file GrTriangulator.h.

{ fLine = Line(fTop, fBottom); }

Member Data Documentation

fBottom

Vertex* GrTriangulator::Edge::fBottom

Definition at line 430 of file GrTriangulator.h.

fLeft

Edge* GrTriangulator::Edge::fLeft

Definition at line 432 of file GrTriangulator.h.

fLeftPoly

Poly* GrTriangulator::Edge::fLeftPoly

Definition at line 438 of file GrTriangulator.h.

fLeftPolyNext

Edge* GrTriangulator::Edge::fLeftPolyNext

Definition at line 441 of file GrTriangulator.h.

fLeftPolyPrev

Edge* GrTriangulator::Edge::fLeftPolyPrev

Definition at line 440 of file GrTriangulator.h.

fLine

Line GrTriangulator::Edge::fLine

Definition at line 446 of file GrTriangulator.h.

fNextEdgeAbove

Edge* GrTriangulator::Edge::fNextEdgeAbove

Definition at line 435 of file GrTriangulator.h.

fNextEdgeBelow

Edge* GrTriangulator::Edge::fNextEdgeBelow

Definition at line 437 of file GrTriangulator.h.

fPrevEdgeAbove

Edge* GrTriangulator::Edge::fPrevEdgeAbove

Definition at line 434 of file GrTriangulator.h.

fPrevEdgeBelow

Edge* GrTriangulator::Edge::fPrevEdgeBelow

Definition at line 436 of file GrTriangulator.h.

fRight

Edge* GrTriangulator::Edge::fRight

Definition at line 433 of file GrTriangulator.h.

fRightPoly

Poly* GrTriangulator::Edge::fRightPoly

Definition at line 439 of file GrTriangulator.h.

fRightPolyNext

Edge* GrTriangulator::Edge::fRightPolyNext

Definition at line 443 of file GrTriangulator.h.

fRightPolyPrev

Edge* GrTriangulator::Edge::fRightPolyPrev

Definition at line 442 of file GrTriangulator.h.

fTop

Vertex* GrTriangulator::Edge::fTop

Definition at line 429 of file GrTriangulator.h.

fType

EdgeType GrTriangulator::Edge::fType

Definition at line 431 of file GrTriangulator.h.

fUsedInLeftPoly

bool GrTriangulator::Edge::fUsedInLeftPoly

Definition at line 444 of file GrTriangulator.h.

fUsedInRightPoly

bool GrTriangulator::Edge::fUsedInRightPoly

Definition at line 445 of file GrTriangulator.h.

fWinding

int GrTriangulator::Edge::fWinding

Definition at line 428 of file GrTriangulator.h.

---

The documentation for this struct was generated from the following files:

• third_party/skia/src/gpu/ganesh/geometry/GrTriangulator.h
• third_party/skia/src/gpu/ganesh/geometry/GrTriangulator.cpp