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