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 62 namespace android { 63 namespace uirenderer { 64 65 /** 66 * Local utility functions. 67 */ 68 inline 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. 78 inline float getAlphaFromFactoredZ(float factoredZ) { 79 return 1.0 / (1 + std::max(factoredZ, 0.0f)); 80 } 81 82 inline 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. 95 inline 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 118 inline 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 */ 166 void 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(¤tSpike, 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