Improve shadow tessellation performance
- Tune and simplify shadow parameters
- Remove additional inner rings
- Improve polygon ray casting algorithm
Change-Id: If0f28b2d66ae0480b675942bb65e8fcd2864425d
diff --git a/libs/hwui/AmbientShadow.cpp b/libs/hwui/AmbientShadow.cpp
index 4935b34..8327ef7 100644
--- a/libs/hwui/AmbientShadow.cpp
+++ b/libs/hwui/AmbientShadow.cpp
@@ -47,9 +47,8 @@
const Vector3& centroid3d, float heightFactor, float geomFactor,
VertexBuffer& shadowVertexBuffer) {
const int rays = SHADOW_RAY_COUNT;
- const int layers = SHADOW_LAYER_COUNT;
// Validate the inputs.
- if (vertexCount < 3 || heightFactor <= 0 || layers <= 0 || rays <= 0
+ if (vertexCount < 3 || heightFactor <= 0 || rays <= 0
|| geomFactor <= 0) {
#if DEBUG_SHADOW
ALOGE("Invalid input for createAmbientShadow(), early return!");
@@ -96,33 +95,32 @@
// calculate the normal N, which should be perpendicular to the edge of the
// polygon (represented by the neighbor intersection points) .
// Shadow's vertices will be generated as : P + N * scale.
- int currentVertexIndex = 0;
- for (int layerIndex = 0; layerIndex <= layers; layerIndex++) {
- for (int rayIndex = 0; rayIndex < rays; rayIndex++) {
+ for (int rayIndex = 0; rayIndex < rays; rayIndex++) {
+ Vector2 normal(1.0f, 0.0f);
+ calculateNormal(rays, rayIndex, dir.array(), rayDist, normal);
- Vector2 normal(1.0f, 0.0f);
- calculateNormal(rays, rayIndex, dir.array(), rayDist, normal);
+ // The vertex should be start from rayDist[i] then scale the
+ // normalizeNormal!
+ Vector2 intersection = dir[rayIndex] * rayDist[rayIndex] +
+ Vector2(centroid3d.x, centroid3d.y);
- float opacity = 1.0 / (1 + rayHeight[rayIndex] / heightFactor);
+ // outer ring of points, expanded based upon height of each ray intersection
+ float expansionDist = rayHeight[rayIndex] * heightFactor *
+ geomFactor;
+ AlphaVertex::set(&shadowVertices[rayIndex],
+ intersection.x + normal.x * expansionDist,
+ intersection.y + normal.y * expansionDist,
+ 0.0f);
- // The vertex should be start from rayDist[i] then scale the
- // normalizeNormal!
- Vector2 intersection = dir[rayIndex] * rayDist[rayIndex] +
- Vector2(centroid3d.x, centroid3d.y);
-
- float layerRatio = layerIndex / (float)(layers);
- // The higher the intersection is, the further the ambient shadow expanded.
- float expansionDist = rayHeight[rayIndex] / heightFactor *
- geomFactor * (1 - layerRatio);
- AlphaVertex::set(&shadowVertices[currentVertexIndex++],
- intersection.x + normal.x * expansionDist,
- intersection.y + normal.y * expansionDist,
- layerRatio * opacity);
- }
-
+ // inner ring of points
+ float opacity = 1.0 / (1 + rayHeight[rayIndex] * heightFactor);
+ AlphaVertex::set(&shadowVertices[rayIndex + rays],
+ intersection.x,
+ intersection.y,
+ opacity);
}
- float centroidAlpha = 1.0 / (1 + centroid3d.z / heightFactor);
- AlphaVertex::set(&shadowVertices[currentVertexIndex++],
+ float centroidAlpha = 1.0 / (1 + centroid3d.z * heightFactor);
+ AlphaVertex::set(&shadowVertices[SHADOW_VERTEX_COUNT - 1],
centroid3d.x, centroid3d.y, centroidAlpha);
#if DEBUG_SHADOW
diff --git a/libs/hwui/Caches.cpp b/libs/hwui/Caches.cpp
index 1d58d96..f02e591 100644
--- a/libs/hwui/Caches.cpp
+++ b/libs/hwui/Caches.cpp
@@ -705,8 +705,8 @@
propertyDirtyViewport = false;
propertyEnable3d = false;
propertyCameraDistance = 1.0f;
- propertyAmbientShadowStrength = 0x3f;
- propertySpotShadowStrength = 0x3f;
+ propertyAmbientShadowStrength = 25;
+ propertySpotShadowStrength = 25;
propertyLightPosXScale = 0.5f;
propertyLightPosYScale = 0.0f;
diff --git a/libs/hwui/DisplayList.cpp b/libs/hwui/DisplayList.cpp
index 0f76486..0c544b8 100644
--- a/libs/hwui/DisplayList.cpp
+++ b/libs/hwui/DisplayList.cpp
@@ -491,7 +491,7 @@
replayStruct.mDrawGlStatus);
}
-#define SHADOW_DELTA 2.0f
+#define SHADOW_DELTA 0.1f
template <class T>
void DisplayList::iterate3dChildren(ChildrenSelectMode mode, OpenGLRenderer& renderer,
diff --git a/libs/hwui/ShadowTessellator.cpp b/libs/hwui/ShadowTessellator.cpp
index 5469aad..f138222 100644
--- a/libs/hwui/ShadowTessellator.cpp
+++ b/libs/hwui/ShadowTessellator.cpp
@@ -40,7 +40,7 @@
// A bunch of parameters to tweak the shadow.
// TODO: Allow some of these changable by debug settings or APIs.
- const float heightFactor = 128;
+ const float heightFactor = 1.0f / 128;
const float geomFactor = 64;
AmbientShadow::createAmbientShadow(casterPolygon, casterVertexCount,
@@ -69,7 +69,7 @@
reverseReceiverTransform.mapPoint3d(lightCenter);
const float lightSize = maximal / 4;
- const int lightVertexCount = 16;
+ const int lightVertexCount = 8;
SpotShadow::createSpotShadow(casterPolygon, casterVertexCount, lightCenter,
lightSize, lightVertexCount, shadowVertexBuffer);
@@ -78,26 +78,23 @@
void ShadowTessellator::generateShadowIndices(uint16_t* shadowIndices) {
int currentIndex = 0;
- const int layers = SHADOW_LAYER_COUNT;
const int rays = SHADOW_RAY_COUNT;
// For the penumbra area.
- for (int i = 0; i < layers; i++) {
- for (int j = 0; j < rays; j++) {
- shadowIndices[currentIndex++] = i * rays + j;
- shadowIndices[currentIndex++] = (i + 1) * rays + j;
- }
- // To close the loop, back to the ray 0.
- shadowIndices[currentIndex++] = i * rays;
- shadowIndices[currentIndex++] = (i + 1) * rays;
+ for (int i = 0; i < rays; i++) {
+ shadowIndices[currentIndex++] = i;
+ shadowIndices[currentIndex++] = rays + i;
}
- uint16_t base = layers * rays;
- uint16_t centroidIndex = (layers + 1) * rays;
+ // To close the loop, back to the ray 0.
+ shadowIndices[currentIndex++] = 0;
+ shadowIndices[currentIndex++] = rays;
+
+ uint16_t centroidIndex = 2 * rays;
// For the umbra area, using strips to simulate the fans.
- for (int k = 0; k < rays; k++) {
- shadowIndices[currentIndex++] = base + k;
+ for (int i = 0; i < rays; i++) {
+ shadowIndices[currentIndex++] = rays + i;
shadowIndices[currentIndex++] = centroidIndex;
}
- shadowIndices[currentIndex++] = base;
+ shadowIndices[currentIndex++] = rays;
#if DEBUG_SHADOW
if (currentIndex != SHADOW_INDEX_COUNT) {
diff --git a/libs/hwui/ShadowTessellator.h b/libs/hwui/ShadowTessellator.h
index c49fdcb1..120774b 100644
--- a/libs/hwui/ShadowTessellator.h
+++ b/libs/hwui/ShadowTessellator.h
@@ -46,17 +46,13 @@
// The total number of rays starting from the centroid of shadow area, in order
// to generate the shadow geometry.
-#define SHADOW_RAY_COUNT 256
-
-// The total number of layers in the outer shadow area, 1 being the minimum.
-#define SHADOW_LAYER_COUNT 2
+#define SHADOW_RAY_COUNT 128
// The total number of all the vertices representing the shadow.
-#define SHADOW_VERTEX_COUNT ((SHADOW_LAYER_COUNT + 1) * SHADOW_RAY_COUNT + 1)
+#define SHADOW_VERTEX_COUNT (2 * SHADOW_RAY_COUNT + 1)
// The total number of indices used for drawing the shadow geometry as triangle strips.
-#define SHADOW_INDEX_COUNT (2 * SHADOW_RAY_COUNT + 1 + 2 * (SHADOW_RAY_COUNT + 1) * \
- SHADOW_LAYER_COUNT)
+#define SHADOW_INDEX_COUNT (2 * SHADOW_RAY_COUNT + 1 + 2 * (SHADOW_RAY_COUNT + 1))
class ShadowTessellator {
public:
diff --git a/libs/hwui/SpotShadow.cpp b/libs/hwui/SpotShadow.cpp
index 22d735b..54039c01 100644
--- a/libs/hwui/SpotShadow.cpp
+++ b/libs/hwui/SpotShadow.cpp
@@ -29,45 +29,46 @@
namespace android {
namespace uirenderer {
+static const double EPSILON = 1e-7;
+
/**
- * Calculate the intersection of a ray with a polygon.
- * It assumes the ray originates inside the polygon.
- *
- * @param poly The polygon, which is represented in a Vector2 array.
- * @param polyLength The length of caster's polygon in terms of number of
- * vertices.
- * @param point the start of the ray
- * @param dx the x vector of the ray
- * @param dy the y vector of the ray
- * @return the distance along the ray if it intersects with the polygon FP_NAN if otherwise
+ * Calculate the angle between and x and a y coordinate.
+ * The atan2 range from -PI to PI.
*/
-float SpotShadow::rayIntersectPoly(const Vector2* poly, int polyLength,
- const Vector2& point, float dx, float dy) {
- double px = point.x;
- double py = point.y;
- int p1 = polyLength - 1;
- for (int p2 = 0; p2 < polyLength; p2++) {
- double p1x = poly[p1].x;
- double p1y = poly[p1].y;
- double p2x = poly[p2].x;
- double p2y = poly[p2].y;
- // The math below is derived from solving this formula, basically the
- // intersection point should stay on both the ray and the edge of (p1, p2).
- // solve([p1x+t*(p2x-p1x)=dx*t2+px,p1y+t*(p2y-p1y)=dy*t2+py],[t,t2]);
- double div = (dx * (p1y - p2y) + dy * p2x - dy * p1x);
- if (div != 0) {
- double t = (dx * (p1y - py) + dy * px - dy * p1x) / (div);
- if (t >= 0 && t <= 1) {
- double t2 = (p1x * (py - p2y) + p2x * (p1y - py) +
- px * (p2y - p1y)) / div;
- if (t2 > 0) {
- return (float)t2;
- }
- }
- }
- p1 = p2;
- }
- return FP_NAN;
+float angle(const Vector2& point, const Vector2& center) {
+ return atan2(point.y - center.y, point.x - center.x);
+}
+
+/**
+ * Calculate the intersection of a ray with the line segment defined by two points.
+ *
+ * Returns a negative value in error conditions.
+
+ * @param rayOrigin The start of the ray
+ * @param dx The x vector of the ray
+ * @param dy The y vector of the ray
+ * @param p1 The first point defining the line segment
+ * @param p2 The second point defining the line segment
+ * @return The distance along the ray if it intersects with the line segment, negative if otherwise
+ */
+float rayIntersectPoints(const Vector2& rayOrigin, float dx, float dy,
+ const Vector2& p1, const Vector2& p2) {
+ // The math below is derived from solving this formula, basically the
+ // intersection point should stay on both the ray and the edge of (p1, p2).
+ // solve([p1x+t*(p2x-p1x)=dx*t2+px,p1y+t*(p2y-p1y)=dy*t2+py],[t,t2]);
+
+ double divisor = (dx * (p1.y - p2.y) + dy * p2.x - dy * p1.x);
+ if (divisor == 0) return -1.0f; // error, invalid divisor
+
+#if DEBUG_SHADOW
+ double interpVal = (dx * (p1.y - rayOrigin.y) + dy * rayOrigin.x - dy * p1.x) / divisor;
+ if (interpVal < 0 || interpVal > 1) return -1.0f; // error, doesn't intersect between points
+#endif
+
+ double distance = (p1.x * (rayOrigin.y - p2.y) + p2.x * (p1.y - rayOrigin.y) +
+ rayOrigin.x * (p2.y - p1.y)) / divisor;
+
+ return distance; // may be negative in error cases
}
/**
@@ -131,30 +132,26 @@
lLowerSize--;
}
}
- int count = 0;
+ // output points in CW ordering
+ const int total = lUpperSize + lLowerSize - 2;
+ int outIndex = total - 1;
for (int i = 0; i < lUpperSize; i++) {
- retPoly[count] = lUpper[i];
- count++;
+ retPoly[outIndex] = lUpper[i];
+ outIndex--;
}
for (int i = 1; i < lLowerSize - 1; i++) {
- retPoly[count] = lLower[i];
- count++;
+ retPoly[outIndex] = lLower[i];
+ outIndex--;
}
// TODO: Add test harness which verify that all the points are inside the hull.
- return count;
+ return total;
}
/**
* Test whether the 3 points form a counter clockwise turn.
*
- * @param ax the x coordinate of point a
- * @param ay the y coordinate of point a
- * @param bx the x coordinate of point b
- * @param by the y coordinate of point b
- * @param cx the x coordinate of point c
- * @param cy the y coordinate of point c
* @return true if a right hand turn
*/
bool SpotShadow::ccw(double ax, double ay, double bx, double by,
@@ -303,15 +300,6 @@
}
/**
- * Calculate the angle between and x and a y coordinate.
- * The atan2 range from -PI to PI, if we want to sort the vertices as clockwise,
- * we just negate the return angle.
- */
-float SpotShadow::angle(const Vector2& point, const Vector2& center) {
- return -(float)atan2(point.y - center.y, point.x - center.x);
-}
-
-/**
* Swap points pointed to by i and j
*/
void SpotShadow::swap(Vector2* points, int i, int j) {
@@ -329,10 +317,10 @@
int p = low + (high - low) / 2;
float pivot = angle(points[p], center);
while (i <= j) {
- while (angle(points[i], center) < pivot) {
+ while (angle(points[i], center) > pivot) {
i++;
}
- while (angle(points[j], center) > pivot) {
+ while (angle(points[j], center) < pivot) {
j--;
}
@@ -508,8 +496,8 @@
// TODO: Caching all the sin / cos values and store them in a look up table.
for (int i = 0; i < points; i++) {
double angle = 2 * i * M_PI / points;
- ret[i].x = sinf(angle) * size + lightCenter.x;
- ret[i].y = cosf(angle) * size + lightCenter.y;
+ ret[i].x = cosf(angle) * size + lightCenter.x;
+ ret[i].y = sinf(angle) * size + lightCenter.y;
ret[i].z = lightCenter.z;
}
}
@@ -657,6 +645,63 @@
}
/**
+ * Converts a polygon specified with CW vertices into an array of distance-from-centroid values.
+ *
+ * Returns false in error conditions
+ *
+ * @param poly Array of vertices. Note that these *must* be CW.
+ * @param polyLength The number of vertices in the polygon.
+ * @param polyCentroid The centroid of the polygon, from which rays will be cast
+ * @param rayDist The output array for the calculated distances, must be SHADOW_RAY_COUNT in size
+ */
+bool convertPolyToRayDist(const Vector2* poly, int polyLength, const Vector2& polyCentroid,
+ float* rayDist) {
+ const int rays = SHADOW_RAY_COUNT;
+ const float step = M_PI * 2 / rays;
+
+ const Vector2* lastVertex = &(poly[polyLength - 1]);
+ float startAngle = angle(*lastVertex, polyCentroid);
+
+ // Start with the ray that's closest to and less than startAngle
+ int rayIndex = floor((startAngle - EPSILON) / step);
+ rayIndex = (rayIndex + rays) % rays; // ensure positive
+
+ for (int polyIndex = 0; polyIndex < polyLength; polyIndex++) {
+ /*
+ * For a given pair of vertices on the polygon, poly[i-1] and poly[i], the rays that
+ * intersect these will be those that are between the two angles from the centroid that the
+ * vertices define.
+ *
+ * Because the polygon vertices are stored clockwise, the closest ray with an angle
+ * *smaller* than that defined by angle(poly[i], centroid) will be the first ray that does
+ * not intersect with poly[i-1], poly[i].
+ */
+ float currentAngle = angle(poly[polyIndex], polyCentroid);
+
+ // find first ray that will not intersect the line segment poly[i-1] & poly[i]
+ int firstRayIndexOnNextSegment = floor((currentAngle - EPSILON) / step);
+ firstRayIndexOnNextSegment = (firstRayIndexOnNextSegment + rays) % rays; // ensure positive
+
+ // Iterate through all rays that intersect with poly[i-1], poly[i] line segment.
+ // This may be 0 rays.
+ while (rayIndex != firstRayIndexOnNextSegment) {
+ float distanceToIntersect = rayIntersectPoints(polyCentroid,
+ cos(rayIndex * step),
+ sin(rayIndex * step),
+ *lastVertex, poly[polyIndex]);
+ if (distanceToIntersect < 0) return false; // error case, abort
+
+ rayDist[rayIndex] = distanceToIntersect;
+
+ rayIndex = (rayIndex - 1 + rays) % rays;
+ }
+ lastVertex = &poly[polyIndex];
+ }
+
+ return true;
+}
+
+/**
* Generate a triangle strip given two convex polygons
*
* @param penumbra The outer polygon x,y vertexes
@@ -669,10 +714,9 @@
void SpotShadow::generateTriangleStrip(const Vector2* penumbra, int penumbraLength,
const Vector2* umbra, int umbraLength, VertexBuffer& shadowTriangleStrip) {
const int rays = SHADOW_RAY_COUNT;
- const int layers = SHADOW_LAYER_COUNT;
- int size = rays * (layers + 1);
- float step = M_PI * 2 / rays;
+ const int size = 2 * rays;
+ const float step = M_PI * 2 / rays;
// Centroid of the umbra.
Vector2 centroid = ShadowTessellator::centroid2d(umbra, umbraLength);
#if DEBUG_SHADOW
@@ -683,48 +727,31 @@
// Intersection to the umbra.
float umbraDistPerRay[rays];
- for (int i = 0; i < rays; i++) {
- // TODO: Setup a lookup table for all the sin/cos.
- float dx = sinf(step * i);
- float dy = cosf(step * i);
- umbraDistPerRay[i] = rayIntersectPoly(umbra, umbraLength, centroid,
- dx, dy);
- if (isnan(umbraDistPerRay[i])) {
- ALOGE("rayIntersectPoly returns NAN");
- return;
- }
- penumbraDistPerRay[i] = rayIntersectPoly(penumbra, penumbraLength,
- centroid, dx, dy);
- if (isnan(umbraDistPerRay[i])) {
- ALOGE("rayIntersectPoly returns NAN");
- return;
- }
- }
+ // convert CW polygons to ray distance encoding, aborting on conversion failure
+ if (!convertPolyToRayDist(umbra, umbraLength, centroid, umbraDistPerRay)) return;
+ if (!convertPolyToRayDist(penumbra, penumbraLength, centroid, penumbraDistPerRay)) return;
- int stripSize = getStripSize(rays, layers);
- AlphaVertex* shadowVertices = shadowTriangleStrip.alloc<AlphaVertex>(stripSize);
- int currentIndex = 0;
+ AlphaVertex* shadowVertices = shadowTriangleStrip.alloc<AlphaVertex>(getStripSize(rays));
// Calculate the vertices (x, y, alpha) in the shadow area.
- for (int layerIndex = 0; layerIndex <= layers; layerIndex++) {
- for (int rayIndex = 0; rayIndex < rays; rayIndex++) {
- float dx = sinf(step * rayIndex);
- float dy = cosf(step * rayIndex);
- float layerRatio = layerIndex / (float) layers;
- float deltaDist = layerRatio *
- (umbraDistPerRay[rayIndex] - penumbraDistPerRay[rayIndex]);
- float currentDist = penumbraDistPerRay[rayIndex] + deltaDist;
- float op = calculateOpacity(layerRatio);
- AlphaVertex::set(&shadowVertices[currentIndex++],
- dx * currentDist + centroid.x, dy * currentDist + centroid.y, op);
- }
+ for (int rayIndex = 0; rayIndex < rays; rayIndex++) {
+ float dx = cosf(step * rayIndex);
+ float dy = sinf(step * rayIndex);
+
+ // outer ring
+ float currentDist = penumbraDistPerRay[rayIndex];
+ AlphaVertex::set(&shadowVertices[rayIndex],
+ dx * currentDist + centroid.x, dy * currentDist + centroid.y, 0.0f);
+
+ // inner ring
+ float deltaDist = umbraDistPerRay[rayIndex] - penumbraDistPerRay[rayIndex];
+ currentDist += deltaDist;
+ AlphaVertex::set(&shadowVertices[rays + rayIndex],
+ dx * currentDist + centroid.x, dy * currentDist + centroid.y, 1.0f);
}
// The centroid is in the umbra area, so the opacity is considered as 1.0.
- AlphaVertex::set(&shadowVertices[currentIndex++], centroid.x, centroid.y, 1.0);
+ AlphaVertex::set(&shadowVertices[SHADOW_VERTEX_COUNT - 1], centroid.x, centroid.y, 1.0f);
#if DEBUG_SHADOW
- if (currentIndex != SHADOW_VERTEX_COUNT) {
- ALOGE("number of vertex generated for spot shadow is wrong!");
- }
for (int i = 0; i < currentIndex; i++) {
ALOGD("spot shadow value: i %d, (x:%f, y:%f, a:%f)", i, shadowVertices[i].x,
shadowVertices[i].y, shadowVertices[i].alpha);
@@ -754,26 +781,14 @@
}
/**
- * Calculate the opacity according to the distance. Ideally, the opacity is 1.0
- * in the umbra area, and fall off to 0.0 till the edge of penumbra area.
- *
- * @param layerRatio The distance ratio of current sample between umbra and penumbra area.
- * Penumbra edge is 0 and umbra edge is 1.
- * @return The opacity according to the distance between umbra and penumbra.
- */
-float SpotShadow::calculateOpacity(float layerRatio) {
- return (layerRatio * layerRatio + layerRatio) / 2.0;
-}
-
-/**
* Calculate the number of vertex we will create given a number of rays and layers
*
* @param rays number of points around the polygons you want
* @param layers number of layers of triangle strips you need
* @return number of vertex (multiply by 3 for number of floats)
*/
-int SpotShadow::getStripSize(int rays, int layers) {
- return (2 + rays + ((layers) * 2 * (rays + 1)));
+int SpotShadow::getStripSize(int rays) {
+ return (2 + rays + (2 * (rays + 1)));
}
#if DEBUG_SHADOW
@@ -898,7 +913,3 @@
}; // namespace uirenderer
}; // namespace android
-
-
-
-
diff --git a/libs/hwui/SpotShadow.h b/libs/hwui/SpotShadow.h
index 6727eac..7839dc3 100644
--- a/libs/hwui/SpotShadow.h
+++ b/libs/hwui/SpotShadow.h
@@ -38,9 +38,8 @@
static void computeLightPolygon(int points, const Vector3& lightCenter,
float size, Vector3* ret);
- static int getStripSize(int rays, int layers);
+ static int getStripSize(int rays);
static void smoothPolygon(int level, int rays, float* rayDist);
- static float calculateOpacity(float jf);
static float rayIntersectPoly(const Vector2* poly, int polyLength,
const Vector2& point, float dx, float dy);
@@ -50,7 +49,6 @@
static int intersection(Vector2* poly1, int poly1length, Vector2* poly2, int poly2length);
static void sort(Vector2* poly, int polyLength, const Vector2& center);
- static float angle(const Vector2& point, const Vector2& center);
static void swap(Vector2* points, int i, int j);
static void quicksortCirc(Vector2* points, int low, int high, const Vector2& center);
static void quicksortX(Vector2* points, int low, int high);
@@ -65,8 +63,6 @@
static void generateTriangleStrip(const Vector2* penumbra, int penumbraLength,
const Vector2* umbra, int umbraLength, VertexBuffer& retstrips);
- static const double EPSILON = 1e-7;
-
#if DEBUG_SHADOW
// Verification utility function.
static bool testConvex(const Vector2* polygon, int polygonLength,