Phrase of the week

May 5, 2013 at 2:00 PMMichele Mottini

It's usually difficult to make the complicated case easy; that's why it's called the complicated case.

Raymond Chen, in 'Another way to create a process with attributes, maybe worse maybe better'

Posted in: Opinion

Tags:

Billiard simulation – part 2: detect collisions

May 4, 2013 at 11:07 AMMichele Mottini

First of all, what exactly ‘detect collisions’ means? As explained in the previous post the update algorithm needs the time of the next collisions between two balls and between a ball and the sides of the table – so ‘detecting collisions’ means computing these times for all the balls.

The initial position of the center of the \(k\)-th ball is \((x_k, y_k)\) and its velocity is \((v_k, w_k)\). The position of the center of each ball varies with time, at time \(t\) it is \((x_k+v_kt, y_k+w_kt)\).

A ball collides with one side of the table when the distance between its center and the side equals the ball radius. A ball moves toward the left or right sides with its horizontal speed \(v_k\) – if this speed is \(0\) the ball won’t collide, otherwise the collision times are \((x_{min}+r_k-x_k)/v_k\) and \((x_{max}-r_k-x_k)/v_k\), where \(x_{min}\) and \(x_{max}\) are the horizontal coordinate of the left and right sides (and hence the minimum and maximum values for the \(x\) coordinates). Only one of these values will be positive, and that is the result (if the ball moves towards the right \(v_k\) is positive and it will collide with the right side in the future – collision time positive, and had collided with the left side in the past – collision time negative; vice-versa for a ball moving to the left).

The collisions time with the top and bottom sides are computed in the same way – replacing \(x_k\) with \(y_k\), \(v_k\) with \(w_k\), \(x_{min}\) with \(y_{min}\) and \(x_{max}\) with \(y_{max}\). 

The complete code for collisions between a ball and the table sides is:

  /**
   * Returns the time of the first future collision with a side of the table. 
   * Returns null if there is no collision.
   * @param x ball horizontal or vertical position
   * @param v ball horizontal or vertical speed
   * @param min minumum horizontal or vertical position (i.e. co-ordinate of one side of the table)
   * @param max maximum horizontal or vertical position (i.e. co-ordinate of the other side of the table)
   */
  private sideCollisionTime(x: number, v: number, min: number, max: number) {
    if (v === 0) {
      // Not moving towards the sides: no collision
      return null;
    }
    var result;
    if (v < 0) {
      // Moving up/left - check agains the minumum 
      result = (min - x + this.radius) / v;
    } else {
      // Moving down/right - check agains the maximum
      result = (max - x - this.radius) / v;
    }
    if (result >= 0) {
      return result;
    }
    return null;
  } // sideCollisionTime

  /**
   * Returns the time of the first future collision with the left or right sides of the table. 
   * Returns null if there is no collision.
   * @param min minumum horizontal position (i.e. x co-ordinate of the left side of the table)
   * @param max maximum horizontal position (i.e. x co-ordinate of the right side of the table)
   */
  sideXCollisionTime(min: number, max: number) {
    return this.sideCollisionTime(this.x, this.v, min, max);
  } // sideXCollisionTime

  /**
   * Returns the time of the first future collision with the top or bottom sides of the table. 
   * Returns null if there is no collision.
   * @param min minumum vertical position (i.e. y co-ordinate of the top side of the table)
   * @param max maximum vertical position (i.e. x co-ordinate of the bottom side of the table)
   */
  sideYCollisionTime(min: number, max: number) {
    return this.sideCollisionTime(this.y, this.w, min, max);
  } // sideYCollisionTime

What about collisions between balls? This is a bit more complex – two balls collide when their distance is equal to the sum of their radiuses:

balls1

The square of the distance between balls \(k\) and \(l\) at time \(t\) is:

$$s^2(t)=(x_k + v_kt - x_l - v_lt)^2 + (y_k + w_kt - y_l - w_lt)^2 = (\Delta x + \Delta vt)^2 + (\Delta y + \Delta wt)^2$$

