# Speeding up 2D shadow algorithm

I wrote a class to represent a set of lights in a 2D game that raycast in order to find shadows. The draw method does a lot of calculations and takes a lot of time. Mainly, the adding of areas and clipping takes from 1 to 12 milliseconds per loop. Is there any way to speed up this method?

The whole project is on Github.

SmoothLight.java

public class SmoothLight {
/** A Polygon object which we will re-use for each shadow geometry. */
protected final static Polygon POLYGON = new Polygon();

List<Light> lights = new ArrayList<>();

/**
*
* @param center
*            the base light
* @param circles
*            the number of circles per layer
* @param oneLayerProjection
*            the amount of projection of one layer from the previous
* @param layers
*            the amount of layers
* @param angle
*            the angle between each layer
*/
public SmoothLight(final Light center, final int circles, final int oneLayerProjection, final int layers, final int angle) {
// creates layers of lights with the angle between each layer
for (int j = 0; j < layers; j++) {
// how much to rotate this layer counter-clockwise
final int radialDifference = angle * j;
// how much to project this layer
final int projection = oneLayerProjection * j;
final int dif = 360 / circles;
for (int i = radialDifference; i < 360 + radialDifference; i += dif) {
final double x = Math.cos(Math.toRadians(i)) * projection + center.getX();
final double y = Math.sin(Math.toRadians(i)) * projection + center.getY();
final int alpha = center.getColor().getAlpha() / circles / layers;
final Color newColor = new Color(center.getColor().getRed(), center.getColor().getGreen(), center.getColor().getBlue(), alpha);

}
}

}

/**
* @param g
*            the graphics to use for rendering
* @param entities
*            the list of entities to take into account when drawing shadows
* @throws Exception
*/
public void draw(final Graphics2D g, final List<Polygon> entities) {
// old Paint object for resetting it later
final Paint oldPaint = g.getPaint();
// amount to extrude our shadow polygon by

for (final Light light : lights) {

// minimum distance (squared) which will save us some checks

// The area for drawing the light in

for (int i = 0; i < entities.size(); i++) {
final Polygon e = entities.get(i);

final Rectangle2D bounds = e.getBounds2D();

// average to find the entity's radius
final float radius = (float) (bounds.getWidth() + bounds.getHeight()) / 4f;

// get center of entity

final Vec2D lightToEntity = center.minus(light.getPosition());

// get euclidean distance from light to center of the entity
final float distSq = (float) lightToEntity.distanceSq(lightToEntity);

// if the entity is outside of the shadow radius, then ignore
if (distSq > minDistSq) {
continue;
}

// if A never gets set, it defaults to the center
Vec2D A = center;
Vec2D B = center;

// Find the farthest away vertices for which a line segment
// between the source and it do not intersect
// the polygon. Basically, a vertex with a line of sight to the
// light source. Store these two in A and B.
float maxA = 0;
float maxB = 0;
for (int j = 0; j < e.npoints; j++) {
final int x = e.xpoints[j];
final int y = e.ypoints[j];

final float newDistSqred = (float) lineToPointDistanceSqrd(light.getPosition(), center, new Vec2D(x, y), false);

if (maxA < newDistSqred) {
maxB = maxA;
B = A;
maxA = newDistSqred;
A = new Vec2D(x, y);
} else if (maxB < newDistSqred) {
maxB = newDistSqred;
B = new Vec2D(x, y);
}
}

// project the points by our SHADOW_EXTRUDE amount

// construct a polygon from our points
POLYGON.reset();
final Area a = new Area(POLYGON);

// adds to the existing light area
} else {
}
g.setColor(Color.PINK);
}

}
// fill the polygon with the gradient
} else {
// get the inverse of the lightArea and set that as the clip for
final Shape s = g.getClip();
final Area lightArea = new Area(new Rectangle2D.Float(0, 0, LightingTest.getWidth(), LightingTest.getHeight()));

g.setClip(lightArea);
g.setClip(s);
}
if (Debug.OUTLINE_LIGHTS) {
g.setColor(Color.PINK);
g.drawOval((int) light.getX() - 2, (int) light.getY() - 2, 4, 4);
}
}

// reset to old Paint object
g.setPaint(oldPaint);
}

