180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2009 The Android Open Source Project 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkEdgeClipper.h" 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkGeometry.h" 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool quick_reject(const SkRect& bounds, const SkRect& clip) { 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return bounds.fTop >= clip.fBottom || bounds.fBottom <= clip.fTop; 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic inline void clamp_le(SkScalar& value, SkScalar max) { 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (value > max) { 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru value = max; 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic inline void clamp_ge(SkScalar& value, SkScalar min) { 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (value < min) { 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru value = min; 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* src[] must be monotonic in Y. This routine copies src into dst, and sorts 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru it to be increasing in Y. If it had to reverse the order of the points, 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru it returns true, otherwise it returns false 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool sort_increasing_Y(SkPoint dst[], const SkPoint src[], int count) { 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // we need the data to be monotonically increasing in Y 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (src[0].fY > src[count - 1].fY) { 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 0; i < count; i++) { 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru dst[i] = src[count - i - 1]; 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(dst, src, count * sizeof(SkPoint)); 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/////////////////////////////////////////////////////////////////////////////// 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2, 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar target, SkScalar* t) { 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * We solve for t, using quadratic equation, hence we have to rearrange 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * our cooefficents to look like At^2 + Bt + C 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar A = c0 - c1 - c1 + c2; 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar B = 2*(c1 - c0); 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar C = c0 - target; 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar roots[2]; // we only expect one, but make room for 2 for safety 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = SkFindUnitQuadRoots(A, B, C, roots); 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (count) { 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *t = roots[0]; 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) { 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t); 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool chopMonoQuadAtX(SkPoint pts[3], SkScalar x, SkScalar* t) { 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return chopMonoQuadAt(pts[0].fX, pts[1].fX, pts[2].fX, x, t); 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// Modify pts[] in place so that it is clipped in Y to the clip rect 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic void chop_quad_in_Y(SkPoint pts[3], const SkRect& clip) { 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t; 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint tmp[5]; // for SkChopQuadAt 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we partially above 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[0].fY < clip.fTop) { 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (chopMonoQuadAtY(pts, clip.fTop, &t)) { 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // take the 2nd chopped quad 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopQuadAt(pts, tmp, t); 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // clamp to clean up imprecise numerics in the chop 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp[2].fY = clip.fTop; 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru clamp_ge(tmp[3].fY, clip.fTop); 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[0] = tmp[2]; 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[1] = tmp[3]; 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if chopMonoQuadAtY failed, then we may have hit inexact numerics 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // so we just clamp against the top 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 0; i < 3; i++) { 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[i].fY < clip.fTop) { 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[i].fY = clip.fTop; 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we partially below 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[2].fY > clip.fBottom) { 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (chopMonoQuadAtY(pts, clip.fBottom, &t)) { 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopQuadAt(pts, tmp, t); 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // clamp to clean up imprecise numerics in the chop 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru clamp_le(tmp[1].fY, clip.fBottom); 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp[2].fY = clip.fBottom; 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[1] = tmp[1]; 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[2] = tmp[2]; 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if chopMonoQuadAtY failed, then we may have hit inexact numerics 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // so we just clamp against the bottom 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 0; i < 3; i++) { 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[i].fY > clip.fBottom) { 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[i].fY = clip.fBottom; 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 12380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// srcPts[] must be monotonic in X and Y 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkEdgeClipper::clipMonoQuad(const SkPoint srcPts[3], const SkRect& clip) { 12680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint pts[3]; 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool reverse = sort_increasing_Y(pts, srcPts, 3); 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we completely above or below 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[2].fY <= clip.fTop || pts[0].fY >= clip.fBottom) { 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 13280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 13380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Now chop so that pts is contained within clip in Y 13580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru chop_quad_in_Y(pts, clip); 13680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[0].fX > pts[2].fX) { 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTSwap<SkPoint>(pts[0], pts[2]); 13980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru reverse = !reverse; 14080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 14180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(pts[0].fX <= pts[1].fX); 14280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(pts[1].fX <= pts[2].fX); 14380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 14480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Now chop in X has needed, and record the segments 14580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 14680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[2].fX <= clip.fLeft) { // wholly to the left 14780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse); 14880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 14980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 15080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[0].fX >= clip.fRight) { // wholly to the right 15180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse); 15280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 15380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 15480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t; 15680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint tmp[5]; // for SkChopQuadAt 15780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we partially to the left 15980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[0].fX < clip.fLeft) { 16080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (chopMonoQuadAtX(pts, clip.fLeft, &t)) { 16180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopQuadAt(pts, tmp, t); 16280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendVLine(clip.fLeft, tmp[0].fY, tmp[2].fY, reverse); 16380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // clamp to clean up imprecise numerics in the chop 16480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp[2].fX = clip.fLeft; 16580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru clamp_ge(tmp[3].fX, clip.fLeft); 16680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 16780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[0] = tmp[2]; 16880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[1] = tmp[3]; 16980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 17080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if chopMonoQuadAtY failed, then we may have hit inexact numerics 17180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // so we just clamp against the left 17280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse); 17380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 17480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 17580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 17680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 17780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we partially to the right 17880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[2].fX > clip.fRight) { 17980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (chopMonoQuadAtX(pts, clip.fRight, &t)) { 18080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopQuadAt(pts, tmp, t); 18180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // clamp to clean up imprecise numerics in the chop 18280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru clamp_le(tmp[1].fX, clip.fRight); 18380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp[2].fX = clip.fRight; 18480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 18580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendQuad(tmp, reverse); 18680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendVLine(clip.fRight, tmp[2].fY, tmp[4].fY, reverse); 18780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 18880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if chopMonoQuadAtY failed, then we may have hit inexact numerics 18980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // so we just clamp against the right 19080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse); 19180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 19280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { // wholly inside the clip 19380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendQuad(pts, reverse); 19480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 19580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 19680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 19780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querubool SkEdgeClipper::clipQuad(const SkPoint srcPts[3], const SkRect& clip) { 19880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint = fPoints; 19980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrVerb = fVerbs; 20080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 20180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRect bounds; 20280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bounds.set(srcPts, 3); 20380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 20480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (!quick_reject(bounds, clip)) { 20580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint monoY[5]; 20680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int countY = SkChopQuadAtYExtrema(srcPts, monoY); 20780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int y = 0; y <= countY; y++) { 20880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint monoX[5]; 20980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX); 21080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int x = 0; x <= countX; x++) { 21180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->clipMonoQuad(&monoX[x * 2], clip); 21280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 21380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 21480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 21580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 21680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 21780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 21880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *fCurrVerb = SkPath::kDone_Verb; 21980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint = fPoints; 22080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrVerb = fVerbs; 22180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkPath::kDone_Verb != fVerbs[0]; 22280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 22380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 22480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/////////////////////////////////////////////////////////////////////////////// 22580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 22680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C, 22780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar D, SkScalar t) { 22880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); 22980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 23080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 23180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the 23280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru t value such that cubic(t) = target 23380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 23480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3, 23580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar target, SkScalar* t) { 23680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3); 23780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(c0 < target && target < c3); 23880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 23980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar D = c0 - target; 24080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar A = c3 + 3*(c1 - c2) - c0; 24180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar B = 3*(c2 - c1 - c1 + c0); 24280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar C = 3*(c1 - c0); 24380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 24480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const SkScalar TOLERANCE = SK_Scalar1 / 4096; 24580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar minT = 0; 24680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar maxT = SK_Scalar1; 24780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar mid; 248096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 249096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger // This is a lot of iterations. Is there a faster way? 250096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger for (int i = 0; i < 24; i++) { 25180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru mid = SkScalarAve(minT, maxT); 25280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar delta = eval_cubic_coeff(A, B, C, D, mid); 25380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (delta < 0) { 25480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru minT = mid; 25580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru delta = -delta; 25680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 25780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru maxT = mid; 25880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 25980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (delta < TOLERANCE) { 26080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru break; 26180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 26280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 26380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *t = mid; 26480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// SkDebugf("-- evalCubicAt %d delta %g\n", i, eval_cubic_coeff(A, B, C, D, *t)); 26580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 26680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 26780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 26880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool chopMonoCubicAtY(SkPoint pts[4], SkScalar y, SkScalar* t) { 26980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, t); 27080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 27180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 27280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic bool chopMonoCubicAtX(SkPoint pts[4], SkScalar x, SkScalar* t) { 27380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return chopMonoCubicAt(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, x, t); 27480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 27580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 27680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// Modify pts[] in place so that it is clipped in Y to the clip rect 27780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic void chop_cubic_in_Y(SkPoint pts[4], const SkRect& clip) { 27880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 27980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we partially above 28080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[0].fY < clip.fTop) { 28180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t; 28280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (chopMonoCubicAtY(pts, clip.fTop, &t)) { 28380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint tmp[7]; 28480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopCubicAt(pts, tmp, t); 28580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 286779bf8a99dc7f03e5c43b26d4b85d7920ce89aeeDerek Sollenberger // tmp[3, 4, 5].fY should all be to the below clip.fTop. 287779bf8a99dc7f03e5c43b26d4b85d7920ce89aeeDerek Sollenberger // Since we can't trust the numerics of 28880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // the chopper, we force those conditions now 28980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp[3].fY = clip.fTop; 29080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru clamp_ge(tmp[4].fY, clip.fTop); 291779bf8a99dc7f03e5c43b26d4b85d7920ce89aeeDerek Sollenberger clamp_ge(tmp[5].fY, clip.fTop); 29280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 29380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[0] = tmp[3]; 29480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[1] = tmp[4]; 29580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[2] = tmp[5]; 29680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 29780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if chopMonoCubicAtY failed, then we may have hit inexact numerics 29880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // so we just clamp against the top 29980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 0; i < 4; i++) { 30080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru clamp_ge(pts[i].fY, clip.fTop); 30180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 30280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 30380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 30480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 30580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we partially below 30680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[3].fY > clip.fBottom) { 30780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t; 30880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (chopMonoCubicAtY(pts, clip.fBottom, &t)) { 30980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint tmp[7]; 31080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopCubicAt(pts, tmp, t); 31180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp[3].fY = clip.fBottom; 31280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru clamp_le(tmp[2].fY, clip.fBottom); 31380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 31480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[1] = tmp[1]; 31580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[2] = tmp[2]; 31680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[3] = tmp[3]; 31780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 31880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if chopMonoCubicAtY failed, then we may have hit inexact numerics 31980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // so we just clamp against the bottom 32080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 0; i < 4; i++) { 32180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru clamp_le(pts[i].fY, clip.fBottom); 32280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 32380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 32480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 32580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 32680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 32780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// srcPts[] must be monotonic in X and Y 32880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkEdgeClipper::clipMonoCubic(const SkPoint src[4], const SkRect& clip) { 32980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint pts[4]; 33080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool reverse = sort_increasing_Y(pts, src, 4); 33180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 33280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we completely above or below 33380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[3].fY <= clip.fTop || pts[0].fY >= clip.fBottom) { 33480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 33580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 33680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 33780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Now chop so that pts is contained within clip in Y 33880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru chop_cubic_in_Y(pts, clip); 33980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 34080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[0].fX > pts[3].fX) { 34180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTSwap<SkPoint>(pts[0], pts[3]); 34280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTSwap<SkPoint>(pts[1], pts[2]); 34380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru reverse = !reverse; 34480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 34580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 34680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Now chop in X has needed, and record the segments 34780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 34880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[3].fX <= clip.fLeft) { // wholly to the left 34980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 35080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 35180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 35280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[0].fX >= clip.fRight) { // wholly to the right 35380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 35480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 35580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 35680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 35780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we partially to the left 35880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[0].fX < clip.fLeft) { 35980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t; 36080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (chopMonoCubicAtX(pts, clip.fLeft, &t)) { 36180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint tmp[7]; 36280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopCubicAt(pts, tmp, t); 36380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendVLine(clip.fLeft, tmp[0].fY, tmp[3].fY, reverse); 36480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 365779bf8a99dc7f03e5c43b26d4b85d7920ce89aeeDerek Sollenberger // tmp[3, 4, 5].fX should all be to the right of clip.fLeft. 366779bf8a99dc7f03e5c43b26d4b85d7920ce89aeeDerek Sollenberger // Since we can't trust the numerics of 36780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // the chopper, we force those conditions now 36880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp[3].fX = clip.fLeft; 36980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru clamp_ge(tmp[4].fX, clip.fLeft); 370779bf8a99dc7f03e5c43b26d4b85d7920ce89aeeDerek Sollenberger clamp_ge(tmp[5].fX, clip.fLeft); 37180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 37280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[0] = tmp[3]; 37380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[1] = tmp[4]; 37480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru pts[2] = tmp[5]; 37580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 37680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if chopMonocubicAtY failed, then we may have hit inexact numerics 37780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // so we just clamp against the left 37880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendVLine(clip.fLeft, pts[0].fY, pts[3].fY, reverse); 37980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 38080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 38180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 38280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 38380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // are we partially to the right 38480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (pts[3].fX > clip.fRight) { 38580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar t; 38680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (chopMonoCubicAtX(pts, clip.fRight, &t)) { 38780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint tmp[7]; 38880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkChopCubicAt(pts, tmp, t); 38980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp[3].fX = clip.fRight; 39080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru clamp_le(tmp[2].fX, clip.fRight); 391779bf8a99dc7f03e5c43b26d4b85d7920ce89aeeDerek Sollenberger clamp_le(tmp[1].fX, clip.fRight); 39280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 39380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendCubic(tmp, reverse); 39480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendVLine(clip.fRight, tmp[3].fY, tmp[6].fY, reverse); 39580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 39680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if chopMonoCubicAtX failed, then we may have hit inexact numerics 39780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // so we just clamp against the right 39880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); 39980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 40080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { // wholly inside the clip 40180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->appendCubic(pts, reverse); 40280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 40380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 40480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 40580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querubool SkEdgeClipper::clipCubic(const SkPoint srcPts[4], const SkRect& clip) { 40680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint = fPoints; 40780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrVerb = fVerbs; 40880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 40980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRect bounds; 41080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bounds.set(srcPts, 4); 41180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 41280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (!quick_reject(bounds, clip)) { 41380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint monoY[10]; 41480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int countY = SkChopCubicAtYExtrema(srcPts, monoY); 41580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int y = 0; y <= countY; y++) { 41680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint monoX[10]; 41780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int countX = SkChopCubicAtXExtrema(&monoY[y * 3], monoX); 41880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int x = 0; x <= countX; x++) { 41980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->clipMonoCubic(&monoX[x * 3], clip); 42080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); 42180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fCurrPoint - fPoints <= kMaxPoints); 42280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 42380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 42480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 42580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 42680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *fCurrVerb = SkPath::kDone_Verb; 42780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint = fPoints; 42880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrVerb = fVerbs; 42980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkPath::kDone_Verb != fVerbs[0]; 43080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 43180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 43280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/////////////////////////////////////////////////////////////////////////////// 43380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 43480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkEdgeClipper::appendVLine(SkScalar x, SkScalar y0, SkScalar y1, 43580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool reverse) { 43680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *fCurrVerb++ = SkPath::kLine_Verb; 43780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 43880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (reverse) { 43980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTSwap<SkScalar>(y0, y1); 44080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 44180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint[0].set(x, y0); 44280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint[1].set(x, y1); 44380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint += 2; 44480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 44580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 44680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkEdgeClipper::appendQuad(const SkPoint pts[3], bool reverse) { 44780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *fCurrVerb++ = SkPath::kQuad_Verb; 44880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 44980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (reverse) { 45080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint[0] = pts[2]; 45180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint[2] = pts[0]; 45280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 45380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint[0] = pts[0]; 45480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint[2] = pts[2]; 45580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 45680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint[1] = pts[1]; 45780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint += 3; 45880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 45980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 46080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkEdgeClipper::appendCubic(const SkPoint pts[4], bool reverse) { 46180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *fCurrVerb++ = SkPath::kCubic_Verb; 46280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 46380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (reverse) { 46480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 0; i < 4; i++) { 46580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint[i] = pts[3 - i]; 46680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 46780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 46880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(fCurrPoint, pts, 4 * sizeof(SkPoint)); 46980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 47080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint += 4; 47180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 47280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 47380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkPath::Verb SkEdgeClipper::next(SkPoint pts[]) { 47480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPath::Verb verb = *fCurrVerb; 47580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 47680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru switch (verb) { 47780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru case SkPath::kLine_Verb: 47880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint)); 47980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint += 2; 48080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrVerb += 1; 48180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru break; 48280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru case SkPath::kQuad_Verb: 48380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint)); 48480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint += 3; 48580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrVerb += 1; 48680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru break; 48780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru case SkPath::kCubic_Verb: 48880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(pts, fCurrPoint, 4 * sizeof(SkPoint)); 48980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrPoint += 4; 49080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrVerb += 1; 49180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru break; 49280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru case SkPath::kDone_Verb: 49380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru break; 49480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru default: 49580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDEBUGFAIL("unexpected verb in quadclippper2 iter"); 49680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru break; 49780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 49880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return verb; 49980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 50080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 50180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/////////////////////////////////////////////////////////////////////////////// 50280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 50380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_DEBUG 50480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic void assert_monotonic(const SkScalar coord[], int count) { 50580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (coord[0] > coord[(count - 1) * 2]) { 50680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 1; i < count; i++) { 50780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(coord[2 * (i - 1)] >= coord[i * 2]); 50880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 50980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else if (coord[0] < coord[(count - 1) * 2]) { 51080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 1; i < count; i++) { 51180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(coord[2 * (i - 1)] <= coord[i * 2]); 51280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 51380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 51480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 1; i < count; i++) { 51580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(coord[2 * (i - 1)] == coord[i * 2]); 51680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 51780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 51880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 51980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 52080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid sk_assert_monotonic_y(const SkPoint pts[], int count) { 52180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (count > 1) { 52280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru assert_monotonic(&pts[0].fY, count); 52380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 52480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 52580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 52680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid sk_assert_monotonic_x(const SkPoint pts[], int count) { 52780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (count > 1) { 52880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru assert_monotonic(&pts[0].fX, count); 52980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 53080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 53180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 532