where \(\Delta v = v_k – v_l\), \(\Delta w = w_k – w_l\), \(\Delta x = x_k – x_l\) and \(\Delta y = y_k – y_l\). Equating this to the squared sum of their radiuses produces:

$$(r_k + r_l)^2 = (\Delta x + \Delta vt)^2 + (\Delta y + \Delta wt)^2$$

that is a quadratic equation in \(t\). Solving it gives the collision time:

$$t_{kl} = \frac{-p \pm \sqrt{q}}{\Delta v^2 + \Delta w^2}$$

where \(p=\Delta v\Delta x + \Delta w\Delta y\) and  \(q = (\Delta v^2+\Delta w^2)(r_k+r_l)^2-(\Delta v\Delta y - \Delta w\Delta x)^2\).

If \(q\) is negative the equation has no (real) solutions, that means that the balls do not collide. If \(q\) is zero the balls have only one collision: they ‘glance’ each other. If \(q\) is greater than zero there are two ‘collisions’: the balls touch, then go through each other and touch again on the other side. In the complete simulation after the first collision the balls change course, so we are interested only in the first – i.e. minimum – value. Finally, one or both solutions can be negative – corresponding to collisions that happened in the past; we want only the collisions in the future, so the result is the minimum non-negative solution.

With this the algorithm is complete, but there is still a problem: it all works fine if the balls never overlap, but if they do we will detect spurious collisions.

If the balls do not overlap to begin with, and the simulation detect the collisions and make the balls bounce away when they touch, how is it possible to even have overlaps? The answer is floating-point arithmetic: the actual code uses floating-point values, that introduces rounding errors in the computation.

What can happen (and actually DO happen) is:

  1. two balls move toward each other,
  2. they reach the collision point,
  3. the simulation updates their velocity so that they ‘bounce’,
  4. due to rounding errors there is a slight overlap in their position,
  5. this cause a new immediate (spurious) collision to be detected, with a new update in the balls velocities

…and so on. The final effect is that sometimes balls touch and then stick together, or start to bounce inside each other – sort of fun, but definitely not billiard.

The solution for this is to check the value of \(p\): only if it is negative the balls are moving toward each other, otherwise are moving apart (or parallel); so when \(p\) is not negative we always return ‘no collision’, this excludes the spurious collisions at step (5) above and fixes the simulation.

The complete code for collisions between two balls is:

  /** 
   * Returns the time of the first future collision between this ball and another ball. 
  *  Returns null if the balls do not collide
   * @param other the other ball
  */
  collisionTime(other: Ball) {
    var dv = this.v - other.v;
    var dw = this.w - other.w;
    var dx = this.x - other.x;
    var dy = this.y - other.y;
    var p = (dv * dx + dw * dy);
    if (p >= 0) {
      // The balls are moving apart or parallel
      return null;
    }
    var dv2 = dv * dv + dw * dw;
    var r = this.radius + other.radius;
    var q = dv2 * r * r - Math.pow(dv * dy - dw * dx, 2);
    if (q < 0) {
      // No real solution: the balls do not collide
      return null;
    }
    q = Math.sqrt(q);
    if (p <= q) {
      return (-p - q) / dv2;
    }
    return (-p + q) / dv2;
  } // collisionTime

How comes that the sign of \(p\) indicates if the balls are moving apart or not? The time derivative of the distance between the balls is

$$\frac{ds}{dt}\bigg|_{t=0} = \frac{\Delta x\Delta v + \Delta y\Delta w}{s} = \frac{p}{s}$$

\(s\) is positive, so if \(p\) is negative the derivative is negative and the distance is decreasing – i.e. the balls are moving towards each other. 

Another way to prove it is noticing that \(s\) is the scalar product of the relative position and speed of the balls, hence the sign of \(p\) is the sign of the cosine of the angle \(\varphi\) between those two vectors. If \(p\) is negative the angle is greater than \(90^\circ\), that means that the direction of the relative velocity is opposite of the direction of the relative position – i.e. the balls are moving towards each other.

balls2  

[Calculus agrees with geometry – that is good]

Posted in: Programming

Tags: , , ,

Billiard simulation - part 1: model and animation

