Use Path Ops to generate PDF clips

src/pdf/SkPDFDevice.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 "SkPDFDevice.h"
 
 #include "SkAnnotation.h"
@@ skipping 309 matching lines @@
 
     NOT_IMPLEMENTED(clipFill == SkPath::kInverseEvenOdd_FillType, false);
     NOT_IMPLEMENTED(clipFill == SkPath::kInverseWinding_FillType, false);
     if (clipFill == SkPath::kEvenOdd_FillType) {
         contentStream->writeText("W* n\n");
     } else {
         contentStream->writeText("W n\n");
     }
 }
 
+/* Calculate an inverted path's equivalent non-inverted path, given the
+ * canvas bounds.
+ * outPath may alias with invPath (since this is supported by PathOps).
+ */
+static bool calculate_inverse_path(const SkRect& bounds, const SkPath& invPath,
+                            SkPath* outPath) {

[edisonn, 2013/07/31 18:27:37]

nit: align

[vandebo (ex-Chrome), 2013/07/31 18:35:17]

indent (in original too).

[ducky, 2013/08/01 00:45:08]

Done.

+    SkASSERT(invPath.isInverseFillType());
+
+    SkPath clipPath;
+    clipPath.addRect(bounds);
+
+    return Op(clipPath, invPath, kIntersect_PathOp, outPath);
+}
+
+#ifdef SK_PDF_USE_PATHOPS
+static SkPathOp region_op_to_pathops_op(SkRegion::Op op) {

[vandebo (ex-Chrome), 2013/07/31 18:35:17]

SkRegion::Op and SkPathOp have the same value for these.  You might want to do
compile asserts that this remains true and then just do a cast - it'll be
faster.

[ducky, 2013/08/01 00:45:08]

Done.

+    switch (op) {
+        case SkRegion::kDifference_Op:
+            return kDifference_PathOp;
+        case SkRegion::kIntersect_Op:
+            return kIntersect_PathOp;
+        case SkRegion::kUnion_Op:
+            return kUnion_PathOp;
+        case SkRegion::kXOR_Op:
+            return kXOR_PathOp;
+        case SkRegion::kReverseDifference_Op:
+            return kReverseDifference_PathOp;
+        default:
+            SkASSERT(false);    // unrecognized op
+    }
+    return kIntersect_PathOp;
+}
+
+static SkPath get_clip_stack_path(const SkMatrix& transform,
+                                  const SkClipStack& clipStack,
+                                  const SkRegion& clipRegion) {
+    SkPath clipPath;
+
+    // Because of additive operations (especially XOR), starting an empty

[vandebo (ex-Chrome), 2013/07/31 18:35:17]

I don't understand the first part.

[ducky, 2013/08/01 00:45:08]

Ok, I tried to clarify.

+    // clip with the bounds of the final clip can cause inaccuracies, since
+    // the intermediate clips may be larger than the final bounds.
+    // Therefore, to guarantee accuracy of the final clip, this starts with a
+    // empty clip 2 units out from the final bounds. After all stack operations
+    // are applied, the final clip is cropped to 1 unit out from the final
+    // bounds. The buffer space ensures there is no ambiguity on edge cases.

[vandebo (ex-Chrome), 2013/07/31 18:35:17]

I don't think we should use this buffer space.  If you need to, write a gm that
clips along the edge to ensure that we get it right.

[ducky, 2013/08/01 00:45:08]

I'm concerned about the numerical issues that were brought up in the Path Ops
talk, where points might not be exact because of floating point limitations or
other accuracy errors. It's probably a very edge case, and if this behavior is a
problem, I'm not sure if I can write a GM to demonstrate it without a deeper
understanding of how PathOps works. So this just plays it safe.

Additionally, SkRegion is a bitmap, which is only an approximation of the
clipping path. If there's any filtering going on (like if a path occupying an
area of less than half a pixel doesn't make the pixel inside the path - I don't
know if this is the case), that may cause the clip bounds to be a tad too small.