private static double lineToPointDistanceSqrd(final Vec2D pointA, final Vec2D pointB, final Vec2D pointC, final boolean isSegment) {
if (isSegment) {
final double dot1 = pointB.minus(pointA).dotProduct(pointC.minus(pointB));
if (dot1 > 0) {
return pointB.distanceSq(pointC);
}

final double dot2 = pointA.minus(pointB).dotProduct(pointC.minus(pointA));
if (dot2 > 0) {
return pointA.distanceSq(pointC);
}
}
final double dist = pointB.minus(pointA).crossProduct(pointC.minus(pointA)) / pointA.distanceSq(pointB);
return Math.abs(dist);
}

private static boolean lineSegmentIntersects(final float x, final float y, final float x2, final float y2, final Polygon e) {
final int ITERATIONS = 15;
for (int i = 1; i < ITERATIONS; i++) {
if (e.contains(new Vec2D(x + (x2 - x) / ITERATIONS * i, y + (y2 - y) / ITERATIONS * i))) {
return true;
}
}
return false;
}

/**
* Projects a point from end along the vector (end - start) by the given scalar amount.
*/
private static Vec2D project(final float x, final float y, final Vec2D end, final float scalar) {
return project(new Vec2D(x, y), end, scalar);
}

private static Vec2D project(final Vec2D start, final Vec2D end, final float scalar) {
return end.minus(start).unitVector().scalarMult(scalar).plus(end);
}

public void setPosition(final float x, final float y) {
final float differenceX = x - lights.get(0).getX();
final float differenceY = y - lights.get(0).getY();
for (final Light l : lights) {
l.setPosition(l.getX() + differenceX, l.getY() + differenceY);
}
}
}


Light.java

public class Light {
static final Color NULL_COLOR = new Color(0, 0, 0, 0);
private static final float[] SIZE_FRACTION = new float[] { 0, 1 };

public final BufferedImage image;
private float x;
private float y;
Color color;

public Light(final Color c, final Vec2D position, final float radius) {
super();
image = new BufferedImage((int) radius * 2, (int) radius * 2, BufferedImage.TYPE_4BYTE_ABGR);

final Graphics2D g = (Graphics2D) image.getGraphics();

color = c;
setPosition((float) position.x, (float) position.y);
}

public float getX() {
return x;
}

public float getY() {
return y;
}

public void setPosition(final float x, final float y) {
this.x = x;
this.y = y;
}

}

public Color getColor() {
return color;
}

}


(Note: The first part of this answer was written without a detailed analysis. See the "EDIT" below for an update)

An interesting question. Some (possibly minor?) remarks and hints.

