PathTessellator.cpp revision 21ef8205a1c741ab4021c2d99c568bed39fc136e
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 "OpenGLRenderer" 18#define LOG_NDEBUG 1 19#define ATRACE_TAG ATRACE_TAG_VIEW 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].x, buffer[i].y, 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].x, buffer[i].y); \ 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#include <SkPoint.h> 41#include <SkGeometry.h> // WARNING: Internal Skia Header 42 43#include <stdlib.h> 44#include <stdint.h> 45#include <sys/types.h> 46 47#include <utils/Log.h> 48#include <utils/Trace.h> 49 50#include "PathTessellator.h" 51#include "Matrix.h" 52#include "Vector.h" 53#include "Vertex.h" 54#include "utils/MathUtils.h" 55 56namespace android { 57namespace uirenderer { 58 59#define OUTLINE_REFINE_THRESHOLD 0.5f 60#define ROUND_CAP_THRESH 0.25f 61#define PI 3.1415926535897932f 62#define MAX_DEPTH 15 63 64/** 65 * Extracts the x and y scale from the transform as positive values, and clamps them 66 */ 67void PathTessellator::extractTessellationScales(const Matrix4& transform, 68 float* scaleX, float* scaleY) { 69 if (CC_LIKELY(transform.isPureTranslate())) { 70 *scaleX = 1.0f; 71 *scaleY = 1.0f; 72 } else { 73 float m00 = transform.data[Matrix4::kScaleX]; 74 float m01 = transform.data[Matrix4::kSkewY]; 75 float m10 = transform.data[Matrix4::kSkewX]; 76 float m11 = transform.data[Matrix4::kScaleY]; 77 *scaleX = MathUtils::clampTessellationScale(sqrt(m00 * m00 + m01 * m01)); 78 *scaleY = MathUtils::clampTessellationScale(sqrt(m10 * m10 + m11 * m11)); 79 } 80} 81 82/** 83 * Produces a pseudo-normal for a vertex, given the normals of the two incoming lines. If the offset 84 * from each vertex in a perimeter is calculated, the resultant lines connecting the offset vertices 85 * will be offset by 1.0 86 * 87 * Note that we can't add and normalize the two vectors, that would result in a rectangle having an 88 * offset of (sqrt(2)/2, sqrt(2)/2) at each corner, instead of (1, 1) 89 * 90 * NOTE: assumes angles between normals 90 degrees or less 91 */ 92inline static Vector2 totalOffsetFromNormals(const Vector2& normalA, const Vector2& normalB) { 93 return (normalA + normalB) / (1 + fabs(normalA.dot(normalB))); 94} 95 96/** 97 * Structure used for storing useful information about the SkPaint and scale used for tessellating 98 */ 99struct PaintInfo { 100public: 101 PaintInfo(const SkPaint* paint, const mat4& transform) : 102 style(paint->getStyle()), cap(paint->getStrokeCap()), isAA(paint->isAntiAlias()), 103 halfStrokeWidth(paint->getStrokeWidth() * 0.5f), maxAlpha(1.0f) { 104 // compute inverse scales 105 if (CC_LIKELY(transform.isPureTranslate())) { 106 inverseScaleX = 1.0f; 107 inverseScaleY = 1.0f; 108 } else { 109 float scaleX, scaleY; 110 PathTessellator::extractTessellationScales(transform, &scaleX, &scaleY); 111 inverseScaleX = 1.0f / scaleX; 112 inverseScaleY = 1.0f / scaleY; 113 } 114 115 if (isAA && halfStrokeWidth != 0 && inverseScaleX == inverseScaleY && 116 2 * halfStrokeWidth < inverseScaleX) { 117 // AA, with non-hairline stroke, width < 1 pixel. Scale alpha and treat as hairline. 118 maxAlpha *= (2 * halfStrokeWidth) / inverseScaleX; 119 halfStrokeWidth = 0.0f; 120 } 121 } 122 123 SkPaint::Style style; 124 SkPaint::Cap cap; 125 bool isAA; 126 float inverseScaleX; 127 float inverseScaleY; 128 float halfStrokeWidth; 129 float maxAlpha; 130 131 inline void scaleOffsetForStrokeWidth(Vector2& offset) const { 132 if (halfStrokeWidth == 0.0f) { 133 // hairline - compensate for scale 134 offset.x *= 0.5f * inverseScaleX; 135 offset.y *= 0.5f * inverseScaleY; 136 } else { 137 offset *= halfStrokeWidth; 138 } 139 } 140 141 /** 142 * NOTE: the input will not always be a normal, especially for sharp edges - it should be the 143 * result of totalOffsetFromNormals (see documentation there) 144 */ 145 inline Vector2 deriveAAOffset(const Vector2& offset) const { 146 return (Vector2){offset.x * 0.5f * inverseScaleX, offset.y * 0.5f * inverseScaleY}; 147 } 148 149 /** 150 * Returns the number of cap divisions beyond the minimum 2 (kButt_Cap/kSquareCap will return 0) 151 * Should only be used when stroking and drawing caps 152 */ 153 inline int capExtraDivisions() const { 154 if (cap == SkPaint::kRound_Cap) { 155 // always use 2 points for hairline 156 if (halfStrokeWidth == 0.0f) return 2; 157 158 float threshold = MathUtils::min(inverseScaleX, inverseScaleY) * ROUND_CAP_THRESH; 159 return MathUtils::divisionsNeededToApproximateArc(halfStrokeWidth, PI, threshold); 160 } 161 return 0; 162 } 163 164 /** 165 * Outset the bounds of point data (for line endpoints or points) to account for stroke 166 * geometry. 167 * 168 * bounds are in pre-scaled space. 169 */ 170 void expandBoundsForStroke(Rect* bounds) const { 171 if (halfStrokeWidth == 0) { 172 // hairline, outset by (0.5f + fudge factor) in post-scaling space 173 bounds->outset(fabs(inverseScaleX) * (0.5f + Vertex::GeometryFudgeFactor()), 174 fabs(inverseScaleY) * (0.5f + Vertex::GeometryFudgeFactor())); 175 } else { 176 // non hairline, outset by half stroke width pre-scaled, and fudge factor post scaled 177 bounds->outset(halfStrokeWidth + fabs(inverseScaleX) * Vertex::GeometryFudgeFactor(), 178 halfStrokeWidth + fabs(inverseScaleY) * Vertex::GeometryFudgeFactor()); 179 } 180 } 181}; 182 183void getFillVerticesFromPerimeter(const Vector<Vertex>& perimeter, VertexBuffer& vertexBuffer) { 184 Vertex* buffer = vertexBuffer.alloc<Vertex>(perimeter.size()); 185 186 int currentIndex = 0; 187 // zig zag between all previous points on the inside of the hull to create a 188 // triangle strip that fills the hull 189 int srcAindex = 0; 190 int srcBindex = perimeter.size() - 1; 191 while (srcAindex <= srcBindex) { 192 buffer[currentIndex++] = perimeter[srcAindex]; 193 if (srcAindex == srcBindex) break; 194 buffer[currentIndex++] = perimeter[srcBindex]; 195 srcAindex++; 196 srcBindex--; 197 } 198} 199 200/* 201 * Fills a vertexBuffer with non-alpha vertices, zig-zagging at each perimeter point to create a 202 * tri-strip as wide as the stroke. 203 * 204 * Uses an additional 2 vertices at the end to wrap around, closing the tri-strip 205 * (for a total of perimeter.size() * 2 + 2 vertices) 206 */ 207void getStrokeVerticesFromPerimeter(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter, 208 VertexBuffer& vertexBuffer) { 209 Vertex* buffer = vertexBuffer.alloc<Vertex>(perimeter.size() * 2 + 2); 210 211 int currentIndex = 0; 212 const Vertex* last = &(perimeter[perimeter.size() - 1]); 213 const Vertex* current = &(perimeter[0]); 214 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 215 lastNormal.normalize(); 216 for (unsigned int i = 0; i < perimeter.size(); i++) { 217 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]); 218 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 219 nextNormal.normalize(); 220 221 Vector2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal); 222 paintInfo.scaleOffsetForStrokeWidth(totalOffset); 223 224 Vertex::set(&buffer[currentIndex++], 225 current->x + totalOffset.x, 226 current->y + totalOffset.y); 227 228 Vertex::set(&buffer[currentIndex++], 229 current->x - totalOffset.x, 230 current->y - totalOffset.y); 231 232 current = next; 233 lastNormal = nextNormal; 234 } 235 236 // wrap around to beginning 237 buffer[currentIndex++] = buffer[0]; 238 buffer[currentIndex++] = buffer[1]; 239 240 DEBUG_DUMP_BUFFER(); 241} 242 243static inline void storeBeginEnd(const PaintInfo& paintInfo, const Vertex& center, 244 const Vector2& normal, Vertex* buffer, int& currentIndex, bool begin) { 245 Vector2 strokeOffset = normal; 246 paintInfo.scaleOffsetForStrokeWidth(strokeOffset); 247 248 Vector2 referencePoint = {center.x, center.y}; 249 if (paintInfo.cap == SkPaint::kSquare_Cap) { 250 Vector2 rotated = {-strokeOffset.y, strokeOffset.x}; 251 referencePoint += rotated * (begin ? -1 : 1); 252 } 253 254 Vertex::set(&buffer[currentIndex++], referencePoint + strokeOffset); 255 Vertex::set(&buffer[currentIndex++], referencePoint - strokeOffset); 256} 257 258/** 259 * Fills a vertexBuffer with non-alpha vertices similar to getStrokeVerticesFromPerimeter, except: 260 * 261 * 1 - Doesn't need to wrap around, since the input vertices are unclosed 262 * 263 * 2 - can zig-zag across 'extra' vertices at either end, to create round caps 264 */ 265void getStrokeVerticesFromUnclosedVertices(const PaintInfo& paintInfo, 266 const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) { 267 const int extra = paintInfo.capExtraDivisions(); 268 const int allocSize = (vertices.size() + extra) * 2; 269 Vertex* buffer = vertexBuffer.alloc<Vertex>(allocSize); 270 271 const int lastIndex = vertices.size() - 1; 272 if (extra > 0) { 273 // tessellate both round caps 274 float beginTheta = atan2( 275 - (vertices[0].x - vertices[1].x), 276 vertices[0].y - vertices[1].y); 277 float endTheta = atan2( 278 - (vertices[lastIndex].x - vertices[lastIndex - 1].x), 279 vertices[lastIndex].y - vertices[lastIndex - 1].y); 280 const float dTheta = PI / (extra + 1); 281 282 int capOffset; 283 for (int i = 0; i < extra; i++) { 284 if (i < extra / 2) { 285 capOffset = extra - 2 * i - 1; 286 } else { 287 capOffset = 2 * i - extra; 288 } 289 290 beginTheta += dTheta; 291 Vector2 beginRadialOffset = {cosf(beginTheta), sinf(beginTheta)}; 292 paintInfo.scaleOffsetForStrokeWidth(beginRadialOffset); 293 Vertex::set(&buffer[capOffset], 294 vertices[0].x + beginRadialOffset.x, 295 vertices[0].y + beginRadialOffset.y); 296 297 endTheta += dTheta; 298 Vector2 endRadialOffset = {cosf(endTheta), sinf(endTheta)}; 299 paintInfo.scaleOffsetForStrokeWidth(endRadialOffset); 300 Vertex::set(&buffer[allocSize - 1 - capOffset], 301 vertices[lastIndex].x + endRadialOffset.x, 302 vertices[lastIndex].y + endRadialOffset.y); 303 } 304 } 305 306 int currentIndex = extra; 307 const Vertex* last = &(vertices[0]); 308 const Vertex* current = &(vertices[1]); 309 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 310 lastNormal.normalize(); 311 312 storeBeginEnd(paintInfo, vertices[0], lastNormal, buffer, currentIndex, true); 313 314 for (unsigned int i = 1; i < vertices.size() - 1; i++) { 315 const Vertex* next = &(vertices[i + 1]); 316 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 317 nextNormal.normalize(); 318 319 Vector2 strokeOffset = totalOffsetFromNormals(lastNormal, nextNormal); 320 paintInfo.scaleOffsetForStrokeWidth(strokeOffset); 321 322 Vector2 center = {current->x, current->y}; 323 Vertex::set(&buffer[currentIndex++], center + strokeOffset); 324 Vertex::set(&buffer[currentIndex++], center - strokeOffset); 325 326 current = next; 327 lastNormal = nextNormal; 328 } 329 330 storeBeginEnd(paintInfo, vertices[lastIndex], lastNormal, buffer, currentIndex, false); 331 332 DEBUG_DUMP_BUFFER(); 333} 334 335/** 336 * Populates a vertexBuffer with AlphaVertices to create an anti-aliased fill shape tessellation 337 * 338 * 1 - create the AA perimeter of unit width, by zig-zagging at each point around the perimeter of 339 * the shape (using 2 * perimeter.size() vertices) 340 * 341 * 2 - wrap around to the beginning to complete the perimeter (2 vertices) 342 * 343 * 3 - zig zag back and forth inside the shape to fill it (using perimeter.size() vertices) 344 */ 345void getFillVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter, 346 VertexBuffer& vertexBuffer, float maxAlpha = 1.0f) { 347 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(perimeter.size() * 3 + 2); 348 349 // generate alpha points - fill Alpha vertex gaps in between each point with 350 // alpha 0 vertex, offset by a scaled normal. 351 int currentIndex = 0; 352 const Vertex* last = &(perimeter[perimeter.size() - 1]); 353 const Vertex* current = &(perimeter[0]); 354 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 355 lastNormal.normalize(); 356 for (unsigned int i = 0; i < perimeter.size(); i++) { 357 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]); 358 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 359 nextNormal.normalize(); 360 361 // AA point offset from original point is that point's normal, such that each side is offset 362 // by .5 pixels 363 Vector2 totalOffset = paintInfo.deriveAAOffset(totalOffsetFromNormals(lastNormal, nextNormal)); 364 365 AlphaVertex::set(&buffer[currentIndex++], 366 current->x + totalOffset.x, 367 current->y + totalOffset.y, 368 0.0f); 369 AlphaVertex::set(&buffer[currentIndex++], 370 current->x - totalOffset.x, 371 current->y - totalOffset.y, 372 maxAlpha); 373 374 current = next; 375 lastNormal = nextNormal; 376 } 377 378 // wrap around to beginning 379 buffer[currentIndex++] = buffer[0]; 380 buffer[currentIndex++] = buffer[1]; 381 382 // zig zag between all previous points on the inside of the hull to create a 383 // triangle strip that fills the hull, repeating the first inner point to 384 // create degenerate tris to start inside path 385 int srcAindex = 0; 386 int srcBindex = perimeter.size() - 1; 387 while (srcAindex <= srcBindex) { 388 buffer[currentIndex++] = buffer[srcAindex * 2 + 1]; 389 if (srcAindex == srcBindex) break; 390 buffer[currentIndex++] = buffer[srcBindex * 2 + 1]; 391 srcAindex++; 392 srcBindex--; 393 } 394 395 DEBUG_DUMP_BUFFER(); 396} 397 398/** 399 * Stores geometry for a single, AA-perimeter (potentially rounded) cap 400 * 401 * For explanation of constants and general methodoloyg, see comments for 402 * getStrokeVerticesFromUnclosedVerticesAA() below. 403 */ 404inline static void storeCapAA(const PaintInfo& paintInfo, const Vector<Vertex>& vertices, 405 AlphaVertex* buffer, bool isFirst, Vector2 normal, int offset) { 406 const int extra = paintInfo.capExtraDivisions(); 407 const int extraOffset = (extra + 1) / 2; 408 const int capIndex = isFirst 409 ? 2 * offset + 6 + 2 * (extra + extraOffset) 410 : offset + 2 + 2 * extraOffset; 411 if (isFirst) normal *= -1; 412 413 // TODO: this normal should be scaled by radialScale if extra != 0, see totalOffsetFromNormals() 414 Vector2 AAOffset = paintInfo.deriveAAOffset(normal); 415 416 Vector2 strokeOffset = normal; 417 paintInfo.scaleOffsetForStrokeWidth(strokeOffset); 418 Vector2 outerOffset = strokeOffset + AAOffset; 419 Vector2 innerOffset = strokeOffset - AAOffset; 420 421 Vector2 capAAOffset = {0, 0}; 422 if (paintInfo.cap != SkPaint::kRound_Cap) { 423 // if the cap is square or butt, the inside primary cap vertices will be inset in two 424 // directions - both normal to the stroke, and parallel to it. 425 capAAOffset = (Vector2){-AAOffset.y, AAOffset.x}; 426 } 427 428 // determine referencePoint, the center point for the 4 primary cap vertices 429 const Vertex* point = isFirst ? vertices.begin() : (vertices.end() - 1); 430 Vector2 referencePoint = {point->x, point->y}; 431 if (paintInfo.cap == SkPaint::kSquare_Cap) { 432 // To account for square cap, move the primary cap vertices (that create the AA edge) by the 433 // stroke offset vector (rotated to be parallel to the stroke) 434 Vector2 rotated = {-strokeOffset.y, strokeOffset.x}; 435 referencePoint += rotated; 436 } 437 438 AlphaVertex::set(&buffer[capIndex + 0], 439 referencePoint.x + outerOffset.x + capAAOffset.x, 440 referencePoint.y + outerOffset.y + capAAOffset.y, 441 0.0f); 442 AlphaVertex::set(&buffer[capIndex + 1], 443 referencePoint.x + innerOffset.x - capAAOffset.x, 444 referencePoint.y + innerOffset.y - capAAOffset.y, 445 paintInfo.maxAlpha); 446 447 bool isRound = paintInfo.cap == SkPaint::kRound_Cap; 448 449 const int postCapIndex = (isRound && isFirst) ? (2 * extraOffset - 2) : capIndex + (2 * extra); 450 AlphaVertex::set(&buffer[postCapIndex + 2], 451 referencePoint.x - outerOffset.x + capAAOffset.x, 452 referencePoint.y - outerOffset.y + capAAOffset.y, 453 0.0f); 454 AlphaVertex::set(&buffer[postCapIndex + 3], 455 referencePoint.x - innerOffset.x - capAAOffset.x, 456 referencePoint.y - innerOffset.y - capAAOffset.y, 457 paintInfo.maxAlpha); 458 459 if (isRound) { 460 const float dTheta = PI / (extra + 1); 461 const float radialScale = 2.0f / (1 + cos(dTheta)); 462 float theta = atan2(normal.y, normal.x); 463 int capPerimIndex = capIndex + 2; 464 465 for (int i = 0; i < extra; i++) { 466 theta += dTheta; 467 468 Vector2 radialOffset = {cosf(theta), sinf(theta)}; 469 470 // scale to compensate for pinching at sharp angles, see totalOffsetFromNormals() 471 radialOffset *= radialScale; 472 473 AAOffset = paintInfo.deriveAAOffset(radialOffset); 474 paintInfo.scaleOffsetForStrokeWidth(radialOffset); 475 AlphaVertex::set(&buffer[capPerimIndex++], 476 referencePoint.x + radialOffset.x + AAOffset.x, 477 referencePoint.y + radialOffset.y + AAOffset.y, 478 0.0f); 479 AlphaVertex::set(&buffer[capPerimIndex++], 480 referencePoint.x + radialOffset.x - AAOffset.x, 481 referencePoint.y + radialOffset.y - AAOffset.y, 482 paintInfo.maxAlpha); 483 484 if (isFirst && i == extra - extraOffset) { 485 //copy most recent two points to first two points 486 buffer[0] = buffer[capPerimIndex - 2]; 487 buffer[1] = buffer[capPerimIndex - 1]; 488 489 capPerimIndex = 2; // start writing the rest of the round cap at index 2 490 } 491 } 492 493 if (isFirst) { 494 const int startCapFillIndex = capIndex + 2 * (extra - extraOffset) + 4; 495 int capFillIndex = startCapFillIndex; 496 for (int i = 0; i < extra + 2; i += 2) { 497 buffer[capFillIndex++] = buffer[1 + i]; 498 // TODO: to support odd numbers of divisions, break here on the last iteration 499 buffer[capFillIndex++] = buffer[startCapFillIndex - 3 - i]; 500 } 501 } else { 502 int capFillIndex = 6 * vertices.size() + 2 + 6 * extra - (extra + 2); 503 for (int i = 0; i < extra + 2; i += 2) { 504 buffer[capFillIndex++] = buffer[capIndex + 1 + i]; 505 // TODO: to support odd numbers of divisions, break here on the last iteration 506 buffer[capFillIndex++] = buffer[capIndex + 3 + 2 * extra - i]; 507 } 508 } 509 return; 510 } 511 if (isFirst) { 512 buffer[0] = buffer[postCapIndex + 2]; 513 buffer[1] = buffer[postCapIndex + 3]; 514 buffer[postCapIndex + 4] = buffer[1]; // degenerate tris (the only two!) 515 buffer[postCapIndex + 5] = buffer[postCapIndex + 1]; 516 } else { 517 buffer[6 * vertices.size()] = buffer[postCapIndex + 1]; 518 buffer[6 * vertices.size() + 1] = buffer[postCapIndex + 3]; 519 } 520} 521 522/* 523the geometry for an aa, capped stroke consists of the following: 524 525 # vertices | function 526---------------------------------------------------------------------- 527a) 2 | Start AA perimeter 528b) 2, 2 * roundDivOff | First half of begin cap's perimeter 529 | 530 2 * middlePts | 'Outer' or 'Top' AA perimeter half (between caps) 531 | 532a) 4 | End cap's 533b) 2, 2 * roundDivs, 2 | AA perimeter 534 | 535 2 * middlePts | 'Inner' or 'bottom' AA perimeter half 536 | 537a) 6 | Begin cap's perimeter 538b) 2, 2*(rD - rDO + 1), | Last half of begin cap's perimeter 539 roundDivs, 2 | 540 | 541 2 * middlePts | Stroke's full opacity center strip 542 | 543a) 2 | end stroke 544b) 2, roundDivs | (and end cap fill, for round) 545 546Notes: 547* rows starting with 'a)' denote the Butt or Square cap vertex use, 'b)' denote Round 548 549* 'middlePts' is (number of points in the unclosed input vertex list, minus 2) times two 550 551* 'roundDivs' or 'rD' is the number of extra vertices (beyond the minimum of 2) that define the 552 round cap's shape, and is at least two. This will increase with cap size to sufficiently 553 define the cap's level of tessellation. 554 555* 'roundDivOffset' or 'rDO' is the point about halfway along the start cap's round perimeter, where 556 the stream of vertices for the AA perimeter starts. By starting and ending the perimeter at 557 this offset, the fill of the stroke is drawn from this point with minimal extra vertices. 558 559This means the outer perimeter starts at: 560 outerIndex = (2) OR (2 + 2 * roundDivOff) 561the inner perimeter (since it is filled in reverse) starts at: 562 innerIndex = outerIndex + (4 * middlePts) + ((4) OR (4 + 2 * roundDivs)) - 1 563the stroke starts at: 564 strokeIndex = innerIndex + 1 + ((6) OR (6 + 3 * roundDivs - 2 * roundDivOffset)) 565 566The total needed allocated space is either: 567 2 + 4 + 6 + 2 + 3 * (2 * middlePts) = 14 + 6 * middlePts = 2 + 6 * pts 568or, for rounded caps: 569 (2 + 2 * rDO) + (4 + 2 * rD) + (2 * (rD - rDO + 1) 570 + roundDivs + 4) + (2 + roundDivs) + 3 * (2 * middlePts) 571 = 14 + 6 * middlePts + 6 * roundDivs 572 = 2 + 6 * pts + 6 * roundDivs 573 */ 574void getStrokeVerticesFromUnclosedVerticesAA(const PaintInfo& paintInfo, 575 const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) { 576 577 const int extra = paintInfo.capExtraDivisions(); 578 const int allocSize = 6 * vertices.size() + 2 + 6 * extra; 579 580 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(allocSize); 581 582 const int extraOffset = (extra + 1) / 2; 583 int offset = 2 * (vertices.size() - 2); 584 // there is no outer/inner here, using them for consistency with below approach 585 int currentAAOuterIndex = 2 + 2 * extraOffset; 586 int currentAAInnerIndex = currentAAOuterIndex + (2 * offset) + 3 + (2 * extra); 587 int currentStrokeIndex = currentAAInnerIndex + 7 + (3 * extra - 2 * extraOffset); 588 589 const Vertex* last = &(vertices[0]); 590 const Vertex* current = &(vertices[1]); 591 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 592 lastNormal.normalize(); 593 594 // TODO: use normal from bezier traversal for cap, instead of from vertices 595 storeCapAA(paintInfo, vertices, buffer, true, lastNormal, offset); 596 597 for (unsigned int i = 1; i < vertices.size() - 1; i++) { 598 const Vertex* next = &(vertices[i + 1]); 599 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 600 nextNormal.normalize(); 601 602 Vector2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal); 603 Vector2 AAOffset = paintInfo.deriveAAOffset(totalOffset); 604 605 Vector2 innerOffset = totalOffset; 606 paintInfo.scaleOffsetForStrokeWidth(innerOffset); 607 Vector2 outerOffset = innerOffset + AAOffset; 608 innerOffset -= AAOffset; 609 610 AlphaVertex::set(&buffer[currentAAOuterIndex++], 611 current->x + outerOffset.x, 612 current->y + outerOffset.y, 613 0.0f); 614 AlphaVertex::set(&buffer[currentAAOuterIndex++], 615 current->x + innerOffset.x, 616 current->y + innerOffset.y, 617 paintInfo.maxAlpha); 618 619 AlphaVertex::set(&buffer[currentStrokeIndex++], 620 current->x + innerOffset.x, 621 current->y + innerOffset.y, 622 paintInfo.maxAlpha); 623 AlphaVertex::set(&buffer[currentStrokeIndex++], 624 current->x - innerOffset.x, 625 current->y - innerOffset.y, 626 paintInfo.maxAlpha); 627 628 AlphaVertex::set(&buffer[currentAAInnerIndex--], 629 current->x - innerOffset.x, 630 current->y - innerOffset.y, 631 paintInfo.maxAlpha); 632 AlphaVertex::set(&buffer[currentAAInnerIndex--], 633 current->x - outerOffset.x, 634 current->y - outerOffset.y, 635 0.0f); 636 637 current = next; 638 lastNormal = nextNormal; 639 } 640 641 // TODO: use normal from bezier traversal for cap, instead of from vertices 642 storeCapAA(paintInfo, vertices, buffer, false, lastNormal, offset); 643 644 DEBUG_DUMP_ALPHA_BUFFER(); 645} 646 647 648void getStrokeVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter, 649 VertexBuffer& vertexBuffer) { 650 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(6 * perimeter.size() + 8); 651 652 int offset = 2 * perimeter.size() + 3; 653 int currentAAOuterIndex = 0; 654 int currentStrokeIndex = offset; 655 int currentAAInnerIndex = offset * 2; 656 657 const Vertex* last = &(perimeter[perimeter.size() - 1]); 658 const Vertex* current = &(perimeter[0]); 659 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 660 lastNormal.normalize(); 661 for (unsigned int i = 0; i < perimeter.size(); i++) { 662 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]); 663 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 664 nextNormal.normalize(); 665 666 Vector2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal); 667 Vector2 AAOffset = paintInfo.deriveAAOffset(totalOffset); 668 669 Vector2 innerOffset = totalOffset; 670 paintInfo.scaleOffsetForStrokeWidth(innerOffset); 671 Vector2 outerOffset = innerOffset + AAOffset; 672 innerOffset -= AAOffset; 673 674 AlphaVertex::set(&buffer[currentAAOuterIndex++], 675 current->x + outerOffset.x, 676 current->y + outerOffset.y, 677 0.0f); 678 AlphaVertex::set(&buffer[currentAAOuterIndex++], 679 current->x + innerOffset.x, 680 current->y + innerOffset.y, 681 paintInfo.maxAlpha); 682 683 AlphaVertex::set(&buffer[currentStrokeIndex++], 684 current->x + innerOffset.x, 685 current->y + innerOffset.y, 686 paintInfo.maxAlpha); 687 AlphaVertex::set(&buffer[currentStrokeIndex++], 688 current->x - innerOffset.x, 689 current->y - innerOffset.y, 690 paintInfo.maxAlpha); 691 692 AlphaVertex::set(&buffer[currentAAInnerIndex++], 693 current->x - innerOffset.x, 694 current->y - innerOffset.y, 695 paintInfo.maxAlpha); 696 AlphaVertex::set(&buffer[currentAAInnerIndex++], 697 current->x - outerOffset.x, 698 current->y - outerOffset.y, 699 0.0f); 700 701 current = next; 702 lastNormal = nextNormal; 703 } 704 705 // wrap each strip around to beginning, creating degenerate tris to bridge strips 706 buffer[currentAAOuterIndex++] = buffer[0]; 707 buffer[currentAAOuterIndex++] = buffer[1]; 708 buffer[currentAAOuterIndex++] = buffer[1]; 709 710 buffer[currentStrokeIndex++] = buffer[offset]; 711 buffer[currentStrokeIndex++] = buffer[offset + 1]; 712 buffer[currentStrokeIndex++] = buffer[offset + 1]; 713 714 buffer[currentAAInnerIndex++] = buffer[2 * offset]; 715 buffer[currentAAInnerIndex++] = buffer[2 * offset + 1]; 716 // don't need to create last degenerate tri 717 718 DEBUG_DUMP_ALPHA_BUFFER(); 719} 720 721void PathTessellator::tessellatePath(const SkPath &path, const SkPaint* paint, 722 const mat4& transform, VertexBuffer& vertexBuffer) { 723 ATRACE_CALL(); 724 725 const PaintInfo paintInfo(paint, transform); 726 727 Vector<Vertex> tempVertices; 728 float threshInvScaleX = paintInfo.inverseScaleX; 729 float threshInvScaleY = paintInfo.inverseScaleY; 730 if (paintInfo.style == SkPaint::kStroke_Style) { 731 // alter the bezier recursion threshold values we calculate in order to compensate for 732 // expansion done after the path vertices are found 733 SkRect bounds = path.getBounds(); 734 if (!bounds.isEmpty()) { 735 threshInvScaleX *= bounds.width() / (bounds.width() + paint->getStrokeWidth()); 736 threshInvScaleY *= bounds.height() / (bounds.height() + paint->getStrokeWidth()); 737 } 738 } 739 740 // force close if we're filling the path, since fill path expects closed perimeter. 741 bool forceClose = paintInfo.style != SkPaint::kStroke_Style; 742 PathApproximationInfo approximationInfo(threshInvScaleX, threshInvScaleY, 743 OUTLINE_REFINE_THRESHOLD); 744 bool wasClosed = approximatePathOutlineVertices(path, forceClose, 745 approximationInfo, tempVertices); 746 747 if (!tempVertices.size()) { 748 // path was empty, return without allocating vertex buffer 749 return; 750 } 751 752#if VERTEX_DEBUG 753 for (unsigned int i = 0; i < tempVertices.size(); i++) { 754 ALOGD("orig path: point at %f %f", 755 tempVertices[i].x, tempVertices[i].y); 756 } 757#endif 758 759 if (paintInfo.style == SkPaint::kStroke_Style) { 760 if (!paintInfo.isAA) { 761 if (wasClosed) { 762 getStrokeVerticesFromPerimeter(paintInfo, tempVertices, vertexBuffer); 763 } else { 764 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer); 765 } 766 767 } else { 768 if (wasClosed) { 769 getStrokeVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer); 770 } else { 771 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer); 772 } 773 } 774 } else { 775 // For kStrokeAndFill style, the path should be adjusted externally. 776 // It will be treated as a fill here. 777 if (!paintInfo.isAA) { 778 getFillVerticesFromPerimeter(tempVertices, vertexBuffer); 779 } else { 780 getFillVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer); 781 } 782 } 783 784 Rect bounds(path.getBounds()); 785 paintInfo.expandBoundsForStroke(&bounds); 786 vertexBuffer.setBounds(bounds); 787 vertexBuffer.setMeshFeatureFlags(paintInfo.isAA ? VertexBuffer::kAlpha : VertexBuffer::kNone); 788} 789 790template <class TYPE> 791static void instanceVertices(VertexBuffer& srcBuffer, VertexBuffer& dstBuffer, 792 const float* points, int count, Rect& bounds) { 793 bounds.set(points[0], points[1], points[0], points[1]); 794 795 int numPoints = count / 2; 796 int verticesPerPoint = srcBuffer.getVertexCount(); 797 dstBuffer.alloc<TYPE>(numPoints * verticesPerPoint + (numPoints - 1) * 2); 798 799 for (int i = 0; i < count; i += 2) { 800 bounds.expandToCoverVertex(points[i + 0], points[i + 1]); 801 dstBuffer.copyInto<TYPE>(srcBuffer, points[i + 0], points[i + 1]); 802 } 803 dstBuffer.createDegenerateSeparators<TYPE>(verticesPerPoint); 804} 805 806void PathTessellator::tessellatePoints(const float* points, int count, const SkPaint* paint, 807 const mat4& transform, VertexBuffer& vertexBuffer) { 808 const PaintInfo paintInfo(paint, transform); 809 810 // determine point shape 811 SkPath path; 812 float radius = paintInfo.halfStrokeWidth; 813 if (radius == 0.0f) radius = 0.5f; 814 815 if (paintInfo.cap == SkPaint::kRound_Cap) { 816 path.addCircle(0, 0, radius); 817 } else { 818 path.addRect(-radius, -radius, radius, radius); 819 } 820 821 // calculate outline 822 Vector<Vertex> outlineVertices; 823 PathApproximationInfo approximationInfo(paintInfo.inverseScaleX, paintInfo.inverseScaleY, 824 OUTLINE_REFINE_THRESHOLD); 825 approximatePathOutlineVertices(path, true, approximationInfo, outlineVertices); 826 827 if (!outlineVertices.size()) return; 828 829 Rect bounds; 830 // tessellate, then duplicate outline across points 831 VertexBuffer tempBuffer; 832 if (!paintInfo.isAA) { 833 getFillVerticesFromPerimeter(outlineVertices, tempBuffer); 834 instanceVertices<Vertex>(tempBuffer, vertexBuffer, points, count, bounds); 835 } else { 836 // note: pass maxAlpha directly, since we want fill to be alpha modulated 837 getFillVerticesFromPerimeterAA(paintInfo, outlineVertices, tempBuffer, paintInfo.maxAlpha); 838 instanceVertices<AlphaVertex>(tempBuffer, vertexBuffer, points, count, bounds); 839 } 840 841 // expand bounds from vertex coords to pixel data 842 paintInfo.expandBoundsForStroke(&bounds); 843 vertexBuffer.setBounds(bounds); 844 vertexBuffer.setMeshFeatureFlags(paintInfo.isAA ? VertexBuffer::kAlpha : VertexBuffer::kNone); 845} 846 847void PathTessellator::tessellateLines(const float* points, int count, const SkPaint* paint, 848 const mat4& transform, VertexBuffer& vertexBuffer) { 849 ATRACE_CALL(); 850 const PaintInfo paintInfo(paint, transform); 851 852 const int extra = paintInfo.capExtraDivisions(); 853 int numLines = count / 4; 854 int lineAllocSize; 855 // pre-allocate space for lines in the buffer, and degenerate tris in between 856 if (paintInfo.isAA) { 857 lineAllocSize = 6 * (2) + 2 + 6 * extra; 858 vertexBuffer.alloc<AlphaVertex>(numLines * lineAllocSize + (numLines - 1) * 2); 859 } else { 860 lineAllocSize = 2 * ((2) + extra); 861 vertexBuffer.alloc<Vertex>(numLines * lineAllocSize + (numLines - 1) * 2); 862 } 863 864 Vector<Vertex> tempVertices; 865 tempVertices.push(); 866 tempVertices.push(); 867 Vertex* tempVerticesData = tempVertices.editArray(); 868 Rect bounds; 869 bounds.set(points[0], points[1], points[0], points[1]); 870 for (int i = 0; i < count; i += 4) { 871 Vertex::set(&(tempVerticesData[0]), points[i + 0], points[i + 1]); 872 Vertex::set(&(tempVerticesData[1]), points[i + 2], points[i + 3]); 873 874 if (paintInfo.isAA) { 875 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer); 876 } else { 877 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer); 878 } 879 880 // calculate bounds 881 bounds.expandToCoverVertex(tempVerticesData[0].x, tempVerticesData[0].y); 882 bounds.expandToCoverVertex(tempVerticesData[1].x, tempVerticesData[1].y); 883 } 884 885 // since multiple objects tessellated into buffer, separate them with degen tris 886 if (paintInfo.isAA) { 887 vertexBuffer.createDegenerateSeparators<AlphaVertex>(lineAllocSize); 888 } else { 889 vertexBuffer.createDegenerateSeparators<Vertex>(lineAllocSize); 890 } 891 892 // expand bounds from vertex coords to pixel data 893 paintInfo.expandBoundsForStroke(&bounds); 894 vertexBuffer.setBounds(bounds); 895 vertexBuffer.setMeshFeatureFlags(paintInfo.isAA ? VertexBuffer::kAlpha : VertexBuffer::kNone); 896} 897 898/////////////////////////////////////////////////////////////////////////////// 899// Simple path line approximation 900/////////////////////////////////////////////////////////////////////////////// 901 902bool PathTessellator::approximatePathOutlineVertices(const SkPath& path, float threshold, 903 Vector<Vertex>& outputVertices) { 904 PathApproximationInfo approximationInfo(1.0f, 1.0f, threshold); 905 return approximatePathOutlineVertices(path, true, approximationInfo, outputVertices); 906} 907 908void pushToVector(Vector<Vertex>& vertices, float x, float y) { 909 // TODO: make this not yuck 910 vertices.push(); 911 Vertex* newVertex = &(vertices.editArray()[vertices.size() - 1]); 912 Vertex::set(newVertex, x, y); 913} 914 915class ClockwiseEnforcer { 916public: 917 void addPoint(const SkPoint& point) { 918 double x = point.x(); 919 double y = point.y(); 920 921 if (initialized) { 922 sum += (x + lastX) * (y - lastY); 923 } else { 924 initialized = true; 925 } 926 927 lastX = x; 928 lastY = y; 929 } 930 void reverseVectorIfNotClockwise(Vector<Vertex>& vertices) { 931 if (sum < 0) { 932 // negative sum implies CounterClockwise 933 const int size = vertices.size(); 934 for (int i = 0; i < size / 2; i++) { 935 Vertex tmp = vertices[i]; 936 int k = size - 1 - i; 937 vertices.replaceAt(vertices[k], i); 938 vertices.replaceAt(tmp, k); 939 } 940 } 941 } 942private: 943 bool initialized = false; 944 double lastX = 0; 945 double lastY = 0; 946 double sum = 0; 947}; 948 949bool PathTessellator::approximatePathOutlineVertices(const SkPath& path, bool forceClose, 950 const PathApproximationInfo& approximationInfo, Vector<Vertex>& outputVertices) { 951 ATRACE_CALL(); 952 953 // TODO: to support joins other than sharp miter, join vertices should be labelled in the 954 // perimeter, or resolved into more vertices. Reconsider forceClose-ing in that case. 955 SkPath::Iter iter(path, forceClose); 956 SkPoint pts[4]; 957 SkPath::Verb v; 958 ClockwiseEnforcer clockwiseEnforcer; 959 while (SkPath::kDone_Verb != (v = iter.next(pts))) { 960 switch (v) { 961 case SkPath::kMove_Verb: 962 pushToVector(outputVertices, pts[0].x(), pts[0].y()); 963 ALOGV("Move to pos %f %f", pts[0].x(), pts[0].y()); 964 clockwiseEnforcer.addPoint(pts[0]); 965 break; 966 case SkPath::kClose_Verb: 967 ALOGV("Close at pos %f %f", pts[0].x(), pts[0].y()); 968 clockwiseEnforcer.addPoint(pts[0]); 969 break; 970 case SkPath::kLine_Verb: 971 ALOGV("kLine_Verb %f %f -> %f %f", pts[0].x(), pts[0].y(), pts[1].x(), pts[1].y()); 972 pushToVector(outputVertices, pts[1].x(), pts[1].y()); 973 clockwiseEnforcer.addPoint(pts[1]); 974 break; 975 case SkPath::kQuad_Verb: 976 ALOGV("kQuad_Verb"); 977 recursiveQuadraticBezierVertices( 978 pts[0].x(), pts[0].y(), 979 pts[2].x(), pts[2].y(), 980 pts[1].x(), pts[1].y(), 981 approximationInfo, outputVertices); 982 clockwiseEnforcer.addPoint(pts[1]); 983 clockwiseEnforcer.addPoint(pts[2]); 984 break; 985 case SkPath::kCubic_Verb: 986 ALOGV("kCubic_Verb"); 987 recursiveCubicBezierVertices( 988 pts[0].x(), pts[0].y(), 989 pts[1].x(), pts[1].y(), 990 pts[3].x(), pts[3].y(), 991 pts[2].x(), pts[2].y(), 992 approximationInfo, outputVertices); 993 clockwiseEnforcer.addPoint(pts[1]); 994 clockwiseEnforcer.addPoint(pts[2]); 995 clockwiseEnforcer.addPoint(pts[3]); 996 break; 997 case SkPath::kConic_Verb: { 998 ALOGV("kConic_Verb"); 999 SkAutoConicToQuads converter; 1000 const SkPoint* quads = converter.computeQuads(pts, iter.conicWeight(), 1001 approximationInfo.thresholdForConicQuads); 1002 for (int i = 0; i < converter.countQuads(); ++i) { 1003 const int offset = 2 * i; 1004 recursiveQuadraticBezierVertices( 1005 quads[offset].x(), quads[offset].y(), 1006 quads[offset+2].x(), quads[offset+2].y(), 1007 quads[offset+1].x(), quads[offset+1].y(), 1008 approximationInfo, outputVertices); 1009 } 1010 clockwiseEnforcer.addPoint(pts[1]); 1011 clockwiseEnforcer.addPoint(pts[2]); 1012 break; 1013 } 1014 default: 1015 break; 1016 } 1017 } 1018 1019 bool wasClosed = false; 1020 int size = outputVertices.size(); 1021 if (size >= 2 && outputVertices[0].x == outputVertices[size - 1].x && 1022 outputVertices[0].y == outputVertices[size - 1].y) { 1023 outputVertices.pop(); 1024 wasClosed = true; 1025 } 1026 1027 // ensure output vector is clockwise 1028 clockwiseEnforcer.reverseVectorIfNotClockwise(outputVertices); 1029 return wasClosed; 1030} 1031 1032/////////////////////////////////////////////////////////////////////////////// 1033// Bezier approximation 1034// 1035// All the inputs and outputs here are in path coordinates. 1036// We convert the error threshold from screen coordinates into path coordinates. 1037/////////////////////////////////////////////////////////////////////////////// 1038 1039// Get a threshold in path coordinates, by scaling the thresholdSquared from screen coordinates. 1040// TODO: Document the math behind this algorithm. 1041static inline float getThreshold(const PathApproximationInfo& info, float dx, float dy) { 1042 // multiplying by sqrInvScaleY/X equivalent to multiplying in dimensional scale factors 1043 float scale = (dx * dx * info.sqrInvScaleY + dy * dy * info.sqrInvScaleX); 1044 return info.thresholdSquared * scale; 1045} 1046 1047void PathTessellator::recursiveCubicBezierVertices( 1048 float p1x, float p1y, float c1x, float c1y, 1049 float p2x, float p2y, float c2x, float c2y, 1050 const PathApproximationInfo& approximationInfo, 1051 Vector<Vertex>& outputVertices, int depth) { 1052 float dx = p2x - p1x; 1053 float dy = p2y - p1y; 1054 float d1 = fabs((c1x - p2x) * dy - (c1y - p2y) * dx); 1055 float d2 = fabs((c2x - p2x) * dy - (c2y - p2y) * dx); 1056 float d = d1 + d2; 1057 1058 if (depth >= MAX_DEPTH 1059 || d * d <= getThreshold(approximationInfo, dx, dy)) { 1060 // below thresh, draw line by adding endpoint 1061 pushToVector(outputVertices, p2x, p2y); 1062 } else { 1063 float p1c1x = (p1x + c1x) * 0.5f; 1064 float p1c1y = (p1y + c1y) * 0.5f; 1065 float p2c2x = (p2x + c2x) * 0.5f; 1066 float p2c2y = (p2y + c2y) * 0.5f; 1067 1068 float c1c2x = (c1x + c2x) * 0.5f; 1069 float c1c2y = (c1y + c2y) * 0.5f; 1070 1071 float p1c1c2x = (p1c1x + c1c2x) * 0.5f; 1072 float p1c1c2y = (p1c1y + c1c2y) * 0.5f; 1073 1074 float p2c1c2x = (p2c2x + c1c2x) * 0.5f; 1075 float p2c1c2y = (p2c2y + c1c2y) * 0.5f; 1076 1077 float mx = (p1c1c2x + p2c1c2x) * 0.5f; 1078 float my = (p1c1c2y + p2c1c2y) * 0.5f; 1079 1080 recursiveCubicBezierVertices( 1081 p1x, p1y, p1c1x, p1c1y, 1082 mx, my, p1c1c2x, p1c1c2y, 1083 approximationInfo, outputVertices, depth + 1); 1084 recursiveCubicBezierVertices( 1085 mx, my, p2c1c2x, p2c1c2y, 1086 p2x, p2y, p2c2x, p2c2y, 1087 approximationInfo, outputVertices, depth + 1); 1088 } 1089} 1090 1091void PathTessellator::recursiveQuadraticBezierVertices( 1092 float ax, float ay, 1093 float bx, float by, 1094 float cx, float cy, 1095 const PathApproximationInfo& approximationInfo, 1096 Vector<Vertex>& outputVertices, int depth) { 1097 float dx = bx - ax; 1098 float dy = by - ay; 1099 // d is the cross product of vector (B-A) and (C-B). 1100 float d = (cx - bx) * dy - (cy - by) * dx; 1101 1102 if (depth >= MAX_DEPTH 1103 || d * d <= getThreshold(approximationInfo, dx, dy)) { 1104 // below thresh, draw line by adding endpoint 1105 pushToVector(outputVertices, bx, by); 1106 } else { 1107 float acx = (ax + cx) * 0.5f; 1108 float bcx = (bx + cx) * 0.5f; 1109 float acy = (ay + cy) * 0.5f; 1110 float bcy = (by + cy) * 0.5f; 1111 1112 // midpoint 1113 float mx = (acx + bcx) * 0.5f; 1114 float my = (acy + bcy) * 0.5f; 1115 1116 recursiveQuadraticBezierVertices(ax, ay, mx, my, acx, acy, 1117 approximationInfo, outputVertices, depth + 1); 1118 recursiveQuadraticBezierVertices(mx, my, bx, by, bcx, bcy, 1119 approximationInfo, outputVertices, depth + 1); 1120 } 1121} 1122 1123}; // namespace uirenderer 1124}; // namespace android 1125