AmbientShadow.cpp revision 05f3d6e5111fd08df5cd9aae2c3d28399dc0e7f5
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#include <math.h> 20#include <utils/Log.h> 21#include <utils/Vector.h> 22 23#include "AmbientShadow.h" 24#include "ShadowTessellator.h" 25#include "Vertex.h" 26 27namespace android { 28namespace uirenderer { 29 30/** 31 * Calculate the shadows as a triangle strips while alpha value as the 32 * shadow values. 33 * 34 * @param isCasterOpaque Whether the caster is opaque. 35 * @param vertices The shadow caster's polygon, which is represented in a Vector3 36 * array. 37 * @param vertexCount The length of caster's polygon in terms of number of 38 * vertices. 39 * @param centroid3d The centroid of the shadow caster. 40 * @param heightFactor The factor showing the higher the object, the lighter the 41 * shadow. 42 * @param geomFactor The factor scaling the geometry expansion along the normal. 43 * 44 * @param shadowVertexBuffer Return an floating point array of (x, y, a) 45 * triangle strips mode. 46 */ 47void AmbientShadow::createAmbientShadow(bool isCasterOpaque, 48 const Vector3* vertices, int vertexCount, const Vector3& centroid3d, 49 float heightFactor, float geomFactor, VertexBuffer& shadowVertexBuffer) { 50 const int rays = SHADOW_RAY_COUNT; 51 VertexBuffer::Mode mode = VertexBuffer::kOnePolyRingShadow; 52 // Validate the inputs. 53 if (vertexCount < 3 || heightFactor <= 0 || rays <= 0 54 || geomFactor <= 0) { 55#if DEBUG_SHADOW 56 ALOGW("Invalid input for createAmbientShadow(), early return!"); 57#endif 58 return; 59 } 60 61 Vector<Vector2> dir; // TODO: use C++11 unique_ptr 62 dir.setCapacity(rays); 63 float rayDist[rays]; 64 float rayHeight[rays]; 65 calculateRayDirections(rays, vertices, vertexCount, centroid3d, dir.editArray()); 66 67 // Calculate the length and height of the points along the edge. 68 // 69 // The math here is: 70 // Intersect each ray (starting from the centroid) with the polygon. 71 for (int i = 0; i < rays; i++) { 72 int edgeIndex; 73 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 = VertexBuffer::kTwoPolyRingShadow; 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 shadowVertexBuffer.setMode(mode); 139 140#if DEBUG_SHADOW 141 for (int i = 0; i < SHADOW_VERTEX_COUNT; i++) { 142 ALOGD("ambient shadow value: i %d, (x:%f, y:%f, a:%f)", i, shadowVertices[i].x, 143 shadowVertices[i].y, shadowVertices[i].alpha); 144 } 145#endif 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