marekp.io

Spotlight Shadow Algorithm

One of the more interesting mechanics in From Ashes was the spotlights. The spotlight would typically move or rotate around the screen, while getting blocked by anything in the way. Falling into the spotlight would usually result in a quick death by a nearby turret.

Being too stubborn to look up how to achieve the “shadow” effect, I decided to implement it on my own. It may not be the most elegant or efficient implementation, but doing it by myself was much more rewarding.

The big picture

Here is a visual representation of a typical scene involving a spotlight:

First, we make an important simplifying assumption: we assume that everything in our scene is composed of line segments, including the three objects and the edges of the scene shown in the picture. Parts of these line segments are color-coded as follows:

As you can probably see, all we need to do is draw a bunch of triangles with one of the points as the light source, and the other two points along some part of some of the lines. These two points will always lie on the same line. Therefore, we can summarize the algorithm as the following:

We’re now ready to dive into all of the nasty details!

Line intersection

First, we need to do some math. All lines are represented as parametric equations: \[ x(t) = \Delta x \cdot t + x_0 \\ y(t) = \Delta y \cdot t + y_0 \]

In code, we have the following class:

// Parametric line class
class PLine {
public:
    PLine();
    PLine(const Vec2& start, const Vec2& end);

    bool Intersect(const PLine& other, float& t1, float& t2);
    Vec2 At(float t);
    float Dot(const PLine& other);

private:
    float dx, dy, x0, y0;
};

The simplest method is the At() method, which simply returns the coordinate along the line for a given value of t. It just implements the equations above:

Phys::Vec2 PLine::At(float t)
{
    Vec2 p;
    p.x = dx*t + x0;
    p.y = dy*t + y0;
    return p;
}

By convention, we will consider \(t=0\) to be the “start” of the line segment, and \(t=1\) to be the “end.” With these conventions, it’s easy to see that \((x_0,y_0)\) should be set to our start point, and \((\Delta x, \Delta y)\) should be set to our end point minus our start point:

PLine::PLine(const Vec2& start, const Vec2& end)
{
    dx = end.x - start.x;
    dy = end.y - start.y;
    x0 = start.x;
    y0 = start.y;
}

The hardest part is calculating the intersection point of two parametric lines. To avoid mixing up our variables, we’ll temporarily use \(a=\Delta x\), \(b=x_0\), \(c=\Delta y\), and \(d=y_0\). We can rewrite the above equations as: \[ x(t) = a \cdot t + b \\ y(t) = c \cdot t + d \] Given two parametric lines, we now have: \[ x_1(t_1) = a_1 \cdot t_1 + b_1 \\ y_1(t_1) = c_1 \cdot t_1 + d_1 \] \[ x_2(t_2) = a_2 \cdot t_2 + b_2 \\ y_2(t_2) = c_2 \cdot t_2 + d_2 \] The intersection point occurs when \(x_1(t_1)=x_2(t_2)\) and \(y_1(t_1)=y_2(t_2)\): \[ a_1 \cdot t_1 + b_1 = a_2 \cdot t_2 + b_2 \\ c_1 \cdot t_1 + d_1 = c_2 \cdot t_2 + d_2 \] which simplifies to \[ a_1 \cdot t_1 - a_2 \cdot t_2 = b_2 - b_1 \\ c_1 \cdot t_1 - c_2 \cdot t_2 = d_2 - d_1 \] We now have a system of two linear equations with two unknowns \(t_1\) and \(t_2\), which we solve using the magic of Wolfram Alpha: \[ t_1 = \frac{a_2 d_1 - a_2 d_2 + b_2 c_2 - b_1 c_2}{a_1 c_2 - a_2 c_1} \\ t_2 = \frac{a_1 d_2 - a_1 d_1 + b_1 c_1 - b_2 c_1}{a_2 c_1 - a_1 c_2} \] We have one corner case to be mindful of: if the denominator is ever zero, it means the lines were either parallel, meaning they never intersect, or they overlap, in which case they intersect at every point along both lines. After some factoring to simplify the code a bit, we get the following code:

bool PLine::Intersect(const PLine& other, float& t1, float& t2)
{
    // calculate denominator, check if zero
    float den = (dx*other.dy - other.dx*dy);
    if (den == 0)
        return false;

    // calclate numerators
    float dx0 = other.x0 - x0;
    float dy0 = y0 - other.y0;
    float num1 = (other.dx*dy0 + other.dy*dx0);
    float num2 = (dx*dy0 + dy*dx0);

    t1 = num1 / den;
    t2 = num2 / den;
    return true;
}

