AmbientShadow.cpp revision c93e45cf045f41aea95f856173e4043d988a5a5c
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 shadowVertexBuffer.computeBounds<AlphaVertex>(); 140 141#if DEBUG_SHADOW 142 for (int i = 0; i < SHADOW_VERTEX_COUNT; i++) { 143 ALOGD("ambient shadow value: i %d, (x:%f, y:%f, a:%f)", i, shadowVertices[i].x, 144 shadowVertices[i].y, shadowVertices[i].alpha); 145 } 146#endif 147} 148 149/** 150 * Generate an array of rays' direction vectors. 151 * To make sure the vertices generated are clockwise, the directions are from PI 152 * to -PI. 153 * 154 * @param rays The number of rays shooting out from the centroid. 155 * @param vertices Vertices of the polygon. 156 * @param vertexCount The number of vertices. 157 * @param centroid3d The centroid of the polygon. 158 * @param dir Return the array of ray vectors. 159 */ 160void AmbientShadow::calculateRayDirections(const int rays, const Vector3* vertices, 161 const int vertexCount, const Vector3& centroid3d, Vector2* dir) { 162 // If we don't have enough rays, then fall back to the uniform distribution. 163 if (vertexCount * 2 > rays) { 164 float deltaAngle = 2 * M_PI / rays; 165 for (int i = 0; i < rays; i++) { 166 dir[i].x = cosf(M_PI - deltaAngle * i); 167 dir[i].y = sinf(M_PI - deltaAngle * i); 168 } 169 return; 170 } 171 172 // If we have enough rays, then we assign each vertices a ray, and distribute 173 // the rest uniformly. 174 float rayThetas[rays]; 175 176 const int uniformRayCount = rays - vertexCount; 177 const float deltaAngle = 2 * M_PI / uniformRayCount; 178 179 // We have to generate all the vertices' theta anyway and we also need to 180 // find the minimal, so let's precompute it first. 181 // Since the incoming polygon is clockwise, we can find the dip to identify 182 // the minimal theta. 183 float polyThetas[vertexCount]; 184 int maxPolyThetaIndex = 0; 185 for (int i = 0; i < vertexCount; i++) { 186 polyThetas[i] = atan2(vertices[i].y - centroid3d.y, 187 vertices[i].x - centroid3d.x); 188 if (i > 0 && polyThetas[i] > polyThetas[i - 1]) { 189 maxPolyThetaIndex = i; 190 } 191 } 192 193 // Both poly's thetas and uniform thetas are in decrease order(clockwise) 194 // from PI to -PI. 195 int polyThetaIndex = maxPolyThetaIndex; 196 float polyTheta = polyThetas[maxPolyThetaIndex]; 197 int uniformThetaIndex = 0; 198 float uniformTheta = M_PI; 199 for (int i = 0; i < rays; i++) { 200 // Compare both thetas and pick the smaller one and move on. 201 bool hasThetaCollision = abs(polyTheta - uniformTheta) < MINIMAL_DELTA_THETA; 202 if (polyTheta > uniformTheta || hasThetaCollision) { 203 if (hasThetaCollision) { 204 // Shift the uniformTheta to middle way between current polyTheta 205 // and next uniform theta. The next uniform theta can wrap around 206 // to exactly PI safely here. 207 // Note that neither polyTheta nor uniformTheta can be FLT_MAX 208 // due to the hasThetaCollision is true. 209 uniformTheta = (polyTheta + M_PI - deltaAngle * (uniformThetaIndex + 1)) / 2; 210#if DEBUG_SHADOW 211 ALOGD("Shifted uniformTheta to %f", uniformTheta); 212#endif 213 } 214 rayThetas[i] = polyTheta; 215 polyThetaIndex = (polyThetaIndex + 1) % vertexCount; 216 if (polyThetaIndex != maxPolyThetaIndex) { 217 polyTheta = polyThetas[polyThetaIndex]; 218 } else { 219 // out of poly points. 220 polyTheta = - FLT_MAX; 221 } 222 } else { 223 rayThetas[i] = uniformTheta; 224 uniformThetaIndex++; 225 if (uniformThetaIndex < uniformRayCount) { 226 uniformTheta = M_PI - deltaAngle * uniformThetaIndex; 227 } else { 228 // out of uniform points. 229 uniformTheta = - FLT_MAX; 230 } 231 } 232 } 233 234 for (int i = 0; i < rays; i++) { 235#if DEBUG_SHADOW 236 ALOGD("No. %d : %f", i, rayThetas[i] * 180 / M_PI); 237#endif 238 // TODO: Fix the intersection precision problem and remvoe the delta added 239 // here. 240 dir[i].x = cosf(rayThetas[i] + MINIMAL_DELTA_THETA); 241 dir[i].y = sinf(rayThetas[i] + MINIMAL_DELTA_THETA); 242 } 243} 244 245/** 246 * Calculate the intersection of a ray hitting the polygon. 247 * 248 * @param vertices The shadow caster's polygon, which is represented in a 249 * Vector3 array. 250 * @param vertexCount The length of caster's polygon in terms of number of vertices. 251 * @param start The starting point of the ray. 252 * @param dir The direction vector of the ray. 253 * 254 * @param outEdgeIndex Return the index of the segment (or index of the starting 255 * vertex) that ray intersect with. 256 * @param outEdgeFraction Return the fraction offset from the segment starting 257 * index. 258 * @param outRayDist Return the ray distance from centroid to the intersection. 259 */ 260void AmbientShadow::calculateIntersection(const Vector3* vertices, int vertexCount, 261 const Vector3& start, const Vector2& dir, int& outEdgeIndex, 262 float& outEdgeFraction, float& outRayDist) { 263 float startX = start.x; 264 float startY = start.y; 265 float dirX = dir.x; 266 float dirY = dir.y; 267 // Start the search from the last edge from poly[len-1] to poly[0]. 268 int p1 = vertexCount - 1; 269 270 for (int p2 = 0; p2 < vertexCount; p2++) { 271 float p1x = vertices[p1].x; 272 float p1y = vertices[p1].y; 273 float p2x = vertices[p2].x; 274 float p2y = vertices[p2].y; 275 276 // The math here is derived from: 277 // f(t, v) = p1x * (1 - t) + p2x * t - (startX + dirX * v) = 0; 278 // g(t, v) = p1y * (1 - t) + p2y * t - (startY + dirY * v) = 0; 279 float div = (dirX * (p1y - p2y) + dirY * p2x - dirY * p1x); 280 if (div != 0) { 281 float t = (dirX * (p1y - startY) + dirY * startX - dirY * p1x) / (div); 282 if (t > 0 && t <= 1) { 283 float t2 = (p1x * (startY - p2y) 284 + p2x * (p1y - startY) 285 + startX * (p2y - p1y)) / div; 286 if (t2 > 0) { 287 outEdgeIndex = p1; 288 outRayDist = t2; 289 outEdgeFraction = t; 290 return; 291 } 292 } 293 } 294 p1 = p2; 295 } 296 return; 297}; 298 299/** 300 * Calculate the normal at the intersection point between a ray and the polygon. 301 * 302 * @param rays The total number of rays. 303 * @param currentRayIndex The index of the ray which the normal is based on. 304 * @param dir The array of the all the rays directions. 305 * @param rayDist The pre-computed ray distances array. 306 * 307 * @param normal Return the normal. 308 */ 309void AmbientShadow::calculateNormal(int rays, int currentRayIndex, 310 const Vector2* dir, const float* rayDist, Vector2& normal) { 311 int preIndex = (currentRayIndex - 1 + rays) % rays; 312 int postIndex = (currentRayIndex + 1) % rays; 313 Vector2 p1 = dir[preIndex] * rayDist[preIndex]; 314 Vector2 p2 = dir[postIndex] * rayDist[postIndex]; 315 316 // Now the rays are going CW around the poly. 317 Vector2 delta = p2 - p1; 318 if (delta.length() != 0) { 319 delta.normalize(); 320 // Calculate the normal , which is CCW 90 rotate to the delta. 321 normal.x = - delta.y; 322 normal.y = delta.x; 323 } 324} 325 326}; // namespace uirenderer 327}; // namespace android 328