Ray Casting

Computer Graphics Rendering

Algorithm

The ray casting algorithm uses lines (rays) within virtual space to represent the path of light from an object to the observer. A ray is emitted from a point on the virtual camera’s projection plane and followed until it hits an object within the virtual scene.

The angle of the ray’s travel is calculated based on the horizontal & vertical field-of-view, combined with the point on the projection plane that the ray originates from and the width & height of the projection plane. Zero degree field-of-view will result in an orthographic projection (no perspective).

Relation to Ray Tracing

Ray casting differs to ray tracing in that the algorithm is halted and no secondary “ray” is emitted towards any light source once an object is hit. In early computer graphics the terms “ray casting” and “ray tracing” were used interchangeably, however these are now considered as two distinct graphics rendering techniques.

Real Time Game Graphics

Ray casting avoids the “hidden surface problem” of 3D raster graphics as the first object the ray hits is guaranteed to be the closest object to the observer at that point on the projection plane. The basic ray casting algorithm is also not affected by the complexity of scene geometry: a highly detailed scene will require the same number of rays across the projection plane as a low detailed scene.

The draw-back of ray casting is that it is computationally expensive to trace each ray, especially in cases where a ray must traverse a great distance before it intersects with an object. This computational requirement is multiplied across the number of rays desired over a projection plane, which for a pixel display equates to the display resolution. A pixel display at 320 × 200 resolution requires 64,000 rays to be cast.

This heavy computational requirement makes ray casting not very ideal for rendering 3D games in real-time, however the algorithm can be applied in other dimensions and by dropping the 3^rd dimension the amount of rays required can be significantly reduced.

2D Space / 3D Projection

Ray casting can be applied to other dimensions than 3D virtual space, in particular it has uses for tracing line-of-sight in 2-dimensional worlds.

This can be used in 2D games (such as a top-down shooter) for real-time lighting effects such as illuminating the cone-of-vision for a player or for projecting shadows cast from 2D light sources in the world.

The limitation of a 2D world also provides an opportunity to reduce the computational requirement of 3D rendering by not casting any rays that are expected to travel in the 3^rd dimension as the world only contains 2D geometry.

To achieve this, the ray-casting algorithm is modified to only cast rays across the horizontal axis of the projection plane, resulting in a flat fan of rays cast from the observer. A pixel display at 320 × 200 resolution requires just 320 rays to be cast across the horizontal axis.

Flattening the 3D ray casting algorithm to only a single axis produces a 1-dimensional projection as only a single row of horizontal rays are cast, projecting onto the 2^nd dimension is no longer possible so further techniques are required to produce the 3D projection.

3D “Wall” Rendering

As the 3^rd dimension has been removed from the world, any information about the height of an object is lost. Only the width and depth of the object is retained in the 2D world. This makes the “height” of the object a more complex concept.

A single, shared “height” can be applied to all the objects to simplify rendering. To make the ray-casting algorithm itself faster all objects can be restricted to square cells on a 2D grid-world. This basic premise results in objects becoming “walls” for a maze-like world.

To project the “height” of the walls from the 1-dimensional ray-cast slice into the 2^nd dimension the inverse distance between the observer and the wall can be used (length of the ray’s path). Distant walls would be short on the projection, closer walls would be tall on the projection. This creates a “fish-eye” effect as the distance of a wall, when faced head-on by the observer, would be further away at the sides than in the middle.

The distance between the wall and the observer is not the correct way to calculate wall height when perspective-correct projection (non fish-eyed) is desired. Instead, the perpendicular distance between the wall and the projection plane itself needs to be used.

The Pythagorean theorem can be helpful here as the length of the ray’s travel would be the hypotenuse and the offset along the ray’s starting point onto the projection plane into the world would be the length of one side of the triangle.

It is also possible to find the perpendicular distance on a 2D grid without the Pythagorean theorem by taking the Manhattan distance between the wall’s position and the observer’s position along a single axis (depending on what side of the wall the ray hit) and dividing by the ray’s movement vector along that same axis.

Additional Enhancements

Data that further describes the world geometry can be added to enhance the ray caster further.

• Texture mapped walls. Calculated based on where (within a cell) the ray intersects with the wall on the grid. Additional information, such as the cardinal direction that the ray hit, can be used for selecting darker textures for North/South walls to make them more visually distinctive.

• Shading walls based on distance for diminished lighting.

• Offset features, such as sliding doors half-way through a cell, a fence or pushable walls.

• Varying height walls with varying floor levels. This would require modification of the ray-casting method to allow the ray to continue travelling, even after it initially hits a wall.

Y Shearing

A side-effect of collapsing the ray casting algorithm to a single dimension for the 2D world is that there is now no way for the observer to change pitch (look up/down).

A close approximation of looking up/down can be achieved through a shear operation (movement) of the projection in the Y direction. This moves the rendered walls up/down the projection plane after projection, which looks similar to the view pitch rotating up/down.

Y shearing is not a technique unique to ray casting and had more success in later Doom-like 3D engines.

Voxel Space Rendering

This application of ray casting was classically used to render realistic landscapes using height-maps.

Whilst it is based on ray casting, it is very different to the 2D Space / 3D Projection technique that is most commonly thought of when discussing ray casting.

The algorithm reverse-loops through slices of a 2D view frustum over a height map (far to near) where each slice corresponds to a point on along the horizontal axis of the projection plane. The distance of the voxel, combined with the value in the height map, calculates the maximum render height on the projection plane.

This results in the “painter’s algorithm” being applied as each slice (which is closer than the previous) will overwrite the rendered voxels of any previous slice if they overlap.

Ray Cast Hit Detection

Modern game engines (Unity, Unreal Engine) use ray casting as a method for quickly finding the first object hit along a line.

For example, a mobile game may require the player to “tap” an object in the 3D world and a ray from the point on the screen that the player’s finger tapped can be cast into the scene to find and return the first object hit (or no object if nothing was hit).

Ray casting can also be used for bullet hit detection in a first person shooter by casting a single ray from the point where the bullet is fired, along the direction of the gun and if an object is hit a more accurate hit detection can then be performed and a decision made for what action to take (such as apply damage or continue ray cast for bullet penetration).

Ray cast is one technique for “hit-scan” weapons, however games may use more appropriate object-line intersection algorithms for their “hit-scan” implementation depending on the type of game.