gfx/skia/trunk/src/core/SkLineClipper.cpp@129ffea94266
gfx/skia/trunk/src/core/SkLineClipper.cpp
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rw-r--r--
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
2 /*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8 #include "SkLineClipper.h"
10 template <typename T> T pin_unsorted(T value, T limit0, T limit1) {
11 if (limit1 < limit0) {
12 SkTSwap(limit0, limit1);
13 }
14 // now the limits are sorted
15 SkASSERT(limit0 <= limit1);
17 if (value < limit0) {
18 value = limit0;
19 } else if (value > limit1) {
20 value = limit1;
21 }
22 return value;
23 }
25 // return X coordinate of intersection with horizontal line at Y
26 static SkScalar sect_with_horizontal(const SkPoint src[2], SkScalar Y) {
27 SkScalar dy = src[1].fY - src[0].fY;
28 if (SkScalarNearlyZero(dy)) {
29 return SkScalarAve(src[0].fX, src[1].fX);
30 } else {
31 // need the extra precision so we don't compute a value that exceeds
32 // our original limits
33 double X0 = src[0].fX;
34 double Y0 = src[0].fY;
35 double X1 = src[1].fX;
36 double Y1 = src[1].fY;
37 double result = X0 + ((double)Y - Y0) * (X1 - X0) / (Y1 - Y0);
39 // The computed X value might still exceed [X0..X1] due to quantum flux
40 // when the doubles were added and subtracted, so we have to pin the
41 // answer :(
42 return (float)pin_unsorted(result, X0, X1);
43 }
44 }
46 // return Y coordinate of intersection with vertical line at X
47 static SkScalar sect_with_vertical(const SkPoint src[2], SkScalar X) {
48 SkScalar dx = src[1].fX - src[0].fX;
49 if (SkScalarNearlyZero(dx)) {
50 return SkScalarAve(src[0].fY, src[1].fY);
51 } else {
52 // need the extra precision so we don't compute a value that exceeds
53 // our original limits
54 double X0 = src[0].fX;
55 double Y0 = src[0].fY;
56 double X1 = src[1].fX;
57 double Y1 = src[1].fY;
58 double result = Y0 + ((double)X - X0) * (Y1 - Y0) / (X1 - X0);
59 return (float)result;
60 }
61 }
63 ///////////////////////////////////////////////////////////////////////////////
65 static inline bool nestedLT(SkScalar a, SkScalar b, SkScalar dim) {
66 return a <= b && (a < b || dim > 0);
67 }
69 // returns true if outer contains inner, even if inner is empty.
70 // note: outer.contains(inner) always returns false if inner is empty.
71 static inline bool containsNoEmptyCheck(const SkRect& outer,
72 const SkRect& inner) {
73 return outer.fLeft <= inner.fLeft && outer.fTop <= inner.fTop &&
74 outer.fRight >= inner.fRight && outer.fBottom >= inner.fBottom;
75 }
77 bool SkLineClipper::IntersectLine(const SkPoint src[2], const SkRect& clip,
78 SkPoint dst[2]) {
79 SkRect bounds;
81 bounds.set(src, 2);
82 if (containsNoEmptyCheck(clip, bounds)) {
83 if (src != dst) {
84 memcpy(dst, src, 2 * sizeof(SkPoint));
85 }
86 return true;
87 }
88 // check for no overlap, and only permit coincident edges if the line
89 // and the edge are colinear
90 if (nestedLT(bounds.fRight, clip.fLeft, bounds.width()) ||
91 nestedLT(clip.fRight, bounds.fLeft, bounds.width()) ||
92 nestedLT(bounds.fBottom, clip.fTop, bounds.height()) ||
93 nestedLT(clip.fBottom, bounds.fTop, bounds.height())) {
94 return false;
95 }
97 int index0, index1;
99 if (src[0].fY < src[1].fY) {
100 index0 = 0;
101 index1 = 1;
102 } else {
103 index0 = 1;
104 index1 = 0;
105 }
107 SkPoint tmp[2];
108 memcpy(tmp, src, sizeof(tmp));
110 // now compute Y intersections
111 if (tmp[index0].fY < clip.fTop) {
112 tmp[index0].set(sect_with_horizontal(src, clip.fTop), clip.fTop);
113 }
114 if (tmp[index1].fY > clip.fBottom) {
115 tmp[index1].set(sect_with_horizontal(src, clip.fBottom), clip.fBottom);
116 }
118 if (tmp[0].fX < tmp[1].fX) {
119 index0 = 0;
120 index1 = 1;
121 } else {
122 index0 = 1;
123 index1 = 0;
124 }
126 // check for quick-reject in X again, now that we may have been chopped
127 if ((tmp[index1].fX <= clip.fLeft || tmp[index0].fX >= clip.fRight) &&
128 tmp[index0].fX < tmp[index1].fX) {
129 // only reject if we have a non-zero width
130 return false;
131 }
133 if (tmp[index0].fX < clip.fLeft) {
134 tmp[index0].set(clip.fLeft, sect_with_vertical(src, clip.fLeft));
135 }
136 if (tmp[index1].fX > clip.fRight) {
137 tmp[index1].set(clip.fRight, sect_with_vertical(src, clip.fRight));
138 }
139 #ifdef SK_DEBUG
140 bounds.set(tmp, 2);
141 SkASSERT(containsNoEmptyCheck(clip, bounds));
142 #endif
143 memcpy(dst, tmp, sizeof(tmp));
144 return true;
145 }
147 #ifdef SK_DEBUG
148 // return value between the two limits, where the limits are either ascending
149 // or descending.
150 static bool is_between_unsorted(SkScalar value,
151 SkScalar limit0, SkScalar limit1) {
152 if (limit0 < limit1) {
153 return limit0 <= value && value <= limit1;
154 } else {
155 return limit1 <= value && value <= limit0;
156 }
157 }
158 #endif
160 #ifdef SK_DEBUG
161 // This is an example of why we need to pin the result computed in
162 // sect_with_horizontal. If we didn't explicitly pin, is_between_unsorted would
163 // fail.
164 //
165 static void sect_with_horizontal_test_for_pin_results() {
166 const SkPoint pts[] = {
167 { -540000, -720000 },
168 { -9.10000017e-05f, 9.99999996e-13f }
169 };
170 float x = sect_with_horizontal(pts, 0);
171 SkASSERT(is_between_unsorted(x, pts[0].fX, pts[1].fX));
172 }
173 #endif
175 int SkLineClipper::ClipLine(const SkPoint pts[], const SkRect& clip,
176 SkPoint lines[]) {
177 #ifdef SK_DEBUG
178 {
179 static bool gOnce;
180 if (!gOnce) {
181 sect_with_horizontal_test_for_pin_results();
182 gOnce = true;
183 }
184 }
185 #endif
187 int index0, index1;
189 if (pts[0].fY < pts[1].fY) {
190 index0 = 0;
191 index1 = 1;
192 } else {
193 index0 = 1;
194 index1 = 0;
195 }
197 // Check if we're completely clipped out in Y (above or below
199 if (pts[index1].fY <= clip.fTop) { // we're above the clip
200 return 0;
201 }
202 if (pts[index0].fY >= clip.fBottom) { // we're below the clip
203 return 0;
204 }
206 // Chop in Y to produce a single segment, stored in tmp[0..1]
208 SkPoint tmp[2];
209 memcpy(tmp, pts, sizeof(tmp));
211 // now compute intersections
212 if (pts[index0].fY < clip.fTop) {
213 tmp[index0].set(sect_with_horizontal(pts, clip.fTop), clip.fTop);
214 SkASSERT(is_between_unsorted(tmp[index0].fX, pts[0].fX, pts[1].fX));
215 }
216 if (tmp[index1].fY > clip.fBottom) {
217 tmp[index1].set(sect_with_horizontal(pts, clip.fBottom), clip.fBottom);
218 SkASSERT(is_between_unsorted(tmp[index1].fX, pts[0].fX, pts[1].fX));
219 }
221 // Chop it into 1..3 segments that are wholly within the clip in X.
223 // temp storage for up to 3 segments
224 SkPoint resultStorage[kMaxPoints];
225 SkPoint* result; // points to our results, either tmp or resultStorage
226 int lineCount = 1;
227 bool reverse;
229 if (pts[0].fX < pts[1].fX) {
230 index0 = 0;
231 index1 = 1;
232 reverse = false;
233 } else {
234 index0 = 1;
235 index1 = 0;
236 reverse = true;
237 }
239 if (tmp[index1].fX <= clip.fLeft) { // wholly to the left
240 tmp[0].fX = tmp[1].fX = clip.fLeft;
241 result = tmp;
242 reverse = false;
243 } else if (tmp[index0].fX >= clip.fRight) { // wholly to the right
244 tmp[0].fX = tmp[1].fX = clip.fRight;
245 result = tmp;
246 reverse = false;
247 } else {
248 result = resultStorage;
249 SkPoint* r = result;
251 if (tmp[index0].fX < clip.fLeft) {
252 r->set(clip.fLeft, tmp[index0].fY);
253 r += 1;
254 r->set(clip.fLeft, sect_with_vertical(tmp, clip.fLeft));
255 SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
256 } else {
257 *r = tmp[index0];
258 }
259 r += 1;
261 if (tmp[index1].fX > clip.fRight) {
262 r->set(clip.fRight, sect_with_vertical(tmp, clip.fRight));
263 SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
264 r += 1;
265 r->set(clip.fRight, tmp[index1].fY);
266 } else {
267 *r = tmp[index1];
268 }
270 lineCount = SkToInt(r - result);
271 }
273 // Now copy the results into the caller's lines[] parameter
274 if (reverse) {
275 // copy the pts in reverse order to maintain winding order
276 for (int i = 0; i <= lineCount; i++) {
277 lines[lineCount - i] = result[i];
278 }
279 } else {
280 memcpy(lines, result, (lineCount + 1) * sizeof(SkPoint));
281 }
282 return lineCount;
283 }
