In search of the Visibility Polygon

I have been building a 2D game for fun recently. Once I implemented a basic lighting system for it, I understood that I want game objects to cast shadows. There are multiple ways to achieve that, and the approach I selected is based on visibility polygons.

A visibility polygon represents the area that, for a given arrangement of occluding objects, has a direct line of sight to a certain point (called the query point). You can read more about them here:

• Visibility polygon on Wikipedia
• 2D Visibility on Red Blob Games

I find the problem of calculating the visibility polygon interesting, and in this post I will tell you how I implemented an algorithm that finds them. I think the algorithm itself and the optimisations involved are conceptually cool, so I am excited to illustrate and describe them.

The algorithm I implemented is based on a description I found in ¹ under the section «3.2 Algorithm of Asano». That paper actually suggests a different algorithm for this problem, but I found the algorithm of Asano more fun. That paper also references a source for the algorithm ² , but I found the short description more interesting to work with. Also, ² is quite hard to access.

In this post I will describe the implementation of that algorithm. There are some basic concepts I expect the reader to be familiar with, I will cover them briefly. There will also be some additional ideas that I will explain in more detail further in the post.

Algorithm inputs and outputs

The algorithm needs the following inputs:

• a query point $Q$,
• a set of segments $\mathbf{S}$.

No segment in $\mathbf{S}$ should include $Q$.

No two distinct segments in $\mathbf{S}$ are allowed to intersect, unless their intersection is a single point that is an endpoint of both of those segments.

Running the algorithm produces a set of segments $\mathbf{S}_Q$ that represents the surfaces visible from $Q$. Each segment in $\mathbf{S}_Q$ is a subset of some segment from $\mathbf{S}$.

From $\mathbf{S}_Q$, the actual polygon can be obtained by combining the endpoints of each of the segments in $\mathbf{S}_Q$ with $Q$ to form triangles. The polygon is the union of all such triangles

The outline of the polygon can also be trivially generated with a slight modification to the algorithm, which is left as an exercise for the reader.

Algorithm overview

To calculate the visibility polygon, we will «visit» all of the segment endpoints, keeping track of which segment is the nearest to $Q$ at all times.

This is a sweep line algorithm ¹¹. The sweep line in this case is the line that connects $Q$ with the current endpoint. As the current endpoint changes, the line rotates around $Q$.

Let $n$ be the number of segments in the input.

This problem can be solved naively in $O(n^2)$ time. For example:

1. Sort segment endpoints by their position relative to $Q$.
2. For each endpoint $E$, find all intersections between $EQ$ and all other segments. Use that information to keep track of which segment is the nearest to $Q$.
3. Whenever the segment nearest to $Q$ changes, register that, and build up the visibility polygon out of the relevant subsegments.

An optimisation allows us to cut down the time to $O(n \, \text{log} \, n)$. Instead of keeping track of just the nearest segment, we will keep track of all segments that are currently intersected by our sweep line (henceforth called active segments).

As the sweep line goes through segment endpoints, we will be «activating» and «deactivating» corresponding segments. In practice, given some endpoint, it can be difficult to tell what to do with it on the fly. For this reason, all endpoints are designated as $\text{Start}$ or $\text{End}$ events. See Ordering endpoints within a segment.

To keep track of currently active segments, an ordered set can be used. Common implementations of ordered sets ¹² can do insertion and removal in $O(\text{log} \, n)$ time – that’s exactly what we need!

Note, though, that we need to define the ordering between the segments to store them in an ordered set. It’s a bit tricky to do, so see Ordering segments by distance to a point.

Summary

Time to bring this all together. This is what the algorithm does:

1. Prepare the input data:
   • Create a set of all segment endpoints, keeping track of which segment they came from;
   • For each of the endpoints, designate it is a $\text{Start}$ or an $\text{End}$ event;
   • Order the endpoints based on the direction from $Q$ to the endpoint.
2. Determine the initial state – choose the first endpoint and find all segments that are active when the sweep line passes through it.
3. Go over all events, doing the following:
   • Activate the segment if this is a $\text{Start}$ event,
   • Deactivate the segment if this is an $\text{End}$ event,
   • Save a new visibility segment whenever the segment closest to $Q$ changes.

Let’s go through an example, and then we can look into the fun implementation detais.

Example

In this example, we will …

Let’s define some example input data. The input data consists of the point $Q$ and a set of segments $\mathbf{S}$. You can see the input configuration in Fig. 3.1. It contains the point $Q$ (the star in the middle) and 16 segments (purple lines) connecting 16 points.

Note the 4 segments $R_1R_2, R_2R_3, R_3R_4, R_4R_1$ that together form a rectangle that surrounds everything else. This guarantees that there is at least one segment in any direction from $Q$, as explained in the Side note: Implications on the output.

For simplicity, let’s say that $Q = (0, 0)$. Let’s also choose coordinates for all of the points:

And, based on those points, let’s define the set of occluding segments

We need to order all segment endpoints by their position relative to $Q$. For each point $E$, let’s find the angle $\overrightarrow{QE}$ makes with the $X$-axis. It can be calculated using the function

Implementation details

Ordering endpoints within a segment

Determining whether a point lies in a half-plane

A naive implementation of $\text{cmp}_Q$ can …

…

Ordering segments by distance to a point

The algorithm features a segment comparison routine that is aimed at decreasing the cost of performing the comparison by reducing the number of required floating point operations.

The cheap segment comparison routine is only valid under the following assumptions:

1. Any two segments can only be compared between each other if a line can be drawn that includes the query point and a point from each of the segments
2. The segments do not intersect between each other with the exception of intersections that yield their endpoints

The comparison routine can be simplified if all segments collinear with the query point are removed from the input data. For completeness, cases when the query point is collinear with the segments are still considered below.

Both segments are collinear with the query point

One of the segments is collinear with the query point

None of the segments are collinear with the query point

Reducing input size

…