PathTessellator.cpp revision 15a07a21eb33e8ca1c7444944fe0541a53380c0c
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_GRAPHICS 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/** 61 * Note: this function doesn't account for the AA case with sub-pixel line thickness (not just 0 < 62 * width < 1.0, canvas scale factors in as well) so this can't be used for points/lines 63 */ 64void PathTessellator::expandBoundsForStroke(SkRect& bounds, const SkPaint* paint) { 65 if (paint->getStyle() != SkPaint::kFill_Style) { 66 float outset = paint->getStrokeWidth() * 0.5f; 67 if (outset == 0) outset = 0.5f; // account for hairline 68 bounds.outset(outset, outset); 69 } 70} 71 72/** 73 * Produces a pseudo-normal for a vertex, given the normals of the two incoming lines. If the offset 74 * from each vertex in a perimeter is calculated, the resultant lines connecting the offset vertices 75 * will be offset by 1.0 76 * 77 * Note that we can't add and normalize the two vectors, that would result in a rectangle having an 78 * offset of (sqrt(2)/2, sqrt(2)/2) at each corner, instead of (1, 1) 79 * 80 * NOTE: assumes angles between normals 90 degrees or less 81 */ 82inline static vec2 totalOffsetFromNormals(const vec2& normalA, const vec2& normalB) { 83 return (normalA + normalB) / (1 + fabs(normalA.dot(normalB))); 84} 85 86/** 87 * Structure used for storing useful information about the SkPaint and scale used for tessellating 88 */ 89struct PaintInfo { 90public: 91 PaintInfo(const SkPaint* paint, const mat4& transform) : 92 style(paint->getStyle()), cap(paint->getStrokeCap()), isAA(paint->isAntiAlias()), 93 inverseScaleX(1.0f), inverseScaleY(1.0f), 94 halfStrokeWidth(paint->getStrokeWidth() * 0.5f), maxAlpha(1.0f) { 95 // compute inverse scales 96 if (CC_UNLIKELY(!transform.isPureTranslate())) { 97 float m00 = transform.data[Matrix4::kScaleX]; 98 float m01 = transform.data[Matrix4::kSkewY]; 99 float m10 = transform.data[Matrix4::kSkewX]; 100 float m11 = transform.data[Matrix4::kScaleY]; 101 float scaleX = sqrt(m00 * m00 + m01 * m01); 102 float scaleY = sqrt(m10 * m10 + m11 * m11); 103 inverseScaleX = (scaleX != 0) ? (1.0f / scaleX) : 1.0f; 104 inverseScaleY = (scaleY != 0) ? (1.0f / scaleY) : 1.0f; 105 } 106 107 if (isAA && halfStrokeWidth != 0 && inverseScaleX == inverseScaleY && 108 2 * halfStrokeWidth < inverseScaleX) { 109 maxAlpha *= (2 * halfStrokeWidth) / inverseScaleX; 110 halfStrokeWidth = 0.0f; 111 } 112 } 113 114 SkPaint::Style style; 115 SkPaint::Cap cap; 116 bool isAA; 117 float inverseScaleX; 118 float inverseScaleY; 119 float halfStrokeWidth; 120 float maxAlpha; 121 122 inline void scaleOffsetForStrokeWidth(vec2& offset) const { 123 if (halfStrokeWidth == 0.0f) { 124 // hairline - compensate for scale 125 offset.x *= 0.5f * inverseScaleX; 126 offset.y *= 0.5f * inverseScaleY; 127 } else { 128 offset *= halfStrokeWidth; 129 } 130 } 131 132 /** 133 * NOTE: the input will not always be a normal, especially for sharp edges - it should be the 134 * result of totalOffsetFromNormals (see documentation there) 135 */ 136 inline vec2 deriveAAOffset(const vec2& offset) const { 137 return vec2(offset.x * 0.5f * inverseScaleX, 138 offset.y * 0.5f * inverseScaleY); 139 } 140 141 /** 142 * Returns the number of cap divisions beyond the minimum 2 (kButt_Cap/kSquareCap will return 0) 143 * Should only be used when stroking and drawing caps 144 */ 145 inline int capExtraDivisions() const { 146 if (cap == SkPaint::kRound_Cap) { 147 if (halfStrokeWidth == 0.0f) return 2; 148 149 // ROUND_CAP_THRESH is the maximum error for polygonal approximation of the round cap 150 const float errConst = (-ROUND_CAP_THRESH / halfStrokeWidth + 1); 151 const float targetCosVal = 2 * errConst * errConst - 1; 152 int neededDivisions = (int)(ceilf(PI / acos(targetCosVal)/2)) * 2; 153 return neededDivisions; 154 } 155 return 0; 156 } 157 158 /** 159 * Outset the bounds of point data (for line endpoints or points) to account for AA stroke 160 * geometry. 161 */ 162 void expandBoundsForStrokeAA(SkRect& bounds) const { 163 float outset = halfStrokeWidth; 164 if (outset == 0) outset = 0.5f; 165 bounds.outset(outset * inverseScaleX + Vertex::GeometryFudgeFactor(), 166 outset * inverseScaleY + Vertex::GeometryFudgeFactor()); 167 } 168}; 169 170void getFillVerticesFromPerimeter(const Vector<Vertex>& perimeter, VertexBuffer& vertexBuffer) { 171 Vertex* buffer = vertexBuffer.alloc<Vertex>(perimeter.size()); 172 173 int currentIndex = 0; 174 // zig zag between all previous points on the inside of the hull to create a 175 // triangle strip that fills the hull 176 int srcAindex = 0; 177 int srcBindex = perimeter.size() - 1; 178 while (srcAindex <= srcBindex) { 179 buffer[currentIndex++] = perimeter[srcAindex]; 180 if (srcAindex == srcBindex) break; 181 buffer[currentIndex++] = perimeter[srcBindex]; 182 srcAindex++; 183 srcBindex--; 184 } 185} 186 187/* 188 * Fills a vertexBuffer with non-alpha vertices, zig-zagging at each perimeter point to create a 189 * tri-strip as wide as the stroke. 190 * 191 * Uses an additional 2 vertices at the end to wrap around, closing the tri-strip 192 * (for a total of perimeter.size() * 2 + 2 vertices) 193 */ 194void getStrokeVerticesFromPerimeter(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter, 195 VertexBuffer& vertexBuffer) { 196 Vertex* buffer = vertexBuffer.alloc<Vertex>(perimeter.size() * 2 + 2); 197 198 int currentIndex = 0; 199 const Vertex* last = &(perimeter[perimeter.size() - 1]); 200 const Vertex* current = &(perimeter[0]); 201 vec2 lastNormal(current->y - last->y, 202 last->x - current->x); 203 lastNormal.normalize(); 204 for (unsigned int i = 0; i < perimeter.size(); i++) { 205 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]); 206 vec2 nextNormal(next->y - current->y, 207 current->x - next->x); 208 nextNormal.normalize(); 209 210 vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal); 211 paintInfo.scaleOffsetForStrokeWidth(totalOffset); 212 213 Vertex::set(&buffer[currentIndex++], 214 current->x + totalOffset.x, 215 current->y + totalOffset.y); 216 217 Vertex::set(&buffer[currentIndex++], 218 current->x - totalOffset.x, 219 current->y - totalOffset.y); 220 221 last = current; 222 current = next; 223 lastNormal = nextNormal; 224 } 225 226 // wrap around to beginning 227 buffer[currentIndex++] = buffer[0]; 228 buffer[currentIndex++] = buffer[1]; 229 230 DEBUG_DUMP_BUFFER(); 231} 232 233static inline void storeBeginEnd(const PaintInfo& paintInfo, const Vertex& center, 234 const vec2& normal, Vertex* buffer, int& currentIndex, bool begin) { 235 vec2 strokeOffset = normal; 236 paintInfo.scaleOffsetForStrokeWidth(strokeOffset); 237 238 vec2 referencePoint(center.x, center.y); 239 if (paintInfo.cap == SkPaint::kSquare_Cap) { 240 referencePoint += vec2(-strokeOffset.y, strokeOffset.x) * (begin ? -1 : 1); 241 } 242 243 Vertex::set(&buffer[currentIndex++], referencePoint + strokeOffset); 244 Vertex::set(&buffer[currentIndex++], referencePoint - strokeOffset); 245} 246 247/** 248 * Fills a vertexBuffer with non-alpha vertices similar to getStrokeVerticesFromPerimeter, except: 249 * 250 * 1 - Doesn't need to wrap around, since the input vertices are unclosed 251 * 252 * 2 - can zig-zag across 'extra' vertices at either end, to create round caps 253 */ 254void getStrokeVerticesFromUnclosedVertices(const PaintInfo& paintInfo, 255 const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) { 256 const int extra = paintInfo.capExtraDivisions(); 257 const int allocSize = (vertices.size() + extra) * 2; 258 Vertex* buffer = vertexBuffer.alloc<Vertex>(allocSize); 259 260 const int lastIndex = vertices.size() - 1; 261 if (extra > 0) { 262 // tessellate both round caps 263 float beginTheta = atan2( 264 - (vertices[0].x - vertices[1].x), 265 vertices[0].y - vertices[1].y); 266 float endTheta = atan2( 267 - (vertices[lastIndex].x - vertices[lastIndex - 1].x), 268 vertices[lastIndex].y - vertices[lastIndex - 1].y); 269 const float dTheta = PI / (extra + 1); 270 const float radialScale = 2.0f / (1 + cos(dTheta)); 271 272 int capOffset; 273 for (int i = 0; i < extra; i++) { 274 if (i < extra / 2) { 275 capOffset = extra - 2 * i - 1; 276 } else { 277 capOffset = 2 * i - extra; 278 } 279 280 beginTheta += dTheta; 281 vec2 beginRadialOffset(cos(beginTheta), sin(beginTheta)); 282 paintInfo.scaleOffsetForStrokeWidth(beginRadialOffset); 283 Vertex::set(&buffer[capOffset], 284 vertices[0].x + beginRadialOffset.x, 285 vertices[0].y + beginRadialOffset.y); 286 287 endTheta += dTheta; 288 vec2 endRadialOffset(cos(endTheta), sin(endTheta)); 289 paintInfo.scaleOffsetForStrokeWidth(endRadialOffset); 290 Vertex::set(&buffer[allocSize - 1 - capOffset], 291 vertices[lastIndex].x + endRadialOffset.x, 292 vertices[lastIndex].y + endRadialOffset.y); 293 } 294 } 295 296 int currentIndex = extra; 297 const Vertex* last = &(vertices[0]); 298 const Vertex* current = &(vertices[1]); 299 vec2 lastNormal(current->y - last->y, 300 last->x - current->x); 301 lastNormal.normalize(); 302 303 storeBeginEnd(paintInfo, vertices[0], lastNormal, buffer, currentIndex, true); 304 305 for (unsigned int i = 1; i < vertices.size() - 1; i++) { 306 const Vertex* next = &(vertices[i + 1]); 307 vec2 nextNormal(next->y - current->y, 308 current->x - next->x); 309 nextNormal.normalize(); 310 311 vec2 strokeOffset = totalOffsetFromNormals(lastNormal, nextNormal); 312 paintInfo.scaleOffsetForStrokeWidth(strokeOffset); 313 314 vec2 center(current->x, current->y); 315 Vertex::set(&buffer[currentIndex++], center + strokeOffset); 316 Vertex::set(&buffer[currentIndex++], center - strokeOffset); 317 318 current = next; 319 lastNormal = nextNormal; 320 } 321 322 storeBeginEnd(paintInfo, vertices[lastIndex], lastNormal, buffer, currentIndex, false); 323 324 DEBUG_DUMP_BUFFER(); 325} 326 327/** 328 * Populates a vertexBuffer with AlphaVertices to create an anti-aliased fill shape tessellation 329 * 330 * 1 - create the AA perimeter of unit width, by zig-zagging at each point around the perimeter of 331 * the shape (using 2 * perimeter.size() vertices) 332 * 333 * 2 - wrap around to the beginning to complete the perimeter (2 vertices) 334 * 335 * 3 - zig zag back and forth inside the shape to fill it (using perimeter.size() vertices) 336 */ 337void getFillVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter, 338 VertexBuffer& vertexBuffer, float maxAlpha = 1.0f) { 339 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(perimeter.size() * 3 + 2); 340 341 // generate alpha points - fill Alpha vertex gaps in between each point with 342 // alpha 0 vertex, offset by a scaled normal. 343 int currentIndex = 0; 344 const Vertex* last = &(perimeter[perimeter.size() - 1]); 345 const Vertex* current = &(perimeter[0]); 346 vec2 lastNormal(current->y - last->y, 347 last->x - current->x); 348 lastNormal.normalize(); 349 for (unsigned int i = 0; i < perimeter.size(); i++) { 350 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]); 351 vec2 nextNormal(next->y - current->y, 352 current->x - next->x); 353 nextNormal.normalize(); 354 355 // AA point offset from original point is that point's normal, such that each side is offset 356 // by .5 pixels 357 vec2 totalOffset = paintInfo.deriveAAOffset(totalOffsetFromNormals(lastNormal, nextNormal)); 358 359 AlphaVertex::set(&buffer[currentIndex++], 360 current->x + totalOffset.x, 361 current->y + totalOffset.y, 362 0.0f); 363 AlphaVertex::set(&buffer[currentIndex++], 364 current->x - totalOffset.x, 365 current->y - totalOffset.y, 366 maxAlpha); 367 368 last = current; 369 current = next; 370 lastNormal = nextNormal; 371 } 372 373 // wrap around to beginning 374 buffer[currentIndex++] = buffer[0]; 375 buffer[currentIndex++] = buffer[1]; 376 377 // zig zag between all previous points on the inside of the hull to create a 378 // triangle strip that fills the hull, repeating the first inner point to 379 // create degenerate tris to start inside path 380 int srcAindex = 0; 381 int srcBindex = perimeter.size() - 1; 382 while (srcAindex <= srcBindex) { 383 buffer[currentIndex++] = buffer[srcAindex * 2 + 1]; 384 if (srcAindex == srcBindex) break; 385 buffer[currentIndex++] = buffer[srcBindex * 2 + 1]; 386 srcAindex++; 387 srcBindex--; 388 } 389 390 DEBUG_DUMP_BUFFER(); 391} 392 393/** 394 * Stores geometry for a single, AA-perimeter (potentially rounded) cap 395 * 396 * For explanation of constants and general methodoloyg, see comments for 397 * getStrokeVerticesFromUnclosedVerticesAA() below. 398 */ 399inline static void storeCapAA(const PaintInfo& paintInfo, const Vector<Vertex>& vertices, 400 AlphaVertex* buffer, bool isFirst, vec2 normal, int offset) { 401 const int extra = paintInfo.capExtraDivisions(); 402 const int extraOffset = (extra + 1) / 2; 403 const int capIndex = isFirst 404 ? 2 * offset + 6 + 2 * (extra + extraOffset) 405 : offset + 2 + 2 * extraOffset; 406 if (isFirst) normal *= -1; 407 408 // TODO: this normal should be scaled by radialScale if extra != 0, see totalOffsetFromNormals() 409 vec2 AAOffset = paintInfo.deriveAAOffset(normal); 410 411 vec2 strokeOffset = normal; 412 paintInfo.scaleOffsetForStrokeWidth(strokeOffset); 413 vec2 outerOffset = strokeOffset + AAOffset; 414 vec2 innerOffset = strokeOffset - AAOffset; 415 416 vec2 capAAOffset; 417 if (paintInfo.cap != SkPaint::kRound_Cap) { 418 // if the cap is square or butt, the inside primary cap vertices will be inset in two 419 // directions - both normal to the stroke, and parallel to it. 420 capAAOffset = vec2(-AAOffset.y, AAOffset.x); 421 } 422 423 // determine referencePoint, the center point for the 4 primary cap vertices 424 const Vertex* point = isFirst ? vertices.begin() : (vertices.end() - 1); 425 vec2 referencePoint(point->x, point->y); 426 if (paintInfo.cap == SkPaint::kSquare_Cap) { 427 // To account for square cap, move the primary cap vertices (that create the AA edge) by the 428 // stroke offset vector (rotated to be parallel to the stroke) 429 referencePoint += vec2(-strokeOffset.y, strokeOffset.x); 430 } 431 432 AlphaVertex::set(&buffer[capIndex + 0], 433 referencePoint.x + outerOffset.x + capAAOffset.x, 434 referencePoint.y + outerOffset.y + capAAOffset.y, 435 0.0f); 436 AlphaVertex::set(&buffer[capIndex + 1], 437 referencePoint.x + innerOffset.x - capAAOffset.x, 438 referencePoint.y + innerOffset.y - capAAOffset.y, 439 paintInfo.maxAlpha); 440 441 bool isRound = paintInfo.cap == SkPaint::kRound_Cap; 442 443 const int postCapIndex = (isRound && isFirst) ? (2 * extraOffset - 2) : capIndex + (2 * extra); 444 AlphaVertex::set(&buffer[postCapIndex + 2], 445 referencePoint.x - outerOffset.x + capAAOffset.x, 446 referencePoint.y - outerOffset.y + capAAOffset.y, 447 0.0f); 448 AlphaVertex::set(&buffer[postCapIndex + 3], 449 referencePoint.x - innerOffset.x - capAAOffset.x, 450 referencePoint.y - innerOffset.y - capAAOffset.y, 451 paintInfo.maxAlpha); 452 453 if (isRound) { 454 const float dTheta = PI / (extra + 1); 455 const float radialScale = 2.0f / (1 + cos(dTheta)); 456 float theta = atan2(normal.y, normal.x); 457 int capPerimIndex = capIndex + 2; 458 459 for (int i = 0; i < extra; i++) { 460 theta += dTheta; 461 462 vec2 radialOffset(cos(theta), sin(theta)); 463 464 // scale to compensate for pinching at sharp angles, see totalOffsetFromNormals() 465 radialOffset *= radialScale; 466 467 AAOffset = paintInfo.deriveAAOffset(radialOffset); 468 paintInfo.scaleOffsetForStrokeWidth(radialOffset); 469 AlphaVertex::set(&buffer[capPerimIndex++], 470 referencePoint.x + radialOffset.x + AAOffset.x, 471 referencePoint.y + radialOffset.y + AAOffset.y, 472 0.0f); 473 AlphaVertex::set(&buffer[capPerimIndex++], 474 referencePoint.x + radialOffset.x - AAOffset.x, 475 referencePoint.y + radialOffset.y - AAOffset.y, 476 paintInfo.maxAlpha); 477 478 if (isFirst && i == extra - extraOffset) { 479 //copy most recent two points to first two points 480 buffer[0] = buffer[capPerimIndex - 2]; 481 buffer[1] = buffer[capPerimIndex - 1]; 482 483 capPerimIndex = 2; // start writing the rest of the round cap at index 2 484 } 485 } 486 487 if (isFirst) { 488 const int startCapFillIndex = capIndex + 2 * (extra - extraOffset) + 4; 489 int capFillIndex = startCapFillIndex; 490 for (int i = 0; i < extra + 2; i += 2) { 491 buffer[capFillIndex++] = buffer[1 + i]; 492 // TODO: to support odd numbers of divisions, break here on the last iteration 493 buffer[capFillIndex++] = buffer[startCapFillIndex - 3 - i]; 494 } 495 } else { 496 int capFillIndex = 6 * vertices.size() + 2 + 6 * extra - (extra + 2); 497 for (int i = 0; i < extra + 2; i += 2) { 498 buffer[capFillIndex++] = buffer[capIndex + 1 + i]; 499 // TODO: to support odd numbers of divisions, break here on the last iteration 500 buffer[capFillIndex++] = buffer[capIndex + 3 + 2 * extra - i]; 501 } 502 } 503 return; 504 } 505 if (isFirst) { 506 buffer[0] = buffer[postCapIndex + 2]; 507 buffer[1] = buffer[postCapIndex + 3]; 508 buffer[postCapIndex + 4] = buffer[1]; // degenerate tris (the only two!) 509 buffer[postCapIndex + 5] = buffer[postCapIndex + 1]; 510 } else { 511 buffer[6 * vertices.size()] = buffer[postCapIndex + 1]; 512 buffer[6 * vertices.size() + 1] = buffer[postCapIndex + 3]; 513 } 514} 515 516/* 517the geometry for an aa, capped stroke consists of the following: 518 519 # vertices | function 520---------------------------------------------------------------------- 521a) 2 | Start AA perimeter 522b) 2, 2 * roundDivOff | First half of begin cap's perimeter 523 | 524 2 * middlePts | 'Outer' or 'Top' AA perimeter half (between caps) 525 | 526a) 4 | End cap's 527b) 2, 2 * roundDivs, 2 | AA perimeter 528 | 529 2 * middlePts | 'Inner' or 'bottom' AA perimeter half 530 | 531a) 6 | Begin cap's perimeter 532b) 2, 2*(rD - rDO + 1), | Last half of begin cap's perimeter 533 roundDivs, 2 | 534 | 535 2 * middlePts | Stroke's full opacity center strip 536 | 537a) 2 | end stroke 538b) 2, roundDivs | (and end cap fill, for round) 539 540Notes: 541* rows starting with 'a)' denote the Butt or Square cap vertex use, 'b)' denote Round 542 543* 'middlePts' is (number of points in the unclosed input vertex list, minus 2) times two 544 545* 'roundDivs' or 'rD' is the number of extra vertices (beyond the minimum of 2) that define the 546 round cap's shape, and is at least two. This will increase with cap size to sufficiently 547 define the cap's level of tessellation. 548 549* 'roundDivOffset' or 'rDO' is the point about halfway along the start cap's round perimeter, where 550 the stream of vertices for the AA perimeter starts. By starting and ending the perimeter at 551 this offset, the fill of the stroke is drawn from this point with minimal extra vertices. 552 553This means the outer perimeter starts at: 554 outerIndex = (2) OR (2 + 2 * roundDivOff) 555the inner perimeter (since it is filled in reverse) starts at: 556 innerIndex = outerIndex + (4 * middlePts) + ((4) OR (4 + 2 * roundDivs)) - 1 557the stroke starts at: 558 strokeIndex = innerIndex + 1 + ((6) OR (6 + 3 * roundDivs - 2 * roundDivOffset)) 559 560The total needed allocated space is either: 561 2 + 4 + 6 + 2 + 3 * (2 * middlePts) = 14 + 6 * middlePts = 2 + 6 * pts 562or, for rounded caps: 563 (2 + 2 * rDO) + (4 + 2 * rD) + (2 * (rD - rDO + 1) 564 + roundDivs + 4) + (2 + roundDivs) + 3 * (2 * middlePts) 565 = 14 + 6 * middlePts + 6 * roundDivs 566 = 2 + 6 * pts + 6 * roundDivs 567 */ 568void getStrokeVerticesFromUnclosedVerticesAA(const PaintInfo& paintInfo, 569 const Vector<Vertex>& vertices, VertexBuffer& vertexBuffer) { 570 571 const int extra = paintInfo.capExtraDivisions(); 572 const int allocSize = 6 * vertices.size() + 2 + 6 * extra; 573 574 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(allocSize); 575 576 const int extraOffset = (extra + 1) / 2; 577 int offset = 2 * (vertices.size() - 2); 578 // there is no outer/inner here, using them for consistency with below approach 579 int currentAAOuterIndex = 2 + 2 * extraOffset; 580 int currentAAInnerIndex = currentAAOuterIndex + (2 * offset) + 3 + (2 * extra); 581 int currentStrokeIndex = currentAAInnerIndex + 7 + (3 * extra - 2 * extraOffset); 582 583 const Vertex* last = &(vertices[0]); 584 const Vertex* current = &(vertices[1]); 585 vec2 lastNormal(current->y - last->y, 586 last->x - current->x); 587 lastNormal.normalize(); 588 589 // TODO: use normal from bezier traversal for cap, instead of from vertices 590 storeCapAA(paintInfo, vertices, buffer, true, lastNormal, offset); 591 592 for (unsigned int i = 1; i < vertices.size() - 1; i++) { 593 const Vertex* next = &(vertices[i + 1]); 594 vec2 nextNormal(next->y - current->y, 595 current->x - next->x); 596 nextNormal.normalize(); 597 598 vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal); 599 vec2 AAOffset = paintInfo.deriveAAOffset(totalOffset); 600 601 vec2 innerOffset = totalOffset; 602 paintInfo.scaleOffsetForStrokeWidth(innerOffset); 603 vec2 outerOffset = innerOffset + AAOffset; 604 innerOffset -= AAOffset; 605 606 AlphaVertex::set(&buffer[currentAAOuterIndex++], 607 current->x + outerOffset.x, 608 current->y + outerOffset.y, 609 0.0f); 610 AlphaVertex::set(&buffer[currentAAOuterIndex++], 611 current->x + innerOffset.x, 612 current->y + innerOffset.y, 613 paintInfo.maxAlpha); 614 615 AlphaVertex::set(&buffer[currentStrokeIndex++], 616 current->x + innerOffset.x, 617 current->y + innerOffset.y, 618 paintInfo.maxAlpha); 619 AlphaVertex::set(&buffer[currentStrokeIndex++], 620 current->x - innerOffset.x, 621 current->y - innerOffset.y, 622 paintInfo.maxAlpha); 623 624 AlphaVertex::set(&buffer[currentAAInnerIndex--], 625 current->x - innerOffset.x, 626 current->y - innerOffset.y, 627 paintInfo.maxAlpha); 628 AlphaVertex::set(&buffer[currentAAInnerIndex--], 629 current->x - outerOffset.x, 630 current->y - outerOffset.y, 631 0.0f); 632 633 current = next; 634 lastNormal = nextNormal; 635 } 636 637 // TODO: use normal from bezier traversal for cap, instead of from vertices 638 storeCapAA(paintInfo, vertices, buffer, false, lastNormal, offset); 639 640 DEBUG_DUMP_ALPHA_BUFFER(); 641} 642 643 644void getStrokeVerticesFromPerimeterAA(const PaintInfo& paintInfo, const Vector<Vertex>& perimeter, 645 VertexBuffer& vertexBuffer) { 646 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(6 * perimeter.size() + 8); 647 648 int offset = 2 * perimeter.size() + 3; 649 int currentAAOuterIndex = 0; 650 int currentStrokeIndex = offset; 651 int currentAAInnerIndex = offset * 2; 652 653 const Vertex* last = &(perimeter[perimeter.size() - 1]); 654 const Vertex* current = &(perimeter[0]); 655 vec2 lastNormal(current->y - last->y, 656 last->x - current->x); 657 lastNormal.normalize(); 658 for (unsigned int i = 0; i < perimeter.size(); i++) { 659 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]); 660 vec2 nextNormal(next->y - current->y, 661 current->x - next->x); 662 nextNormal.normalize(); 663 664 vec2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal); 665 vec2 AAOffset = paintInfo.deriveAAOffset(totalOffset); 666 667 vec2 innerOffset = totalOffset; 668 paintInfo.scaleOffsetForStrokeWidth(innerOffset); 669 vec2 outerOffset = innerOffset + AAOffset; 670 innerOffset -= AAOffset; 671 672 AlphaVertex::set(&buffer[currentAAOuterIndex++], 673 current->x + outerOffset.x, 674 current->y + outerOffset.y, 675 0.0f); 676 AlphaVertex::set(&buffer[currentAAOuterIndex++], 677 current->x + innerOffset.x, 678 current->y + innerOffset.y, 679 paintInfo.maxAlpha); 680 681 AlphaVertex::set(&buffer[currentStrokeIndex++], 682 current->x + innerOffset.x, 683 current->y + innerOffset.y, 684 paintInfo.maxAlpha); 685 AlphaVertex::set(&buffer[currentStrokeIndex++], 686 current->x - innerOffset.x, 687 current->y - innerOffset.y, 688 paintInfo.maxAlpha); 689 690 AlphaVertex::set(&buffer[currentAAInnerIndex++], 691 current->x - innerOffset.x, 692 current->y - innerOffset.y, 693 paintInfo.maxAlpha); 694 AlphaVertex::set(&buffer[currentAAInnerIndex++], 695 current->x - outerOffset.x, 696 current->y - outerOffset.y, 697 0.0f); 698 699 last = current; 700 current = next; 701 lastNormal = nextNormal; 702 } 703 704 // wrap each strip around to beginning, creating degenerate tris to bridge strips 705 buffer[currentAAOuterIndex++] = buffer[0]; 706 buffer[currentAAOuterIndex++] = buffer[1]; 707 buffer[currentAAOuterIndex++] = buffer[1]; 708 709 buffer[currentStrokeIndex++] = buffer[offset]; 710 buffer[currentStrokeIndex++] = buffer[offset + 1]; 711 buffer[currentStrokeIndex++] = buffer[offset + 1]; 712 713 buffer[currentAAInnerIndex++] = buffer[2 * offset]; 714 buffer[currentAAInnerIndex++] = buffer[2 * offset + 1]; 715 // don't need to create last degenerate tri 716 717 DEBUG_DUMP_ALPHA_BUFFER(); 718} 719 720void PathTessellator::tessellatePath(const SkPath &path, const SkPaint* paint, 721 const mat4& transform, VertexBuffer& vertexBuffer) { 722 ATRACE_CALL(); 723 724 const PaintInfo paintInfo(paint, transform); 725 726 Vector<Vertex> tempVertices; 727 float threshInvScaleX = paintInfo.inverseScaleX; 728 float threshInvScaleY = paintInfo.inverseScaleY; 729 if (paintInfo.style == SkPaint::kStroke_Style) { 730 // alter the bezier recursion threshold values we calculate in order to compensate for 731 // expansion done after the path vertices are found 732 SkRect bounds = path.getBounds(); 733 if (!bounds.isEmpty()) { 734 threshInvScaleX *= bounds.width() / (bounds.width() + paint->getStrokeWidth()); 735 threshInvScaleY *= bounds.height() / (bounds.height() + paint->getStrokeWidth()); 736 } 737 } 738 739 // force close if we're filling the path, since fill path expects closed perimeter. 740 bool forceClose = paintInfo.style != SkPaint::kStroke_Style; 741 bool wasClosed = approximatePathOutlineVertices(path, forceClose, 742 threshInvScaleX * threshInvScaleX, threshInvScaleY * threshInvScaleY, 743 OUTLINE_REFINE_THRESHOLD_SQUARED, tempVertices); 744 745 if (!tempVertices.size()) { 746 // path was empty, return without allocating vertex buffer 747 return; 748 } 749 750#if VERTEX_DEBUG 751 for (unsigned int i = 0; i < tempVertices.size(); i++) { 752 ALOGD("orig path: point at %f %f", 753 tempVertices[i].x, tempVertices[i].y); 754 } 755#endif 756 757 if (paintInfo.style == SkPaint::kStroke_Style) { 758 if (!paintInfo.isAA) { 759 if (wasClosed) { 760 getStrokeVerticesFromPerimeter(paintInfo, tempVertices, vertexBuffer); 761 } else { 762 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer); 763 } 764 765 } else { 766 if (wasClosed) { 767 getStrokeVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer); 768 } else { 769 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer); 770 } 771 } 772 } else { 773 // For kStrokeAndFill style, the path should be adjusted externally. 774 // It will be treated as a fill here. 775 if (!paintInfo.isAA) { 776 getFillVerticesFromPerimeter(tempVertices, vertexBuffer); 777 } else { 778 getFillVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer); 779 } 780 } 781} 782 783static void expandRectToCoverVertex(SkRect& rect, float x, float y) { 784 rect.fLeft = fminf(rect.fLeft, x); 785 rect.fTop = fminf(rect.fTop, y); 786 rect.fRight = fmaxf(rect.fRight, x); 787 rect.fBottom = fmaxf(rect.fBottom, y); 788} 789static void expandRectToCoverVertex(SkRect& rect, const Vertex& vertex) { 790 expandRectToCoverVertex(rect, vertex.x, vertex.y); 791} 792 793template <class TYPE> 794static void instanceVertices(VertexBuffer& srcBuffer, VertexBuffer& dstBuffer, 795 const float* points, int count, SkRect& bounds) { 796 bounds.set(points[0], points[1], points[0], points[1]); 797 798 int numPoints = count / 2; 799 int verticesPerPoint = srcBuffer.getVertexCount(); 800 dstBuffer.alloc<TYPE>(numPoints * verticesPerPoint + (numPoints - 1) * 2); 801 802 for (int i = 0; i < count; i += 2) { 803 expandRectToCoverVertex(bounds, points[i + 0], points[i + 1]); 804 dstBuffer.copyInto<TYPE>(srcBuffer, points[i + 0], points[i + 1]); 805 } 806 dstBuffer.createDegenerateSeparators<TYPE>(verticesPerPoint); 807} 808 809void PathTessellator::tessellatePoints(const float* points, int count, const SkPaint* paint, 810 const mat4& transform, SkRect& bounds, VertexBuffer& vertexBuffer) { 811 const PaintInfo paintInfo(paint, transform); 812 813 // determine point shape 814 SkPath path; 815 float radius = paintInfo.halfStrokeWidth; 816 if (radius == 0.0f) radius = 0.25f; 817 818 if (paintInfo.cap == SkPaint::kRound_Cap) { 819 path.addCircle(0, 0, radius); 820 } else { 821 path.addRect(-radius, -radius, radius, radius); 822 } 823 824 // calculate outline 825 Vector<Vertex> outlineVertices; 826 approximatePathOutlineVertices(path, true, 827 paintInfo.inverseScaleX * paintInfo.inverseScaleX, 828 paintInfo.inverseScaleY * paintInfo.inverseScaleY, 829 OUTLINE_REFINE_THRESHOLD_SQUARED, outlineVertices); 830 831 if (!outlineVertices.size()) return; 832 833 // tessellate, then duplicate outline across points 834 int numPoints = count / 2; 835 VertexBuffer tempBuffer; 836 if (!paintInfo.isAA) { 837 getFillVerticesFromPerimeter(outlineVertices, tempBuffer); 838 instanceVertices<Vertex>(tempBuffer, vertexBuffer, points, count, bounds); 839 } else { 840 // note: pass maxAlpha directly, since we want fill to be alpha modulated 841 getFillVerticesFromPerimeterAA(paintInfo, outlineVertices, tempBuffer, paintInfo.maxAlpha); 842 instanceVertices<AlphaVertex>(tempBuffer, vertexBuffer, points, count, bounds); 843 } 844 845 // expand bounds from vertex coords to pixel data 846 paintInfo.expandBoundsForStrokeAA(bounds); 847 848} 849 850void PathTessellator::tessellateLines(const float* points, int count, const SkPaint* paint, 851 const mat4& transform, SkRect& bounds, VertexBuffer& vertexBuffer) { 852 ATRACE_CALL(); 853 const PaintInfo paintInfo(paint, transform); 854 855 const int extra = paintInfo.capExtraDivisions(); 856 int numLines = count / 4; 857 int lineAllocSize; 858 // pre-allocate space for lines in the buffer, and degenerate tris in between 859 if (paintInfo.isAA) { 860 lineAllocSize = 6 * (2) + 2 + 6 * extra; 861 vertexBuffer.alloc<AlphaVertex>(numLines * lineAllocSize + (numLines - 1) * 2); 862 } else { 863 lineAllocSize = 2 * ((2) + extra); 864 vertexBuffer.alloc<Vertex>(numLines * lineAllocSize + (numLines - 1) * 2); 865 } 866 867 Vector<Vertex> tempVertices; 868 tempVertices.push(); 869 tempVertices.push(); 870 Vertex* tempVerticesData = tempVertices.editArray(); 871 bounds.set(points[0], points[1], points[0], points[1]); 872 for (int i = 0; i < count; i += 4) { 873 Vertex::set(&(tempVerticesData[0]), points[i + 0], points[i + 1]); 874 Vertex::set(&(tempVerticesData[1]), points[i + 2], points[i + 3]); 875 876 if (paintInfo.isAA) { 877 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer); 878 } else { 879 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer); 880 } 881 882 // calculate bounds 883 expandRectToCoverVertex(bounds, tempVerticesData[0]); 884 expandRectToCoverVertex(bounds, tempVerticesData[1]); 885 } 886 887 // since multiple objects tessellated into buffer, separate them with degen tris 888 if (paintInfo.isAA) { 889 vertexBuffer.createDegenerateSeparators<AlphaVertex>(lineAllocSize); 890 } else { 891 vertexBuffer.createDegenerateSeparators<Vertex>(lineAllocSize); 892 } 893 894 // expand bounds from vertex coords to pixel data 895 paintInfo.expandBoundsForStrokeAA(bounds); 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) { 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 985 if (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); 1010 recursiveCubicBezierVertices( 1011 mx, my, p2c1c2x, p2c1c2y, 1012 p2x, p2y, p2c2x, p2c2y, 1013 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices); 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) { 1023 float dx = bx - ax; 1024 float dy = by - ay; 1025 float d = (cx - bx) * dy - (cy - by) * dx; 1026 1027 if (d * d < thresholdSquared * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) { 1028 // below thresh, draw line by adding endpoint 1029 pushToVector(outputVertices, bx, by); 1030 } else { 1031 float acx = (ax + cx) * 0.5f; 1032 float bcx = (bx + cx) * 0.5f; 1033 float acy = (ay + cy) * 0.5f; 1034 float bcy = (by + cy) * 0.5f; 1035 1036 // midpoint 1037 float mx = (acx + bcx) * 0.5f; 1038 float my = (acy + bcy) * 0.5f; 1039 1040 recursiveQuadraticBezierVertices(ax, ay, mx, my, acx, acy, 1041 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices); 1042 recursiveQuadraticBezierVertices(mx, my, bx, by, bcx, bcy, 1043 sqrInvScaleX, sqrInvScaleY, thresholdSquared, outputVertices); 1044 } 1045} 1046 1047}; // namespace uirenderer 1048}; // namespace android 1049