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 <algorithm> 60 #include <utils/Log.h> 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, 83 const Vector3& secondVertex, 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, 96 int* totalUmbraCount, int casterVertexCount, bool isCasterOpaque) { 97 // Compute the size of the vertex buffer. 98 int outerVertexCount = casterVertexCount * 2 + MAX_EXTRA_CORNER_VERTEX_NUMBER + 99 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, 167 const Vector3* casterVertices, int casterVertexCount, const Vector3& centroid3d, 168 float heightFactor, float geomFactor, VertexBuffer& shadowVertexBuffer) { 169 shadowVertexBuffer.setMeshFeatureFlags(VertexBuffer::kAlpha | VertexBuffer::kIndices); 170 171 // In order to computer the outer vertices in one loop, we need pre-compute 172 // the normal by the vertex (n - 1) to vertex 0, and the spike and alpha value 173 // for vertex 0. 174 Vector2 previousNormal = getNormalFromVertices(casterVertices, 175 casterVertexCount - 1 , 0); 176 Vector2 currentSpike = {casterVertices[0].x - centroid3d.x, 177 casterVertices[0].y - centroid3d.y}; 178 currentSpike.normalize(); 179 float currentAlpha = getAlphaFromFactoredZ(casterVertices[0].z * heightFactor); 180 181 // Preparing all the output data. 182 int totalVertexCount, totalIndexCount, totalUmbraCount; 183 computeBufferSize(&totalVertexCount, &totalIndexCount, &totalUmbraCount, 184 casterVertexCount, isCasterOpaque); 185 AlphaVertex* shadowVertices = 186 shadowVertexBuffer.alloc<AlphaVertex>(totalVertexCount); 187 int vertexBufferIndex = 0; 188 uint16_t* indexBuffer = shadowVertexBuffer.allocIndices<uint16_t>(totalIndexCount); 189 int indexBufferIndex = 0; 190 uint16_t umbraVertices[totalUmbraCount]; 191 int umbraIndex = 0; 192 193 for (int i = 0; i < casterVertexCount; i++) { 194 // Corner: first figure out the extra vertices we need for the corner. 195 const Vector3& innerVertex = casterVertices[i]; 196 Vector2 currentNormal = getNormalFromVertices(casterVertices, i, 197 (i + 1) % casterVertexCount); 198 199 int extraVerticesNumber = ShadowTessellator::getExtraVertexNumber(currentNormal, 200 previousNormal, CORNER_RADIANS_DIVISOR); 201 202 float expansionDist = innerVertex.z * heightFactor * geomFactor; 203 const int cornerSlicesNumber = extraVerticesNumber + 1; // Minimal as 1. 204 #if DEBUG_SHADOW 205 ALOGD("cornerSlicesNumber is %d", cornerSlicesNumber); 206 #endif 207 208 // Corner: fill the corner Vertex Buffer(VB) and Index Buffer(IB). 209 // We fill the inner vertex first, such that we can fill the index buffer 210 // inside the loop. 211 int currentInnerVertexIndex = vertexBufferIndex; 212 if (!isCasterOpaque) { 213 umbraVertices[umbraIndex++] = vertexBufferIndex; 214 } 215 AlphaVertex::set(&shadowVertices[vertexBufferIndex++], 216 casterVertices[i].x, casterVertices[i].y, 217 currentAlpha); 218 219 const Vector3& innerStart = casterVertices[i]; 220 221 // outerStart is the first outer vertex for this inner vertex. 222 // outerLast is the last outer vertex for this inner vertex. 223 Vector2 outerStart = {0, 0}; 224 Vector2 outerLast = {0, 0}; 225 // This will create vertices from [0, cornerSlicesNumber] inclusively, 226 // which means minimally 2 vertices even without the extra ones. 227 for (int j = 0; j <= cornerSlicesNumber; j++) { 228 Vector2 averageNormal = 229 previousNormal * (cornerSlicesNumber - j) + currentNormal * j; 230 averageNormal /= cornerSlicesNumber; 231 averageNormal.normalize(); 232 Vector2 outerVertex; 233 outerVertex.x = innerVertex.x + averageNormal.x * expansionDist; 234 outerVertex.y = innerVertex.y + averageNormal.y * expansionDist; 235 236 indexBuffer[indexBufferIndex++] = vertexBufferIndex; 237 indexBuffer[indexBufferIndex++] = currentInnerVertexIndex; 238 AlphaVertex::set(&shadowVertices[vertexBufferIndex++], outerVertex.x, 239 outerVertex.y, OUTER_ALPHA); 240 241 if (j == 0) { 242 outerStart = outerVertex; 243 } else if (j == cornerSlicesNumber) { 244 outerLast = outerVertex; 245 } 246 } 247 previousNormal = currentNormal; 248 249 // Edge: first figure out the extra vertices needed for the edge. 250 const Vector3& innerNext = casterVertices[(i + 1) % casterVertexCount]; 251 float nextAlpha = getAlphaFromFactoredZ(innerNext.z * heightFactor); 252 if (needsExtraForEdge(currentAlpha, nextAlpha)) { 253 // TODO: See if we can / should cache this outer vertex across the loop. 254 Vector2 outerNext; 255 float expansionDist = innerNext.z * heightFactor * geomFactor; 256 outerNext.x = innerNext.x + currentNormal.x * expansionDist; 257 outerNext.y = innerNext.y + currentNormal.y * expansionDist; 258 259 // Compute the angle and see how many extra points we need. 260 int extraVerticesNumber = getEdgeExtraAndUpdateSpike(¤tSpike, 261 innerNext, centroid3d); 262 #if DEBUG_SHADOW 263 ALOGD("extraVerticesNumber %d for edge %d", extraVerticesNumber, i); 264 #endif 265 // Edge: fill the edge's VB and IB. 266 // This will create vertices pair from [1, extraVerticesNumber - 1]. 267 // If there is no extra vertices created here, the edge will be drawn 268 // as just 2 triangles. 269 for (int k = 1; k < extraVerticesNumber; k++) { 270 int startWeight = extraVerticesNumber - k; 271 Vector2 currentOuter = 272 (outerLast * startWeight + outerNext * k) / extraVerticesNumber; 273 indexBuffer[indexBufferIndex++] = vertexBufferIndex; 274 AlphaVertex::set(&shadowVertices[vertexBufferIndex++], currentOuter.x, 275 currentOuter.y, OUTER_ALPHA); 276 277 if (!isCasterOpaque) { 278 umbraVertices[umbraIndex++] = vertexBufferIndex; 279 } 280 Vector3 currentInner = 281 (innerStart * startWeight + innerNext * k) / extraVerticesNumber; 282 indexBuffer[indexBufferIndex++] = vertexBufferIndex; 283 AlphaVertex::set(&shadowVertices[vertexBufferIndex++], currentInner.x, 284 currentInner.y, 285 getAlphaFromFactoredZ(currentInner.z * heightFactor)); 286 } 287 } 288 currentAlpha = nextAlpha; 289 } 290 291 indexBuffer[indexBufferIndex++] = 1; 292 indexBuffer[indexBufferIndex++] = 0; 293 294 if (!isCasterOpaque) { 295 // Add the centroid as the last one in the vertex buffer. 296 float centroidOpacity = 297 getAlphaFromFactoredZ(centroid3d.z * heightFactor); 298 int centroidIndex = vertexBufferIndex; 299 AlphaVertex::set(&shadowVertices[vertexBufferIndex++], centroid3d.x, 300 centroid3d.y, centroidOpacity); 301 302 for (int i = 0; i < umbraIndex; i++) { 303 // Note that umbraVertices[0] is always 0. 304 // So the start and the end of the umbra are using the "0". 305 // And penumbra ended with 0, so a degenerated triangle is formed b/t 306 // the umbra and penumbra. 307 indexBuffer[indexBufferIndex++] = umbraVertices[i]; 308 indexBuffer[indexBufferIndex++] = centroidIndex; 309 } 310 indexBuffer[indexBufferIndex++] = 0; 311 } 312 313 // At the end, update the real index and vertex buffer size. 314 shadowVertexBuffer.updateVertexCount(vertexBufferIndex); 315 shadowVertexBuffer.updateIndexCount(indexBufferIndex); 316 shadowVertexBuffer.computeBounds<AlphaVertex>(); 317 318 ShadowTessellator::checkOverflow(vertexBufferIndex, totalVertexCount, "Ambient Vertex Buffer"); 319 ShadowTessellator::checkOverflow(indexBufferIndex, totalIndexCount, "Ambient Index Buffer"); 320 ShadowTessellator::checkOverflow(umbraIndex, totalUmbraCount, "Ambient Umbra Buffer"); 321 322 #if DEBUG_SHADOW 323 for (int i = 0; i < vertexBufferIndex; i++) { 324 ALOGD("vertexBuffer i %d, (%f, %f %f)", i, shadowVertices[i].x, shadowVertices[i].y, 325 shadowVertices[i].alpha); 326 } 327 for (int i = 0; i < indexBufferIndex; i++) { 328 ALOGD("indexBuffer i %d, indexBuffer[i] %d", i, indexBuffer[i]); 329 } 330 #endif 331 } 332 333 }; // namespace uirenderer 334 }; // namespace android 335
