–

For a while now, I’ve been trying to figure out a cheap and simple way to create shadows in a 2D environment in order to find out if a point light source would be casting light on a given point. It wasn’t until recently until I sat down and thought about it for a while and realized it would be best for me to start by using **convex shapes**, because this allows the calculations to make a lot of assumptions about the shapes they’re dealing with.

After brainstorming a few options, I figured out that you can create a shadow with a convex shape by just using the **point light’s position** and the **position of the two most “extreme” vertices** of the shape. But how do we find these two vertices?

For every vertex (vert1) and every other vertex (vert2), create **two lines**: one going from vert1 to the point light, and one going from vert2 to the point light. Then, test the angle between the two lines. The two extreme vertices are **whichever two verts create the biggest angle**. (Since we’re just *comparing* angles, we don’t need the actual *value*, so we can substitute the angle formula with (eee!) the dot product between the two lines. In this case, the smaller the dot product, the larger the angle. A -1 dot product in this case would be 180 degrees. Since the shape is convex and the light is hopefully outside the shape, the angle will never be greater than 180 degrees anyway.)

Once those two vertices are found, we need to create the **three yellow lines** shown below, which define one shadow per shape per light.

To perform collision with these lines, we need to do **half-space tests with all three of them**. If they are behind all three, they are not being affected by that point light.

Since the half-space test uses a line normal and a point on the line, it would be best to **store the normals** for the lines, not the lines themselves. (Storing the third normal is simply an optimization; you can still calculate it if you have your two vertices.) Also, be sure to** store LeftVert and RightVert in their proper places**: a simple dot product check can be used to determine whether the vertex is on the **left or right side** of the light.

Since we’re dealing with convex shapes, we can get away with just one line going between the two vertices because the line **never passes through open space**. However, using the line going directly between the two vertices does create an issue: in the image above, the points in the red circle here are technically lit. But, keep in mind that those points are also **inside the shape**, and two solid objects should realistically never be inside each other anyway. (Obviously this check will need to be changed when it comes to rendering, but I find it works well in regards to collision checks.)

Beyond that, there are optimizations that can be done to reduce time spend on collision checks. For example, if the **line segment** joining the two extreme vertices is not touching the **circle** that defines the reach of the light, you don’t need to create the shadow. Also, a more complicated optimization is to not create a shadow if it’s completely encompassed by another shadow, like in the image above.

Your simplification of geometric properties is superb but it, unfortunately, reminds me of work. Being that I have to deal with Collisions of motor vehicles all day.