GrTessellator: refactor Line out of Edge.

src/gpu/GrTessellator.cpp

 /*
  * 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 "GrTessellator.h"
 
 #include "GrDefaultGeoProcFactory.h"
@@ skipping 242 matching lines @@
     }
 };
 
 // Round to nearest quarter-pixel. This is used for screenspace tessellation.
 
 inline void round(SkPoint* p) {
     p->fX = SkScalarRoundToScalar(p->fX * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f);
     p->fY = SkScalarRoundToScalar(p->fY * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f);
 }
 
+// A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line.
+struct Line {
+    Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {}
+    Line(const SkPoint& p, const SkPoint& q)
+        : fA(static_cast<double>(q.fY) - p.fY)      // a = dY
+        , fB(static_cast<double>(p.fX) - q.fX)      // b = -dX
+        , fC(static_cast<double>(p.fY) * q.fX -     // c = cross(q, p)
+             static_cast<double>(p.fX) * q.fY) {}
+    double dist(const SkPoint& p) const {
+        return fA * p.fX + fB * p.fY + fC;
+    }
+    double magSq() const {
+        return fA * fA + fB * fB;
+    }
+    double fA, fB, fC;
+};
+
 /**
  * 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 which require it (e.g.,
  * cleanup_active_edges()). 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.
  *
@@ skipping 16 matching lines @@
         , fNextEdgeAbove(nullptr)
         , fPrevEdgeBelow(nullptr)
         , fNextEdgeBelow(nullptr)
         , fLeftPoly(nullptr)
         , fRightPoly(nullptr)
         , fLeftPolyPrev(nullptr)
         , fLeftPolyNext(nullptr)
         , fRightPolyPrev(nullptr)
         , fRightPolyNext(nullptr)
         , fUsedInLeftPoly(false)
-        , fUsedInRightPoly(false) {
-            recompute();
+        , fUsedInRightPoly(false)
+        , fLine(top, bottom) {
         }
     int      fWinding;          // 1 == edge goes downward; -1 = edge goes upward.
     Vertex*  fTop;              // The top vertex in vertex-sort-order (sweep_lt).
     Vertex*  fBottom;           // The bottom vertex in vertex-sort-order.
     Edge*    fLeft;             // The linked list of edges in the active edge list.
     Edge*    fRight;            // "
     Edge*    fPrevEdgeAbove;    // The linked list of edges in the bottom Vertex's "edges above".
     Edge*    fNextEdgeAbove;    // "
     Edge*    fPrevEdgeBelow;    // The linked list of edges in the top Vertex's "edges below".
     Edge*    fNextEdgeBelow;    // "
     Poly*    fLeftPoly;         // The Poly to the left of this edge, if any.
     Poly*    fRightPoly;        // The Poly to the right of this edge, if any.
     Edge*    fLeftPolyPrev;
     Edge*    fLeftPolyNext;
     Edge*    fRightPolyPrev;
     Edge*    fRightPolyNext;
     bool     fUsedInLeftPoly;
     bool     fUsedInRightPoly;
-    double   fDX;               // The line equation for this edge, in implicit form.
-    double   fDY;               // fDY * x + fDX * y + fC = 0, for point (x, y) on the line.
-    double   fC;
+    Line     fLine;
     double dist(const SkPoint& p) const {
-        return fDY * p.fX - fDX * p.fY + fC;
+        return fLine.dist(p);
     }
     bool isRightOf(Vertex* v) const {
-        return dist(v->fPoint) < 0.0;
+        return fLine.dist(v->fPoint) < 0.0;
     }
     bool isLeftOf(Vertex* v) const {
-        return dist(v->fPoint) > 0.0;
+        return fLine.dist(v->fPoint) > 0.0;
     }
     void recompute() {
-        fDX = static_cast<double>(fBottom->fPoint.fX) - fTop->fPoint.fX;
-        fDY = static_cast<double>(fBottom->fPoint.fY) - fTop->fPoint.fY;
-        fC = static_cast<double>(fTop->fPoint.fY) * fBottom->fPoint.fX -
-             static_cast<double>(fTop->fPoint.fX) * fBottom->fPoint.fY;
+        fLine = Line(fTop, fBottom);
     }
     bool intersect(const Edge& other, SkPoint* p) {
         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) {
             return false;
         }
-        double denom = fDX * other.fDY - fDY * other.fDX;
+        double denom = fLine.fA * other.fLine.fB - fLine.fB * other.fLine.fA;
         if (denom == 0.0) {
             return false;
         }
         double dx = static_cast<double>(fTop->fPoint.fX) - other.fTop->fPoint.fX;
         double dy = static_cast<double>(fTop->fPoint.fY) - other.fTop->fPoint.fY;
-        double sNumer = dy * other.fDX - dx * other.fDY;
-        double tNumer = dy * fDX - dx * fDY;
+        double sNumer = -dy * other.fLine.fB - dx * other.fLine.fA;
+        double tNumer = -dy * fLine.fB - dx * fLine.fA;
         // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early.
         // This saves us doing the divide below unless absolutely necessary.
         if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNumer > denom)
                         : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNumer < denom)) {
             return false;
         }
         double s = sNumer / denom;
         SkASSERT(s >= 0.0 && s <= 1.0);
-        p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX);
-        p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY);
+        p->fX = SkDoubleToScalar(fTop->fPoint.fX - s * fLine.fB);
+        p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fLine.fA);
         return true;
     }
 };
 
 struct EdgeList {
     EdgeList() : fHead(nullptr), fTail(nullptr), fNext(nullptr), fCount(0) {}
     Edge* fHead;
     Edge* fTail;
     EdgeList* fNext;
     int fCount;
@@ skipping 1044 matching lines @@
             if (!is_boundary_edge(e, fillType)) {
                 remove_edge_above(e);
                 remove_edge_below(e);
             }
             e = next;
         }
     }
     return vertices;
 }
 
 // This is different from Edge::intersect, in that it intersects lines, not line segments.

[robertphillips, 2016/10/07 13:30:58]

Should this somehow be associated more explicitly with the Line class ? 

[Stephen White, 2016/10/07 15:03:20]

Done.

-bool intersect(const Edge& a, const Edge& b, SkPoint* point) {
-    double denom = a.fDX * b.fDY - a.fDY * b.fDX;
+bool intersect(const Line& a, const Line& b, SkPoint* point) {
+    double denom = a.fA * b.fB - a.fB * b.fA;
     if (denom == 0.0) {
         return false;
     }
     double scale = 1.0f / denom;
-    point->fX = SkDoubleToScalar((b.fDX * a.fC - a.fDX * b.fC) * scale);
-    point->fY = SkDoubleToScalar((b.fDY * a.fC - a.fDY * b.fC) * scale);
+    point->fX = SkDoubleToScalar((a.fB * b.fC - b.fB * a.fC) * scale);
+    point->fY = SkDoubleToScalar((b.fA * a.fC - a.fA * b.fC) * scale);
     round(point);
     return true;
 }
 
 void get_edge_normal(const Edge* e, SkVector* normal) {
-    normal->setNormalize(SkDoubleToScalar(e->fDX) * e->fWinding,
-                         SkDoubleToScalar(e->fDY) * e->fWinding);
+    normal->setNormalize(SkDoubleToScalar(-e->fLine.fB) * e->fWinding,
+                         SkDoubleToScalar(e->fLine.fA) * e->fWinding);
 }
 
 // Stage 5c: detect and remove "pointy" vertices whose edge normals point in opposite directions
 // and whose adjacent vertices are less than a quarter pixel from an edge. These are guaranteed to
 // invert on stroking.
 
 void simplify_boundary(EdgeList* boundary, Comparator& c, SkChunkAlloc& alloc) {
     Edge* prevEdge = boundary->fTail;
     SkVector prevNormal;
     get_edge_normal(prevEdge, &prevNormal);
     for (Edge* e = boundary->fHead; e != nullptr;) {
         Vertex* prev = prevEdge->fWinding == 1 ? prevEdge->fTop : prevEdge->fBottom;
         Vertex* next = e->fWinding == 1 ? e->fBottom : e->fTop;
         double dist = e->dist(prev->fPoint);
         SkVector normal;
         get_edge_normal(e, &normal);
-        float denom = 0.25f * static_cast<float>(e->fDX * e->fDX + e->fDY * e->fDY);
+        float denom = 0.25f * static_cast<float>(e->fLine.magSq());
         if (prevNormal.dot(normal) < 0.0 && (dist * dist) <= denom) {
             Edge* join = new_edge(prev, next, alloc, c);
             insert_edge(join, e, boundary);
             remove_edge(prevEdge, boundary);
             remove_edge(e, boundary);
             if (join->fLeft && join->fRight) {
                 prevEdge = join->fLeft;
                 e = join;
             } else {
                 prevEdge = boundary->fTail;
                 e = boundary->fHead; // join->fLeft ? join->fLeft : join;
             }
             get_edge_normal(prevEdge, &prevNormal);
         } else {
             prevEdge = e;
             prevNormal = normal;
             e = e->fRight;
         }
     }
 }
 
 // Stage 5d: Displace edges by half a pixel inward and outward along their normals. Intersect to
 // find new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a
 // new antialiased mesh from those vertices.
 
 void boundary_to_aa_mesh(EdgeList* boundary, VertexList* mesh, Comparator& c, SkChunkAlloc& alloc) {
     EdgeList outerContour;
     Edge* prevEdge = boundary->fTail;
     float radius = 0.5f;
-    double offset = radius * sqrt(prevEdge->fDX * prevEdge->fDX + prevEdge->fDY * prevEdge->fDY)
-                           * prevEdge->fWinding;
-    Edge prevInner(prevEdge->fTop, prevEdge->fBottom, prevEdge->fWinding);
+    double offset = radius * sqrt(prevEdge->fLine.magSq()) * prevEdge->fWinding;
+    Line prevInner(prevEdge->fTop, prevEdge->fBottom);
     prevInner.fC -= offset;
-    Edge prevOuter(prevEdge->fTop, prevEdge->fBottom, prevEdge->fWinding);
+    Line prevOuter(prevEdge->fTop, prevEdge->fBottom);
     prevOuter.fC += offset;
     VertexList innerVertices;
     VertexList outerVertices;
     SkScalar innerCount = SK_Scalar1, outerCount = SK_Scalar1;
     for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) {
-        double offset = radius * sqrt(e->fDX * e->fDX + e->fDY * e->fDY) * e->fWinding;
-        Edge inner(e->fTop, e->fBottom, e->fWinding);
+        double offset = radius * sqrt(e->fLine.magSq()) * e->fWinding;
+        Line inner(e->fTop, e->fBottom);
         inner.fC -= offset;
-        Edge outer(e->fTop, e->fBottom, e->fWinding);
+        Line outer(e->fTop, e->fBottom);
         outer.fC += offset;
         SkPoint innerPoint, outerPoint;
         if (intersect(prevInner, inner, &innerPoint) &&
             intersect(prevOuter, outer, &outerPoint)) {
             Vertex* innerVertex = ALLOC_NEW(Vertex, (innerPoint, 255), alloc);
             Vertex* outerVertex = ALLOC_NEW(Vertex, (outerPoint, 0), alloc);
             if (innerVertices.fTail && outerVertices.fTail) {
                 Edge innerEdge(innerVertices.fTail, innerVertex, 1);
                 Edge outerEdge(outerVertices.fTail, outerVertex, 1);
                 SkVector innerNormal;
@@ skipping 292 matching lines @@
         }
     }
     int actualCount = static_cast<int>(vertsEnd - *verts);
     SkASSERT(actualCount <= count);
     SkASSERT(pointsEnd - points == actualCount);
     delete[] points;
     return actualCount;
 }
 
 } // namespace