michael@0: /*
michael@0:  * Copyright 2009 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #include "SkQuadClipper.h"
michael@0: #include "SkGeometry.h"
michael@0: 
michael@0: SkQuadClipper::SkQuadClipper() {
michael@0:     fClip.setEmpty();
michael@0: }
michael@0: 
michael@0: void SkQuadClipper::setClip(const SkIRect& clip) {
michael@0:     // conver to scalars, since that's where we'll see the points
michael@0:     fClip.set(clip);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2,
michael@0:                            SkScalar target, SkScalar* t) {
michael@0:     /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2
michael@0:      *  We solve for t, using quadratic equation, hence we have to rearrange
michael@0:      * our cooefficents to look like At^2 + Bt + C
michael@0:      */
michael@0:     SkScalar A = c0 - c1 - c1 + c2;
michael@0:     SkScalar B = 2*(c1 - c0);
michael@0:     SkScalar C = c0 - target;
michael@0: 
michael@0:     SkScalar roots[2];  // we only expect one, but make room for 2 for safety
michael@0:     int count = SkFindUnitQuadRoots(A, B, C, roots);
michael@0:     if (count) {
michael@0:         *t = roots[0];
michael@0:         return true;
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: static bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) {
michael@0:     return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: /*  If we somehow returned the fact that we had to flip the pts in Y, we could
michael@0:  communicate that to setQuadratic, and then avoid having to flip it back
michael@0:  here (only to have setQuadratic do the flip again)
michael@0:  */
michael@0: bool SkQuadClipper::clipQuad(const SkPoint srcPts[3], SkPoint dst[3]) {
michael@0:     bool reverse;
michael@0: 
michael@0:     // we need the data to be monotonically increasing in Y
michael@0:     if (srcPts[0].fY > srcPts[2].fY) {
michael@0:         dst[0] = srcPts[2];
michael@0:         dst[1] = srcPts[1];
michael@0:         dst[2] = srcPts[0];
michael@0:         reverse = true;
michael@0:     } else {
michael@0:         memcpy(dst, srcPts, 3 * sizeof(SkPoint));
michael@0:         reverse = false;
michael@0:     }
michael@0: 
michael@0:     // are we completely above or below
michael@0:     const SkScalar ctop = fClip.fTop;
michael@0:     const SkScalar cbot = fClip.fBottom;
michael@0:     if (dst[2].fY <= ctop || dst[0].fY >= cbot) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     SkScalar t;
michael@0:     SkPoint tmp[5]; // for SkChopQuadAt
michael@0: 
michael@0:     // are we partially above
michael@0:     if (dst[0].fY < ctop) {
michael@0:         if (chopMonoQuadAtY(dst, ctop, &t)) {
michael@0:             // take the 2nd chopped quad
michael@0:             SkChopQuadAt(dst, tmp, t);
michael@0:             dst[0] = tmp[2];
michael@0:             dst[1] = tmp[3];
michael@0:         } else {
michael@0:             // if chopMonoQuadAtY failed, then we may have hit inexact numerics
michael@0:             // so we just clamp against the top
michael@0:             for (int i = 0; i < 3; i++) {
michael@0:                 if (dst[i].fY < ctop) {
michael@0:                     dst[i].fY = ctop;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // are we partially below
michael@0:     if (dst[2].fY > cbot) {
michael@0:         if (chopMonoQuadAtY(dst, cbot, &t)) {
michael@0:             SkChopQuadAt(dst, tmp, t);
michael@0:             dst[1] = tmp[1];
michael@0:             dst[2] = tmp[2];
michael@0:         } else {
michael@0:             // if chopMonoQuadAtY failed, then we may have hit inexact numerics
michael@0:             // so we just clamp against the bottom
michael@0:             for (int i = 0; i < 3; i++) {
michael@0:                 if (dst[i].fY > cbot) {
michael@0:                     dst[i].fY = cbot;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (reverse) {
michael@0:         SkTSwap<SkPoint>(dst[0], dst[2]);
michael@0:     }
michael@0:     return true;
michael@0: }