1/*
2 * Copyright (C) 2013 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/**
20 * Extra vertices for the corner for smoother corner.
21 * Only for outer vertices.
22 * Note that we use such extra memory to avoid an extra loop.
23 */
24// For half circle, we could add EXTRA_VERTEX_PER_PI vertices.
25// Set to 1 if we don't want to have any.
26#define EXTRA_CORNER_VERTEX_PER_PI 12
27
28// For the whole polygon, the sum of all the deltas b/t normals is 2 * M_PI,
29// therefore, the maximum number of extra vertices will be twice bigger.
30#define MAX_EXTRA_CORNER_VERTEX_NUMBER  (2 * EXTRA_CORNER_VERTEX_PER_PI)
31
32// For each RADIANS_DIVISOR, we would allocate one more vertex b/t the normals.
33#define CORNER_RADIANS_DIVISOR (M_PI / EXTRA_CORNER_VERTEX_PER_PI)
34
35/**
36 * Extra vertices for the Edge for interpolation artifacts.
37 * Same value for both inner and outer vertices.
38 */
39#define EXTRA_EDGE_VERTEX_PER_PI 50
40
41#define MAX_EXTRA_EDGE_VERTEX_NUMBER  (2 * EXTRA_EDGE_VERTEX_PER_PI)
42
43#define EDGE_RADIANS_DIVISOR  (M_PI / EXTRA_EDGE_VERTEX_PER_PI)
44
45/**
46 * Other constants:
47 */
48// For the edge of the penumbra, the opacity is 0. After transform (1 - alpha),
49// it is 1.
50#define TRANSFORMED_OUTER_OPACITY (1.0f)
51
52// Once the alpha difference is greater than this threshold, we will allocate extra
53// edge vertices.
54// If this is set to negative value, then all the edge will be tessellated.
55#define ALPHA_THRESHOLD (0.1f / 255.0f)
56
57#include <math.h>
58#include <utils/Log.h>
59#include <utils/Vector.h>
60
61#include "AmbientShadow.h"
62#include "ShadowTessellator.h"
63#include "Vertex.h"
64#include "VertexBuffer.h"
65#include "utils/MathUtils.h"
66
67namespace android {
68namespace uirenderer {
69
70/**
71 *  Local utility functions.
72 */
73inline Vector2 getNormalFromVertices(const Vector3* vertices, int current, int next) {
74    // Convert from Vector3 to Vector2 first.
75    Vector2 currentVertex = { vertices[current].x, vertices[current].y };
76    Vector2 nextVertex = { vertices[next].x, vertices[next].y };
77
78    return ShadowTessellator::calculateNormal(currentVertex, nextVertex);
79}
80
81// The input z value will be converted to be non-negative inside.
82// The output must be ranged from 0 to 1.
83inline float getAlphaFromFactoredZ(float factoredZ) {
84    return 1.0 / (1 + MathUtils::max(factoredZ, 0.0f));
85}
86
87// The shader is using gaussian function e^-(1-x)*(1-x)*4, therefore, we transform
88// the alpha value to (1 - alpha)
89inline float getTransformedAlphaFromAlpha(float alpha) {
90    return 1.0f - alpha;
91}
92
93// The output is ranged from 0 to 1.
94inline float getTransformedAlphaFromFactoredZ(float factoredZ) {
95    return getTransformedAlphaFromAlpha(getAlphaFromFactoredZ(factoredZ));
96}
97
98inline int getEdgeExtraAndUpdateSpike(Vector2* currentSpike,
99        const Vector3& secondVertex, const Vector3& centroid) {
100    Vector2 secondSpike  = {secondVertex.x - centroid.x, secondVertex.y - centroid.y};
101    secondSpike.normalize();
102
103    int result = ShadowTessellator::getExtraVertexNumber(secondSpike, *currentSpike,
104            EDGE_RADIANS_DIVISOR);
105    *currentSpike = secondSpike;
106    return result;
107}
108
109// Given the caster's vertex count, compute all the buffers size depending on
110// whether or not the caster is opaque.
111inline void computeBufferSize(int* totalVertexCount, int* totalIndexCount,
112        int* totalUmbraCount, int casterVertexCount, bool isCasterOpaque) {
113    // Compute the size of the vertex buffer.
114    int outerVertexCount = casterVertexCount * 2 + MAX_EXTRA_CORNER_VERTEX_NUMBER +
115        MAX_EXTRA_EDGE_VERTEX_NUMBER;
116    int innerVertexCount = casterVertexCount + MAX_EXTRA_EDGE_VERTEX_NUMBER;
117    *totalVertexCount = outerVertexCount + innerVertexCount;
118
119    // Compute the size of the index buffer.
120    *totalIndexCount = 2 * outerVertexCount + 2;
121
122    // Compute the size of the umber buffer.
123    // For translucent object, keep track of the umbra(inner) vertex in order to draw
124    // inside. We only need to store the index information.
125    *totalUmbraCount = 0;
126    if (!isCasterOpaque) {
127        // Add the centroid if occluder is translucent.
128        (*totalVertexCount)++;
129        *totalIndexCount += 2 * innerVertexCount + 1;
130        *totalUmbraCount = innerVertexCount;
131    }
132}
133
134inline bool needsExtraForEdge(float firstAlpha, float secondAlpha) {
135    return fabsf(firstAlpha - secondAlpha) > ALPHA_THRESHOLD;
136}
137
138/**
139 * Calculate the shadows as a triangle strips while alpha value as the
140 * shadow values.
141 *
142 * @param isCasterOpaque Whether the caster is opaque.
143 * @param vertices The shadow caster's polygon, which is represented in a Vector3
144 *                  array.
145 * @param vertexCount The length of caster's polygon in terms of number of
146 *                    vertices.
147 * @param centroid3d The centroid of the shadow caster.
148 * @param heightFactor The factor showing the higher the object, the lighter the
149 *                     shadow.
150 * @param geomFactor The factor scaling the geometry expansion along the normal.
151 *
152 * @param shadowVertexBuffer Return an floating point array of (x, y, a)
153 *               triangle strips mode.
154 *
155 * An simple illustration:
156 * For now let's mark the outer vertex as Pi, the inner as Vi, the centroid as C.
157 *
158 * First project the occluder to the Z=0 surface.
159 * Then we got all the inner vertices. And we compute the normal for each edge.
160 * According to the normal, we generate outer vertices. E.g: We generate P1 / P4
161 * as extra corner vertices to make the corner looks round and smoother.
162 *
163 * Due to the fact that the alpha is not linear interpolated along the inner
164 * edge, when the alpha is different, we may add extra vertices such as P2.1, P2.2,
165 * V0.1, V0.2 to avoid the visual artifacts.
166 *
167 *                                            (P3)
168 *          (P2)     (P2.1)     (P2.2)         |     ' (P4)
169 *   (P1)'   |        |           |            |   '
170 *         ' |        |           |            | '
171 * (P0)  ------------------------------------------------(P5)
172 *           | (V0)   (V0.1)    (V0.2)         |(V1)
173 *           |                                 |
174 *           |                                 |
175 *           |               (C)               |
176 *           |                                 |
177 *           |                                 |
178 *           |                                 |
179 *           |                                 |
180 *        (V3)-----------------------------------(V2)
181 */
182void AmbientShadow::createAmbientShadow(bool isCasterOpaque,
183        const Vector3* casterVertices, int casterVertexCount, const Vector3& centroid3d,
184        float heightFactor, float geomFactor, VertexBuffer& shadowVertexBuffer) {
185    shadowVertexBuffer.setMeshFeatureFlags(VertexBuffer::kAlpha | VertexBuffer::kIndices);
186
187    // In order to computer the outer vertices in one loop, we need pre-compute
188    // the normal by the vertex (n - 1) to vertex 0, and the spike and alpha value
189    // for vertex 0.
190    Vector2 previousNormal = getNormalFromVertices(casterVertices,
191            casterVertexCount - 1 , 0);
192    Vector2 currentSpike = {casterVertices[0].x - centroid3d.x,
193        casterVertices[0].y - centroid3d.y};
194    currentSpike.normalize();
195    float currentAlpha = getAlphaFromFactoredZ(casterVertices[0].z * heightFactor);
196
197    // Preparing all the output data.
198    int totalVertexCount, totalIndexCount, totalUmbraCount;
199    computeBufferSize(&totalVertexCount, &totalIndexCount, &totalUmbraCount,
200            casterVertexCount, isCasterOpaque);
201    AlphaVertex* shadowVertices =
202            shadowVertexBuffer.alloc<AlphaVertex>(totalVertexCount);
203    int vertexBufferIndex = 0;
204    uint16_t* indexBuffer = shadowVertexBuffer.allocIndices<uint16_t>(totalIndexCount);
205    int indexBufferIndex = 0;
206    uint16_t umbraVertices[totalUmbraCount];
207    int umbraIndex = 0;
208
209    for (int i = 0; i < casterVertexCount; i++)  {
210        // Corner: first figure out the extra vertices we need for the corner.
211        const Vector3& innerVertex = casterVertices[i];
212        Vector2 currentNormal = getNormalFromVertices(casterVertices, i,
213                (i + 1) % casterVertexCount);
214
215        int extraVerticesNumber = ShadowTessellator::getExtraVertexNumber(currentNormal,
216                previousNormal, CORNER_RADIANS_DIVISOR);
217
218        float expansionDist = innerVertex.z * heightFactor * geomFactor;
219        const int cornerSlicesNumber = extraVerticesNumber + 1; // Minimal as 1.
220#if DEBUG_SHADOW
221        ALOGD("cornerSlicesNumber is %d", cornerSlicesNumber);
222#endif
223
224        // Corner: fill the corner Vertex Buffer(VB) and Index Buffer(IB).
225        // We fill the inner vertex first, such that we can fill the index buffer
226        // inside the loop.
227        int currentInnerVertexIndex = vertexBufferIndex;
228        if (!isCasterOpaque) {
229            umbraVertices[umbraIndex++] = vertexBufferIndex;
230        }
231        AlphaVertex::set(&shadowVertices[vertexBufferIndex++], casterVertices[i].x,
232                casterVertices[i].y,
233                getTransformedAlphaFromAlpha(currentAlpha));
234
235        const Vector3& innerStart = casterVertices[i];
236
237        // outerStart is the first outer vertex for this inner vertex.
238        // outerLast is the last outer vertex for this inner vertex.
239        Vector2 outerStart = {0, 0};
240        Vector2 outerLast = {0, 0};
241        // This will create vertices from [0, cornerSlicesNumber] inclusively,
242        // which means minimally 2 vertices even without the extra ones.
243        for (int j = 0; j <= cornerSlicesNumber; j++) {
244            Vector2 averageNormal =
245                previousNormal * (cornerSlicesNumber - j) + currentNormal * j;
246            averageNormal /= cornerSlicesNumber;
247            averageNormal.normalize();
248            Vector2 outerVertex;
249            outerVertex.x = innerVertex.x + averageNormal.x * expansionDist;
250            outerVertex.y = innerVertex.y + averageNormal.y * expansionDist;
251
252            indexBuffer[indexBufferIndex++] = vertexBufferIndex;
253            indexBuffer[indexBufferIndex++] = currentInnerVertexIndex;
254            AlphaVertex::set(&shadowVertices[vertexBufferIndex++], outerVertex.x,
255                    outerVertex.y, TRANSFORMED_OUTER_OPACITY);
256
257            if (j == 0) {
258                outerStart = outerVertex;
259            } else if (j == cornerSlicesNumber) {
260                outerLast = outerVertex;
261            }
262        }
263        previousNormal = currentNormal;
264
265        // Edge: first figure out the extra vertices needed for the edge.
266        const Vector3& innerNext = casterVertices[(i + 1) % casterVertexCount];
267        float nextAlpha = getAlphaFromFactoredZ(innerNext.z * heightFactor);
268        if (needsExtraForEdge(currentAlpha, nextAlpha)) {
269            // TODO: See if we can / should cache this outer vertex across the loop.
270            Vector2 outerNext;
271            float expansionDist = innerNext.z * heightFactor * geomFactor;
272            outerNext.x = innerNext.x + currentNormal.x * expansionDist;
273            outerNext.y = innerNext.y + currentNormal.y * expansionDist;
274
275            // Compute the angle and see how many extra points we need.
276            int extraVerticesNumber = getEdgeExtraAndUpdateSpike(&currentSpike,
277                    innerNext, centroid3d);
278#if DEBUG_SHADOW
279            ALOGD("extraVerticesNumber %d for edge %d", extraVerticesNumber, i);
280#endif
281            // Edge: fill the edge's VB and IB.
282            // This will create vertices pair from [1, extraVerticesNumber - 1].
283            // If there is no extra vertices created here, the edge will be drawn
284            // as just 2 triangles.
285            for (int k = 1; k < extraVerticesNumber; k++) {
286                int startWeight = extraVerticesNumber - k;
287                Vector2 currentOuter =
288                    (outerLast * startWeight + outerNext * k) / extraVerticesNumber;
289                indexBuffer[indexBufferIndex++] = vertexBufferIndex;
290                AlphaVertex::set(&shadowVertices[vertexBufferIndex++], currentOuter.x,
291                        currentOuter.y, TRANSFORMED_OUTER_OPACITY);
292
293                if (!isCasterOpaque) {
294                    umbraVertices[umbraIndex++] = vertexBufferIndex;
295                }
296                Vector3 currentInner =
297                    (innerStart * startWeight + innerNext * k) / extraVerticesNumber;
298                indexBuffer[indexBufferIndex++] = vertexBufferIndex;
299                AlphaVertex::set(&shadowVertices[vertexBufferIndex++], currentInner.x,
300                        currentInner.y,
301                        getTransformedAlphaFromFactoredZ(currentInner.z * heightFactor));
302            }
303        }
304        currentAlpha = nextAlpha;
305    }
306
307    indexBuffer[indexBufferIndex++] = 1;
308    indexBuffer[indexBufferIndex++] = 0;
309
310    if (!isCasterOpaque) {
311        // Add the centroid as the last one in the vertex buffer.
312        float centroidOpacity =
313            getTransformedAlphaFromFactoredZ(centroid3d.z * heightFactor);
314        int centroidIndex = vertexBufferIndex;
315        AlphaVertex::set(&shadowVertices[vertexBufferIndex++], centroid3d.x,
316                centroid3d.y, centroidOpacity);
317
318        for (int i = 0; i < umbraIndex; i++) {
319            // Note that umbraVertices[0] is always 0.
320            // So the start and the end of the umbra are using the "0".
321            // And penumbra ended with 0, so a degenerated triangle is formed b/t
322            // the umbra and penumbra.
323            indexBuffer[indexBufferIndex++] = umbraVertices[i];
324            indexBuffer[indexBufferIndex++] = centroidIndex;
325        }
326        indexBuffer[indexBufferIndex++] = 0;
327    }
328
329    // At the end, update the real index and vertex buffer size.
330    shadowVertexBuffer.updateVertexCount(vertexBufferIndex);
331    shadowVertexBuffer.updateIndexCount(indexBufferIndex);
332    shadowVertexBuffer.computeBounds<AlphaVertex>();
333
334    ShadowTessellator::checkOverflow(vertexBufferIndex, totalVertexCount, "Ambient Vertex Buffer");
335    ShadowTessellator::checkOverflow(indexBufferIndex, totalIndexCount, "Ambient Index Buffer");
336    ShadowTessellator::checkOverflow(umbraIndex, totalUmbraCount, "Ambient Umbra Buffer");
337
338#if DEBUG_SHADOW
339    for (int i = 0; i < vertexBufferIndex; i++) {
340        ALOGD("vertexBuffer i %d, (%f, %f %f)", i, shadowVertices[i].x, shadowVertices[i].y,
341                shadowVertices[i].alpha);
342    }
343    for (int i = 0; i < indexBufferIndex; i++) {
344        ALOGD("indexBuffer i %d, indexBuffer[i] %d", i, indexBuffer[i]);
345    }
346#endif
347}
348
349}; // namespace uirenderer
350}; // namespace android
351