AmbientShadow.cpp revision 2e023f3827dfc0dfc1ed7c3dd54d02b4a993f0b4
1e4d011201cea40d46cb2b2eef401db8fddc5c9c6Romain Guy/* 2e4d011201cea40d46cb2b2eef401db8fddc5c9c6Romain Guy * Copyright (C) 2013 The Android Open Source Project 3e4d011201cea40d46cb2b2eef401db8fddc5c9c6Romain Guy * 4163935113919a184122b8b3bd672ef08c8df65dcRomain Guy * Licensed under the Apache License, Version 2.0 (the "License"); 5163935113919a184122b8b3bd672ef08c8df65dcRomain Guy * you may not use this file except in compliance with the License. 6163935113919a184122b8b3bd672ef08c8df65dcRomain Guy * You may obtain a copy of the License at 7163935113919a184122b8b3bd672ef08c8df65dcRomain Guy * 88550c4c7b5952b7a4e1e0ede95c9492d03099a13Romain Guy * http://www.apache.org/licenses/LICENSE-2.0 99f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * 109f5dab3fc228fa11c32b483e6101ec086895a32bRomain Guy * Unless required by applicable law or agreed to in writing, software 11163935113919a184122b8b3bd672ef08c8df65dcRomain Guy * distributed under the License is distributed on an "AS IS" BASIS, 12b45c0c9774bd19a9dbe77d149abae4e124b08bf6Romain Guy * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13dd78ccacff83f0714ad90be98b58ad85f5d08c66Chet Haase * See the License for the specific language governing permissions and 140776a6069365bdea83855db154fa2d37f9d1d808Chris Craik * limitations under the License. 159c1e23baf5bfbebd1aebbd6d9a18c225325567ceChet Haase */ 1603750a067e818ca7fbd0f590e2ff6a8fded21e6cRomain Guy 17211efea7376371ee755edd2ad03e83ef6eea464eRomain Guy#define LOG_TAG "OpenGLRenderer" 183bbacf27c0be1bae4e4483577fc89ae3113abe5dRomain Guy 1903750a067e818ca7fbd0f590e2ff6a8fded21e6cRomain Guy#include <math.h> 20163935113919a184122b8b3bd672ef08c8df65dcRomain Guy#include <utils/Log.h> 21d15ebf25c595b855f6978d0600218e3ea5f31e92Chet Haase#include <utils/Vector.h> 22163935113919a184122b8b3bd672ef08c8df65dcRomain Guy 236c319ca1275c8db892c39b48fc54864c949f9171Romain Guy#include "AmbientShadow.h" 24163935113919a184122b8b3bd672ef08c8df65dcRomain Guy#include "ShadowTessellator.h" 25163935113919a184122b8b3bd672ef08c8df65dcRomain Guy#include "Vertex.h" 26163935113919a184122b8b3bd672ef08c8df65dcRomain Guy 27163935113919a184122b8b3bd672ef08c8df65dcRomain Guynamespace android { 28163935113919a184122b8b3bd672ef08c8df65dcRomain Guynamespace uirenderer { 2965cd612face362d054a85d0f7e5881c59cd523beChris Craik 30163935113919a184122b8b3bd672ef08c8df65dcRomain Guy/** 31163935113919a184122b8b3bd672ef08c8df65dcRomain Guy * Calculate the shadows as a triangle strips while alpha value as the 328d4aeb7111afac0c3c7e56d4ad5d92f9cfce2ffdRomain Guy * shadow values. 335c13d89c1332fcc499379b9064b891187b75ca32Chet Haase * 3401d58e43ede5ca98cbebdd166f9b0c545032c01bRomain Guy * @param isCasterOpaque Whether the caster is opaque. 35163935113919a184122b8b3bd672ef08c8df65dcRomain Guy * @param vertices The shadow caster's polygon, which is represented in a Vector3 36163935113919a184122b8b3bd672ef08c8df65dcRomain Guy * array. 37ada4d53d50dc869b8278573ad640dc44118d3bcfRomain Guy * @param vertexCount The length of caster's polygon in terms of number of 380baaac5e9adf3ee280ae1239e2e58754a9d2b099Romain Guy * vertices. 391e45aae5de003657e5d18f74d34998f5de5db5b7Romain Guy * @param centroid3d The centroid of the shadow caster. 401e45aae5de003657e5d18f74d34998f5de5db5b7Romain Guy * @param heightFactor The factor showing the higher the object, the lighter the 41710f46d9d6a5bf9ea1c1833384caf61e1934124fChris Craik * shadow. 42f2d8ccc15d7272b3416f73605c1f31d1d346bd40Chris Craik * @param geomFactor The factor scaling the geometry expansion along the normal. 43f2d8ccc15d7272b3416f73605c1f31d1d346bd40Chris Craik * 44163935113919a184122b8b3bd672ef08c8df65dcRomain Guy * @param shadowVertexBuffer Return an floating point array of (x, y, a) 45163935113919a184122b8b3bd672ef08c8df65dcRomain Guy * triangle strips mode. 46163935113919a184122b8b3bd672ef08c8df65dcRomain Guy */ 47163935113919a184122b8b3bd672ef08c8df65dcRomain GuyVertexBufferMode AmbientShadow::createAmbientShadow(bool isCasterOpaque, 48163935113919a184122b8b3bd672ef08c8df65dcRomain Guy const Vector3* vertices, int vertexCount, const Vector3& centroid3d, 49163935113919a184122b8b3bd672ef08c8df65dcRomain Guy float heightFactor, float geomFactor, VertexBuffer& shadowVertexBuffer) { 50163935113919a184122b8b3bd672ef08c8df65dcRomain Guy const int rays = SHADOW_RAY_COUNT; 51f2d8ccc15d7272b3416f73605c1f31d1d346bd40Chris Craik VertexBufferMode mode = kVertexBufferMode_OnePolyRingShadow; 52f2d8ccc15d7272b3416f73605c1f31d1d346bd40Chris Craik // Validate the inputs. 53f2d8ccc15d7272b3416f73605c1f31d1d346bd40Chris Craik if (vertexCount < 3 || heightFactor <= 0 || rays <= 0 54f2d8ccc15d7272b3416f73605c1f31d1d346bd40Chris Craik || geomFactor <= 0) { 5585bf02fc16784d935fb9eebfa9cb20fe46ff7951Romain Guy#if DEBUG_SHADOW 569c4b79af221b53f602f946faa9ff317a596a0c39Romain Guy ALOGW("Invalid input for createAmbientShadow(), early return!"); 57163935113919a184122b8b3bd672ef08c8df65dcRomain Guy#endif 58f2d8ccc15d7272b3416f73605c1f31d1d346bd40Chris Craik return mode; // vertex buffer is empty, so any mode doesn't matter. 59163935113919a184122b8b3bd672ef08c8df65dcRomain Guy } 60163935113919a184122b8b3bd672ef08c8df65dcRomain Guy 618a4ac610e1aaf04931ac1af54b146a7fc8e66114Romain Guy Vector<Vector2> dir; // TODO: use C++11 unique_ptr 628a4ac610e1aaf04931ac1af54b146a7fc8e66114Romain Guy dir.setCapacity(rays); 638a4ac610e1aaf04931ac1af54b146a7fc8e66114Romain Guy float rayDist[rays]; 648a4ac610e1aaf04931ac1af54b146a7fc8e66114Romain Guy float rayHeight[rays]; 658a4ac610e1aaf04931ac1af54b146a7fc8e66114Romain Guy calculateRayDirections(rays, vertices, vertexCount, centroid3d, dir.editArray()); 668a4ac610e1aaf04931ac1af54b146a7fc8e66114Romain Guy 678a4ac610e1aaf04931ac1af54b146a7fc8e66114Romain Guy // Calculate the length and height of the points along the edge. 688a4ac610e1aaf04931ac1af54b146a7fc8e66114Romain Guy // 698a4ac610e1aaf04931ac1af54b146a7fc8e66114Romain Guy // The math here is: 70163935113919a184122b8b3bd672ef08c8df65dcRomain Guy // Intersect each ray (starting from the centroid) with the polygon. 71e4d011201cea40d46cb2b2eef401db8fddc5c9c6Romain Guy for (int i = 0; i < rays; i++) { 72f2d8ccc15d7272b3416f73605c1f31d1d346bd40Chris Craik int edgeIndex; 73163935113919a184122b8b3bd672ef08c8df65dcRomain Guy float edgeFraction; 74 float rayDistance; 75 calculateIntersection(vertices, vertexCount, centroid3d, dir[i], edgeIndex, 76 edgeFraction, rayDistance); 77 rayDist[i] = rayDistance; 78 if (edgeIndex < 0 || edgeIndex >= vertexCount) { 79#if DEBUG_SHADOW 80 ALOGW("Invalid edgeIndex!"); 81#endif 82 edgeIndex = 0; 83 } 84 float h1 = vertices[edgeIndex].z; 85 float h2 = vertices[((edgeIndex + 1) % vertexCount)].z; 86 rayHeight[i] = h1 + edgeFraction * (h2 - h1); 87 } 88 89 // The output buffer length basically is roughly rays * layers, but since we 90 // need triangle strips, so we need to duplicate vertices to accomplish that. 91 AlphaVertex* shadowVertices = 92 shadowVertexBuffer.alloc<AlphaVertex>(SHADOW_VERTEX_COUNT); 93 94 // Calculate the vertex of the shadows. 95 // 96 // The math here is: 97 // Along the edges of the polygon, for each intersection point P (generated above), 98 // calculate the normal N, which should be perpendicular to the edge of the 99 // polygon (represented by the neighbor intersection points) . 100 // Shadow's vertices will be generated as : P + N * scale. 101 const Vector2 centroid2d = Vector2(centroid3d.x, centroid3d.y); 102 for (int rayIndex = 0; rayIndex < rays; rayIndex++) { 103 Vector2 normal(1.0f, 0.0f); 104 calculateNormal(rays, rayIndex, dir.array(), rayDist, normal); 105 106 // The vertex should be start from rayDist[i] then scale the 107 // normalizeNormal! 108 Vector2 intersection = dir[rayIndex] * rayDist[rayIndex] + 109 centroid2d; 110 111 // outer ring of points, expanded based upon height of each ray intersection 112 float expansionDist = rayHeight[rayIndex] * heightFactor * 113 geomFactor; 114 AlphaVertex::set(&shadowVertices[rayIndex], 115 intersection.x + normal.x * expansionDist, 116 intersection.y + normal.y * expansionDist, 117 0.0f); 118 119 // inner ring of points 120 float opacity = 1.0 / (1 + rayHeight[rayIndex] * heightFactor); 121 AlphaVertex::set(&shadowVertices[rays + rayIndex], 122 intersection.x, 123 intersection.y, 124 opacity); 125 } 126 127 // If caster isn't opaque, we need to to fill the umbra by storing the umbra's 128 // centroid in the innermost ring of vertices. 129 if (!isCasterOpaque) { 130 mode = kVertexBufferMode_TwoPolyRingShadow; 131 float centroidAlpha = 1.0 / (1 + centroid3d.z * heightFactor); 132 AlphaVertex centroidXYA; 133 AlphaVertex::set(¢roidXYA, centroid2d.x, centroid2d.y, centroidAlpha); 134 for (int rayIndex = 0; rayIndex < rays; rayIndex++) { 135 shadowVertices[2 * rays + rayIndex] = centroidXYA; 136 } 137 } 138 139#if DEBUG_SHADOW 140 for (int i = 0; i < SHADOW_VERTEX_COUNT; i++) { 141 ALOGD("ambient shadow value: i %d, (x:%f, y:%f, a:%f)", i, shadowVertices[i].x, 142 shadowVertices[i].y, shadowVertices[i].alpha); 143 } 144#endif 145 return mode; 146} 147 148/** 149 * Generate an array of rays' direction vectors. 150 * To make sure the vertices generated are clockwise, the directions are from PI 151 * to -PI. 152 * 153 * @param rays The number of rays shooting out from the centroid. 154 * @param vertices Vertices of the polygon. 155 * @param vertexCount The number of vertices. 156 * @param centroid3d The centroid of the polygon. 157 * @param dir Return the array of ray vectors. 158 */ 159void AmbientShadow::calculateRayDirections(const int rays, const Vector3* vertices, 160 const int vertexCount, const Vector3& centroid3d, Vector2* dir) { 161 // If we don't have enough rays, then fall back to the uniform distribution. 162 if (vertexCount * 2 > rays) { 163 float deltaAngle = 2 * M_PI / rays; 164 for (int i = 0; i < rays; i++) { 165 dir[i].x = cosf(M_PI - deltaAngle * i); 166 dir[i].y = sinf(M_PI - deltaAngle * i); 167 } 168 return; 169 } 170 171 // If we have enough rays, then we assign each vertices a ray, and distribute 172 // the rest uniformly. 173 float rayThetas[rays]; 174 175 const int uniformRayCount = rays - vertexCount; 176 const float deltaAngle = 2 * M_PI / uniformRayCount; 177 178 // We have to generate all the vertices' theta anyway and we also need to 179 // find the minimal, so let's precompute it first. 180 // Since the incoming polygon is clockwise, we can find the dip to identify 181 // the minimal theta. 182 float polyThetas[vertexCount]; 183 int maxPolyThetaIndex = 0; 184 for (int i = 0; i < vertexCount; i++) { 185 polyThetas[i] = atan2(vertices[i].y - centroid3d.y, 186 vertices[i].x - centroid3d.x); 187 if (i > 0 && polyThetas[i] > polyThetas[i - 1]) { 188 maxPolyThetaIndex = i; 189 } 190 } 191 192 // Both poly's thetas and uniform thetas are in decrease order(clockwise) 193 // from PI to -PI. 194 int polyThetaIndex = maxPolyThetaIndex; 195 float polyTheta = polyThetas[maxPolyThetaIndex]; 196 int uniformThetaIndex = 0; 197 float uniformTheta = M_PI; 198 for (int i = 0; i < rays; i++) { 199 // Compare both thetas and pick the smaller one and move on. 200 bool hasThetaCollision = abs(polyTheta - uniformTheta) < MINIMAL_DELTA_THETA; 201 if (polyTheta > uniformTheta || hasThetaCollision) { 202 if (hasThetaCollision) { 203 // Shift the uniformTheta to middle way between current polyTheta 204 // and next uniform theta. The next uniform theta can wrap around 205 // to exactly PI safely here. 206 // Note that neither polyTheta nor uniformTheta can be FLT_MAX 207 // due to the hasThetaCollision is true. 208 uniformTheta = (polyTheta + M_PI - deltaAngle * (uniformThetaIndex + 1)) / 2; 209#if DEBUG_SHADOW 210 ALOGD("Shifted uniformTheta to %f", uniformTheta); 211#endif 212 } 213 rayThetas[i] = polyTheta; 214 polyThetaIndex = (polyThetaIndex + 1) % vertexCount; 215 if (polyThetaIndex != maxPolyThetaIndex) { 216 polyTheta = polyThetas[polyThetaIndex]; 217 } else { 218 // out of poly points. 219 polyTheta = - FLT_MAX; 220 } 221 } else { 222 rayThetas[i] = uniformTheta; 223 uniformThetaIndex++; 224 if (uniformThetaIndex < uniformRayCount) { 225 uniformTheta = M_PI - deltaAngle * uniformThetaIndex; 226 } else { 227 // out of uniform points. 228 uniformTheta = - FLT_MAX; 229 } 230 } 231 } 232 233 for (int i = 0; i < rays; i++) { 234#if DEBUG_SHADOW 235 ALOGD("No. %d : %f", i, rayThetas[i] * 180 / M_PI); 236#endif 237 // TODO: Fix the intersection precision problem and remvoe the delta added 238 // here. 239 dir[i].x = cosf(rayThetas[i] + MINIMAL_DELTA_THETA); 240 dir[i].y = sinf(rayThetas[i] + MINIMAL_DELTA_THETA); 241 } 242} 243 244/** 245 * Calculate the intersection of a ray hitting the polygon. 246 * 247 * @param vertices The shadow caster's polygon, which is represented in a 248 * Vector3 array. 249 * @param vertexCount The length of caster's polygon in terms of number of vertices. 250 * @param start The starting point of the ray. 251 * @param dir The direction vector of the ray. 252 * 253 * @param outEdgeIndex Return the index of the segment (or index of the starting 254 * vertex) that ray intersect with. 255 * @param outEdgeFraction Return the fraction offset from the segment starting 256 * index. 257 * @param outRayDist Return the ray distance from centroid to the intersection. 258 */ 259void AmbientShadow::calculateIntersection(const Vector3* vertices, int vertexCount, 260 const Vector3& start, const Vector2& dir, int& outEdgeIndex, 261 float& outEdgeFraction, float& outRayDist) { 262 float startX = start.x; 263 float startY = start.y; 264 float dirX = dir.x; 265 float dirY = dir.y; 266 // Start the search from the last edge from poly[len-1] to poly[0]. 267 int p1 = vertexCount - 1; 268 269 for (int p2 = 0; p2 < vertexCount; p2++) { 270 float p1x = vertices[p1].x; 271 float p1y = vertices[p1].y; 272 float p2x = vertices[p2].x; 273 float p2y = vertices[p2].y; 274 275 // The math here is derived from: 276 // f(t, v) = p1x * (1 - t) + p2x * t - (startX + dirX * v) = 0; 277 // g(t, v) = p1y * (1 - t) + p2y * t - (startY + dirY * v) = 0; 278 float div = (dirX * (p1y - p2y) + dirY * p2x - dirY * p1x); 279 if (div != 0) { 280 float t = (dirX * (p1y - startY) + dirY * startX - dirY * p1x) / (div); 281 if (t > 0 && t <= 1) { 282 float t2 = (p1x * (startY - p2y) 283 + p2x * (p1y - startY) 284 + startX * (p2y - p1y)) / div; 285 if (t2 > 0) { 286 outEdgeIndex = p1; 287 outRayDist = t2; 288 outEdgeFraction = t; 289 return; 290 } 291 } 292 } 293 p1 = p2; 294 } 295 return; 296}; 297 298/** 299 * Calculate the normal at the intersection point between a ray and the polygon. 300 * 301 * @param rays The total number of rays. 302 * @param currentRayIndex The index of the ray which the normal is based on. 303 * @param dir The array of the all the rays directions. 304 * @param rayDist The pre-computed ray distances array. 305 * 306 * @param normal Return the normal. 307 */ 308void AmbientShadow::calculateNormal(int rays, int currentRayIndex, 309 const Vector2* dir, const float* rayDist, Vector2& normal) { 310 int preIndex = (currentRayIndex - 1 + rays) % rays; 311 int postIndex = (currentRayIndex + 1) % rays; 312 Vector2 p1 = dir[preIndex] * rayDist[preIndex]; 313 Vector2 p2 = dir[postIndex] * rayDist[postIndex]; 314 315 // Now the rays are going CW around the poly. 316 Vector2 delta = p2 - p1; 317 if (delta.length() != 0) { 318 delta.normalize(); 319 // Calculate the normal , which is CCW 90 rotate to the delta. 320 normal.x = - delta.y; 321 normal.y = delta.x; 322 } 323} 324 325}; // namespace uirenderer 326}; // namespace android 327