SpotShadow.cpp revision 7b4516e7ea552ad08d6e7277d311ef11bd8f12e8
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#define SHADOW_SHRINK_SCALE 0.1f 20 21#include <math.h> 22#include <utils/Log.h> 23 24#include "SpotShadow.h" 25#include "Vertex.h" 26 27namespace android { 28namespace uirenderer { 29 30/** 31 * Calculate the intersection of a ray with a polygon. 32 * It assumes the ray originates inside the polygon. 33 * 34 * @param poly The polygon, which is represented in a Vector2 array. 35 * @param polyLength The length of caster's polygon in terms of number of 36 * vertices. 37 * @param point the start of the ray 38 * @param dx the x vector of the ray 39 * @param dy the y vector of the ray 40 * @return the distance along the ray if it intersects with the polygon FP_NAN if otherwise 41 */ 42float SpotShadow::rayIntersectPoly(const Vector2* poly, int polyLength, 43 const Vector2& point, float dx, float dy) { 44 double px = point.x; 45 double py = point.y; 46 int p1 = polyLength - 1; 47 for (int p2 = 0; p2 < polyLength; p2++) { 48 double p1x = poly[p1].x; 49 double p1y = poly[p1].y; 50 double p2x = poly[p2].x; 51 double p2y = poly[p2].y; 52 // The math below is derived from solving this formula, basically the 53 // intersection point should stay on both the ray and the edge of (p1, p2). 54 // solve([p1x+t*(p2x-p1x)=dx*t2+px,p1y+t*(p2y-p1y)=dy*t2+py],[t,t2]); 55 double div = (dx * (p1y - p2y) + dy * p2x - dy * p1x); 56 if (div != 0) { 57 double t = (dx * (p1y - py) + dy * px - dy * p1x) / (div); 58 if (t >= 0 && t <= 1) { 59 double t2 = (p1x * (py - p2y) + p2x * (p1y - py) + 60 px * (p2y - p1y)) / div; 61 if (t2 > 0) { 62 return (float)t2; 63 } 64 } 65 } 66 p1 = p2; 67 } 68 return FP_NAN; 69} 70 71/** 72 * Calculate the centroid of a 2d polygon. 73 * 74 * @param poly The polygon, which is represented in a Vector2 array. 75 * @param polyLength The length of the polygon in terms of number of vertices. 76 * @return the centroid of the polygon. 77 */ 78Vector2 SpotShadow::centroid2d(const Vector2* poly, int polyLength) { 79 double sumx = 0; 80 double sumy = 0; 81 int p1 = polyLength - 1; 82 double area = 0; 83 for (int p2 = 0; p2 < polyLength; p2++) { 84 double x1 = poly[p1].x; 85 double y1 = poly[p1].y; 86 double x2 = poly[p2].x; 87 double y2 = poly[p2].y; 88 double a = (x1 * y2 - x2 * y1); 89 sumx += (x1 + x2) * a; 90 sumy += (y1 + y2) * a; 91 area += a; 92 p1 = p2; 93 } 94 95 double centroidx = sumx / (3 * area); 96 double centroidy = sumy / (3 * area); 97 return Vector2((float)centroidx, (float)centroidy); 98} 99 100/** 101 * Sort points by their X coordinates 102 * 103 * @param points the points as a Vector2 array. 104 * @param pointsLength the number of vertices of the polygon. 105 */ 106void SpotShadow::xsort(Vector2* points, int pointsLength) { 107 quicksortX(points, 0, pointsLength - 1); 108} 109 110/** 111 * compute the convex hull of a collection of Points 112 * 113 * @param points the points as a Vector2 array. 114 * @param pointsLength the number of vertices of the polygon. 115 * @param retPoly pre allocated array of floats to put the vertices 116 * @return the number of points in the polygon 0 if no intersection 117 */ 118int SpotShadow::hull(Vector2* points, int pointsLength, Vector2* retPoly) { 119 xsort(points, pointsLength); 120 int n = pointsLength; 121 Vector2 lUpper[n]; 122 lUpper[0] = points[0]; 123 lUpper[1] = points[1]; 124 125 int lUpperSize = 2; 126 127 for (int i = 2; i < n; i++) { 128 lUpper[lUpperSize] = points[i]; 129 lUpperSize++; 130 131 while (lUpperSize > 2 && !rightTurn( 132 (double)lUpper[lUpperSize - 3].x, (double)lUpper[lUpperSize - 3].y, 133 (double)lUpper[lUpperSize - 2].x, (double)lUpper[lUpperSize - 2].y, 134 (double)lUpper[lUpperSize - 1].x, (double)lUpper[lUpperSize - 1].y)) { 135 // Remove the middle point of the three last 136 lUpper[lUpperSize - 2].x = lUpper[lUpperSize - 1].x; 137 lUpper[lUpperSize - 2].y = lUpper[lUpperSize - 1].y; 138 lUpperSize--; 139 } 140 } 141 142 Vector2 lLower[n]; 143 lLower[0] = points[n - 1]; 144 lLower[1] = points[n - 2]; 145 146 int lLowerSize = 2; 147 148 for (int i = n - 3; i >= 0; i--) { 149 lLower[lLowerSize] = points[i]; 150 lLowerSize++; 151 152 while (lLowerSize > 2 && !rightTurn( 153 (double)lLower[lLowerSize - 3].x, (double)lLower[lLowerSize - 3].y, 154 (double)lLower[lLowerSize - 2].x, (double)lLower[lLowerSize - 2].y, 155 (double)lLower[lLowerSize - 1].x, (double)lLower[lLowerSize - 1].y)) { 156 // Remove the middle point of the three last 157 lLower[lLowerSize - 2] = lLower[lLowerSize - 1]; 158 lLowerSize--; 159 } 160 } 161 int count = 0; 162 163 for (int i = 0; i < lUpperSize; i++) { 164 retPoly[count] = lUpper[i]; 165 count++; 166 } 167 168 for (int i = 1; i < lLowerSize - 1; i++) { 169 retPoly[count] = lLower[i]; 170 count++; 171 } 172 // TODO: Add test harness which verify that all the points are inside the hull. 173 return count; 174} 175 176/** 177 * Test whether the 3 points form a right hand turn 178 * 179 * @param ax the x coordinate of point a 180 * @param ay the y coordinate of point a 181 * @param bx the x coordinate of point b 182 * @param by the y coordinate of point b 183 * @param cx the x coordinate of point c 184 * @param cy the y coordinate of point c 185 * @return true if a right hand turn 186 */ 187bool SpotShadow::rightTurn(double ax, double ay, double bx, double by, 188 double cx, double cy) { 189 return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) > EPSILON; 190} 191 192/** 193 * Calculates the intersection of poly1 with poly2 and put in poly2. 194 * 195 * 196 * @param poly1 The 1st polygon, as a Vector2 array. 197 * @param poly1Length The number of vertices of 1st polygon. 198 * @param poly2 The 2nd and output polygon, as a Vector2 array. 199 * @param poly2Length The number of vertices of 2nd polygon. 200 * @return number of vertices in output polygon as poly2. 201 */ 202int SpotShadow::intersection(Vector2* poly1, int poly1Length, 203 Vector2* poly2, int poly2Length) { 204 makeClockwise(poly1, poly1Length); 205 makeClockwise(poly2, poly2Length); 206 Vector2 poly[poly1Length * poly2Length + 2]; 207 int count = 0; 208 int pcount = 0; 209 210 // If one vertex from one polygon sits inside another polygon, add it and 211 // count them. 212 for (int i = 0; i < poly1Length; i++) { 213 if (testPointInsidePolygon(poly1[i], poly2, poly2Length)) { 214 poly[count] = poly1[i]; 215 count++; 216 pcount++; 217 218 } 219 } 220 221 int insidePoly2 = pcount; 222 for (int i = 0; i < poly2Length; i++) { 223 if (testPointInsidePolygon(poly2[i], poly1, poly1Length)) { 224 poly[count] = poly2[i]; 225 count++; 226 } 227 } 228 229 int insidePoly1 = count - insidePoly2; 230 // If all vertices from poly1 are inside poly2, then just return poly1. 231 if (insidePoly2 == poly1Length) { 232 memcpy(poly2, poly1, poly1Length * sizeof(Vector2)); 233 return poly1Length; 234 } 235 236 // If all vertices from poly2 are inside poly1, then just return poly2. 237 if (insidePoly1 == poly2Length) { 238 return poly2Length; 239 } 240 241 // Since neither polygon fully contain the other one, we need to add all the 242 // intersection points. 243 Vector2 intersection; 244 for (int i = 0; i < poly2Length; i++) { 245 for (int j = 0; j < poly1Length; j++) { 246 int poly2LineStart = i; 247 int poly2LineEnd = ((i + 1) % poly2Length); 248 int poly1LineStart = j; 249 int poly1LineEnd = ((j + 1) % poly1Length); 250 bool found = lineIntersection( 251 poly2[poly2LineStart].x, poly2[poly2LineStart].y, 252 poly2[poly2LineEnd].x, poly2[poly2LineEnd].y, 253 poly1[poly1LineStart].x, poly1[poly1LineStart].y, 254 poly1[poly1LineEnd].x, poly1[poly1LineEnd].y, 255 intersection); 256 if (found) { 257 poly[count].x = intersection.x; 258 poly[count].y = intersection.y; 259 count++; 260 } else { 261 Vector2 delta = poly2[i] - poly1[j]; 262 if (delta.lengthSquared() < 0.01) { 263 poly[count] = poly2[i]; 264 count++; 265 } 266 } 267 } 268 } 269 270 if (count == 0) { 271 return 0; 272 } 273 274 // Sort the result polygon around the center. 275 Vector2 center(0.0f, 0.0f); 276 for (int i = 0; i < count; i++) { 277 center += poly[i]; 278 } 279 center /= count; 280 sort(poly, count, center); 281 282 // TODO: Verify the intersection works correctly, like any random point 283 // inside both poly1 and poly2 should be inside the intersection, and the 284 // result intersection polygon is convex. 285 286 // Merge the vertices if they are too close. 287 poly2[0] = poly[0]; 288 int resultLength = 1; 289 for (int i = 1; i < count; i++) { 290 Vector2 delta = poly[i] - poly[i - 1]; 291 if (delta.lengthSquared() >= 0.01) { 292 poly2[resultLength] = poly[i]; 293 resultLength++; 294 } 295 } 296 297 return resultLength; 298} 299 300/** 301 * Sort points about a center point 302 * 303 * @param poly The in and out polyogon as a Vector2 array. 304 * @param polyLength The number of vertices of the polygon. 305 * @param center the center ctr[0] = x , ctr[1] = y to sort around. 306 */ 307void SpotShadow::sort(Vector2* poly, int polyLength, const Vector2& center) { 308 quicksortCirc(poly, 0, polyLength - 1, center); 309} 310 311/** 312 * Calculate the angle between and x and a y coordinate 313 */ 314float SpotShadow::angle(const Vector2& point, const Vector2& center) { 315 return -(float)atan2(point.x - center.x, point.y - center.y); 316} 317 318/** 319 * Swap points pointed to by i and j 320 */ 321void SpotShadow::swap(Vector2* points, int i, int j) { 322 Vector2 temp = points[i]; 323 points[i] = points[j]; 324 points[j] = temp; 325} 326 327/** 328 * quick sort implementation about the center. 329 */ 330void SpotShadow::quicksortCirc(Vector2* points, int low, int high, 331 const Vector2& center) { 332 int i = low, j = high; 333 int p = low + (high - low) / 2; 334 float pivot = angle(points[p], center); 335 while (i <= j) { 336 while (angle(points[i], center) < pivot) { 337 i++; 338 } 339 while (angle(points[j], center) > pivot) { 340 j--; 341 } 342 343 if (i <= j) { 344 swap(points, i, j); 345 i++; 346 j--; 347 } 348 } 349 if (low < j) quicksortCirc(points, low, j, center); 350 if (i < high) quicksortCirc(points, i, high, center); 351} 352 353/** 354 * Sort points by x axis 355 * 356 * @param points points to sort 357 * @param low start index 358 * @param high end index 359 */ 360void SpotShadow::quicksortX(Vector2* points, int low, int high) { 361 int i = low, j = high; 362 int p = low + (high - low) / 2; 363 float pivot = points[p].x; 364 while (i <= j) { 365 while (points[i].x < pivot) { 366 i++; 367 } 368 while (points[j].x > pivot) { 369 j--; 370 } 371 372 if (i <= j) { 373 swap(points, i, j); 374 i++; 375 j--; 376 } 377 } 378 if (low < j) quicksortX(points, low, j); 379 if (i < high) quicksortX(points, i, high); 380} 381 382/** 383 * Test whether a point is inside the polygon. 384 * 385 * @param testPoint the point to test 386 * @param poly the polygon 387 * @return true if the testPoint is inside the poly. 388 */ 389bool SpotShadow::testPointInsidePolygon(const Vector2 testPoint, 390 const Vector2* poly, int len) { 391 bool c = false; 392 double testx = testPoint.x; 393 double testy = testPoint.y; 394 for (int i = 0, j = len - 1; i < len; j = i++) { 395 double startX = poly[j].x; 396 double startY = poly[j].y; 397 double endX = poly[i].x; 398 double endY = poly[i].y; 399 400 if (((endY > testy) != (startY > testy)) && 401 (testx < (startX - endX) * (testy - endY) 402 / (startY - endY) + endX)) { 403 c = !c; 404 } 405 } 406 return c; 407} 408 409/** 410 * Make the polygon turn clockwise. 411 * 412 * @param polygon the polygon as a Vector2 array. 413 * @param len the number of points of the polygon 414 */ 415void SpotShadow::makeClockwise(Vector2* polygon, int len) { 416 if (polygon == 0 || len == 0) { 417 return; 418 } 419 if (!isClockwise(polygon, len)) { 420 reverse(polygon, len); 421 } 422} 423 424/** 425 * Test whether the polygon is order in clockwise. 426 * 427 * @param polygon the polygon as a Vector2 array 428 * @param len the number of points of the polygon 429 */ 430bool SpotShadow::isClockwise(Vector2* polygon, int len) { 431 double sum = 0; 432 double p1x = polygon[len - 1].x; 433 double p1y = polygon[len - 1].y; 434 for (int i = 0; i < len; i++) { 435 436 double p2x = polygon[i].x; 437 double p2y = polygon[i].y; 438 sum += p1x * p2y - p2x * p1y; 439 p1x = p2x; 440 p1y = p2y; 441 } 442 return sum < 0; 443} 444 445/** 446 * Reverse the polygon 447 * 448 * @param polygon the polygon as a Vector2 array 449 * @param len the number of points of the polygon 450 */ 451void SpotShadow::reverse(Vector2* polygon, int len) { 452 int n = len / 2; 453 for (int i = 0; i < n; i++) { 454 Vector2 tmp = polygon[i]; 455 int k = len - 1 - i; 456 polygon[i] = polygon[k]; 457 polygon[k] = tmp; 458 } 459} 460 461/** 462 * Intersects two lines in parametric form. This function is called in a tight 463 * loop, and we need double precision to get things right. 464 * 465 * @param x1 the x coordinate point 1 of line 1 466 * @param y1 the y coordinate point 1 of line 1 467 * @param x2 the x coordinate point 2 of line 1 468 * @param y2 the y coordinate point 2 of line 1 469 * @param x3 the x coordinate point 1 of line 2 470 * @param y3 the y coordinate point 1 of line 2 471 * @param x4 the x coordinate point 2 of line 2 472 * @param y4 the y coordinate point 2 of line 2 473 * @param ret the x,y location of the intersection 474 * @return true if it found an intersection 475 */ 476inline bool SpotShadow::lineIntersection(double x1, double y1, double x2, double y2, 477 double x3, double y3, double x4, double y4, Vector2& ret) { 478 double d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4); 479 if (d == 0.0) return false; 480 481 double dx = (x1 * y2 - y1 * x2); 482 double dy = (x3 * y4 - y3 * x4); 483 double x = (dx * (x3 - x4) - (x1 - x2) * dy) / d; 484 double y = (dx * (y3 - y4) - (y1 - y2) * dy) / d; 485 486 // The intersection should be in the middle of the point 1 and point 2, 487 // likewise point 3 and point 4. 488 if (((x - x1) * (x - x2) > EPSILON) 489 || ((x - x3) * (x - x4) > EPSILON) 490 || ((y - y1) * (y - y2) > EPSILON) 491 || ((y - y3) * (y - y4) > EPSILON)) { 492 // Not interesected 493 return false; 494 } 495 ret.x = x; 496 ret.y = y; 497 return true; 498 499} 500 501/** 502 * Compute a horizontal circular polygon about point (x , y , height) of radius 503 * (size) 504 * 505 * @param points number of the points of the output polygon. 506 * @param lightCenter the center of the light. 507 * @param size the light size. 508 * @param ret result polygon. 509 */ 510void SpotShadow::computeLightPolygon(int points, const Vector3& lightCenter, 511 float size, Vector3* ret) { 512 // TODO: Caching all the sin / cos values and store them in a look up table. 513 for (int i = 0; i < points; i++) { 514 double angle = 2 * i * M_PI / points; 515 ret[i].x = sinf(angle) * size + lightCenter.x; 516 ret[i].y = cosf(angle) * size + lightCenter.y; 517 ret[i].z = lightCenter.z; 518 } 519} 520 521/** 522* Generate the shadow from a spot light. 523* 524* @param poly x,y,z vertexes of a convex polygon that occludes the light source 525* @param polyLength number of vertexes of the occluding polygon 526* @param lightCenter the center of the light 527* @param lightSize the radius of the light source 528* @param lightVertexCount the vertex counter for the light polygon 529* @param rays the number of vertexes to create along the edges of the shadow 530* @param layers the number of layers of triangles strips to create 531* @param strength the "darkness" of the shadow 532* @param shadowTriangleStrip return an (x,y,alpha) triangle strip representing the shadow. Return 533* empty strip if error. 534* 535*/ 536void SpotShadow::createSpotShadow(const Vector3* poly, int polyLength, 537 const Vector3& lightCenter, float lightSize, int lightVertexCount, 538 int rays, int layers, float strength, VertexBuffer& retStrips) { 539 Vector3 light[lightVertexCount * 3]; 540 computeLightPolygon(lightVertexCount, lightCenter, lightSize, light); 541 computeSpotShadow(light, lightVertexCount, lightCenter, 542 poly, polyLength, rays, layers, strength, retStrips); 543} 544 545/** 546 * Generate the shadow spot light of shape lightPoly and a object poly 547 * 548 * @param lightPoly x,y,z vertex of a convex polygon that is the light source 549 * @param lightPolyLength number of vertexes of the light source polygon 550 * @param poly x,y,z vertexes of a convex polygon that occludes the light source 551 * @param polyLength number of vertexes of the occluding polygon 552 * @param rays the number of vertexes to create along the edges of the shadow 553 * @param layers the number of layers of triangles strips to create 554 * @param strength the "darkness" of the shadow 555 * @param shadowTriangleStrip return an (x,y,alpha) triangle strip representing the shadow. Return 556 * empty strip if error. 557 */ 558void SpotShadow::computeSpotShadow(const Vector3* lightPoly, int lightPolyLength, 559 const Vector3& lightCenter, const Vector3* poly, int polyLength, 560 int rays, int layers, float strength, VertexBuffer& shadowTriangleStrip) { 561 // Point clouds for all the shadowed vertices 562 Vector2 shadowRegion[lightPolyLength * polyLength]; 563 // Shadow polygon from one point light. 564 Vector2 outline[polyLength]; 565 Vector2 umbraMem[polyLength * lightPolyLength]; 566 Vector2* umbra = umbraMem; 567 568 int umbraLength = 0; 569 570 // Validate input, receiver is always at z = 0 plane. 571 bool inputPolyPositionValid = true; 572 for (int i = 0; i < polyLength; i++) { 573 if (poly[i].z <= 0.00001) { 574 inputPolyPositionValid = false; 575 ALOGE("polygon below the surface"); 576 break; 577 } 578 if (poly[i].z >= lightPoly[0].z) { 579 inputPolyPositionValid = false; 580 ALOGE("polygon above the light"); 581 break; 582 } 583 } 584 585 // If the caster's position is invalid, don't draw anything. 586 if (!inputPolyPositionValid) { 587 return; 588 } 589 590 // Calculate the umbra polygon based on intersections of all outlines 591 int k = 0; 592 for (int j = 0; j < lightPolyLength; j++) { 593 int m = 0; 594 for (int i = 0; i < polyLength; i++) { 595 float t = lightPoly[j].z - poly[i].z; 596 if (t == 0) { 597 return; 598 } 599 t = lightPoly[j].z / t; 600 float x = lightPoly[j].x - t * (lightPoly[j].x - poly[i].x); 601 float y = lightPoly[j].y - t * (lightPoly[j].y - poly[i].y); 602 603 Vector2 newPoint = Vector2(x, y); 604 shadowRegion[k] = newPoint; 605 outline[m] = newPoint; 606 607 k++; 608 m++; 609 } 610 611 // For the first light polygon's vertex, use the outline as the umbra. 612 // Later on, use the intersection of the outline and existing umbra. 613 if (umbraLength == 0) { 614 for (int i = 0; i < polyLength; i++) { 615 umbra[i] = outline[i]; 616 } 617 umbraLength = polyLength; 618 } else { 619 int col = ((j * 255) / lightPolyLength); 620 umbraLength = intersection(outline, polyLength, umbra, umbraLength); 621 if (umbraLength == 0) { 622 break; 623 } 624 } 625 } 626 627 // Generate the penumbra area using the hull of all shadow regions. 628 int shadowRegionLength = k; 629 Vector2 penumbra[k]; 630 int penumbraLength = hull(shadowRegion, shadowRegionLength, penumbra); 631 632 // no real umbra make a fake one 633 if (umbraLength < 3) { 634 // The shadow from the centroid of the light polygon. 635 Vector2 centShadow[polyLength]; 636 637 for (int i = 0; i < polyLength; i++) { 638 float t = lightCenter.z - poly[i].z; 639 if (t == 0) { 640 return; 641 } 642 t = lightCenter.z / t; 643 float x = lightCenter.x - t * (lightCenter.x - poly[i].x); 644 float y = lightCenter.y - t * (lightCenter.y - poly[i].y); 645 646 centShadow[i].x = x; 647 centShadow[i].y = y; 648 } 649 650 // Shrink the centroid's shadow by 10%. 651 // TODO: Study the magic number of 10%. 652 Vector2 shadowCentroid = centroid2d(centShadow, polyLength); 653 for (int i = 0; i < polyLength; i++) { 654 centShadow[i] = shadowCentroid * (1.0f - SHADOW_SHRINK_SCALE) + 655 centShadow[i] * SHADOW_SHRINK_SCALE; 656 } 657#if DEBUG_SHADOW 658 ALOGD("No real umbra make a fake one, centroid2d = %f , %f", 659 shadowCentroid.x, shadowCentroid.y); 660#endif 661 // Set the fake umbra, whose size is the same as the original polygon. 662 umbra = centShadow; 663 umbraLength = polyLength; 664 } 665 666 generateTriangleStrip(penumbra, penumbraLength, umbra, umbraLength, 667 rays, layers, strength, shadowTriangleStrip); 668} 669 670/** 671 * Generate a triangle strip given two convex polygons 672 * 673 * @param penumbra The outer polygon x,y vertexes 674 * @param penumbraLength The number of vertexes in the outer polygon 675 * @param umbra The inner outer polygon x,y vertexes 676 * @param umbraLength The number of vertexes in the inner polygon 677 * @param rays The number of points along the polygons to create 678 * @param layers The number of layers of triangle strips between the umbra and penumbra 679 * @param strength The max alpha of the umbra 680 * @param shadowTriangleStrip return an (x,y,alpha) triangle strip representing the shadow. Return 681 * empty strip if error. 682**/ 683void SpotShadow::generateTriangleStrip(const Vector2* penumbra, int penumbraLength, 684 const Vector2* umbra, int umbraLength, int rays, int layers, 685 float strength, VertexBuffer& shadowTriangleStrip) { 686 687 int rings = layers + 1; 688 int size = rays * rings; 689 690 float step = M_PI * 2 / rays; 691 // Centroid of the umbra. 692 Vector2 centroid = centroid2d(umbra, umbraLength); 693#if DEBUG_SHADOW 694 ALOGD("centroid2d = %f , %f", centroid.x, centroid.y); 695#endif 696 // Intersection to the penumbra. 697 float penumbraDistPerRay[rays]; 698 // Intersection to the umbra. 699 float umbraDistPerRay[rays]; 700 701 for (int i = 0; i < rays; i++) { 702 // TODO: Setup a lookup table for all the sin/cos. 703 float dx = sinf(step * i); 704 float dy = cosf(step * i); 705 umbraDistPerRay[i] = rayIntersectPoly(umbra, umbraLength, centroid, 706 dx, dy); 707 if (isnan(umbraDistPerRay[i])) { 708 ALOGE("rayIntersectPoly returns NAN"); 709 return; 710 } 711 penumbraDistPerRay[i] = rayIntersectPoly(penumbra, penumbraLength, 712 centroid, dx, dy); 713 if (isnan(umbraDistPerRay[i])) { 714 ALOGE("rayIntersectPoly returns NAN"); 715 return; 716 } 717 } 718 719 int stripSize = getStripSize(rays, layers); 720 AlphaVertex* shadowVertices = shadowTriangleStrip.alloc<AlphaVertex>(stripSize); 721 int currentIndex = 0; 722 // Calculate the vertex values in the penumbra area. 723 for (int r = 0; r < layers; r++) { 724 int firstInEachLayer = currentIndex; 725 for (int i = 0; i < rays; i++) { 726 float dx = sinf(step * i); 727 float dy = cosf(step * i); 728 729 for (int j = r; j < (r + 2); j++) { 730 float layerRatio = j / (float)(rings - 1); 731 float deltaDist = layerRatio * (umbraDistPerRay[i] - penumbraDistPerRay[i]); 732 float currentDist = penumbraDistPerRay[i] + deltaDist; 733 float op = calculateOpacity(layerRatio, deltaDist); 734 AlphaVertex::set(&shadowVertices[currentIndex], 735 dx * currentDist + centroid.x, 736 dy * currentDist + centroid.y, 737 layerRatio * op * strength); 738 currentIndex++; 739 } 740 } 741 742 // Duplicate the vertices from one layer to another one to make triangle 743 // strip. 744 shadowVertices[currentIndex++] = shadowVertices[firstInEachLayer]; 745 firstInEachLayer++; 746 shadowVertices[currentIndex++] = shadowVertices[firstInEachLayer]; 747 } 748 749 int lastInPenumbra = currentIndex - 1; 750 shadowVertices[currentIndex++] = shadowVertices[lastInPenumbra]; 751 752 // Preallocate the vertices (index as [firstInUmbra - 1]) for jumping from 753 // the penumbra to umbra. 754 currentIndex++; 755 int firstInUmbra = currentIndex; 756 757 // traverse the umbra area in a zig zag pattern for strips. 758 for (int k = 0; k < rays; k++) { 759 int i = k / 2; 760 if ((k & 1) == 1) { 761 i = rays - i - 1; 762 } 763 float dx = sinf(step * i); 764 float dy = cosf(step * i); 765 766 float ratio = 1.0; 767 float deltaDist = ratio * (umbraDistPerRay[i] - penumbraDistPerRay[i]); 768 float currentDist = penumbraDistPerRay[i] + deltaDist; 769 float op = calculateOpacity(ratio, deltaDist); 770 AlphaVertex::set(&shadowVertices[currentIndex], 771 dx * currentDist + centroid.x, dy * currentDist + centroid.y, 772 ratio * op * strength); 773 currentIndex++; 774 775 } 776 777 // Back fill the one vertex for jumping from penumbra to umbra. 778 shadowVertices[firstInUmbra - 1] = shadowVertices[firstInUmbra]; 779 780#if DEBUG_SHADOW 781 for (int i = 0; i < currentIndex; i++) { 782 ALOGD("shadow value: i %d, (x:%f, y:%f, a:%f)", i, shadowVertices[i].x, 783 shadowVertices[i].y, shadowVertices[i].alpha); 784 } 785#endif 786} 787 788/** 789 * This is only for experimental purpose. 790 * After intersections are calculated, we could smooth the polygon if needed. 791 * So far, we don't think it is more appealing yet. 792 * 793 * @param level The level of smoothness. 794 * @param rays The total number of rays. 795 * @param rayDist (In and Out) The distance for each ray. 796 * 797 */ 798void SpotShadow::smoothPolygon(int level, int rays, float* rayDist) { 799 for (int k = 0; k < level; k++) { 800 for (int i = 0; i < rays; i++) { 801 float p1 = rayDist[(rays - 1 + i) % rays]; 802 float p2 = rayDist[i]; 803 float p3 = rayDist[(i + 1) % rays]; 804 rayDist[i] = (p1 + p2 * 2 + p3) / 4; 805 } 806 } 807} 808 809/** 810 * Calculate the opacity according to the distance and falloff ratio. 811 * 812 * @param distRatio The distance ratio of current sample between umbra and 813 * penumbra area. 814 * @param deltaDist The distance between current sample to the penumbra area. 815 * @return The opacity according to the distance between umbra and penumbra. 816 */ 817float SpotShadow::calculateOpacity(float distRatio, float deltaDist) { 818 // TODO: Experiment on the opacity calculation. 819 float falloffRatio = 1 + deltaDist * deltaDist; 820 return (distRatio + 1 - 1 / falloffRatio) / 2; 821} 822 823/** 824 * Calculate the number of vertex we will create given a number of rays and layers 825 * 826 * @param rays number of points around the polygons you want 827 * @param layers number of layers of triangle strips you need 828 * @return number of vertex (multiply by 3 for number of floats) 829 */ 830int SpotShadow::getStripSize(int rays, int layers) { 831 return (2 + rays + ((layers) * 2 * (rays + 1))); 832} 833 834}; // namespace uirenderer 835}; // namespace android 836 837 838 839 840