PathTessellator.cpp revision 117bdbcfa3e8306dad21e7e01fa71b00cdfa7265
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 41#include <stdlib.h> 42#include <stdint.h> 43#include <sys/types.h> 44 45#include <utils/Log.h> 46#include <utils/Trace.h> 47 48#include "PathTessellator.h" 49#include "Matrix.h" 50#include "Vector.h" 51#include "Vertex.h" 52#include "utils/MathUtils.h" 53 54namespace android { 55namespace uirenderer { 56 57#define OUTLINE_REFINE_THRESHOLD_SQUARED (0.5f * 0.5f) 58#define ROUND_CAP_THRESH 0.25f 59#define PI 3.1415926535897932f 60#define MAX_DEPTH 15 61 62/** 63 * Extracts the x and y scale from the transform as positive values, and clamps them 64 */ 65void PathTessellator::extractTessellationScales(const Matrix4& transform, 66 float* scaleX, float* scaleY) { 67 if (CC_LIKELY(transform.isPureTranslate())) { 68 *scaleX = 1.0f; 69 *scaleY = 1.0f; 70 } else { 71 float m00 = transform.data[Matrix4::kScaleX]; 72 float m01 = transform.data[Matrix4::kSkewY]; 73 float m10 = transform.data[Matrix4::kSkewX]; 74 float m11 = transform.data[Matrix4::kScaleY]; 75 *scaleX = MathUtils::clampTessellationScale(sqrt(m00 * m00 + m01 * m01)); 76 *scaleY = MathUtils::clampTessellationScale(sqrt(m10 * m10 + m11 * m11)); 77 } 78} 79 80/** 81 * Produces a pseudo-normal for a vertex, given the normals of the two incoming lines. If the offset 82 * from each vertex in a perimeter is calculated, the resultant lines connecting the offset vertices 83 * will be offset by 1.0 84 * 85 * Note that we can't add and normalize the two vectors, that would result in a rectangle having an 86 * offset of (sqrt(2)/2, sqrt(2)/2) at each corner, instead of (1, 1) 87 * 88 * NOTE: assumes angles between normals 90 degrees or less 89 */ 90inline static Vector2 totalOffsetFromNormals(const Vector2& normalA, const Vector2& normalB) { 91 return (normalA + normalB) / (1 + fabs(normalA.dot(normalB))); 92} 93 94/** 95 * Structure used for storing useful information about the SkPaint and scale used for tessellating 96 */ 97struct PaintInfo { 98public: 99 PaintInfo(const SkPaint* paint, const mat4& transform) : 100 style(paint->getStyle()), cap(paint->getStrokeCap()), isAA(paint->isAntiAlias()), 101 halfStrokeWidth(paint->getStrokeWidth() * 0.5f), maxAlpha(1.0f) { 102 // compute inverse scales 103 if (CC_LIKELY(transform.isPureTranslate())) { 104 inverseScaleX = 1.0f; 105 inverseScaleY = 1.0f; 106 } else { 107 float scaleX, scaleY; 108 PathTessellator::extractTessellationScales(transform, &scaleX, &scaleY); 109 inverseScaleX = 1.0f / scaleX; 110 inverseScaleY = 1.0f / scaleY; 111 } 112 113 if (isAA && halfStrokeWidth != 0 && inverseScaleX == inverseScaleY && 114 2 * halfStrokeWidth < inverseScaleX) { 115 // AA, with non-hairline stroke, width < 1 pixel. Scale alpha and treat as hairline. 116 maxAlpha *= (2 * halfStrokeWidth) / inverseScaleX; 117 halfStrokeWidth = 0.0f; 118 } 119 } 120 121 SkPaint::Style style; 122 SkPaint::Cap cap; 123 bool isAA; 124 float inverseScaleX; 125 float inverseScaleY; 126 float halfStrokeWidth; 127 float maxAlpha; 128 129 inline void scaleOffsetForStrokeWidth(Vector2& offset) const { 130 if (halfStrokeWidth == 0.0f) { 131 // hairline - compensate for scale 132 offset.x *= 0.5f * inverseScaleX; 133 offset.y *= 0.5f * inverseScaleY; 134 } else { 135 offset *= halfStrokeWidth; 136 } 137 } 138 139 /** 140 * NOTE: the input will not always be a normal, especially for sharp edges - it should be the 141 * result of totalOffsetFromNormals (see documentation there) 142 */ 143 inline Vector2 deriveAAOffset(const Vector2& offset) const { 144 return (Vector2){offset.x * 0.5f * inverseScaleX, offset.y * 0.5f * inverseScaleY}; 145 } 146 147 /** 148 * Returns the number of cap divisions beyond the minimum 2 (kButt_Cap/kSquareCap will return 0) 149 * Should only be used when stroking and drawing caps 150 */ 151 inline int capExtraDivisions() const { 152 if (cap == SkPaint::kRound_Cap) { 153 if (halfStrokeWidth == 0.0f) return 2; 154 155 // ROUND_CAP_THRESH is the maximum error for polygonal approximation of the round cap 156 const float errConst = (-ROUND_CAP_THRESH / halfStrokeWidth + 1); 157 const float targetCosVal = 2 * errConst * errConst - 1; 158 int neededDivisions = (int)(ceilf(PI / acos(targetCosVal)/2)) * 2; 159 return neededDivisions; 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 bool wasClosed = approximatePathOutlineVertices(path, forceClose, 743 threshInvScaleX * threshInvScaleX, threshInvScaleY * threshInvScaleY, 744 OUTLINE_REFINE_THRESHOLD_SQUARED, tempVertices); 745 746 if (!tempVertices.size()) { 747 // path was empty, return without allocating vertex buffer 748 return; 749 } 750 751#if VERTEX_DEBUG 752 for (unsigned int i = 0; i < tempVertices.size(); i++) { 753 ALOGD("orig path: point at %f %f", 754 tempVertices[i].x, tempVertices[i].y); 755 } 756#endif 757 758 if (paintInfo.style == SkPaint::kStroke_Style) { 759 if (!paintInfo.isAA) { 760 if (wasClosed) { 761 getStrokeVerticesFromPerimeter(paintInfo, tempVertices, vertexBuffer); 762 } else { 763 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer); 764 } 765 766 } else { 767 if (wasClosed) { 768 getStrokeVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer); 769 } else { 770 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer); 771 } 772 } 773 } else { 774 // For kStrokeAndFill style, the path should be adjusted externally. 775 // It will be treated as a fill here. 776 if (!paintInfo.isAA) { 777 getFillVerticesFromPerimeter(tempVertices, vertexBuffer); 778 } else { 779 getFillVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer); 780 } 781 } 782 783 Rect bounds(path.getBounds()); 784 paintInfo.expandBoundsForStroke(&bounds); 785 vertexBuffer.setBounds(bounds); 786 vertexBuffer.setMeshFeatureFlags(paintInfo.isAA ? VertexBuffer::kAlpha : VertexBuffer::kNone); 787} 788 789template <class TYPE> 790static void instanceVertices(VertexBuffer& srcBuffer, VertexBuffer& dstBuffer, 791 const float* points, int count, Rect& bounds) { 792 bounds.set(points[0], points[1], points[0], points[1]); 793 794 int numPoints = count / 2; 795 int verticesPerPoint = srcBuffer.getVertexCount(); 796 dstBuffer.alloc<TYPE>(numPoints * verticesPerPoint + (numPoints - 1) * 2); 797 798 for (int i = 0; i < count; i += 2) { 799 bounds.expandToCoverVertex(points[i + 0], points[i + 1]); 800 dstBuffer.copyInto<TYPE>(srcBuffer, points[i + 0], points[i + 1]); 801 } 802 dstBuffer.createDegenerateSeparators<TYPE>(verticesPerPoint); 803} 804 805void PathTessellator::tessellatePoints(const float* points, int count, const SkPaint* paint, 806 const mat4& transform, VertexBuffer& vertexBuffer) { 807 const PaintInfo paintInfo(paint, transform); 808 809 // determine point shape 810 SkPath path; 811 float radius = paintInfo.halfStrokeWidth; 812 if (radius == 0.0f) radius = 0.5f; 813 814 if (paintInfo.cap == SkPaint::kRound_Cap) { 815 path.addCircle(0, 0, radius); 816 } else { 817 path.addRect(-radius, -radius, radius, radius); 818 } 819 820 // calculate outline 821 Vector<Vertex> outlineVertices; 822 approximatePathOutlineVertices(path, true, 823 paintInfo.inverseScaleX * paintInfo.inverseScaleX, 824 paintInfo.inverseScaleY * paintInfo.inverseScaleY, 825 OUTLINE_REFINE_THRESHOLD_SQUARED, 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 thresholdSquared, 903 Vector<Vertex>& outputVertices) { 904 return approximatePathOutlineVertices(path, true, 1.0f, 1.0f, thresholdSquared, outputVertices); 905} 906 907void pushToVector(Vector<Vertex>& vertices, float x, float y) { 908 // TODO: make this not yuck 909 vertices.push(); 910 Vertex* newVertex = &(vertices.editArray()[vertices.size() - 1]); 911 Vertex::set(newVertex, x, y); 912} 913 914bool PathTessellator::approximatePathOutlineVertices(const SkPath& path, bool forceClose, 915 float sqrInvScaleX, float sqrInvScaleY, float thresholdSquared, 916 Vector<Vertex>& outputVertices) { 917 ATRACE_CALL(); 918 919 // TODO: to support joins other than sharp miter, join vertices should be labelled in the 920 // perimeter, or resolved into more vertices. Reconsider forceClose-ing in that case. 921 SkPath::Iter iter(path, forceClose); 922 SkPoint pts[4]; 923 SkPath::Verb v; 924 while (SkPath::kDone_Verb != (v = iter.next(pts))) { 925 switch (v) { 926 case SkPath::kMove_Verb: 927 pushToVector(outputVertices, pts[0].x(), pts[0].y()); 928 ALOGV("Move to pos %f %f", pts[0].x(), pts[0].y()); 929 break; 930 case SkPath::kClose_Verb: 931 ALOGV("Close at pos %f %f", pts[0].x(), pts[0].y()); 932 break; 933 case SkPath::kLine_Verb: 934 ALOGV("kLine_Verb %f %f -> %f %f", pts[0].x(), pts[0].y(), pts[1].x(), pts[1].y()); 935 pushToVector(outputVertices, pts[1].x(), pts[1].y()); 936 break; 937 case SkPath::kQuad_Verb: 938 ALOGV("kQuad_Verb"); 939 recursiveQuadraticBezierVertices( 940 pts[0].x(), pts[0].y(), 941 pts[2].x(), pts[2].y(), 942 pts[1].x(), pts[1].y(), 943 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices); 944 break; 945 case SkPath::kCubic_Verb: 946 ALOGV("kCubic_Verb"); 947 recursiveCubicBezierVertices( 948 pts[0].x(), pts[0].y(), 949 pts[1].x(), pts[1].y(), 950 pts[3].x(), pts[3].y(), 951 pts[2].x(), pts[2].y(), 952 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices); 953 break; 954 default: 955 break; 956 } 957 } 958 959 int size = outputVertices.size(); 960 if (size >= 2 && outputVertices[0].x == outputVertices[size - 1].x && 961 outputVertices[0].y == outputVertices[size - 1].y) { 962 outputVertices.pop(); 963 return true; 964 } 965 return false; 966} 967 968/////////////////////////////////////////////////////////////////////////////// 969// Bezier approximation 970/////////////////////////////////////////////////////////////////////////////// 971 972void PathTessellator::recursiveCubicBezierVertices( 973 float p1x, float p1y, float c1x, float c1y, 974 float p2x, float p2y, float c2x, float c2y, 975 float sqrInvScaleX, float sqrInvScaleY, float thresholdSquared, 976 Vector<Vertex>& outputVertices, int depth) { 977 float dx = p2x - p1x; 978 float dy = p2y - p1y; 979 float d1 = fabs((c1x - p2x) * dy - (c1y - p2y) * dx); 980 float d2 = fabs((c2x - p2x) * dy - (c2y - p2y) * dx); 981 float d = d1 + d2; 982 983 // multiplying by sqrInvScaleY/X equivalent to multiplying in dimensional scale factors 984 if (depth >= MAX_DEPTH 985 || d * d <= thresholdSquared * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) { 986 // below thresh, draw line by adding endpoint 987 pushToVector(outputVertices, p2x, p2y); 988 } else { 989 float p1c1x = (p1x + c1x) * 0.5f; 990 float p1c1y = (p1y + c1y) * 0.5f; 991 float p2c2x = (p2x + c2x) * 0.5f; 992 float p2c2y = (p2y + c2y) * 0.5f; 993 994 float c1c2x = (c1x + c2x) * 0.5f; 995 float c1c2y = (c1y + c2y) * 0.5f; 996 997 float p1c1c2x = (p1c1x + c1c2x) * 0.5f; 998 float p1c1c2y = (p1c1y + c1c2y) * 0.5f; 999 1000 float p2c1c2x = (p2c2x + c1c2x) * 0.5f; 1001 float p2c1c2y = (p2c2y + c1c2y) * 0.5f; 1002 1003 float mx = (p1c1c2x + p2c1c2x) * 0.5f; 1004 float my = (p1c1c2y + p2c1c2y) * 0.5f; 1005 1006 recursiveCubicBezierVertices( 1007 p1x, p1y, p1c1x, p1c1y, 1008 mx, my, p1c1c2x, p1c1c2y, 1009 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices, depth + 1); 1010 recursiveCubicBezierVertices( 1011 mx, my, p2c1c2x, p2c1c2y, 1012 p2x, p2y, p2c2x, p2c2y, 1013 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices, depth + 1); 1014 } 1015} 1016 1017void PathTessellator::recursiveQuadraticBezierVertices( 1018 float ax, float ay, 1019 float bx, float by, 1020 float cx, float cy, 1021 float sqrInvScaleX, float sqrInvScaleY, float thresholdSquared, 1022 Vector<Vertex>& outputVertices, int depth) { 1023 float dx = bx - ax; 1024 float dy = by - ay; 1025 float d = (cx - bx) * dy - (cy - by) * dx; 1026 1027 // multiplying by sqrInvScaleY/X equivalent to multiplying in dimensional scale factors 1028 if (depth >= MAX_DEPTH 1029 || d * d <= thresholdSquared * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) { 1030 // below thresh, draw line by adding endpoint 1031 pushToVector(outputVertices, bx, by); 1032 } else { 1033 float acx = (ax + cx) * 0.5f; 1034 float bcx = (bx + cx) * 0.5f; 1035 float acy = (ay + cy) * 0.5f; 1036 float bcy = (by + cy) * 0.5f; 1037 1038 // midpoint 1039 float mx = (acx + bcx) * 0.5f; 1040 float my = (acy + bcy) * 0.5f; 1041 1042 recursiveQuadraticBezierVertices(ax, ay, mx, my, acx, acy, 1043 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices, depth + 1); 1044 recursiveQuadraticBezierVertices(mx, my, bx, by, bcx, bcy, 1045 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices, depth + 1); 1046 } 1047} 1048 1049}; // namespace uirenderer 1050}; // namespace android 1051