April 28, 2013 at 6:25 PMMichele Mottini

The simulation model is pretty straightforward: the table is just a rectangle, represented by the coordinates of its top left corner and its width and height; the balls are spheres, represented by the position of their center \(\vec p_k=(x_k, y_k)\), their velocity \(\vec v_k=(v_k, w_k)\) and their radius \(r_k\) – where \(k\) is the index identifying the ball.

Billiard table with balls

I kept the radius as a property of each ball instead than a global parameter, to be able to model balls of different size.

This is just the geometrical part of the model; I’ll introduce additional parameters for the physics part (mass, friction, restitution) as I develop the physics model.

The animation logic is simple as well: the screen needs to be updated with a certain frequency – let’s say 30 times a second to provide a smooth display. To do this a timer calls an update function every \(\Delta t = 1/30\) seconds, and this function computes the new positions of all the balls and then re-draws everything.

The update function has to compute the change of the balls positions in the \(\Delta t\) seconds elapsed since the last update. For a ball moving freely this change is simply its velocity times \(\Delta t\). The balls do not move freely though: they can hit other balls or the sides of the table, and every time there is a collision the velocity of the colliding balls(s) changes. The complete update algorithm then is:

  1. Compute the time \(t_{min}\) of the first collision(s)
  2. If \(t_{min}\)  is equal or greater than \(\Delta t\) then move all the balls freely for \(\Delta t\) seconds and we are done (no collisions to consider)
  3. Otherwise: move all the balls freely for \(t_{min}\) seconds
  4. Compute the new velocities of all the balls that collide
  5. Repeat from (1), reducing \(\Delta t \) to  \(\Delta t – t_{min}\)

Next time: detecting collisions.

Posted in: Programming

Tags: , ,

Phrase of the week

April 28, 2013 at 5:15 PMMichele Mottini

economists can . . . link almost any unexpected effect with any favorite cause. That is one reason they are held in lower esteem than engineers.

The Economist in ‘Climbing, stretching and stumbling’ – China section of the April 20th 2013 issue.

Posted in: Opinion

Tags: , ,

Billiard simulation – introduction

April 23, 2013 at 6:57 PMMichele Mottini

I failed with the Udacity course (see previous episode), but I still want to improve my JavaScript / HTML5 / canvas skills. 

I am a software developer by trade, but a physicist by training: physics was my passion before computers sort-of-displaced it. I always had an itch to get back into it.

Hence the idea of writing physics simulation code running in a browser, and billiard seems a reasonably simple but interesting case.

The plan is to write a series of posts here describing the development of the simulation, writing about both the physics and the software parts. It will be a work-in-progress kind of thing: I don’t have a finished program that can be described from A to Z; I am going to describe the various pieces as I implement (and possibly ditch) them.

The ambition is to start with classical mechanics and then ‘graduate’ to relativity and/or quantum mechanics. It would be interesting to have a relativistic simulation and be able to play with \(c\) and see how the classical behavior changes into the relativistic one.

The simulation will run entirely in the browser, without a server part. The code will be in TypeScript, compiled into JavaScript for deployment.

