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