Controls

Grab and move lights around.

Overview

2D visibility is an interesting problem in graphics and AI. This simulation is based on a tutorial by Red Blob Games which has a great walkthrough of the algorithm.

We start with three light sources in the middle of the canvas. We seed the surrounding area with random points and generate random regular convex polygons. We then cast rays from each light source to all the vertices of the polygons to find where they intersect barriers. To determine if a ray hits an object, we can use a line segement intersection test. We find all collision points for each ray and use the one closest to the light source as the barrier point for that ray. If we then sort the barrier points for each light source in a clockwise order, we can define a polygon enclosing the area visible from that light. Filling in this area with a limited gradient and using colour mixing we can create lights and shadows.

If a ray hits the corner of a polygon (either its target or an aligned point), we would like it to continue past it, rather than stop. An easy way of achieving this is to cast three rays for each polygon vertex, separated by a small epsilon value such that when a ray hits a corner, one of the other two continues past the object. When the difference is very small, the resulting picture will look correct. We are also interested in the visbility of the canvas rectangle and add the four corners of the domain as target vertices for the rays.