Ray tracing using time to collision

1 Motivation

Imagine a 2D grid world with obstacles and walls in the form of blocks. Imagine a robot with a laser sensor inside this world. I am given the position of the robot and the angle at which laser is emitted, I want to know the grid cell with which this laser collides and the exact position where it collides.

I had a look at Stage library, but I was not able to understand the code in world.cc properly. It cites a book called Graphics Gems IV to which I didn’t have access. So to understand the algorithm, I derived it from first principles, which you will see is not very difficult.

2 Notation

Let the size of grid cells be denoted by $\left(\Delta x,\Delta y\right)$ and the unit vector along the ray be denoted by $\left(dx,dy\right)$. The distance from the nearest grid walls in the direction of ray be denoted by $\left(e_x,e_y\right)$. Assume that the ray is as given in Fig 1 and intersects consecutive grid lines at $P_1$ and $P_2$.

---

Figure 1: A ray intersecting with grid lines in a grid world

---

3 Derivation

For ray tracing we want to find all the grid cell from which the ray crosses. Since we can do it recursively, support we are at point $P_1$ and want to find point $P_2$. The first question to be answered is whether $P_2$ lies on the Y-axes or X-axes. In the case of given diagram, $P_2$ lies on the Y-axes, or we have taken one step along X-axes. However, if the slope was greater than $45^{\circ }$ than the line would have crossed the gridline $x=0.5$ earlier than $y=1.5$. This can be easily detected by the sign of $e_{y2}$.

$$\begin{array}{lll}\hfill e_{y2}& =e_{y1}-e_{x1}\frac{dy}{dx}& \hfill \text{ (1)}\\ \hfill & & \hfill \text{ (2)}\end{array}$$

We take a step along X-axes when $e_{y2}>0$ or

$$\begin{array}{lllll}\hfill e_{y1}-e_{x1}\frac{dy}{dx}& >\; 0& \hfill & & \hfill \text{ (3)}\\ \hfill \frac{e_{y1}}{dy} & >\frac{e_{x1}}{dx}& \hfill \text{ Assuming }dy>0& & \hfill \text{ (4)}\end{array}$$

Now, we just need a recursive formula for $e_{xt}$ and $e_{yt}$. Let’s compute $e_{x2}$ and $e_{y2}$ for this case when we know that $\frac{e_{y1}}{dy}>\frac{e_{x1}}{dx}$.

$$\begin{array}{lll}\hfill e_{y2}& =e_{y1}-e_{x1}\frac{dy}{dx}& \hfill \text{ (5)}\\ \hfill \frac{e_{y2}}{dy}& =\frac{e_{y1}}{dy}-\frac{e_{x1}}{dx}& \hfill \text{ (6)}\end{array}$$

Aren’t we lucky that we got a formula of $\frac{e_{y2}}{dy}$ in terms of $\frac{e_{y1}}{dy}$ and $\frac{e_{x1}}{dx}$? Both the terms we already knew and needed to compute for comparison. Also note that $\frac{e_{x2}}{dx}$ is simply $\frac{\Delta x}{dx}$.

Also doesn’t the fraction $\frac{e_x}{dx}$ looks something meaningful? Note that $\frac{e_x}{dx}$ is proportional to $\frac{e_x}{dx∕dt}$ which is makes me think it in terms of distance to next gridline upon velocity. This term is nothing but time to collision to nearest gridline. Lets denote this terms as $t_x=\frac{e_x}{dx}$. We can also think of $T_x=\frac{\Delta x}{dx}$ as maximum possible time to collision when travelling along X axes. Using this simpler notation our recursive formula are:

So the complete recursive formula can be written as:

$$\begin{array}{lll}\hfill \left(t_{xt+1},t_{yt+1}\right)& =\left\{\begin{array}{cc}\left(T_x,t_{yt}-t_{xt}\right)\hfill & \text{ if }{t}_{yt}>t_{xt}\hfill \\ \left(t_{xt}-t_{yt},T_y\right)\hfill & \text{ otherwise}\hfill \end{array}\right.& \hfill \text{ (7)}\end{array}$$

Extension to 3D case is trivial:

$$\begin{array}{lll}\hfill \left(t_{xt+1},t_{yt+1},t_{zt+1}\right)& =\left\{\begin{array}{cc}\left(T_x,t_{yt}-t_{xt},t_{zt}-t_{xt}\right)\hfill & \text{ if }{t}_{yt}>t_{xt}\wedge t_{zt}>t_{xt}\hfill \\ \left(t_{xt}-t_{yt},T_y,t_{zt}-t_{yt}\right)\hfill & \text{ if }{t}_{xt}>t_{yt}\wedge t_{zt}>t_{yt}\hfill \\ \left(t_{xt}-t_{zt},t_{yt}-t_{zt},T_z\right)\hfill & \text{ otherwise}\hfill \end{array}\right.& \hfill \text{ (8)}\end{array}$$

4 Algorithm