(Disclaimer: I currently can't do a dedicated performance analysis with VisualVM & Co. So You should consider the following only as hints, and possible points to look at, but not as a "todo list". Modifications of existing code that aim at improving the performance should be done step by step, and interveaved with detailed benchmark and profiler runs.)

• In your Light class, you are creating an image with a type TYPE_4BYTE_ABGR. Usually, images with the type TYPE_INT_ARGB are the fastest (or TYPE_INT_RGB when no transparency is required)

• A class like the Vec2D class in the GitHub repository is very convenient. However, one should keep in mind the possible drawbacks of repeated allocations in such chained calls like dot2 = pointA.minus(pointB).dotProduct(pointC.minus(pointA)). It's hard to measure the direct impact on the performance, but the repeated object allocations might at least impose a workload on the Garbage Collector that could be avoided. The Escape Analysis has improved significantly in the recent Java versions, but it's still something that you should keep an eye on.

• Most of the above mentioned usages of Vec2D are in helper methods of the SmoothLight class. For example, the method lineToPointDistanceSqrd, which computes the squared distance of a point to a line or a line segment. You should consider replacing this method with the corresponding methods from the Line2D class, namely Line2D#ptLineDistSq and Line2D#ptSegDistSq.

• The lineSegmentIntersects method, particularly the ITERATIONS counter, looks dubious. I'll have to analyze this further (to make sure that the result is equivalent), but you might consider replacing this with a test whether the given line intersects one edge of the given polygon, using Line#linesIntersect

• Operations on Areas can be expensive. Again, it's hard to analyze this much code in detail. But you could consider to not compute the light- and shadow areas with the Area class, but instead create these Shapes manually, by connecting the intersection points (ordered clockwise around the light source) and build a Path2D that describes the shape of the lit area.

Finally, two links to questions on stackoverflow where I wrote answers that contain "building blocks" that may be useful here. Note that these answers did not primarily aim at achieving a particularly high performance, but ... I did not try to post rubbish there either, so there might be some useful snippets involved:

• How to do 2D shadow casting in Java? : My answer here basically contains the code that was roughly created based on the description on the site linked in the original question. It shows one way of computing the shadow/light areas. This computation involves some tricks (as described on the site), and should do the computation of the light shape rather efficiently (for example, without using the Area class)

• Java2D Alpha Mapping images: Here, my answer shows how it is possible to apply a "light effect" to an image. This could be a way to avoid the use of "light images" altogether, by just painting the light shape directly into the target image, with an appropriate RadialGradientPaint and AlphaComposite.

(By the way: Extending the program from the first answer to create "soft" shadows was still on my todo-list - I'll probably try to combine my answers and try to achieve the same effect as in your program, to see which of these approaches perform better and where the potential bottlenecks are)

EDIT Extended based on a further analysis

I performed some tests, mainly with jVisualVM, which showed that the main bottlenecks are not the usual suspects like the geometry computations or other high-level methods, but really in the low-level ones: Most of the time seems to be spent...

• in the g.drawImage(light.image...) call of the SmoothLight#draw method
• in the GraphicsUtils#glowFilter method

and, the largest block:

• when the lightmap is drawn using the BLUR_FILTER

Drawing this blurred image (with size 1024x768 - slightly larger than your original one) takes ~40ms on my machine - in contrast to 1-2ms of a simple call like g.drawImage(lightmap, 0, 0, null);.

I've seen that you are already using a FastBlurFilter (by Romain Guy - he usually knows his stuff...), which internally exploits the fact that the blur can be implemented as a separable filter. However, this could possibly be implemented even faster through parallelization. A quick tests indicates that this might bring a speedup, but your mileage may vary (depending on the CPU, the image size and other factors...). However, you might try replacing the blur function of this filter with something like this:

    private static final ExecutorService executor =

static void blur(final int[] srcPixels, final int[] dstPixels,
final int width, final int height, final int radius)
{
final int windowSize = radius * 2 + 1;

final int[] sumLookupTable = new int[256 * windowSize];
for (int i = 0; i < sumLookupTable.length; i++)
{
sumLookupTable[i] = i / windowSize;
}

final int[] indexLookupTable = new int[radiusPlusOne];
{
for (int i = 0; i < indexLookupTable.length; i++)
{
indexLookupTable[i] = i;
}
}
else
{
for (int i = 0; i < width; i++)
{
indexLookupTable[i] = i;
}
for (int i = width; i < indexLookupTable.length; i++)
{
indexLookupTable[i] = width - 1;
}
}

for (int y = 0; y < height; y++)
{
final int fy = y;
final int srcIndex = y * width;
Callable<Object> callable = Executors.callable(new Runnable()
{
@Override
public void run()
{
srcIndex);
}
});
}
try
{
}
catch (InterruptedException e)
{
}
}

private static void process(final int[] srcPixels,
final int[] dstPixels, final int width, final int height,
final int[] sumLookupTable, final int[] indexLookupTable, int y,
int srcIndex)
{
int pixel;
int sumAlpha;
int sumRed;
int sumGreen;
int sumBlue;

sumAlpha = sumRed = sumGreen = sumBlue = 0;

int dstIndex;
dstIndex = y;

pixel = srcPixels[srcIndex];
sumAlpha += radiusPlusOne * (pixel >> 24 & 0xFF);
sumRed += radiusPlusOne * (pixel >> 16 & 0xFF);
sumGreen += radiusPlusOne * (pixel >> 8 & 0xFF);
sumBlue += radiusPlusOne * (pixel & 0xFF);

for (int i = 1; i <= radius; i++)
{
pixel = srcPixels[srcIndex + indexLookupTable[i]];
sumAlpha += pixel >> 24 & 0xFF;
sumRed += pixel >> 16 & 0xFF;
sumGreen += pixel >> 8 & 0xFF;
sumBlue += pixel & 0xFF;
}

for (int x = 0; x < width; x++)
{
dstPixels[dstIndex] =
sumLookupTable[sumAlpha] << 24
| sumLookupTable[sumRed] << 16
| sumLookupTable[sumGreen] << 8
| sumLookupTable[sumBlue];
dstIndex += height;

int nextPixelIndex = x + radiusPlusOne;
if (nextPixelIndex >= width)
{
nextPixelIndex = width - 1;
}

int previousPixelIndex = x - radius;
if (previousPixelIndex < 0)
{
previousPixelIndex = 0;
}

final int nextPixel = srcPixels[srcIndex + nextPixelIndex];
final int previousPixel =
srcPixels[srcIndex + previousPixelIndex];

sumAlpha += nextPixel >> 24 & 0xFF;
sumAlpha -= previousPixel >> 24 & 0xFF;

sumRed += nextPixel >> 16 & 0xFF;
sumRed -= previousPixel >> 16 & 0xFF;

sumGreen += nextPixel >> 8 & 0xFF;
sumGreen -= previousPixel >> 8 & 0xFF;

sumBlue += nextPixel & 0xFF;
sumBlue -= previousPixel & 0xFF;
}

srcIndex += width;
}


(This was just quickly created by extracting the core of the method and parallelizing it pragmatically - it may be cleaned up and improved).

The GraphicsUtils#glowFilter method might be parallelized similarly, but there, the parallelization might imply an overhead that eats up the performance gains (though I have not tested it).

An aside: When you call Graphics g=image.getGraphics(), you should eventually dispose the graphics object, by calling g.dispose() when you're done with it. You did not dispose the graphics, for example, in the Light constructor (but I have not systematically looked for this).

Apart from that, it's not so easy to make this program faster in its current form. As mentioned in the first part of the answer: I also tried to implement something like this, based on my other answers on stackoverflow, but in its current version it's far slower than your approach. Although it looks a bit nicer, I think:

(I tried to properly mix the lights: A magenta light and a green light should yield a white light - things like this don't come for free...).

But, the same as with your approach: Making the shadows soft definitely IS expensive.

One could try to think of a completely different approach here, I'm sure the computer graphics / OpenGL community already had some ideas about this. But this is beyond what can be discussed here...

• Wow, I haven't gone through everything you've said yet, but the 4BYTE vs INT already improved my fps by about 20. – Kyranstar Mar 7 '15 at 3:03
• @Kyranstar I'm currently using an ancient PC where the FPS was only 4 to 5 anyhow... I'll definitely revisit this question and analyze it further, when I have access to my real development machine. Until now, these hints should really be taken with a grain of salt. Don't put toooo much effort into changes that might not even bring an advantage (the image type was one of the easier ones here, of course...) – Marco13 Mar 7 '15 at 3:10

It doesn't make much performance difference, as you don't call the SmoothLight constructor enough to matter. However, you repeat several calculations unnecessarily.

        for (int j = 0; j < layers; j++) {
// how much to rotate this layer counter-clockwise
final int radialDifference = angle * j;
// how much to project this layer
final int projection = oneLayerProjection * j;
final int dif = 360 / circles;
for (int i = radialDifference; i < 360 + radialDifference; i += dif) {
final double x = Math.cos(Math.toRadians(i)) * projection + center.getX();
final double y = Math.sin(Math.toRadians(i)) * projection + center.getY();
final int alpha = center.getColor().getAlpha() / circles / layers;
final Color newColor = new Color(center.getColor().getRed(), center.getColor().getGreen(), center.getColor().getBlue(), alpha);

}
}


Note that alpha and newColor are constant relative to both i and j; dif is constant relative to j. Since none of those change in the loops, you can calculate all of those first rather than waiting.

        final int dif = 360 / circles;
final int alpha = center.getColor().getAlpha() / circles / layers;
final Color newColor = new Color(center.getColor().getRed(), center.getColor().getGreen(), center.getColor().getBlue(), alpha);

for (int j = 0; j < layers; j++) {
// how much to rotate this layer counter-clockwise
final int radialDifference = angle * j;
// how much to project this layer
final int projection = oneLayerProjection * j;

for (int i = radialDifference; i < 360 + radialDifference; i += dif) {
final double x = Math.cos(radialAngle) * projection + center.getX();
final double y = Math.sin(radialAngle) * projection + center.getY();

}
}


I also changed it to only calculate the radian version of i once rather than twice.

I also created another version that loops in radians rather than degrees.

        int projection = 0;
final double dif = 2 * Math.PI / circles;
final int alpha = center.getColor().getAlpha() / circles / layers;
final Color newColor = new Color(center.getColor().getRed(),
center.getColor().getGreen(), center.getColor().getBlue(), alpha);

// creates layers of lights with the angle between each layer