From 3df87cb36e9f9d2e04d2f81ac64cf3d778c33847 Mon Sep 17 00:00:00 2001
From: "mike@reedtribe.org"
 <mike@reedtribe.org@2bbb7eff-a529-9590-31e7-b0007b416f81>
Date: Mon, 15 Apr 2013 15:20:52 +0000
Subject: [PATCH] add experimental chop-into-quads for conics

git-svn-id: http://skia.googlecode.com/svn/trunk@8681 2bbb7eff-a529-9590-31e7-b0007b416f81
---
 include/core/SkGeometry.h |  3 +++
 src/core/SkGeometry.cpp   | 61 ++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 63 insertions(+), 1 deletion(-)

diff --git a/include/core/SkGeometry.h b/include/core/SkGeometry.h
index 8bdbbe0..909aeb9 100644
--- a/include/core/SkGeometry.h
+++ b/include/core/SkGeometry.h
@@ -219,6 +219,9 @@ struct SkRationalQuad {
     void evalAt(SkScalar t, SkPoint* pt) const;
     void chopAt(SkScalar t, SkRationalQuad dst[2]) const;
     void chop(SkRationalQuad dst[2]) const;
+    
+    int computeQuadPOW2(SkScalar tol) const;
+    int chopIntoQuadsPOW2(SkPoint pts[], int pow2) const;
 };
 
 #endif
diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp
index fed11e4..32b44f9 100644
--- a/src/core/SkGeometry.cpp
+++ b/src/core/SkGeometry.cpp
@@ -1465,6 +1465,10 @@ void SkRationalQuad::chopAt(SkScalar t, SkRationalQuad dst[2]) const {
     dst[1].fW = tmp2[2].fZ / root;
 }
 
+static SkScalar subdivide_w_value(SkScalar w) {
+    return SkScalarSqrt((1 + w) * SK_ScalarHalf);
+}
+
 void SkRationalQuad::chop(SkRationalQuad dst[2]) const {
     SkScalar scale = SkScalarInvert(SK_Scalar1 + fW);
     SkScalar p1x = fW * fPts[1].fX;
@@ -1482,5 +1486,60 @@ void SkRationalQuad::chop(SkRationalQuad dst[2]) const {
                        (p1y + fPts[2].fY) * scale);
     dst[1].fPts[2] = fPts[2];
 
-    dst[0].fW = dst[1].fW = SkScalarSqrt((1 + fW) * SK_ScalarHalf);
+    dst[0].fW = dst[1].fW = subdivide_w_value(fW);
+}
+
+int SkRationalQuad::computeQuadPOW2(SkScalar tol) const {
+    if (fW <= SK_ScalarNearlyZero) {
+        return 0;   // treat as a line
+    }
+    
+    tol = SkScalarAbs(tol);
+    SkScalar w = fW;
+    int i = 0;
+    for (; i < 8; ++i) {
+        if (SkScalarAbs(w - 1) <= tol) {
+            break;
+        }
+        w = subdivide_w_value(w);
+    }
+    return i;
+}
+
+static SkPoint* subdivide(const SkRationalQuad& src, SkPoint pts[], int level) {
+    SkASSERT(level >= 0);
+    if (0 == level) {
+        memcpy(pts, &src.fPts[1], 2 * sizeof(SkPoint));
+        return pts + 2;
+    } else {
+        SkRationalQuad dst[2];
+        src.chop(dst);
+        --level;
+        pts = subdivide(dst[0], pts, level);
+        return subdivide(dst[1], pts, level);
+    }
 }
+
+int SkRationalQuad::chopIntoQuadsPOW2(SkPoint pts[], int pow2) const {
+    if (pow2 < 0) {
+        return 0;
+    }
+    if (0 == pow2) {
+        memcpy(pts, fPts, 3 * sizeof(SkPoint));
+        return 1;
+    }
+    if (1 == pow2) {
+        SkRationalQuad dst[2];
+        this->chop(dst);
+        memcpy(pts, dst[0].fPts, 3 * sizeof(SkPoint));
+        pts += 3;
+        memcpy(pts, dst[1].fPts + 1, 2 * sizeof(SkPoint));
+        return 2;
+    }
+
+    *pts = fPts[0];
+    SkPoint* endPts = subdivide(*this, pts + 1, pow2);
+    SkASSERT(endPts - pts == (2 * (1 << pow2) + 1));
+    return 1 << pow2;
+}
+
-- 
2.7.4