Intersect() returns true if we found an intersection point, or false otherwise. It also returns the point along both lines where the intersection occured; for example, if the intersection point was 1/4 of the way after the start of line 1 and at the end point of line 2, t1 would be set to 0.25 and t2 would be set to 1. Note that t1 and t2 can be negative or greater than 1, meaning the lines would intersect if they were longer.

The last thing we need is a function to calculate the dot product between the directions of the two lines. Why this is needed will be explained later.

float PLine::Dot(const PLine& other)
{
    return dx*other.dx + dy*other.dy;
}

Calculating lit regions

Before we start iterating through each line, we first want to calculate the boundary lines of our spotlight.

The light is defined by three parameters:

  1. mLightSrc: The coordinates of the light source
  2. mDirection: The direction the light is currently pointing, as an angle
  3. mWidth: The angular width of the light beam

Figuring out the PLine for the light boundaries is therefore just a matter of simple math: \[ \Delta x_1 = \cos(\theta - \phi) \\ \Delta y_1 = \sin(\theta - \phi) \\ \Delta x_2 = \cos(\theta + \phi) \\ \Delta y_2 = \sin(\theta + \phi) \] where \(\theta\) is mDirection and \(\phi\) is mWidth. In code, this becomes:

PLine lightBound1(mLightSrc, Vec2(
    mLightSrc.x + cos(mAngle - mWidth),
    mLightSrc.y + sin(mAngle - mWidth)));
PLine lightBound2(mLightSrc, Vec2(
    mLightSrc.x + cos(mAngle + mWidth),
    mLightSrc.y + sin(mAngle + mWidth)));

We set lightBound1 and lightBound2 to be the boundary lines of our spotlight. Because the PLine class only takes a start and an end point, we must add the light source coordinate for the second argument.

The next thing we need is a data structure to represent lit regions of a line segment. I simply used a list of pairs of numbers, specifically std::list<std::pair<float, float>>, where each pair represents the start and end points of a lit area. For example, if we had the lit areas {0.1, 0.25}, {0.5, 1}, then the lit areas would look something like this:

To make things easier, I made sure that everything in the list and each pair was always sorted, so that iterating through the list would be like walking down the line from start to finish.

Finally, we can begin implemting our algorithm!

for (int i = 0; i < mLines.size(); i++) {
    std::list<std::pair<float, float>> litAreas;

    // ?!
}

We begin iterating through each line. Here, mLines is just an array of PLines for each line in our scene. Importantly, this also includes the screen boundaries.

So, how do we figure out which part of the line should be lit? Well, we could just check where lightBound1 and lightBound2 intersect mLines[i]:

// figure out our intersection points
float tr1, tr2, ti1, ti2;
lightBound1.Intersect(mLines[i], tr1, ti1);
lightBound2.Intersect(mLines[i], tr2, ti2);

// ensure we have the order {start, end}
if (ti1 > ti2)
    std::swap(ti1, ti2);

// add the lit area, being sure to limit the area to the line's boundaries
litAreas.push_back({ std::max(0, ti1), std::min(1, ti2) });

The r in tr1 and tr2 stands for “ray,” as in “light ray.” So, tr1 is the point on lightBound1 where it intersects with mLines[i], and likewise for tr2. Similarly, the i in ti1 and ti2 stands for “line i,” ti1 is the point on mLines[i] where it intersects with lightBound1, and likewise for ti2. We always make sure the first element of the pair is less than or equal to the second one, and we also make sure none of the elements of litAreas are outside the range [0, 1].

Unfortunately, we’ve got a problem: what if tr1 or tr2 is negative?

The code above only works for the case on the left. For the case on the right, tr2 is negative, but the above code would light up the middle portion of the line segment, rather than the end. The problem is the way everything is arranged, the lit area should start at t=0.86 along our line, and continue forever (or until the end of the line). While our intuition tells us that lightBound2 does not intersect with mLines[i], it actually does intersect behind lightBound2, hence the negative value for tr2.

Therefore, we must be able to account for cases then tr1 or tr2 are negative. Note that if they are both negative, then mLines[i] is entirely behind the light, and should have no lit areas, so we can just skip it.

// figure out our intersection points
float tr1, tr2, ti1, ti2;
lightBound1.Intersect(mLines[i], tr1, ti1);
lightBound2.Intersect(mLines[i], tr2, ti2);

