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