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