1 /*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #define LOG_TAG "PathTessellator"
18 #define LOG_NDEBUG 1
19 #define ATRACE_TAG ATRACE_TAG_GRAPHICS
20
21 #define VERTEX_DEBUG 0
22
23 #if VERTEX_DEBUG
24 #define DEBUG_DUMP_ALPHA_BUFFER() \
25 for (unsigned int i = 0; i < vertexBuffer.getSize(); i++) { \
26 ALOGD("point %d at %f %f, alpha %f", \
27 i, buffer[i].position[0], buffer[i].position[1], buffer[i].alpha); \
28 }
29 #define DEBUG_DUMP_BUFFER() \
30 for (unsigned int i = 0; i < vertexBuffer.getSize(); i++) { \
31 ALOGD("point %d at %f %f", i, buffer[i].position[0], buffer[i].position[1]); \
32 }
33 #else
34 #define DEBUG_DUMP_ALPHA_BUFFER()
35 #define DEBUG_DUMP_BUFFER()
36 #endif
37
38 #include <SkPath.h>
39 #include <SkPaint.h>
40
41 #include <stdlib.h>
42 #include <stdint.h>
43 #include <sys/types.h>
44
45 #include <utils/Log.h>
46 #include <utils/Trace.h>
47
48 #include "PathTessellator.h"
49 #include "Matrix.h"
50 #include "Vector.h"
51 #include "Vertex.h"
52
53 namespace android {
54 namespace uirenderer {
55
56 #define THRESHOLD 0.5f
57 #define ROUND_CAP_THRESH 0.25f
58 #define PI 3.1415926535897932f
59
expandBoundsForStroke(SkRect & bounds,const SkPaint * paint,bool forceExpand)60 void PathTessellator::expandBoundsForStroke(SkRect& bounds, const SkPaint* paint,
61 bool forceExpand) {
62 if (forceExpand || paint->getStyle() != SkPaint::kFill_Style) {
63 float outset = paint->getStrokeWidth() * 0.5f;
64 if (outset == 0) outset = 0.5f; // account for hairline
65 bounds.outset(outset, outset);
66 }
67 }
68
copyVertex(Vertex * destPtr,const Vertex * srcPtr)69 inline void copyVertex(Vertex* destPtr, const Vertex* srcPtr) {
70 Vertex::set(destPtr, srcPtr->position[0], srcPtr->position[1]);
71 }
72
copyAlphaVertex(AlphaVertex * destPtr,const AlphaVertex * srcPtr)73 inline void copyAlphaVertex(AlphaVertex* destPtr, const AlphaVertex* srcPtr) {
74 AlphaVertex::set(destPtr, srcPtr->position[0], srcPtr->position[1], srcPtr->alpha);
75 }
76
77 /**
78 * Produces a pseudo-normal for a vertex, given the normals of the two incoming lines. If the offset
79 * from each vertex in a perimeter is calculated, the resultant lines connecting the offset vertices
80 * will be offset by 1.0
81 *
82 * Note that we can't add and normalize the two vectors, that would result in a rectangle having an
83 * offset of (sqrt(2)/2, sqrt(2)/2) at each corner, instead of (1, 1)
84 *
85 * NOTE: assumes angles between normals 90 degrees or less
86 */
totalOffsetFromNormals(const vec2 & normalA,const vec2 & normalB)87 inline vec2 totalOffsetFromNormals(const vec2& normalA, const vec2& normalB) {
88 return (normalA + normalB) / (1 + fabs(normalA.dot(normalB)));
89 }
90
91 /**
92 * Structure used for storing useful information about the SkPaint and scale used for tessellating
93 */
94 struct PaintInfo {
95 public:
PaintInfoandroid::uirenderer::PaintInfo96 PaintInfo(const SkPaint* paint, const mat4 *transform) :
97 style(paint->getStyle()), cap(paint->getStrokeCap()), isAA(paint->isAntiAlias()),
98 inverseScaleX(1.0f), inverseScaleY(1.0f),
99 halfStrokeWidth(paint->getStrokeWidth() * 0.5f), maxAlpha(1.0f) {
100 // compute inverse scales
101 if (CC_UNLIKELY(!transform->isPureTranslate())) {
102 float m00 = transform->data[Matrix4::kScaleX];
103 float m01 = transform->data[Matrix4::kSkewY];
104 float m10 = transform->data[Matrix4::kSkewX];
105 float m11 = transform->data[Matrix4::kScaleY];
106 float scaleX = sqrt(m00 * m00 + m01 * m01);
107 float scaleY = sqrt(m10 * m10 + m11 * m11);
108 inverseScaleX = (scaleX != 0) ? (1.0f / scaleX) : 1.0f;
109 inverseScaleY = (scaleY != 0) ? (1.0f / scaleY) : 1.0f;
110 }
111
112 if (isAA && halfStrokeWidth != 0 && inverseScaleX == inverseScaleY &&
113 2 * halfStrokeWidth < inverseScaleX) {
114 maxAlpha *= (2 * halfStrokeWidth) / inverseScaleX;
115 halfStrokeWidth = 0.0f;
116 }
117 }
118
119 SkPaint::Style style;
120 SkPaint::Cap cap;
121 bool isAA;
122 float inverseScaleX;
123 float inverseScaleY;
124 float halfStrokeWidth;
125 float maxAlpha;
126
scaleOffsetForStrokeWidthandroid::uirenderer::PaintInfo127 inline void scaleOffsetForStrokeWidth(vec2& offset) const {
128 if (halfStrokeWidth == 0.0f) {
129 // hairline - compensate for scale
130 offset.x *= 0.5f * inverseScaleX;
131 offset.y *= 0.5f * inverseScaleY;
132 } else {
133 offset *= halfStrokeWidth;
134 }
135 }
136
137 /**
138 * NOTE: the input will not always be a normal, especially for sharp edges - it should be the
139 * result of totalOffsetFromNormals (see documentation there)
140 */
deriveAAOffsetandroid::uirenderer::PaintInfo141 inline vec2 deriveAAOffset(const vec2& offset) const {
142 return vec2(offset.x * 0.5f * inverseScaleX,
143 offset.y * 0.5f * inverseScaleY);
144 }
145
146 /**
147 * Returns the number of cap divisions beyond the minimum 2 (kButt_Cap/kSquareCap will return 0)
148 * Should only be used when stroking and drawing caps
149 */
capExtraDivisionsandroid::uirenderer::PaintInfo150 inline int capExtraDivisions() const {
151 if (cap == SkPaint::kRound_Cap) {
152 if (halfStrokeWidth == 0.0f) return 2;
153
154 // ROUND_CAP_THRESH is the maximum error for polygonal approximation of the round cap
155 const float errConst = (-ROUND_CAP_THRESH / halfStrokeWidth + 1);
156 const float targetCosVal = 2 * errConst * errConst - 1;
157 int neededDivisions = (int)(ceilf(PI / acos(targetCosVal)/2)) * 2;
158 return neededDivisions;
159 }
160 return 0;
161 }
162 };
163
getFillVerticesFromPerimeter(const Vector<Vertex> & perimeter,VertexBuffer & vertexBuffer)164 void getFillVerticesFromPerimeter(const Vector<Vertex>& perimeter, VertexBuffer& vertexBuffer) {
165 Vertex* buffer = vertexBuffer.alloc<Vertex>(perimeter.size());
166
167 int currentIndex = 0;
168 // zig zag between all previous points on the inside of the hull to create a
169 // triangle strip that fills the hull
170 int srcAindex = 0;
171 int srcBindex = perimeter.size() - 1;
172 while (srcAindex <= srcBindex) {
173 copyVertex(&buffer[currentIndex++], &perimeter[srcAindex]);
174 if (srcAindex == srcBindex) break;
175 copyVertex(&buffer[currentIndex++], &perimeter[srcBindex]);
176 srcAindex++;
177 srcBindex--;
178 }
179 }
180
181 /*
182 * Fills a vertexBuffer with non-alpha vertices, zig-zagging at each perimeter point to create a
183 * tri-strip as wide as the stroke.
184 *
185 * Uses an additional 2 vertices at the end to wrap around, closing the tri-strip
186 * (for a total of perimeter.size() * 2 + 2 vertices)
187 */
getStrokeVerticesFromPerimeter(const PaintInfo & paintInfo,const Vector<Vertex> & perimeter,VertexBuffer & vertexBuffer)188 void getStrokeVerticesFromPerimeter(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter,
189 VertexBuffer& vertexBuffer) {
190 Vertex* buffer = vertexBuffer.alloc<Vertex>(perimeter.size() * 2 + 2);
191
192 int currentIndex = 0;
193 const Vertex* last = &(perimeter[perimeter.size() - 1]);
194 const Vertex* current = &(perimeter[0]);
195 vec2 lastNormal(current->position[1] - last->position[1],
196 last->position[0] - current->position[0]);
197 lastNormal.normalize();
198 for (unsigned int i = 0; i < perimeter.size(); i++) {
199 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]);
200 vec2 nextNormal(next->position[1] - current->position[1],
201 current->position[0] - next->position[0]);
202 nextNormal.normalize();
203
204 vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
205 paintInfo.scaleOffsetForStrokeWidth(totalOffset);
206
207 Vertex::set(&buffer[currentIndex++],
208 current->position[0] + totalOffset.x,
209 current->position[1] + totalOffset.y);
210
211 Vertex::set(&buffer[currentIndex++],
212 current->position[0] - totalOffset.x,
213 current->position[1] - totalOffset.y);
214
215 last = current;
216 current = next;
217 lastNormal = nextNormal;
218 }
219
220 // wrap around to beginning
221 copyVertex(&buffer[currentIndex++], &buffer[0]);
222 copyVertex(&buffer[currentIndex++], &buffer[1]);
223
224 DEBUG_DUMP_BUFFER();
225 }
226
227 /**
228 * Fills a vertexBuffer with non-alpha vertices similar to getStrokeVerticesFromPerimeter, except:
229 *
230 * 1 - Doesn't need to wrap around, since the input vertices are unclosed
231 *
232 * 2 - can zig-zag across 'extra' vertices at either end, to create round caps
233 */
getStrokeVerticesFromUnclosedVertices(const PaintInfo & paintInfo,const Vector<Vertex> & vertices,VertexBuffer & vertexBuffer)234 void getStrokeVerticesFromUnclosedVertices(const PaintInfo& paintInfo,
235 const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) {
236 const int extra = paintInfo.capExtraDivisions();
237 const int allocSize = (vertices.size() + extra) * 2;
238
239 Vertex* buffer = vertexBuffer.alloc<Vertex>(allocSize);
240
241 if (extra > 0) {
242 // tessellate both round caps
243 const int last = vertices.size() - 1;
244 float beginTheta = atan2(
245 - (vertices[0].position[0] - vertices[1].position[0]),
246 vertices[0].position[1] - vertices[1].position[1]);
247 float endTheta = atan2(
248 - (vertices[last].position[0] - vertices[last - 1].position[0]),
249 vertices[last].position[1] - vertices[last - 1].position[1]);
250
251 const float dTheta = PI / (extra + 1);
252 const float radialScale = 2.0f / (1 + cos(dTheta));
253
254 int capOffset;
255 for (int i = 0; i < extra; i++) {
256 if (i < extra / 2) {
257 capOffset = extra - 2 * i - 1;
258 } else {
259 capOffset = 2 * i - extra;
260 }
261
262 beginTheta += dTheta;
263 vec2 beginRadialOffset(cos(beginTheta), sin(beginTheta));
264 paintInfo.scaleOffsetForStrokeWidth(beginRadialOffset);
265 Vertex::set(&buffer[capOffset],
266 vertices[0].position[0] + beginRadialOffset.x,
267 vertices[0].position[1] + beginRadialOffset.y);
268
269 endTheta += dTheta;
270 vec2 endRadialOffset(cos(endTheta), sin(endTheta));
271 paintInfo.scaleOffsetForStrokeWidth(endRadialOffset);
272 Vertex::set(&buffer[allocSize - 1 - capOffset],
273 vertices[last].position[0] + endRadialOffset.x,
274 vertices[last].position[1] + endRadialOffset.y);
275 }
276 }
277
278 int currentIndex = extra;
279 const Vertex* current = &(vertices[0]);
280 vec2 lastNormal;
281 for (unsigned int i = 0; i < vertices.size() - 1; i++) {
282 const Vertex* next = &(vertices[i + 1]);
283 vec2 nextNormal(next->position[1] - current->position[1],
284 current->position[0] - next->position[0]);
285 nextNormal.normalize();
286
287 vec2 totalOffset;
288 if (i == 0) {
289 totalOffset = nextNormal;
290 } else {
291 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
292 }
293 paintInfo.scaleOffsetForStrokeWidth(totalOffset);
294
295 Vertex::set(&buffer[currentIndex++],
296 current->position[0] + totalOffset.x,
297 current->position[1] + totalOffset.y);
298
299 Vertex::set(&buffer[currentIndex++],
300 current->position[0] - totalOffset.x,
301 current->position[1] - totalOffset.y);
302
303 current = next;
304 lastNormal = nextNormal;
305 }
306
307 vec2 totalOffset = lastNormal;
308 paintInfo.scaleOffsetForStrokeWidth(totalOffset);
309
310 Vertex::set(&buffer[currentIndex++],
311 current->position[0] + totalOffset.x,
312 current->position[1] + totalOffset.y);
313 Vertex::set(&buffer[currentIndex++],
314 current->position[0] - totalOffset.x,
315 current->position[1] - totalOffset.y);
316
317 DEBUG_DUMP_BUFFER();
318 }
319
320 /**
321 * Populates a vertexBuffer with AlphaVertices to create an anti-aliased fill shape tessellation
322 *
323 * 1 - create the AA perimeter of unit width, by zig-zagging at each point around the perimeter of
324 * the shape (using 2 * perimeter.size() vertices)
325 *
326 * 2 - wrap around to the beginning to complete the perimeter (2 vertices)
327 *
328 * 3 - zig zag back and forth inside the shape to fill it (using perimeter.size() vertices)
329 */
getFillVerticesFromPerimeterAA(const PaintInfo & paintInfo,const Vector<Vertex> & perimeter,VertexBuffer & vertexBuffer)330 void getFillVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter,
331 VertexBuffer& vertexBuffer) {
332 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(perimeter.size() * 3 + 2);
333
334 // generate alpha points - fill Alpha vertex gaps in between each point with
335 // alpha 0 vertex, offset by a scaled normal.
336 int currentIndex = 0;
337 const Vertex* last = &(perimeter[perimeter.size() - 1]);
338 const Vertex* current = &(perimeter[0]);
339 vec2 lastNormal(current->position[1] - last->position[1],
340 last->position[0] - current->position[0]);
341 lastNormal.normalize();
342 for (unsigned int i = 0; i < perimeter.size(); i++) {
343 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]);
344 vec2 nextNormal(next->position[1] - current->position[1],
345 current->position[0] - next->position[0]);
346 nextNormal.normalize();
347
348 // AA point offset from original point is that point's normal, such that each side is offset
349 // by .5 pixels
350 vec2 totalOffset = paintInfo.deriveAAOffset(totalOffsetFromNormals(lastNormal, nextNormal));
351
352 AlphaVertex::set(&buffer[currentIndex++],
353 current->position[0] + totalOffset.x,
354 current->position[1] + totalOffset.y,
355 0.0f);
356 AlphaVertex::set(&buffer[currentIndex++],
357 current->position[0] - totalOffset.x,
358 current->position[1] - totalOffset.y,
359 1.0f);
360
361 last = current;
362 current = next;
363 lastNormal = nextNormal;
364 }
365
366 // wrap around to beginning
367 copyAlphaVertex(&buffer[currentIndex++], &buffer[0]);
368 copyAlphaVertex(&buffer[currentIndex++], &buffer[1]);
369
370 // zig zag between all previous points on the inside of the hull to create a
371 // triangle strip that fills the hull, repeating the first inner point to
372 // create degenerate tris to start inside path
373 int srcAindex = 0;
374 int srcBindex = perimeter.size() - 1;
375 while (srcAindex <= srcBindex) {
376 copyAlphaVertex(&buffer[currentIndex++], &buffer[srcAindex * 2 + 1]);
377 if (srcAindex == srcBindex) break;
378 copyAlphaVertex(&buffer[currentIndex++], &buffer[srcBindex * 2 + 1]);
379 srcAindex++;
380 srcBindex--;
381 }
382
383 DEBUG_DUMP_BUFFER();
384 }
385
386 /**
387 * Stores geometry for a single, AA-perimeter (potentially rounded) cap
388 *
389 * For explanation of constants and general methodoloyg, see comments for
390 * getStrokeVerticesFromUnclosedVerticesAA() below.
391 */
storeCapAA(const PaintInfo & paintInfo,const Vector<Vertex> & vertices,AlphaVertex * buffer,bool isFirst,vec2 normal,int offset)392 inline void storeCapAA(const PaintInfo& paintInfo, const Vector<Vertex>& vertices,
393 AlphaVertex* buffer, bool isFirst, vec2 normal, int offset) {
394 const int extra = paintInfo.capExtraDivisions();
395 const int extraOffset = (extra + 1) / 2;
396 const int capIndex = isFirst
397 ? 2 * offset + 6 + 2 * (extra + extraOffset)
398 : offset + 2 + 2 * extraOffset;
399 if (isFirst) normal *= -1;
400
401 // TODO: this normal should be scaled by radialScale if extra != 0, see totalOffsetFromNormals()
402 vec2 AAOffset = paintInfo.deriveAAOffset(normal);
403
404 vec2 strokeOffset = normal;
405 paintInfo.scaleOffsetForStrokeWidth(strokeOffset);
406 vec2 outerOffset = strokeOffset + AAOffset;
407 vec2 innerOffset = strokeOffset - AAOffset;
408
409 vec2 capAAOffset;
410 if (paintInfo.cap != SkPaint::kRound_Cap) {
411 // if the cap is square or butt, the inside primary cap vertices will be inset in two
412 // directions - both normal to the stroke, and parallel to it.
413 capAAOffset = vec2(-AAOffset.y, AAOffset.x);
414 }
415
416 // determine referencePoint, the center point for the 4 primary cap vertices
417 const Vertex* point = isFirst ? vertices.begin() : (vertices.end() - 1);
418 vec2 referencePoint(point->position[0], point->position[1]);
419 if (paintInfo.cap == SkPaint::kSquare_Cap) {
420 // To account for square cap, move the primary cap vertices (that create the AA edge) by the
421 // stroke offset vector (rotated to be parallel to the stroke)
422 referencePoint += vec2(-strokeOffset.y, strokeOffset.x);
423 }
424
425 AlphaVertex::set(&buffer[capIndex + 0],
426 referencePoint.x + outerOffset.x + capAAOffset.x,
427 referencePoint.y + outerOffset.y + capAAOffset.y,
428 0.0f);
429 AlphaVertex::set(&buffer[capIndex + 1],
430 referencePoint.x + innerOffset.x - capAAOffset.x,
431 referencePoint.y + innerOffset.y - capAAOffset.y,
432 paintInfo.maxAlpha);
433
434 bool isRound = paintInfo.cap == SkPaint::kRound_Cap;
435
436 const int postCapIndex = (isRound && isFirst) ? (2 * extraOffset - 2) : capIndex + (2 * extra);
437 AlphaVertex::set(&buffer[postCapIndex + 2],
438 referencePoint.x - outerOffset.x + capAAOffset.x,
439 referencePoint.y - outerOffset.y + capAAOffset.y,
440 0.0f);
441 AlphaVertex::set(&buffer[postCapIndex + 3],
442 referencePoint.x - innerOffset.x - capAAOffset.x,
443 referencePoint.y - innerOffset.y - capAAOffset.y,
444 paintInfo.maxAlpha);
445
446 if (isRound) {
447 const float dTheta = PI / (extra + 1);
448 const float radialScale = 2.0f / (1 + cos(dTheta));
449 float theta = atan2(normal.y, normal.x);
450 int capPerimIndex = capIndex + 2;
451
452 for (int i = 0; i < extra; i++) {
453 theta += dTheta;
454
455 vec2 radialOffset(cos(theta), sin(theta));
456
457 // scale to compensate for pinching at sharp angles, see totalOffsetFromNormals()
458 radialOffset *= radialScale;
459
460 AAOffset = paintInfo.deriveAAOffset(radialOffset);
461 paintInfo.scaleOffsetForStrokeWidth(radialOffset);
462 AlphaVertex::set(&buffer[capPerimIndex++],
463 referencePoint.x + radialOffset.x + AAOffset.x,
464 referencePoint.y + radialOffset.y + AAOffset.y,
465 0.0f);
466 AlphaVertex::set(&buffer[capPerimIndex++],
467 referencePoint.x + radialOffset.x - AAOffset.x,
468 referencePoint.y + radialOffset.y - AAOffset.y,
469 paintInfo.maxAlpha);
470
471 if (isFirst && i == extra - extraOffset) {
472 //copy most recent two points to first two points
473 copyAlphaVertex(&buffer[0], &buffer[capPerimIndex - 2]);
474 copyAlphaVertex(&buffer[1], &buffer[capPerimIndex - 1]);
475
476 capPerimIndex = 2; // start writing the rest of the round cap at index 2
477 }
478 }
479
480 if (isFirst) {
481 const int startCapFillIndex = capIndex + 2 * (extra - extraOffset) + 4;
482 int capFillIndex = startCapFillIndex;
483 for (int i = 0; i < extra + 2; i += 2) {
484 copyAlphaVertex(&buffer[capFillIndex++], &buffer[1 + i]);
485 // TODO: to support odd numbers of divisions, break here on the last iteration
486 copyAlphaVertex(&buffer[capFillIndex++], &buffer[startCapFillIndex - 3 - i]);
487 }
488 } else {
489 int capFillIndex = 6 * vertices.size() + 2 + 6 * extra - (extra + 2);
490 for (int i = 0; i < extra + 2; i += 2) {
491 copyAlphaVertex(&buffer[capFillIndex++], &buffer[capIndex + 1 + i]);
492 // TODO: to support odd numbers of divisions, break here on the last iteration
493 copyAlphaVertex(&buffer[capFillIndex++], &buffer[capIndex + 3 + 2 * extra - i]);
494 }
495 }
496 return;
497 }
498 if (isFirst) {
499 copyAlphaVertex(&buffer[0], &buffer[postCapIndex + 2]);
500 copyAlphaVertex(&buffer[1], &buffer[postCapIndex + 3]);
501 copyAlphaVertex(&buffer[postCapIndex + 4], &buffer[1]); // degenerate tris (the only two!)
502 copyAlphaVertex(&buffer[postCapIndex + 5], &buffer[postCapIndex + 1]);
503 } else {
504 copyAlphaVertex(&buffer[6 * vertices.size()], &buffer[postCapIndex + 1]);
505 copyAlphaVertex(&buffer[6 * vertices.size() + 1], &buffer[postCapIndex + 3]);
506 }
507 }
508
509 /*
510 the geometry for an aa, capped stroke consists of the following:
511
512 # vertices | function
513 ----------------------------------------------------------------------
514 a) 2 | Start AA perimeter
515 b) 2, 2 * roundDivOff | First half of begin cap's perimeter
516 |
517 2 * middlePts | 'Outer' or 'Top' AA perimeter half (between caps)
518 |
519 a) 4 | End cap's
520 b) 2, 2 * roundDivs, 2 | AA perimeter
521 |
522 2 * middlePts | 'Inner' or 'bottom' AA perimeter half
523 |
524 a) 6 | Begin cap's perimeter
525 b) 2, 2*(rD - rDO + 1), | Last half of begin cap's perimeter
526 roundDivs, 2 |
527 |
528 2 * middlePts | Stroke's full opacity center strip
529 |
530 a) 2 | end stroke
531 b) 2, roundDivs | (and end cap fill, for round)
532
533 Notes:
534 * rows starting with 'a)' denote the Butt or Square cap vertex use, 'b)' denote Round
535
536 * 'middlePts' is (number of points in the unclosed input vertex list, minus 2) times two
537
538 * 'roundDivs' or 'rD' is the number of extra vertices (beyond the minimum of 2) that define the
539 round cap's shape, and is at least two. This will increase with cap size to sufficiently
540 define the cap's level of tessellation.
541
542 * 'roundDivOffset' or 'rDO' is the point about halfway along the start cap's round perimeter, where
543 the stream of vertices for the AA perimeter starts. By starting and ending the perimeter at
544 this offset, the fill of the stroke is drawn from this point with minimal extra vertices.
545
546 This means the outer perimeter starts at:
547 outerIndex = (2) OR (2 + 2 * roundDivOff)
548 the inner perimeter (since it is filled in reverse) starts at:
549 innerIndex = outerIndex + (4 * middlePts) + ((4) OR (4 + 2 * roundDivs)) - 1
550 the stroke starts at:
551 strokeIndex = innerIndex + 1 + ((6) OR (6 + 3 * roundDivs - 2 * roundDivOffset))
552
553 The total needed allocated space is either:
554 2 + 4 + 6 + 2 + 3 * (2 * middlePts) = 14 + 6 * middlePts = 2 + 6 * pts
555 or, for rounded caps:
556 (2 + 2 * rDO) + (4 + 2 * rD) + (2 * (rD - rDO + 1)
557 + roundDivs + 4) + (2 + roundDivs) + 3 * (2 * middlePts)
558 = 14 + 6 * middlePts + 6 * roundDivs
559 = 2 + 6 * pts + 6 * roundDivs
560 */
getStrokeVerticesFromUnclosedVerticesAA(const PaintInfo & paintInfo,const Vector<Vertex> & vertices,VertexBuffer & vertexBuffer)561 void getStrokeVerticesFromUnclosedVerticesAA(const PaintInfo& paintInfo,
562 const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) {
563
564 const int extra = paintInfo.capExtraDivisions();
565 const int allocSize = 6 * vertices.size() + 2 + 6 * extra;
566
567 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(allocSize);
568
569 const int extraOffset = (extra + 1) / 2;
570 int offset = 2 * (vertices.size() - 2);
571 // there is no outer/inner here, using them for consistency with below approach
572 int currentAAOuterIndex = 2 + 2 * extraOffset;
573 int currentAAInnerIndex = currentAAOuterIndex + (2 * offset) + 3 + (2 * extra);
574 int currentStrokeIndex = currentAAInnerIndex + 7 + (3 * extra - 2 * extraOffset);
575
576 const Vertex* last = &(vertices[0]);
577 const Vertex* current = &(vertices[1]);
578 vec2 lastNormal(current->position[1] - last->position[1],
579 last->position[0] - current->position[0]);
580 lastNormal.normalize();
581
582 // TODO: use normal from bezier traversal for cap, instead of from vertices
583 storeCapAA(paintInfo, vertices, buffer, true, lastNormal, offset);
584
585 for (unsigned int i = 1; i < vertices.size() - 1; i++) {
586 const Vertex* next = &(vertices[i + 1]);
587 vec2 nextNormal(next->position[1] - current->position[1],
588 current->position[0] - next->position[0]);
589 nextNormal.normalize();
590
591 vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
592 vec2 AAOffset = paintInfo.deriveAAOffset(totalOffset);
593
594 vec2 innerOffset = totalOffset;
595 paintInfo.scaleOffsetForStrokeWidth(innerOffset);
596 vec2 outerOffset = innerOffset + AAOffset;
597 innerOffset -= AAOffset;
598
599 AlphaVertex::set(&buffer[currentAAOuterIndex++],
600 current->position[0] + outerOffset.x,
601 current->position[1] + outerOffset.y,
602 0.0f);
603 AlphaVertex::set(&buffer[currentAAOuterIndex++],
604 current->position[0] + innerOffset.x,
605 current->position[1] + innerOffset.y,
606 paintInfo.maxAlpha);
607
608 AlphaVertex::set(&buffer[currentStrokeIndex++],
609 current->position[0] + innerOffset.x,
610 current->position[1] + innerOffset.y,
611 paintInfo.maxAlpha);
612 AlphaVertex::set(&buffer[currentStrokeIndex++],
613 current->position[0] - innerOffset.x,
614 current->position[1] - innerOffset.y,
615 paintInfo.maxAlpha);
616
617 AlphaVertex::set(&buffer[currentAAInnerIndex--],
618 current->position[0] - innerOffset.x,
619 current->position[1] - innerOffset.y,
620 paintInfo.maxAlpha);
621 AlphaVertex::set(&buffer[currentAAInnerIndex--],
622 current->position[0] - outerOffset.x,
623 current->position[1] - outerOffset.y,
624 0.0f);
625
626 current = next;
627 lastNormal = nextNormal;
628 }
629
630 // TODO: use normal from bezier traversal for cap, instead of from vertices
631 storeCapAA(paintInfo, vertices, buffer, false, lastNormal, offset);
632
633 DEBUG_DUMP_ALPHA_BUFFER();
634 }
635
636
getStrokeVerticesFromPerimeterAA(const PaintInfo & paintInfo,const Vector<Vertex> & perimeter,VertexBuffer & vertexBuffer)637 void getStrokeVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter,
638 VertexBuffer& vertexBuffer) {
639 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(6 * perimeter.size() + 8);
640
641 int offset = 2 * perimeter.size() + 3;
642 int currentAAOuterIndex = 0;
643 int currentStrokeIndex = offset;
644 int currentAAInnerIndex = offset * 2;
645
646 const Vertex* last = &(perimeter[perimeter.size() - 1]);
647 const Vertex* current = &(perimeter[0]);
648 vec2 lastNormal(current->position[1] - last->position[1],
649 last->position[0] - current->position[0]);
650 lastNormal.normalize();
651 for (unsigned int i = 0; i < perimeter.size(); i++) {
652 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]);
653 vec2 nextNormal(next->position[1] - current->position[1],
654 current->position[0] - next->position[0]);
655 nextNormal.normalize();
656
657 vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
658 vec2 AAOffset = paintInfo.deriveAAOffset(totalOffset);
659
660 vec2 innerOffset = totalOffset;
661 paintInfo.scaleOffsetForStrokeWidth(innerOffset);
662 vec2 outerOffset = innerOffset + AAOffset;
663 innerOffset -= AAOffset;
664
665 AlphaVertex::set(&buffer[currentAAOuterIndex++],
666 current->position[0] + outerOffset.x,
667 current->position[1] + outerOffset.y,
668 0.0f);
669 AlphaVertex::set(&buffer[currentAAOuterIndex++],
670 current->position[0] + innerOffset.x,
671 current->position[1] + innerOffset.y,
672 paintInfo.maxAlpha);
673
674 AlphaVertex::set(&buffer[currentStrokeIndex++],
675 current->position[0] + innerOffset.x,
676 current->position[1] + innerOffset.y,
677 paintInfo.maxAlpha);
678 AlphaVertex::set(&buffer[currentStrokeIndex++],
679 current->position[0] - innerOffset.x,
680 current->position[1] - innerOffset.y,
681 paintInfo.maxAlpha);
682
683 AlphaVertex::set(&buffer[currentAAInnerIndex++],
684 current->position[0] - innerOffset.x,
685 current->position[1] - innerOffset.y,
686 paintInfo.maxAlpha);
687 AlphaVertex::set(&buffer[currentAAInnerIndex++],
688 current->position[0] - outerOffset.x,
689 current->position[1] - outerOffset.y,
690 0.0f);
691
692 last = current;
693 current = next;
694 lastNormal = nextNormal;
695 }
696
697 // wrap each strip around to beginning, creating degenerate tris to bridge strips
698 copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[0]);
699 copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[1]);
700 copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[1]);
701
702 copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset]);
703 copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset + 1]);
704 copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset + 1]);
705
706 copyAlphaVertex(&buffer[currentAAInnerIndex++], &buffer[2 * offset]);
707 copyAlphaVertex(&buffer[currentAAInnerIndex++], &buffer[2 * offset + 1]);
708 // don't need to create last degenerate tri
709
710 DEBUG_DUMP_ALPHA_BUFFER();
711 }
712
tessellatePath(const SkPath & path,const SkPaint * paint,const mat4 * transform,VertexBuffer & vertexBuffer)713 void PathTessellator::tessellatePath(const SkPath &path, const SkPaint* paint,
714 const mat4 *transform, VertexBuffer& vertexBuffer) {
715 ATRACE_CALL();
716
717 const PaintInfo paintInfo(paint, transform);
718
719 Vector<Vertex> tempVertices;
720 float threshInvScaleX = paintInfo.inverseScaleX;
721 float threshInvScaleY = paintInfo.inverseScaleY;
722 if (paintInfo.style == SkPaint::kStroke_Style) {
723 // alter the bezier recursion threshold values we calculate in order to compensate for
724 // expansion done after the path vertices are found
725 SkRect bounds = path.getBounds();
726 if (!bounds.isEmpty()) {
727 threshInvScaleX *= bounds.width() / (bounds.width() + paint->getStrokeWidth());
728 threshInvScaleY *= bounds.height() / (bounds.height() + paint->getStrokeWidth());
729 }
730 }
731
732 // force close if we're filling the path, since fill path expects closed perimeter.
733 bool forceClose = paintInfo.style != SkPaint::kStroke_Style;
734 bool wasClosed = approximatePathOutlineVertices(path, forceClose,
735 threshInvScaleX * threshInvScaleX, threshInvScaleY * threshInvScaleY, tempVertices);
736
737 if (!tempVertices.size()) {
738 // path was empty, return without allocating vertex buffer
739 return;
740 }
741
742 #if VERTEX_DEBUG
743 for (unsigned int i = 0; i < tempVertices.size(); i++) {
744 ALOGD("orig path: point at %f %f",
745 tempVertices[i].position[0], tempVertices[i].position[1]);
746 }
747 #endif
748
749 if (paintInfo.style == SkPaint::kStroke_Style) {
750 if (!paintInfo.isAA) {
751 if (wasClosed) {
752 getStrokeVerticesFromPerimeter(paintInfo, tempVertices, vertexBuffer);
753 } else {
754 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer);
755 }
756
757 } else {
758 if (wasClosed) {
759 getStrokeVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer);
760 } else {
761 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer);
762 }
763 }
764 } else {
765 // For kStrokeAndFill style, the path should be adjusted externally.
766 // It will be treated as a fill here.
767 if (!paintInfo.isAA) {
768 getFillVerticesFromPerimeter(tempVertices, vertexBuffer);
769 } else {
770 getFillVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer);
771 }
772 }
773 }
774
expandRectToCoverVertex(SkRect & rect,const Vertex & vertex)775 static void expandRectToCoverVertex(SkRect& rect, const Vertex& vertex) {
776 rect.fLeft = fminf(rect.fLeft, vertex.position[0]);
777 rect.fTop = fminf(rect.fTop, vertex.position[1]);
778 rect.fRight = fmaxf(rect.fRight, vertex.position[0]);
779 rect.fBottom = fmaxf(rect.fBottom, vertex.position[1]);
780 }
781
tessellateLines(const float * points,int count,SkPaint * paint,const mat4 * transform,SkRect & bounds,VertexBuffer & vertexBuffer)782 void PathTessellator::tessellateLines(const float* points, int count, SkPaint* paint,
783 const mat4* transform, SkRect& bounds, VertexBuffer& vertexBuffer) {
784 ATRACE_CALL();
785 const PaintInfo paintInfo(paint, transform);
786
787 const int extra = paintInfo.capExtraDivisions();
788 int numLines = count / 4;
789 int lineAllocSize;
790 // pre-allocate space for lines in the buffer, and degenerate tris in between
791 if (paintInfo.isAA) {
792 lineAllocSize = 6 * (2) + 2 + 6 * extra;
793 vertexBuffer.alloc<AlphaVertex>(numLines * lineAllocSize + (numLines - 1) * 2);
794 } else {
795 lineAllocSize = 2 * ((2) + extra);
796 vertexBuffer.alloc<Vertex>(numLines * lineAllocSize + (numLines - 1) * 2);
797 }
798
799 Vector<Vertex> tempVertices;
800 tempVertices.push();
801 tempVertices.push();
802 Vertex* tempVerticesData = tempVertices.editArray();
803 bounds.set(points[0], points[1], points[0], points[1]);
804 for (int i = 0; i < count; i += 4) {
805 Vertex::set(&(tempVerticesData[0]), points[i + 0], points[i + 1]);
806 Vertex::set(&(tempVerticesData[1]), points[i + 2], points[i + 3]);
807
808 if (paintInfo.isAA) {
809 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer);
810 } else {
811 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer);
812 }
813
814 // calculate bounds
815 expandRectToCoverVertex(bounds, tempVerticesData[0]);
816 expandRectToCoverVertex(bounds, tempVerticesData[1]);
817 }
818
819 expandBoundsForStroke(bounds, paint, true); // force-expand bounds to incorporate stroke
820
821 // since multiple objects tessellated into buffer, separate them with degen tris
822 if (paintInfo.isAA) {
823 vertexBuffer.createDegenerateSeparators<AlphaVertex>(lineAllocSize);
824 } else {
825 vertexBuffer.createDegenerateSeparators<Vertex>(lineAllocSize);
826 }
827 }
828
829 ///////////////////////////////////////////////////////////////////////////////
830 // Simple path line approximation
831 ///////////////////////////////////////////////////////////////////////////////
832
pushToVector(Vector<Vertex> & vertices,float x,float y)833 void pushToVector(Vector<Vertex>& vertices, float x, float y) {
834 // TODO: make this not yuck
835 vertices.push();
836 Vertex* newVertex = &(vertices.editArray()[vertices.size() - 1]);
837 Vertex::set(newVertex, x, y);
838 }
839
approximatePathOutlineVertices(const SkPath & path,bool forceClose,float sqrInvScaleX,float sqrInvScaleY,Vector<Vertex> & outputVertices)840 bool PathTessellator::approximatePathOutlineVertices(const SkPath& path, bool forceClose,
841 float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) {
842 ATRACE_CALL();
843
844 // TODO: to support joins other than sharp miter, join vertices should be labelled in the
845 // perimeter, or resolved into more vertices. Reconsider forceClose-ing in that case.
846 SkPath::Iter iter(path, forceClose);
847 SkPoint pts[4];
848 SkPath::Verb v;
849 while (SkPath::kDone_Verb != (v = iter.next(pts))) {
850 switch (v) {
851 case SkPath::kMove_Verb:
852 pushToVector(outputVertices, pts[0].x(), pts[0].y());
853 ALOGV("Move to pos %f %f", pts[0].x(), pts[0].y());
854 break;
855 case SkPath::kClose_Verb:
856 ALOGV("Close at pos %f %f", pts[0].x(), pts[0].y());
857 break;
858 case SkPath::kLine_Verb:
859 ALOGV("kLine_Verb %f %f -> %f %f", pts[0].x(), pts[0].y(), pts[1].x(), pts[1].y());
860 pushToVector(outputVertices, pts[1].x(), pts[1].y());
861 break;
862 case SkPath::kQuad_Verb:
863 ALOGV("kQuad_Verb");
864 recursiveQuadraticBezierVertices(
865 pts[0].x(), pts[0].y(),
866 pts[2].x(), pts[2].y(),
867 pts[1].x(), pts[1].y(),
868 sqrInvScaleX, sqrInvScaleY, outputVertices);
869 break;
870 case SkPath::kCubic_Verb:
871 ALOGV("kCubic_Verb");
872 recursiveCubicBezierVertices(
873 pts[0].x(), pts[0].y(),
874 pts[1].x(), pts[1].y(),
875 pts[3].x(), pts[3].y(),
876 pts[2].x(), pts[2].y(),
877 sqrInvScaleX, sqrInvScaleY, outputVertices);
878 break;
879 default:
880 break;
881 }
882 }
883
884 int size = outputVertices.size();
885 if (size >= 2 && outputVertices[0].position[0] == outputVertices[size - 1].position[0] &&
886 outputVertices[0].position[1] == outputVertices[size - 1].position[1]) {
887 outputVertices.pop();
888 return true;
889 }
890 return false;
891 }
892
893 ///////////////////////////////////////////////////////////////////////////////
894 // Bezier approximation
895 ///////////////////////////////////////////////////////////////////////////////
896
recursiveCubicBezierVertices(float p1x,float p1y,float c1x,float c1y,float p2x,float p2y,float c2x,float c2y,float sqrInvScaleX,float sqrInvScaleY,Vector<Vertex> & outputVertices)897 void PathTessellator::recursiveCubicBezierVertices(
898 float p1x, float p1y, float c1x, float c1y,
899 float p2x, float p2y, float c2x, float c2y,
900 float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) {
901 float dx = p2x - p1x;
902 float dy = p2y - p1y;
903 float d1 = fabs((c1x - p2x) * dy - (c1y - p2y) * dx);
904 float d2 = fabs((c2x - p2x) * dy - (c2y - p2y) * dx);
905 float d = d1 + d2;
906
907 // multiplying by sqrInvScaleY/X equivalent to multiplying in dimensional scale factors
908
909 if (d * d < THRESHOLD * THRESHOLD * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) {
910 // below thresh, draw line by adding endpoint
911 pushToVector(outputVertices, p2x, p2y);
912 } else {
913 float p1c1x = (p1x + c1x) * 0.5f;
914 float p1c1y = (p1y + c1y) * 0.5f;
915 float p2c2x = (p2x + c2x) * 0.5f;
916 float p2c2y = (p2y + c2y) * 0.5f;
917
918 float c1c2x = (c1x + c2x) * 0.5f;
919 float c1c2y = (c1y + c2y) * 0.5f;
920
921 float p1c1c2x = (p1c1x + c1c2x) * 0.5f;
922 float p1c1c2y = (p1c1y + c1c2y) * 0.5f;
923
924 float p2c1c2x = (p2c2x + c1c2x) * 0.5f;
925 float p2c1c2y = (p2c2y + c1c2y) * 0.5f;
926
927 float mx = (p1c1c2x + p2c1c2x) * 0.5f;
928 float my = (p1c1c2y + p2c1c2y) * 0.5f;
929
930 recursiveCubicBezierVertices(
931 p1x, p1y, p1c1x, p1c1y,
932 mx, my, p1c1c2x, p1c1c2y,
933 sqrInvScaleX, sqrInvScaleY, outputVertices);
934 recursiveCubicBezierVertices(
935 mx, my, p2c1c2x, p2c1c2y,
936 p2x, p2y, p2c2x, p2c2y,
937 sqrInvScaleX, sqrInvScaleY, outputVertices);
938 }
939 }
940
recursiveQuadraticBezierVertices(float ax,float ay,float bx,float by,float cx,float cy,float sqrInvScaleX,float sqrInvScaleY,Vector<Vertex> & outputVertices)941 void PathTessellator::recursiveQuadraticBezierVertices(
942 float ax, float ay,
943 float bx, float by,
944 float cx, float cy,
945 float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) {
946 float dx = bx - ax;
947 float dy = by - ay;
948 float d = (cx - bx) * dy - (cy - by) * dx;
949
950 if (d * d < THRESHOLD * THRESHOLD * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) {
951 // below thresh, draw line by adding endpoint
952 pushToVector(outputVertices, bx, by);
953 } else {
954 float acx = (ax + cx) * 0.5f;
955 float bcx = (bx + cx) * 0.5f;
956 float acy = (ay + cy) * 0.5f;
957 float bcy = (by + cy) * 0.5f;
958
959 // midpoint
960 float mx = (acx + bcx) * 0.5f;
961 float my = (acy + bcy) * 0.5f;
962
963 recursiveQuadraticBezierVertices(ax, ay, mx, my, acx, acy,
964 sqrInvScaleX, sqrInvScaleY, outputVertices);
965 recursiveQuadraticBezierVertices(mx, my, bx, by, bcx, bcy,
966 sqrInvScaleX, sqrInvScaleY, outputVertices);
967 }
968 }
969
970 }; // namespace uirenderer
971 }; // namespace android
972