combine vertical overlapping edges

src/core/SkEdgeBuilder.cpp

 
 /*
  * Copyright 2011 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "SkEdgeBuilder.h"
 #include "SkPath.h"
 #include "SkEdge.h"
 #include "SkEdgeClipper.h"
 #include "SkLineClipper.h"
 #include "SkGeometry.h"
 
 template <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) {
     return static_cast<T*>(alloc.allocThrow(sizeof(T)));
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
 SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) {
     fEdgeList = nullptr;
 }
 
+SkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical(const SkEdge* edge, SkEdge* last) {
+    if (last->fCurveCount || last->fDX || edge->fX != last->fX) {
+        return kNo_Combine;
+    }
+    if (edge->fWinding == last->fWinding) {
+        if (edge->fLastY + 1 == last->fFirstY) {
+            last->fFirstY = edge->fFirstY;
+            return kPartial_Combine;
+        }
+        if (edge->fFirstY == last->fLastY + 1) {
+            last->fLastY = edge->fLastY;
+            return kPartial_Combine;
+        }
+        return kNo_Combine;
+    }
+    if (edge->fFirstY == last->fFirstY) {
+        if (edge->fLastY == last->fLastY) {
+            return kTotal_Combine;
+        }
+        if (edge->fLastY < last->fLastY) {
+            last->fFirstY = edge->fLastY + 1;
+            return kPartial_Combine;
+        }
+        last->fFirstY = last->fLastY + 1;
+        last->fLastY = edge->fLastY;
+        last->fWinding = edge->fWinding;
+        return kPartial_Combine;
+    }
+    if (edge->fLastY == last->fLastY) {
+        if (edge->fFirstY > last->fFirstY) {
+            last->fLastY = edge->fFirstY - 1;
+            return kPartial_Combine;
+        }
+        last->fLastY = last->fFirstY - 1;
+        last->fFirstY = edge->fFirstY;
+        last->fWinding = edge->fWinding;
+        return kPartial_Combine;
+    }
+    return kNo_Combine;
+}
+
+static bool vertical_line(const SkEdge* edge) {
+#ifdef SK_SUPPORT_LEGACY_VERTICAL_EDGE  // this disables combining vertical overlapping edges
+    return false;
+#endif
+    return !edge->fDX && !edge->fCurveCount;
+}
+
 void SkEdgeBuilder::addLine(const SkPoint pts[]) {
     SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc);
     if (edge->setLine(pts[0], pts[1], fShiftUp)) {
+        if (vertical_line(edge) && fList.count()) {
+            Combine combine = CombineVertical(edge, *(fList.end() - 1));
+            if (kNo_Combine != combine) {
+                if (kTotal_Combine == combine) {
+                    fList.pop();
+                }
+                goto unallocate_edge;
+            }
+        }
         fList.push(edge);
     } else {
+unallocate_edge:
+        ;
         // TODO: unallocate edge from storage...
     }
 }
 
 void SkEdgeBuilder::addQuad(const SkPoint pts[]) {
     SkQuadraticEdge* edge = typedAllocThrow<SkQuadraticEdge>(fAlloc);
     if (edge->setQuadratic(pts, fShiftUp)) {
         fList.push(edge);
     } else {
         // TODO: unallocate edge from storage...
@@ skipping 32 matching lines @@
 
 ///////////////////////////////////////////////////////////////////////////////
 
 static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) {
     dst->set(SkIntToScalar(src.fLeft >> shift),
              SkIntToScalar(src.fTop >> shift),
              SkIntToScalar(src.fRight >> shift),
              SkIntToScalar(src.fBottom >> shift));
 }
 
+SkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkEdge* edge, SkEdge** edgePtr) {
+    return !vertical_line(edge) || edgePtr <= fEdgeList ? kNo_Combine :
+            CombineVertical(edge, edgePtr[-1]);
+}
+
 int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shiftUp,
                              bool canCullToTheRight) {
     SkPath::Iter    iter(path, true);
     SkPoint         pts[4];
     SkPath::Verb    verb;
 
     int maxEdgeCount = path.countPoints();
     if (iclip) {
         // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
         // we turn portions that are clipped out on the left/right into vertical
@@ skipping 20 matching lines @@
                 case SkPath::kClose_Verb:
                     // we ignore these, and just get the whole segment from
                     // the corresponding line/quad/cubic verbs
                     break;
                 case SkPath::kLine_Verb: {
                     SkPoint lines[SkLineClipper::kMaxPoints];
                     int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
                     SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
                     for (int i = 0; i < lineCount; i++) {
                         if (edge->setLine(lines[i], lines[i + 1], shiftUp)) {
-                            *edgePtr++ = edge++;
+                            Combine combine = checkVertical(edge, edgePtr);
+                            if (kNo_Combine == combine) {
+                                *edgePtr++ = edge++;
+                            } else if (kTotal_Combine == combine) {
+                                --edgePtr;
+                            }
                         }
                     }
                     break;
                 }
                 default:
                     SkDEBUGFAIL("unexpected verb");
                     break;
             }
         }
     } else {
         while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
             switch (verb) {
                 case SkPath::kMove_Verb:
                 case SkPath::kClose_Verb:
                     // we ignore these, and just get the whole segment from
                     // the corresponding line/quad/cubic verbs
                     break;
                 case SkPath::kLine_Verb:
                     if (edge->setLine(pts[0], pts[1], shiftUp)) {
-                        *edgePtr++ = edge++;
+                        Combine combine = checkVertical(edge, edgePtr);
+                        if (kNo_Combine == combine) {
+                            *edgePtr++ = edge++;
+                        } else if (kTotal_Combine == combine) {
+                            --edgePtr;
+                        }
                     }
                     break;
                 default:
                     SkDEBUGFAIL("unexpected verb");
                     break;
             }
         }
     }
     SkASSERT((char*)edge <= (char*)fEdgeList);
     SkASSERT(edgePtr - fEdgeList <= maxEdgeCount);
@@ skipping 103 matching lines @@
                 }
                 default:
                     SkDEBUGFAIL("unexpected verb");
                     break;
             }
         }
     }
     fEdgeList = fList.begin();
     return fList.count();
 }