# 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:

- Green: That part of the line is illuminated.
- Blue: That part of the line is shadowed. If not for another line, it would have been illuminated.
- Red: That part of the line is not illuminated because it is outside of the light’s area.

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:

- For each line L in our scene:
- Figure out what part of the line would be lit given no other lines
- For each other line L’ in our scene:
- Figure out which part of the remaining lit area(s) of L would be shadowed by L’, and shrink or split the lit area(s) as needed

- For each lit area remaining:
- Output a triangle with points at the light source, and the beginning and the end of the lit area

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:

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.

## 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:

`mLightSrc`

: The coordinates of the light source`mDirection`

: The direction the light is currently pointing, as an angle`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!

We begin iterating through each line. Here, `mLines`

is just an array of `PLine`

s 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 `PLine`

s 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 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:

- The intersection between
`mLines[i]`

and`mLines[j]`

- The intersection between
`mLines[i]`

and one of the “rays”

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:

- The light source coordinate
- The coordinate along
`mLines[i]`

of the start of the lit area - 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(*n*^{2}), 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.