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