Line data Source code
1 : /*
2 : * Copyright 2015 Google Inc.
3 : *
4 : * Use of this source code is governed by a BSD-style license that can be
5 : * found in the LICENSE file.
6 : */
7 : #include "SkPathOpsBounds.h"
8 : #include "SkPathOpsRect.h"
9 : #include "SkPathOpsCurve.h"
10 :
11 : // this cheats and assumes that the perpendicular to the point is the closest ray to the curve
12 : // this case (where the line and the curve are nearly coincident) may be the only case that counts
13 0 : double SkDCurve::nearPoint(SkPath::Verb verb, const SkDPoint& xy, const SkDPoint& opp) const {
14 0 : int count = SkPathOpsVerbToPoints(verb);
15 0 : double minX = fCubic.fPts[0].fX;
16 0 : double maxX = minX;
17 0 : for (int index = 1; index <= count; ++index) {
18 0 : minX = SkTMin(minX, fCubic.fPts[index].fX);
19 0 : maxX = SkTMax(maxX, fCubic.fPts[index].fX);
20 : }
21 0 : if (!AlmostBetweenUlps(minX, xy.fX, maxX)) {
22 0 : return -1;
23 : }
24 0 : double minY = fCubic.fPts[0].fY;
25 0 : double maxY = minY;
26 0 : for (int index = 1; index <= count; ++index) {
27 0 : minY = SkTMin(minY, fCubic.fPts[index].fY);
28 0 : maxY = SkTMax(maxY, fCubic.fPts[index].fY);
29 : }
30 0 : if (!AlmostBetweenUlps(minY, xy.fY, maxY)) {
31 0 : return -1;
32 : }
33 0 : SkIntersections i;
34 0 : SkDLine perp = {{ xy, { xy.fX + opp.fY - xy.fY, xy.fY + xy.fX - opp.fX }}};
35 0 : (*CurveDIntersectRay[verb])(*this, perp, &i);
36 0 : int minIndex = -1;
37 0 : double minDist = FLT_MAX;
38 0 : for (int index = 0; index < i.used(); ++index) {
39 0 : double dist = xy.distance(i.pt(index));
40 0 : if (minDist > dist) {
41 0 : minDist = dist;
42 0 : minIndex = index;
43 : }
44 : }
45 0 : if (minIndex < 0) {
46 0 : return -1;
47 : }
48 0 : double largest = SkTMax(SkTMax(maxX, maxY), -SkTMin(minX, minY));
49 0 : if (!AlmostEqualUlps_Pin(largest, largest + minDist)) { // is distance within ULPS tolerance?
50 0 : return -1;
51 : }
52 0 : return SkPinT(i[0][minIndex]);
53 : }
54 :
55 0 : void SkDCurve::offset(SkPath::Verb verb, const SkDVector& off) {
56 0 : int count = SkPathOpsVerbToPoints(verb);
57 0 : for (int index = 0; index <= count; ++index) {
58 0 : fCubic.fPts[index] += off;
59 : }
60 0 : }
61 :
62 0 : void SkDCurve::setConicBounds(const SkPoint curve[3], SkScalar curveWeight,
63 : double tStart, double tEnd, SkPathOpsBounds* bounds) {
64 : SkDConic dCurve;
65 0 : dCurve.set(curve, curveWeight);
66 : SkDRect dRect;
67 0 : dRect.setBounds(dCurve, fConic, tStart, tEnd);
68 0 : bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
69 0 : SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
70 0 : }
71 :
72 0 : void SkDCurve::setCubicBounds(const SkPoint curve[4], SkScalar ,
73 : double tStart, double tEnd, SkPathOpsBounds* bounds) {
74 : SkDCubic dCurve;
75 0 : dCurve.set(curve);
76 : SkDRect dRect;
77 0 : dRect.setBounds(dCurve, fCubic, tStart, tEnd);
78 0 : bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
79 0 : SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
80 0 : }
81 :
82 0 : void SkDCurve::setQuadBounds(const SkPoint curve[3], SkScalar ,
83 : double tStart, double tEnd, SkPathOpsBounds* bounds) {
84 : SkDQuad dCurve;
85 0 : dCurve.set(curve);
86 : SkDRect dRect;
87 0 : dRect.setBounds(dCurve, fQuad, tStart, tEnd);
88 0 : bounds->set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
89 0 : SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
90 0 : }
91 :
92 0 : void SkDCurveSweep::setCurveHullSweep(SkPath::Verb verb) {
93 0 : fOrdered = true;
94 0 : fSweep[0] = fCurve[1] - fCurve[0];
95 0 : if (SkPath::kLine_Verb == verb) {
96 0 : fSweep[1] = fSweep[0];
97 0 : fIsCurve = false;
98 0 : return;
99 : }
100 0 : fSweep[1] = fCurve[2] - fCurve[0];
101 : // OPTIMIZE: I do the following float check a lot -- probably need a
102 : // central place for this val-is-small-compared-to-curve check
103 0 : double maxVal = 0;
104 0 : for (int index = 0; index <= SkPathOpsVerbToPoints(verb); ++index) {
105 0 : maxVal = SkTMax(maxVal, SkTMax(SkTAbs(fCurve[index].fX),
106 0 : SkTAbs(fCurve[index].fY)));
107 : }
108 : {
109 0 : if (SkPath::kCubic_Verb != verb) {
110 0 : if (roughly_zero_when_compared_to(fSweep[0].fX, maxVal)
111 0 : && roughly_zero_when_compared_to(fSweep[0].fY, maxVal)) {
112 0 : fSweep[0] = fSweep[1];
113 : }
114 0 : goto setIsCurve;
115 : }
116 0 : SkDVector thirdSweep = fCurve[3] - fCurve[0];
117 0 : if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
118 0 : fSweep[0] = fSweep[1];
119 0 : fSweep[1] = thirdSweep;
120 0 : if (roughly_zero_when_compared_to(fSweep[0].fX, maxVal)
121 0 : && roughly_zero_when_compared_to(fSweep[0].fY, maxVal)) {
122 0 : fSweep[0] = fSweep[1];
123 0 : fCurve[1] = fCurve[3];
124 : }
125 0 : goto setIsCurve;
126 : }
127 0 : double s1x3 = fSweep[0].crossCheck(thirdSweep);
128 0 : double s3x2 = thirdSweep.crossCheck(fSweep[1]);
129 0 : if (s1x3 * s3x2 >= 0) { // if third vector is on or between first two vectors
130 0 : goto setIsCurve;
131 : }
132 0 : double s2x1 = fSweep[1].crossCheck(fSweep[0]);
133 : // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in trouble
134 : // probably such wide sweeps should be artificially subdivided earlier so that never happens
135 0 : SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0);
136 0 : if (s3x2 * s2x1 < 0) {
137 0 : SkASSERT(s2x1 * s1x3 > 0);
138 0 : fSweep[0] = fSweep[1];
139 0 : fOrdered = false;
140 : }
141 0 : fSweep[1] = thirdSweep;
142 : }
143 : setIsCurve:
144 0 : fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0;
145 : }
|