SkEdgeClipper.cpp revision a90aa534986ffa2019b6a99260bbba086a5c608e
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 2909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2009 The Android Open Source Project 4909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 7909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com */ 8909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 9ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 10909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkEdgeClipper.h" 11909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkGeometry.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 46909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/////////////////////////////////////////////////////////////////////////////// 47909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 48909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2, 49909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar target, SkScalar* t) { 50909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2 51909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com * We solve for t, using quadratic equation, hence we have to rearrange 52909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com * our cooefficents to look like At^2 + Bt + C 53909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com */ 54909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar A = c0 - c1 - c1 + c2; 55909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar B = 2*(c1 - c0); 56909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar C = c0 - target; 57909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 58909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar roots[2]; // we only expect one, but make room for 2 for safety 59909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int count = SkFindUnitQuadRoots(A, B, C, roots); 60909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (count) { 61909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com *t = roots[0]; 62909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return true; 63909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 64909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return false; 65909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 66909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 67909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) { 68909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t); 69909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 70909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 71909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic bool chopMonoQuadAtX(SkPoint pts[3], SkScalar x, SkScalar* t) { 72909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return chopMonoQuadAt(pts[0].fX, pts[1].fX, pts[2].fX, x, t); 73909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 74909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 75909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com// Modify pts[] in place so that it is clipped in Y to the clip rect 76909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic void chop_quad_in_Y(SkPoint pts[3], const SkRect& clip) { 77909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar t; 78909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint tmp[5]; // for SkChopQuadAt 79909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 80909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially above 81909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fY < clip.fTop) { 82909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (chopMonoQuadAtY(pts, clip.fTop, &t)) { 83909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // take the 2nd chopped quad 84909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkChopQuadAt(pts, tmp, t); 85e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com // clamp to clean up imprecise numerics in the chop 86e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com tmp[2].fY = clip.fTop; 87909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com clamp_ge(tmp[3].fY, clip.fTop); 88e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com 89909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[0] = tmp[2]; 90909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[1] = tmp[3]; 91909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 92909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // if chopMonoQuadAtY failed, then we may have hit inexact numerics 93909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // so we just clamp against the top 94909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i < 3; i++) { 95909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[i].fY < clip.fTop) { 96909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[i].fY = clip.fTop; 97909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 98909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 99909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 100909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 101909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 102909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially below 103909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[2].fY > clip.fBottom) { 104909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (chopMonoQuadAtY(pts, clip.fBottom, &t)) { 105909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkChopQuadAt(pts, tmp, t); 106e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com // clamp to clean up imprecise numerics in the chop 107909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com clamp_le(tmp[1].fY, clip.fBottom); 108e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com tmp[2].fY = clip.fBottom; 109e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com 110909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[1] = tmp[1]; 111909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[2] = tmp[2]; 112909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 113909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // if chopMonoQuadAtY failed, then we may have hit inexact numerics 114909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // so we just clamp against the bottom 115909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i < 3; i++) { 116909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[i].fY > clip.fBottom) { 117909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[i].fY = clip.fBottom; 118909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 119909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 120909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 121909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 122909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 123909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 124909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com// srcPts[] must be monotonic in X and Y 125909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeClipper::clipMonoQuad(const SkPoint srcPts[3], const SkRect& clip) { 126909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint pts[3]; 127909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com bool reverse = sort_increasing_Y(pts, srcPts, 3); 128909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 129909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we completely above or below 130909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[2].fY <= clip.fTop || pts[0].fY >= clip.fBottom) { 131909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return; 132909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 133909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 134909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // Now chop so that pts is contained within clip in Y 135909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com chop_quad_in_Y(pts, clip); 136909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 137909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fX > pts[2].fX) { 138909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkTSwap<SkPoint>(pts[0], pts[2]); 139909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com reverse = !reverse; 140909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 141909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(pts[0].fX <= pts[1].fX); 142909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(pts[1].fX <= pts[2].fX); 143909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 144909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // Now chop in X has needed, and record the segments 145909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 146909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[2].fX <= clip.fLeft) { // wholly to the left 147909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse); 148909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return; 149909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 150909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fX >= clip.fRight) { // wholly to the right 151909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse); 152909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return; 153909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 154909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 155909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar t; 156909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint tmp[5]; // for SkChopQuadAt 157909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 158909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially to the left 159909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fX < clip.fLeft) { 160909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (chopMonoQuadAtX(pts, clip.fLeft, &t)) { 161909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkChopQuadAt(pts, tmp, t); 162909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fLeft, tmp[0].fY, tmp[2].fY, reverse); 163e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com // clamp to clean up imprecise numerics in the chop 164e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com tmp[2].fX = clip.fLeft; 165909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com clamp_ge(tmp[3].fX, clip.fLeft); 166e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com 167909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[0] = tmp[2]; 168909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[1] = tmp[3]; 169909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 170909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // if chopMonoQuadAtY failed, then we may have hit inexact numerics 171909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // so we just clamp against the left 172909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse); 173181172d5642fce4a4c1d339a6e3c5e4a8079b11areed@android.com return; 174909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 175909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 176909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 177909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially to the right 178909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[2].fX > clip.fRight) { 179909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (chopMonoQuadAtX(pts, clip.fRight, &t)) { 180909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkChopQuadAt(pts, tmp, t); 181e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com // clamp to clean up imprecise numerics in the chop 182909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com clamp_le(tmp[1].fX, clip.fRight); 183e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com tmp[2].fX = clip.fRight; 184e01403096cc8fc15217d7de08c476c2056d8b9d0reed@google.com 185909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendQuad(tmp, reverse); 186909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fRight, tmp[2].fY, tmp[4].fY, reverse); 187909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 188909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // if chopMonoQuadAtY failed, then we may have hit inexact numerics 189909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // so we just clamp against the right 1903f0785e0c675c906c0bd704702e122149c5ee951reed@android.com this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse); 191909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 192909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { // wholly inside the clip 193909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendQuad(pts, reverse); 194909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 195909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 196909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 197909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.combool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) { 198909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint = fPoints; 199909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb = fVerbs; 200909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 201909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkRect bounds; 202909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com bounds.set(srcPts, 3); 203909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 204909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (!quick_reject(bounds, clip)) { 205909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint monoY[5]; 206909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int countY = SkChopQuadAtYExtrema(srcPts, monoY); 207909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int y = 0; y <= countY; y++) { 208909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint monoX[5]; 209909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX); 210909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int x = 0; x <= countX; x++) { 211909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->clipMonoQuad(&monoX[x * 2], clip); 212909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 213909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 214909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 215909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 216909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 217909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 218909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com *fCurrVerb = SkPath::kDone_Verb; 219909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint = fPoints; 220909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb = fVerbs; 221909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return SkPath::kDone_Verb != fVerbs[0]; 222909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 223909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 224909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/////////////////////////////////////////////////////////////////////////////// 225909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 226909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C, 227909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar D, SkScalar t) { 228909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); 229909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 230909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 231909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/* Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the 232909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com t value such that cubic(t) = target 233909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com */ 234909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic bool chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3, 235909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar target, SkScalar* t) { 236909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3); 237909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(c0 < target && target < c3); 238909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 239a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com SkScalar D = c0 - target; 240909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar A = c3 + 3*(c1 - c2) - c0; 241909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar B = 3*(c2 - c1 - c1 + c0); 242909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar C = 3*(c1 - c0); 243909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 244a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com const SkScalar TOLERANCE = SK_Scalar1 / 4096; 245909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar minT = 0; 246909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkScalar maxT = SK_Scalar1; 247a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com SkScalar mid; 248a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com int i; 249a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com for (i = 0; i < 16; i++) { 250a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com mid = SkScalarAve(minT, maxT); 251a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com SkScalar delta = eval_cubic_coeff(A, B, C, D, mid); 252a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com if (delta < 0) { 253909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com minT = mid; 254a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com delta = -delta; 255909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 256909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com maxT = mid; 257909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 258a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com if (delta < TOLERANCE) { 259a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com break; 260a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com } 261909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 262a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com *t = mid; 263a3d901099d7d295cd7d9df4114e874d9ccfff447reed@android.com// SkDebugf("-- evalCubicAt %d delta %g\n", i, eval_cubic_coeff(A, B, C, D, *t)); 264909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return true; 265909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 266909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 267909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic bool chopMonoCubicAtY(SkPoint pts[4], SkScalar y, SkScalar* t) { 268909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, t); 269909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 270909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 271909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic bool chopMonoCubicAtX(SkPoint pts[4], SkScalar x, SkScalar* t) { 272909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return chopMonoCubicAt(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, x, t); 273909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 274909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 275909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com// Modify pts[] in place so that it is clipped in Y to the clip rect 276909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) { 277909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 278909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially above 279909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fY < clip.fTop) { 2806da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com SkScalar t; 281909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (chopMonoCubicAtY(pts, clip.fTop, &t)) { 2826da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com SkPoint tmp[7]; 283909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkChopCubicAt(pts, tmp, t); 2846da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com 2856da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com // tmp[3, 4, 5].fY should all be to the below clip.fTop, and 2866da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com // still be monotonic in Y. Since we can't trust the numerics of 2876da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com // the chopper, we force those conditions now 28815161620bee33efcb706685486c9ce0fb51a72bbreed@android.com tmp[3].fY = clip.fTop; 289a90aa534986ffa2019b6a99260bbba086a5c608ereed@google.com clamp_ge(tmp[4].fY, clip.fTop); 290a90aa534986ffa2019b6a99260bbba086a5c608ereed@google.com clamp_ge(tmp[5].fY, tmp[4].fY); 2916da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com 292909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[0] = tmp[3]; 293909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[1] = tmp[4]; 294909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[2] = tmp[5]; 295909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 296909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // if chopMonoCubicAtY failed, then we may have hit inexact numerics 297909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // so we just clamp against the top 298909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i < 4; i++) { 299909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com clamp_ge(pts[i].fY, clip.fTop); 300909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 301909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 302909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 303909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 304909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially below 305909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[3].fY > clip.fBottom) { 3066da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com SkScalar t; 307909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (chopMonoCubicAtY(pts, clip.fBottom, &t)) { 3086da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com SkPoint tmp[7]; 309909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkChopCubicAt(pts, tmp, t); 310a90aa534986ffa2019b6a99260bbba086a5c608ereed@google.com tmp[3].fY = clip.fBottom; 311909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com clamp_le(tmp[2].fY, clip.fBottom); 312a90aa534986ffa2019b6a99260bbba086a5c608ereed@google.com clamp_le(tmp[1].fY, tmp[2].fY); 313a90aa534986ffa2019b6a99260bbba086a5c608ereed@google.com 314909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[1] = tmp[1]; 315909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[2] = tmp[2]; 316909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[3] = tmp[3]; 317909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 318909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // if chopMonoCubicAtY failed, then we may have hit inexact numerics 319909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // so we just clamp against the bottom 320909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i < 4; i++) { 321909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com clamp_le(pts[i].fY, clip.fBottom); 322909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 323909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 324909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 325909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 326909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 327909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com// srcPts[] must be monotonic in X and Y 328909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) { 329909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint pts[4]; 330909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com bool reverse = sort_increasing_Y(pts, src, 4); 331909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 332909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we completely above or below 333909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) { 334909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return; 335909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 33615161620bee33efcb706685486c9ce0fb51a72bbreed@android.com 337909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // Now chop so that pts is contained within clip in Y 338909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com chop_cubic_in_Y(pts, clip); 33915161620bee33efcb706685486c9ce0fb51a72bbreed@android.com 340909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fX > pts[3].fX) { 341909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkTSwap<SkPoint>(pts[0], pts[3]); 342909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkTSwap<SkPoint>(pts[1], pts[2]); 343909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com reverse = !reverse; 344909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 345909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 346909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // Now chop in X has needed, and record the segments 347909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 348909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[3].fX <= clip.fLeft) { // wholly to the left 349909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 350909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return; 351909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 352909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fX >= clip.fRight) { // wholly to the right 353909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 354909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return; 355909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 3566da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com 357909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially to the left 358909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[0].fX < clip.fLeft) { 3596da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com SkScalar t; 360909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (chopMonoCubicAtX(pts, clip.fLeft, &t)) { 3616da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com SkPoint tmp[7]; 362909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkChopCubicAt(pts, tmp, t); 363909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse); 3646da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com 3656da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com // tmp[3, 4, 5].fX should all be to the right of clip.fLeft, and 3666da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com // still be monotonic in X. Since we can't trust the numerics of 3676da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com // the chopper, we force those conditions now 3686da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com tmp[3].fX = clip.fLeft; 369a90aa534986ffa2019b6a99260bbba086a5c608ereed@google.com clamp_ge(tmp[4].fX, clip.fLeft); 370a90aa534986ffa2019b6a99260bbba086a5c608ereed@google.com clamp_ge(tmp[5].fX, tmp[4].fX); 3716da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com 372909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[0] = tmp[3]; 373909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[1] = tmp[4]; 374909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com pts[2] = tmp[5]; 375909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 376909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // if chopMonocubicAtY failed, then we may have hit inexact numerics 377909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // so we just clamp against the left 378909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 379181172d5642fce4a4c1d339a6e3c5e4a8079b11areed@android.com return; 380909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 381909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 382909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 383909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // are we partially to the right 384909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (pts[3].fX > clip.fRight) { 3856da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com SkScalar t; 386909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (chopMonoCubicAtX(pts, clip.fRight, &t)) { 3876da3d1757cfee75c25a86b580834dc49d8b53f05reed@google.com SkPoint tmp[7]; 388909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkChopCubicAt(pts, tmp, t); 389a90aa534986ffa2019b6a99260bbba086a5c608ereed@google.com tmp[3].fX = clip.fRight; 390909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com clamp_le(tmp[2].fX, clip.fRight); 391a90aa534986ffa2019b6a99260bbba086a5c608ereed@google.com clamp_le(tmp[1].fX, tmp[2].fX); 392a90aa534986ffa2019b6a99260bbba086a5c608ereed@google.com 393909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendCubic(tmp, reverse); 394909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse); 395909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 396909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // if chopMonoCubicAtX failed, then we may have hit inexact numerics 397909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // so we just clamp against the right 398909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 399909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 400909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { // wholly inside the clip 401909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->appendCubic(pts, reverse); 402909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 403909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 404909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 405909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.combool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) { 406909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint = fPoints; 407909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb = fVerbs; 408909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 409909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkRect bounds; 410909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com bounds.set(srcPts, 4); 411909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 412909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (!quick_reject(bounds, clip)) { 413909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint monoY[10]; 414909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int countY = SkChopCubicAtYExtrema(srcPts, monoY); 415909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int y = 0; y <= countY; y++) { 416909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // sk_assert_monotonic_y(&monoY[y * 3], 4); 417909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint monoX[10]; 418909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX); 419909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int x = 0; x <= countX; x++) { 420909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // sk_assert_monotonic_y(&monoX[x * 3], 4); 421909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // sk_assert_monotonic_x(&monoX[x * 3], 4); 422909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->clipMonoCubic(&monoX[x * 3], clip); 423909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 424909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 425909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 426909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 427909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 428909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 429909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com *fCurrVerb = SkPath::kDone_Verb; 430909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint = fPoints; 431909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb = fVerbs; 432909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return SkPath::kDone_Verb != fVerbs[0]; 433909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 434909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 435909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/////////////////////////////////////////////////////////////////////////////// 436909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 437909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1, 438909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com bool reverse) { 439909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com *fCurrVerb++ = SkPath::kLine_Verb; 440909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 441909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (reverse) { 442909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkTSwap<SkScalar>(y0, y1); 443909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 444909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[0].set(x, y0); 445909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[1].set(x, y1); 446909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint += 2; 447909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 448909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 449909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) { 450909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com *fCurrVerb++ = SkPath::kQuad_Verb; 451909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 452909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (reverse) { 453909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[0] = pts[2]; 454909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[2] = pts[0]; 455909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 456909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[0] = pts[0]; 457909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[2] = pts[2]; 458909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 459909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[1] = pts[1]; 460909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint += 3; 461909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 462909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 463909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) { 464909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com *fCurrVerb++ = SkPath::kCubic_Verb; 465909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 466909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (reverse) { 467909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i < 4; i++) { 468909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint[i] = pts[3 - i]; 469909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 470909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 471909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint)); 472909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 473909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint += 4; 474909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 475909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 476909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comSkPath::Verb SkEdgeClipper::next(SkPoint pts[]) { 477909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPath::Verb verb = *fCurrVerb; 478909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 479909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com switch (verb) { 480909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kLine_Verb: 481909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint)); 482909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint += 2; 483909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb += 1; 484909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 485909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kQuad_Verb: 486909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint)); 487909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint += 3; 488909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb += 1; 489909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 490909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kCubic_Verb: 491909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint)); 492909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrPoint += 4; 493909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fCurrVerb += 1; 494909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 495909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kDone_Verb: 496909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 497909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com default: 4980c00f21fee3f5cfa3aa7e5d46ff94cb8cf340451tomhudson@google.com SkDEBUGFAIL("unexpected verb in quadclippper2 iter"); 499909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 500909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 501909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return verb; 502909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 503909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 504909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/////////////////////////////////////////////////////////////////////////////// 505909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 506909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#ifdef SK_DEBUG 507909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic void assert_monotonic(const SkScalar coord[], int count) { 508909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (coord[0] > coord[(count - 1) * 2]) { 509909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 1; i < count; i++) { 510909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]); 511909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 512909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else if (coord[0] < coord[(count - 1) * 2]) { 513909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 1; i < count; i++) { 514909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]); 515909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 516909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 517909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 1; i < count; i++) { 518909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkASSERT(coord[2 * (i - 1)] == coord[i * 2]); 519909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 520909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 521909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 522909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 523909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid sk_assert_monotonic_y(const SkPoint pts[], int count) { 524909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (count > 1) { 525909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com assert_monotonic(&pts[0].fY, count); 526909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 527909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 528909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 529909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid sk_assert_monotonic_x(const SkPoint pts[], int count) { 530909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (count > 1) { 531909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com assert_monotonic(&pts[0].fX, count); 532909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 533909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 534909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#endif 535