Remove the remainder of the skia source code from the Chromium repo....

skia/sgl/SkPathMeasure.cpp

Index: skia/sgl/SkPathMeasure.cpp
===================================================================
--- skia/sgl/SkPathMeasure.cpp	(revision 16859)
+++ skia/sgl/SkPathMeasure.cpp	(working copy)
@@ -1,598 +0,0 @@
-/*
- * Copyright (C) 2006-2008 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include "SkPathMeasure.h"
-#include "SkGeometry.h"
-#include "SkPath.h"
-#include "SkTSearch.h"
-
-// these must be 0,1,2 since they are in our 2-bit field
-enum {
-    kLine_SegType,
-    kCloseLine_SegType,
-    kQuad_SegType,
-    kCubic_SegType
-};
-
-#define kMaxTValue  32767
-
-static inline SkScalar tValue2Scalar(int t) {
-    SkASSERT((unsigned)t <= kMaxTValue);
-
-#ifdef SK_SCALAR_IS_FLOAT
-    return t * 3.05185e-5f; // t / 32767
-#else
-    return (t + (t >> 14)) << 1;
-#endif
-}
-
-SkScalar SkPathMeasure::Segment::getScalarT() const {
-    return tValue2Scalar(fTValue);
-}
-
-const SkPathMeasure::Segment* SkPathMeasure::NextSegment(const Segment* seg) {
-    unsigned ptIndex = seg->fPtIndex;
-
-    do {
-        ++seg;
-    } while (seg->fPtIndex == ptIndex);
-    return seg;
-}
-
-///////////////////////////////////////////////////////////////////////////////
-
-static inline int tspan_big_enough(int tspan) {
-    SkASSERT((unsigned)tspan <= kMaxTValue);
-    return tspan >> 10;
-}
-
-#if 0
-static inline bool tangents_too_curvy(const SkVector& tan0, SkVector& tan1) {
-    static const SkScalar kFlatEnoughTangentDotProd = SK_Scalar1 * 99 / 100;
-
-    SkASSERT(kFlatEnoughTangentDotProd > 0 &&
-             kFlatEnoughTangentDotProd < SK_Scalar1);
-
-    return SkPoint::DotProduct(tan0, tan1) < kFlatEnoughTangentDotProd;
-}
-#endif
-
-// can't use tangents, since we need [0..1..................2] to be seen
-// as definitely not a line (it is when drawn, but not parametrically)
-// so we compare midpoints
-#define CHEAP_DIST_LIMIT    (SK_Scalar1/2)  // just made this value up
-
-static bool quad_too_curvy(const SkPoint pts[3]) {
-    // diff = (a/4 + b/2 + c/4) - (a/2 + c/2)
-    // diff = -a/4 + b/2 - c/4
-    SkScalar dx = SkScalarHalf(pts[1].fX) -
-                        SkScalarHalf(SkScalarHalf(pts[0].fX + pts[2].fX));
-    SkScalar dy = SkScalarHalf(pts[1].fY) -
-                        SkScalarHalf(SkScalarHalf(pts[0].fY + pts[2].fY));
-
-    SkScalar dist = SkMaxScalar(SkScalarAbs(dx), SkScalarAbs(dy));
-    return dist > CHEAP_DIST_LIMIT;
-}
-
-static bool cheap_dist_exceeds_limit(const SkPoint& pt,
-                                     SkScalar x, SkScalar y) {
-    SkScalar dist = SkMaxScalar(SkScalarAbs(x - pt.fX), SkScalarAbs(y - pt.fY));
-    // just made up the 1/2
-    return dist > CHEAP_DIST_LIMIT;
-}
-
-static bool cubic_too_curvy(const SkPoint pts[4]) {
-    return  cheap_dist_exceeds_limit(pts[1],
-                         SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1/3),
-                         SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1/3))
-                         ||
-            cheap_dist_exceeds_limit(pts[2],
-                         SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1*2/3),
-                         SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1*2/3));
-}
-
-SkScalar SkPathMeasure::compute_quad_segs(const SkPoint pts[3],
-                          SkScalar distance, int mint, int maxt, int ptIndex) {
-    if (tspan_big_enough(maxt - mint) && quad_too_curvy(pts)) {
-        SkPoint tmp[5];
-        int     halft = (mint + maxt) >> 1;
-
-        SkChopQuadAtHalf(pts, tmp);
-        distance = this->compute_quad_segs(tmp, distance, mint, halft, ptIndex);
-        distance = this->compute_quad_segs(&tmp[2], distance, halft, maxt, ptIndex);
-    } else {
-        SkScalar d = SkPoint::Distance(pts[0], pts[2]);
-        SkASSERT(d >= 0);
-        if (!SkScalarNearlyZero(d)) {
-            distance += d;
-            Segment* seg = fSegments.append();
-            seg->fDistance = distance;
-            seg->fPtIndex = ptIndex;
-            seg->fType = kQuad_SegType;
-            seg->fTValue = maxt;
-        }
-    }
-    return distance;
-}
-
-SkScalar SkPathMeasure::compute_cubic_segs(const SkPoint pts[4],
-                           SkScalar distance, int mint, int maxt, int ptIndex) {
-    if (tspan_big_enough(maxt - mint) && cubic_too_curvy(pts)) {
-        SkPoint tmp[7];
-        int     halft = (mint + maxt) >> 1;
-
-        SkChopCubicAtHalf(pts, tmp);
-        distance = this->compute_cubic_segs(tmp, distance, mint, halft, ptIndex);
-        distance = this->compute_cubic_segs(&tmp[3], distance, halft, maxt, ptIndex);
-    } else {
-        SkScalar d = SkPoint::Distance(pts[0], pts[3]);
-        SkASSERT(d >= 0);
-        if (!SkScalarNearlyZero(d)) {
-            distance += d;
-            Segment* seg = fSegments.append();
-            seg->fDistance = distance;
-            seg->fPtIndex = ptIndex;
-            seg->fType = kCubic_SegType;
-            seg->fTValue = maxt;
-        }
-    }
-    return distance;
-}
-
-void SkPathMeasure::buildSegments() {
-    SkPoint         pts[4];
-    int             ptIndex = fFirstPtIndex;
-    SkScalar        d, distance = 0;
-    bool            isClosed = fForceClosed;
-    bool            firstMoveTo = ptIndex < 0;
-    Segment*        seg;
-
-    fSegments.reset();
-    for (;;) {
-        switch (fIter.next(pts)) {
-            case SkPath::kMove_Verb:
-                if (!firstMoveTo) {
-                    goto DONE;
-                }
-            ptIndex += 1;
-            firstMoveTo = false;
-            break;
-
-            case SkPath::kLine_Verb:
-                d = SkPoint::Distance(pts[0], pts[1]);
-                SkASSERT(d >= 0);
-                if (!SkScalarNearlyZero(d)) {
-                    distance += d;
-                    seg = fSegments.append();
-                    seg->fDistance = distance;
-                    seg->fPtIndex = ptIndex;
-                    seg->fType = fIter.isCloseLine() ?
-                                    kCloseLine_SegType : kLine_SegType;
-                    seg->fTValue = kMaxTValue;
-                }
-                ptIndex += !fIter.isCloseLine();
-                break;
-
-            case SkPath::kQuad_Verb:
-                distance = this->compute_quad_segs(pts, distance, 0,
-                                                   kMaxTValue, ptIndex);
-                ptIndex += 2;
-                break;
-
-            case SkPath::kCubic_Verb:
-                distance = this->compute_cubic_segs(pts, distance, 0,
-                                                    kMaxTValue, ptIndex);
-                ptIndex += 3;
-                break;
-
-            case SkPath::kClose_Verb:
-                isClosed = true;
-                break;
-                
-            case SkPath::kDone_Verb:
-                goto DONE;
-        }
-    }
-DONE:
-    fLength = distance;
-    fIsClosed = isClosed;
-    fFirstPtIndex = ptIndex + 1;
-
-#ifdef SK_DEBUG
-    {
-        const Segment* seg = fSegments.begin();
-        const Segment* stop = fSegments.end();
-        unsigned        ptIndex = 0;
-        SkScalar        distance = 0;
-
-        while (seg < stop) {
-            SkASSERT(seg->fDistance > distance);
-            SkASSERT(seg->fPtIndex >= ptIndex);
-            SkASSERT(seg->fTValue > 0);
-
-            const Segment* s = seg;
-            while (s < stop - 1 && s[0].fPtIndex == s[1].fPtIndex) {
-                SkASSERT(s[0].fType == s[1].fType);
-                SkASSERT(s[0].fTValue < s[1].fTValue);
-                s += 1;
-            }
-
-            distance = seg->fDistance;
-            ptIndex = seg->fPtIndex;
-            seg += 1;
-        }
-    //  SkDebugf("\n");
-    }
-#endif
-}
-
-// marked as a friend in SkPath.h
-const SkPoint* sk_get_path_points(const SkPath& path, int index) {
-    return &path.fPts[index];
-}
-
-static void compute_pos_tan(const SkPath& path, int firstPtIndex, int ptIndex,
-                    int segType, SkScalar t, SkPoint* pos, SkVector* tangent) {
-    const SkPoint*  pts = sk_get_path_points(path, ptIndex);
-
-    switch (segType) {
-        case kLine_SegType:
-        case kCloseLine_SegType: {
-            const SkPoint* endp = (segType == kLine_SegType) ?
-                                    &pts[1] :
-                                    sk_get_path_points(path, firstPtIndex);
-
-            if (pos) {
-                pos->set(SkScalarInterp(pts[0].fX, endp->fX, t),
-                        SkScalarInterp(pts[0].fY, endp->fY, t));
-            }
-            if (tangent) {
-                tangent->setNormalize(endp->fX - pts[0].fX, endp->fY - pts[0].fY);
-            }
-            break;
-        }
-        case kQuad_SegType:
-            SkEvalQuadAt(pts, t, pos, tangent);
-            if (tangent) {
-                tangent->normalize();
-            }
-            break;
-        case kCubic_SegType:
-            SkEvalCubicAt(pts, t, pos, tangent, NULL);
-            if (tangent) {
-                tangent->normalize();
-            }
-            break;
-        default:
-            SkASSERT(!"unknown segType");
-    }
-}
-
-static void seg_to(const SkPath& src, int firstPtIndex, int ptIndex,
-                   int segType, SkScalar startT, SkScalar stopT, SkPath* dst) {
-    SkASSERT(startT >= 0 && startT <= SK_Scalar1);
-    SkASSERT(stopT >= 0 && stopT <= SK_Scalar1);
-    SkASSERT(startT <= stopT);
-
-    if (SkScalarNearlyZero(stopT - startT)) {
-        return;
-    }
-
-    const SkPoint*  pts = sk_get_path_points(src, ptIndex);
-    SkPoint         tmp0[7], tmp1[7];
-
-    switch (segType) {
-        case kLine_SegType:
-        case kCloseLine_SegType: {
-            const SkPoint* endp = (segType == kLine_SegType) ?
-                                    &pts[1] :
-                                    sk_get_path_points(src, firstPtIndex);
-
-            if (stopT == kMaxTValue) {
-                dst->lineTo(*endp);
-            } else {
-                dst->lineTo(SkScalarInterp(pts[0].fX, endp->fX, stopT),
-                            SkScalarInterp(pts[0].fY, endp->fY, stopT));
-            }
-            break;
-        }
-        case kQuad_SegType:
-            if (startT == 0) {
-                if (stopT == SK_Scalar1) {
-                    dst->quadTo(pts[1], pts[2]);
-                } else {
-                    SkChopQuadAt(pts, tmp0, stopT);
-                    dst->quadTo(tmp0[1], tmp0[2]);
-                }
-            } else {
-                SkChopQuadAt(pts, tmp0, startT);
-                if (stopT == SK_Scalar1) {
-                    dst->quadTo(tmp0[3], tmp0[4]);
-                } else {
-                    SkChopQuadAt(&tmp0[2], tmp1, SkScalarDiv(stopT - startT,
-                                                         SK_Scalar1 - startT));
-                    dst->quadTo(tmp1[1], tmp1[2]);
-                }
-            }
-            break;
-        case kCubic_SegType:
-            if (startT == 0) {
-                if (stopT == SK_Scalar1) {
-                    dst->cubicTo(pts[1], pts[2], pts[3]);
-                } else {
-                    SkChopCubicAt(pts, tmp0, stopT);
-                    dst->cubicTo(tmp0[1], tmp0[2], tmp0[3]);
-                }
-            } else {
-                SkChopCubicAt(pts, tmp0, startT);
-                if (stopT == SK_Scalar1) {
-                    dst->cubicTo(tmp0[4], tmp0[5], tmp0[6]);
-                } else {
-                    SkChopCubicAt(&tmp0[3], tmp1, SkScalarDiv(stopT - startT,
-                                                        SK_Scalar1 - startT));
-                    dst->cubicTo(tmp1[1], tmp1[2], tmp1[3]);
-                }
-            }
-            break;
-        default:
-            SkASSERT(!"unknown segType");
-            sk_throw();
-    }
-}
-
-////////////////////////////////////////////////////////////////////////////////
-////////////////////////////////////////////////////////////////////////////////
-
-SkPathMeasure::SkPathMeasure() {
-    fPath = NULL;
-    fLength = -1;   // signal we need to compute it
-    fForceClosed = false;
-    fFirstPtIndex = -1;
-}
-
-SkPathMeasure::SkPathMeasure(const SkPath& path, bool forceClosed) {
-    fPath = &path;
-    fLength = -1;   // signal we need to compute it
-    fForceClosed = forceClosed;
-    fFirstPtIndex = -1;
-
-    fIter.setPath(path, forceClosed);
-}
-
-SkPathMeasure::~SkPathMeasure() {}
-
-/** Assign a new path, or null to have none.
-*/
-void SkPathMeasure::setPath(const SkPath* path, bool forceClosed) {
-    fPath = path;
-    fLength = -1;   // signal we need to compute it
-    fForceClosed = forceClosed;
-    fFirstPtIndex = -1;
-
-    if (path) {
-        fIter.setPath(*path, forceClosed);
-    }
-    fSegments.reset();
-}
-
-SkScalar SkPathMeasure::getLength() {
-    if (fPath == NULL) {
-        return 0;
-    }
-    if (fLength < 0) {
-        this->buildSegments();
-    }
-    SkASSERT(fLength >= 0);
-    return fLength;
-}
-
-const SkPathMeasure::Segment* SkPathMeasure::distanceToSegment(
-                                            SkScalar distance, SkScalar* t) {
-    SkDEBUGCODE(SkScalar length = ) this->getLength();
-    SkASSERT(distance >= 0 && distance <= length);
-
-    const Segment*  seg = fSegments.begin();
-    int             count = fSegments.count();
-
-    int index = SkTSearch<SkScalar>(&seg->fDistance, count, distance,
-                                    sizeof(Segment));
-    // don't care if we hit an exact match or not, so we xor index if it is negative
-    index ^= (index >> 31);
-    seg = &seg[index];
-
-    // now interpolate t-values with the prev segment (if possible)
-    SkScalar    startT = 0, startD = 0;
-    // check if the prev segment is legal, and references the same set of points
-    if (index > 0) {
-        startD = seg[-1].fDistance;
-        if (seg[-1].fPtIndex == seg->fPtIndex) {
-            SkASSERT(seg[-1].fType == seg->fType);
-            startT = seg[-1].getScalarT();
-        }
-    }
-
-    SkASSERT(seg->getScalarT() > startT);
-    SkASSERT(distance >= startD);
-    SkASSERT(seg->fDistance > startD);
-
-    *t = startT + SkScalarMulDiv(seg->getScalarT() - startT,
-                                 distance - startD,
-                                 seg->fDistance - startD);
-    return seg;
-}
-
-bool SkPathMeasure::getPosTan(SkScalar distance, SkPoint* pos,
-                              SkVector* tangent) {
-    SkASSERT(fPath);
-    if (fPath == NULL) {
-    EMPTY:
-        return false;
-    }
-
-    SkScalar    length = this->getLength(); // call this to force computing it
-    int         count = fSegments.count();
-
-    if (count == 0 || length == 0) {
-        goto EMPTY;
-    }
-
-    // pin the distance to a legal range
-    if (distance < 0) {
-        distance = 0;
-    } else if (distance > length) {
-        distance = length;
-    }
-    
-    SkScalar        t;
-    const Segment*  seg = this->distanceToSegment(distance, &t);
-
-    compute_pos_tan(*fPath, fSegments[0].fPtIndex, seg->fPtIndex, seg->fType,
-                    t, pos, tangent);
-    return true;
-}
-
-bool SkPathMeasure::getMatrix(SkScalar distance, SkMatrix* matrix,
-                              MatrixFlags flags) {
-    SkPoint     position;
-    SkVector    tangent;
-
-    if (this->getPosTan(distance, &position, &tangent)) {
-        if (matrix) {
-            if (flags & kGetTangent_MatrixFlag) {
-                matrix->setSinCos(tangent.fY, tangent.fX, 0, 0);
-            } else {
-                matrix->reset();
-            }
-            if (flags & kGetPosition_MatrixFlag) {
-                matrix->postTranslate(position.fX, position.fY);
-            }
-        }
-        return true;
-    }
-    return false;
-}
-
-bool SkPathMeasure::getSegment(SkScalar startD, SkScalar stopD, SkPath* dst,
-                               bool startWithMoveTo) {
-    SkASSERT(dst);
-
-    SkScalar length = this->getLength();    // ensure we have built our segments
-
-    if (startD < 0) {
-        startD = 0;
-    }
-    if (stopD > length) {
-        stopD = length;
-    }
-    if (startD >= stopD) {
-        return false;
-    }
-
-    SkPoint  p;
-    SkScalar startT, stopT;
-    const Segment* seg = this->distanceToSegment(startD, &startT);
-    const Segment* stopSeg = this->distanceToSegment(stopD, &stopT);
-    SkASSERT(seg <= stopSeg);
-
-    if (startWithMoveTo) {
-        compute_pos_tan(*fPath, fSegments[0].fPtIndex, seg->fPtIndex,
-                        seg->fType, startT, &p, NULL);
-        dst->moveTo(p);
-    }
-
-    if (seg->fPtIndex == stopSeg->fPtIndex) {
-        seg_to(*fPath, fSegments[0].fPtIndex, seg->fPtIndex, seg->fType,
-               startT, stopT, dst);
-    } else {
-        do {
-            seg_to(*fPath, fSegments[0].fPtIndex, seg->fPtIndex, seg->fType,
-                   startT, SK_Scalar1, dst);
-            seg = SkPathMeasure::NextSegment(seg);
-            startT = 0;
-        } while (seg->fPtIndex < stopSeg->fPtIndex);
-        seg_to(*fPath, fSegments[0].fPtIndex, seg->fPtIndex, seg->fType,
-               0, stopT, dst);
-    }
-    return true;
-}
-
-bool SkPathMeasure::isClosed() {
-    (void)this->getLength();
-    return fIsClosed;
-}
-
-/** Move to the next contour in the path. Return true if one exists, or false if
-    we're done with the path.
-*/
-bool SkPathMeasure::nextContour() {
-    fLength = -1;
-    return this->getLength() > 0;
-}
-
-///////////////////////////////////////////////////////////////////////////////
-///////////////////////////////////////////////////////////////////////////////
-
-#ifdef SK_DEBUG
-
-void SkPathMeasure::dump() {
-    SkDebugf("pathmeas: length=%g, segs=%d\n", fLength, fSegments.count());
-
-    for (int i = 0; i < fSegments.count(); i++) {
-        const Segment* seg = &fSegments[i];
-        SkDebugf("pathmeas: seg[%d] distance=%g, point=%d, t=%g, type=%d\n",
-                i, seg->fDistance, seg->fPtIndex, seg->getScalarT(),
-                 seg->fType);
-    }
-}
-
-void SkPathMeasure::UnitTest() {
-#ifdef SK_SUPPORT_UNITTEST
-    SkPath  path;
-
-    path.moveTo(0, 0);
-    path.lineTo(SK_Scalar1, 0);
-    path.lineTo(SK_Scalar1, SK_Scalar1);
-    path.lineTo(0, SK_Scalar1);
-
-    SkPathMeasure   meas(path, true);
-    SkScalar        length = meas.getLength();
-    SkASSERT(length == SK_Scalar1*4);
-
-    path.reset();
-    path.moveTo(0, 0);
-    path.lineTo(SK_Scalar1*3, SK_Scalar1*4);
-    meas.setPath(&path, false);
-    length = meas.getLength();
-    SkASSERT(length == SK_Scalar1*5);
-
-    path.reset();
-    path.addCircle(0, 0, SK_Scalar1);
-    meas.setPath(&path, true);
-    length = meas.getLength();
-    SkDebugf("circle arc-length = %g\n", length);
-
-    for (int i = 0; i < 8; i++) {
-        SkScalar    d = length * i / 8;
-        SkPoint     p;
-        SkVector    v;
-        meas.getPosTan(d, &p, &v);
-        SkDebugf("circle arc-length=%g, pos[%g %g] tan[%g %g]\n",
-                 d, p.fX, p.fY, v.fX, v.fY);
-    }
-#endif
-}
-
-#endif