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