1909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2009 The Android Open Source Project 3909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com */ 7909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 8ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 9909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkEdgeClipper.h" 10909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkGeometry.h" 115baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed#include "SkLineClipper.h" 12909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 13909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic bool quick_reject(const SkRect& bounds, const SkRect& clip) { 14909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return bounds.fTop >= clip.fBottom || bounds.fBottom <= clip.fTop; 15909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 16909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 17909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic inline void clamp_le(SkScalar& value, SkScalar max) { 18909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (value > max) { 19909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com value = max; 20909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 21909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 22909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 23909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic inline void clamp_ge(SkScalar& value, SkScalar min) { 24909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (value < min) { 25909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com value = min; 26909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 27909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 28909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 29909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/* src[] must be monotonic in Y. This routine copies src into dst, and sorts 30909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com it to be increasing in Y. If it had to reverse the order of the points, 31909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com it returns true, otherwise it returns false 32909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com */ 33909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic bool sort_increasing_Y(SkPoint dst[], const SkPoint src[], int count) { 34909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // we need the data to be monotonically increasing in Y 35909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (src[0].fY > src[count - 1].fY) { 36909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i < count; i++) { 37909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com dst[i] = src[count - i - 1]; 38909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 39909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return true; 40909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 41909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com memcpy(dst, src, count * sizeof(SkPoint)); 42909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return false; 43909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 44909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 45909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 465baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reedbool SkEdgeClipper::clipLine(SkPoint p0, SkPoint p1, const SkRect& clip) { 475baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed fCurrPoint = fPoints; 485baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed fCurrVerb = fVerbs; 495baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed 505baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed SkPoint lines[SkLineClipper::kMaxPoints]; 515baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed const SkPoint pts[] = { p0, p1 }; 525baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed int lineCount = SkLineClipper::ClipLine(pts, clip, lines, fCanCullToTheRight); 535baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed for (int i = 0; i < lineCount; i++) { 545baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed this->appendLine(lines[i], lines[i + 1]); 555baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed } 565baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed 575baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed *fCurrVerb = SkPath::kDone_Verb; 585baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed fCurrPoint = fPoints; 595baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed fCurrVerb = fVerbs; 605baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed return SkPath::kDone_Verb != fVerbs[0]; 615baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed} 625baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed 63909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/////////////////////////////////////////////////////////////////////////////// 64909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 65909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2, 66909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar target, SkScalar* t) { 67909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2 68909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com * We solve for t, using quadratic equation, hence we have to rearrange 69909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com * our cooefficents to look like At^2 + Bt + C 70909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com */ 71909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar A = c0 - c1 - c1 + c2; 72909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar B = 2*(c1 - c0); 73909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar C = c0 - target; 74fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 75909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar roots[2]; // we only expect one, but make room for 2 for safety 76909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int count = SkFindUnitQuadRoots(A, B, C, roots); 77909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (count) { 78909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com *t = roots[0]; 79909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return true; 80909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 81909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return false; 82909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 83909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 84909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) { 85909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t); 86909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 87909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 88909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic bool chopMonoQuadAtX(SkPoint pts[3], SkScalar x, SkScalar* t) { 89909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return chopMonoQuadAt(pts[0].fX, pts[1].fX, pts[2].fX, x, t); 90909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 91909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 92909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com// Modify pts[] in place so that it is clipped in Y to the clip rect 93909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic void chop_quad_in_Y(SkPoint pts[3], const SkRect& clip) { 94909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar t; 95909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint tmp[5]; // for SkChopQuadAt 96909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 97909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially above 98909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fY < clip.fTop) { 99909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (chopMonoQuadAtY(pts, clip.fTop, &t)) { 100909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // take the 2nd chopped quad 101909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkChopQuadAt(pts, tmp, t); 102e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com // clamp to clean up imprecise numerics in the chop 103e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com tmp[2].fY = clip.fTop; 104909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com clamp_ge(tmp[3].fY, clip.fTop); 105e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com 106909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[0] = tmp[2]; 107909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[1] = tmp[3]; 108909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 109909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // if chopMonoQuadAtY failed, then we may have hit inexact numerics 110909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // so we just clamp against the top 111909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i < 3; i++) { 112909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[i].fY < clip.fTop) { 113909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[i].fY = clip.fTop; 114909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 115909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 116909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 117909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 118fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 119909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially below 120909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[2].fY > clip.fBottom) { 121909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (chopMonoQuadAtY(pts, clip.fBottom, &t)) { 122909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkChopQuadAt(pts, tmp, t); 123e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com // clamp to clean up imprecise numerics in the chop 124909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com clamp_le(tmp[1].fY, clip.fBottom); 125e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com tmp[2].fY = clip.fBottom; 126e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com 127909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[1] = tmp[1]; 128909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[2] = tmp[2]; 129909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 130909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // if chopMonoQuadAtY failed, then we may have hit inexact numerics 131909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // so we just clamp against the bottom 132909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i < 3; i++) { 133909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[i].fY > clip.fBottom) { 134909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[i].fY = clip.fBottom; 135909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 136909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 137909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 138909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 139909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 140909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 141909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com// srcPts[] must be monotonic in X and Y 142909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeClipper::clipMonoQuad(const SkPoint srcPts[3], const SkRect& clip) { 143909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint pts[3]; 144909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com bool reverse = sort_increasing_Y(pts, srcPts, 3); 145909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 146909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we completely above or below 147909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[2].fY <= clip.fTop || pts[0].fY >= clip.fBottom) { 148909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return; 149909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 150fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 151909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // Now chop so that pts is contained within clip in Y 152909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com chop_quad_in_Y(pts, clip); 153909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 154909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fX > pts[2].fX) { 155909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkTSwap<SkPoint>(pts[0], pts[2]); 156909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com reverse = !reverse; 157909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 158909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(pts[0].fX <= pts[1].fX); 159909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(pts[1].fX <= pts[2].fX); 160909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 161909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // Now chop in X has needed, and record the segments 162909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 163909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[2].fX <= clip.fLeft) { // wholly to the left 164909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse); 165909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return; 166909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 167909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fX >= clip.fRight) { // wholly to the right 16831223e0cb74f47f63b094520a9830c525b72fe87reed if (!this->canCullToTheRight()) { 16931223e0cb74f47f63b094520a9830c525b72fe87reed this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse); 17031223e0cb74f47f63b094520a9830c525b72fe87reed } 171909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return; 172909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 173909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 174909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar t; 175909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint tmp[5]; // for SkChopQuadAt 176909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 177909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially to the left 178909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fX < clip.fLeft) { 179909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (chopMonoQuadAtX(pts, clip.fLeft, &t)) { 180909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkChopQuadAt(pts, tmp, t); 181909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fLeft, tmp[0].fY, tmp[2].fY, reverse); 182e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com // clamp to clean up imprecise numerics in the chop 183e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com tmp[2].fX = clip.fLeft; 184909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com clamp_ge(tmp[3].fX, clip.fLeft); 185e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com 186909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[0] = tmp[2]; 187909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[1] = tmp[3]; 188909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 189909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // if chopMonoQuadAtY failed, then we may have hit inexact numerics 190909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // so we just clamp against the left 191909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse); 192181172d5642fce4a4c1d339a6e3c5e4a8079b11areed@android.com return; 193909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 194909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 195fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 196909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially to the right 197909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[2].fX > clip.fRight) { 198909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (chopMonoQuadAtX(pts, clip.fRight, &t)) { 199909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkChopQuadAt(pts, tmp, t); 200e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com // clamp to clean up imprecise numerics in the chop 201909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com clamp_le(tmp[1].fX, clip.fRight); 202e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com tmp[2].fX = clip.fRight; 203e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com 204909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendQuad(tmp, reverse); 205909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fRight, tmp[2].fY, tmp[4].fY, reverse); 206909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 207909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // if chopMonoQuadAtY failed, then we may have hit inexact numerics 208909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // so we just clamp against the right 2093f0785e0c675c906c0bd704702e122149c5ee951reed@android.com this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse); 210909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 211909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { // wholly inside the clip 212909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendQuad(pts, reverse); 213909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 214909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 215909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 216909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.combool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) { 217909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint = fPoints; 218909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb = fVerbs; 219909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 220909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkRect bounds; 221909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com bounds.set(srcPts, 3); 222fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 223909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (!quick_reject(bounds, clip)) { 224909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint monoY[5]; 225909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int countY = SkChopQuadAtYExtrema(srcPts, monoY); 226909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int y = 0; y <= countY; y++) { 227909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint monoX[5]; 228909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX); 229909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int x = 0; x <= countX; x++) { 230909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->clipMonoQuad(&monoX[x * 2], clip); 231909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 232909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 233909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 234909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 235909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 236909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 237909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com *fCurrVerb = SkPath::kDone_Verb; 238909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint = fPoints; 239909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb = fVerbs; 240909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return SkPath::kDone_Verb != fVerbs[0]; 241909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 242909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 243909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/////////////////////////////////////////////////////////////////////////////// 244909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 24505424f77fa8812b6c9e3a21def954e2c8971886acaryclarkstatic SkScalar mono_cubic_closestT(const SkScalar src[], SkScalar x) { 2467d173403f47bb85cfd5c42b69c734668e25e47f9caryclark SkScalar t = 0.5f; 2477d173403f47bb85cfd5c42b69c734668e25e47f9caryclark SkScalar lastT; 2487d173403f47bb85cfd5c42b69c734668e25e47f9caryclark SkScalar bestT SK_INIT_TO_AVOID_WARNING; 2497d173403f47bb85cfd5c42b69c734668e25e47f9caryclark SkScalar step = 0.25f; 25005424f77fa8812b6c9e3a21def954e2c8971886acaryclark SkScalar D = src[0]; 25105424f77fa8812b6c9e3a21def954e2c8971886acaryclark SkScalar A = src[6] + 3*(src[2] - src[4]) - D; 25205424f77fa8812b6c9e3a21def954e2c8971886acaryclark SkScalar B = 3*(src[4] - src[2] - src[2] + D); 25305424f77fa8812b6c9e3a21def954e2c8971886acaryclark SkScalar C = 3*(src[2] - D); 2547d173403f47bb85cfd5c42b69c734668e25e47f9caryclark x -= D; 2557d173403f47bb85cfd5c42b69c734668e25e47f9caryclark SkScalar closest = SK_ScalarMax; 2567d173403f47bb85cfd5c42b69c734668e25e47f9caryclark do { 2577d173403f47bb85cfd5c42b69c734668e25e47f9caryclark SkScalar loc = ((A * t + B) * t + C) * t; 2587d173403f47bb85cfd5c42b69c734668e25e47f9caryclark SkScalar dist = SkScalarAbs(loc - x); 2597d173403f47bb85cfd5c42b69c734668e25e47f9caryclark if (closest > dist) { 2607d173403f47bb85cfd5c42b69c734668e25e47f9caryclark closest = dist; 2617d173403f47bb85cfd5c42b69c734668e25e47f9caryclark bestT = t; 2627d173403f47bb85cfd5c42b69c734668e25e47f9caryclark } 2637d173403f47bb85cfd5c42b69c734668e25e47f9caryclark lastT = t; 2647d173403f47bb85cfd5c42b69c734668e25e47f9caryclark t += loc < x ? step : -step; 2657d173403f47bb85cfd5c42b69c734668e25e47f9caryclark step *= 0.5f; 2667d173403f47bb85cfd5c42b69c734668e25e47f9caryclark } while (closest > 0.25f && lastT != t); 26705424f77fa8812b6c9e3a21def954e2c8971886acaryclark return bestT; 26805424f77fa8812b6c9e3a21def954e2c8971886acaryclark} 26905424f77fa8812b6c9e3a21def954e2c8971886acaryclark 27005424f77fa8812b6c9e3a21def954e2c8971886acaryclarkstatic void chop_mono_cubic_at_y(SkPoint src[4], SkScalar y, SkPoint dst[7]) { 27105424f77fa8812b6c9e3a21def954e2c8971886acaryclark if (SkChopMonoCubicAtY(src, y, dst)) { 27205424f77fa8812b6c9e3a21def954e2c8971886acaryclark return; 27305424f77fa8812b6c9e3a21def954e2c8971886acaryclark } 27405424f77fa8812b6c9e3a21def954e2c8971886acaryclark SkChopCubicAt(src, dst, mono_cubic_closestT(&src->fY, y)); 27505424f77fa8812b6c9e3a21def954e2c8971886acaryclark} 27605424f77fa8812b6c9e3a21def954e2c8971886acaryclark 27705424f77fa8812b6c9e3a21def954e2c8971886acaryclark// Modify pts[] in place so that it is clipped in Y to the clip rect 27805424f77fa8812b6c9e3a21def954e2c8971886acaryclarkstatic void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) { 27905424f77fa8812b6c9e3a21def954e2c8971886acaryclark 28005424f77fa8812b6c9e3a21def954e2c8971886acaryclark // are we partially above 28105424f77fa8812b6c9e3a21def954e2c8971886acaryclark if (pts[0].fY < clip.fTop) { 28205424f77fa8812b6c9e3a21def954e2c8971886acaryclark SkPoint tmp[7]; 28305424f77fa8812b6c9e3a21def954e2c8971886acaryclark chop_mono_cubic_at_y(pts, clip.fTop, tmp); 284158fabb071f2cb275bc88c139e88e8eb3bf140eereed 285158fabb071f2cb275bc88c139e88e8eb3bf140eereed /* 286158fabb071f2cb275bc88c139e88e8eb3bf140eereed * For a large range in the points, we can do a poor job of chopping, such that the t 287158fabb071f2cb275bc88c139e88e8eb3bf140eereed * we computed resulted in the lower cubic still being partly above the clip. 288158fabb071f2cb275bc88c139e88e8eb3bf140eereed * 289158fabb071f2cb275bc88c139e88e8eb3bf140eereed * If just the first or first 2 Y values are above the fTop, we can just smash them 290158fabb071f2cb275bc88c139e88e8eb3bf140eereed * down. If the first 3 Ys are above fTop, we can't smash all 3, as that can really 291158fabb071f2cb275bc88c139e88e8eb3bf140eereed * distort the cubic. In this case, we take the first output (tmp[3..6] and treat it as 292158fabb071f2cb275bc88c139e88e8eb3bf140eereed * a guess, and re-chop against fTop. Then we fall through to checking if we need to 293158fabb071f2cb275bc88c139e88e8eb3bf140eereed * smash the first 1 or 2 Y values. 294158fabb071f2cb275bc88c139e88e8eb3bf140eereed */ 295158fabb071f2cb275bc88c139e88e8eb3bf140eereed if (tmp[3].fY < clip.fTop && tmp[4].fY < clip.fTop && tmp[5].fY < clip.fTop) { 296158fabb071f2cb275bc88c139e88e8eb3bf140eereed SkPoint tmp2[4]; 297158fabb071f2cb275bc88c139e88e8eb3bf140eereed memcpy(tmp2, &tmp[3].fX, 4 * sizeof(SkPoint)); 298158fabb071f2cb275bc88c139e88e8eb3bf140eereed chop_mono_cubic_at_y(tmp2, clip.fTop, tmp); 299158fabb071f2cb275bc88c139e88e8eb3bf140eereed } 300158fabb071f2cb275bc88c139e88e8eb3bf140eereed 30105424f77fa8812b6c9e3a21def954e2c8971886acaryclark // tmp[3, 4].fY should all be to the below clip.fTop. 302158fabb071f2cb275bc88c139e88e8eb3bf140eereed // Since we can't trust the numerics of the chopper, we force those conditions now 30305424f77fa8812b6c9e3a21def954e2c8971886acaryclark tmp[3].fY = clip.fTop; 30405424f77fa8812b6c9e3a21def954e2c8971886acaryclark clamp_ge(tmp[4].fY, clip.fTop); 30505424f77fa8812b6c9e3a21def954e2c8971886acaryclark 30605424f77fa8812b6c9e3a21def954e2c8971886acaryclark pts[0] = tmp[3]; 30705424f77fa8812b6c9e3a21def954e2c8971886acaryclark pts[1] = tmp[4]; 30805424f77fa8812b6c9e3a21def954e2c8971886acaryclark pts[2] = tmp[5]; 30905424f77fa8812b6c9e3a21def954e2c8971886acaryclark } 31005424f77fa8812b6c9e3a21def954e2c8971886acaryclark 31105424f77fa8812b6c9e3a21def954e2c8971886acaryclark // are we partially below 31205424f77fa8812b6c9e3a21def954e2c8971886acaryclark if (pts[3].fY > clip.fBottom) { 31305424f77fa8812b6c9e3a21def954e2c8971886acaryclark SkPoint tmp[7]; 31405424f77fa8812b6c9e3a21def954e2c8971886acaryclark chop_mono_cubic_at_y(pts, clip.fBottom, tmp); 31505424f77fa8812b6c9e3a21def954e2c8971886acaryclark tmp[3].fY = clip.fBottom; 31605424f77fa8812b6c9e3a21def954e2c8971886acaryclark clamp_le(tmp[2].fY, clip.fBottom); 31705424f77fa8812b6c9e3a21def954e2c8971886acaryclark 31805424f77fa8812b6c9e3a21def954e2c8971886acaryclark pts[1] = tmp[1]; 31905424f77fa8812b6c9e3a21def954e2c8971886acaryclark pts[2] = tmp[2]; 32005424f77fa8812b6c9e3a21def954e2c8971886acaryclark pts[3] = tmp[3]; 32105424f77fa8812b6c9e3a21def954e2c8971886acaryclark } 32205424f77fa8812b6c9e3a21def954e2c8971886acaryclark} 32305424f77fa8812b6c9e3a21def954e2c8971886acaryclark 32405424f77fa8812b6c9e3a21def954e2c8971886acaryclarkstatic void chop_mono_cubic_at_x(SkPoint src[4], SkScalar x, SkPoint dst[7]) { 32505424f77fa8812b6c9e3a21def954e2c8971886acaryclark if (SkChopMonoCubicAtX(src, x, dst)) { 32605424f77fa8812b6c9e3a21def954e2c8971886acaryclark return; 32705424f77fa8812b6c9e3a21def954e2c8971886acaryclark } 32805424f77fa8812b6c9e3a21def954e2c8971886acaryclark SkChopCubicAt(src, dst, mono_cubic_closestT(&src->fX, x)); 3297d173403f47bb85cfd5c42b69c734668e25e47f9caryclark} 3307d173403f47bb85cfd5c42b69c734668e25e47f9caryclark 331909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com// srcPts[] must be monotonic in X and Y 332909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) { 333909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint pts[4]; 334909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com bool reverse = sort_increasing_Y(pts, src, 4); 335fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 336909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we completely above or below 337909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) { 338909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return; 339909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 34015161620bee33efcb706685486c9ce0fb51a72bbreed@android.com 341909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // Now chop so that pts is contained within clip in Y 342909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com chop_cubic_in_Y(pts, clip); 34315161620bee33efcb706685486c9ce0fb51a72bbreed@android.com 344909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fX > pts[3].fX) { 345909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkTSwap<SkPoint>(pts[0], pts[3]); 346909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkTSwap<SkPoint>(pts[1], pts[2]); 347909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com reverse = !reverse; 348909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 349fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 350909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // Now chop in X has needed, and record the segments 351fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 352909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[3].fX <= clip.fLeft) { // wholly to the left 353909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 354909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return; 355909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 356909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fX >= clip.fRight) { // wholly to the right 35731223e0cb74f47f63b094520a9830c525b72fe87reed if (!this->canCullToTheRight()) { 35831223e0cb74f47f63b094520a9830c525b72fe87reed this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 35931223e0cb74f47f63b094520a9830c525b72fe87reed } 360909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return; 361909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 3626da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com 363909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially to the left 364909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fX < clip.fLeft) { 365dc3088570f945ed0ede84f0af0016eedc267dda3reed SkPoint tmp[7]; 3667d173403f47bb85cfd5c42b69c734668e25e47f9caryclark chop_mono_cubic_at_x(pts, clip.fLeft, tmp); 3677d173403f47bb85cfd5c42b69c734668e25e47f9caryclark this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse); 3687d173403f47bb85cfd5c42b69c734668e25e47f9caryclark 3697d173403f47bb85cfd5c42b69c734668e25e47f9caryclark // tmp[3, 4].fX should all be to the right of clip.fLeft. 3707d173403f47bb85cfd5c42b69c734668e25e47f9caryclark // Since we can't trust the numerics of 3717d173403f47bb85cfd5c42b69c734668e25e47f9caryclark // the chopper, we force those conditions now 3727d173403f47bb85cfd5c42b69c734668e25e47f9caryclark tmp[3].fX = clip.fLeft; 3737d173403f47bb85cfd5c42b69c734668e25e47f9caryclark clamp_ge(tmp[4].fX, clip.fLeft); 3747d173403f47bb85cfd5c42b69c734668e25e47f9caryclark 3757d173403f47bb85cfd5c42b69c734668e25e47f9caryclark pts[0] = tmp[3]; 3767d173403f47bb85cfd5c42b69c734668e25e47f9caryclark pts[1] = tmp[4]; 3777d173403f47bb85cfd5c42b69c734668e25e47f9caryclark pts[2] = tmp[5]; 378909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 379fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 380909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially to the right 381909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[3].fX > clip.fRight) { 382dc3088570f945ed0ede84f0af0016eedc267dda3reed SkPoint tmp[7]; 3837d173403f47bb85cfd5c42b69c734668e25e47f9caryclark chop_mono_cubic_at_x(pts, clip.fRight, tmp); 3847d173403f47bb85cfd5c42b69c734668e25e47f9caryclark tmp[3].fX = clip.fRight; 3857d173403f47bb85cfd5c42b69c734668e25e47f9caryclark clamp_le(tmp[2].fX, clip.fRight); 386a90aa534986ffa2019b6a99260bbba086a5c608ereed@google.com 3877d173403f47bb85cfd5c42b69c734668e25e47f9caryclark this->appendCubic(tmp, reverse); 3887d173403f47bb85cfd5c42b69c734668e25e47f9caryclark this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse); 389909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { // wholly inside the clip 390909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendCubic(pts, reverse); 391909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 392909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 393909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 394c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reedstatic SkRect compute_cubic_bounds(const SkPoint pts[4]) { 395c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed SkRect r; 396c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed r.set(pts, 4); 397c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed return r; 398c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed} 39970509762c88df911c58c3984e6b1e673b5ecaeacreed 400c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reedstatic bool too_big_for_reliable_float_math(const SkRect& r) { 401c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // limit set as the largest float value for which we can still reliably compute things like 402c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // - chopping at XY extrema 403c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // - chopping at Y or X values for clipping 404c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // 405c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // Current value chosen just by experiment. Larger (and still succeeds) is always better. 406c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // 407c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed const SkScalar limit = 1 << 22; 408c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed return r.fLeft < -limit || r.fTop < -limit || r.fRight > limit || r.fBottom > limit; 40970509762c88df911c58c3984e6b1e673b5ecaeacreed} 41070509762c88df911c58c3984e6b1e673b5ecaeacreed 411909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.combool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) { 412909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint = fPoints; 413909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb = fVerbs; 414fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 415c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed const SkRect bounds = compute_cubic_bounds(srcPts); 416c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // check if we're clipped out vertically 417c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed if (bounds.fBottom > clip.fTop && bounds.fTop < clip.fBottom) { 418c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed if (too_big_for_reliable_float_math(bounds)) { 419c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // can't safely clip the cubic, so we give up and draw a line (which we can safely clip) 420c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // 421c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // If we rewrote chopcubicat*extrema and chopmonocubic using doubles, we could very 422c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // likely always handle the cubic safely, but (it seems) at a big loss in speed, so 423c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // we'd only want to take that alternate impl if needed. Perhaps a TODO to try it. 424c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed // 425c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed return this->clipLine(srcPts[0], srcPts[3], clip); 426c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed } else { 427c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed SkPoint monoY[10]; 428c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed int countY = SkChopCubicAtYExtrema(srcPts, monoY); 429c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed for (int y = 0; y <= countY; y++) { 430c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed SkPoint monoX[10]; 431c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX); 432c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed for (int x = 0; x <= countX; x++) { 433c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed this->clipMonoCubic(&monoX[x * 3], clip); 434c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 435c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 436c121a8849cf6d1d535e69fc3836c5720e0372a28Mike Reed } 437909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 438909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 439909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 440fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 441909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com *fCurrVerb = SkPath::kDone_Verb; 442909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint = fPoints; 443909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb = fVerbs; 444909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return SkPath::kDone_Verb != fVerbs[0]; 445909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 446909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 447909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/////////////////////////////////////////////////////////////////////////////// 448909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 4495baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reedvoid SkEdgeClipper::appendLine(SkPoint p0, SkPoint p1) { 4505baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed *fCurrVerb++ = SkPath::kLine_Verb; 4515baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed fCurrPoint[0] = p0; 4525baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed fCurrPoint[1] = p1; 4535baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed fCurrPoint += 2; 4545baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed} 4555baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed 456909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1, 457909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com bool reverse) { 458909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com *fCurrVerb++ = SkPath::kLine_Verb; 459fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 460909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (reverse) { 461909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkTSwap<SkScalar>(y0, y1); 462909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 463909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[0].set(x, y0); 464909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[1].set(x, y1); 465909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint += 2; 466909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 467909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 468909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) { 469909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com *fCurrVerb++ = SkPath::kQuad_Verb; 470fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 471909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (reverse) { 472909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[0] = pts[2]; 473909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[2] = pts[0]; 474909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 475909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[0] = pts[0]; 476909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[2] = pts[2]; 477909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 478909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[1] = pts[1]; 479909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint += 3; 480909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 481909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 482909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) { 483909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com *fCurrVerb++ = SkPath::kCubic_Verb; 484fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 485909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (reverse) { 486909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i < 4; i++) { 487909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[i] = pts[3 - i]; 488909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 489909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 490909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint)); 491909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 492909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint += 4; 493909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 494909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 495909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comSkPath::Verb SkEdgeClipper::next(SkPoint pts[]) { 496909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPath::Verb verb = *fCurrVerb; 497909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 498909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com switch (verb) { 499909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kLine_Verb: 500909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint)); 501909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint += 2; 502909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb += 1; 503909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 504909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kQuad_Verb: 505909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint)); 506909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint += 3; 507909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb += 1; 508909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 509909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kCubic_Verb: 510909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint)); 511909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint += 4; 512909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb += 1; 513909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 514909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kDone_Verb: 515909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 516909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com default: 5170c00f21fee3f5cfa3aa7e5d46ff94cb8cf340451tomhudson@google.com SkDEBUGFAIL("unexpected verb in quadclippper2 iter"); 518909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 519909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 520909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return verb; 521909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 522909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 523909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/////////////////////////////////////////////////////////////////////////////// 524909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 525909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#ifdef SK_DEBUG 526909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic void assert_monotonic(const SkScalar coord[], int count) { 527909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (coord[0] > coord[(count - 1) * 2]) { 528909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 1; i < count; i++) { 529909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]); 530909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 531909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else if (coord[0] < coord[(count - 1) * 2]) { 532909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 1; i < count; i++) { 533909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]); 534909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 535909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 536909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 1; i < count; i++) { 537909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(coord[2 * (i - 1)] == coord[i * 2]); 538909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 539909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 540909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 541909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 542909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid sk_assert_monotonic_y(const SkPoint pts[], int count) { 543909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (count > 1) { 544909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com assert_monotonic(&pts[0].fY, count); 545909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 546909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 547909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 548909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid sk_assert_monotonic_x(const SkPoint pts[], int count) { 549909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (count > 1) { 550909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com assert_monotonic(&pts[0].fX, count); 551909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 552909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 553909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#endif 554