Line data Source code
1 : /*
2 : * Copyright 2016 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 :
8 : #ifndef SkLinearBitmapPipeline_tile_DEFINED
9 : #define SkLinearBitmapPipeline_tile_DEFINED
10 :
11 : #include "SkLinearBitmapPipeline_core.h"
12 : #include "SkPM4f.h"
13 : #include <algorithm>
14 : #include <cmath>
15 : #include <limits>
16 :
17 : namespace {
18 :
19 0 : void assertTiled(const Sk4s& vs, SkScalar vMax) {
20 0 : SkASSERT(0 <= vs[0] && vs[0] < vMax);
21 0 : SkASSERT(0 <= vs[1] && vs[1] < vMax);
22 0 : SkASSERT(0 <= vs[2] && vs[2] < vMax);
23 0 : SkASSERT(0 <= vs[3] && vs[3] < vMax);
24 0 : }
25 :
26 : /*
27 : * Clamp in the X direction.
28 : * Observations:
29 : * * sample pointer border - if the sample point is <= 0.5 or >= Max - 0.5 then the pixel
30 : * value should be a border color. For this case, create the span using clampToSinglePixel.
31 : */
32 : class XClampStrategy {
33 : public:
34 0 : XClampStrategy(int32_t max)
35 0 : : fXMaxPixel{SkScalar(max - SK_ScalarHalf)}
36 0 : , fXMax{SkScalar(max)} { }
37 :
38 0 : void tileXPoints(Sk4s* xs) {
39 0 : *xs = Sk4s::Min(Sk4s::Max(*xs, SK_ScalarHalf), fXMaxPixel);
40 0 : assertTiled(*xs, fXMax);
41 0 : }
42 :
43 : template<typename Next>
44 0 : bool maybeProcessSpan(Span originalSpan, Next* next) {
45 0 : SkASSERT(!originalSpan.isEmpty());
46 : SkPoint start; SkScalar length; int count;
47 0 : std::tie(start, length, count) = originalSpan;
48 0 : SkScalar x = X(start);
49 0 : SkScalar y = Y(start);
50 0 : Span span{{x, y}, length, count};
51 :
52 0 : if (span.completelyWithin(0.0f, fXMax)) {
53 0 : next->pointSpan(span);
54 0 : return true;
55 : }
56 0 : if (1 == count || 0.0f == length) {
57 0 : return false;
58 : }
59 :
60 0 : SkScalar dx = length / (count - 1);
61 :
62 : // A B C
63 : // +-------+-------+-------++-------+-------+-------+ +-------+-------++------
64 : // | *---*|---*---|*---*--||-*---*-|---*---|*---...| |--*---*|---*---||*---*....
65 : // | | | || | | | ... | | ||
66 : // | | | || | | | | | ||
67 : // +-------+-------+-------++-------+-------+-------+ +-------+-------++------
68 : // ^ ^
69 : // | xMin xMax-1 | xMax
70 : //
71 : // *---*---*---... - track of samples. * = sample
72 : //
73 : // +-+ ||
74 : // | | - pixels in source space. || - tile border.
75 : // +-+ ||
76 : //
77 : // The length from A to B is the length in source space or 4 * dx or (count - 1) * dx
78 : // where dx is the distance between samples. There are 5 destination pixels
79 : // corresponding to 5 samples specified in the A, B span. The distance from A to the next
80 : // span starting at C is 5 * dx, so count * dx.
81 : // Remember, count is the number of pixels needed for the destination and the number of
82 : // samples.
83 : // Overall Strategy:
84 : // * Under - for portions of the span < xMin, take the color at pixel {xMin, y} and use it
85 : // to fill in the 5 pixel sampled from A to B.
86 : // * Middle - for the portion of the span between xMin and xMax sample normally.
87 : // * Over - for the portion of the span > xMax, take the color at pixel {xMax-1, y} and
88 : // use it to fill in the rest of the destination pixels.
89 0 : if (dx >= 0) {
90 0 : Span leftClamped = span.breakAt(SK_ScalarHalf, dx);
91 0 : if (!leftClamped.isEmpty()) {
92 0 : leftClamped.clampToSinglePixel({SK_ScalarHalf, y});
93 0 : next->pointSpan(leftClamped);
94 : }
95 0 : Span center = span.breakAt(fXMax, dx);
96 0 : if (!center.isEmpty()) {
97 0 : next->pointSpan(center);
98 : }
99 0 : if (!span.isEmpty()) {
100 0 : span.clampToSinglePixel({fXMaxPixel, y});
101 0 : next->pointSpan(span);
102 : }
103 : } else {
104 0 : Span rightClamped = span.breakAt(fXMax, dx);
105 0 : if (!rightClamped.isEmpty()) {
106 0 : rightClamped.clampToSinglePixel({fXMaxPixel, y});
107 0 : next->pointSpan(rightClamped);
108 : }
109 0 : Span center = span.breakAt(SK_ScalarHalf, dx);
110 0 : if (!center.isEmpty()) {
111 0 : next->pointSpan(center);
112 : }
113 0 : if (!span.isEmpty()) {
114 0 : span.clampToSinglePixel({SK_ScalarHalf, y});
115 0 : next->pointSpan(span);
116 : }
117 : }
118 0 : return true;
119 : }
120 :
121 : private:
122 : const SkScalar fXMaxPixel;
123 : const SkScalar fXMax;
124 : };
125 :
126 : class YClampStrategy {
127 : public:
128 0 : YClampStrategy(int32_t max)
129 0 : : fYMaxPixel{SkScalar(max) - SK_ScalarHalf} { }
130 :
131 0 : void tileYPoints(Sk4s* ys) {
132 0 : *ys = Sk4s::Min(Sk4s::Max(*ys, SK_ScalarHalf), fYMaxPixel);
133 0 : assertTiled(*ys, fYMaxPixel + SK_ScalarHalf);
134 0 : }
135 :
136 0 : SkScalar tileY(SkScalar y) {
137 : Sk4f ys{y};
138 0 : tileYPoints(&ys);
139 0 : return ys[0];
140 : }
141 :
142 : private:
143 : const SkScalar fYMaxPixel;
144 : };
145 :
146 0 : SkScalar tile_mod(SkScalar x, SkScalar base, SkScalar cap) {
147 : // When x is a negative number *very* close to zero, the difference becomes 0 - (-base) = base
148 : // which is an out of bound value. The min() corrects these problematic values.
149 0 : return std::min(x - SkScalarFloorToScalar(x / base) * base, cap);
150 : }
151 :
152 : class XRepeatStrategy {
153 : public:
154 0 : XRepeatStrategy(int32_t max)
155 0 : : fXMax{SkScalar(max)}
156 0 : , fXCap{SkScalar(nextafterf(SkScalar(max), 0.0f))}
157 0 : , fXInvMax{1.0f / SkScalar(max)} { }
158 :
159 0 : void tileXPoints(Sk4s* xs) {
160 0 : Sk4s divX = *xs * fXInvMax;
161 0 : Sk4s modX = *xs - divX.floor() * fXMax;
162 0 : *xs = Sk4s::Min(fXCap, modX);
163 0 : assertTiled(*xs, fXMax);
164 0 : }
165 :
166 : template<typename Next>
167 0 : bool maybeProcessSpan(Span originalSpan, Next* next) {
168 0 : SkASSERT(!originalSpan.isEmpty());
169 : SkPoint start; SkScalar length; int count;
170 0 : std::tie(start, length, count) = originalSpan;
171 : // Make x and y in range on the tile.
172 0 : SkScalar x = tile_mod(X(start), fXMax, fXCap);
173 0 : SkScalar y = Y(start);
174 0 : SkScalar dx = length / (count - 1);
175 :
176 : // No need trying to go fast because the steps are larger than a tile or there is one point.
177 0 : if (SkScalarAbs(dx) >= fXMax || count <= 1) {
178 0 : return false;
179 : }
180 :
181 : // A B C D Z
182 : // +-------+-------+-------++-------+-------+-------++ +-------+-------++------
183 : // | | *---|*---*--||-*---*-|---*---|*---*--|| |--*---*| ||
184 : // | | | || | | || ... | | ||
185 : // | | | || | | || | | ||
186 : // +-------+-------+-------++-------+-------+-------++ +-------+-------++------
187 : // ^^ ^^ ^^
188 : // xMax || xMin xMax || xMin xMax || xMin
189 : //
190 : // *---*---*---... - track of samples. * = sample
191 : //
192 : // +-+ ||
193 : // | | - pixels in source space. || - tile border.
194 : // +-+ ||
195 : //
196 : //
197 : // The given span starts at A and continues on through several tiles to sample point Z.
198 : // The idea is to break this into several spans one on each tile the entire span
199 : // intersects. The A to B span only covers a partial tile and has a count of 3 and the
200 : // distance from A to B is (count - 1) * dx or 2 * dx. The distance from A to the start of
201 : // the next span is count * dx or 3 * dx. Span C to D covers an entire tile has a count
202 : // of 5 and a length of 4 * dx. Remember, count is the number of pixels needed for the
203 : // destination and the number of samples.
204 : //
205 : // Overall Strategy:
206 : // While the span hangs over the edge of the tile, draw the span covering the tile then
207 : // slide the span over to the next tile.
208 :
209 : // The guard could have been count > 0, but then a bunch of math would be done in the
210 : // common case.
211 :
212 0 : Span span({x, y}, length, count);
213 0 : if (dx > 0) {
214 0 : while (!span.isEmpty() && span.endX() >= fXMax) {
215 0 : Span toDraw = span.breakAt(fXMax, dx);
216 0 : next->pointSpan(toDraw);
217 0 : span.offset(-fXMax);
218 : }
219 : } else {
220 0 : while (!span.isEmpty() && span.endX() < 0.0f) {
221 0 : Span toDraw = span.breakAt(0.0f, dx);
222 0 : next->pointSpan(toDraw);
223 0 : span.offset(fXMax);
224 : }
225 : }
226 :
227 : // All on a single tile.
228 0 : if (!span.isEmpty()) {
229 0 : next->pointSpan(span);
230 : }
231 :
232 0 : return true;
233 : }
234 :
235 : private:
236 : const SkScalar fXMax;
237 : const SkScalar fXCap;
238 : const SkScalar fXInvMax;
239 : };
240 :
241 : // The XRepeatUnitScaleStrategy exploits the situation where dx = 1.0. The main advantage is that
242 : // the relationship between the sample points and the source pixels does not change from tile to
243 : // repeated tile. This allows the tiler to calculate the span once and re-use it for each
244 : // repeated tile. This is later exploited by some samplers to avoid converting pixels to linear
245 : // space allowing the use of memmove to place pixel in the destination.
246 : class XRepeatUnitScaleStrategy {
247 : public:
248 0 : XRepeatUnitScaleStrategy(int32_t max)
249 0 : : fXMax{SkScalar(max)}
250 0 : , fXCap{SkScalar(nextafterf(SkScalar(max), 0.0f))}
251 0 : , fXInvMax{1.0f / SkScalar(max)} { }
252 :
253 0 : void tileXPoints(Sk4s* xs) {
254 0 : Sk4s divX = *xs * fXInvMax;
255 0 : Sk4s modX = *xs - divX.floor() * fXMax;
256 0 : *xs = Sk4s::Min(fXCap, modX);
257 0 : assertTiled(*xs, fXMax);
258 0 : }
259 :
260 : template<typename Next>
261 0 : bool maybeProcessSpan(Span originalSpan, Next* next) {
262 0 : SkASSERT(!originalSpan.isEmpty());
263 : SkPoint start; SkScalar length; int count;
264 0 : std::tie(start, length, count) = originalSpan;
265 : // Make x and y in range on the tile.
266 0 : SkScalar x = tile_mod(X(start), fXMax, fXCap);
267 0 : SkScalar y = Y(start);
268 :
269 : // No need trying to go fast because the steps are larger than a tile or there is one point.
270 0 : if (fXMax == 1 || count <= 1) {
271 0 : return false;
272 : }
273 :
274 : // x should be on the tile.
275 0 : SkASSERT(0.0f <= x && x < fXMax);
276 0 : Span span({x, y}, length, count);
277 :
278 0 : if (SkScalarFloorToScalar(x) != 0.0f) {
279 0 : Span toDraw = span.breakAt(fXMax, 1.0f);
280 0 : SkASSERT(0.0f <= toDraw.startX() && toDraw.endX() < fXMax);
281 0 : next->pointSpan(toDraw);
282 0 : span.offset(-fXMax);
283 : }
284 :
285 : // All of the span could have been on the first tile. If so, then no work to do.
286 0 : if (span.isEmpty()) return true;
287 :
288 : // At this point the span should be aligned to zero.
289 0 : SkASSERT(SkScalarFloorToScalar(span.startX()) == 0.0f);
290 :
291 : // Note: The span length has an unintuitive relation to the tile width. The tile width is
292 : // a half open interval [tb, te), but the span is a closed interval [sb, se]. In order to
293 : // compare the two, you need to convert the span to a half open interval. This is done by
294 : // adding dx to se. So, the span becomes: [sb, se + dx). Hence the + 1.0f below.
295 0 : SkScalar div = (span.length() + 1.0f) / fXMax;
296 0 : int32_t repeatCount = SkScalarFloorToInt(div);
297 0 : Span repeatableSpan{{0.0f, y}, fXMax - 1.0f, SkScalarFloorToInt(fXMax)};
298 :
299 : // Repeat the center section.
300 0 : SkASSERT(0.0f <= repeatableSpan.startX() && repeatableSpan.endX() < fXMax);
301 0 : if (repeatCount > 0) {
302 0 : next->repeatSpan(repeatableSpan, repeatCount);
303 : }
304 :
305 : // Calculate the advance past the center portion.
306 0 : SkScalar advance = SkScalar(repeatCount) * fXMax;
307 :
308 : // There may be some of the span left over.
309 0 : span.breakAt(advance, 1.0f);
310 :
311 : // All on a single tile.
312 0 : if (!span.isEmpty()) {
313 0 : span.offset(-advance);
314 0 : SkASSERT(0.0f <= span.startX() && span.endX() < fXMax);
315 0 : next->pointSpan(span);
316 : }
317 :
318 0 : return true;
319 : }
320 :
321 : private:
322 : const SkScalar fXMax;
323 : const SkScalar fXCap;
324 : const SkScalar fXInvMax;
325 : };
326 :
327 : class YRepeatStrategy {
328 : public:
329 0 : YRepeatStrategy(int32_t max)
330 0 : : fYMax{SkScalar(max)}
331 0 : , fYCap{SkScalar(nextafterf(SkScalar(max), 0.0f))}
332 0 : , fYsInvMax{1.0f / SkScalar(max)} { }
333 :
334 0 : void tileYPoints(Sk4s* ys) {
335 0 : Sk4s divY = *ys * fYsInvMax;
336 0 : Sk4s modY = *ys - divY.floor() * fYMax;
337 0 : *ys = Sk4s::Min(fYCap, modY);
338 0 : assertTiled(*ys, fYMax);
339 0 : }
340 :
341 0 : SkScalar tileY(SkScalar y) {
342 0 : SkScalar answer = tile_mod(y, fYMax, fYCap);
343 0 : SkASSERT(0 <= answer && answer < fYMax);
344 0 : return answer;
345 : }
346 :
347 : private:
348 : const SkScalar fYMax;
349 : const SkScalar fYCap;
350 : const SkScalar fYsInvMax;
351 : };
352 : // max = 40
353 : // mq2[x_] := Abs[(x - 40) - Floor[(x - 40)/80] * 80 - 40]
354 : class XMirrorStrategy {
355 : public:
356 0 : XMirrorStrategy(int32_t max)
357 0 : : fXMax{SkScalar(max)}
358 0 : , fXCap{SkScalar(nextafterf(SkScalar(max), 0.0f))}
359 0 : , fXDoubleInvMax{1.0f / (2.0f * SkScalar(max))} { }
360 :
361 0 : void tileXPoints(Sk4s* xs) {
362 0 : Sk4f bias = *xs - fXMax;
363 0 : Sk4f div = bias * fXDoubleInvMax;
364 0 : Sk4f mod = bias - div.floor() * 2.0f * fXMax;
365 0 : Sk4f unbias = mod - fXMax;
366 0 : *xs = Sk4f::Min(unbias.abs(), fXCap);
367 0 : assertTiled(*xs, fXMax);
368 0 : }
369 :
370 : template <typename Next>
371 0 : bool maybeProcessSpan(Span originalSpan, Next* next) { return false; }
372 :
373 : private:
374 : SkScalar fXMax;
375 : SkScalar fXCap;
376 : SkScalar fXDoubleInvMax;
377 : };
378 :
379 : class YMirrorStrategy {
380 : public:
381 0 : YMirrorStrategy(int32_t max)
382 0 : : fYMax{SkScalar(max)}
383 0 : , fYCap{nextafterf(SkScalar(max), 0.0f)}
384 0 : , fYDoubleInvMax{1.0f / (2.0f * SkScalar(max))} { }
385 :
386 0 : void tileYPoints(Sk4s* ys) {
387 0 : Sk4f bias = *ys - fYMax;
388 0 : Sk4f div = bias * fYDoubleInvMax;
389 0 : Sk4f mod = bias - div.floor() * 2.0f * fYMax;
390 0 : Sk4f unbias = mod - fYMax;
391 0 : *ys = Sk4f::Min(unbias.abs(), fYCap);
392 0 : assertTiled(*ys, fYMax);
393 0 : }
394 :
395 0 : SkScalar tileY(SkScalar y) {
396 0 : SkScalar bias = y - fYMax;
397 0 : SkScalar div = bias * fYDoubleInvMax;
398 0 : SkScalar mod = bias - SkScalarFloorToScalar(div) * 2.0f * fYMax;
399 0 : SkScalar unbias = mod - fYMax;
400 0 : SkScalar answer = SkMinScalar(SkScalarAbs(unbias), fYCap);
401 0 : SkASSERT(0 <= answer && answer < fYMax);
402 0 : return answer;
403 : }
404 :
405 : private:
406 : SkScalar fYMax;
407 : SkScalar fYCap;
408 : SkScalar fYDoubleInvMax;
409 : };
410 :
411 : } // namespace
412 : #endif // SkLinearBitmapPipeline_tile_DEFINED
|