Wednesday, August 26, 2009

Raycasting explained

Raycasting can be an extremely useful tool in computer games. There is a lot of confusion on what raycasting really is and how it can be used. I’ll try to explain some it in simple terms and give some simple examples.

Raycasting - as the name suggests involves a ray – but what exactly is a ray?

A ray is part of a line which is finite in one direction, but infinite in the other. It can be defined by two points, the initial point, A, and one other, B.

Source: Wikipedia

In Farseer Physics Engine we define a ray as two vectors; start and end. We can for obvious reasons not have an infinite length ray, we have to have some kind of boundary where the ray stops. This means that rays essentially become lines and then we simply use those lines to test for collisions with other stuff like other lines, AABB or geometries.

Collision testing

There are 4 test cases that can be performed:

  1. Point
  2. Line
  3. AABB
  4. Geometry

The great thing about all those (except number 1) is that they can be reduced to simple line vs. line tests. An AABB is made up of 4 lines and a geometry is made of N (where N > 2) lines. With this in mind we just have to know how to test two lines against each other.

This is done simply by using a linear equation from basic algebra:

d24ebc87176b242c935535a363c5fc10

Using this equation we can create a line. m is the amount that the y-value grows or shrinks with each time x increases by 1. b is point on which the line crosses the y-axis. With this knowledge we can draw a line like this:

OneLine

It has the equation: y = 2*x+1

Now that we know how to create a line, we need a second one to test against:

TwoLines

This line has the equation y = –1*x+1. From what we gathered earlier, b was the point where the line crosses the y-axis. Since both linear equations has a b value of 1, they must be intersecting each other there at (0, 1).

To check for intersections, we take the two equations and simply does an equality check between them and input the result (the value of x) into one of our equations:

image

So our intersection point is at (0,1). Exactly how this is done in code is a little more complicated. In Farseer Physics Engine we implemented line intersection like described here: Intersection Point Of Two Lines

Usage

Now we know that raycasting operates on lines, but how can this be applied to games? Here is a list of a few examples:

  • Collision detection
  • Distance calculation
  • Jumping
  • Lasers
  • Field of view
  • Lightning
  • Suspension
  • Many more…

You can use rays for collision detection and check the distance between the two objects. You can also use it for smooth jumping on to platforms and even car suspension. Another common usage is finding the field of view. The only limit is your imagination.

Ray casts are cheap, but they should not be used for everything. Some physics engines incorporate rays into their broad phase collider to speed up permanent rays. This will soon be implemented into Farseer Physics Engine too.

No comments:

Post a Comment