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