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 static 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 static 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 static 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
storeBeginEnd(const PaintInfo & paintInfo,const Vertex & center,const vec2 & normal,Vertex * buffer,int & currentIndex,bool begin)227 static inline void storeBeginEnd(const PaintInfo& paintInfo, const Vertex& center,
228 const vec2& normal, Vertex* buffer, int& currentIndex, bool begin) {
229 vec2 strokeOffset = normal;
230 paintInfo.scaleOffsetForStrokeWidth(strokeOffset);
231
232 vec2 referencePoint(center.position[0], center.position[1]);
233 if (paintInfo.cap == SkPaint::kSquare_Cap) {
234 referencePoint += vec2(-strokeOffset.y, strokeOffset.x) * (begin ? -1 : 1);
235 }
236
237 Vertex::set(&buffer[currentIndex++], referencePoint + strokeOffset);
238 Vertex::set(&buffer[currentIndex++], referencePoint - strokeOffset);
239 }
240
241 /**
242 * Fills a vertexBuffer with non-alpha vertices similar to getStrokeVerticesFromPerimeter, except:
243 *
244 * 1 - Doesn't need to wrap around, since the input vertices are unclosed
245 *
246 * 2 - can zig-zag across 'extra' vertices at either end, to create round caps
247 */
getStrokeVerticesFromUnclosedVertices(const PaintInfo & paintInfo,const Vector<Vertex> & vertices,VertexBuffer & vertexBuffer)248 void getStrokeVerticesFromUnclosedVertices(const PaintInfo& paintInfo,
249 const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) {
250 const int extra = paintInfo.capExtraDivisions();
251 const int allocSize = (vertices.size() + extra) * 2;
252 Vertex* buffer = vertexBuffer.alloc<Vertex>(allocSize);
253
254 const int lastIndex = vertices.size() - 1;
255 if (extra > 0) {
256 // tessellate both round caps
257 float beginTheta = atan2(
258 - (vertices[0].position[0] - vertices[1].position[0]),
259 vertices[0].position[1] - vertices[1].position[1]);
260 float endTheta = atan2(
261 - (vertices[lastIndex].position[0] - vertices[lastIndex - 1].position[0]),
262 vertices[lastIndex].position[1] - vertices[lastIndex - 1].position[1]);
263 const float dTheta = PI / (extra + 1);
264 const float radialScale = 2.0f / (1 + cos(dTheta));
265
266 int capOffset;
267 for (int i = 0; i < extra; i++) {
268 if (i < extra / 2) {
269 capOffset = extra - 2 * i - 1;
270 } else {
271 capOffset = 2 * i - extra;
272 }
273
274 beginTheta += dTheta;
275 vec2 beginRadialOffset(cos(beginTheta), sin(beginTheta));
276 paintInfo.scaleOffsetForStrokeWidth(beginRadialOffset);
277 Vertex::set(&buffer[capOffset],
278 vertices[0].position[0] + beginRadialOffset.x,
279 vertices[0].position[1] + beginRadialOffset.y);
280
281 endTheta += dTheta;
282 vec2 endRadialOffset(cos(endTheta), sin(endTheta));
283 paintInfo.scaleOffsetForStrokeWidth(endRadialOffset);
284 Vertex::set(&buffer[allocSize - 1 - capOffset],
285 vertices[lastIndex].position[0] + endRadialOffset.x,
286 vertices[lastIndex].position[1] + endRadialOffset.y);
287 }
288 }
289
290 int currentIndex = extra;
291 const Vertex* last = &(vertices[0]);
292 const Vertex* current = &(vertices[1]);
293 vec2 lastNormal(current->position[1] - last->position[1],
294 last->position[0] - current->position[0]);
295 lastNormal.normalize();
296
297 storeBeginEnd(paintInfo, vertices[0], lastNormal, buffer, currentIndex, true);
298
299 for (unsigned int i = 1; i < vertices.size() - 1; i++) {
300 const Vertex* next = &(vertices[i + 1]);
301 vec2 nextNormal(next->position[1] - current->position[1],
302 current->position[0] - next->position[0]);
303 nextNormal.normalize();
304
305 vec2 strokeOffset = totalOffsetFromNormals(lastNormal, nextNormal);
306 paintInfo.scaleOffsetForStrokeWidth(strokeOffset);
307
308 vec2 center(current->position[0], current->position[1]);
309 Vertex::set(&buffer[currentIndex++], center + strokeOffset);
310 Vertex::set(&buffer[currentIndex++], center - strokeOffset);
311
312 current = next;
313 lastNormal = nextNormal;
314 }
315
316 storeBeginEnd(paintInfo, vertices[lastIndex], lastNormal, buffer, currentIndex, false);
317
318 DEBUG_DUMP_BUFFER();
319 }
320
321 /**
322 * Populates a vertexBuffer with AlphaVertices to create an anti-aliased fill shape tessellation
323 *
324 * 1 - create the AA perimeter of unit width, by zig-zagging at each point around the perimeter of
325 * the shape (using 2 * perimeter.size() vertices)
326 *
327 * 2 - wrap around to the beginning to complete the perimeter (2 vertices)
328 *
329 * 3 - zig zag back and forth inside the shape to fill it (using perimeter.size() vertices)
330 */
getFillVerticesFromPerimeterAA(const PaintInfo & paintInfo,const Vector<Vertex> & perimeter,VertexBuffer & vertexBuffer)331 void getFillVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter,
332 VertexBuffer& vertexBuffer) {
333 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(perimeter.size() * 3 + 2);
334
335 // generate alpha points - fill Alpha vertex gaps in between each point with
336 // alpha 0 vertex, offset by a scaled normal.
337 int currentIndex = 0;
338 const Vertex* last = &(perimeter[perimeter.size() - 1]);
339 const Vertex* current = &(perimeter[0]);
340 vec2 lastNormal(current->position[1] - last->position[1],
341 last->position[0] - current->position[0]);
342 lastNormal.normalize();
343 for (unsigned int i = 0; i < perimeter.size(); i++) {
344 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]);
345 vec2 nextNormal(next->position[1] - current->position[1],
346 current->position[0] - next->position[0]);
347 nextNormal.normalize();
348
349 // AA point offset from original point is that point's normal, such that each side is offset
350 // by .5 pixels
351 vec2 totalOffset = paintInfo.deriveAAOffset(totalOffsetFromNormals(lastNormal, nextNormal));
352
353 AlphaVertex::set(&buffer[currentIndex++],
354 current->position[0] + totalOffset.x,
355 current->position[1] + totalOffset.y,
356 0.0f);
357 AlphaVertex::set(&buffer[currentIndex++],
358 current->position[0] - totalOffset.x,
359 current->position[1] - totalOffset.y,
360 1.0f);
361
362 last = current;
363 current = next;
364 lastNormal = nextNormal;
365 }
366
367 // wrap around to beginning
368 copyAlphaVertex(&buffer[currentIndex++], &buffer[0]);
369 copyAlphaVertex(&buffer[currentIndex++], &buffer[1]);
370
371 // zig zag between all previous points on the inside of the hull to create a
372 // triangle strip that fills the hull, repeating the first inner point to
373 // create degenerate tris to start inside path
374 int srcAindex = 0;
375 int srcBindex = perimeter.size() - 1;
376 while (srcAindex <= srcBindex) {
377 copyAlphaVertex(&buffer[currentIndex++], &buffer[srcAindex * 2 + 1]);
378 if (srcAindex == srcBindex) break;
379 copyAlphaVertex(&buffer[currentIndex++], &buffer[srcBindex * 2 + 1]);
380 srcAindex++;
381 srcBindex--;
382 }
383
384 DEBUG_DUMP_BUFFER();
385 }
386
387 /**
388 * Stores geometry for a single, AA-perimeter (potentially rounded) cap
389 *
390 * For explanation of constants and general methodoloyg, see comments for
391 * getStrokeVerticesFromUnclosedVerticesAA() below.
392 */
storeCapAA(const PaintInfo & paintInfo,const Vector<Vertex> & vertices,AlphaVertex * buffer,bool isFirst,vec2 normal,int offset)393 inline static void storeCapAA(const PaintInfo& paintInfo, const Vector<Vertex>& vertices,
394 AlphaVertex* buffer, bool isFirst, vec2 normal, int offset) {
395 const int extra = paintInfo.capExtraDivisions();
396 const int extraOffset = (extra + 1) / 2;
397 const int capIndex = isFirst
398 ? 2 * offset + 6 + 2 * (extra + extraOffset)
399 : offset + 2 + 2 * extraOffset;
400 if (isFirst) normal *= -1;
401
402 // TODO: this normal should be scaled by radialScale if extra != 0, see totalOffsetFromNormals()
403 vec2 AAOffset = paintInfo.deriveAAOffset(normal);
404
405 vec2 strokeOffset = normal;
406 paintInfo.scaleOffsetForStrokeWidth(strokeOffset);
407 vec2 outerOffset = strokeOffset + AAOffset;
408 vec2 innerOffset = strokeOffset - AAOffset;
409
410 vec2 capAAOffset;
411 if (paintInfo.cap != SkPaint::kRound_Cap) {
412 // if the cap is square or butt, the inside primary cap vertices will be inset in two
413 // directions - both normal to the stroke, and parallel to it.
414 capAAOffset = vec2(-AAOffset.y, AAOffset.x);
415 }
416
417 // determine referencePoint, the center point for the 4 primary cap vertices
418 const Vertex* point = isFirst ? vertices.begin() : (vertices.end() - 1);
419 vec2 referencePoint(point->position[0], point->position[1]);
420 if (paintInfo.cap == SkPaint::kSquare_Cap) {
421 // To account for square cap, move the primary cap vertices (that create the AA edge) by the
422 // stroke offset vector (rotated to be parallel to the stroke)
423 referencePoint += vec2(-strokeOffset.y, strokeOffset.x);
424 }
425
426 AlphaVertex::set(&buffer[capIndex + 0],
427 referencePoint.x + outerOffset.x + capAAOffset.x,
428 referencePoint.y + outerOffset.y + capAAOffset.y,
429 0.0f);
430 AlphaVertex::set(&buffer[capIndex + 1],
431 referencePoint.x + innerOffset.x - capAAOffset.x,
432 referencePoint.y + innerOffset.y - capAAOffset.y,
433 paintInfo.maxAlpha);
434
435 bool isRound = paintInfo.cap == SkPaint::kRound_Cap;
436
437 const int postCapIndex = (isRound && isFirst) ? (2 * extraOffset - 2) : capIndex + (2 * extra);
438 AlphaVertex::set(&buffer[postCapIndex + 2],
439 referencePoint.x - outerOffset.x + capAAOffset.x,
440 referencePoint.y - outerOffset.y + capAAOffset.y,
441 0.0f);
442 AlphaVertex::set(&buffer[postCapIndex + 3],
443 referencePoint.x - innerOffset.x - capAAOffset.x,
444 referencePoint.y - innerOffset.y - capAAOffset.y,
445 paintInfo.maxAlpha);
446
447 if (isRound) {
448 const float dTheta = PI / (extra + 1);
449 const float radialScale = 2.0f / (1 + cos(dTheta));
450 float theta = atan2(normal.y, normal.x);
451 int capPerimIndex = capIndex + 2;
452
453 for (int i = 0; i < extra; i++) {
454 theta += dTheta;
455
456 vec2 radialOffset(cos(theta), sin(theta));
457
458 // scale to compensate for pinching at sharp angles, see totalOffsetFromNormals()
459 radialOffset *= radialScale;
460
461 AAOffset = paintInfo.deriveAAOffset(radialOffset);
462 paintInfo.scaleOffsetForStrokeWidth(radialOffset);
463 AlphaVertex::set(&buffer[capPerimIndex++],
464 referencePoint.x + radialOffset.x + AAOffset.x,
465 referencePoint.y + radialOffset.y + AAOffset.y,
466 0.0f);
467 AlphaVertex::set(&buffer[capPerimIndex++],
468 referencePoint.x + radialOffset.x - AAOffset.x,
469 referencePoint.y + radialOffset.y - AAOffset.y,
470 paintInfo.maxAlpha);
471
472 if (isFirst && i == extra - extraOffset) {
473 //copy most recent two points to first two points
474 copyAlphaVertex(&buffer[0], &buffer[capPerimIndex - 2]);
475 copyAlphaVertex(&buffer[1], &buffer[capPerimIndex - 1]);
476
477 capPerimIndex = 2; // start writing the rest of the round cap at index 2
478 }
479 }
480
481 if (isFirst) {
482 const int startCapFillIndex = capIndex + 2 * (extra - extraOffset) + 4;
483 int capFillIndex = startCapFillIndex;
484 for (int i = 0; i < extra + 2; i += 2) {
485 copyAlphaVertex(&buffer[capFillIndex++], &buffer[1 + i]);
486 // TODO: to support odd numbers of divisions, break here on the last iteration
487 copyAlphaVertex(&buffer[capFillIndex++], &buffer[startCapFillIndex - 3 - i]);
488 }
489 } else {
490 int capFillIndex = 6 * vertices.size() + 2 + 6 * extra - (extra + 2);
491 for (int i = 0; i < extra + 2; i += 2) {
492 copyAlphaVertex(&buffer[capFillIndex++], &buffer[capIndex + 1 + i]);
493 // TODO: to support odd numbers of divisions, break here on the last iteration
494 copyAlphaVertex(&buffer[capFillIndex++], &buffer[capIndex + 3 + 2 * extra - i]);
495 }
496 }
497 return;
498 }
499 if (isFirst) {
500 copyAlphaVertex(&buffer[0], &buffer[postCapIndex + 2]);
501 copyAlphaVertex(&buffer[1], &buffer[postCapIndex + 3]);
502 copyAlphaVertex(&buffer[postCapIndex + 4], &buffer[1]); // degenerate tris (the only two!)
503 copyAlphaVertex(&buffer[postCapIndex + 5], &buffer[postCapIndex + 1]);
504 } else {
505 copyAlphaVertex(&buffer[6 * vertices.size()], &buffer[postCapIndex + 1]);
506 copyAlphaVertex(&buffer[6 * vertices.size() + 1], &buffer[postCapIndex + 3]);
507 }
508 }
509
510 /*
511 the geometry for an aa, capped stroke consists of the following:
512
513 # vertices | function
514 ----------------------------------------------------------------------
515 a) 2 | Start AA perimeter
516 b) 2, 2 * roundDivOff | First half of begin cap's perimeter
517 |
518 2 * middlePts | 'Outer' or 'Top' AA perimeter half (between caps)
519 |
520 a) 4 | End cap's
521 b) 2, 2 * roundDivs, 2 | AA perimeter
522 |
523 2 * middlePts | 'Inner' or 'bottom' AA perimeter half
524 |
525 a) 6 | Begin cap's perimeter
526 b) 2, 2*(rD - rDO + 1), | Last half of begin cap's perimeter
527 roundDivs, 2 |
528 |
529 2 * middlePts | Stroke's full opacity center strip
530 |
531 a) 2 | end stroke
532 b) 2, roundDivs | (and end cap fill, for round)
533
534 Notes:
535 * rows starting with 'a)' denote the Butt or Square cap vertex use, 'b)' denote Round
536
537 * 'middlePts' is (number of points in the unclosed input vertex list, minus 2) times two
538
539 * 'roundDivs' or 'rD' is the number of extra vertices (beyond the minimum of 2) that define the
540 round cap's shape, and is at least two. This will increase with cap size to sufficiently
541 define the cap's level of tessellation.
542
543 * 'roundDivOffset' or 'rDO' is the point about halfway along the start cap's round perimeter, where
544 the stream of vertices for the AA perimeter starts. By starting and ending the perimeter at
545 this offset, the fill of the stroke is drawn from this point with minimal extra vertices.
546
547 This means the outer perimeter starts at:
548 outerIndex = (2) OR (2 + 2 * roundDivOff)
549 the inner perimeter (since it is filled in reverse) starts at:
550 innerIndex = outerIndex + (4 * middlePts) + ((4) OR (4 + 2 * roundDivs)) - 1
551 the stroke starts at:
552 strokeIndex = innerIndex + 1 + ((6) OR (6 + 3 * roundDivs - 2 * roundDivOffset))
553
554 The total needed allocated space is either:
555 2 + 4 + 6 + 2 + 3 * (2 * middlePts) = 14 + 6 * middlePts = 2 + 6 * pts
556 or, for rounded caps:
557 (2 + 2 * rDO) + (4 + 2 * rD) + (2 * (rD - rDO + 1)
558 + roundDivs + 4) + (2 + roundDivs) + 3 * (2 * middlePts)
559 = 14 + 6 * middlePts + 6 * roundDivs
560 = 2 + 6 * pts + 6 * roundDivs
561 */
getStrokeVerticesFromUnclosedVerticesAA(const PaintInfo & paintInfo,const Vector<Vertex> & vertices,VertexBuffer & vertexBuffer)562 void getStrokeVerticesFromUnclosedVerticesAA(const PaintInfo& paintInfo,
563 const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) {
564
565 const int extra = paintInfo.capExtraDivisions();
566 const int allocSize = 6 * vertices.size() + 2 + 6 * extra;
567
568 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(allocSize);
569
570 const int extraOffset = (extra + 1) / 2;
571 int offset = 2 * (vertices.size() - 2);
572 // there is no outer/inner here, using them for consistency with below approach
573 int currentAAOuterIndex = 2 + 2 * extraOffset;
574 int currentAAInnerIndex = currentAAOuterIndex + (2 * offset) + 3 + (2 * extra);
575 int currentStrokeIndex = currentAAInnerIndex + 7 + (3 * extra - 2 * extraOffset);
576
577 const Vertex* last = &(vertices[0]);
578 const Vertex* current = &(vertices[1]);
579 vec2 lastNormal(current->position[1] - last->position[1],
580 last->position[0] - current->position[0]);
581 lastNormal.normalize();
582
583 // TODO: use normal from bezier traversal for cap, instead of from vertices
584 storeCapAA(paintInfo, vertices, buffer, true, lastNormal, offset);
585
586 for (unsigned int i = 1; i < vertices.size() - 1; i++) {
587 const Vertex* next = &(vertices[i + 1]);
588 vec2 nextNormal(next->position[1] - current->position[1],
589 current->position[0] - next->position[0]);
590 nextNormal.normalize();
591
592 vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
593 vec2 AAOffset = paintInfo.deriveAAOffset(totalOffset);
594
595 vec2 innerOffset = totalOffset;
596 paintInfo.scaleOffsetForStrokeWidth(innerOffset);
597 vec2 outerOffset = innerOffset + AAOffset;
598 innerOffset -= AAOffset;
599
600 AlphaVertex::set(&buffer[currentAAOuterIndex++],
601 current->position[0] + outerOffset.x,
602 current->position[1] + outerOffset.y,
603 0.0f);
604 AlphaVertex::set(&buffer[currentAAOuterIndex++],
605 current->position[0] + innerOffset.x,
606 current->position[1] + innerOffset.y,
607 paintInfo.maxAlpha);
608
609 AlphaVertex::set(&buffer[currentStrokeIndex++],
610 current->position[0] + innerOffset.x,
611 current->position[1] + innerOffset.y,
612 paintInfo.maxAlpha);
613 AlphaVertex::set(&buffer[currentStrokeIndex++],
614 current->position[0] - innerOffset.x,
615 current->position[1] - innerOffset.y,
616 paintInfo.maxAlpha);
617
618 AlphaVertex::set(&buffer[currentAAInnerIndex--],
619 current->position[0] - innerOffset.x,
620 current->position[1] - innerOffset.y,
621 paintInfo.maxAlpha);
622 AlphaVertex::set(&buffer[currentAAInnerIndex--],
623 current->position[0] - outerOffset.x,
624 current->position[1] - outerOffset.y,
625 0.0f);
626
627 current = next;
628 lastNormal = nextNormal;
629 }
630
631 // TODO: use normal from bezier traversal for cap, instead of from vertices
632 storeCapAA(paintInfo, vertices, buffer, false, lastNormal, offset);
633
634 DEBUG_DUMP_ALPHA_BUFFER();
635 }
636
637
getStrokeVerticesFromPerimeterAA(const PaintInfo & paintInfo,const Vector<Vertex> & perimeter,VertexBuffer & vertexBuffer)638 void getStrokeVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter,
639 VertexBuffer& vertexBuffer) {
640 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(6 * perimeter.size() + 8);
641
642 int offset = 2 * perimeter.size() + 3;
643 int currentAAOuterIndex = 0;
644 int currentStrokeIndex = offset;
645 int currentAAInnerIndex = offset * 2;
646
647 const Vertex* last = &(perimeter[perimeter.size() - 1]);
648 const Vertex* current = &(perimeter[0]);
649 vec2 lastNormal(current->position[1] - last->position[1],
650 last->position[0] - current->position[0]);
651 lastNormal.normalize();
652 for (unsigned int i = 0; i < perimeter.size(); i++) {
653 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]);
654 vec2 nextNormal(next->position[1] - current->position[1],
655 current->position[0] - next->position[0]);
656 nextNormal.normalize();
657
658 vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal);
659 vec2 AAOffset = paintInfo.deriveAAOffset(totalOffset);
660
661 vec2 innerOffset = totalOffset;
662 paintInfo.scaleOffsetForStrokeWidth(innerOffset);
663 vec2 outerOffset = innerOffset + AAOffset;
664 innerOffset -= AAOffset;
665
666 AlphaVertex::set(&buffer[currentAAOuterIndex++],
667 current->position[0] + outerOffset.x,
668 current->position[1] + outerOffset.y,
669 0.0f);
670 AlphaVertex::set(&buffer[currentAAOuterIndex++],
671 current->position[0] + innerOffset.x,
672 current->position[1] + innerOffset.y,
673 paintInfo.maxAlpha);
674
675 AlphaVertex::set(&buffer[currentStrokeIndex++],
676 current->position[0] + innerOffset.x,
677 current->position[1] + innerOffset.y,
678 paintInfo.maxAlpha);
679 AlphaVertex::set(&buffer[currentStrokeIndex++],
680 current->position[0] - innerOffset.x,
681 current->position[1] - innerOffset.y,
682 paintInfo.maxAlpha);
683
684 AlphaVertex::set(&buffer[currentAAInnerIndex++],
685 current->position[0] - innerOffset.x,
686 current->position[1] - innerOffset.y,
687 paintInfo.maxAlpha);
688 AlphaVertex::set(&buffer[currentAAInnerIndex++],
689 current->position[0] - outerOffset.x,
690 current->position[1] - outerOffset.y,
691 0.0f);
692
693 last = current;
694 current = next;
695 lastNormal = nextNormal;
696 }
697
698 // wrap each strip around to beginning, creating degenerate tris to bridge strips
699 copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[0]);
700 copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[1]);
701 copyAlphaVertex(&buffer[currentAAOuterIndex++], &buffer[1]);
702
703 copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset]);
704 copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset + 1]);
705 copyAlphaVertex(&buffer[currentStrokeIndex++], &buffer[offset + 1]);
706
707 copyAlphaVertex(&buffer[currentAAInnerIndex++], &buffer[2 * offset]);
708 copyAlphaVertex(&buffer[currentAAInnerIndex++], &buffer[2 * offset + 1]);
709 // don't need to create last degenerate tri
710
711 DEBUG_DUMP_ALPHA_BUFFER();
712 }
713
tessellatePath(const SkPath & path,const SkPaint * paint,const mat4 * transform,VertexBuffer & vertexBuffer)714 void PathTessellator::tessellatePath(const SkPath &path, const SkPaint* paint,
715 const mat4 *transform, VertexBuffer& vertexBuffer) {
716 ATRACE_CALL();
717
718 const PaintInfo paintInfo(paint, transform);
719
720 Vector<Vertex> tempVertices;
721 float threshInvScaleX = paintInfo.inverseScaleX;
722 float threshInvScaleY = paintInfo.inverseScaleY;
723 if (paintInfo.style == SkPaint::kStroke_Style) {
724 // alter the bezier recursion threshold values we calculate in order to compensate for
725 // expansion done after the path vertices are found
726 SkRect bounds = path.getBounds();
727 if (!bounds.isEmpty()) {
728 threshInvScaleX *= bounds.width() / (bounds.width() + paint->getStrokeWidth());
729 threshInvScaleY *= bounds.height() / (bounds.height() + paint->getStrokeWidth());
730 }
731 }
732
733 // force close if we're filling the path, since fill path expects closed perimeter.
734 bool forceClose = paintInfo.style != SkPaint::kStroke_Style;
735 bool wasClosed = approximatePathOutlineVertices(path, forceClose,
736 threshInvScaleX * threshInvScaleX, threshInvScaleY * threshInvScaleY, tempVertices);
737
738 if (!tempVertices.size()) {
739 // path was empty, return without allocating vertex buffer
740 return;
741 }
742
743 #if VERTEX_DEBUG
744 for (unsigned int i = 0; i < tempVertices.size(); i++) {
745 ALOGD("orig path: point at %f %f",
746 tempVertices[i].position[0], tempVertices[i].position[1]);
747 }
748 #endif
749
750 if (paintInfo.style == SkPaint::kStroke_Style) {
751 if (!paintInfo.isAA) {
752 if (wasClosed) {
753 getStrokeVerticesFromPerimeter(paintInfo, tempVertices, vertexBuffer);
754 } else {
755 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer);
756 }
757
758 } else {
759 if (wasClosed) {
760 getStrokeVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer);
761 } else {
762 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer);
763 }
764 }
765 } else {
766 // For kStrokeAndFill style, the path should be adjusted externally.
767 // It will be treated as a fill here.
768 if (!paintInfo.isAA) {
769 getFillVerticesFromPerimeter(tempVertices, vertexBuffer);
770 } else {
771 getFillVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer);
772 }
773 }
774 }
775
expandRectToCoverVertex(SkRect & rect,float x,float y)776 static void expandRectToCoverVertex(SkRect& rect, float x, float y) {
777 rect.fLeft = fminf(rect.fLeft, x);
778 rect.fTop = fminf(rect.fTop, y);
779 rect.fRight = fmaxf(rect.fRight, x);
780 rect.fBottom = fmaxf(rect.fBottom, y);
781 }
expandRectToCoverVertex(SkRect & rect,const Vertex & vertex)782 static void expandRectToCoverVertex(SkRect& rect, const Vertex& vertex) {
783 expandRectToCoverVertex(rect, vertex.position[0], vertex.position[1]);
784 }
785
786 template <class TYPE>
instanceVertices(VertexBuffer & srcBuffer,VertexBuffer & dstBuffer,const float * points,int count,SkRect & bounds)787 static void instanceVertices(VertexBuffer& srcBuffer, VertexBuffer& dstBuffer,
788 const float* points, int count, SkRect& bounds) {
789 bounds.set(points[0], points[1], points[0], points[1]);
790
791 int numPoints = count / 2;
792 int verticesPerPoint = srcBuffer.getVertexCount();
793 dstBuffer.alloc<TYPE>(numPoints * verticesPerPoint + (numPoints - 1) * 2);
794
795 for (int i = 0; i < count; i += 2) {
796 expandRectToCoverVertex(bounds, points[i + 0], points[i + 1]);
797 dstBuffer.copyInto<TYPE>(srcBuffer, points[i + 0], points[i + 1]);
798 }
799 dstBuffer.createDegenerateSeparators<TYPE>(verticesPerPoint);
800 }
801
tessellatePoints(const float * points,int count,SkPaint * paint,const mat4 * transform,SkRect & bounds,VertexBuffer & vertexBuffer)802 void PathTessellator::tessellatePoints(const float* points, int count, SkPaint* paint,
803 const mat4* transform, SkRect& bounds, VertexBuffer& vertexBuffer) {
804 const PaintInfo paintInfo(paint, transform);
805
806 // determine point shape
807 SkPath path;
808 float radius = paintInfo.halfStrokeWidth;
809 if (radius == 0.0f) radius = 0.25f;
810
811 if (paintInfo.cap == SkPaint::kRound_Cap) {
812 path.addCircle(0, 0, radius);
813 } else {
814 path.addRect(-radius, -radius, radius, radius);
815 }
816
817 // calculate outline
818 Vector<Vertex> outlineVertices;
819 approximatePathOutlineVertices(path, true,
820 paintInfo.inverseScaleX * paintInfo.inverseScaleX,
821 paintInfo.inverseScaleY * paintInfo.inverseScaleY, outlineVertices);
822
823 if (!outlineVertices.size()) return;
824
825 // tessellate, then duplicate outline across points
826 int numPoints = count / 2;
827 VertexBuffer tempBuffer;
828 if (!paintInfo.isAA) {
829 getFillVerticesFromPerimeter(outlineVertices, tempBuffer);
830 instanceVertices<Vertex>(tempBuffer, vertexBuffer, points, count, bounds);
831 } else {
832 getFillVerticesFromPerimeterAA(paintInfo, outlineVertices, tempBuffer);
833 instanceVertices<AlphaVertex>(tempBuffer, vertexBuffer, points, count, bounds);
834 }
835
836 expandBoundsForStroke(bounds, paint, true); // force-expand bounds to incorporate stroke
837 }
838
tessellateLines(const float * points,int count,SkPaint * paint,const mat4 * transform,SkRect & bounds,VertexBuffer & vertexBuffer)839 void PathTessellator::tessellateLines(const float* points, int count, SkPaint* paint,
840 const mat4* transform, SkRect& bounds, VertexBuffer& vertexBuffer) {
841 ATRACE_CALL();
842 const PaintInfo paintInfo(paint, transform);
843
844 const int extra = paintInfo.capExtraDivisions();
845 int numLines = count / 4;
846 int lineAllocSize;
847 // pre-allocate space for lines in the buffer, and degenerate tris in between
848 if (paintInfo.isAA) {
849 lineAllocSize = 6 * (2) + 2 + 6 * extra;
850 vertexBuffer.alloc<AlphaVertex>(numLines * lineAllocSize + (numLines - 1) * 2);
851 } else {
852 lineAllocSize = 2 * ((2) + extra);
853 vertexBuffer.alloc<Vertex>(numLines * lineAllocSize + (numLines - 1) * 2);
854 }
855
856 Vector<Vertex> tempVertices;
857 tempVertices.push();
858 tempVertices.push();
859 Vertex* tempVerticesData = tempVertices.editArray();
860 bounds.set(points[0], points[1], points[0], points[1]);
861 for (int i = 0; i < count; i += 4) {
862 Vertex::set(&(tempVerticesData[0]), points[i + 0], points[i + 1]);
863 Vertex::set(&(tempVerticesData[1]), points[i + 2], points[i + 3]);
864
865 if (paintInfo.isAA) {
866 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer);
867 } else {
868 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer);
869 }
870
871 // calculate bounds
872 expandRectToCoverVertex(bounds, tempVerticesData[0]);
873 expandRectToCoverVertex(bounds, tempVerticesData[1]);
874 }
875
876 expandBoundsForStroke(bounds, paint, true); // force-expand bounds to incorporate stroke
877
878 // since multiple objects tessellated into buffer, separate them with degen tris
879 if (paintInfo.isAA) {
880 vertexBuffer.createDegenerateSeparators<AlphaVertex>(lineAllocSize);
881 } else {
882 vertexBuffer.createDegenerateSeparators<Vertex>(lineAllocSize);
883 }
884 }
885
886 ///////////////////////////////////////////////////////////////////////////////
887 // Simple path line approximation
888 ///////////////////////////////////////////////////////////////////////////////
889
pushToVector(Vector<Vertex> & vertices,float x,float y)890 void pushToVector(Vector<Vertex>& vertices, float x, float y) {
891 // TODO: make this not yuck
892 vertices.push();
893 Vertex* newVertex = &(vertices.editArray()[vertices.size() - 1]);
894 Vertex::set(newVertex, x, y);
895 }
896
approximatePathOutlineVertices(const SkPath & path,bool forceClose,float sqrInvScaleX,float sqrInvScaleY,Vector<Vertex> & outputVertices)897 bool PathTessellator::approximatePathOutlineVertices(const SkPath& path, bool forceClose,
898 float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) {
899 ATRACE_CALL();
900
901 // TODO: to support joins other than sharp miter, join vertices should be labelled in the
902 // perimeter, or resolved into more vertices. Reconsider forceClose-ing in that case.
903 SkPath::Iter iter(path, forceClose);
904 SkPoint pts[4];
905 SkPath::Verb v;
906 while (SkPath::kDone_Verb != (v = iter.next(pts))) {
907 switch (v) {
908 case SkPath::kMove_Verb:
909 pushToVector(outputVertices, pts[0].x(), pts[0].y());
910 ALOGV("Move to pos %f %f", pts[0].x(), pts[0].y());
911 break;
912 case SkPath::kClose_Verb:
913 ALOGV("Close at pos %f %f", pts[0].x(), pts[0].y());
914 break;
915 case SkPath::kLine_Verb:
916 ALOGV("kLine_Verb %f %f -> %f %f", pts[0].x(), pts[0].y(), pts[1].x(), pts[1].y());
917 pushToVector(outputVertices, pts[1].x(), pts[1].y());
918 break;
919 case SkPath::kQuad_Verb:
920 ALOGV("kQuad_Verb");
921 recursiveQuadraticBezierVertices(
922 pts[0].x(), pts[0].y(),
923 pts[2].x(), pts[2].y(),
924 pts[1].x(), pts[1].y(),
925 sqrInvScaleX, sqrInvScaleY, outputVertices);
926 break;
927 case SkPath::kCubic_Verb:
928 ALOGV("kCubic_Verb");
929 recursiveCubicBezierVertices(
930 pts[0].x(), pts[0].y(),
931 pts[1].x(), pts[1].y(),
932 pts[3].x(), pts[3].y(),
933 pts[2].x(), pts[2].y(),
934 sqrInvScaleX, sqrInvScaleY, outputVertices);
935 break;
936 default:
937 break;
938 }
939 }
940
941 int size = outputVertices.size();
942 if (size >= 2 && outputVertices[0].position[0] == outputVertices[size - 1].position[0] &&
943 outputVertices[0].position[1] == outputVertices[size - 1].position[1]) {
944 outputVertices.pop();
945 return true;
946 }
947 return false;
948 }
949
950 ///////////////////////////////////////////////////////////////////////////////
951 // Bezier approximation
952 ///////////////////////////////////////////////////////////////////////////////
953
recursiveCubicBezierVertices(float p1x,float p1y,float c1x,float c1y,float p2x,float p2y,float c2x,float c2y,float sqrInvScaleX,float sqrInvScaleY,Vector<Vertex> & outputVertices)954 void PathTessellator::recursiveCubicBezierVertices(
955 float p1x, float p1y, float c1x, float c1y,
956 float p2x, float p2y, float c2x, float c2y,
957 float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) {
958 float dx = p2x - p1x;
959 float dy = p2y - p1y;
960 float d1 = fabs((c1x - p2x) * dy - (c1y - p2y) * dx);
961 float d2 = fabs((c2x - p2x) * dy - (c2y - p2y) * dx);
962 float d = d1 + d2;
963
964 // multiplying by sqrInvScaleY/X equivalent to multiplying in dimensional scale factors
965
966 if (d * d < THRESHOLD * THRESHOLD * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) {
967 // below thresh, draw line by adding endpoint
968 pushToVector(outputVertices, p2x, p2y);
969 } else {
970 float p1c1x = (p1x + c1x) * 0.5f;
971 float p1c1y = (p1y + c1y) * 0.5f;
972 float p2c2x = (p2x + c2x) * 0.5f;
973 float p2c2y = (p2y + c2y) * 0.5f;
974
975 float c1c2x = (c1x + c2x) * 0.5f;
976 float c1c2y = (c1y + c2y) * 0.5f;
977
978 float p1c1c2x = (p1c1x + c1c2x) * 0.5f;
979 float p1c1c2y = (p1c1y + c1c2y) * 0.5f;
980
981 float p2c1c2x = (p2c2x + c1c2x) * 0.5f;
982 float p2c1c2y = (p2c2y + c1c2y) * 0.5f;
983
984 float mx = (p1c1c2x + p2c1c2x) * 0.5f;
985 float my = (p1c1c2y + p2c1c2y) * 0.5f;
986
987 recursiveCubicBezierVertices(
988 p1x, p1y, p1c1x, p1c1y,
989 mx, my, p1c1c2x, p1c1c2y,
990 sqrInvScaleX, sqrInvScaleY, outputVertices);
991 recursiveCubicBezierVertices(
992 mx, my, p2c1c2x, p2c1c2y,
993 p2x, p2y, p2c2x, p2c2y,
994 sqrInvScaleX, sqrInvScaleY, outputVertices);
995 }
996 }
997
recursiveQuadraticBezierVertices(float ax,float ay,float bx,float by,float cx,float cy,float sqrInvScaleX,float sqrInvScaleY,Vector<Vertex> & outputVertices)998 void PathTessellator::recursiveQuadraticBezierVertices(
999 float ax, float ay,
1000 float bx, float by,
1001 float cx, float cy,
1002 float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) {
1003 float dx = bx - ax;
1004 float dy = by - ay;
1005 float d = (cx - bx) * dy - (cy - by) * dx;
1006
1007 if (d * d < THRESHOLD * THRESHOLD * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) {
1008 // below thresh, draw line by adding endpoint
1009 pushToVector(outputVertices, bx, by);
1010 } else {
1011 float acx = (ax + cx) * 0.5f;
1012 float bcx = (bx + cx) * 0.5f;
1013 float acy = (ay + cy) * 0.5f;
1014 float bcy = (by + cy) * 0.5f;
1015
1016 // midpoint
1017 float mx = (acx + bcx) * 0.5f;
1018 float my = (acy + bcy) * 0.5f;
1019
1020 recursiveQuadraticBezierVertices(ax, ay, mx, my, acx, acy,
1021 sqrInvScaleX, sqrInvScaleY, outputVertices);
1022 recursiveQuadraticBezierVertices(mx, my, bx, by, bcx, bcy,
1023 sqrInvScaleX, sqrInvScaleY, outputVertices);
1024 }
1025 }
1026
1027 }; // namespace uirenderer
1028 }; // namespace android
1029