patternjavaMinor

Speeding up 2D shadow algorithm

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

speedingalgorithmshadow

Problem

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 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 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
final float minDistSq = light.getRadius() * light.getRadius();

// The area for drawing the light in
Area shadowArea = null;

for (int i = 0; i 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. Basical

Solution

(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 =
Executors.newCachedThre

Code Snippets

private static final ExecutorService executor = 
        Executors.newCachedThreadPool();

    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 radiusPlusOne = radius + 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];
        if (radius < width)
        {
            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;
            }
        }

        List<Callable<Object>> tasks = new ArrayList<Callable<Object>>(height);
        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()
                {
                    process(srcPixels, dstPixels, width, height, radius,
                        radiusPlusOne, sumLookupTable, indexLookupTable, fy,
                        srcIndex);
                }
            });
            tasks.add(callable);
        }
        try
        {
            executor.invokeAll(tasks);
        }
        catch (InterruptedException e)
        {
            Thread.currentThread().interrupt();
        }
    }

    private static void process(final int[] srcPixels,
        final int[] dstPixels, final int width, final int height,
        final int radius, final int radiusPlusOne,
        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

Context

StackExchange Code Review Q#83235, answer score: 4

Revisions (0)

No revisions yet.