AmbientShadow.cpp revision 55bfb4e728fe1db619af5d2c287f4abe711b3343
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 22#include "AmbientShadow.h" 23#include "Vertex.h" 24 25namespace android { 26namespace uirenderer { 27 28/** 29 * Calculate the shadows as a triangle strips while alpha value as the 30 * shadow values. 31 * 32 * @param vertices The shadow caster's polygon, which is represented in a Vector3 33 * array. 34 * @param vertexCount The length of caster's polygon in terms of number of 35 * vertices. 36 * @param rays The number of rays shooting out from the centroid. 37 * @param layers The number of rings outside the polygon. 38 * @param strength The darkness of the shadow, the higher, the darker. 39 * @param heightFactor The factor showing the higher the object, the lighter the 40 * shadow. 41 * @param geomFactor The factor scaling the geometry expansion along the normal. 42 * 43 * @param shadowVertexBuffer Return an floating point array of (x, y, a) 44 * triangle strips mode. 45 */ 46void AmbientShadow::createAmbientShadow(const Vector3* vertices, int vertexCount, 47 int rays, int layers, float strength, float heightFactor, float geomFactor, 48 VertexBuffer& shadowVertexBuffer) { 49 50 // Validate the inputs. 51 if (strength <= 0 || heightFactor <= 0 || layers <= 0 || rays <= 0 52 || geomFactor <= 0) { 53#if DEBUG_SHADOW 54 ALOGE("Invalid input for createAmbientShadow(), early return!"); 55#endif 56 return; 57 } 58 int rings = layers + 1; 59 int size = rays * rings; 60 Vector2 centroid; 61 calculatePolygonCentroid(vertices, vertexCount, centroid); 62 63 Vector2 dir[rays]; 64 float rayDist[rays]; 65 float rayHeight[rays]; 66 calculateRayDirections(rays, dir); 67 68 // Calculate the length and height of the points along the edge. 69 // 70 // The math here is: 71 // Intersect each ray (starting from the centroid) with the polygon. 72 for (int i = 0; i < rays; i++) { 73 int edgeIndex; 74 float edgeFraction; 75 float rayDistance; 76 calculateIntersection(vertices, vertexCount, centroid, dir[i], edgeIndex, 77 edgeFraction, rayDistance); 78 rayDist[i] = rayDistance; 79 if (edgeIndex < 0 || edgeIndex >= vertexCount) { 80#if DEBUG_SHADOW 81 ALOGE("Invalid edgeIndex!"); 82#endif 83 edgeIndex = 0; 84 } 85 float h1 = vertices[edgeIndex].z; 86 float h2 = vertices[((edgeIndex + 1) % vertexCount)].z; 87 rayHeight[i] = h1 + edgeFraction * (h2 - h1); 88 } 89 90 // The output buffer length basically is roughly rays * layers, but since we 91 // need triangle strips, so we need to duplicate vertices to accomplish that. 92 const int shadowVertexCount = (2 + rays + ((layers) * 2 * (rays + 1))); 93 AlphaVertex* shadowVertices = shadowVertexBuffer.alloc<AlphaVertex>(shadowVertexCount); 94 95 // Calculate the vertex of the shadows. 96 // 97 // The math here is: 98 // Along the edges of the polygon, for each intersection point P (generated above), 99 // calculate the normal N, which should be perpendicular to the edge of the 100 // polygon (represented by the neighbor intersection points) . 101 // Shadow's vertices will be generated as : P + N * scale. 102 int currentIndex = 0; 103 for (int r = 0; r < layers; r++) { 104 int firstInLayer = currentIndex; 105 for (int i = 0; i < rays; i++) { 106 107 Vector2 normal(1.0f, 0.0f); 108 calculateNormal(rays, i, dir, rayDist, normal); 109 110 float opacity = strength * (0.5f) / (1 + rayHeight[i] / heightFactor); 111 112 // The vertex should be start from rayDist[i] then scale the 113 // normalizeNormal! 114 Vector2 intersection = dir[i] * rayDist[i] + centroid; 115 116 // Use 2 rings' vertices to complete one layer's strip 117 for (int j = r; j < (r + 2); j++) { 118 float jf = j / (float)(rings - 1); 119 120 float expansionDist = rayHeight[i] / heightFactor * geomFactor * jf; 121 AlphaVertex::set(&shadowVertices[currentIndex], 122 intersection.x + normal.x * expansionDist, 123 intersection.y + normal.y * expansionDist, 124 (1 - jf) * opacity); 125 currentIndex++; 126 } 127 } 128 129 // From one layer to the next, we need to duplicate the vertex to 130 // continue as a single strip. 131 shadowVertices[currentIndex] = shadowVertices[firstInLayer]; 132 currentIndex++; 133 shadowVertices[currentIndex] = shadowVertices[firstInLayer + 1]; 134 currentIndex++; 135 } 136 137 // After all rings are done, we need to jump into the polygon. 138 // In order to keep everything in a strip, we need to duplicate the last one 139 // of the rings and the first one inside the polygon. 140 int lastInRings = currentIndex - 1; 141 shadowVertices[currentIndex] = shadowVertices[lastInRings]; 142 currentIndex++; 143 144 // We skip one and fill it back after we finish the internal triangles. 145 currentIndex++; 146 int firstInternal = currentIndex; 147 148 // Combine the internal area of the polygon into a triangle strip, too. 149 // The basic idea is zig zag between the intersection points. 150 // 0 -> (n - 1) -> 1 -> (n - 2) ... 151 for (int k = 0; k < rays; k++) { 152 int i = k / 2; 153 if ((k & 1) == 1) { // traverse the inside in a zig zag pattern for strips 154 i = rays - i - 1; 155 } 156 float cast = rayDist[i] * (1 + rayHeight[i] / heightFactor); 157 float opacity = strength * (0.5f) / (1 + rayHeight[i] / heightFactor); 158 float t = rayDist[i]; 159 160 AlphaVertex::set(&shadowVertices[currentIndex], dir[i].x * t + centroid.x, 161 dir[i].y * t + centroid.y, opacity); 162 currentIndex++; 163 } 164 165 currentIndex = firstInternal - 1; 166 shadowVertices[currentIndex] = shadowVertices[firstInternal]; 167} 168 169/** 170 * Calculate the centroid of a given polygon. 171 * 172 * @param vertices The shadow caster's polygon, which is represented in a 173 * straight Vector3 array. 174 * @param vertexCount The length of caster's polygon in terms of number of vertices. 175 * 176 * @param centroid Return the centroid of the polygon. 177 */ 178void AmbientShadow::calculatePolygonCentroid(const Vector3* vertices, int vertexCount, 179 Vector2& centroid) { 180 float sumx = 0; 181 float sumy = 0; 182 int p1 = vertexCount - 1; 183 float area = 0; 184 for (int p2 = 0; p2 < vertexCount; p2++) { 185 float x1 = vertices[p1].x; 186 float y1 = vertices[p1].y; 187 float x2 = vertices[p2].x; 188 float y2 = vertices[p2].y; 189 float a = (x1 * y2 - x2 * y1); 190 sumx += (x1 + x2) * a; 191 sumy += (y1 + y2) * a; 192 area += a; 193 p1 = p2; 194 } 195 196 if (area == 0) { 197#if DEBUG_SHADOW 198 ALOGE("Area is 0!"); 199#endif 200 centroid.x = vertices[0].x; 201 centroid.y = vertices[0].y; 202 } else { 203 centroid.x = sumx / (3 * area); 204 centroid.y = sumy / (3 * area); 205 } 206} 207 208/** 209 * Generate an array of rays' direction vectors. 210 * 211 * @param rays The number of rays shooting out from the centroid. 212 * @param dir Return the array of ray vectors. 213 */ 214void AmbientShadow::calculateRayDirections(int rays, Vector2* dir) { 215 float deltaAngle = 2 * M_PI / rays; 216 217 for (int i = 0; i < rays; i++) { 218 dir[i].x = sinf(deltaAngle * i); 219 dir[i].y = cosf(deltaAngle * i); 220 } 221} 222 223/** 224 * Calculate the intersection of a ray hitting the polygon. 225 * 226 * @param vertices The shadow caster's polygon, which is represented in a 227 * Vector3 array. 228 * @param vertexCount The length of caster's polygon in terms of number of vertices. 229 * @param start The starting point of the ray. 230 * @param dir The direction vector of the ray. 231 * 232 * @param outEdgeIndex Return the index of the segment (or index of the starting 233 * vertex) that ray intersect with. 234 * @param outEdgeFraction Return the fraction offset from the segment starting 235 * index. 236 * @param outRayDist Return the ray distance from centroid to the intersection. 237 */ 238void AmbientShadow::calculateIntersection(const Vector3* vertices, int vertexCount, 239 const Vector2& start, const Vector2& dir, int& outEdgeIndex, 240 float& outEdgeFraction, float& outRayDist) { 241 float startX = start.x; 242 float startY = start.y; 243 float dirX = dir.x; 244 float dirY = dir.y; 245 // Start the search from the last edge from poly[len-1] to poly[0]. 246 int p1 = vertexCount - 1; 247 248 for (int p2 = 0; p2 < vertexCount; p2++) { 249 float p1x = vertices[p1].x; 250 float p1y = vertices[p1].y; 251 float p2x = vertices[p2].x; 252 float p2y = vertices[p2].y; 253 254 // The math here is derived from: 255 // f(t, v) = p1x * (1 - t) + p2x * t - (startX + dirX * v) = 0; 256 // g(t, v) = p1y * (1 - t) + p2y * t - (startY + dirY * v) = 0; 257 float div = (dirX * (p1y - p2y) + dirY * p2x - dirY * p1x); 258 if (div != 0) { 259 float t = (dirX * (p1y - startY) + dirY * startX - dirY * p1x) / (div); 260 if (t > 0 && t <= 1) { 261 float t2 = (p1x * (startY - p2y) 262 + p2x * (p1y - startY) 263 + startX * (p2y - p1y)) / div; 264 if (t2 > 0) { 265 outEdgeIndex = p1; 266 outRayDist = t2; 267 outEdgeFraction = t; 268 return; 269 } 270 } 271 } 272 p1 = p2; 273 } 274 return; 275}; 276 277/** 278 * Calculate the normal at the intersection point between a ray and the polygon. 279 * 280 * @param rays The total number of rays. 281 * @param currentRayIndex The index of the ray which the normal is based on. 282 * @param dir The array of the all the rays directions. 283 * @param rayDist The pre-computed ray distances array. 284 * 285 * @param normal Return the normal. 286 */ 287void AmbientShadow::calculateNormal(int rays, int currentRayIndex, 288 const Vector2* dir, const float* rayDist, Vector2& normal) { 289 int preIndex = (currentRayIndex - 1 + rays) % rays; 290 int postIndex = (currentRayIndex + 1) % rays; 291 Vector2 p1 = dir[preIndex] * rayDist[preIndex]; 292 Vector2 p2 = dir[postIndex] * rayDist[postIndex]; 293 294 // Now the V (deltaX, deltaY) is the vector going CW around the poly. 295 Vector2 delta = p2 - p1; 296 if (delta.length() != 0) { 297 delta.normalize(); 298 // Calculate the normal , which is CCW 90 rotate to the V. 299 // 90 degrees CCW about z-axis: (x, y, z) -> (-y, x, z) 300 normal.x = -delta.y; 301 normal.y = delta.x; 302 } 303} 304 305}; // namespace uirenderer 306}; // namespace android 307