if (tr1 < 0 || tr2 < 0) {
    // both negative: mLines[i] is behind the light, skip it
    if (tr1 < 0 && tr2 < 0)
        continue;

    if (tr1 > 0) {
        // tr2 was negative, therefore at ti2 along mLines[i] we are behind the
        //     light, so we want that part to be dark.
        // So, if ti2 was less than ti1, then we want to light up everything
        //     from ti1 upwards to 1. Otherwise, we want to light up everything
        //     from ti1 downwards to 0.
        ti2 = (ti1 < ti2 ? 0 : 1);
    }
    else { // tr2 > 0
        // same as above, but swap ti1 with ti2, and tr1 with tr2
        ti1 = (ti2 < ti1 ? 0 : 1);
    }
}

// if the lit area is entirely outside of the line's boundaries, then
// we must skip this line
if ((ti1 < 0 && ti2 < 0) || (ti1 > 1 && ti2 > 1))
    continue;

// ensure we have the order {start, end}
if (ti1 > ti2)
    std::swap(ti1, ti2);

// add the lit area, being sure to limit the area to the line's boundaries
litAreas.push_back({ std::max(0, ti1), std::min(1, ti2) });

There is one corner case that hasn’t been discussed: what if Intersect() returns false? This occurs when the edge of the light is exactly parallel with the line. To handle this, we will simply pretend that the light boundary line is angled ever so slightly away from the line, so that the intersection point is negative, i.e. tr1 or tr2 is negative, so we set it to -1. Next, we need to set either ti1 or ti2 to match where along mLines[i] our light boundary line would have intersected. If mLines[i] and the boundary line are going in the same direction, then we want the intersection point along mLines[i] to be negative, so we set it to -1; otherwise, we want it to be positive, so we set it to 2. We use the dot product of the lines’ directions to determine if they are going in the same direction.

// figure out our intersection points
float tr1, tr2, ti1, ti2;
bool isect1 = lightBound1.Intersect(mLines[i], tr1, ti1);
bool isect2 = lightBound2.Intersect(mLines[i], tr2, ti2);
if (!isect1) {
    tr1 = -1;
    ti1 = lightBound1.Dot(mLines[i]) > 0 ? -1 : 2;
}
if (!isect2) {
    tr2 = -1;
    ti2 = lightBound2.Dot(mLines[i]) > 0 ? -1 : 2;
}

Calculating shadowed regions

Now it’s time for the really fun part: calculating the shadows! The first thing I will do is define a helper function for adding shadows to our litAreas. This function may need to shrink an existing lit area, split one into two separate lit areas, or even remove a lit area altogether. I don’t this function is too tricky, so I’ll just provide the code here without further explation:

// adds a shadow to the given litAreas
void AddShadow(std::list<std::pair<float, float>>& litAreas, float start, float end)
{
    if (start == end)
        return;

    if (start > end)
        std::swap(start, end);

    auto it = litAreas.begin();

    while (it != litAreas.end()) {
        auto& a = *it;

        // cut off the end of a lit area
        if (start <= a.first && end > a.first && end < a.second)
            a.first = end;

        // cut off the beginning of a lit area
        else if (start > a.first && start < a.second && end >= a.second)
            a.second = start;

        // split a lit area in two
        else if (start > a.first && end < a.second) {
            litAreas.push_back({ end, a.second });
            a.second = start;
        }

        // shadow covers an entire lit area
        else if (start <= a.first && end >= a.second) {
            litAreas.erase(it++);
            continue;  // skip extra ++it at the end of the loop
        }
        ++it;
    }
}

We must now iterate through every other line in the scene:

for (int j = 0; j < mLines.size(); j++) {
    // a line can't cast a shadow onto itself
    if (i == j)
        continue;
    
    // ?!
}

Now, mLines[j] is the shadow casting line, and mLines[i] is the shadow receiving line. At this point, we forget about lightBound1 and lightBound2, and rather try to answer the following question: if the spotlight were emitting light in all directions, what part of mLines[i] would be shadowed by mLines[j]?

First, we create two new PLines from the light source to the start and end points of mLines[j]. We then check to see where these lines intersect with mLines[i], and use that to determine the part of mLines[i] shadowed by mLines[j]. Since these two lines are used repeatedly, we precalculate them before the first loop:

std::vector<PLine> srcToStart, srcToEnd;
for (auto l : mLines) {
    srcToStart.push_back(PLine(mLightSrc, l.At(0)));
    srcToEnd.push_back(PLine(mLightSrc, l.At(1)));
}