Why TypeScript instead than plain JavaScript? I always used strongly typed languages (C#, C++, Pascal, C), and JavaScript seems a bit too loose to me, especially for bigger projects. TypeScript seems a very good solution: offers strong typing, classes and modules, but it is very similar to JavaScript and can use native JavaScript libraries.

The snippets of code I am going to place here will most likely run unchanged – or with very minor changes - as pure JavaScript, so whoever is interested in the simulation and physics part won’t have to learn TypeScript just to follow the implementation.

The simulation I developed so far can be seen here, the source code is on GitHub here. Everything is still very very rough – hopefully it will improve.

Posted in: Programming | Physics

Tags: ,

Udacity HTML5 game development course

April 18, 2013 at 6:13 PMMichele Mottini

…I dropped it after completing five of the eight units.

I kept reading about these new free on-line courses. I want to improve my JavaScript / HTML5 / canvas skills. I saw that Udacity was offering a new  HTML5 Game Development course. It seemed perfect – and is free! – so I  gave it a try.

The course is organized as a walk-through of the development of the GRITS video game – a technology demonstration by Google. Good idea: better to work on something specific instead than explaining things in general.

The course is split in eight units, each on a specific subject: use of the canvas, atlases, handling input and so on. Good as well.

Each unit is composed of short videos – and when I say short I mean it: never longer than 3 minutes, and often under a minute. Here is the first problem: it is difficult (impossible?) to explain anything of real substance in such a short time, so what you get are small snippet of information without much real meat.

The second problem is that there are not that many videos – the total time of all the videos for an entire unit is in the order of 10-15 minutes. This means that in the entire course you are getting something like a total of a couple hours (at most) of lessons.

Then there are the quizzes! After almost every video you have to complete a quiz. Most of the quiz involve writing some JavaScript code, that is then automatically tested. You write the code directly in the browser.

Writing code in the browser as part of a fairly large project is not that easy, so they ‘dumbed down’ the tests a lot: often you have to write no more that 10 lines of code following comments placed in the code itself (‘Write a loop that does such and such. Insert your code here’). On top of this the automatic tests use fairly simplistic test cases. The result is that the quizzes are an exercise of writing syntactically correct small JavaScript snippets; they do not test if you really understand (or not) what you are supposed to be learning. Finally, often the quiz code does not match the instructions – or even the comments inside the code itself – so you have to guess what is being asked.

A couple of other things (and then I stop, promise):

There is no explanation of the overall structure of the program, you look at the various pieces in isolation. Makes everything more difficult to follow – and it would have been an interesting subject in its own right.

The code itself look a bit weird, for example there are methods of a class that has a global instance that access directly the global instance instead than the current one:

var TILEDMapClass = Class.extend({
    currMapData: null,

    parseMapJSON: function (mapJSON) {
        gMap.currMapData = JSON.parse(mapJSON)
    },

});

var gMap = new TILEDMapClass();

No explanation given – but surely looks wrong to me.

As I wrote at the beginning: I stuck with it for some weeks, but in the end I dropped out.

Posted in: Opinion | Programming

Tags: , ,

Free as in speech

April 13, 2013 at 12:32 PMMichele Mottini

I don’t completely get the enthusiasm for open source software, to try to understand it better I had a look at the Web site of the Free Software Foundation. I found it…puzzling? objectionable? …crazy? Not sure what’s the right word.

Start with this:

The corporations behind proprietary software will often spy on your activities and restrict you from sharing with others.

The assumption seems to be that proprietary software is developed by (evil) Megacorp Inc and used by Jane Consumer or Joe Small Business. This is ridiculous: most software is developed by small companies and used by other companies – including large ones. Amongst the first 100 US corporation by revenue only two are software developers – Microsoft (37) and Oracle (82). I’d bet that for most line of business application the norm would be small(ish) software companies selling to much larger customers (it has always been the case with my own software business).

Then there is this:

The freedom to study how the program works, and change it so it does your computing as you wish (freedom 1). Access to the source code is a precondition for this.

Nice. Let’s go ahead and use this freedom – here is the list of the 100+ top-level directories containing the OpenOffice source code and here you are warned:

Let's be honest. The size, age and complexity of OpenOffice's C++ codebase makes coding a challenge. This is not a trivial codebase to learn.

Who can honestly say that access to these sources will allow Jane Consumer – or even Bob C++ Programmer – to ‘change it so it does …as you whish’?

Of course it is a different matter if the USER of the software is Megacorp Inc – that has the resources to actually do something with the sources: fix bugs, make improvements, adapt it. Think of Google or Facebook - big businesses that use a lot of software and sell advertisement: they surely benefitted from the availability of Linux, PHP, Python and so forth.

Aside: the free software definition apparently applies to all possible software, but – just as an example - would it really be a good thing if anyone was able to tinker with the software embedded in their cars? No mention of this nuances though.

Finally, there is this:

“Free software” does not mean “noncommercial”. A free program must be available for commercial use, commercial development, and commercial distribution. Commercial development of free software is no longer unusual; such free commercial software is very important.

That is very true – there are a number of businesses based on distributing and supporting free software. But if the software itself is freely distributed these businesses would never be able to charge much – the marginal price will be the cost of distribution and support, disregarding development – and this will hurt software development companies (that – see above - are mostly small and mid-sized, not Megacorp Inc.). The free availability of Git allows GitHub to exists – but hurts Perforce and SourceGear.

Summary: free software – benefits the big at the expense of the small. And Jane Consumer, in the meantime, switched to an iPad.

Posted in: Opinion

Tags: ,

Windows Live Writer crashing

April 13, 2013 at 11:23 AMMichele Mottini

I installed Windows Live Writer to have something better to write blog posts, but it was systematically crashing on startup.

The crash was an ‘APP CRASH’ in nvdxgiwrap.dll called by wlstartup.exe.

After some failed attempt I managed to solve the problem disabling the NVIDIA display card (start Device Manager, right-click on NVIDIA under ‘Display adapters’ and select ‘Disable’).

Once I did this Live Writer started up fine, completing the installation process. Afterwards I was able to re-enable the NVIDIA card and Live Writer kept working. Apparently the problem was just in the startup that runs when Live Writer is started the first time.

My setup is a Dell Latitude E6420 laptop running Windows 7 Professional 64 bits with Service Pack 1 and an NVIDIA NVS 4200M video card with the latest drivers – version 8.17.12.6696.

Posted in: Blogging

Tags: , ,

Overloading in TypeScript - part 2

April 12, 2013 at 3:44 PMMichele Mottini

In the previous post I dealt with overloading constructors. The exact same system can be used to overload class methods - this code:

class DateHour {

  private date: Date;
  private relativeHour: number;

  . . .

  init(year: number, month: number, day: number, relativeHour: number);
  init(date: Date, relativeHour: number);
  init(dateOrYear: any, monthOrRelativeHour: number, day?: number, relativeHour?: number) {
    if (typeof dateOrYear === "number" && monthOrRelativeHour && day) {
      this.date = new Date(dateOrYear, monthOrRelativeHour, day);
      this.relativeHour = relativeHour;
    } else {
      var date = <Date> dateOrYear;
      this.date = new Date(date.getFullYear(), date.getMonth(), date.getDate());
      this.relativeHour = monthOrRelativeHour;
    }
  }
}

defines an 'init' method with two overloads, one taking a year/moth/day triplet and the other a date object. The one and only implementation is hidden by the overloads, and checks the type of the parameters to determine which of the two overloads to implement.

Finally, the same system can be used to overload stand-alone functions:

function initDateHour(year: number, month: number, day: number, relativeHour: number);
function initDateHour(date: Date, relativeHour: number);
function initDateHour(dateOrYear: any, monthOrRelativeHour: number, day ? : number, relativeHour?: number) {
  if (typeof dateOrYear === "number" && monthOrRelativeHour && day) {
    // Handle the year/moth/day case    
  } else {
    // Handle the date object case
  }
}

Part 1

Posted in: Programming

Tags: ,

Highlighting TypeScript code

April 10, 2013 at 6:05 PMMichele Mottini

The previous post was about TypeScript, and I am probably going to write more about it.

The default code highlighter that comes with BlogEngine.Net - based on Alex Gorbatchev's Syntax Highlighter - does not support TypeScript, so I had a go at adding it.

It turns out to be very easy: you need to add a 'brush' JavaScript code file defining the highlighting rules for the language. Given that TypeScript is very similar to JavaScript I just took the JavaScript one and adapted it.

To make BlogEngine.Net pages recognize the new language I added the reference to the new brush in scripts\syntaxhighlighter\shInit.js. Finally I added the new language name in the 'Insert code' form of the HTML editor. That's it.

If anyone is interested here are the files: 

TypeScriptHighlighter.zip (3.19 kb)

Simply un-zip in the BlogEngine.Net root directory preserving the paths - the files will go to the right place.

I issued a pull request in Syntax Highlighter GitHub repository - but there are quite a number piled up, so I don't know if it is going to be integrated.

 

Posted in: Blogging | Programming

Tags: ,