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