for (int i = 0; i < mLines.size(); i++) {
    // ...
}

Now inside the loop, we check the intersection of srcToStart[j] and srcToEnd[j] with mLines[i]:

float tr1, tr2, ti1, ti2;
bool isect1 = srcToStart[j].Intersect(mLines[i], tr1, ti1);
bool isect2 = srcToEnd[j].Intersect(mLines[i], tr2, ti2);
if (!isect1) {
    tr1 = -1;
    ti1 = srcToStart[i].Dot(mLines[i]) > 0 ? -1 : 2;
}
if (!isect2) {
    tr2 = -1;
    ti2 = srcToEnd[i].Dot(mLines[i]) > 0 ? -1 : 2;
}

ti1 and ti2 mean the same thing as before. However, we are now considering the light “rays” as the rays going through the edges of mLines[j]. These effectively become “shadow rays.” Also note that like before, if one of the calls to Intersect() returns false, we consider that equivalent to being angled away from the line, and handle that case in the same way as before.

Now, all we have to do is process these values to figure out which part of the line is shadowed! However, this is much easier said than done, and there are many more corner cases than for just figuring out the lit area.

The above drawing shows the easiest case: tr1 and tr2 are both greater than 1. Like before, we consider the shadow to be cast between ti1 and ti2 along mLines[i].

Our first corner case is when both calls to Intersect() return false. This can only happen when mLines[j] lines up perfectly with the light, and both mLines[i] and mLines[j] are parallel. In this case, we just don’t cast the shadow:

if (!isect1 && !isect2) {
    // line j lines up perfectly towards the light, so it cannot cast a shadow
    continue;
}

Also like before, if both tr1 and tr2 are negative, then mLines[i] is on the opposite side of the light from mLines[j], so it cannot possibly cast a shadow.

if (tr1 < 0 && tr2 < 0)     //both negative
    continue;

If both tr1 and tr2 are between 0 and 1, then mLines[i] must be closer to the light than mLines[j], therefore we should cast no shadow.

if (tr1 >= 0 && tr1 <= 1 && tr2 >= 0 && tr2 <= 1)   //both tr1 and tr2 between 0 and 1
    continue;   //line i is closer to the light than line j

Now for the first hard case: one of tr1 or tr2 is greater than 1, and the other is between 0 and 1. This means some part of mLines[i] is closer to the light than mLines[j], while another part is farther.

From the drawing, we can see that we want the shadowed area to span from the intersection of mLines[i] and mLines[j] to the intersection of mLines[i] and whichever side was farther from the light than mLines[j]. Note that mLines[i] could occupy any section of the green line from the drawing, so it may not actually need any shadows, but would still give the same ranges for tr1 and tr2.

// one >1, one between 0 and 1
if ((tr1 > 1 && tr2 >= 0 && tr2 <= 1) || (tr2 > 1 && tr1 >= 0 && tr1 <= 1)) {
    // if both rays fall outside of line i's range, we don't cast a shadow
    if ((ti1 > 1 && ti2 > 1) || (ti1 < 0 && ti2 < 0))
        continue;

    
    float tij, tji;

    // find intersection between i and j lines
    // if they are parallel, then there is no shadow to cast
    if (!mLines[i].Intersect(mLines[j], tij, tji))
        continue;

    // if the intersection point between lines i and j are not on line i, and
    // that point is on the same side as the intersection point between line i
    // and the greater ray, then the shadow is being cast past the end or
    // before the beginning of the line
    if ((tr1 > 1 && ((ti1 > 1 && tij > 1) || (ti1 < 0 && tij < 0))) || 
        (tr2 > 1 && ((ti2 > 1 && tij > 1) || (ti2 < 0 && tij < 0))))
    {
        continue;
    }
    
    // set either ti1 or ti2 to the intersection point between lines i and j
    if (tr1 > tr2)
        ti2 = tij;
    else
        ti1 = tij;
}

The other difficult case is when one of tr1 or tr2 is negative. Similar to when we calculated the lit areas, this means the shadow being cast goes on forever in one direction.

From the drawings, we see that we want the shadowed area to span from one end of the line to either:

We pick the one that is farther from the negative ray. There are a few other corner cases which need to be covered, but which I won’t go into much detail here. For now, the explainations are simply comments in the source code, and I encourage anyone reading to draw these out on their own.

