PathTessellator.cpp revision 564acf7c9bff822f608cda0d5df0a64a9f9aaefd
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 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, tempVertices); 743 744 if (!tempVertices.size()) { 745 // path was empty, return without allocating vertex buffer 746 return; 747 } 748 749#if VERTEX_DEBUG 750 for (unsigned int i = 0; i < tempVertices.size(); i++) { 751 ALOGD("orig path: point at %f %f", 752 tempVertices[i].x, tempVertices[i].y); 753 } 754#endif 755 756 if (paintInfo.style == SkPaint::kStroke_Style) { 757 if (!paintInfo.isAA) { 758 if (wasClosed) { 759 getStrokeVerticesFromPerimeter(paintInfo, tempVertices, vertexBuffer); 760 } else { 761 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer); 762 } 763 764 } else { 765 if (wasClosed) { 766 getStrokeVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer); 767 } else { 768 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer); 769 } 770 } 771 } else { 772 // For kStrokeAndFill style, the path should be adjusted externally. 773 // It will be treated as a fill here. 774 if (!paintInfo.isAA) { 775 getFillVerticesFromPerimeter(tempVertices, vertexBuffer); 776 } else { 777 getFillVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer); 778 } 779 } 780} 781 782static void expandRectToCoverVertex(SkRect& rect, float x, float y) { 783 rect.fLeft = fminf(rect.fLeft, x); 784 rect.fTop = fminf(rect.fTop, y); 785 rect.fRight = fmaxf(rect.fRight, x); 786 rect.fBottom = fmaxf(rect.fBottom, y); 787} 788static void expandRectToCoverVertex(SkRect& rect, const Vertex& vertex) { 789 expandRectToCoverVertex(rect, vertex.x, vertex.y); 790} 791 792template <class TYPE> 793static void instanceVertices(VertexBuffer& srcBuffer, VertexBuffer& dstBuffer, 794 const float* points, int count, SkRect& bounds) { 795 bounds.set(points[0], points[1], points[0], points[1]); 796 797 int numPoints = count / 2; 798 int verticesPerPoint = srcBuffer.getVertexCount(); 799 dstBuffer.alloc<TYPE>(numPoints * verticesPerPoint + (numPoints - 1) * 2); 800 801 for (int i = 0; i < count; i += 2) { 802 expandRectToCoverVertex(bounds, points[i + 0], points[i + 1]); 803 dstBuffer.copyInto<TYPE>(srcBuffer, points[i + 0], points[i + 1]); 804 } 805 dstBuffer.createDegenerateSeparators<TYPE>(verticesPerPoint); 806} 807 808void PathTessellator::tessellatePoints(const float* points, int count, SkPaint* paint, 809 const mat4& transform, SkRect& bounds, VertexBuffer& vertexBuffer) { 810 const PaintInfo paintInfo(paint, transform); 811 812 // determine point shape 813 SkPath path; 814 float radius = paintInfo.halfStrokeWidth; 815 if (radius == 0.0f) radius = 0.25f; 816 817 if (paintInfo.cap == SkPaint::kRound_Cap) { 818 path.addCircle(0, 0, radius); 819 } else { 820 path.addRect(-radius, -radius, radius, radius); 821 } 822 823 // calculate outline 824 Vector<Vertex> outlineVertices; 825 approximatePathOutlineVertices(path, true, 826 paintInfo.inverseScaleX * paintInfo.inverseScaleX, 827 paintInfo.inverseScaleY * paintInfo.inverseScaleY, outlineVertices); 828 829 if (!outlineVertices.size()) return; 830 831 // tessellate, then duplicate outline across points 832 int numPoints = count / 2; 833 VertexBuffer tempBuffer; 834 if (!paintInfo.isAA) { 835 getFillVerticesFromPerimeter(outlineVertices, tempBuffer); 836 instanceVertices<Vertex>(tempBuffer, vertexBuffer, points, count, bounds); 837 } else { 838 // note: pass maxAlpha directly, since we want fill to be alpha modulated 839 getFillVerticesFromPerimeterAA(paintInfo, outlineVertices, tempBuffer, paintInfo.maxAlpha); 840 instanceVertices<AlphaVertex>(tempBuffer, vertexBuffer, points, count, bounds); 841 } 842 843 // expand bounds from vertex coords to pixel data 844 paintInfo.expandBoundsForStrokeAA(bounds); 845 846} 847 848void PathTessellator::tessellateLines(const float* points, int count, SkPaint* paint, 849 const mat4& transform, SkRect& bounds, VertexBuffer& vertexBuffer) { 850 ATRACE_CALL(); 851 const PaintInfo paintInfo(paint, transform); 852 853 const int extra = paintInfo.capExtraDivisions(); 854 int numLines = count / 4; 855 int lineAllocSize; 856 // pre-allocate space for lines in the buffer, and degenerate tris in between 857 if (paintInfo.isAA) { 858 lineAllocSize = 6 * (2) + 2 + 6 * extra; 859 vertexBuffer.alloc<AlphaVertex>(numLines * lineAllocSize + (numLines - 1) * 2); 860 } else { 861 lineAllocSize = 2 * ((2) + extra); 862 vertexBuffer.alloc<Vertex>(numLines * lineAllocSize + (numLines - 1) * 2); 863 } 864 865 Vector<Vertex> tempVertices; 866 tempVertices.push(); 867 tempVertices.push(); 868 Vertex* tempVerticesData = tempVertices.editArray(); 869 bounds.set(points[0], points[1], points[0], points[1]); 870 for (int i = 0; i < count; i += 4) { 871 Vertex::set(&(tempVerticesData[0]), points[i + 0], points[i + 1]); 872 Vertex::set(&(tempVerticesData[1]), points[i + 2], points[i + 3]); 873 874 if (paintInfo.isAA) { 875 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer); 876 } else { 877 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer); 878 } 879 880 // calculate bounds 881 expandRectToCoverVertex(bounds, tempVerticesData[0]); 882 expandRectToCoverVertex(bounds, tempVerticesData[1]); 883 } 884 885 // since multiple objects tessellated into buffer, separate them with degen tris 886 if (paintInfo.isAA) { 887 vertexBuffer.createDegenerateSeparators<AlphaVertex>(lineAllocSize); 888 } else { 889 vertexBuffer.createDegenerateSeparators<Vertex>(lineAllocSize); 890 } 891 892 // expand bounds from vertex coords to pixel data 893 paintInfo.expandBoundsForStrokeAA(bounds); 894} 895 896/////////////////////////////////////////////////////////////////////////////// 897// Simple path line approximation 898/////////////////////////////////////////////////////////////////////////////// 899 900void pushToVector(Vector<Vertex>& vertices, float x, float y) { 901 // TODO: make this not yuck 902 vertices.push(); 903 Vertex* newVertex = &(vertices.editArray()[vertices.size() - 1]); 904 Vertex::set(newVertex, x, y); 905} 906 907bool PathTessellator::approximatePathOutlineVertices(const SkPath& path, bool forceClose, 908 float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) { 909 ATRACE_CALL(); 910 911 // TODO: to support joins other than sharp miter, join vertices should be labelled in the 912 // perimeter, or resolved into more vertices. Reconsider forceClose-ing in that case. 913 SkPath::Iter iter(path, forceClose); 914 SkPoint pts[4]; 915 SkPath::Verb v; 916 while (SkPath::kDone_Verb != (v = iter.next(pts))) { 917 switch (v) { 918 case SkPath::kMove_Verb: 919 pushToVector(outputVertices, pts[0].x(), pts[0].y()); 920 ALOGV("Move to pos %f %f", pts[0].x(), pts[0].y()); 921 break; 922 case SkPath::kClose_Verb: 923 ALOGV("Close at pos %f %f", pts[0].x(), pts[0].y()); 924 break; 925 case SkPath::kLine_Verb: 926 ALOGV("kLine_Verb %f %f -> %f %f", pts[0].x(), pts[0].y(), pts[1].x(), pts[1].y()); 927 pushToVector(outputVertices, pts[1].x(), pts[1].y()); 928 break; 929 case SkPath::kQuad_Verb: 930 ALOGV("kQuad_Verb"); 931 recursiveQuadraticBezierVertices( 932 pts[0].x(), pts[0].y(), 933 pts[2].x(), pts[2].y(), 934 pts[1].x(), pts[1].y(), 935 sqrInvScaleX, sqrInvScaleY, outputVertices); 936 break; 937 case SkPath::kCubic_Verb: 938 ALOGV("kCubic_Verb"); 939 recursiveCubicBezierVertices( 940 pts[0].x(), pts[0].y(), 941 pts[1].x(), pts[1].y(), 942 pts[3].x(), pts[3].y(), 943 pts[2].x(), pts[2].y(), 944 sqrInvScaleX, sqrInvScaleY, outputVertices); 945 break; 946 default: 947 break; 948 } 949 } 950 951 int size = outputVertices.size(); 952 if (size >= 2 && outputVertices[0].x == outputVertices[size - 1].x && 953 outputVertices[0].y == outputVertices[size - 1].y) { 954 outputVertices.pop(); 955 return true; 956 } 957 return false; 958} 959 960/////////////////////////////////////////////////////////////////////////////// 961// Bezier approximation 962/////////////////////////////////////////////////////////////////////////////// 963 964void PathTessellator::recursiveCubicBezierVertices( 965 float p1x, float p1y, float c1x, float c1y, 966 float p2x, float p2y, float c2x, float c2y, 967 float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) { 968 float dx = p2x - p1x; 969 float dy = p2y - p1y; 970 float d1 = fabs((c1x - p2x) * dy - (c1y - p2y) * dx); 971 float d2 = fabs((c2x - p2x) * dy - (c2y - p2y) * dx); 972 float d = d1 + d2; 973 974 // multiplying by sqrInvScaleY/X equivalent to multiplying in dimensional scale factors 975 976 if (d * d < THRESHOLD * THRESHOLD * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) { 977 // below thresh, draw line by adding endpoint 978 pushToVector(outputVertices, p2x, p2y); 979 } else { 980 float p1c1x = (p1x + c1x) * 0.5f; 981 float p1c1y = (p1y + c1y) * 0.5f; 982 float p2c2x = (p2x + c2x) * 0.5f; 983 float p2c2y = (p2y + c2y) * 0.5f; 984 985 float c1c2x = (c1x + c2x) * 0.5f; 986 float c1c2y = (c1y + c2y) * 0.5f; 987 988 float p1c1c2x = (p1c1x + c1c2x) * 0.5f; 989 float p1c1c2y = (p1c1y + c1c2y) * 0.5f; 990 991 float p2c1c2x = (p2c2x + c1c2x) * 0.5f; 992 float p2c1c2y = (p2c2y + c1c2y) * 0.5f; 993 994 float mx = (p1c1c2x + p2c1c2x) * 0.5f; 995 float my = (p1c1c2y + p2c1c2y) * 0.5f; 996 997 recursiveCubicBezierVertices( 998 p1x, p1y, p1c1x, p1c1y, 999 mx, my, p1c1c2x, p1c1c2y, 1000 sqrInvScaleX, sqrInvScaleY, outputVertices); 1001 recursiveCubicBezierVertices( 1002 mx, my, p2c1c2x, p2c1c2y, 1003 p2x, p2y, p2c2x, p2c2y, 1004 sqrInvScaleX, sqrInvScaleY, outputVertices); 1005 } 1006} 1007 1008void PathTessellator::recursiveQuadraticBezierVertices( 1009 float ax, float ay, 1010 float bx, float by, 1011 float cx, float cy, 1012 float sqrInvScaleX, float sqrInvScaleY, Vector<Vertex>& outputVertices) { 1013 float dx = bx - ax; 1014 float dy = by - ay; 1015 float d = (cx - bx) * dy - (cy - by) * dx; 1016 1017 if (d * d < THRESHOLD * THRESHOLD * (dx * dx * sqrInvScaleY + dy * dy * sqrInvScaleX)) { 1018 // below thresh, draw line by adding endpoint 1019 pushToVector(outputVertices, bx, by); 1020 } else { 1021 float acx = (ax + cx) * 0.5f; 1022 float bcx = (bx + cx) * 0.5f; 1023 float acy = (ay + cy) * 0.5f; 1024 float bcy = (by + cy) * 0.5f; 1025 1026 // midpoint 1027 float mx = (acx + bcx) * 0.5f; 1028 float my = (acy + bcy) * 0.5f; 1029 1030 recursiveQuadraticBezierVertices(ax, ay, mx, my, acx, acy, 1031 sqrInvScaleX, sqrInvScaleY, outputVertices); 1032 recursiveQuadraticBezierVertices(mx, my, bx, by, bcx, bcy, 1033 sqrInvScaleX, sqrInvScaleY, outputVertices); 1034 } 1035} 1036 1037}; // namespace uirenderer 1038}; // namespace android 1039