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

First bookmarklet

Convert

Add reminder on Unix terminal

   echo "DISPLAY=':0' zenity --warning --text 'Tea time'" | at 1756 March 11

You can also make it a bash function as I have done

>> remind () {
    echo "DISPLAY=':0' zenity --warning --text '$@'" | at $1
}

Usage:

>> remind 17:56 Tea Time

>> remind 17:56today Tea Time

>> remind 17:56tomorrow Tea Time

>> remind now+30min Take break

The time formats that "at" command accepts are

At allows fairly complex time specifications, extending the POSIX.2 standard. It accepts times of the form HH:MM to run a job at a spe‐ cific time of day. (If that time is already past, the next day is assumed.) You may also specify midnight, noon, or teatime (4pm) and you can have a time-of-day suffixed with AM or PM for running in the morning or the evening. You can also say what day the job will be run, by giving a date in the form month-name day with an optional year, or giving a date of the form MMDD[CC]YY, MM/DD/[CC]YY, DD.MM.[CC]YY or [CC]YY-MM-DD. The specification of a date must follow the specifica‐ tion of the time of day. You can also give times like now + count time-units, where the time-units can be minutes, hours, days, or weeks and you can tell at to run the job today by suffixing the time with today and to run the job tomorrow by suffixing the time with tomorrow. For example, to run a job at 4pm three days from now, you would do at 4pm + 3 days, to run a job at 10:00am on July 31, you would do at 10am Jul 31 and to run a job at 1am tomorrow, you would do at 1am tomorrow. The definition of the time specification can be found in /usr/share/doc/at/timespec.

What if you want to be reminded every weekday at 6:17 PM to go to gym? For that you can use crontab

> > echo "17 18 1-5 * * DISPLAY=':0' zenity --warning --text 'Tea time'" | crontab -

The first 5 space separated words provide when the script should run in the format "minute hour weekday day-of-month month", followed by the script to execute. Google crontab to learn more.

4 Perl concepts to scare off Beginners

Perl [5.8.6] is a relatively easier language to learn and program, but a tough one if you are trying to read someone's else code. The features in Perl programming language go well beyond, what a beginner is expected to know.

Typeglobs

Today, I just scared off a guy by throwing at him the concept of a typeglob. I conf'ess, that at the time of writing this blog, even I am not clear of the concept of typeglob's. But the point of the blog is to find concepts that Perl beginners don't care to learn about.
Typeglobs are Perl's internal datatype to hold entries in Symbol Tables. Better if you read it from perlmod.

Tie

Well, you can modify the behavior of a normal scalar, array, hash or file handle by using tie. Read more at perltie.

Closures

Not going into technical definition of closures, it's usage for generating iterators is interesting.

Here's a code to demonstrate the usage of closure for reading a tab separated file.

# Closure use case. Here $itr is our closure which will be used as an iterator.
# In Perl terminology, $itr is just a subroutine reference
my $itr = tabfile_itr($ARGV[0], "\t");
while (my $row = $itr->()) {
    # Let's say tabular file has three columns namely name, age and rank
    print "$row->{name} with age $row->{age} has a rank of $row->{rank}\n";
}

# Here's the closure factory. This function takes a file name and a separator
# and returns an iterator that gives a hash reference for each row.
sub tabfile_itr {
    my ($file, $seperator) = @_;
    # Open file
    open(my $fh, "<", $file) or die $!;
 
    # Get the header of file and split by separator
    my $hline = <$fh>;
    chomp $hline;
    my @headers = split $seperator, $hline;

    # Now this thing is called the closure
    my $closure =  sub {
        # The file handle "$fh" was lexically scoped but it will stay
        # statically scoped as long as the $closure is referenced
        my $line = <$fh>;
        chomp $line;
  
        # This is an important part, to break the recursion.
        return unless (defined $line);
  
        # Another lexically scoped variable used in this closure is
        # @headers. To understand each column in the file, we need to
        # have a record of @headers.
        my %col_hash;
        @col_hash{@headers} = split $seperator, $line;
        return \%col_hash;
    };
    return $closure;
}

Read more at perlfaq and perlsub. More closure as iterators examples at perl.com.

use vs require

This is an easy one. "use" runs in the BEGIN block and calls the import function of the package after "require"ing the package. Read more at perldoc -f use.

Sweet Python

My first impression of Python was language that was over-hyped. Now, that I have got to experience and feel it's power, I have begun to love it.

Why not semicolons, braces, dollars, at-the-rates and all the rubbish symbols that have been so long in other programming languages.
That's the first surprise you see, when you get to know Python. Well there may be many reasons like it keeps your fingers in the home row while typing or makes the code looks beautiful. My favorite reason is that it removes redundancy-why have a semicolon when you are going to have a new line anyway; why have pair of braces when you are going to indent and de-indent anyway. I have observed that it does reduces syntax errors, especially when you are away from your favorite on the fly syntax checking IDE.

What is module, function, class, method and object? they are simply types.

Wow! this is coolest feature of Python I have learned so far: Metaclasses. Everything you can see is a type, even in the language it self. And all the classes that we understand in the usual sense are just the predecessors of the type "object". Using these with setattr and getattr, you can generate any kind of code on the fly, even that one which in-turn generates code on the fly. Of course, don't do that because it do not generates a debugger on the fly.

LaTeX for formatting resume

I was looking for something that had macros for formatting my resume. LaTeX was the perfect answer to provide a consistent formatting. Here is my resume and it's tex and the original template page .

LaTeX
LaTeX is like typesetting system to produce standard printable documents like articles, books, reports and resumes.
As in HTML we just provide the content and external CSS files take care of formatting or display. On the same lines, in LaTeX we can provide the content and LaTeX styles or classes take care of the formatting and display.

If you want quick results, you can use an existing resume latex file and replace the contents. You can convert LaTeX to pdf by using online tools.

Getting Started:
http://www.latex-project.org/intro.html

Wiki book is quite helpfull:
en.wikibooks.org/wiki/LaTeX

Other recommended books:

• A beginner's introduction to typesetting with LATEX
• The Latex Companion

Thanks to the LaTeX resume templates (Top few google results for "latex resume"):

• www.rpi.edu/dept/arc/training/latex/resumes/
• www.yisongyue.com/resume/
• www.tedpavlic.com/post_resume_cv_latex_example.php
• people.debian.org/~dburrows/resume-cls.html
• www.derekhildreth.com/blog/latex-resume-examples/

Use online LaTeX to PDF converter, in case you are not planning to install LaTeX.