+    SkRect clipBounds = SkRect::Make(clipRegion.getBounds());
+    clipBounds.outset(SK_Scalar1, SK_Scalar1);
+    SkRect workingBounds = clipBounds;
+    workingBounds.outset(SK_Scalar1, SK_Scalar1);
+    clipPath.addRect(workingBounds);
+
+    const SkClipStack::Element* clipEntry;
+    SkClipStack::Iter iter;
+    iter.reset(clipStack, SkClipStack::Iter::kBottom_IterStart);
+    for (clipEntry = iter.next(); clipEntry; clipEntry = iter.next()) {
+        SkPath entryPath;
+        if (SkClipStack::Element::kEmpty_Type == clipEntry->getType()) {
+            clipPath.reset();
+            continue;
+        } else if (SkClipStack::Element::kRect_Type == clipEntry->getType()) {
+            SkRect translatedRect;
+            transform.mapRect(&translatedRect, clipEntry->getRect());

[edisonn, 2013/07/31 18:27:37]

this can fail!

[ducky, 2013/08/01 00:45:08]

Fixed, now the transform happens as a path, which hopefully should handle the
cases that rect can't.

+            entryPath.addRect(translatedRect);
+        } else if (SkClipStack::Element::kPath_Type == clipEntry->getType()) {
+            clipEntry->getPath().transform(transform, &entryPath);

[edisonn, 2013/07/31 18:27:37]

this can fail?

[ducky, 2013/08/01 00:45:08]

Doesn't look like it. SkPath::transform returns void.

+        }
+
+        if (SkRegion::kReplace_Op == clipEntry->getOp()) {
+            clipPath = entryPath;
+        } else {
+            SkPathOp op = region_op_to_pathops_op(clipEntry->getOp());

[vandebo (ex-Chrome), 2013/07/31 18:35:17]

Do you have to check if entryPath has an inverse fill type?

You could have a rectangle and then a inverse path inside that...

[ducky, 2013/08/01 00:45:08]

I think PathOps handles inverses. All the GMs (some including inverses) that
were affected have turned out fine.

+            if (!Op(clipPath, entryPath, op, &clipPath)) {
+                SkAssertResult(clipRegion.getBoundaryPath(&clipPath));
+                return clipPath;
+            }
+        }
+    }
+
+    if (clipPath.isInverseFillType()) {
+        calculate_inverse_path(SkRect::Make(clipRegion.getBounds()),
+                               clipPath, &clipPath);
+    }
+
+    SkPath boundsPath;
+    boundsPath.addRect(clipBounds);
+
+    if (!Op(clipPath, boundsPath, kIntersect_PathOp, &clipPath)) {

[vandebo (ex-Chrome), 2013/07/31 18:35:17]

Won't this last step take care of any inverse path fill of clipPath ?

[ducky, 2013/08/01 00:45:08]

Good point.

+        SkAssertResult(clipRegion.getBoundaryPath(&clipPath));
+        return clipPath;
+    }
+
+    return clipPath;
+}
+#endif
+
 // TODO(vandebo): Take advantage of SkClipStack::getSaveCount(), the PDF
 // graphic state stack, and the fact that we can know all the clips used
 // on the page to optimize this.
 void GraphicStackState::updateClip(const SkClipStack& clipStack,
                                    const SkRegion& clipRegion,
                                    const SkPoint& translation) {
     if (clipStack == currentEntry()->fClipStack) {
         return;
     }
 
@@ skipping 11 matching lines @@
     // the clip in effect when the layer was created.)  There's no need to
     // reapply that clip; SKCanvas's SkDrawIter will draw anything outside the
     // initial clip on the parent layer.  (This means there's a bug if the user
     // expands the clip and then uses any xfer mode that uses dst:
     // http://code.google.com/p/skia/issues/detail?id=228 )
     SkClipStack::Iter iter;
     skip_clip_stack_prefix(fEntries[0].fClipStack, clipStack, &iter);
 
     // If the clip stack does anything other than intersect or if it uses
     // an inverse fill type, we have to fall back to the clip region.
     bool needRegion = false;

[vandebo (ex-Chrome), 2013/07/31 18:35:17]

If we have path ops turned on, what do you think of always using it, even if
needsRegion would be false.

[ducky, 2013/08/01 00:45:08]

Sure - added.
Though, this could potentially preclude optimizations where common parts of the
clip stack don't need to be re-emitted for every clip operation. But I don't
think that is happening right now, and this makes the code a lot cleaner.

     const SkClipStack::Element* clipEntry;
     for (clipEntry = iter.next(); clipEntry; clipEntry = iter.next()) {
         if (clipEntry->getOp() != SkRegion::kIntersect_Op || clipEntry->isInverseFilled()) {
             needRegion = true;
             break;
         }
     }
 
+    SkMatrix transform;
+    transform.setTranslate(translation.fX, translation.fY);
+
     if (needRegion) {
+#ifdef SK_PDF_USE_PATHOPS
+        SkPath clipPath = get_clip_stack_path(transform, clipStack, clipRegion);
+        emit_clip(&clipPath, NULL, fContentStream);
+#else
         SkPath clipPath;
         SkAssertResult(clipRegion.getBoundaryPath(&clipPath));
         emit_clip(&clipPath, NULL, fContentStream);
+#endif
     } else {
         skip_clip_stack_prefix(fEntries[0].fClipStack, clipStack, &iter);
-        SkMatrix transform;
-        transform.setTranslate(translation.fX, translation.fY);
         const SkClipStack::Element* clipEntry;
         for (clipEntry = iter.next(); clipEntry; clipEntry = iter.next()) {
             SkASSERT(clipEntry->getOp() == SkRegion::kIntersect_Op);
             switch (clipEntry->getType()) {
                 case SkClipStack::Element::kRect_Type: {
                     SkRect translatedClip;
                     transform.mapRect(&translatedClip, clipEntry->getRect());
                     emit_clip(NULL, &translatedClip, fContentStream);
                     break;
                 }
@@ skipping 844 matching lines @@
         emit_clip(NULL, &r, &data);
     }
 
     SkPDFDevice::copyContentEntriesToData(fContentEntries.get(), &data);
 
     // potentially we could cache this SkData, and only rebuild it if we
     // see that our state has changed.
     return data.copyToData();
 }
 
-/* Calculate an inverted path's equivalent non-inverted path, given the
- * canvas bounds.
- */
-static bool calculate_inverse_path(const SkRect& bounds, const SkPath& invPath,
-                            SkPath* outPath) {
-    SkASSERT(invPath.isInverseFillType());
-
-    SkPath clipPath;
-    clipPath.addRect(bounds);
-
-    return Op(clipPath, invPath, kIntersect_PathOp, outPath);
-}
-
 /* Draws an inverse filled path by using Path Ops to compute the positive
  * inverse using the current clip as the inverse bounds.
  * Return true if this was an inverse path and was properly handled,
  * otherwise returns false and the normal drawing routine should continue,
  * either as a (incorrect) fallback or because the path was not inverse
  * in the first place.
  */
 bool SkPDFDevice::handleInversePath(const SkDraw& d, const SkPath& origPath,
                                     const SkPaint& paint, bool pathIsMutable) {
     if (!origPath.isInverseFillType()) {
@@ skipping 567 matching lines @@
 }
 
 bool SkPDFDevice::onReadPixels(const SkBitmap& bitmap, int x, int y,
                                SkCanvas::Config8888) {
     return false;
 }
 
 bool SkPDFDevice::allowImageFilter(SkImageFilter*) {
     return false;
 }