// one negative: shadow casting starts at one point on the line but never ends
if (tr1 < 0 || tr2 < 0) {
    // line i lies entirely within the gap between ti1 and ti2
    // therefore, we should cast no shadow
    if ((ti1 > 1 && ti2 < 0) || (ti1 < 0 && ti2 > 1))
        continue;
    
    // If the intersection with the positive ray does not lie on line i, and
    // the intersection with the negative ray does lie on line i, then line i
    // must be behind the light, so line j cannot cast any shadows
    if ((tr2 < 0 && ti2 >= 0 && ti2 <= 1 && (ti1 < 0 || ti1 > 1)) || 
        (tr1 < 0 && ti1 >= 0 && ti1 <= 1 && (ti2 < 0 || ti2 > 1)))
    {
        continue;
    }

    // Similar to the above, but this time the intersections with both rays are
    // beyond the same side of the line
    if ((tr2 < 0 && ((ti1 > 1 && ti2 > 1 && ti1 > ti2) || (ti1 < 0 && ti2 < 0 && ti1 < ti2))) ||
        (tr1 < 0 && ((ti2 > 1 && ti1 > 1 && ti2 > ti1) || (ti2 < 0 && ti1 < 0 && ti2 < ti1))))
    {
        continue;
    }

    // cast shadow fron intersection with non-negative r1/r2 to the end of the line
    // if they are parallel, then no shadow can be cast
    float tji, tij;
    if (!mLines[i].Intersect(mLines[j], tij, tji))
        continue;

    if (tr2 < 0) {
        if (ti1 > ti2) {
            ti2 = 1;                   // endpoint
            ti1 = std::max(ti1, tij);  // furthest of intersection with line j or ray 1
        }
        else {
            ti2 = 0;                   // endpoint
            ti1 = std::min(ti1, tij);  // furthest of intersection with line j or ray 1
        }
    }
    else {
        // same as above, but with ti1 and ti2 switched
        if (ti2 > ti1) {
            ti1 = 1;
            ti2 = std::max(ti2, tij);
        }
        else {
            ti1 = 0;
            ti2 = std::min(ti2, tij);
        }
    }
}

Finally, we have all of the cases covered. The only thing left is to add the shadow to litAreas:

// ignore the shadow if it doesn't collide with the line
if ((ti1 < 0 && ti2 < 0) || (ti1 > 1 && ti2 > 1))
    continue;

// add the shadow
AddShadow(litAreas, ti1, ti2);

We now only have a couple more simple things to attend to.

Detecting the player

To detect the player, I simply add the four lines representing the player’s hitbox to the list of lines. Then, check to see if there are any lit areas remaining on any of the lines. If there are, then the player has been seen by the spotlight, and the game should take the appropriate action. Some things to watch out for include making sure the player doesn’t cast any shadows, and making sure we don’t render any lit areas that fall onto the player.

Rendering

Finally, we need to output the list of triangles to be rendered. For each lit area, we add a triangle with the following vertices:

  1. The light source coordinate
  2. The coordinate along mLines[i] of the start of the lit area
  3. The coordinate along mLines[i] of the end of the lit area
for (auto a : litAreas) {
    mVerts.push_back(mLightSrc);
    mVerts.push_back(mLines[i].At(a.first));
    mVerts.push_back(mLines[i].At(a.second));
}

The actual rendering of these triangles is beyond the scope of this article, but you get the idea.

Putting it all together

You can find the “complete” C++ source code for the algorithm here. However, be warned that I have never actually tried to compile this exact code. It should be considered an excerpt of the game’s code, not a complete demonstration, which you could use with some modification. However, if you wanted a complete demonstration…

Demo

Below you can see a live demonstration of the shadow spotlight algorithm. To do this, I ported the algorithm to javascript, which you can view here. It is essentially the same as the C++ code, with added code for rendering and adding or removing lines. The most relevant parts are the PLine class, the addShadow function, and the calculateShadows function.

The demo requires Chrome 49, Firefox 45, Edge 13, or Safari 9. Internet Explorer and Opera are not supported.

Limitations and Possible Improvements

Performance

The time complexity of this algorithm is O(n2), where n is the number of lines in our scene. For more complex scenes, this may be unacceptably slow. The main problem is that we iterate through each and every pair of lines to calculate the shadows. It may be possible to somehow filter these pairs so that we don’t have to check all of them. However, in practice I never ran into a situation where this algorithm was unacceptably slow, so I never looked into these kinds of optimizations.

Code Complexity

The code for this algorithm is rather messy, due to my poor choice of variable names and long conditional statements. It may be possible to summarize all those conditionals in some kind of table, such as in the marching cubes algorithm.