AmbientShadow.cpp revision 9a89bc6524620c87c7a321433470c668e2b95d69
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 // Validate the inputs. 52 if (vertexCount < 3 || heightFactor <= 0 || rays <= 0 53 || geomFactor <= 0) { 54#if DEBUG_SHADOW 55 ALOGW("Invalid input for createAmbientShadow(), early return!"); 56#endif 57 return; 58 } 59 60 Vector<Vector2> dir; // TODO: use C++11 unique_ptr 61 dir.setCapacity(rays); 62 float rayDist[rays]; 63 float rayHeight[rays]; 64 calculateRayDirections(rays, vertices, vertexCount, centroid3d, dir.editArray()); 65 66 // Calculate the length and height of the points along the edge. 67 // 68 // The math here is: 69 // Intersect each ray (starting from the centroid) with the polygon. 70 for (int i = 0; i < rays; i++) { 71 int edgeIndex; 72 float edgeFraction; 73 float rayDistance; 74 calculateIntersection(vertices, vertexCount, centroid3d, dir[i], edgeIndex, 75 edgeFraction, rayDistance); 76 rayDist[i] = rayDistance; 77 if (edgeIndex < 0 || edgeIndex >= vertexCount) { 78#if DEBUG_SHADOW 79 ALOGW("Invalid edgeIndex!"); 80#endif 81 edgeIndex = 0; 82 } 83 float h1 = vertices[edgeIndex].z; 84 float h2 = vertices[((edgeIndex + 1) % vertexCount)].z; 85 rayHeight[i] = h1 + edgeFraction * (h2 - h1); 86 } 87 88 // The output buffer length basically is roughly rays * layers, but since we 89 // need triangle strips, so we need to duplicate vertices to accomplish that. 90 AlphaVertex* shadowVertices = 91 shadowVertexBuffer.alloc<AlphaVertex>(SHADOW_VERTEX_COUNT); 92 93 // Calculate the vertex of the shadows. 94 // 95 // The math here is: 96 // Along the edges of the polygon, for each intersection point P (generated above), 97 // calculate the normal N, which should be perpendicular to the edge of the 98 // polygon (represented by the neighbor intersection points) . 99 // Shadow's vertices will be generated as : P + N * scale. 100 const Vector2 centroid2d = Vector2(centroid3d.x, centroid3d.y); 101 for (int rayIndex = 0; rayIndex < rays; rayIndex++) { 102 Vector2 normal(1.0f, 0.0f); 103 calculateNormal(rays, rayIndex, dir.array(), rayDist, normal); 104 105 // The vertex should be start from rayDist[i] then scale the 106 // normalizeNormal! 107 Vector2 intersection = dir[rayIndex] * rayDist[rayIndex] + 108 centroid2d; 109 110 // outer ring of points, expanded based upon height of each ray intersection 111 float expansionDist = rayHeight[rayIndex] * heightFactor * 112 geomFactor; 113 AlphaVertex::set(&shadowVertices[rayIndex], 114 intersection.x + normal.x * expansionDist, 115 intersection.y + normal.y * expansionDist, 116 0.0f); 117 118 // inner ring of points 119 float opacity = 1.0 / (1 + rayHeight[rayIndex] * heightFactor); 120 AlphaVertex::set(&shadowVertices[rays + rayIndex], 121 intersection.x, 122 intersection.y, 123 opacity); 124 } 125 126 if (isCasterOpaque) { 127 // skip inner ring, calc bounds over filled portion of buffer 128 shadowVertexBuffer.computeBounds<AlphaVertex>(2 * rays); 129 shadowVertexBuffer.setMode(VertexBuffer::kOnePolyRingShadow); 130 } else { 131 // If caster isn't opaque, we need to to fill the umbra by storing the umbra's 132 // centroid in the innermost ring of vertices. 133 float centroidAlpha = 1.0 / (1 + centroid3d.z * heightFactor); 134 AlphaVertex centroidXYA; 135 AlphaVertex::set(¢roidXYA, centroid2d.x, centroid2d.y, centroidAlpha); 136 for (int rayIndex = 0; rayIndex < rays; rayIndex++) { 137 shadowVertices[2 * rays + rayIndex] = centroidXYA; 138 } 139 // calc bounds over entire buffer 140 shadowVertexBuffer.computeBounds<AlphaVertex>(); 141 shadowVertexBuffer.setMode(VertexBuffer::kTwoPolyRingShadow); 142 } 143 144#if DEBUG_SHADOW 145 for (int i = 0; i < SHADOW_VERTEX_COUNT; i++) { 146 ALOGD("ambient shadow value: i %d, (x:%f, y:%f, a:%f)", i, shadowVertices[i].x, 147 shadowVertices[i].y, shadowVertices[i].alpha); 148 } 149#endif 150} 151 152/** 153 * Generate an array of rays' direction vectors. 154 * To make sure the vertices generated are clockwise, the directions are from PI 155 * to -PI. 156 * 157 * @param rays The number of rays shooting out from the centroid. 158 * @param vertices Vertices of the polygon. 159 * @param vertexCount The number of vertices. 160 * @param centroid3d The centroid of the polygon. 161 * @param dir Return the array of ray vectors. 162 */ 163void AmbientShadow::calculateRayDirections(const int rays, const Vector3* vertices, 164 const int vertexCount, const Vector3& centroid3d, Vector2* dir) { 165 // If we don't have enough rays, then fall back to the uniform distribution. 166 if (vertexCount * 2 > rays) { 167 float deltaAngle = 2 * M_PI / rays; 168 for (int i = 0; i < rays; i++) { 169 dir[i].x = cosf(M_PI - deltaAngle * i); 170 dir[i].y = sinf(M_PI - deltaAngle * i); 171 } 172 return; 173 } 174 175 // If we have enough rays, then we assign each vertices a ray, and distribute 176 // the rest uniformly. 177 float rayThetas[rays]; 178 179 const int uniformRayCount = rays - vertexCount; 180 const float deltaAngle = 2 * M_PI / uniformRayCount; 181 182 // We have to generate all the vertices' theta anyway and we also need to 183 // find the minimal, so let's precompute it first. 184 // Since the incoming polygon is clockwise, we can find the dip to identify 185 // the minimal theta. 186 float polyThetas[vertexCount]; 187 int maxPolyThetaIndex = 0; 188 for (int i = 0; i < vertexCount; i++) { 189 polyThetas[i] = atan2(vertices[i].y - centroid3d.y, 190 vertices[i].x - centroid3d.x); 191 if (i > 0 && polyThetas[i] > polyThetas[i - 1]) { 192 maxPolyThetaIndex = i; 193 } 194 } 195 196 // Both poly's thetas and uniform thetas are in decrease order(clockwise) 197 // from PI to -PI. 198 int polyThetaIndex = maxPolyThetaIndex; 199 float polyTheta = polyThetas[maxPolyThetaIndex]; 200 int uniformThetaIndex = 0; 201 float uniformTheta = M_PI; 202 for (int i = 0; i < rays; i++) { 203 // Compare both thetas and pick the smaller one and move on. 204 bool hasThetaCollision = abs(polyTheta - uniformTheta) < MINIMAL_DELTA_THETA; 205 if (polyTheta > uniformTheta || hasThetaCollision) { 206 if (hasThetaCollision) { 207 // Shift the uniformTheta to middle way between current polyTheta 208 // and next uniform theta. The next uniform theta can wrap around 209 // to exactly PI safely here. 210 // Note that neither polyTheta nor uniformTheta can be FLT_MAX 211 // due to the hasThetaCollision is true. 212 uniformTheta = (polyTheta + M_PI - deltaAngle * (uniformThetaIndex + 1)) / 2; 213#if DEBUG_SHADOW 214 ALOGD("Shifted uniformTheta to %f", uniformTheta); 215#endif 216 } 217 rayThetas[i] = polyTheta; 218 polyThetaIndex = (polyThetaIndex + 1) % vertexCount; 219 if (polyThetaIndex != maxPolyThetaIndex) { 220 polyTheta = polyThetas[polyThetaIndex]; 221 } else { 222 // out of poly points. 223 polyTheta = - FLT_MAX; 224 } 225 } else { 226 rayThetas[i] = uniformTheta; 227 uniformThetaIndex++; 228 if (uniformThetaIndex < uniformRayCount) { 229 uniformTheta = M_PI - deltaAngle * uniformThetaIndex; 230 } else { 231 // out of uniform points. 232 uniformTheta = - FLT_MAX; 233 } 234 } 235 } 236 237 for (int i = 0; i < rays; i++) { 238#if DEBUG_SHADOW 239 ALOGD("No. %d : %f", i, rayThetas[i] * 180 / M_PI); 240#endif 241 // TODO: Fix the intersection precision problem and remvoe the delta added 242 // here. 243 dir[i].x = cosf(rayThetas[i] + MINIMAL_DELTA_THETA); 244 dir[i].y = sinf(rayThetas[i] + MINIMAL_DELTA_THETA); 245 } 246} 247 248/** 249 * Calculate the intersection of a ray hitting the polygon. 250 * 251 * @param vertices The shadow caster's polygon, which is represented in a 252 * Vector3 array. 253 * @param vertexCount The length of caster's polygon in terms of number of vertices. 254 * @param start The starting point of the ray. 255 * @param dir The direction vector of the ray. 256 * 257 * @param outEdgeIndex Return the index of the segment (or index of the starting 258 * vertex) that ray intersect with. 259 * @param outEdgeFraction Return the fraction offset from the segment starting 260 * index. 261 * @param outRayDist Return the ray distance from centroid to the intersection. 262 */ 263void AmbientShadow::calculateIntersection(const Vector3* vertices, int vertexCount, 264 const Vector3& start, const Vector2& dir, int& outEdgeIndex, 265 float& outEdgeFraction, float& outRayDist) { 266 float startX = start.x; 267 float startY = start.y; 268 float dirX = dir.x; 269 float dirY = dir.y; 270 // Start the search from the last edge from poly[len-1] to poly[0]. 271 int p1 = vertexCount - 1; 272 273 for (int p2 = 0; p2 < vertexCount; p2++) { 274 float p1x = vertices[p1].x; 275 float p1y = vertices[p1].y; 276 float p2x = vertices[p2].x; 277 float p2y = vertices[p2].y; 278 279 // The math here is derived from: 280 // f(t, v) = p1x * (1 - t) + p2x * t - (startX + dirX * v) = 0; 281 // g(t, v) = p1y * (1 - t) + p2y * t - (startY + dirY * v) = 0; 282 float div = (dirX * (p1y - p2y) + dirY * p2x - dirY * p1x); 283 if (div != 0) { 284 float t = (dirX * (p1y - startY) + dirY * startX - dirY * p1x) / (div); 285 if (t > 0 && t <= 1) { 286 float t2 = (p1x * (startY - p2y) 287 + p2x * (p1y - startY) 288 + startX * (p2y - p1y)) / div; 289 if (t2 > 0) { 290 outEdgeIndex = p1; 291 outRayDist = t2; 292 outEdgeFraction = t; 293 return; 294 } 295 } 296 } 297 p1 = p2; 298 } 299 return; 300}; 301 302/** 303 * Calculate the normal at the intersection point between a ray and the polygon. 304 * 305 * @param rays The total number of rays. 306 * @param currentRayIndex The index of the ray which the normal is based on. 307 * @param dir The array of the all the rays directions. 308 * @param rayDist The pre-computed ray distances array. 309 * 310 * @param normal Return the normal. 311 */ 312void AmbientShadow::calculateNormal(int rays, int currentRayIndex, 313 const Vector2* dir, const float* rayDist, Vector2& normal) { 314 int preIndex = (currentRayIndex - 1 + rays) % rays; 315 int postIndex = (currentRayIndex + 1) % rays; 316 Vector2 p1 = dir[preIndex] * rayDist[preIndex]; 317 Vector2 p2 = dir[postIndex] * rayDist[postIndex]; 318 319 // Now the rays are going CW around the poly. 320 Vector2 delta = p2 - p1; 321 if (delta.length() != 0) { 322 delta.normalize(); 323 // Calculate the normal , which is CCW 90 rotate to the delta. 324 normal.x = - delta.y; 325 normal.y = delta.x; 326 } 327} 328 329}; // namespace uirenderer 330}; // namespace android 331