17b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/*
27b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * Copyright (C) 2014 The Android Open Source Project
37b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
47b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * Licensed under the Apache License, Version 2.0 (the "License");
57b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * you may not use this file except in compliance with the License.
67b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * You may obtain a copy of the License at
77b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
87b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *      http://www.apache.org/licenses/LICENSE-2.0
97b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
107b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * Unless required by applicable law or agreed to in writing, software
117b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * distributed under the License is distributed on an "AS IS" BASIS,
127b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
137b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * See the License for the specific language governing permissions and
147b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * limitations under the License.
157b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
167b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
177b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui#define LOG_TAG "OpenGLRenderer"
187b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
19512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui// The highest z value can't be higher than (CASTER_Z_CAP_RATIO * light.z)
20c50a03d78aaedd0003377e98710e7038bda330e9ztenghui#define CASTER_Z_CAP_RATIO 0.95f
21512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
22512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui// When there is no umbra, then just fake the umbra using
23512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui// centroid * (1 - FAKE_UMBRA_SIZE_RATIO) + outline * FAKE_UMBRA_SIZE_RATIO
24512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#define FAKE_UMBRA_SIZE_RATIO 0.05f
25512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
26512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui// When the polygon is about 90 vertices, the penumbra + umbra can reach 270 rays.
27512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui// That is consider pretty fine tessllated polygon so far.
28512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui// This is just to prevent using too much some memory when edge slicing is not
29512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui// needed any more.
30512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#define FINE_TESSELLATED_POLYGON_RAY_NUMBER 270
31512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui/**
32512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * Extra vertices for the corner for smoother corner.
33512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * Only for outer loop.
34512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * Note that we use such extra memory to avoid an extra loop.
35512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui */
36512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui// For half circle, we could add EXTRA_VERTEX_PER_PI vertices.
37512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui// Set to 1 if we don't want to have any.
38512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#define SPOT_EXTRA_CORNER_VERTEX_PER_PI 18
39512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
40512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui// For the whole polygon, the sum of all the deltas b/t normals is 2 * M_PI,
41512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui// therefore, the maximum number of extra vertices will be twice bigger.
42512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#define SPOT_MAX_EXTRA_CORNER_VERTEX_NUMBER  (2 * SPOT_EXTRA_CORNER_VERTEX_PER_PI)
43512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
44512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui// For each RADIANS_DIVISOR, we would allocate one more vertex b/t the normals.
45512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#define SPOT_CORNER_RADIANS_DIVISOR (M_PI / SPOT_EXTRA_CORNER_VERTEX_PER_PI)
46512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
477b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
487b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui#include <math.h>
49f5ca8b4cb178008472e67fa0ae6a3e3fa75d7952ztenghui#include <stdlib.h>
507b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui#include <utils/Log.h>
517b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
5263d41abb40b3ce40d8b9bccb1cf186e8158a3687ztenghui#include "ShadowTessellator.h"
537b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui#include "SpotShadow.h"
547b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui#include "Vertex.h"
55c50a03d78aaedd0003377e98710e7038bda330e9ztenghui#include "utils/MathUtils.h"
567b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
57c50a03d78aaedd0003377e98710e7038bda330e9ztenghui// TODO: After we settle down the new algorithm, we can remove the old one and
58c50a03d78aaedd0003377e98710e7038bda330e9ztenghui// its utility functions.
59c50a03d78aaedd0003377e98710e7038bda330e9ztenghui// Right now, we still need to keep it for comparison purpose and future expansion.
607b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghuinamespace android {
617b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghuinamespace uirenderer {
627b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
639122b1b168d2a74d51517ed7282f4d6a8adea367ztenghuistatic const float EPSILON = 1e-7;
64726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik
65726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik/**
66c50a03d78aaedd0003377e98710e7038bda330e9ztenghui * For each polygon's vertex, the light center will project it to the receiver
67c50a03d78aaedd0003377e98710e7038bda330e9ztenghui * as one of the outline vertex.
68c50a03d78aaedd0003377e98710e7038bda330e9ztenghui * For each outline vertex, we need to store the position and normal.
69c50a03d78aaedd0003377e98710e7038bda330e9ztenghui * Normal here is defined against the edge by the current vertex and the next vertex.
70c50a03d78aaedd0003377e98710e7038bda330e9ztenghui */
71c50a03d78aaedd0003377e98710e7038bda330e9ztenghuistruct OutlineData {
72c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    Vector2 position;
73c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    Vector2 normal;
74c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    float radius;
75c50a03d78aaedd0003377e98710e7038bda330e9ztenghui};
76c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
77c50a03d78aaedd0003377e98710e7038bda330e9ztenghui/**
78512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * For each vertex, we need to keep track of its angle, whether it is penumbra or
79512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * umbra, and its corresponding vertex index.
80512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui */
81512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghuistruct SpotShadow::VertexAngleData {
82512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // The angle to the vertex from the centroid.
83512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    float mAngle;
84512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // True is the vertex comes from penumbra, otherwise it comes from umbra.
85512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    bool mIsPenumbra;
86512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // The index of the vertex described by this data.
87512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    int mVertexIndex;
88512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    void set(float angle, bool isPenumbra, int index) {
89512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        mAngle = angle;
90512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        mIsPenumbra = isPenumbra;
91512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        mVertexIndex = index;
92512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    }
93512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui};
94512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
95512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui/**
96726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik * Calculate the angle between and x and a y coordinate.
97726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik * The atan2 range from -PI to PI.
98726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik */
99b79a3e301a8d89b9e1b1f6f3d7fd6aa56610a6f0Chris Craikstatic float angle(const Vector2& point, const Vector2& center) {
100726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik    return atan2(point.y - center.y, point.x - center.x);
101726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik}
102726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik
1037b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
104726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik * Calculate the intersection of a ray with the line segment defined by two points.
1057b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
106726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik * Returns a negative value in error conditions.
107726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik
108726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik * @param rayOrigin The start of the ray
109726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik * @param dx The x vector of the ray
110726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik * @param dy The y vector of the ray
111726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik * @param p1 The first point defining the line segment
112726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik * @param p2 The second point defining the line segment
113726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik * @return The distance along the ray if it intersects with the line segment, negative if otherwise
1147b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
115b79a3e301a8d89b9e1b1f6f3d7fd6aa56610a6f0Chris Craikstatic float rayIntersectPoints(const Vector2& rayOrigin, float dx, float dy,
116726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik        const Vector2& p1, const Vector2& p2) {
117726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik    // The math below is derived from solving this formula, basically the
118726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik    // intersection point should stay on both the ray and the edge of (p1, p2).
119726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik    // solve([p1x+t*(p2x-p1x)=dx*t2+px,p1y+t*(p2y-p1y)=dy*t2+py],[t,t2]);
120726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik
1219122b1b168d2a74d51517ed7282f4d6a8adea367ztenghui    float divisor = (dx * (p1.y - p2.y) + dy * p2.x - dy * p1.x);
122726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik    if (divisor == 0) return -1.0f; // error, invalid divisor
123726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik
124726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik#if DEBUG_SHADOW
1259122b1b168d2a74d51517ed7282f4d6a8adea367ztenghui    float interpVal = (dx * (p1.y - rayOrigin.y) + dy * rayOrigin.x - dy * p1.x) / divisor;
12699af9429cda84ad0af1d7fcecb580295b0046882ztenghui    if (interpVal < 0 || interpVal > 1) {
12799af9429cda84ad0af1d7fcecb580295b0046882ztenghui        ALOGW("rayIntersectPoints is hitting outside the segment %f", interpVal);
12899af9429cda84ad0af1d7fcecb580295b0046882ztenghui    }
129726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik#endif
130726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik
1319122b1b168d2a74d51517ed7282f4d6a8adea367ztenghui    float distance = (p1.x * (rayOrigin.y - p2.y) + p2.x * (p1.y - rayOrigin.y) +
132726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik            rayOrigin.x * (p2.y - p1.y)) / divisor;
133726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik
134726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik    return distance; // may be negative in error cases
1357b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui}
1367b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
1377b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
1387b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * Sort points by their X coordinates
1397b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
1407b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param points the points as a Vector2 array.
1417b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param pointsLength the number of vertices of the polygon.
1427b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
1437b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghuivoid SpotShadow::xsort(Vector2* points, int pointsLength) {
1447b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    quicksortX(points, 0, pointsLength - 1);
1457b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui}
1467b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
1477b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
1487b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * compute the convex hull of a collection of Points
1497b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
1507b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param points the points as a Vector2 array.
1517b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param pointsLength the number of vertices of the polygon.
1527b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param retPoly pre allocated array of floats to put the vertices
1537b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @return the number of points in the polygon 0 if no intersection
1547b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
1557b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghuiint SpotShadow::hull(Vector2* points, int pointsLength, Vector2* retPoly) {
1567b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    xsort(points, pointsLength);
1577b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    int n = pointsLength;
1587b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    Vector2 lUpper[n];
1597b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    lUpper[0] = points[0];
1607b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    lUpper[1] = points[1];
1617b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
1627b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    int lUpperSize = 2;
1637b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
1647b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    for (int i = 2; i < n; i++) {
1657b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        lUpper[lUpperSize] = points[i];
1667b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        lUpperSize++;
1677b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
168f5ca8b4cb178008472e67fa0ae6a3e3fa75d7952ztenghui        while (lUpperSize > 2 && !ccw(
169f5ca8b4cb178008472e67fa0ae6a3e3fa75d7952ztenghui                lUpper[lUpperSize - 3].x, lUpper[lUpperSize - 3].y,
170f5ca8b4cb178008472e67fa0ae6a3e3fa75d7952ztenghui                lUpper[lUpperSize - 2].x, lUpper[lUpperSize - 2].y,
171f5ca8b4cb178008472e67fa0ae6a3e3fa75d7952ztenghui                lUpper[lUpperSize - 1].x, lUpper[lUpperSize - 1].y)) {
1727b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            // Remove the middle point of the three last
1737b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            lUpper[lUpperSize - 2].x = lUpper[lUpperSize - 1].x;
1747b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            lUpper[lUpperSize - 2].y = lUpper[lUpperSize - 1].y;
1757b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            lUpperSize--;
1767b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        }
1777b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    }
1787b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
1797b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    Vector2 lLower[n];
1807b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    lLower[0] = points[n - 1];
1817b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    lLower[1] = points[n - 2];
1827b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
1837b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    int lLowerSize = 2;
1847b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
1857b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    for (int i = n - 3; i >= 0; i--) {
1867b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        lLower[lLowerSize] = points[i];
1877b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        lLowerSize++;
1887b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
189f5ca8b4cb178008472e67fa0ae6a3e3fa75d7952ztenghui        while (lLowerSize > 2 && !ccw(
190f5ca8b4cb178008472e67fa0ae6a3e3fa75d7952ztenghui                lLower[lLowerSize - 3].x, lLower[lLowerSize - 3].y,
191f5ca8b4cb178008472e67fa0ae6a3e3fa75d7952ztenghui                lLower[lLowerSize - 2].x, lLower[lLowerSize - 2].y,
192f5ca8b4cb178008472e67fa0ae6a3e3fa75d7952ztenghui                lLower[lLowerSize - 1].x, lLower[lLowerSize - 1].y)) {
1937b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            // Remove the middle point of the three last
1947b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            lLower[lLowerSize - 2] = lLower[lLowerSize - 1];
1957b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            lLowerSize--;
1967b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        }
1977b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    }
1987b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
199726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik    // output points in CW ordering
200726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik    const int total = lUpperSize + lLowerSize - 2;
201726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik    int outIndex = total - 1;
2027b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    for (int i = 0; i < lUpperSize; i++) {
203726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik        retPoly[outIndex] = lUpper[i];
204726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik        outIndex--;
2057b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    }
2067b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
2077b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    for (int i = 1; i < lLowerSize - 1; i++) {
208726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik        retPoly[outIndex] = lLower[i];
209726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik        outIndex--;
2107b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    }
2117b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    // TODO: Add test harness which verify that all the points are inside the hull.
212726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik    return total;
2137b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui}
2147b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
2157b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
216f5ca8b4cb178008472e67fa0ae6a3e3fa75d7952ztenghui * Test whether the 3 points form a counter clockwise turn.
2177b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
2187b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @return true if a right hand turn
2197b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
2209122b1b168d2a74d51517ed7282f4d6a8adea367ztenghuibool SpotShadow::ccw(float ax, float ay, float bx, float by,
2219122b1b168d2a74d51517ed7282f4d6a8adea367ztenghui        float cx, float cy) {
2227b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) > EPSILON;
2237b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui}
2247b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
2257b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
2267b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * Sort points about a center point
2277b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
2287b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param poly The in and out polyogon as a Vector2 array.
2297b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param polyLength The number of vertices of the polygon.
2307b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param center the center ctr[0] = x , ctr[1] = y to sort around.
2317b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
2327b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghuivoid SpotShadow::sort(Vector2* poly, int polyLength, const Vector2& center) {
2337b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    quicksortCirc(poly, 0, polyLength - 1, center);
2347b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui}
2357b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
2367b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
2377b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * Swap points pointed to by i and j
2387b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
2397b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghuivoid SpotShadow::swap(Vector2* points, int i, int j) {
2407b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    Vector2 temp = points[i];
2417b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    points[i] = points[j];
2427b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    points[j] = temp;
2437b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui}
2447b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
2457b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
2467b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * quick sort implementation about the center.
2477b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
2487b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghuivoid SpotShadow::quicksortCirc(Vector2* points, int low, int high,
2497b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        const Vector2& center) {
2507b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    int i = low, j = high;
2517b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    int p = low + (high - low) / 2;
2527b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    float pivot = angle(points[p], center);
2537b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    while (i <= j) {
254726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik        while (angle(points[i], center) > pivot) {
2557b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            i++;
2567b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        }
257726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik        while (angle(points[j], center) < pivot) {
2587b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            j--;
2597b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        }
2607b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
2617b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        if (i <= j) {
2627b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            swap(points, i, j);
2637b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            i++;
2647b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            j--;
2657b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        }
2667b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    }
2677b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    if (low < j) quicksortCirc(points, low, j, center);
2687b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    if (i < high) quicksortCirc(points, i, high, center);
2697b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui}
2707b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
2717b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
2727b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * Sort points by x axis
2737b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
2747b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param points points to sort
2757b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param low start index
2767b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param high end index
2777b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
2787b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghuivoid SpotShadow::quicksortX(Vector2* points, int low, int high) {
2797b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    int i = low, j = high;
2807b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    int p = low + (high - low) / 2;
2817b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    float pivot = points[p].x;
2827b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    while (i <= j) {
2837b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        while (points[i].x < pivot) {
2847b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            i++;
2857b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        }
2867b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        while (points[j].x > pivot) {
2877b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            j--;
2887b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        }
2897b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
2907b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        if (i <= j) {
2917b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            swap(points, i, j);
2927b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            i++;
2937b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            j--;
2947b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        }
2957b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    }
2967b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    if (low < j) quicksortX(points, low, j);
2977b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    if (i < high) quicksortX(points, i, high);
2987b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui}
2997b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
3007b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
3017b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * Test whether a point is inside the polygon.
3027b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
3037b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param testPoint the point to test
3047b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param poly the polygon
3057b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @return true if the testPoint is inside the poly.
3067b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
3077b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghuibool SpotShadow::testPointInsidePolygon(const Vector2 testPoint,
3087b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        const Vector2* poly, int len) {
3097b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    bool c = false;
3109122b1b168d2a74d51517ed7282f4d6a8adea367ztenghui    float testx = testPoint.x;
3119122b1b168d2a74d51517ed7282f4d6a8adea367ztenghui    float testy = testPoint.y;
3127b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    for (int i = 0, j = len - 1; i < len; j = i++) {
3139122b1b168d2a74d51517ed7282f4d6a8adea367ztenghui        float startX = poly[j].x;
3149122b1b168d2a74d51517ed7282f4d6a8adea367ztenghui        float startY = poly[j].y;
3159122b1b168d2a74d51517ed7282f4d6a8adea367ztenghui        float endX = poly[i].x;
3169122b1b168d2a74d51517ed7282f4d6a8adea367ztenghui        float endY = poly[i].y;
3177b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
318512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        if (((endY > testy) != (startY > testy))
319512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui            && (testx < (startX - endX) * (testy - endY)
3207b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui             / (startY - endY) + endX)) {
3217b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui            c = !c;
3227b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        }
3237b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    }
3247b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    return c;
3257b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui}
3267b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
3277b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
3287b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * Make the polygon turn clockwise.
3297b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
3307b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param polygon the polygon as a Vector2 array.
3317b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param len the number of points of the polygon
3327b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
3337b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghuivoid SpotShadow::makeClockwise(Vector2* polygon, int len) {
3347b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    if (polygon == 0  || len == 0) {
3357b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        return;
3367b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    }
3372e023f3827dfc0dfc1ed7c3dd54d02b4a993f0b4ztenghui    if (!ShadowTessellator::isClockwise(polygon, len)) {
3387b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        reverse(polygon, len);
3397b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    }
3407b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui}
3417b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
3427b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
3437b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * Reverse the polygon
3447b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
3457b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param polygon the polygon as a Vector2 array
3467b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param len the number of points of the polygon
3477b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
3487b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghuivoid SpotShadow::reverse(Vector2* polygon, int len) {
3497b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    int n = len / 2;
3507b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    for (int i = 0; i < n; i++) {
3517b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        Vector2 tmp = polygon[i];
3527b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        int k = len - 1 - i;
3537b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        polygon[i] = polygon[k];
3547b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        polygon[k] = tmp;
3557b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    }
3567b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui}
3577b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
3587b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
3597b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * Compute a horizontal circular polygon about point (x , y , height) of radius
3607b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * (size)
3617b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
3627b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param points number of the points of the output polygon.
3637b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param lightCenter the center of the light.
3647b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param size the light size.
3657b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui * @param ret result polygon.
3667b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
3677b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghuivoid SpotShadow::computeLightPolygon(int points, const Vector3& lightCenter,
3687b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        float size, Vector3* ret) {
3697b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    // TODO: Caching all the sin / cos values and store them in a look up table.
3707b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    for (int i = 0; i < points; i++) {
3719122b1b168d2a74d51517ed7282f4d6a8adea367ztenghui        float angle = 2 * i * M_PI / points;
372726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik        ret[i].x = cosf(angle) * size + lightCenter.x;
373726118b35240957710d4d85fb5747e2ba8b934f7Chris Craik        ret[i].y = sinf(angle) * size + lightCenter.y;
3747b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui        ret[i].z = lightCenter.z;
3757b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui    }
3767b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui}
3777b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
3787b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
379512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * From light center, project one vertex to the z=0 surface and get the outline.
3807b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
381512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * @param outline The result which is the outline position.
382512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * @param lightCenter The center of light.
383512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * @param polyVertex The input polygon's vertex.
384512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui *
385512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * @return float The ratio of (polygon.z / light.z - polygon.z)
3867b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui */
387c50a03d78aaedd0003377e98710e7038bda330e9ztenghuifloat SpotShadow::projectCasterToOutline(Vector2& outline,
388c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        const Vector3& lightCenter, const Vector3& polyVertex) {
389c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    float lightToPolyZ = lightCenter.z - polyVertex.z;
390c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    float ratioZ = CASTER_Z_CAP_RATIO;
391c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    if (lightToPolyZ != 0) {
392c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // If any caster's vertex is almost above the light, we just keep it as 95%
393c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // of the height of the light.
3943bd3fa1f1d437e22aee35381a559dcee15a437ddztenghui        ratioZ = MathUtils::clamp(polyVertex.z / lightToPolyZ, 0.0f, CASTER_Z_CAP_RATIO);
395c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    }
396c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
397c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    outline.x = polyVertex.x - ratioZ * (lightCenter.x - polyVertex.x);
398c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    outline.y = polyVertex.y - ratioZ * (lightCenter.y - polyVertex.y);
399c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    return ratioZ;
400c50a03d78aaedd0003377e98710e7038bda330e9ztenghui}
401c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
402c50a03d78aaedd0003377e98710e7038bda330e9ztenghui/**
403c50a03d78aaedd0003377e98710e7038bda330e9ztenghui * Generate the shadow spot light of shape lightPoly and a object poly
404c50a03d78aaedd0003377e98710e7038bda330e9ztenghui *
405c50a03d78aaedd0003377e98710e7038bda330e9ztenghui * @param isCasterOpaque whether the caster is opaque
406c50a03d78aaedd0003377e98710e7038bda330e9ztenghui * @param lightCenter the center of the light
407c50a03d78aaedd0003377e98710e7038bda330e9ztenghui * @param lightSize the radius of the light
408c50a03d78aaedd0003377e98710e7038bda330e9ztenghui * @param poly x,y,z vertexes of a convex polygon that occludes the light source
409c50a03d78aaedd0003377e98710e7038bda330e9ztenghui * @param polyLength number of vertexes of the occluding polygon
410c50a03d78aaedd0003377e98710e7038bda330e9ztenghui * @param shadowTriangleStrip return an (x,y,alpha) triangle strip representing the shadow. Return
411c50a03d78aaedd0003377e98710e7038bda330e9ztenghui *                            empty strip if error.
412c50a03d78aaedd0003377e98710e7038bda330e9ztenghui */
413c50a03d78aaedd0003377e98710e7038bda330e9ztenghuivoid SpotShadow::createSpotShadow(bool isCasterOpaque, const Vector3& lightCenter,
414c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        float lightSize, const Vector3* poly, int polyLength, const Vector3& polyCentroid,
415c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        VertexBuffer& shadowTriangleStrip) {
4163bd3fa1f1d437e22aee35381a559dcee15a437ddztenghui    if (CC_UNLIKELY(lightCenter.z <= 0)) {
4173bd3fa1f1d437e22aee35381a559dcee15a437ddztenghui        ALOGW("Relative Light Z is not positive. No spot shadow!");
4183bd3fa1f1d437e22aee35381a559dcee15a437ddztenghui        return;
4193bd3fa1f1d437e22aee35381a559dcee15a437ddztenghui    }
420512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    if (CC_UNLIKELY(polyLength < 3)) {
421512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#if DEBUG_SHADOW
422512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        ALOGW("Invalid polygon length. No spot shadow!");
423512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#endif
424512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        return;
425512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    }
426c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    OutlineData outlineData[polyLength];
427c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    Vector2 outlineCentroid;
428c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    // Calculate the projected outline for each polygon's vertices from the light center.
429c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    //
430c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    //                       O     Light
431c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    //                      /
432c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    //                    /
433c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    //                   .     Polygon vertex
434c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    //                 /
435c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    //               /
436c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    //              O     Outline vertices
437c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    //
438c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    // Ratio = (Poly - Outline) / (Light - Poly)
439c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    // Outline.x = Poly.x - Ratio * (Light.x - Poly.x)
440c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    // Outline's radius / Light's radius = Ratio
441c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
442c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    // Compute the last outline vertex to make sure we can get the normal and outline
443c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    // in one single loop.
444c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    projectCasterToOutline(outlineData[polyLength - 1].position, lightCenter,
445c50a03d78aaedd0003377e98710e7038bda330e9ztenghui            poly[polyLength - 1]);
446c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
447c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    // Take the outline's polygon, calculate the normal for each outline edge.
448c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    int currentNormalIndex = polyLength - 1;
449c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    int nextNormalIndex = 0;
450c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
451c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    for (int i = 0; i < polyLength; i++) {
452c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        float ratioZ = projectCasterToOutline(outlineData[i].position,
453c50a03d78aaedd0003377e98710e7038bda330e9ztenghui                lightCenter, poly[i]);
454c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        outlineData[i].radius = ratioZ * lightSize;
455c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
456c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        outlineData[currentNormalIndex].normal = ShadowTessellator::calculateNormal(
457c50a03d78aaedd0003377e98710e7038bda330e9ztenghui                outlineData[currentNormalIndex].position,
458c50a03d78aaedd0003377e98710e7038bda330e9ztenghui                outlineData[nextNormalIndex].position);
459c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        currentNormalIndex = (currentNormalIndex + 1) % polyLength;
460c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        nextNormalIndex++;
461c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    }
462c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
463c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    projectCasterToOutline(outlineCentroid, lightCenter, polyCentroid);
464c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
465c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    int penumbraIndex = 0;
466512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // Then each polygon's vertex produce at minmal 2 penumbra vertices.
467512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // Since the size can be dynamic here, we keep track of the size and update
468512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // the real size at the end.
469512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    int allocatedPenumbraLength = 2 * polyLength + SPOT_MAX_EXTRA_CORNER_VERTEX_NUMBER;
470512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    Vector2 penumbra[allocatedPenumbraLength];
471512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    int totalExtraCornerSliceNumber = 0;
472c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
473c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    Vector2 umbra[polyLength];
474c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
475512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // When centroid is covered by all circles from outline, then we consider
476512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // the umbra is invalid, and we will tune down the shadow strength.
477c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    bool hasValidUmbra = true;
478512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // We need the minimal of RaitoVI to decrease the spot shadow strength accordingly.
479512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    float minRaitoVI = FLT_MAX;
480c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
481c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    for (int i = 0; i < polyLength; i++) {
482c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // Generate all the penumbra's vertices only using the (outline vertex + normal * radius)
483c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // There is no guarantee that the penumbra is still convex, but for
484c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // each outline vertex, it will connect to all its corresponding penumbra vertices as
485c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // triangle fans. And for neighber penumbra vertex, it will be a trapezoid.
486c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //
487c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // Penumbra Vertices marked as Pi
488c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // Outline Vertices marked as Vi
489c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //                                            (P3)
490c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //          (P2)                               |     ' (P4)
491c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //   (P1)'   |                                 |   '
492c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //         ' |                                 | '
493c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // (P0)  ------------------------------------------------(P5)
494c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           | (V0)                            |(V1)
495c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |                                 |
496c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |                                 |
497c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |                                 |
498c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |                                 |
499c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |                                 |
500c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |                                 |
501c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |                                 |
502c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |                                 |
503c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //       (V3)-----------------------------------(V2)
504c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        int preNormalIndex = (i + polyLength - 1) % polyLength;
505c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
506512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        const Vector2& previousNormal = outlineData[preNormalIndex].normal;
507512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        const Vector2& currentNormal = outlineData[i].normal;
508512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
509512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        // Depending on how roundness we want for each corner, we can subdivide
510c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // further here and/or introduce some heuristic to decide how much the
511c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // subdivision should be.
512512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        int currentExtraSliceNumber = ShadowTessellator::getExtraVertexNumber(
513512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui                previousNormal, currentNormal, SPOT_CORNER_RADIANS_DIVISOR);
514c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
515512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        int currentCornerSliceNumber = 1 + currentExtraSliceNumber;
516512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        totalExtraCornerSliceNumber += currentExtraSliceNumber;
517512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#if DEBUG_SHADOW
518512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        ALOGD("currentExtraSliceNumber should be %d", currentExtraSliceNumber);
519512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        ALOGD("currentCornerSliceNumber should be %d", currentCornerSliceNumber);
520512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        ALOGD("totalCornerSliceNumber is %d", totalExtraCornerSliceNumber);
521512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#endif
522512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        if (CC_UNLIKELY(totalExtraCornerSliceNumber > SPOT_MAX_EXTRA_CORNER_VERTEX_NUMBER)) {
523512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui            currentCornerSliceNumber = 1;
524512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        }
525512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        for (int k = 0; k <= currentCornerSliceNumber; k++) {
526512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui            Vector2 avgNormal =
527512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui                    (previousNormal * (currentCornerSliceNumber - k) + currentNormal * k) /
528512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui                    currentCornerSliceNumber;
529512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui            avgNormal.normalize();
530512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui            penumbra[penumbraIndex++] = outlineData[i].position +
531512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui                    avgNormal * outlineData[i].radius;
532512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        }
533c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
534c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
535c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // Compute the umbra by the intersection from the outline's centroid!
536c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //
537c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //       (V) ------------------------------------
538c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |          '                       |
539c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |         '                        |
540c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |       ' (I)                      |
541c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |    '                             |
542c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           | '             (C)                |
543c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |                                  |
544c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |                                  |
545c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |                                  |
546c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           |                                  |
547c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //           ------------------------------------
548c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //
549c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // Connect a line b/t the outline vertex (V) and the centroid (C), it will
550c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // intersect with the outline vertex's circle at point (I).
551c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // Now, ratioVI = VI / VC, ratioIC = IC / VC
552c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // Then the intersetion point can be computed as Ixy = Vxy * ratioIC + Cxy * ratioVI;
553c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        //
554512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        // When all of the outline circles cover the the outline centroid, (like I is
555c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // on the other side of C), there is no real umbra any more, so we just fake
556c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // a small area around the centroid as the umbra, and tune down the spot
557c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // shadow's umbra strength to simulate the effect the whole shadow will
558c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // become lighter in this case.
559c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // The ratio can be simulated by using the inverse of maximum of ratioVI for
560c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // all (V).
561512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        float distOutline = (outlineData[i].position - outlineCentroid).length();
5623bd3fa1f1d437e22aee35381a559dcee15a437ddztenghui        if (CC_UNLIKELY(distOutline == 0)) {
563c50a03d78aaedd0003377e98710e7038bda330e9ztenghui            // If the outline has 0 area, then there is no spot shadow anyway.
564c50a03d78aaedd0003377e98710e7038bda330e9ztenghui            ALOGW("Outline has 0 area, no spot shadow!");
565c50a03d78aaedd0003377e98710e7038bda330e9ztenghui            return;
566c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        }
567512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
568512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        float ratioVI = outlineData[i].radius / distOutline;
569512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        minRaitoVI = MathUtils::min(minRaitoVI, ratioVI);
570512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        if (ratioVI >= (1 - FAKE_UMBRA_SIZE_RATIO)) {
571512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui            ratioVI = (1 - FAKE_UMBRA_SIZE_RATIO);
572c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        }
573c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // When we know we don't have valid umbra, don't bother to compute the
574c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // values below. But we can't skip the loop yet since we want to know the
575c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        // maximum ratio.
576512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        float ratioIC = 1 - ratioVI;
577512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        umbra[i] = outlineData[i].position * ratioIC + outlineCentroid * ratioVI;
578c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    }
579c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
580512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    hasValidUmbra = (minRaitoVI <= 1.0);
581c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    float shadowStrengthScale = 1.0;
582c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    if (!hasValidUmbra) {
583512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#if DEBUG_SHADOW
584c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        ALOGW("The object is too close to the light or too small, no real umbra!");
585512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#endif
586c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        for (int i = 0; i < polyLength; i++) {
587c50a03d78aaedd0003377e98710e7038bda330e9ztenghui            umbra[i] = outlineData[i].position * FAKE_UMBRA_SIZE_RATIO +
588512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui                    outlineCentroid * (1 - FAKE_UMBRA_SIZE_RATIO);
589c50a03d78aaedd0003377e98710e7038bda330e9ztenghui        }
590512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        shadowStrengthScale = 1.0 / minRaitoVI;
591c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    }
592c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
593512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    int penumbraLength = penumbraIndex;
594512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    int umbraLength = polyLength;
595512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
596c50a03d78aaedd0003377e98710e7038bda330e9ztenghui#if DEBUG_SHADOW
597512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    ALOGD("penumbraLength is %d , allocatedPenumbraLength %d", penumbraLength, allocatedPenumbraLength);
598c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    dumpPolygon(poly, polyLength, "input poly");
599c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    dumpPolygon(penumbra, penumbraLength, "penumbra");
600512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    dumpPolygon(umbra, umbraLength, "umbra");
601c50a03d78aaedd0003377e98710e7038bda330e9ztenghui    ALOGD("hasValidUmbra is %d and shadowStrengthScale is %f", hasValidUmbra, shadowStrengthScale);
602c50a03d78aaedd0003377e98710e7038bda330e9ztenghui#endif
603c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
604512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // The penumbra and umbra needs to be in convex shape to keep consistency
605512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // and quality.
606512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // Since we are still shooting rays to penumbra, it needs to be convex.
607512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // Umbra can be represented as a fan from the centroid, but visually umbra
608512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    // looks nicer when it is convex.
609512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    Vector2 finalUmbra[umbraLength];
610512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    Vector2 finalPenumbra[penumbraLength];
611512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    int finalUmbraLength = hull(umbra, umbraLength, finalUmbra);
612512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    int finalPenumbraLength = hull(penumbra, penumbraLength, finalPenumbra);
613512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
614512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    generateTriangleStrip(isCasterOpaque, shadowStrengthScale, finalPenumbra,
615512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui            finalPenumbraLength, finalUmbra, finalUmbraLength, poly, polyLength,
616512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui            shadowTriangleStrip, outlineCentroid);
617512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
618c50a03d78aaedd0003377e98710e7038bda330e9ztenghui}
619c50a03d78aaedd0003377e98710e7038bda330e9ztenghui
6207b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui/**
621512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * This is only for experimental purpose.
622512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * After intersections are calculated, we could smooth the polygon if needed.
623512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * So far, we don't think it is more appealing yet.
6247b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui *
625512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * @param level The level of smoothness.
626512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * @param rays The total number of rays.
627512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui * @param rayDist (In and Out) The distance for each ray.
628512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui *
629512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui */
630512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghuivoid SpotShadow::smoothPolygon(int level, int rays, float* rayDist) {
631512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    for (int k = 0; k < level; k++) {
632512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        for (int i = 0; i < rays; i++) {
633512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui            float p1 = rayDist[(rays - 1 + i) % rays];
634512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui            float p2 = rayDist[i];
635512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui            float p3 = rayDist[(i + 1) % rays];
636512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui            rayDist[i] = (p1 + p2 * 2 + p3) / 4;
637512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        }
638512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    }
639512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui}
640512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
641d2dcd6fded3a036f334a88bf9593398833f2919aztenghui// Index pair is meant for storing the tessellation information for the penumbra
642d2dcd6fded3a036f334a88bf9593398833f2919aztenghui// area. One index must come from exterior tangent of the circles, the other one
643d2dcd6fded3a036f334a88bf9593398833f2919aztenghui// must come from the interior tangent of the circles.
644d2dcd6fded3a036f334a88bf9593398833f2919aztenghuistruct IndexPair {
645d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    int outerIndex;
646d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    int innerIndex;
647d2dcd6fded3a036f334a88bf9593398833f2919aztenghui};
6487b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
649d2dcd6fded3a036f334a88bf9593398833f2919aztenghui// For one penumbra vertex, find the cloest umbra vertex and return its index.
650d2dcd6fded3a036f334a88bf9593398833f2919aztenghuiinline int getClosestUmbraIndex(const Vector2& pivot, const Vector2* polygon, int polygonLength) {
651d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    float minLengthSquared = FLT_MAX;
652d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    int resultIndex = -1;
653d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    bool hasDecreased = false;
654d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    // Starting with some negative offset, assuming both umbra and penumbra are starting
655d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    // at the same angle, this can help to find the result faster.
656d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    // Normally, loop 3 times, we can find the closest point.
657d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    int offset = polygonLength - 2;
658d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    for (int i = 0; i < polygonLength; i++) {
659d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        int currentIndex = (i + offset) % polygonLength;
660d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        float currentLengthSquared = (pivot - polygon[currentIndex]).lengthSquared();
661d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        if (currentLengthSquared < minLengthSquared) {
662d2dcd6fded3a036f334a88bf9593398833f2919aztenghui            if (minLengthSquared != FLT_MAX) {
663d2dcd6fded3a036f334a88bf9593398833f2919aztenghui                hasDecreased = true;
664d2dcd6fded3a036f334a88bf9593398833f2919aztenghui            }
665d2dcd6fded3a036f334a88bf9593398833f2919aztenghui            minLengthSquared = currentLengthSquared;
666d2dcd6fded3a036f334a88bf9593398833f2919aztenghui            resultIndex = currentIndex;
667d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        } else if (currentLengthSquared > minLengthSquared && hasDecreased) {
668d2dcd6fded3a036f334a88bf9593398833f2919aztenghui            // Early break b/c we have found the closet one and now the length
669d2dcd6fded3a036f334a88bf9593398833f2919aztenghui            // is increasing again.
670d2dcd6fded3a036f334a88bf9593398833f2919aztenghui            break;
671512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        }
672512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    }
673d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    if(resultIndex == -1) {
674d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        ALOGE("resultIndex is -1, the polygon must be invalid!");
675d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        resultIndex = 0;
676d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    }
677d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    return resultIndex;
678512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui}
6797b4516e7ea552ad08d6e7277d311ef11bd8f12e8ztenghui
6803932063bc75dc1e4efc2c428ca208d2e2290164dztenghui// Allow some epsilon here since the later ray intersection did allow for some small
6813932063bc75dc1e4efc2c428ca208d2e2290164dztenghui// floating point error, when the intersection point is slightly outside the segment.
682d2dcd6fded3a036f334a88bf9593398833f2919aztenghuiinline bool sameDirections(bool isPositiveCross, float a, float b) {
683d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    if (isPositiveCross) {
6843932063bc75dc1e4efc2c428ca208d2e2290164dztenghui        return a >= -EPSILON && b >= -EPSILON;
685d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    } else {
6863932063bc75dc1e4efc2c428ca208d2e2290164dztenghui        return a <= EPSILON && b <= EPSILON;
687512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    }
688512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui}
689512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
690d2dcd6fded3a036f334a88bf9593398833f2919aztenghui// Find the right polygon edge to shoot the ray at.
691d2dcd6fded3a036f334a88bf9593398833f2919aztenghuiinline int findPolyIndex(bool isPositiveCross, int startPolyIndex, const Vector2& umbraDir,
692d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        const Vector2* polyToCentroid, int polyLength) {
693d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    // Make sure we loop with a bound.
694d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    for (int i = 0; i < polyLength; i++) {
695d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        int currentIndex = (i + startPolyIndex) % polyLength;
696d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        const Vector2& currentToCentroid = polyToCentroid[currentIndex];
697d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        const Vector2& nextToCentroid = polyToCentroid[(currentIndex + 1) % polyLength];
698d2dcd6fded3a036f334a88bf9593398833f2919aztenghui
699d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        float currentCrossUmbra = currentToCentroid.cross(umbraDir);
700d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        float umbraCrossNext = umbraDir.cross(nextToCentroid);
701d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        if (sameDirections(isPositiveCross, currentCrossUmbra, umbraCrossNext)) {
702512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#if DEBUG_SHADOW
703d2dcd6fded3a036f334a88bf9593398833f2919aztenghui            ALOGD("findPolyIndex loop %d times , index %d", i, currentIndex );
704512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui#endif
705d2dcd6fded3a036f334a88bf9593398833f2919aztenghui            return currentIndex;
706512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui        }
707512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui    }
708d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    LOG_ALWAYS_FATAL("Can't find the right polygon's edge from startPolyIndex %d", startPolyIndex);
709d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    return -1;
710512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui}
711512e643ce83b1d48ad9630a3622276f795cf4fb2ztenghui
712d2dcd6fded3a036f334a88bf9593398833f2919aztenghui// Generate the index pair for penumbra / umbra vertices, and more penumbra vertices
713d2dcd6fded3a036f334a88bf9593398833f2919aztenghui// if needed.
714d2dcd6fded3a036f334a88bf9593398833f2919aztenghuiinline void genNewPenumbraAndPairWithUmbra(const Vector2* penumbra, int penumbraLength,
715d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        const Vector2* umbra, int umbraLength, Vector2* newPenumbra, int& newPenumbraIndex,
716d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        IndexPair* verticesPair, int& verticesPairIndex) {
717d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    // In order to keep everything in just one loop, we need to pre-compute the
718d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    // closest umbra vertex for the last penumbra vertex.
719d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    int previousClosestUmbraIndex = getClosestUmbraIndex(penumbra[penumbraLength - 1],
720d2dcd6fded3a036f334a88bf9593398833f2919aztenghui            umbra, umbraLength);
721d2dcd6fded3a036f334a88bf9593398833f2919aztenghui    for (int i = 0; i < penumbraLength; i++) {
722d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        const Vector2& currentPenumbraVertex = penumbra[i];
723d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        // For current penumbra vertex, starting from previousClosestUmbraIndex,
724d2dcd6fded3a036f334a88bf9593398833f2919aztenghui        // then check the next one until the distance increase.
725