Raycasting the easy way?

During work on a side-project, I required an efficient algorithm for performing dynamic line-of-sight calculations. This is where, in a world containing any number of sight-blocking positions in any arrangement, we calculate all of the visible points from any one given point. But the process is quite CPU intensive, even with a custom lookup table for the math functions.

I refuse to sacrifice simulation integrity for performance, and in theory it seemed like a better algorithm should be possible by simply expanding outwards and remembering obstructions along the way, so I decided to attempt an implementation.

Why should such an algorithm exist?

Because we have a very significant pattern in that the ray source is static. Existing algorithms do not seem to make full use of that fact.

To take obstructions as an example: If you only travel along rays of sight, then you never look behind an object. I don’t have to look behind a wall to know I can’t see behind it.

Every ray cast provides information for many other rays further from the origin than itself. If we propagate this information outwards, we need never look at inner points again.

This is like line-drawing, except that we need to draw a lot of lines. Described here is a method for following every ray from a single point simultaneously and without redundancy.

The method.

In practice, it’s more efficient to assume we are on rays of sight, and instead generate rays of obscurity whenever we strike a blocking position.

Keeping track of these rays of obscurity while expanding our vision is really our only task – everything follows from this. So this is a method to remember those rays of obscurity (or in fact any effect).

The explanation that follows is based on a 2D world, but adding a third dimension is straight-forward.

----

Divide the world up into an evenly spaced grid and mark all ray-blocking positions (which we will call obstructions). The algorithm needs a reference to this for looking up obstructions.

Starting from the ray source position, initiate a breadth-first traversal of the grid. The children of a node are the grid positions adjacent to it travelling parallel to the axes, away from the origin. E.g. Positions on an axis (like (2, 0)) will have three children ((3, 0), (2, 1), (2, -1)), other positions (like (4, 5)) will have two ((4, 6), (5, 5)).

This means that most grid positions will have two parent positions (the two grid positions closer to the origin travelling parallel to the axes). We call the parent positions ‘inputs’.

On an empty grid, this arrangement is not particularly useful. But when we encounter obstructions, it is quite beneficial.

When the traversal hits a ray-blocking position, we store the direction (relative to the origin) of that position in our search node. We also store error data in the search node (although at the blocking position it is of course zeroed).

When we generate the children of a ray-blocking position, those search nodes receive a copy of the ray-blocking direction data, as well as error data adjusted according to their position relative to the ray. In fact, we do this for any children of nodes carrying effect ray data, as long as they are close enough to the ray (within a certain error margin).

So in effect we begin propagating a ‘ray of obscurity’ whenever we strike an obstruction. We know that if the error of a position from such a ray is small enough, then a ray to that position must have passed through the obstruction, and hence the position should be obscure.

Because of the way we are storing ray data, it is possible for one ray’s data to overwrite another ray’s data. For these cases we have a policy where we only allow overwrites if a propagated ray is in the process of switching rows or columns (because it will go out of the error bounds on the other child). Because both rays have the same source, they are always travelling apart, so we never have a case where one ray actually collides with another by reducing its own error.

This is where the redundancy in writing to both children comes in handy – if one child is appropriated by another ray, we continue the ray with the other. If both children have their data hijacked, we know that any position on our ray would have been within the ‘arc of effect’ created by the hijacking rays.

This ‘arc of effect’ is the implication that if a position has rays of obscurity passing directly by on both sides, then a ray to that position will have crossed one of the effect-generators (e.g. obstructions) that produced those rays. We can initiate a cull on these grounds – knowing that we are inside an arc of effect, we can cease looking for the effect. We propagate the cull whenever a position has any combination of null (culled) inputs, and inputs which show rays of obscurity passing by.

For line of sight, at least, this is all we have to do. Positions that are on or close to a ray of obscurity are obscure, as are any positions that we didn’t look at (were culled). Everything else is visible.

Generally speaking..

