1 /* 2 * Copyright (C) 2014 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 19 // The highest z value can't be higher than (CASTER_Z_CAP_RATIO * light.z) 20 #define CASTER_Z_CAP_RATIO 0.95f 21 22 // When there is no umbra, then just fake the umbra using 23 // centroid * (1 - FAKE_UMBRA_SIZE_RATIO) + outline * FAKE_UMBRA_SIZE_RATIO 24 #define FAKE_UMBRA_SIZE_RATIO 0.05f 25 26 // When the polygon is about 90 vertices, the penumbra + umbra can reach 270 rays. 27 // That is consider pretty fine tessllated polygon so far. 28 // This is just to prevent using too much some memory when edge slicing is not 29 // needed any more. 30 #define FINE_TESSELLATED_POLYGON_RAY_NUMBER 270 31 /** 32 * Extra vertices for the corner for smoother corner. 33 * Only for outer loop. 34 * Note that we use such extra memory to avoid an extra loop. 35 */ 36 // For half circle, we could add EXTRA_VERTEX_PER_PI vertices. 37 // Set to 1 if we don't want to have any. 38 #define SPOT_EXTRA_CORNER_VERTEX_PER_PI 18 39 40 // For the whole polygon, the sum of all the deltas b/t normals is 2 * M_PI, 41 // therefore, the maximum number of extra vertices will be twice bigger. 42 #define SPOT_MAX_EXTRA_CORNER_VERTEX_NUMBER (2 * SPOT_EXTRA_CORNER_VERTEX_PER_PI) 43 44 // For each RADIANS_DIVISOR, we would allocate one more vertex b/t the normals. 45 #define SPOT_CORNER_RADIANS_DIVISOR (M_PI / SPOT_EXTRA_CORNER_VERTEX_PER_PI) 46 47 48 #include <math.h> 49 #include <stdlib.h> 50 #include <utils/Log.h> 51 52 #include "ShadowTessellator.h" 53 #include "SpotShadow.h" 54 #include "Vertex.h" 55 #include "utils/MathUtils.h" 56 57 // TODO: After we settle down the new algorithm, we can remove the old one and 58 // its utility functions. 59 // Right now, we still need to keep it for comparison purpose and future expansion. 60 namespace android { 61 namespace uirenderer { 62 63 static const double EPSILON = 1e-7; 64 65 /** 66 * For each polygon's vertex, the light center will project it to the receiver 67 * as one of the outline vertex. 68 * For each outline vertex, we need to store the position and normal. 69 * Normal here is defined against the edge by the current vertex and the next vertex. 70 */ 71 struct OutlineData { 72 Vector2 position; 73 Vector2 normal; 74 float radius; 75 }; 76 77 /** 78 * For each vertex, we need to keep track of its angle, whether it is penumbra or 79 * umbra, and its corresponding vertex index. 80 */ 81 struct SpotShadow::VertexAngleData { 82 // The angle to the vertex from the centroid. 83 float mAngle; 84 // True is the vertex comes from penumbra, otherwise it comes from umbra. 85 bool mIsPenumbra; 86 // The index of the vertex described by this data. 87 int mVertexIndex; 88 void set(float angle, bool isPenumbra, int index) { 89 mAngle = angle; 90 mIsPenumbra = isPenumbra; 91 mVertexIndex = index; 92 } 93 }; 94 95 /** 96 * Calculate the angle between and x and a y coordinate. 97 * The atan2 range from -PI to PI. 98 */ 99 static float angle(const Vector2& point, const Vector2& center) { 100 return atan2(point.y - center.y, point.x - center.x); 101 } 102 103 /** 104 * Calculate the intersection of a ray with the line segment defined by two points. 105 * 106 * Returns a negative value in error conditions. 107 108 * @param rayOrigin The start of the ray 109 * @param dx The x vector of the ray 110 * @param dy The y vector of the ray 111 * @param p1 The first point defining the line segment 112 * @param p2 The second point defining the line segment 113 * @return The distance along the ray if it intersects with the line segment, negative if otherwise 114 */ 115 static float rayIntersectPoints(const Vector2& rayOrigin, float dx, float dy, 116 const Vector2& p1, const Vector2& p2) { 117 // The math below is derived from solving this formula, basically the 118 // intersection point should stay on both the ray and the edge of (p1, p2). 119 // solve([p1x+t*(p2x-p1x)=dx*t2+px,p1y+t*(p2y-p1y)=dy*t2+py],[t,t2]); 120 121 double divisor = (dx * (p1.y - p2.y) + dy * p2.x - dy * p1.x); 122 if (divisor == 0) return -1.0f; // error, invalid divisor 123 124 #if DEBUG_SHADOW 125 double interpVal = (dx * (p1.y - rayOrigin.y) + dy * rayOrigin.x - dy * p1.x) / divisor; 126 if (interpVal < 0 || interpVal > 1) { 127 ALOGW("rayIntersectPoints is hitting outside the segment %f", interpVal); 128 } 129 #endif 130 131 double distance = (p1.x * (rayOrigin.y - p2.y) + p2.x * (p1.y - rayOrigin.y) + 132 rayOrigin.x * (p2.y - p1.y)) / divisor; 133 134 return distance; // may be negative in error cases 135 } 136 137 /** 138 * Sort points by their X coordinates 139 * 140 * @param points the points as a Vector2 array. 141 * @param pointsLength the number of vertices of the polygon. 142 */ 143 void SpotShadow::xsort(Vector2* points, int pointsLength) { 144 quicksortX(points, 0, pointsLength - 1); 145 } 146 147 /** 148 * compute the convex hull of a collection of Points 149 * 150 * @param points the points as a Vector2 array. 151 * @param pointsLength the number of vertices of the polygon. 152 * @param retPoly pre allocated array of floats to put the vertices 153 * @return the number of points in the polygon 0 if no intersection 154 */ 155 int SpotShadow::hull(Vector2* points, int pointsLength, Vector2* retPoly) { 156 xsort(points, pointsLength); 157 int n = pointsLength; 158 Vector2 lUpper[n]; 159 lUpper[0] = points[0]; 160 lUpper[1] = points[1]; 161 162 int lUpperSize = 2; 163 164 for (int i = 2; i < n; i++) { 165 lUpper[lUpperSize] = points[i]; 166 lUpperSize++; 167 168 while (lUpperSize > 2 && !ccw( 169 lUpper[lUpperSize - 3].x, lUpper[lUpperSize - 3].y, 170 lUpper[lUpperSize - 2].x, lUpper[lUpperSize - 2].y, 171 lUpper[lUpperSize - 1].x, lUpper[lUpperSize - 1].y)) { 172 // Remove the middle point of the three last 173 lUpper[lUpperSize - 2].x = lUpper[lUpperSize - 1].x; 174 lUpper[lUpperSize - 2].y = lUpper[lUpperSize - 1].y; 175 lUpperSize--; 176 } 177 } 178 179 Vector2 lLower[n]; 180 lLower[0] = points[n - 1]; 181 lLower[1] = points[n - 2]; 182 183 int lLowerSize = 2; 184 185 for (int i = n - 3; i >= 0; i--) { 186 lLower[lLowerSize] = points[i]; 187 lLowerSize++; 188 189 while (lLowerSize > 2 && !ccw( 190 lLower[lLowerSize - 3].x, lLower[lLowerSize - 3].y, 191 lLower[lLowerSize - 2].x, lLower[lLowerSize - 2].y, 192 lLower[lLowerSize - 1].x, lLower[lLowerSize - 1].y)) { 193 // Remove the middle point of the three last 194 lLower[lLowerSize - 2] = lLower[lLowerSize - 1]; 195 lLowerSize--; 196 } 197 } 198 199 // output points in CW ordering 200 const int total = lUpperSize + lLowerSize - 2; 201 int outIndex = total - 1; 202 for (int i = 0; i < lUpperSize; i++) { 203 retPoly[outIndex] = lUpper[i]; 204 outIndex--; 205 } 206 207 for (int i = 1; i < lLowerSize - 1; i++) { 208 retPoly[outIndex] = lLower[i]; 209 outIndex--; 210 } 211 // TODO: Add test harness which verify that all the points are inside the hull. 212 return total; 213 } 214 215 /** 216 * Test whether the 3 points form a counter clockwise turn. 217 * 218 * @return true if a right hand turn 219 */ 220 bool SpotShadow::ccw(double ax, double ay, double bx, double by, 221 double cx, double cy) { 222 return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) > EPSILON; 223 } 224 225 /** 226 * Calculates the intersection of poly1 with poly2 and put in poly2. 227 * Note that both poly1 and poly2 must be in CW order already! 228 * 229 * @param poly1 The 1st polygon, as a Vector2 array. 230 * @param poly1Length The number of vertices of 1st polygon. 231 * @param poly2 The 2nd and output polygon, as a Vector2 array. 232 * @param poly2Length The number of vertices of 2nd polygon. 233 * @return number of vertices in output polygon as poly2. 234 */ 235 int SpotShadow::intersection(const Vector2* poly1, int poly1Length, 236 Vector2* poly2, int poly2Length) { 237 #if DEBUG_SHADOW 238 if (!ShadowTessellator::isClockwise(poly1, poly1Length)) { 239 ALOGW("Poly1 is not clockwise! Intersection is wrong!"); 240 } 241 if (!ShadowTessellator::isClockwise(poly2, poly2Length)) { 242 ALOGW("Poly2 is not clockwise! Intersection is wrong!"); 243 } 244 #endif 245 Vector2 poly[poly1Length * poly2Length + 2]; 246 int count = 0; 247 int pcount = 0; 248 249 // If one vertex from one polygon sits inside another polygon, add it and 250 // count them. 251 for (int i = 0; i < poly1Length; i++) { 252 if (testPointInsidePolygon(poly1[i], poly2, poly2Length)) { 253 poly[count] = poly1[i]; 254 count++; 255 pcount++; 256 257 } 258 } 259 260 int insidePoly2 = pcount; 261 for (int i = 0; i < poly2Length; i++) { 262 if (testPointInsidePolygon(poly2[i], poly1, poly1Length)) { 263 poly[count] = poly2[i]; 264 count++; 265 } 266 } 267 268 int insidePoly1 = count - insidePoly2; 269 // If all vertices from poly1 are inside poly2, then just return poly1. 270 if (insidePoly2 == poly1Length) { 271 memcpy(poly2, poly1, poly1Length * sizeof(Vector2)); 272 return poly1Length; 273 } 274 275 // If all vertices from poly2 are inside poly1, then just return poly2. 276 if (insidePoly1 == poly2Length) { 277 return poly2Length; 278 } 279 280 // Since neither polygon fully contain the other one, we need to add all the 281 // intersection points. 282 Vector2 intersection = {0, 0}; 283 for (int i = 0; i < poly2Length; i++) { 284 for (int j = 0; j < poly1Length; j++) { 285 int poly2LineStart = i; 286 int poly2LineEnd = ((i + 1) % poly2Length); 287 int poly1LineStart = j; 288 int poly1LineEnd = ((j + 1) % poly1Length); 289 bool found = lineIntersection( 290 poly2[poly2LineStart].x, poly2[poly2LineStart].y, 291 poly2[poly2LineEnd].x, poly2[poly2LineEnd].y, 292 poly1[poly1LineStart].x, poly1[poly1LineStart].y, 293 poly1[poly1LineEnd].x, poly1[poly1LineEnd].y, 294 intersection); 295 if (found) { 296 poly[count].x = intersection.x; 297 poly[count].y = intersection.y; 298 count++; 299 } else { 300 Vector2 delta = poly2[i] - poly1[j]; 301 if (delta.lengthSquared() < EPSILON) { 302 poly[count] = poly2[i]; 303 count++; 304 } 305 } 306 } 307 } 308 309 if (count == 0) { 310 return 0; 311 } 312 313 // Sort the result polygon around the center. 314 Vector2 center = {0.0f, 0.0f}; 315 for (int i = 0; i < count; i++) { 316 center += poly[i]; 317 } 318 center /= count; 319 sort(poly, count, center); 320 321 #if DEBUG_SHADOW 322 // Since poly2 is overwritten as the result, we need to save a copy to do 323 // our verification. 324 Vector2 oldPoly2[poly2Length]; 325 int oldPoly2Length = poly2Length; 326 memcpy(oldPoly2, poly2, sizeof(Vector2) * poly2Length); 327 #endif 328 329 // Filter the result out from poly and put it into poly2. 330 poly2[0] = poly[0]; 331 int lastOutputIndex = 0; 332 for (int i = 1; i < count; i++) { 333 Vector2 delta = poly[i] - poly2[lastOutputIndex]; 334 if (delta.lengthSquared() >= EPSILON) { 335 poly2[++lastOutputIndex] = poly[i]; 336 } else { 337 // If the vertices are too close, pick the inner one, because the 338 // inner one is more likely to be an intersection point. 339 Vector2 delta1 = poly[i] - center; 340 Vector2 delta2 = poly2[lastOutputIndex] - center; 341 if (delta1.lengthSquared() < delta2.lengthSquared()) { 342 poly2[lastOutputIndex] = poly[i]; 343 } 344 } 345 } 346 int resultLength = lastOutputIndex + 1; 347 348 #if DEBUG_SHADOW 349 testConvex(poly2, resultLength, "intersection"); 350 testConvex(poly1, poly1Length, "input poly1"); 351 testConvex(oldPoly2, oldPoly2Length, "input poly2"); 352 353 testIntersection(poly1, poly1Length, oldPoly2, oldPoly2Length, poly2, resultLength); 354 #endif 355 356 return resultLength; 357 } 358 359 /** 360 * Sort points about a center point 361 * 362 * @param poly The in and out polyogon as a Vector2 array. 363 * @param polyLength The number of vertices of the polygon. 364 * @param center the center ctr[0] = x , ctr[1] = y to sort around. 365 */ 366 void SpotShadow::sort(Vector2* poly, int polyLength, const Vector2& center) { 367 quicksortCirc(poly, 0, polyLength - 1, center); 368 } 369 370 /** 371 * Swap points pointed to by i and j 372 */ 373 void SpotShadow::swap(Vector2* points, int i, int j) { 374 Vector2 temp = points[i]; 375 points[i] = points[j]; 376 points[j] = temp; 377 } 378 379 /** 380 * quick sort implementation about the center. 381 */ 382 void SpotShadow::quicksortCirc(Vector2* points, int low, int high, 383 const Vector2& center) { 384 int i = low, j = high; 385 int p = low + (high - low) / 2; 386 float pivot = angle(points[p], center); 387 while (i <= j) { 388 while (angle(points[i], center) > pivot) { 389 i++; 390 } 391 while (angle(points[j], center) < pivot) { 392 j--; 393 } 394 395 if (i <= j) { 396 swap(points, i, j); 397 i++; 398 j--; 399 } 400 } 401 if (low < j) quicksortCirc(points, low, j, center); 402 if (i < high) quicksortCirc(points, i, high, center); 403 } 404 405 /** 406 * Sort points by x axis 407 * 408 * @param points points to sort 409 * @param low start index 410 * @param high end index 411 */ 412 void SpotShadow::quicksortX(Vector2* points, int low, int high) { 413 int i = low, j = high; 414 int p = low + (high - low) / 2; 415 float pivot = points[p].x; 416 while (i <= j) { 417 while (points[i].x < pivot) { 418 i++; 419 } 420 while (points[j].x > pivot) { 421 j--; 422 } 423 424 if (i <= j) { 425 swap(points, i, j); 426 i++; 427 j--; 428 } 429 } 430 if (low < j) quicksortX(points, low, j); 431 if (i < high) quicksortX(points, i, high); 432 } 433 434 /** 435 * Test whether a point is inside the polygon. 436 * 437 * @param testPoint the point to test 438 * @param poly the polygon 439 * @return true if the testPoint is inside the poly. 440 */ 441 bool SpotShadow::testPointInsidePolygon(const Vector2 testPoint, 442 const Vector2* poly, int len) { 443 bool c = false; 444 double testx = testPoint.x; 445 double testy = testPoint.y; 446 for (int i = 0, j = len - 1; i < len; j = i++) { 447 double startX = poly[j].x; 448 double startY = poly[j].y; 449 double endX = poly[i].x; 450 double endY = poly[i].y; 451 452 if (((endY > testy) != (startY > testy)) 453 && (testx < (startX - endX) * (testy - endY) 454 / (startY - endY) + endX)) { 455 c = !c; 456 } 457 } 458 return c; 459 } 460 461 /** 462 * Make the polygon turn clockwise. 463 * 464 * @param polygon the polygon as a Vector2 array. 465 * @param len the number of points of the polygon 466 */ 467 void SpotShadow::makeClockwise(Vector2* polygon, int len) { 468 if (polygon == 0 || len == 0) { 469 return; 470 } 471 if (!ShadowTessellator::isClockwise(polygon, len)) { 472 reverse(polygon, len); 473 } 474 } 475 476 /** 477 * Reverse the polygon 478 * 479 * @param polygon the polygon as a Vector2 array 480 * @param len the number of points of the polygon 481 */ 482 void SpotShadow::reverse(Vector2* polygon, int len) { 483 int n = len / 2; 484 for (int i = 0; i < n; i++) { 485 Vector2 tmp = polygon[i]; 486 int k = len - 1 - i; 487 polygon[i] = polygon[k]; 488 polygon[k] = tmp; 489 } 490 } 491 492 /** 493 * Intersects two lines in parametric form. This function is called in a tight 494 * loop, and we need double precision to get things right. 495 * 496 * @param x1 the x coordinate point 1 of line 1 497 * @param y1 the y coordinate point 1 of line 1 498 * @param x2 the x coordinate point 2 of line 1 499 * @param y2 the y coordinate point 2 of line 1 500 * @param x3 the x coordinate point 1 of line 2 501 * @param y3 the y coordinate point 1 of line 2 502 * @param x4 the x coordinate point 2 of line 2 503 * @param y4 the y coordinate point 2 of line 2 504 * @param ret the x,y location of the intersection 505 * @return true if it found an intersection 506 */ 507 inline bool SpotShadow::lineIntersection(double x1, double y1, double x2, double y2, 508 double x3, double y3, double x4, double y4, Vector2& ret) { 509 double d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4); 510 if (d == 0.0) return false; 511 512 double dx = (x1 * y2 - y1 * x2); 513 double dy = (x3 * y4 - y3 * x4); 514 double x = (dx * (x3 - x4) - (x1 - x2) * dy) / d; 515 double y = (dx * (y3 - y4) - (y1 - y2) * dy) / d; 516 517 // The intersection should be in the middle of the point 1 and point 2, 518 // likewise point 3 and point 4. 519 if (((x - x1) * (x - x2) > EPSILON) 520 || ((x - x3) * (x - x4) > EPSILON) 521 || ((y - y1) * (y - y2) > EPSILON) 522 || ((y - y3) * (y - y4) > EPSILON)) { 523 // Not interesected 524 return false; 525 } 526 ret.x = x; 527 ret.y = y; 528 return true; 529 530 } 531 532 /** 533 * Compute a horizontal circular polygon about point (x , y , height) of radius 534 * (size) 535 * 536 * @param points number of the points of the output polygon. 537 * @param lightCenter the center of the light. 538 * @param size the light size. 539 * @param ret result polygon. 540 */ 541 void SpotShadow::computeLightPolygon(int points, const Vector3& lightCenter, 542 float size, Vector3* ret) { 543 // TODO: Caching all the sin / cos values and store them in a look up table. 544 for (int i = 0; i < points; i++) { 545 double angle = 2 * i * M_PI / points; 546 ret[i].x = cosf(angle) * size + lightCenter.x; 547 ret[i].y = sinf(angle) * size + lightCenter.y; 548 ret[i].z = lightCenter.z; 549 } 550 } 551 552 /** 553 * From light center, project one vertex to the z=0 surface and get the outline. 554 * 555 * @param outline The result which is the outline position. 556 * @param lightCenter The center of light. 557 * @param polyVertex The input polygon's vertex. 558 * 559 * @return float The ratio of (polygon.z / light.z - polygon.z) 560 */ 561 float SpotShadow::projectCasterToOutline(Vector2& outline, 562 const Vector3& lightCenter, const Vector3& polyVertex) { 563 float lightToPolyZ = lightCenter.z - polyVertex.z; 564 float ratioZ = CASTER_Z_CAP_RATIO; 565 if (lightToPolyZ != 0) { 566 // If any caster's vertex is almost above the light, we just keep it as 95% 567 // of the height of the light. 568 ratioZ = MathUtils::clamp(polyVertex.z / lightToPolyZ, 0.0f, CASTER_Z_CAP_RATIO); 569 } 570 571 outline.x = polyVertex.x - ratioZ * (lightCenter.x - polyVertex.x); 572 outline.y = polyVertex.y - ratioZ * (lightCenter.y - polyVertex.y); 573 return ratioZ; 574 } 575 576 /** 577 * Generate the shadow spot light of shape lightPoly and a object poly 578 * 579 * @param isCasterOpaque whether the caster is opaque 580 * @param lightCenter the center of the light 581 * @param lightSize the radius of the light 582 * @param poly x,y,z vertexes of a convex polygon that occludes the light source 583 * @param polyLength number of vertexes of the occluding polygon 584 * @param shadowTriangleStrip return an (x,y,alpha) triangle strip representing the shadow. Return 585 * empty strip if error. 586 */ 587 void SpotShadow::createSpotShadow(bool isCasterOpaque, const Vector3& lightCenter, 588 float lightSize, const Vector3* poly, int polyLength, const Vector3& polyCentroid, 589 VertexBuffer& shadowTriangleStrip) { 590 if (CC_UNLIKELY(lightCenter.z <= 0)) { 591 ALOGW("Relative Light Z is not positive. No spot shadow!"); 592 return; 593 } 594 if (CC_UNLIKELY(polyLength < 3)) { 595 #if DEBUG_SHADOW 596 ALOGW("Invalid polygon length. No spot shadow!"); 597 #endif 598 return; 599 } 600 OutlineData outlineData[polyLength]; 601 Vector2 outlineCentroid; 602 // Calculate the projected outline for each polygon's vertices from the light center. 603 // 604 // O Light 605 // / 606 // / 607 // . Polygon vertex 608 // / 609 // / 610 // O Outline vertices 611 // 612 // Ratio = (Poly - Outline) / (Light - Poly) 613 // Outline.x = Poly.x - Ratio * (Light.x - Poly.x) 614 // Outline's radius / Light's radius = Ratio 615 616 // Compute the last outline vertex to make sure we can get the normal and outline 617 // in one single loop. 618 projectCasterToOutline(outlineData[polyLength - 1].position, lightCenter, 619 poly[polyLength - 1]); 620 621 // Take the outline's polygon, calculate the normal for each outline edge. 622 int currentNormalIndex = polyLength - 1; 623 int nextNormalIndex = 0; 624 625 for (int i = 0; i < polyLength; i++) { 626 float ratioZ = projectCasterToOutline(outlineData[i].position, 627 lightCenter, poly[i]); 628 outlineData[i].radius = ratioZ * lightSize; 629 630 outlineData[currentNormalIndex].normal = ShadowTessellator::calculateNormal( 631 outlineData[currentNormalIndex].position, 632 outlineData[nextNormalIndex].position); 633 currentNormalIndex = (currentNormalIndex + 1) % polyLength; 634 nextNormalIndex++; 635 } 636 637 projectCasterToOutline(outlineCentroid, lightCenter, polyCentroid); 638 639 int penumbraIndex = 0; 640 // Then each polygon's vertex produce at minmal 2 penumbra vertices. 641 // Since the size can be dynamic here, we keep track of the size and update 642 // the real size at the end. 643 int allocatedPenumbraLength = 2 * polyLength + SPOT_MAX_EXTRA_CORNER_VERTEX_NUMBER; 644 Vector2 penumbra[allocatedPenumbraLength]; 645 int totalExtraCornerSliceNumber = 0; 646 647 Vector2 umbra[polyLength]; 648 649 // When centroid is covered by all circles from outline, then we consider 650 // the umbra is invalid, and we will tune down the shadow strength. 651 bool hasValidUmbra = true; 652 // We need the minimal of RaitoVI to decrease the spot shadow strength accordingly. 653 float minRaitoVI = FLT_MAX; 654 655 for (int i = 0; i < polyLength; i++) { 656 // Generate all the penumbra's vertices only using the (outline vertex + normal * radius) 657 // There is no guarantee that the penumbra is still convex, but for 658 // each outline vertex, it will connect to all its corresponding penumbra vertices as 659 // triangle fans. And for neighber penumbra vertex, it will be a trapezoid. 660 // 661 // Penumbra Vertices marked as Pi 662 // Outline Vertices marked as Vi 663 // (P3) 664 // (P2) | ' (P4) 665 // (P1)' | | ' 666 // ' | | ' 667 // (P0) ------------------------------------------------(P5) 668 // | (V0) |(V1) 669 // | | 670 // | | 671 // | | 672 // | | 673 // | | 674 // | | 675 // | | 676 // | | 677 // (V3)-----------------------------------(V2) 678 int preNormalIndex = (i + polyLength - 1) % polyLength; 679 680 const Vector2& previousNormal = outlineData[preNormalIndex].normal; 681 const Vector2& currentNormal = outlineData[i].normal; 682 683 // Depending on how roundness we want for each corner, we can subdivide 684 // further here and/or introduce some heuristic to decide how much the 685 // subdivision should be. 686 int currentExtraSliceNumber = ShadowTessellator::getExtraVertexNumber( 687 previousNormal, currentNormal, SPOT_CORNER_RADIANS_DIVISOR); 688 689 int currentCornerSliceNumber = 1 + currentExtraSliceNumber; 690 totalExtraCornerSliceNumber += currentExtraSliceNumber; 691 #if DEBUG_SHADOW 692 ALOGD("currentExtraSliceNumber should be %d", currentExtraSliceNumber); 693 ALOGD("currentCornerSliceNumber should be %d", currentCornerSliceNumber); 694 ALOGD("totalCornerSliceNumber is %d", totalExtraCornerSliceNumber); 695 #endif 696 if (CC_UNLIKELY(totalExtraCornerSliceNumber > SPOT_MAX_EXTRA_CORNER_VERTEX_NUMBER)) { 697 currentCornerSliceNumber = 1; 698 } 699 for (int k = 0; k <= currentCornerSliceNumber; k++) { 700 Vector2 avgNormal = 701 (previousNormal * (currentCornerSliceNumber - k) + currentNormal * k) / 702 currentCornerSliceNumber; 703 avgNormal.normalize(); 704 penumbra[penumbraIndex++] = outlineData[i].position + 705 avgNormal * outlineData[i].radius; 706 } 707 708 709 // Compute the umbra by the intersection from the outline's centroid! 710 // 711 // (V) ------------------------------------ 712 // | ' | 713 // | ' | 714 // | ' (I) | 715 // | ' | 716 // | ' (C) | 717 // | | 718 // | | 719 // | | 720 // | | 721 // ------------------------------------ 722 // 723 // Connect a line b/t the outline vertex (V) and the centroid (C), it will 724 // intersect with the outline vertex's circle at point (I). 725 // Now, ratioVI = VI / VC, ratioIC = IC / VC 726 // Then the intersetion point can be computed as Ixy = Vxy * ratioIC + Cxy * ratioVI; 727 // 728 // When all of the outline circles cover the the outline centroid, (like I is 729 // on the other side of C), there is no real umbra any more, so we just fake 730 // a small area around the centroid as the umbra, and tune down the spot 731 // shadow's umbra strength to simulate the effect the whole shadow will 732 // become lighter in this case. 733 // The ratio can be simulated by using the inverse of maximum of ratioVI for 734 // all (V). 735 float distOutline = (outlineData[i].position - outlineCentroid).length(); 736 if (CC_UNLIKELY(distOutline == 0)) { 737 // If the outline has 0 area, then there is no spot shadow anyway. 738 ALOGW("Outline has 0 area, no spot shadow!"); 739 return; 740 } 741 742 float ratioVI = outlineData[i].radius / distOutline; 743 minRaitoVI = MathUtils::min(minRaitoVI, ratioVI); 744 if (ratioVI >= (1 - FAKE_UMBRA_SIZE_RATIO)) { 745 ratioVI = (1 - FAKE_UMBRA_SIZE_RATIO); 746 } 747 // When we know we don't have valid umbra, don't bother to compute the 748 // values below. But we can't skip the loop yet since we want to know the 749 // maximum ratio. 750 float ratioIC = 1 - ratioVI; 751 umbra[i] = outlineData[i].position * ratioIC + outlineCentroid * ratioVI; 752 } 753 754 hasValidUmbra = (minRaitoVI <= 1.0); 755 float shadowStrengthScale = 1.0; 756 if (!hasValidUmbra) { 757 #if DEBUG_SHADOW 758 ALOGW("The object is too close to the light or too small, no real umbra!"); 759 #endif 760 for (int i = 0; i < polyLength; i++) { 761 umbra[i] = outlineData[i].position * FAKE_UMBRA_SIZE_RATIO + 762 outlineCentroid * (1 - FAKE_UMBRA_SIZE_RATIO); 763 } 764 shadowStrengthScale = 1.0 / minRaitoVI; 765 } 766 767 int penumbraLength = penumbraIndex; 768 int umbraLength = polyLength; 769 770 #if DEBUG_SHADOW 771 ALOGD("penumbraLength is %d , allocatedPenumbraLength %d", penumbraLength, allocatedPenumbraLength); 772 dumpPolygon(poly, polyLength, "input poly"); 773 dumpPolygon(penumbra, penumbraLength, "penumbra"); 774 dumpPolygon(umbra, umbraLength, "umbra"); 775 ALOGD("hasValidUmbra is %d and shadowStrengthScale is %f", hasValidUmbra, shadowStrengthScale); 776 #endif 777 778 // The penumbra and umbra needs to be in convex shape to keep consistency 779 // and quality. 780 // Since we are still shooting rays to penumbra, it needs to be convex. 781 // Umbra can be represented as a fan from the centroid, but visually umbra 782 // looks nicer when it is convex. 783 Vector2 finalUmbra[umbraLength]; 784 Vector2 finalPenumbra[penumbraLength]; 785 int finalUmbraLength = hull(umbra, umbraLength, finalUmbra); 786 int finalPenumbraLength = hull(penumbra, penumbraLength, finalPenumbra); 787 788 generateTriangleStrip(isCasterOpaque, shadowStrengthScale, finalPenumbra, 789 finalPenumbraLength, finalUmbra, finalUmbraLength, poly, polyLength, 790 shadowTriangleStrip, outlineCentroid); 791 792 } 793 794 /** 795 * Converts a polygon specified with CW vertices into an array of distance-from-centroid values. 796 * 797 * Returns false in error conditions 798 * 799 * @param poly Array of vertices. Note that these *must* be CW. 800 * @param polyLength The number of vertices in the polygon. 801 * @param polyCentroid The centroid of the polygon, from which rays will be cast 802 * @param rayDist The output array for the calculated distances, must be SHADOW_RAY_COUNT in size 803 */ 804 bool convertPolyToRayDist(const Vector2* poly, int polyLength, const Vector2& polyCentroid, 805 float* rayDist) { 806 const int rays = SHADOW_RAY_COUNT; 807 const float step = M_PI * 2 / rays; 808 809 const Vector2* lastVertex = &(poly[polyLength - 1]); 810 float startAngle = angle(*lastVertex, polyCentroid); 811 812 // Start with the ray that's closest to and less than startAngle 813 int rayIndex = floor((startAngle - EPSILON) / step); 814 rayIndex = (rayIndex + rays) % rays; // ensure positive 815 816 for (int polyIndex = 0; polyIndex < polyLength; polyIndex++) { 817 /* 818 * For a given pair of vertices on the polygon, poly[i-1] and poly[i], the rays that 819 * intersect these will be those that are between the two angles from the centroid that the 820 * vertices define. 821 * 822 * Because the polygon vertices are stored clockwise, the closest ray with an angle 823 * *smaller* than that defined by angle(poly[i], centroid) will be the first ray that does 824 * not intersect with poly[i-1], poly[i]. 825 */ 826 float currentAngle = angle(poly[polyIndex], polyCentroid); 827 828 // find first ray that will not intersect the line segment poly[i-1] & poly[i] 829 int firstRayIndexOnNextSegment = floor((currentAngle - EPSILON) / step); 830 firstRayIndexOnNextSegment = (firstRayIndexOnNextSegment + rays) % rays; // ensure positive 831 832 // Iterate through all rays that intersect with poly[i-1], poly[i] line segment. 833 // This may be 0 rays. 834 while (rayIndex != firstRayIndexOnNextSegment) { 835 float distanceToIntersect = rayIntersectPoints(polyCentroid, 836 cos(rayIndex * step), 837 sin(rayIndex * step), 838 *lastVertex, poly[polyIndex]); 839 if (distanceToIntersect < 0) { 840 #if DEBUG_SHADOW 841 ALOGW("ERROR: convertPolyToRayDist failed"); 842 #endif 843 return false; // error case, abort 844 } 845 846 rayDist[rayIndex] = distanceToIntersect; 847 848 rayIndex = (rayIndex - 1 + rays) % rays; 849 } 850 lastVertex = &poly[polyIndex]; 851 } 852 853 return true; 854 } 855 856 int SpotShadow::calculateOccludedUmbra(const Vector2* umbra, int umbraLength, 857 const Vector3* poly, int polyLength, Vector2* occludedUmbra) { 858 // Occluded umbra area is computed as the intersection of the projected 2D 859 // poly and umbra. 860 for (int i = 0; i < polyLength; i++) { 861 occludedUmbra[i].x = poly[i].x; 862 occludedUmbra[i].y = poly[i].y; 863 } 864 865 // Both umbra and incoming polygon are guaranteed to be CW, so we can call 866 // intersection() directly. 867 return intersection(umbra, umbraLength, 868 occludedUmbra, polyLength); 869 } 870 871 /** 872 * This is only for experimental purpose. 873 * After intersections are calculated, we could smooth the polygon if needed. 874 * So far, we don't think it is more appealing yet. 875 * 876 * @param level The level of smoothness. 877 * @param rays The total number of rays. 878 * @param rayDist (In and Out) The distance for each ray. 879 * 880 */ 881 void SpotShadow::smoothPolygon(int level, int rays, float* rayDist) { 882 for (int k = 0; k < level; k++) { 883 for (int i = 0; i < rays; i++) { 884 float p1 = rayDist[(rays - 1 + i) % rays]; 885 float p2 = rayDist[i]; 886 float p3 = rayDist[(i + 1) % rays]; 887 rayDist[i] = (p1 + p2 * 2 + p3) / 4; 888 } 889 } 890 } 891 892 /** 893 * Generate a array of the angleData for either umbra or penumbra vertices. 894 * 895 * This array will be merged and used to guide where to shoot the rays, in clockwise order. 896 * 897 * @param angleDataList The result array of angle data. 898 * 899 * @return int The maximum angle's index in the array. 900 */ 901 int SpotShadow::setupAngleList(VertexAngleData* angleDataList, 902 int polyLength, const Vector2* polygon, const Vector2& centroid, 903 bool isPenumbra, const char* name) { 904 float maxAngle = FLT_MIN; 905 int maxAngleIndex = 0; 906 for (int i = 0; i < polyLength; i++) { 907 float currentAngle = angle(polygon[i], centroid); 908 if (currentAngle > maxAngle) { 909 maxAngle = currentAngle; 910 maxAngleIndex = i; 911 } 912 angleDataList[i].set(currentAngle, isPenumbra, i); 913 #if DEBUG_SHADOW 914 ALOGD("%s AngleList i %d %f", name, i, currentAngle); 915 #endif 916 } 917 return maxAngleIndex; 918 } 919 920 /** 921 * Make sure the polygons are indeed in clockwise order. 922 * 923 * Possible reasons to return false: 1. The input polygon is not setup properly. 2. The hull 924 * algorithm is not able to generate it properly. 925 * 926 * Anyway, since the algorithm depends on the clockwise, when these kind of unexpected error 927 * situation is found, we need to detect it and early return without corrupting the memory. 928 * 929 * @return bool True if the angle list is actually from big to small. 930 */ 931 bool SpotShadow::checkClockwise(int indexOfMaxAngle, int listLength, VertexAngleData* angleList, 932 const char* name) { 933 int currentIndex = indexOfMaxAngle; 934 #if DEBUG_SHADOW 935 ALOGD("max index %d", currentIndex); 936 #endif 937 for (int i = 0; i < listLength - 1; i++) { 938 // TODO: Cache the last angle. 939 float currentAngle = angleList[currentIndex].mAngle; 940 float nextAngle = angleList[(currentIndex + 1) % listLength].mAngle; 941 if (currentAngle < nextAngle) { 942 #if DEBUG_SHADOW 943 ALOGE("%s, is not CW, at index %d", name, currentIndex); 944 #endif 945 return false; 946 } 947 currentIndex = (currentIndex + 1) % listLength; 948 } 949 return true; 950 } 951 952 /** 953 * Check the polygon is clockwise. 954 * 955 * @return bool True is the polygon is clockwise. 956 */ 957 bool SpotShadow::checkPolyClockwise(int polyAngleLength, int maxPolyAngleIndex, 958 const float* polyAngleList) { 959 bool isPolyCW = true; 960 // Starting from maxPolyAngleIndex , check around to make sure angle decrease. 961 for (int i = 0; i < polyAngleLength - 1; i++) { 962 float currentAngle = polyAngleList[(i + maxPolyAngleIndex) % polyAngleLength]; 963 float nextAngle = polyAngleList[(i + maxPolyAngleIndex + 1) % polyAngleLength]; 964 if (currentAngle < nextAngle) { 965 isPolyCW = false; 966 } 967 } 968 return isPolyCW; 969 } 970 971 /** 972 * Given the sorted array of all the vertices angle data, calculate for each 973 * vertices, the offset value to array element which represent the start edge 974 * of the polygon we need to shoot the ray at. 975 * 976 * TODO: Calculate this for umbra and penumbra in one loop using one single array. 977 * 978 * @param distances The result of the array distance counter. 979 */ 980 void SpotShadow::calculateDistanceCounter(bool needsOffsetToUmbra, int angleLength, 981 const VertexAngleData* allVerticesAngleData, int* distances) { 982 983 bool firstVertexIsPenumbra = allVerticesAngleData[0].mIsPenumbra; 984 // If we want distance to inner, then we just set to 0 when we see inner. 985 bool needsSearch = needsOffsetToUmbra ? firstVertexIsPenumbra : !firstVertexIsPenumbra; 986 int distanceCounter = 0; 987 if (needsSearch) { 988 int foundIndex = -1; 989 for (int i = (angleLength - 1); i >= 0; i--) { 990 bool currentIsOuter = allVerticesAngleData[i].mIsPenumbra; 991 // If we need distance to inner, then we need to find a inner vertex. 992 if (currentIsOuter != firstVertexIsPenumbra) { 993 foundIndex = i; 994 break; 995 } 996 } 997 LOG_ALWAYS_FATAL_IF(foundIndex == -1, "Wrong index found, means either" 998 " umbra or penumbra's length is 0"); 999 distanceCounter = angleLength - foundIndex; 1000 } 1001 #if DEBUG_SHADOW 1002 ALOGD("distances[0] is %d", distanceCounter); 1003 #endif 1004 1005 distances[0] = distanceCounter; // means never see a target poly 1006 1007 for (int i = 1; i < angleLength; i++) { 1008 bool firstVertexIsPenumbra = allVerticesAngleData[i].mIsPenumbra; 1009 // When we needs for distance for each outer vertex to inner, then we 1010 // increase the distance when seeing outer vertices. Otherwise, we clear 1011 // to 0. 1012 bool needsIncrement = needsOffsetToUmbra ? firstVertexIsPenumbra : !firstVertexIsPenumbra; 1013 // If counter is not -1, that means we have seen an other polygon's vertex. 1014 if (needsIncrement && distanceCounter != -1) { 1015 distanceCounter++; 1016 } else { 1017 distanceCounter = 0; 1018 } 1019 distances[i] = distanceCounter; 1020 } 1021 } 1022 1023 /** 1024 * Given umbra and penumbra angle data list, merge them by sorting the angle 1025 * from the biggest to smallest. 1026 * 1027 * @param allVerticesAngleData The result array of merged angle data. 1028 */ 1029 void SpotShadow::mergeAngleList(int maxUmbraAngleIndex, int maxPenumbraAngleIndex, 1030 const VertexAngleData* umbraAngleList, int umbraLength, 1031 const VertexAngleData* penumbraAngleList, int penumbraLength, 1032 VertexAngleData* allVerticesAngleData) { 1033 1034 int totalRayNumber = umbraLength + penumbraLength; 1035 int umbraIndex = maxUmbraAngleIndex; 1036 int penumbraIndex = maxPenumbraAngleIndex; 1037 1038 float currentUmbraAngle = umbraAngleList[umbraIndex].mAngle; 1039 float currentPenumbraAngle = penumbraAngleList[penumbraIndex].mAngle; 1040 1041 // TODO: Clean this up using a while loop with 2 iterators. 1042 for (int i = 0; i < totalRayNumber; i++) { 1043 if (currentUmbraAngle > currentPenumbraAngle) { 1044 allVerticesAngleData[i] = umbraAngleList[umbraIndex]; 1045 umbraIndex = (umbraIndex + 1) % umbraLength; 1046 1047 // If umbraIndex round back, that means we are running out of 1048 // umbra vertices to merge, so just copy all the penumbra leftover. 1049 // Otherwise, we update the currentUmbraAngle. 1050 if (umbraIndex != maxUmbraAngleIndex) { 1051 currentUmbraAngle = umbraAngleList[umbraIndex].mAngle; 1052 } else { 1053 for (int j = i + 1; j < totalRayNumber; j++) { 1054 allVerticesAngleData[j] = penumbraAngleList[penumbraIndex]; 1055 penumbraIndex = (penumbraIndex + 1) % penumbraLength; 1056 } 1057 break; 1058 } 1059 } else { 1060 allVerticesAngleData[i] = penumbraAngleList[penumbraIndex]; 1061 penumbraIndex = (penumbraIndex + 1) % penumbraLength; 1062 // If penumbraIndex round back, that means we are running out of 1063 // penumbra vertices to merge, so just copy all the umbra leftover. 1064 // Otherwise, we update the currentPenumbraAngle. 1065 if (penumbraIndex != maxPenumbraAngleIndex) { 1066 currentPenumbraAngle = penumbraAngleList[penumbraIndex].mAngle; 1067 } else { 1068 for (int j = i + 1; j < totalRayNumber; j++) { 1069 allVerticesAngleData[j] = umbraAngleList[umbraIndex]; 1070 umbraIndex = (umbraIndex + 1) % umbraLength; 1071 } 1072 break; 1073 } 1074 } 1075 } 1076 } 1077 1078 #if DEBUG_SHADOW 1079 /** 1080 * DEBUG ONLY: Verify all the offset compuation is correctly done by examining 1081 * each vertex and its neighbor. 1082 */ 1083 static void verifyDistanceCounter(const VertexAngleData* allVerticesAngleData, 1084 const int* distances, int angleLength, const char* name) { 1085 int currentDistance = distances[0]; 1086 for (int i = 1; i < angleLength; i++) { 1087 if (distances[i] != INT_MIN) { 1088 if (!((currentDistance + 1) == distances[i] 1089 || distances[i] == 0)) { 1090 ALOGE("Wrong distance found at i %d name %s", i, name); 1091 } 1092 currentDistance = distances[i]; 1093 if (currentDistance != 0) { 1094 bool currentOuter = allVerticesAngleData[i].mIsPenumbra; 1095 for (int j = 1; j <= (currentDistance - 1); j++) { 1096 bool neigborOuter = 1097 allVerticesAngleData[(i + angleLength - j) % angleLength].mIsPenumbra; 1098 if (neigborOuter != currentOuter) { 1099 ALOGE("Wrong distance found at i %d name %s", i, name); 1100 } 1101 } 1102 bool oppositeOuter = 1103 allVerticesAngleData[(i + angleLength - currentDistance) % angleLength].mIsPenumbra; 1104 if (oppositeOuter == currentOuter) { 1105 ALOGE("Wrong distance found at i %d name %s", i, name); 1106 } 1107 } 1108 } 1109 } 1110 } 1111 1112 /** 1113 * DEBUG ONLY: Verify all the angle data compuated are is correctly done 1114 */ 1115 static void verifyAngleData(int totalRayNumber, const VertexAngleData* allVerticesAngleData, 1116 const int* distancesToInner, const int* distancesToOuter, 1117 const VertexAngleData* umbraAngleList, int maxUmbraAngleIndex, int umbraLength, 1118 const VertexAngleData* penumbraAngleList, int maxPenumbraAngleIndex, 1119 int penumbraLength) { 1120 for (int i = 0; i < totalRayNumber; i++) { 1121 ALOGD("currentAngleList i %d, angle %f, isInner %d, index %d distancesToInner" 1122 " %d distancesToOuter %d", i, allVerticesAngleData[i].mAngle, 1123 !allVerticesAngleData[i].mIsPenumbra, 1124 allVerticesAngleData[i].mVertexIndex, distancesToInner[i], distancesToOuter[i]); 1125 } 1126 1127 verifyDistanceCounter(allVerticesAngleData, distancesToInner, totalRayNumber, "distancesToInner"); 1128 verifyDistanceCounter(allVerticesAngleData, distancesToOuter, totalRayNumber, "distancesToOuter"); 1129 1130 for (int i = 0; i < totalRayNumber; i++) { 1131 if ((distancesToInner[i] * distancesToOuter[i]) != 0) { 1132 ALOGE("distancesToInner wrong at index %d distancesToInner[i] %d," 1133 " distancesToOuter[i] %d", i, distancesToInner[i], distancesToOuter[i]); 1134 } 1135 } 1136 int currentUmbraVertexIndex = 1137 umbraAngleList[maxUmbraAngleIndex].mVertexIndex; 1138 int currentPenumbraVertexIndex = 1139 penumbraAngleList[maxPenumbraAngleIndex].mVertexIndex; 1140 for (int i = 0; i < totalRayNumber; i++) { 1141 if (allVerticesAngleData[i].mIsPenumbra == true) { 1142 if (allVerticesAngleData[i].mVertexIndex != currentPenumbraVertexIndex) { 1143 ALOGW("wrong penumbra indexing i %d allVerticesAngleData[i].mVertexIndex %d " 1144 "currentpenumbraVertexIndex %d", i, 1145 allVerticesAngleData[i].mVertexIndex, currentPenumbraVertexIndex); 1146 } 1147 currentPenumbraVertexIndex = (currentPenumbraVertexIndex + 1) % penumbraLength; 1148 } else { 1149 if (allVerticesAngleData[i].mVertexIndex != currentUmbraVertexIndex) { 1150 ALOGW("wrong umbra indexing i %d allVerticesAngleData[i].mVertexIndex %d " 1151 "currentUmbraVertexIndex %d", i, 1152 allVerticesAngleData[i].mVertexIndex, currentUmbraVertexIndex); 1153 } 1154 currentUmbraVertexIndex = (currentUmbraVertexIndex + 1) % umbraLength; 1155 } 1156 } 1157 for (int i = 0; i < totalRayNumber - 1; i++) { 1158 float currentAngle = allVerticesAngleData[i].mAngle; 1159 float nextAngle = allVerticesAngleData[(i + 1) % totalRayNumber].mAngle; 1160 if (currentAngle < nextAngle) { 1161 ALOGE("Unexpected angle values!, currentAngle nextAngle %f %f", currentAngle, nextAngle); 1162 } 1163 } 1164 } 1165 #endif 1166 1167 /** 1168 * In order to compute the occluded umbra, we need to setup the angle data list 1169 * for the polygon data. Since we only store one poly vertex per polygon vertex, 1170 * this array only needs to be a float array which are the angles for each vertex. 1171 * 1172 * @param polyAngleList The result list 1173 * 1174 * @return int The index for the maximum angle in this array. 1175 */ 1176 int SpotShadow::setupPolyAngleList(float* polyAngleList, int polyAngleLength, 1177 const Vector2* poly2d, const Vector2& centroid) { 1178 int maxPolyAngleIndex = -1; 1179 float maxPolyAngle = -FLT_MAX; 1180 for (int i = 0; i < polyAngleLength; i++) { 1181 polyAngleList[i] = angle(poly2d[i], centroid); 1182 if (polyAngleList[i] > maxPolyAngle) { 1183 maxPolyAngle = polyAngleList[i]; 1184 maxPolyAngleIndex = i; 1185 } 1186 } 1187 return maxPolyAngleIndex; 1188 } 1189 1190 /** 1191 * For umbra and penumbra, given the offset info and the current ray number, 1192 * find the right edge index (the (starting vertex) for the ray to shoot at. 1193 * 1194 * @return int The index of the starting vertex of the edge. 1195 */ 1196 inline int SpotShadow::getEdgeStartIndex(const int* offsets, int rayIndex, int totalRayNumber, 1197 const VertexAngleData* allVerticesAngleData) { 1198 int tempOffset = offsets[rayIndex]; 1199 int targetRayIndex = (rayIndex - tempOffset + totalRayNumber) % totalRayNumber; 1200 return allVerticesAngleData[targetRayIndex].mVertexIndex; 1201 } 1202 1203 /** 1204 * For the occluded umbra, given the array of angles, find the index of the 1205 * starting vertex of the edge, for the ray to shoo at. 1206 * 1207 * TODO: Save the last result to shorten the search distance. 1208 * 1209 * @return int The index of the starting vertex of the edge. 1210 */ 1211 inline int SpotShadow::getPolyEdgeStartIndex(int maxPolyAngleIndex, int polyLength, 1212 const float* polyAngleList, float rayAngle) { 1213 int minPolyAngleIndex = (maxPolyAngleIndex + polyLength - 1) % polyLength; 1214 int resultIndex = -1; 1215 if (rayAngle > polyAngleList[maxPolyAngleIndex] 1216 || rayAngle <= polyAngleList[minPolyAngleIndex]) { 1217 resultIndex = minPolyAngleIndex; 1218 } else { 1219 for (int i = 0; i < polyLength - 1; i++) { 1220 int currentIndex = (maxPolyAngleIndex + i) % polyLength; 1221 int nextIndex = (maxPolyAngleIndex + i + 1) % polyLength; 1222 if (rayAngle <= polyAngleList[currentIndex] 1223 && rayAngle > polyAngleList[nextIndex]) { 1224 resultIndex = currentIndex; 1225 } 1226 } 1227 } 1228 if (CC_UNLIKELY(resultIndex == -1)) { 1229 // TODO: Add more error handling here. 1230 ALOGE("Wrong index found, means no edge can't be found for rayAngle %f", rayAngle); 1231 } 1232 return resultIndex; 1233 } 1234 1235 /** 1236 * Convert the incoming polygons into arrays of vertices, for each ray. 1237 * Ray only shoots when there is one vertex either on penumbra on umbra. 1238 * 1239 * Finally, it will generate vertices per ray for umbra, penumbra and optionally 1240 * occludedUmbra. 1241 * 1242 * Return true (success) when all vertices are generated 1243 */ 1244 int SpotShadow::convertPolysToVerticesPerRay( 1245 bool hasOccludedUmbraArea, const Vector2* poly2d, int polyLength, 1246 const Vector2* umbra, int umbraLength, const Vector2* penumbra, 1247 int penumbraLength, const Vector2& centroid, 1248 Vector2* umbraVerticesPerRay, Vector2* penumbraVerticesPerRay, 1249 Vector2* occludedUmbraVerticesPerRay) { 1250 int totalRayNumber = umbraLength + penumbraLength; 1251 1252 // For incoming umbra / penumbra polygons, we will build an intermediate data 1253 // structure to help us sort all the vertices according to the vertices. 1254 // Using this data structure, we can tell where (the angle) to shoot the ray, 1255 // whether we shoot at penumbra edge or umbra edge, and which edge to shoot at. 1256 // 1257 // We first parse each vertices and generate a table of VertexAngleData. 1258 // Based on that, we create 2 arrays telling us which edge to shoot at. 1259 VertexAngleData allVerticesAngleData[totalRayNumber]; 1260 VertexAngleData umbraAngleList[umbraLength]; 1261 VertexAngleData penumbraAngleList[penumbraLength]; 1262 1263 int polyAngleLength = hasOccludedUmbraArea ? polyLength : 0; 1264 float polyAngleList[polyAngleLength]; 1265 1266 const int maxUmbraAngleIndex = 1267 setupAngleList(umbraAngleList, umbraLength, umbra, centroid, false, "umbra"); 1268 const int maxPenumbraAngleIndex = 1269 setupAngleList(penumbraAngleList, penumbraLength, penumbra, centroid, true, "penumbra"); 1270 const int maxPolyAngleIndex = setupPolyAngleList(polyAngleList, polyAngleLength, poly2d, centroid); 1271 1272 // Check all the polygons here are CW. 1273 bool isPolyCW = checkPolyClockwise(polyAngleLength, maxPolyAngleIndex, polyAngleList); 1274 bool isUmbraCW = checkClockwise(maxUmbraAngleIndex, umbraLength, 1275 umbraAngleList, "umbra"); 1276 bool isPenumbraCW = checkClockwise(maxPenumbraAngleIndex, penumbraLength, 1277 penumbraAngleList, "penumbra"); 1278 1279 if (!isUmbraCW || !isPenumbraCW || !isPolyCW) { 1280 #if DEBUG_SHADOW 1281 ALOGE("One polygon is not CW isUmbraCW %d isPenumbraCW %d isPolyCW %d", 1282 isUmbraCW, isPenumbraCW, isPolyCW); 1283 #endif 1284 return false; 1285 } 1286 1287 mergeAngleList(maxUmbraAngleIndex, maxPenumbraAngleIndex, 1288 umbraAngleList, umbraLength, penumbraAngleList, penumbraLength, 1289 allVerticesAngleData); 1290 1291 // Calculate the offset to the left most Inner vertex for each outerVertex. 1292 // Then the offset to the left most Outer vertex for each innerVertex. 1293 int offsetToInner[totalRayNumber]; 1294 int offsetToOuter[totalRayNumber]; 1295 calculateDistanceCounter(true, totalRayNumber, allVerticesAngleData, offsetToInner); 1296 calculateDistanceCounter(false, totalRayNumber, allVerticesAngleData, offsetToOuter); 1297 1298 // Generate both umbraVerticesPerRay and penumbraVerticesPerRay 1299 for (int i = 0; i < totalRayNumber; i++) { 1300 float rayAngle = allVerticesAngleData[i].mAngle; 1301 bool isUmbraVertex = !allVerticesAngleData[i].mIsPenumbra; 1302 1303 float dx = cosf(rayAngle); 1304 float dy = sinf(rayAngle); 1305 float distanceToIntersectUmbra = -1; 1306 1307 if (isUmbraVertex) { 1308 // We can just copy umbra easily, and calculate the distance for the 1309 // occluded umbra computation. 1310 int startUmbraIndex = allVerticesAngleData[i].mVertexIndex; 1311 umbraVerticesPerRay[i] = umbra[startUmbraIndex]; 1312 if (hasOccludedUmbraArea) { 1313 distanceToIntersectUmbra = (umbraVerticesPerRay[i] - centroid).length(); 1314 } 1315 1316 //shoot ray to penumbra only 1317 int startPenumbraIndex = getEdgeStartIndex(offsetToOuter, i, totalRayNumber, 1318 allVerticesAngleData); 1319 float distanceToIntersectPenumbra = rayIntersectPoints(centroid, dx, dy, 1320 penumbra[startPenumbraIndex], 1321 penumbra[(startPenumbraIndex + 1) % penumbraLength]); 1322 if (distanceToIntersectPenumbra < 0) { 1323 #if DEBUG_SHADOW 1324 ALOGW("convertPolyToRayDist for penumbra failed rayAngle %f dx %f dy %f", 1325 rayAngle, dx, dy); 1326 #endif 1327 distanceToIntersectPenumbra = 0; 1328 } 1329 penumbraVerticesPerRay[i].x = centroid.x + dx * distanceToIntersectPenumbra; 1330 penumbraVerticesPerRay[i].y = centroid.y + dy * distanceToIntersectPenumbra; 1331 } else { 1332 // We can just copy the penumbra 1333 int startPenumbraIndex = allVerticesAngleData[i].mVertexIndex; 1334 penumbraVerticesPerRay[i] = penumbra[startPenumbraIndex]; 1335 1336 // And shoot ray to umbra only 1337 int startUmbraIndex = getEdgeStartIndex(offsetToInner, i, totalRayNumber, 1338 allVerticesAngleData); 1339 1340 distanceToIntersectUmbra = rayIntersectPoints(centroid, dx, dy, 1341 umbra[startUmbraIndex], umbra[(startUmbraIndex + 1) % umbraLength]); 1342 if (distanceToIntersectUmbra < 0) { 1343 #if DEBUG_SHADOW 1344 ALOGW("convertPolyToRayDist for umbra failed rayAngle %f dx %f dy %f", 1345 rayAngle, dx, dy); 1346 #endif 1347 distanceToIntersectUmbra = 0; 1348 } 1349 umbraVerticesPerRay[i].x = centroid.x + dx * distanceToIntersectUmbra; 1350 umbraVerticesPerRay[i].y = centroid.y + dy * distanceToIntersectUmbra; 1351 } 1352 1353 if (hasOccludedUmbraArea) { 1354 // Shoot the same ray to the poly2d, and get the distance. 1355 int startPolyIndex = getPolyEdgeStartIndex(maxPolyAngleIndex, polyLength, 1356 polyAngleList, rayAngle); 1357 1358 float distanceToIntersectPoly = rayIntersectPoints(centroid, dx, dy, 1359 poly2d[startPolyIndex], poly2d[(startPolyIndex + 1) % polyLength]); 1360 if (distanceToIntersectPoly < 0) { 1361 distanceToIntersectPoly = 0; 1362 } 1363 distanceToIntersectPoly = MathUtils::min(distanceToIntersectUmbra, distanceToIntersectPoly); 1364 occludedUmbraVerticesPerRay[i].x = centroid.x + dx * distanceToIntersectPoly; 1365 occludedUmbraVerticesPerRay[i].y = centroid.y + dy * distanceToIntersectPoly; 1366 } 1367 } 1368 1369 #if DEBUG_SHADOW 1370 verifyAngleData(totalRayNumber, allVerticesAngleData, offsetToInner, 1371 offsetToOuter, umbraAngleList, maxUmbraAngleIndex, umbraLength, 1372 penumbraAngleList, maxPenumbraAngleIndex, penumbraLength); 1373 #endif 1374 return true; // success 1375 1376 } 1377 1378 /** 1379 * Generate a triangle strip given two convex polygon 1380 **/ 1381 void SpotShadow::generateTriangleStrip(bool isCasterOpaque, float shadowStrengthScale, 1382 Vector2* penumbra, int penumbraLength, Vector2* umbra, int umbraLength, 1383 const Vector3* poly, int polyLength, VertexBuffer& shadowTriangleStrip, 1384 const Vector2& centroid) { 1385 1386 bool hasOccludedUmbraArea = false; 1387 Vector2 poly2d[polyLength]; 1388 1389 if (isCasterOpaque) { 1390 for (int i = 0; i < polyLength; i++) { 1391 poly2d[i].x = poly[i].x; 1392 poly2d[i].y = poly[i].y; 1393 } 1394 // Make sure the centroid is inside the umbra, otherwise, fall back to the 1395 // approach as if there is no occluded umbra area. 1396 if (testPointInsidePolygon(centroid, poly2d, polyLength)) { 1397 hasOccludedUmbraArea = true; 1398 } 1399 } 1400 1401 int totalRayNum = umbraLength + penumbraLength; 1402 Vector2 umbraVertices[totalRayNum]; 1403 Vector2 penumbraVertices[totalRayNum]; 1404 Vector2 occludedUmbraVertices[totalRayNum]; 1405 bool convertSuccess = convertPolysToVerticesPerRay(hasOccludedUmbraArea, poly2d, 1406 polyLength, umbra, umbraLength, penumbra, penumbraLength, 1407 centroid, umbraVertices, penumbraVertices, occludedUmbraVertices); 1408 if (!convertSuccess) { 1409 return; 1410 } 1411 1412 // Minimal value is 1, for each vertex show up once. 1413 // The bigger this value is , the smoother the look is, but more memory 1414 // is consumed. 1415 // When the ray number is high, that means the polygon has been fine 1416 // tessellated, we don't need this extra slice, just keep it as 1. 1417 int sliceNumberPerEdge = (totalRayNum > FINE_TESSELLATED_POLYGON_RAY_NUMBER) ? 1 : 2; 1418 1419 // For each polygon, we at most add (totalRayNum * sliceNumberPerEdge) vertices. 1420 int slicedVertexCountPerPolygon = totalRayNum * sliceNumberPerEdge; 1421 int totalVertexCount = slicedVertexCountPerPolygon * 2 + totalRayNum; 1422 int totalIndexCount = 2 * (slicedVertexCountPerPolygon * 2 + 2); 1423 AlphaVertex* shadowVertices = 1424 shadowTriangleStrip.alloc<AlphaVertex>(totalVertexCount); 1425 uint16_t* indexBuffer = 1426 shadowTriangleStrip.allocIndices<uint16_t>(totalIndexCount); 1427 1428 int indexBufferIndex = 0; 1429 int vertexBufferIndex = 0; 1430 1431 uint16_t slicedUmbraVertexIndex[totalRayNum * sliceNumberPerEdge]; 1432 // Should be something like 0 0 0 1 1 1 2 3 3 3... 1433 int rayNumberPerSlicedUmbra[totalRayNum * sliceNumberPerEdge]; 1434 int realUmbraVertexCount = 0; 1435 for (int i = 0; i < totalRayNum; i++) { 1436 Vector2 currentPenumbra = penumbraVertices[i]; 1437 Vector2 currentUmbra = umbraVertices[i]; 1438 1439 Vector2 nextPenumbra = penumbraVertices[(i + 1) % totalRayNum]; 1440 Vector2 nextUmbra = umbraVertices[(i + 1) % totalRayNum]; 1441 // NextUmbra/Penumbra will be done in the next loop!! 1442 for (int weight = 0; weight < sliceNumberPerEdge; weight++) { 1443 const Vector2& slicedPenumbra = (currentPenumbra * (sliceNumberPerEdge - weight) 1444 + nextPenumbra * weight) / sliceNumberPerEdge; 1445 1446 const Vector2& slicedUmbra = (currentUmbra * (sliceNumberPerEdge - weight) 1447 + nextUmbra * weight) / sliceNumberPerEdge; 1448 1449 // In the vertex buffer, we fill the Penumbra first, then umbra. 1450 indexBuffer[indexBufferIndex++] = vertexBufferIndex; 1451 AlphaVertex::set(&shadowVertices[vertexBufferIndex++], slicedPenumbra.x, 1452 slicedPenumbra.y, 0.0f); 1453 1454 // When we add umbra vertex, we need to remember its current ray number. 1455 // And its own vertexBufferIndex. This is for occluded umbra usage. 1456 indexBuffer[indexBufferIndex++] = vertexBufferIndex; 1457 rayNumberPerSlicedUmbra[realUmbraVertexCount] = i; 1458 slicedUmbraVertexIndex[realUmbraVertexCount] = vertexBufferIndex; 1459 realUmbraVertexCount++; 1460 AlphaVertex::set(&shadowVertices[vertexBufferIndex++], slicedUmbra.x, 1461 slicedUmbra.y, M_PI); 1462 } 1463 } 1464 1465 indexBuffer[indexBufferIndex++] = 0; 1466 //RealUmbraVertexIndex[0] must be 1, so we connect back well at the 1467 //beginning of occluded area. 1468 indexBuffer[indexBufferIndex++] = 1; 1469 1470 float occludedUmbraAlpha = M_PI; 1471 if (hasOccludedUmbraArea) { 1472 // Now the occludedUmbra area; 1473 int currentRayNumber = -1; 1474 int firstOccludedUmbraIndex = -1; 1475 for (int i = 0; i < realUmbraVertexCount; i++) { 1476 indexBuffer[indexBufferIndex++] = slicedUmbraVertexIndex[i]; 1477 1478 // If the occludedUmbra vertex has not been added yet, then add it. 1479 // Otherwise, just use the previously added occludedUmbra vertices. 1480 if (rayNumberPerSlicedUmbra[i] != currentRayNumber) { 1481 currentRayNumber++; 1482 indexBuffer[indexBufferIndex++] = vertexBufferIndex; 1483 // We need to remember the begining of the occludedUmbra vertices 1484 // to close this loop. 1485 if (currentRayNumber == 0) { 1486 firstOccludedUmbraIndex = vertexBufferIndex; 1487 } 1488 AlphaVertex::set(&shadowVertices[vertexBufferIndex++], 1489 occludedUmbraVertices[currentRayNumber].x, 1490 occludedUmbraVertices[currentRayNumber].y, 1491 occludedUmbraAlpha); 1492 } else { 1493 indexBuffer[indexBufferIndex++] = (vertexBufferIndex - 1); 1494 } 1495 } 1496 // Close the loop here! 1497 indexBuffer[indexBufferIndex++] = slicedUmbraVertexIndex[0]; 1498 indexBuffer[indexBufferIndex++] = firstOccludedUmbraIndex; 1499 } else { 1500 int lastCentroidIndex = vertexBufferIndex; 1501 AlphaVertex::set(&shadowVertices[vertexBufferIndex++], centroid.x, 1502 centroid.y, occludedUmbraAlpha); 1503 for (int i = 0; i < realUmbraVertexCount; i++) { 1504 indexBuffer[indexBufferIndex++] = slicedUmbraVertexIndex[i]; 1505 indexBuffer[indexBufferIndex++] = lastCentroidIndex; 1506 } 1507 // Close the loop here! 1508 indexBuffer[indexBufferIndex++] = slicedUmbraVertexIndex[0]; 1509 indexBuffer[indexBufferIndex++] = lastCentroidIndex; 1510 } 1511 1512 #if DEBUG_SHADOW 1513 ALOGD("allocated IB %d allocated VB is %d", totalIndexCount, totalVertexCount); 1514 ALOGD("IB index %d VB index is %d", indexBufferIndex, vertexBufferIndex); 1515 for (int i = 0; i < vertexBufferIndex; i++) { 1516 ALOGD("vertexBuffer i %d, (%f, %f %f)", i, shadowVertices[i].x, shadowVertices[i].y, 1517 shadowVertices[i].alpha); 1518 } 1519 for (int i = 0; i < indexBufferIndex; i++) { 1520 ALOGD("indexBuffer i %d, indexBuffer[i] %d", i, indexBuffer[i]); 1521 } 1522 #endif 1523 1524 // At the end, update the real index and vertex buffer size. 1525 shadowTriangleStrip.updateVertexCount(vertexBufferIndex); 1526 shadowTriangleStrip.updateIndexCount(indexBufferIndex); 1527 ShadowTessellator::checkOverflow(vertexBufferIndex, totalVertexCount, "Spot Vertex Buffer"); 1528 ShadowTessellator::checkOverflow(indexBufferIndex, totalIndexCount, "Spot Index Buffer"); 1529 1530 shadowTriangleStrip.setMode(VertexBuffer::kIndices); 1531 shadowTriangleStrip.computeBounds<AlphaVertex>(); 1532 } 1533 1534 #if DEBUG_SHADOW 1535 1536 #define TEST_POINT_NUMBER 128 1537 /** 1538 * Calculate the bounds for generating random test points. 1539 */ 1540 void SpotShadow::updateBound(const Vector2 inVector, Vector2& lowerBound, 1541 Vector2& upperBound) { 1542 if (inVector.x < lowerBound.x) { 1543 lowerBound.x = inVector.x; 1544 } 1545 1546 if (inVector.y < lowerBound.y) { 1547 lowerBound.y = inVector.y; 1548 } 1549 1550 if (inVector.x > upperBound.x) { 1551 upperBound.x = inVector.x; 1552 } 1553 1554 if (inVector.y > upperBound.y) { 1555 upperBound.y = inVector.y; 1556 } 1557 } 1558 1559 /** 1560 * For debug purpose, when things go wrong, dump the whole polygon data. 1561 */ 1562 void SpotShadow::dumpPolygon(const Vector2* poly, int polyLength, const char* polyName) { 1563 for (int i = 0; i < polyLength; i++) { 1564 ALOGD("polygon %s i %d x %f y %f", polyName, i, poly[i].x, poly[i].y); 1565 } 1566 } 1567 1568 /** 1569 * For debug purpose, when things go wrong, dump the whole polygon data. 1570 */ 1571 void SpotShadow::dumpPolygon(const Vector3* poly, int polyLength, const char* polyName) { 1572 for (int i = 0; i < polyLength; i++) { 1573 ALOGD("polygon %s i %d x %f y %f", polyName, i, poly[i].x, poly[i].y); 1574 } 1575 } 1576 1577 /** 1578 * Test whether the polygon is convex. 1579 */ 1580 bool SpotShadow::testConvex(const Vector2* polygon, int polygonLength, 1581 const char* name) { 1582 bool isConvex = true; 1583 for (int i = 0; i < polygonLength; i++) { 1584 Vector2 start = polygon[i]; 1585 Vector2 middle = polygon[(i + 1) % polygonLength]; 1586 Vector2 end = polygon[(i + 2) % polygonLength]; 1587 1588 double delta = (double(middle.x) - start.x) * (double(end.y) - start.y) - 1589 (double(middle.y) - start.y) * (double(end.x) - start.x); 1590 bool isCCWOrCoLinear = (delta >= EPSILON); 1591 1592 if (isCCWOrCoLinear) { 1593 ALOGW("(Error Type 2): polygon (%s) is not a convex b/c start (x %f, y %f)," 1594 "middle (x %f, y %f) and end (x %f, y %f) , delta is %f !!!", 1595 name, start.x, start.y, middle.x, middle.y, end.x, end.y, delta); 1596 isConvex = false; 1597 break; 1598 } 1599 } 1600 return isConvex; 1601 } 1602 1603 /** 1604 * Test whether or not the polygon (intersection) is within the 2 input polygons. 1605 * Using Marte Carlo method, we generate a random point, and if it is inside the 1606 * intersection, then it must be inside both source polygons. 1607 */ 1608 void SpotShadow::testIntersection(const Vector2* poly1, int poly1Length, 1609 const Vector2* poly2, int poly2Length, 1610 const Vector2* intersection, int intersectionLength) { 1611 // Find the min and max of x and y. 1612 Vector2 lowerBound = {FLT_MAX, FLT_MAX}; 1613 Vector2 upperBound = {-FLT_MAX, -FLT_MAX}; 1614 for (int i = 0; i < poly1Length; i++) { 1615 updateBound(poly1[i], lowerBound, upperBound); 1616 } 1617 for (int i = 0; i < poly2Length; i++) { 1618 updateBound(poly2[i], lowerBound, upperBound); 1619 } 1620 1621 bool dumpPoly = false; 1622 for (int k = 0; k < TEST_POINT_NUMBER; k++) { 1623 // Generate a random point between minX, minY and maxX, maxY. 1624 double randomX = rand() / double(RAND_MAX); 1625 double randomY = rand() / double(RAND_MAX); 1626 1627 Vector2 testPoint; 1628 testPoint.x = lowerBound.x + randomX * (upperBound.x - lowerBound.x); 1629 testPoint.y = lowerBound.y + randomY * (upperBound.y - lowerBound.y); 1630 1631 // If the random point is in both poly 1 and 2, then it must be intersection. 1632 if (testPointInsidePolygon(testPoint, intersection, intersectionLength)) { 1633 if (!testPointInsidePolygon(testPoint, poly1, poly1Length)) { 1634 dumpPoly = true; 1635 ALOGW("(Error Type 1): one point (%f, %f) in the intersection is" 1636 " not in the poly1", 1637 testPoint.x, testPoint.y); 1638 } 1639 1640 if (!testPointInsidePolygon(testPoint, poly2, poly2Length)) { 1641 dumpPoly = true; 1642 ALOGW("(Error Type 1): one point (%f, %f) in the intersection is" 1643 " not in the poly2", 1644 testPoint.x, testPoint.y); 1645 } 1646 } 1647 } 1648 1649 if (dumpPoly) { 1650 dumpPolygon(intersection, intersectionLength, "intersection"); 1651 for (int i = 1; i < intersectionLength; i++) { 1652 Vector2 delta = intersection[i] - intersection[i - 1]; 1653 ALOGD("Intersetion i, %d Vs i-1 is delta %f", i, delta.lengthSquared()); 1654 } 1655 1656 dumpPolygon(poly1, poly1Length, "poly 1"); 1657 dumpPolygon(poly2, poly2Length, "poly 2"); 1658 } 1659 } 1660 #endif 1661 1662 }; // namespace uirenderer 1663 }; // namespace android 1664