PathTessellator.cpp revision 1aa5d2d7068147ff781cfe911a93f01593a68c79
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 53namespace android { 54namespace uirenderer { 55 56#define OUTLINE_REFINE_THRESHOLD_SQUARED (0.5f * 0.5f) 57#define ROUND_CAP_THRESH 0.25f 58#define PI 3.1415926535897932f 59 60// temporary error thresholds 61#define ERROR_DEPTH 20 62#define ERROR_SCALE 1e10 63#define ERROR_SQR_INV_THRESH 1e-20 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 = sqrt(m00 * m00 + m01 * m01); 76 *scaleY = sqrt(m10 * m10 + m11 * m11); 77 78 LOG_ALWAYS_FATAL_IF(*scaleX > ERROR_SCALE || *scaleY > ERROR_SCALE, 79 "scales %e x %e too large for tessellation", *scaleX, *scaleY); 80 } 81} 82 83/** 84 * Produces a pseudo-normal for a vertex, given the normals of the two incoming lines. If the offset 85 * from each vertex in a perimeter is calculated, the resultant lines connecting the offset vertices 86 * will be offset by 1.0 87 * 88 * Note that we can't add and normalize the two vectors, that would result in a rectangle having an 89 * offset of (sqrt(2)/2, sqrt(2)/2) at each corner, instead of (1, 1) 90 * 91 * NOTE: assumes angles between normals 90 degrees or less 92 */ 93inline static Vector2 totalOffsetFromNormals(const Vector2& normalA, const Vector2& normalB) { 94 return (normalA + normalB) / (1 + fabs(normalA.dot(normalB))); 95} 96 97/** 98 * Structure used for storing useful information about the SkPaint and scale used for tessellating 99 */ 100struct PaintInfo { 101public: 102 PaintInfo(const SkPaint* paint, const mat4& transform) : 103 style(paint->getStyle()), cap(paint->getStrokeCap()), isAA(paint->isAntiAlias()), 104 halfStrokeWidth(paint->getStrokeWidth() * 0.5f), maxAlpha(1.0f) { 105 // compute inverse scales 106 if (CC_LIKELY(transform.isPureTranslate())) { 107 inverseScaleX = 1.0f; 108 inverseScaleY = 1.0f; 109 } else { 110 float scaleX, scaleY; 111 PathTessellator::extractTessellationScales(transform, &scaleX, &scaleY); 112 inverseScaleX = (scaleX != 0) ? (1.0f / scaleX) : 1.0f; 113 inverseScaleY = (scaleY != 0) ? (1.0f / scaleY) : 1.0f; 114 } 115 116 if (isAA && halfStrokeWidth != 0 && inverseScaleX == inverseScaleY && 117 2 * halfStrokeWidth < inverseScaleX) { 118 // AA, with non-hairline stroke, width < 1 pixel. Scale alpha and treat as hairline. 119 maxAlpha *= (2 * halfStrokeWidth) / inverseScaleX; 120 halfStrokeWidth = 0.0f; 121 } 122 } 123 124 SkPaint::Style style; 125 SkPaint::Cap cap; 126 bool isAA; 127 float inverseScaleX; 128 float inverseScaleY; 129 float halfStrokeWidth; 130 float maxAlpha; 131 132 inline void scaleOffsetForStrokeWidth(Vector2& offset) const { 133 if (halfStrokeWidth == 0.0f) { 134 // hairline - compensate for scale 135 offset.x *= 0.5f * inverseScaleX; 136 offset.y *= 0.5f * inverseScaleY; 137 } else { 138 offset *= halfStrokeWidth; 139 } 140 } 141 142 /** 143 * NOTE: the input will not always be a normal, especially for sharp edges - it should be the 144 * result of totalOffsetFromNormals (see documentation there) 145 */ 146 inline Vector2 deriveAAOffset(const Vector2& offset) const { 147 return (Vector2){offset.x * 0.5f * inverseScaleX, offset.y * 0.5f * inverseScaleY}; 148 } 149 150 /** 151 * Returns the number of cap divisions beyond the minimum 2 (kButt_Cap/kSquareCap will return 0) 152 * Should only be used when stroking and drawing caps 153 */ 154 inline int capExtraDivisions() const { 155 if (cap == SkPaint::kRound_Cap) { 156 if (halfStrokeWidth == 0.0f) return 2; 157 158 // ROUND_CAP_THRESH is the maximum error for polygonal approximation of the round cap 159 const float errConst = (-ROUND_CAP_THRESH / halfStrokeWidth + 1); 160 const float targetCosVal = 2 * errConst * errConst - 1; 161 int neededDivisions = (int)(ceilf(PI / acos(targetCosVal)/2)) * 2; 162 return neededDivisions; 163 } 164 return 0; 165 } 166 167 /** 168 * Outset the bounds of point data (for line endpoints or points) to account for AA stroke 169 * geometry. 170 */ 171 void expandBoundsForStroke(Rect* bounds) const { 172 float outset = halfStrokeWidth; 173 if (outset == 0) outset = 0.5f; 174 bounds->outset(outset * inverseScaleX + Vertex::GeometryFudgeFactor(), 175 outset * inverseScaleY + Vertex::GeometryFudgeFactor()); 176 } 177}; 178 179void getFillVerticesFromPerimeter(const Vector<Vertex>& perimeter, VertexBuffer& vertexBuffer) { 180 Vertex* buffer = vertexBuffer.alloc<Vertex>(perimeter.size()); 181 182 int currentIndex = 0; 183 // zig zag between all previous points on the inside of the hull to create a 184 // triangle strip that fills the hull 185 int srcAindex = 0; 186 int srcBindex = perimeter.size() - 1; 187 while (srcAindex <= srcBindex) { 188 buffer[currentIndex++] = perimeter[srcAindex]; 189 if (srcAindex == srcBindex) break; 190 buffer[currentIndex++] = perimeter[srcBindex]; 191 srcAindex++; 192 srcBindex--; 193 } 194} 195 196/* 197 * Fills a vertexBuffer with non-alpha vertices, zig-zagging at each perimeter point to create a 198 * tri-strip as wide as the stroke. 199 * 200 * Uses an additional 2 vertices at the end to wrap around, closing the tri-strip 201 * (for a total of perimeter.size() * 2 + 2 vertices) 202 */ 203void getStrokeVerticesFromPerimeter(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter, 204 VertexBuffer& vertexBuffer) { 205 Vertex* buffer = vertexBuffer.alloc<Vertex>(perimeter.size() * 2 + 2); 206 207 int currentIndex = 0; 208 const Vertex* last = &(perimeter[perimeter.size() - 1]); 209 const Vertex* current = &(perimeter[0]); 210 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 211 lastNormal.normalize(); 212 for (unsigned int i = 0; i < perimeter.size(); i++) { 213 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]); 214 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 215 nextNormal.normalize(); 216 217 Vector2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal); 218 paintInfo.scaleOffsetForStrokeWidth(totalOffset); 219 220 Vertex::set(&buffer[currentIndex++], 221 current->x + totalOffset.x, 222 current->y + totalOffset.y); 223 224 Vertex::set(&buffer[currentIndex++], 225 current->x - totalOffset.x, 226 current->y - totalOffset.y); 227 228 last = current; 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 const float radialScale = 2.0f / (1 + cos(dTheta)); 279 280 int capOffset; 281 for (int i = 0; i < extra; i++) { 282 if (i < extra / 2) { 283 capOffset = extra - 2 * i - 1; 284 } else { 285 capOffset = 2 * i - extra; 286 } 287 288 beginTheta += dTheta; 289 Vector2 beginRadialOffset = {cos(beginTheta), sin(beginTheta)}; 290 paintInfo.scaleOffsetForStrokeWidth(beginRadialOffset); 291 Vertex::set(&buffer[capOffset], 292 vertices[0].x + beginRadialOffset.x, 293 vertices[0].y + beginRadialOffset.y); 294 295 endTheta += dTheta; 296 Vector2 endRadialOffset = {cos(endTheta), sin(endTheta)}; 297 paintInfo.scaleOffsetForStrokeWidth(endRadialOffset); 298 Vertex::set(&buffer[allocSize - 1 - capOffset], 299 vertices[lastIndex].x + endRadialOffset.x, 300 vertices[lastIndex].y + endRadialOffset.y); 301 } 302 } 303 304 int currentIndex = extra; 305 const Vertex* last = &(vertices[0]); 306 const Vertex* current = &(vertices[1]); 307 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 308 lastNormal.normalize(); 309 310 storeBeginEnd(paintInfo, vertices[0], lastNormal, buffer, currentIndex, true); 311 312 for (unsigned int i = 1; i < vertices.size() - 1; i++) { 313 const Vertex* next = &(vertices[i + 1]); 314 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 315 nextNormal.normalize(); 316 317 Vector2 strokeOffset = totalOffsetFromNormals(lastNormal, nextNormal); 318 paintInfo.scaleOffsetForStrokeWidth(strokeOffset); 319 320 Vector2 center = {current->x, current->y}; 321 Vertex::set(&buffer[currentIndex++], center + strokeOffset); 322 Vertex::set(&buffer[currentIndex++], center - strokeOffset); 323 324 current = next; 325 lastNormal = nextNormal; 326 } 327 328 storeBeginEnd(paintInfo, vertices[lastIndex], lastNormal, buffer, currentIndex, false); 329 330 DEBUG_DUMP_BUFFER(); 331} 332 333/** 334 * Populates a vertexBuffer with AlphaVertices to create an anti-aliased fill shape tessellation 335 * 336 * 1 - create the AA perimeter of unit width, by zig-zagging at each point around the perimeter of 337 * the shape (using 2 * perimeter.size() vertices) 338 * 339 * 2 - wrap around to the beginning to complete the perimeter (2 vertices) 340 * 341 * 3 - zig zag back and forth inside the shape to fill it (using perimeter.size() vertices) 342 */ 343void getFillVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter, 344 VertexBuffer& vertexBuffer, float maxAlpha = 1.0f) { 345 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(perimeter.size() * 3 + 2); 346 347 // generate alpha points - fill Alpha vertex gaps in between each point with 348 // alpha 0 vertex, offset by a scaled normal. 349 int currentIndex = 0; 350 const Vertex* last = &(perimeter[perimeter.size() - 1]); 351 const Vertex* current = &(perimeter[0]); 352 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 353 lastNormal.normalize(); 354 for (unsigned int i = 0; i < perimeter.size(); i++) { 355 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]); 356 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 357 nextNormal.normalize(); 358 359 // AA point offset from original point is that point's normal, such that each side is offset 360 // by .5 pixels 361 Vector2 totalOffset = paintInfo.deriveAAOffset(totalOffsetFromNormals(lastNormal, nextNormal)); 362 363 AlphaVertex::set(&buffer[currentIndex++], 364 current->x + totalOffset.x, 365 current->y + totalOffset.y, 366 0.0f); 367 AlphaVertex::set(&buffer[currentIndex++], 368 current->x - totalOffset.x, 369 current->y - totalOffset.y, 370 maxAlpha); 371 372 last = current; 373 current = next; 374 lastNormal = nextNormal; 375 } 376 377 // wrap around to beginning 378 buffer[currentIndex++] = buffer[0]; 379 buffer[currentIndex++] = buffer[1]; 380 381 // zig zag between all previous points on the inside of the hull to create a 382 // triangle strip that fills the hull, repeating the first inner point to 383 // create degenerate tris to start inside path 384 int srcAindex = 0; 385 int srcBindex = perimeter.size() - 1; 386 while (srcAindex <= srcBindex) { 387 buffer[currentIndex++] = buffer[srcAindex * 2 + 1]; 388 if (srcAindex == srcBindex) break; 389 buffer[currentIndex++] = buffer[srcBindex * 2 + 1]; 390 srcAindex++; 391 srcBindex--; 392 } 393 394 DEBUG_DUMP_BUFFER(); 395} 396 397/** 398 * Stores geometry for a single, AA-perimeter (potentially rounded) cap 399 * 400 * For explanation of constants and general methodoloyg, see comments for 401 * getStrokeVerticesFromUnclosedVerticesAA() below. 402 */ 403inline static void storeCapAA(const PaintInfo& paintInfo, const Vector<Vertex>& vertices, 404 AlphaVertex* buffer, bool isFirst, Vector2 normal, int offset) { 405 const int extra = paintInfo.capExtraDivisions(); 406 const int extraOffset = (extra + 1) / 2; 407 const int capIndex = isFirst 408 ? 2 * offset + 6 + 2 * (extra + extraOffset) 409 : offset + 2 + 2 * extraOffset; 410 if (isFirst) normal *= -1; 411 412 // TODO: this normal should be scaled by radialScale if extra != 0, see totalOffsetFromNormals() 413 Vector2 AAOffset = paintInfo.deriveAAOffset(normal); 414 415 Vector2 strokeOffset = normal; 416 paintInfo.scaleOffsetForStrokeWidth(strokeOffset); 417 Vector2 outerOffset = strokeOffset + AAOffset; 418 Vector2 innerOffset = strokeOffset - AAOffset; 419 420 Vector2 capAAOffset = {0, 0}; 421 if (paintInfo.cap != SkPaint::kRound_Cap) { 422 // if the cap is square or butt, the inside primary cap vertices will be inset in two 423 // directions - both normal to the stroke, and parallel to it. 424 capAAOffset = (Vector2){-AAOffset.y, AAOffset.x}; 425 } 426 427 // determine referencePoint, the center point for the 4 primary cap vertices 428 const Vertex* point = isFirst ? vertices.begin() : (vertices.end() - 1); 429 Vector2 referencePoint = {point->x, point->y}; 430 if (paintInfo.cap == SkPaint::kSquare_Cap) { 431 // To account for square cap, move the primary cap vertices (that create the AA edge) by the 432 // stroke offset vector (rotated to be parallel to the stroke) 433 Vector2 rotated = {-strokeOffset.y, strokeOffset.x}; 434 referencePoint += rotated; 435 } 436 437 AlphaVertex::set(&buffer[capIndex + 0], 438 referencePoint.x + outerOffset.x + capAAOffset.x, 439 referencePoint.y + outerOffset.y + capAAOffset.y, 440 0.0f); 441 AlphaVertex::set(&buffer[capIndex + 1], 442 referencePoint.x + innerOffset.x - capAAOffset.x, 443 referencePoint.y + innerOffset.y - capAAOffset.y, 444 paintInfo.maxAlpha); 445 446 bool isRound = paintInfo.cap == SkPaint::kRound_Cap; 447 448 const int postCapIndex = (isRound && isFirst) ? (2 * extraOffset - 2) : capIndex + (2 * extra); 449 AlphaVertex::set(&buffer[postCapIndex + 2], 450 referencePoint.x - outerOffset.x + capAAOffset.x, 451 referencePoint.y - outerOffset.y + capAAOffset.y, 452 0.0f); 453 AlphaVertex::set(&buffer[postCapIndex + 3], 454 referencePoint.x - innerOffset.x - capAAOffset.x, 455 referencePoint.y - innerOffset.y - capAAOffset.y, 456 paintInfo.maxAlpha); 457 458 if (isRound) { 459 const float dTheta = PI / (extra + 1); 460 const float radialScale = 2.0f / (1 + cos(dTheta)); 461 float theta = atan2(normal.y, normal.x); 462 int capPerimIndex = capIndex + 2; 463 464 for (int i = 0; i < extra; i++) { 465 theta += dTheta; 466 467 Vector2 radialOffset = {cos(theta), sin(theta)}; 468 469 // scale to compensate for pinching at sharp angles, see totalOffsetFromNormals() 470 radialOffset *= radialScale; 471 472 AAOffset = paintInfo.deriveAAOffset(radialOffset); 473 paintInfo.scaleOffsetForStrokeWidth(radialOffset); 474 AlphaVertex::set(&buffer[capPerimIndex++], 475 referencePoint.x + radialOffset.x + AAOffset.x, 476 referencePoint.y + radialOffset.y + AAOffset.y, 477 0.0f); 478 AlphaVertex::set(&buffer[capPerimIndex++], 479 referencePoint.x + radialOffset.x - AAOffset.x, 480 referencePoint.y + radialOffset.y - AAOffset.y, 481 paintInfo.maxAlpha); 482 483 if (isFirst && i == extra - extraOffset) { 484 //copy most recent two points to first two points 485 buffer[0] = buffer[capPerimIndex - 2]; 486 buffer[1] = buffer[capPerimIndex - 1]; 487 488 capPerimIndex = 2; // start writing the rest of the round cap at index 2 489 } 490 } 491 492 if (isFirst) { 493 const int startCapFillIndex = capIndex + 2 * (extra - extraOffset) + 4; 494 int capFillIndex = startCapFillIndex; 495 for (int i = 0; i < extra + 2; i += 2) { 496 buffer[capFillIndex++] = buffer[1 + i]; 497 // TODO: to support odd numbers of divisions, break here on the last iteration 498 buffer[capFillIndex++] = buffer[startCapFillIndex - 3 - i]; 499 } 500 } else { 501 int capFillIndex = 6 * vertices.size() + 2 + 6 * extra - (extra + 2); 502 for (int i = 0; i < extra + 2; i += 2) { 503 buffer[capFillIndex++] = buffer[capIndex + 1 + i]; 504 // TODO: to support odd numbers of divisions, break here on the last iteration 505 buffer[capFillIndex++] = buffer[capIndex + 3 + 2 * extra - i]; 506 } 507 } 508 return; 509 } 510 if (isFirst) { 511 buffer[0] = buffer[postCapIndex + 2]; 512 buffer[1] = buffer[postCapIndex + 3]; 513 buffer[postCapIndex + 4] = buffer[1]; // degenerate tris (the only two!) 514 buffer[postCapIndex + 5] = buffer[postCapIndex + 1]; 515 } else { 516 buffer[6 * vertices.size()] = buffer[postCapIndex + 1]; 517 buffer[6 * vertices.size() + 1] = buffer[postCapIndex + 3]; 518 } 519} 520 521/* 522the geometry for an aa, capped stroke consists of the following: 523 524 # vertices | function 525---------------------------------------------------------------------- 526a) 2 | Start AA perimeter 527b) 2, 2 * roundDivOff | First half of begin cap's perimeter 528 | 529 2 * middlePts | 'Outer' or 'Top' AA perimeter half (between caps) 530 | 531a) 4 | End cap's 532b) 2, 2 * roundDivs, 2 | AA perimeter 533 | 534 2 * middlePts | 'Inner' or 'bottom' AA perimeter half 535 | 536a) 6 | Begin cap's perimeter 537b) 2, 2*(rD - rDO + 1), | Last half of begin cap's perimeter 538 roundDivs, 2 | 539 | 540 2 * middlePts | Stroke's full opacity center strip 541 | 542a) 2 | end stroke 543b) 2, roundDivs | (and end cap fill, for round) 544 545Notes: 546* rows starting with 'a)' denote the Butt or Square cap vertex use, 'b)' denote Round 547 548* 'middlePts' is (number of points in the unclosed input vertex list, minus 2) times two 549 550* 'roundDivs' or 'rD' is the number of extra vertices (beyond the minimum of 2) that define the 551 round cap's shape, and is at least two. This will increase with cap size to sufficiently 552 define the cap's level of tessellation. 553 554* 'roundDivOffset' or 'rDO' is the point about halfway along the start cap's round perimeter, where 555 the stream of vertices for the AA perimeter starts. By starting and ending the perimeter at 556 this offset, the fill of the stroke is drawn from this point with minimal extra vertices. 557 558This means the outer perimeter starts at: 559 outerIndex = (2) OR (2 + 2 * roundDivOff) 560the inner perimeter (since it is filled in reverse) starts at: 561 innerIndex = outerIndex + (4 * middlePts) + ((4) OR (4 + 2 * roundDivs)) - 1 562the stroke starts at: 563 strokeIndex = innerIndex + 1 + ((6) OR (6 + 3 * roundDivs - 2 * roundDivOffset)) 564 565The total needed allocated space is either: 566 2 + 4 + 6 + 2 + 3 * (2 * middlePts) = 14 + 6 * middlePts = 2 + 6 * pts 567or, for rounded caps: 568 (2 + 2 * rDO) + (4 + 2 * rD) + (2 * (rD - rDO + 1) 569 + roundDivs + 4) + (2 + roundDivs) + 3 * (2 * middlePts) 570 = 14 + 6 * middlePts + 6 * roundDivs 571 = 2 + 6 * pts + 6 * roundDivs 572 */ 573void getStrokeVerticesFromUnclosedVerticesAA(const PaintInfo& paintInfo, 574 const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) { 575 576 const int extra = paintInfo.capExtraDivisions(); 577 const int allocSize = 6 * vertices.size() + 2 + 6 * extra; 578 579 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(allocSize); 580 581 const int extraOffset = (extra + 1) / 2; 582 int offset = 2 * (vertices.size() - 2); 583 // there is no outer/inner here, using them for consistency with below approach 584 int currentAAOuterIndex = 2 + 2 * extraOffset; 585 int currentAAInnerIndex = currentAAOuterIndex + (2 * offset) + 3 + (2 * extra); 586 int currentStrokeIndex = currentAAInnerIndex + 7 + (3 * extra - 2 * extraOffset); 587 588 const Vertex* last = &(vertices[0]); 589 const Vertex* current = &(vertices[1]); 590 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 591 lastNormal.normalize(); 592 593 // TODO: use normal from bezier traversal for cap, instead of from vertices 594 storeCapAA(paintInfo, vertices, buffer, true, lastNormal, offset); 595 596 for (unsigned int i = 1; i < vertices.size() - 1; i++) { 597 const Vertex* next = &(vertices[i + 1]); 598 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 599 nextNormal.normalize(); 600 601 Vector2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal); 602 Vector2 AAOffset = paintInfo.deriveAAOffset(totalOffset); 603 604 Vector2 innerOffset = totalOffset; 605 paintInfo.scaleOffsetForStrokeWidth(innerOffset); 606 Vector2 outerOffset = innerOffset + AAOffset; 607 innerOffset -= AAOffset; 608 609 AlphaVertex::set(&buffer[currentAAOuterIndex++], 610 current->x + outerOffset.x, 611 current->y + outerOffset.y, 612 0.0f); 613 AlphaVertex::set(&buffer[currentAAOuterIndex++], 614 current->x + innerOffset.x, 615 current->y + innerOffset.y, 616 paintInfo.maxAlpha); 617 618 AlphaVertex::set(&buffer[currentStrokeIndex++], 619 current->x + innerOffset.x, 620 current->y + innerOffset.y, 621 paintInfo.maxAlpha); 622 AlphaVertex::set(&buffer[currentStrokeIndex++], 623 current->x - innerOffset.x, 624 current->y - innerOffset.y, 625 paintInfo.maxAlpha); 626 627 AlphaVertex::set(&buffer[currentAAInnerIndex--], 628 current->x - innerOffset.x, 629 current->y - innerOffset.y, 630 paintInfo.maxAlpha); 631 AlphaVertex::set(&buffer[currentAAInnerIndex--], 632 current->x - outerOffset.x, 633 current->y - outerOffset.y, 634 0.0f); 635 636 current = next; 637 lastNormal = nextNormal; 638 } 639 640 // TODO: use normal from bezier traversal for cap, instead of from vertices 641 storeCapAA(paintInfo, vertices, buffer, false, lastNormal, offset); 642 643 DEBUG_DUMP_ALPHA_BUFFER(); 644} 645 646 647void getStrokeVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter, 648 VertexBuffer& vertexBuffer) { 649 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(6 * perimeter.size() + 8); 650 651 int offset = 2 * perimeter.size() + 3; 652 int currentAAOuterIndex = 0; 653 int currentStrokeIndex = offset; 654 int currentAAInnerIndex = offset * 2; 655 656 const Vertex* last = &(perimeter[perimeter.size() - 1]); 657 const Vertex* current = &(perimeter[0]); 658 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 659 lastNormal.normalize(); 660 for (unsigned int i = 0; i < perimeter.size(); i++) { 661 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]); 662 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 663 nextNormal.normalize(); 664 665 Vector2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal); 666 Vector2 AAOffset = paintInfo.deriveAAOffset(totalOffset); 667 668 Vector2 innerOffset = totalOffset; 669 paintInfo.scaleOffsetForStrokeWidth(innerOffset); 670 Vector2 outerOffset = innerOffset + AAOffset; 671 innerOffset -= AAOffset; 672 673 AlphaVertex::set(&buffer[currentAAOuterIndex++], 674 current->x + outerOffset.x, 675 current->y + outerOffset.y, 676 0.0f); 677 AlphaVertex::set(&buffer[currentAAOuterIndex++], 678 current->x + innerOffset.x, 679 current->y + innerOffset.y, 680 paintInfo.maxAlpha); 681 682 AlphaVertex::set(&buffer[currentStrokeIndex++], 683 current->x + innerOffset.x, 684 current->y + innerOffset.y, 685 paintInfo.maxAlpha); 686 AlphaVertex::set(&buffer[currentStrokeIndex++], 687 current->x - innerOffset.x, 688 current->y - innerOffset.y, 689 paintInfo.maxAlpha); 690 691 AlphaVertex::set(&buffer[currentAAInnerIndex++], 692 current->x - innerOffset.x, 693 current->y - innerOffset.y, 694 paintInfo.maxAlpha); 695 AlphaVertex::set(&buffer[currentAAInnerIndex++], 696 current->x - outerOffset.x, 697 current->y - outerOffset.y, 698 0.0f); 699 700 last = current; 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} 787 788template <class TYPE> 789static void instanceVertices(VertexBuffer& srcBuffer, VertexBuffer& dstBuffer, 790 const float* points, int count, Rect& bounds) { 791 bounds.set(points[0], points[1], points[0], points[1]); 792 793 int numPoints = count / 2; 794 int verticesPerPoint = srcBuffer.getVertexCount(); 795 dstBuffer.alloc<TYPE>(numPoints * verticesPerPoint + (numPoints - 1) * 2); 796 797 for (int i = 0; i < count; i += 2) { 798 bounds.expandToCoverVertex(points[i + 0], points[i + 1]); 799 dstBuffer.copyInto<TYPE>(srcBuffer, points[i + 0], points[i + 1]); 800 } 801 dstBuffer.createDegenerateSeparators<TYPE>(verticesPerPoint); 802} 803 804void PathTessellator::tessellatePoints(const float* points, int count, const SkPaint* paint, 805 const mat4& transform, VertexBuffer& vertexBuffer) { 806 const PaintInfo paintInfo(paint, transform); 807 808 // determine point shape 809 SkPath path; 810 float radius = paintInfo.halfStrokeWidth; 811 if (radius == 0.0f) radius = 0.25f; 812 813 if (paintInfo.cap == SkPaint::kRound_Cap) { 814 path.addCircle(0, 0, radius); 815 } else { 816 path.addRect(-radius, -radius, radius, radius); 817 } 818 819 // calculate outline 820 Vector<Vertex> outlineVertices; 821 approximatePathOutlineVertices(path, true, 822 paintInfo.inverseScaleX * paintInfo.inverseScaleX, 823 paintInfo.inverseScaleY * paintInfo.inverseScaleY, 824 OUTLINE_REFINE_THRESHOLD_SQUARED, outlineVertices); 825 826 if (!outlineVertices.size()) return; 827 828 Rect bounds; 829 // tessellate, then duplicate outline across points 830 int numPoints = count / 2; 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} 845 846void PathTessellator::tessellateLines(const float* points, int count, const SkPaint* paint, 847 const mat4& transform, VertexBuffer& vertexBuffer) { 848 ATRACE_CALL(); 849 const PaintInfo paintInfo(paint, transform); 850 851 const int extra = paintInfo.capExtraDivisions(); 852 int numLines = count / 4; 853 int lineAllocSize; 854 // pre-allocate space for lines in the buffer, and degenerate tris in between 855 if (paintInfo.isAA) { 856 lineAllocSize = 6 * (2) + 2 + 6 * extra; 857 vertexBuffer.alloc<AlphaVertex>(numLines * lineAllocSize + (numLines - 1) * 2); 858 } else { 859 lineAllocSize = 2 * ((2) + extra); 860 vertexBuffer.alloc<Vertex>(numLines * lineAllocSize + (numLines - 1) * 2); 861 } 862 863 Vector<Vertex> tempVertices; 864 tempVertices.push(); 865 tempVertices.push(); 866 Vertex* tempVerticesData = tempVertices.editArray(); 867 Rect bounds; 868 bounds.set(points[0], points[1], points[0], points[1]); 869 for (int i = 0; i < count; i += 4) { 870 Vertex::set(&(tempVerticesData[0]), points[i + 0], points[i + 1]); 871 Vertex::set(&(tempVerticesData[1]), points[i + 2], points[i + 3]); 872 873 if (paintInfo.isAA) { 874 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer); 875 } else { 876 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer); 877 } 878 879 // calculate bounds 880 bounds.expandToCoverVertex(tempVerticesData[0].x, tempVerticesData[0].y); 881 bounds.expandToCoverVertex(tempVerticesData[1].x, tempVerticesData[1].y); 882 } 883 884 // since multiple objects tessellated into buffer, separate them with degen tris 885 if (paintInfo.isAA) { 886 vertexBuffer.createDegenerateSeparators<AlphaVertex>(lineAllocSize); 887 } else { 888 vertexBuffer.createDegenerateSeparators<Vertex>(lineAllocSize); 889 } 890 891 // expand bounds from vertex coords to pixel data 892 paintInfo.expandBoundsForStroke(&bounds); 893 vertexBuffer.setBounds(bounds); 894} 895 896/////////////////////////////////////////////////////////////////////////////// 897// Simple path line approximation 898/////////////////////////////////////////////////////////////////////////////// 899 900bool PathTessellator::approximatePathOutlineVertices(const SkPath& path, float thresholdSquared, 901 Vector<Vertex>& outputVertices) { 902 return approximatePathOutlineVertices(path, true, 1.0f, 1.0f, thresholdSquared, 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 912bool PathTessellator::approximatePathOutlineVertices(const SkPath& path, bool forceClose, 913 float sqrInvScaleX, float sqrInvScaleY, float thresholdSquared, 914 Vector<Vertex>& outputVertices) { 915 ATRACE_CALL(); 916 917 LOG_ALWAYS_FATAL_IF(sqrInvScaleX < ERROR_SQR_INV_THRESH || sqrInvScaleY < ERROR_SQR_INV_THRESH, 918 "Invalid scale factors used for approx %e, %e", sqrInvScaleX, sqrInvScaleY); 919 920 // TODO: to support joins other than sharp miter, join vertices should be labelled in the 921 // perimeter, or resolved into more vertices. Reconsider forceClose-ing in that case. 922 SkPath::Iter iter(path, forceClose); 923 SkPoint pts[4]; 924 SkPath::Verb v; 925 while (SkPath::kDone_Verb != (v = iter.next(pts))) { 926 switch (v) { 927 case SkPath::kMove_Verb: 928 pushToVector(outputVertices, pts[0].x(), pts[0].y()); 929 ALOGV("Move to pos %f %f", pts[0].x(), pts[0].y()); 930 break; 931 case SkPath::kClose_Verb: 932 ALOGV("Close at pos %f %f", pts[0].x(), pts[0].y()); 933 break; 934 case SkPath::kLine_Verb: 935 ALOGV("kLine_Verb %f %f -> %f %f", pts[0].x(), pts[0].y(), pts[1].x(), pts[1].y()); 936 pushToVector(outputVertices, pts[1].x(), pts[1].y()); 937 break; 938 case SkPath::kQuad_Verb: 939 ALOGV("kQuad_Verb"); 940 recursiveQuadraticBezierVertices( 941 pts[0].x(), pts[0].y(), 942 pts[2].x(), pts[2].y(), 943 pts[1].x(), pts[1].y(), 944 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices); 945 break; 946 case SkPath::kCubic_Verb: 947 ALOGV("kCubic_Verb"); 948 recursiveCubicBezierVertices( 949 pts[0].x(), pts[0].y(), 950 pts[1].x(), pts[1].y(), 951 pts[3].x(), pts[3].y(), 952 pts[2].x(), pts[2].y(), 953 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices); 954 break; 955 default: 956 break; 957 } 958 } 959 960 int size = outputVertices.size(); 961 if (size >= 2 && outputVertices[0].x == outputVertices[size - 1].x && 962 outputVertices[0].y == outputVertices[size - 1].y) { 963 outputVertices.pop(); 964 return true; 965 } 966 return false; 967} 968 969/////////////////////////////////////////////////////////////////////////////// 970// Bezier approximation 971/////////////////////////////////////////////////////////////////////////////// 972 973void PathTessellator::recursiveCubicBezierVertices( 974 float p1x, float p1y, float c1x, float c1y, 975 float p2x, float p2y, float c2x, float c2y, 976 float sqrInvScaleX, float sqrInvScaleY, float thresholdSquared, 977 Vector<Vertex>& outputVertices, int depth) { 978 LOG_ALWAYS_FATAL_IF(depth >= ERROR_DEPTH, "ERROR DEPTH exceeded: cubic approx, invscale %e x %e, vertcount %d", 979 sqrInvScaleX, sqrInvScaleY, outputVertices.size()); 980 981 float dx = p2x - p1x; 982 float dy = p2y - p1y; 983 float d1 = fabs((c1x - p2x) * dy - (c1y - p2y) * dx); 984 float d2 = fabs((c2x - p2x) * dy - (c2y - p2y) * dx); 985 float d = d1 + d2; 986 987 // multiplying by sqrInvScaleY/X equivalent to multiplying in dimensional scale factors 988 if (d * d < thresholdSquared * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) { 989 // below thresh, draw line by adding endpoint 990 pushToVector(outputVertices, p2x, p2y); 991 } else { 992 float p1c1x = (p1x + c1x) * 0.5f; 993 float p1c1y = (p1y + c1y) * 0.5f; 994 float p2c2x = (p2x + c2x) * 0.5f; 995 float p2c2y = (p2y + c2y) * 0.5f; 996 997 float c1c2x = (c1x + c2x) * 0.5f; 998 float c1c2y = (c1y + c2y) * 0.5f; 999 1000 float p1c1c2x = (p1c1x + c1c2x) * 0.5f; 1001 float p1c1c2y = (p1c1y + c1c2y) * 0.5f; 1002 1003 float p2c1c2x = (p2c2x + c1c2x) * 0.5f; 1004 float p2c1c2y = (p2c2y + c1c2y) * 0.5f; 1005 1006 float mx = (p1c1c2x + p2c1c2x) * 0.5f; 1007 float my = (p1c1c2y + p2c1c2y) * 0.5f; 1008 1009 recursiveCubicBezierVertices( 1010 p1x, p1y, p1c1x, p1c1y, 1011 mx, my, p1c1c2x, p1c1c2y, 1012 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices, depth + 1); 1013 recursiveCubicBezierVertices( 1014 mx, my, p2c1c2x, p2c1c2y, 1015 p2x, p2y, p2c2x, p2c2y, 1016 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices, depth + 1); 1017 } 1018} 1019 1020void PathTessellator::recursiveQuadraticBezierVertices( 1021 float ax, float ay, 1022 float bx, float by, 1023 float cx, float cy, 1024 float sqrInvScaleX, float sqrInvScaleY, float thresholdSquared, 1025 Vector<Vertex>& outputVertices, int depth) { 1026 LOG_ALWAYS_FATAL_IF(depth >= ERROR_DEPTH, "ERROR_DEPTH exceeded: quadratic approx, invscale %e x %e, vertcount %d", 1027 sqrInvScaleX, sqrInvScaleY, outputVertices.size()); 1028 1029 float dx = bx - ax; 1030 float dy = by - ay; 1031 float d = (cx - bx) * dy - (cy - by) * dx; 1032 1033 if (d * d < thresholdSquared * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) { 1034 // below thresh, draw line by adding endpoint 1035 pushToVector(outputVertices, bx, by); 1036 } else { 1037 float acx = (ax + cx) * 0.5f; 1038 float bcx = (bx + cx) * 0.5f; 1039 float acy = (ay + cy) * 0.5f; 1040 float bcy = (by + cy) * 0.5f; 1041 1042 // midpoint 1043 float mx = (acx + bcx) * 0.5f; 1044 float my = (acy + bcy) * 0.5f; 1045 1046 recursiveQuadraticBezierVertices(ax, ay, mx, my, acx, acy, 1047 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices, depth + 1); 1048 recursiveQuadraticBezierVertices(mx, my, bx, by, bcx, bcy, 1049 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices, depth + 1); 1050 } 1051} 1052 1053}; // namespace uirenderer 1054}; // namespace android 1055