A world may contain positions which apply effects to rays, which are part of the rules of the world. By referral to the rules, we know when we are at a position that applies an effect.

If every position is relative to the ray source (our origin), we know what direction any encountered effect position lies on. If we propagate this effect information when we expand our search outwards, then we always know whether the position we are looking at lies in the path of a ray of effect.

So we need a way to propagate effect information when we expand our search. An effect is simply made up of direction information. When we expand a perimeter which contains effect data, the new (child) nodes carry some of that effect data with them.

Specifically, this extra information describes the effect ray’s direction, and the position’s divergence from it. Represented efficiently, this is another set of vector data plus error data. Every effect generates a ray of effect, and every ray of effect is carried through the search.

If we can accomplish this, then we always know whether a position we are looking at carries the effect, which is the goal of the algorithm.

To carry the effect along a ray, we move the ray in all dimensions, adjusting any error data appropriately. In other words, we generate new endpoints by moving parallel to each axis away from the origin. Of course, this means ray data may overlap, but we have a copy of the ray data for every axis. And as long as our overlap policy consistently chooses the ray which will result in the largest area/volume of effect, it doesn’t matter if all of our copies are overwritten, because in that case, the ray would have been within the effect area anyway.

This obviates the need to cast rays into an arc (or cone) of effect, - we can start cutting search branches on the condition that rays of effect surround it. This is because we know that these rays have the same origin, so we must be within an arc (or cone) of effect. (Any ray immediately within two effect rays must have passed through one of the nodes that produced those rays.)
We propagate a cut by culling endpoints with any combination of null (culled) inputs and inputs which show rays of obscurity passing by.

Every node in the area/volume is only checked once at most, and we only need to store data for the current perimeter (actually it is possible to run through chunks of arbitrary size (see extensions), so memory complexity should not be an issue). As an added bonus, the entire operation can be completed without using divisions – only comparisons, addition, and subtraction are used in the (Java) implementation posted here.

Demonstration implementation. http://argus.fileave.com/raymulticast3.zip

The implementation is perhaps not canonical, but it is as simple as I could make it, and quite easy to follow. Note that the pictures posted actually come from an earlier version, not the linked implementation, but they both produce similar data, so as long as you get the idea.

The blue spot is the origin, the red spots are map obstructions, and the white area is visible. For the occluded areas, black positions show an edge of an occluded area, dark gray nodes are those that were ignored (didn’t get expanded), and light gray nodes are those that were never looked at (since they were assumed to be in the area of effect).

Extensions

Obviously, the demonstrated algorithm can be easily extended to work with a third dimension for 3D processing by adding Z components to the world, the search nodes, and the effect data.

Though we demonstrate obstructions here, note that any data which is carried along rays from the origin can be carried with the rays – the data would just have a different effect. Or we can transport multiple effects on search nodes by adding separate effect data. If rays only carry one effect, and the effect operation is idempotent (as it is with obstructions), then we can still perform culling, as we can assume that any unsearched position has the effect.

If perimeter memory is an issue, it is possible to simply set the world to falsify obstructions in the directions you do not wish to compute at the time, or start the expansion in a different place to the origin (e.g. start at (1, 1) for just the lower right quadrant.
Another option is to divide a high-resolution scene up into smaller areas/volumes. Then perform searches on each area/volume, starting the search from the innermost point (relative to the origin). If you remember the outer edges of the input grids, then you have all of the data necessary to continue a search, and so on.

Distance-limited rays can easily be accomplished by adding all expansions for the current perimeter to a separate data structure, incrementing a ‘count’, and then adding all expansions from there back into the original data structure. i.e. just count when each ‘ring’ is expanded, and stop at a predefined count.

It is also possible for obstructions to produce arcs/cones by making obstructions a special case which generate diverging child rays. This has the effect of reducing the viewer’s size relative to obstruction sizes, which would be needed if we wanted points to represent larger areas. Scaling the ray data upwards is necessary when doing this, and there may be a number of edge cases produced.