The modern interest in computer vision as a consumer input for computer games has led to the development of several SDKs for performing computer-vision pattern recognition. One such system is Kinect for Windows. Although Microsoft provides a very high-level API with the Kinect, the downside is that you are locked into its hardware. The popular open source alternative is OpenCV, a library of computer-vision algorithms. Its advantage is that it can use a wide variety of camera hardware and not just the Kinect sensor.

As previously noted, there are many ways to collect optical tracking data, but since we are focusing on the physics aspects, we’ll now talk about how to process the data to get meaningfully physical simulation. By combining object detection with depth sensing, we can detect and then track an object as it moves in the camera’s field of vision. Let’s assume that you have used the frame rate or internal clock to generate data of the following format:

{(x[i],y[i],z[i],t[i]),(x[i+1],y[i+1],z[i+1],t[i+1]) ,
(x[i+2],y[i+2],z[i+2],t[i+2]), ...}

Now, a single data point consisting of three coordinates and a timestamp doesn’t allow us to determine what is going on with an object’s velocity or acceleration. However, as the camera is supplying new position data at around 20–30 Hz, we will generate a time history of position or displacement. Using techniques similar to the numerical integration we used to take acceleration and turn it into velocities and then turn those velocities into position in earlier chapters, we can apply numerical differentiation to accomplish the reverse. Specifically, we can use the finite difference method.

For velocity, we need a first-order finite difference numerical differentiation scheme. Because we know the current data point and the previous data point, we are looking backward in time to get the current position. This is known as the backward difference scheme. In general, the backward difference is given by:

We must use the backward difference for the first-order differentiation, as we know only the present position and past positions. In our case, h is the difference in time between two data points and has a nonzero, fixed value. Therefore, the equation can be rewritten as:

where ∆f(x) is the position at the second timestamp minus the position at the first timestamp, and h is the difference in time. This is relatively straightforward, as we are just calculating the distance traveled divided by the time it took to travel that distance. This is the definition of average velocity.

Note that because we are finding the average velocity between the two data points, if the time delta, h, is too large, this will not accurately approximate the instantaneous velocity of the object. You may be tempted to push whatever hardware you have to its limit and get the highest possible sampling rate; however, if the time step is too small, the subtraction of one displacement from another will result in significant round-off error using floating-point arithmetic. You must take care to ensure that when you’re selecting a timestamp, (t[i] + h) – t[i] is exactly h. For more information on tuning these parameters, refer to the classic Numerical Recipes in C. The function to find velocity from our data structure would be as follows. Note that in our notation, t[i−1] is behind in time compared to t[i], so we are using the backward form. Your program needs to ensure that t[i−1] exists before executing this function:

Vector findVelocity (x[i-1], y[i-1], z[i-1], t[i-1], x[i], y[i], z[i], t[i]){

    float vx, vy, vz;

    vx = (x[i] − x[i-1])/(t[i]-t[i-1]);
    vy = (y[i] − y[i-1])/(t[i]-t[i-1]);
    vz = (z[i] − z[i-1])/(t[i]-t[i-1]);

    vector velocity = {vx, vy, vz};

    return velocity;

}

To compute the acceleration vector, we need to compare two velocities. However, we note that to get a velocity, we need two data points. Therefore, a total of three data points is required. The acceleration we solve for will actually be the acceleration for the middle data point as we compare the backward and forward difference. This technique is named the second-order central difference. In general, that form is as follows:

This allows you to compute the acceleration directly without first finding the velocities. Here again, f(x) is the position reported by the sensor and h is the time step between data points. The same discussion of h applies here as well. Some tuning of the time step might be required to provide a stable differential. Of particular note with central difference forms is that periodic functions that are in sync with your time step may result in zero slope. If the motion you are tracking is periodic, you should take care to avoid a time step near the period of oscillation. This is called aliasing and is a problem with all signal analysis, including computer graphics displays. Also, note that this cannot be computed until at least three time steps have been stored. In our notation, t[i−1] is the center data point, t[i−2] the backward value, and t[i] the forward value. The acceleration function would therefore be as follows:

Vector findAcceleration (x[i-2], y[i-2], z[i-2], t[i-2], x[i-1], y[i-1], z[i-1], 
                         t[i-1], x[i], y[i], z[i], t[i] ){

    float ax, ay, az, h;
    vector acceleration;

    h = t[i]-t[i-1];

    ax = (x[i] − 2*x[i-1] + x[i-2]) / h;
    ay = (y[i] − 2*y[i-1] + y[i-2]) / h;
    az = (z[i] − 2*z[i-1] + z[i-2]) / h;

    return acceleration = {ax, ay, az};
}

Now, let’s say that you are tracking a ball in someone’s hand. Until he lets it go, the velocity and acceleration we are calculating could change at any moment in any number of ways. It is not until the user lets go of the ball that the physics we have discussed takes over. Hence, you have to optically track it until he completes the throw. Once the ball is released, the physics from the rest of this book applies! You can then use the position at time of release, the velocity vector, and the acceleration vector to plot its trajectory in the game.