# Box2D Blob Skeleton

This week in nature of code, we talked about using a physics engine to build a skeleton for an onscreen character. Two projects we referenced are:

Karsten Schmidt’s Nokia Friends and Elie Zananiri’s Big Screams.

Both of these projects involve an underlying skeleton (Nokia Friends uses toxiclibs verlet physics and Big Screams uses Box2D) that serves as the structure for a cute, cuddly, jiggly creature drawn on top. In my efforts to expand the nature of code materials this semester, I’ve released a new example that demonstrates this technique. It constructs a skeleton of out Box2D bodies and distance joints and draws a curvy polygon with eyes and mouth on top.

Source: BlobSkeleton.zip
(Requires pbox2d: https://github.com/shiffman/PBox2D

# Night #7: Nature of Code excerpts

For tonight’s post, I’m going to include three new examples from my upcoming Nature of Code book. I’ll also excerpt some of the text with these examples below.

This first example expands on the existing Recursive Tree example that comes with Processing.

Chapter 8: Recursion and Fractals

The recursive tree fractal is a nice example of a scenario in which adding a little bit of randomness can make the tree look more natural. Take a look outside and you’ll notice that branch lengths and angles vary from branch to branch, not to mention the fact that branches don’t all have exactly the same number of smaller branches. First, let’s see what happens when we simply vary the angle and length. This is a pretty easy one, given that we can just ask Processing for a random number each time we draw the tree.

```void branch(float len) { // Start by picking a random angle for each branch float theta = random(0,PI/3);   line(0, 0, 0, -len); translate(0, -len); len *= 0.66; if (len > 2) { pushMatrix(); rotate(theta); branch(len); popMatrix(); pushMatrix(); rotate(-theta); branch(len); popMatrix(); } }```

In the above function, we always call branch() twice. But why not pick a random number of branches and call branch() that number of times?

```void branch(float len) {   line(0, 0, 0, -len); translate(0, -len);   if (len > 2) {   // Call branch() a random number of times int n = int(random(1,4)); for (int i = 0; i < n; i++) {   // Each branch gets its own random angle float theta = random(-PI/2, PI/2); pushMatrix(); rotate(theta); branch(h); popMatrix(); } } }```

The example below takes the above a few steps further. It uses Perlin noise to generate the angles, as well as animate them. In addition, it draws each branch with a thickness according to its level and sometimes shrinks a branch by a factor of two to vary where the levels begin.

TreeStochasticNoise.zip

Next up an excerpt from the Genetic Algorithm chapter.

Chapter 9: Evolution and Code

In 2009, Jer Thorp released a great genetic algorithms example on his blog entitled “Smart Rockets.” Jer points out that NASA uses evolutionary computing techniques to solve all sorts of problems, from satellite antenna design to rocket firing patterns. This inspired him to create a Flash demonstration of evolving rockets. Here is a description of the scenario:

A population of rockets launches from the bottom of the screen with the goal of hitting a target at the top of the screen (with obstacles blocking a straight line path).

Each rocket is equipped with five thrusters of variable strength and direction. The thrusters don’t fire all at once and continuously; rather, they fire one at a time in a custom sequence. In this example, we’re going to evolve our own simplified Smart Rockets, inspired by Jer Thorp’s. You can leave implementing some of Jer’s additional advanced features as an exercise.

Our rockets will have only one thruster, and this thruster will be able to fire in any direction with any strength in every single frame of animation. This isn’t particularly realistic, but it will make building out the framework a little easier. (We can always make the rocket and its thrusters more advanced and realistic later.)

Source: SmartRockets.zip

And here’s a short excerpt from the beginning of the chapter on neural networks, as well as the example that closes out the chapter demonstrating how to visualize the flow of information through a network.

Chapter 10: The Brain

Computer scientists have long been inspired by the human brain. In 1943, Warren S. McCulloch, a neuroscientist, and Walter Pitts, a logician, developed the first conceptual model of an artificial neural network. In their paper, “A logical calculus of the ideas imminent in nervous activity,” they describe the concept of a neuron, a single cell living in a network of cells that receives inputs, processes those inputs, and generates an output.

Their work, and the work of many scientists and researchers that followed, was not meant to accurately describe how the biological brain works. Rather, an artificial neural network (which we will now simply refer to as a “neural network”) was designed as a computational model based on the brain that can solve certain kinds of problems.

It’s probably pretty obvious to you that there are certain problems that are incredibly simple for a computer to solve, but difficult for you. Take the square root of 964,324, for example. A quick line of code produces the value 982, a number Processing computed in less than a millisecond. There are, on the other hand, problems that are incredibly simple for you or me to solve, but not so easy for a computer. Show any toddler a picture of a kitten or puppy and they’ll be able to tell you very quickly which one is which. Say hello and shake my hand one morning and you should be able to pick me out of a crowd of people the next day. But need a machine to perform one of these tasks? People have already spent careers researching and implementing complex solutions.

The most common application of neural networks in computing today is to perform one of these easy-for-a-human, difficult-for-a-machine” tasks, often referred to as pattern classification. Applications range from optical character recognition (turning printed or handwritten scans into digital text) to facial recognition. We don’t have the time or need to use some of these more elaborate artificial intelligence algorithms here, but if you are interested in researching neural networks, I’d recommend the books Artificial Intelligence: A Modern Approach by Stuart J. Russell and Peter Norvig and AI for Game Developers by David M. Bourg and Glenn Seemann.

In this chapter, we’ll instead begin with a conceptual overview of the properties and features of neural networks and build the simplest example possible of one (a network that consists of a singular neuron). Afterwards, we’ll examine strategies for building a “Brain” object that can be inserted into our Vehicle class and used to determine steering. Finally, we’ll also look at techniques for visualizing and animating a network of neurons.

Source: NetworkAnimation.zip

# Night #6: Image Sequence Object (with variable speed)

I have an example from Learning Processing which demonstrates how to package a “pre-made” animation (i.e. sequence of images) into an object in Processing so that it can be duplicated many times on screen. For tonight’s example, I’m going to make a new version that improves a few key points.

First, in the original example the the image files are loaded in the class itself. This is problematic. Sure, if you make one object then you are loading files from the hard drive once. However, if you make many objects, then you are loading the same images over and over again which is totally unnecessary (and can cause problems like using too much memory, stuttering if objects are made during draw(), taking too long to start up, etc.).

We can fix this by loading an array of images in setup() and passing it to the object.

```Animation a;   void setup() { // Load the image sequence first! PImage[] seq = new PImage[40]; for (int i = 0; i < seq.length; i++) { seq[i] = loadImage("stick/stick"+nf(i+1,2)+".png"); }   // Now when you make the animation object, you pass it the image array! a = new Animation(seq); }```

The class then receives the array in the constructor and passes it to its own array.

```class Animation { // The array of images PImage[] images;   Animation(PImage[] images_) { images = images_; }```

This way (as you'll see in the example) if we make an array of objects, each one uses the same array of images (which we loaded only once). Another feature of this improvement is that the Animation object is more generic, and can be created with any arbitrary array of images.

The original example demonstrated how to have the sequences start at different images so that they didn't all appear to be perfectly in sync. However, the question I usually get is instead: "How can the sequences play back at variable speeds?"

The original example used an integer to keep track of the current "frame" of the animation.

```int index = 0;   void next() { index = (index + 1) % images.length; }```

Here, you see that we move one spot in the array each frame, and the animation is then shown at the frame rate of our sketch. So in theory, you could change the above to "index = index + 2" to, say, double the speed. A more flexible way to vary the rate of the animation, however, is to use a float for the index in the array, i.e.

```float index = 0; float speed = random(1,5);   void next() { // Move the index forward in the animation sequence index += speed; // If we are at the end, go back to the beginning if (index >= images.length) { // We could just say index = 0 // but this is slightly more accurate index -= images.length; } }```

Of course, you can't actually use this float when you go to look up an image in the array -- indices must be integers! So we simply convert it to an int when the time comes to draw the image.

```void display() { int imageIndex = int(index); image(images[imageIndex], x, y); }```

Here is the example.

# Night #5: thread() in Processing

I just updated the Thread tutorial on the Processing wiki to include a little known function in Processing called thread(). It’s undocumented as of now, but will be a part of the 2.0 documentation. Here’s how it works.

(This following is excerpted from the tutorial).

You are likely familiar with the idea of writing a program that follows a specific sequence of steps — setup() first then draw() over and over and over again! A Thread is also a series of steps with a beginning, a middle, and an end. A Processing sketch is a single thread, often referred to as the “Animation” thread. Other threads sequences, however, can run independently of the main “Processing” sketch. In fact, you can launch any number of threads at one time and they will all run concurrently.

Processing does this all the time, whenever you write an event callback, such as serialEvent(), or captureEvent(), etc. these functions are triggered by a different thread running behind the scenes, and they alert Processing whenever they have something to report. This is useful whenever you need to perform a task that takes too long and would slow down the main animation’s frame rate, such as grabbing data from the network (XML, database, etc.) If a separate thread gets stuck or has an error, the entire program won’t grind to a halt, since the error only stops that individual thread. To create independent, asynchronous threads, you can use the thread() function built into Processing.

```void setup() { size(200,200); // This will tell someFunction() to execute now as a separate thread thread("someFunction"); }   void draw() {   }   void someFunction() { // This function will run as a thread when called via // thread("someFunction") as it was in setup! }```

The thread() function receives a String as an argument. The String should match the name of the function you want to run as a thread. While using the thread() function is a very simple way of getting an independent thread, it is somewhat limited. Being able to make a thread object is a great deal more powerful, and this can be done by extending java’s Thread class.

For more about how to do that, take a look at the full tutorial.

Following is an example draws a loading bar in the “animation” thread that reports progress on another thread(). This is a nice demonstration, however, it would not be necessary in a sketch where you wanted to load data in the background and hide this from the user, allowing the draw() loop to simply continue.

# Night #4: Sorting the Vertices of a Polygon

The following problem came up in my ICM course this year. A student was working on a sketch that involved tiling polygons arbitrarily drawn by a user. Allowing a user to set the vertices of a polygon should be easy enough, right? But what if the user does not happen to draw them in a nice clock-wise (or counter clock-wise) order?

Imagine for a moment, you have an ArrayList of PVectors called “vertices.” When the user clicks, the mouse you could add that mouse location to that ArrayList.

```void mousePressed() { vertices.add(new PVector(mouseX,mouseY)); }```

You could then draw that list as a polygon using beginShape() and endShape().

```void draw() { beginShape(); for (PVector v : vertices) { vertex(v.x, v.y); } endShape(CLOSE); }```

But depending on how the user set the vertices, you might end up with:

when what you really want is the following:

One solution for solving this problem is to always sort all of the vertices according to their relative angle from the center. Let’s say you calculate the center of the polygon as the average location of all vertices.

``` PVector centroid = new PVector(); for (PVector v : vertices) { centroid.add(v); } centroid.div(vertices.size());```

You can then make a vector that points from the center to each vertex and get its direction (using PVector’s heading2D() method).

``` for (PVector v : vertices) { PVector dir = PVector.sub(v, centroid); float a = dir.heading2D() + PI; }```

Note how we add PI to the angle. The heading2D() function will return an angle between -PI and PI and it’ll be easier to sort if we just have an angle between 0 and TWO_PI. One way to sort an ArrayList is called a Selection Sort. In the example below, you’ll find a variation of the selection sort. The code iterates through the ArrayList, finds the element with the highest angle, removes that element and sticks it at the end of a new ArrayList. It does this again and again until the original ArrayList is empty. The result is a new ArrayList in sorted order.

Following is that example which implements all of the above into a class. If you are looking for an exercise, try allowing the user to move or delete existing vertices. Also, how you would make a system of these polygons so that the user can draw more than one?

Source: PolygonVertexSorting.zip

# Night #3: Regular Expressions in Processing

Several years ago I became somewhat obsessed with regular expressions while reading Jeffrey Friedl’s Mastering Regular Expressions. At the time, I wrote a short tutorial about regular expressions for my course Programming from A to Z. The sad truth is that if you’ve ever done regular expressions in Java, it’s pretty darn awkward compared to, say, python or perl. The good news is there are some nice regex helper functions in Processing that can make it a bit easier. Before we get to that let’s start with the Java API:

• Pattern — a compiled representation of a regular expression.
• Matcher — an engine that performs match operations on a character sequence (or String) by interpreting a Pattern.

An example of Pattern and Matcher in Java (which you can write directly into Processing) looks like the following:

```String inputtext = "This is a test of regular expressions."; // Input text String regex = "test"; // The regular expression to match Pattern p = Pattern.compile(regex); // Making a Pattern object with the regex Matcher m = p.matcher(inputtext); // Matching that regex in the input string if (m.find()) { System.out.println(m.group()); // Here's the match! } else { System.out.println("No match!"); // No match! }```

Of course, in most cases, you want to do something more sophisticated where you iterate over many matches.

```// Regex that matches double words // Ugh, look at all these double back slashes!! String regex = "\\\\b(\\\\w+)\\\\b\\\\W+\\\\1";   Pattern p = Pattern.compile(regex); // Compile Regex Matcher m = p.matcher(content); // Create Matcher while (m.find()) { System.out.println(m.group()); }```

Processing provides some regex helper functions that wrap all of this Java Pattern/Matcher stuff. They are match() and matchAll().

The match() function is used to apply a regular expression to a piece of text, and return matching groups (elements found inside parentheses) as a String array. If there is no match, the function will return null. If no groups are specified in the regular expression, but the sequence matches, an array of length one (with the matched text as the first element of the array) will be returned.

Here’s an example (this is straight from the reference page).

```String s = "Inside a tag, you will find <tag>content</tag>."; String[] m = match(s, "<tag>(.*?)</tag>"); println("Found '" + m[1] + "' inside the tag."); // Prints to the console: // "Found 'content' inside the tag."```

The matchAll() function is at first a bit confusing because it returns a two dimensional array. But if you look right back to how match() works, it’s pretty simple. match() assumes you want just one match, and gives you an array, a list of all the groups for that single match. matchAll() assumes you want all the matches, so it gives you a bunch of those arrays, one for every match. What’s an array of an array? A two dimensional array! The first dimension is the match itself, and the second dimension is the group for that match, i.e.

```String s = "Some tags! <tag>one</tag> <tag>two</tag> <tag>three</tag>.";   // Match this regular expression String[][] m = matchAll(s, "<tag>(.*?)</tag>"); // Loop through all the matches for (int i = 0; i < m.length; i++) { // Print out group 1 for each match println("Found '" + m[i][1] + "' inside a tag."); }```

This new example uses a regex that matches anything inside an HTML href tag and draws it the screen.

# Night #2: Fade Sound In and Out Using Minim

I made this example earlier in the semester after seeing countless projects with the following functionality: turning a sound on when a sensor reading reaches a given level, turning the sound off when a sensor reading falls below a certain level. Most the projects used Minim for sound playback and pause() and play() to start and stop a sound, along with rewind() to send the sound back to the beginning. While this does work, I find a more effective strategy is to fade a sound in and out using shiftGain().

Now this is a fairly simple problem if you can pinpoint the moment a sound should fade in. For example, let’s say you want it to happen when the mouse is clicked.

```void mousePressed() { player.shiftGain(-80, 13, 1000); }```

The above line of code will fade the sound over 1,000 milliseconds (i.e. 1 second) from a decibel level of -80 (inaudible) to 13 (some vaguely loud level.)

If you put this code in draw(), however, you’ve got a problem.

```void draw() { if (sensorVal > threshold) { player.shiftGain(-80, 13, 1000); } }```

You can’t call shiftGain() over and over again! You want this to happen just once, the moment the sensor value reaches that threshold. Introducing a boolean is a quick way to solve this problem. If you set the boolean to true when the sound is fading and only call shiftGain() when the boolean is set to false, you’ve now got only one call to the function.

```boolean fade = false;   void draw() { if (sensorVal > threshold && !fade) { player.shiftGain(-80, 13, 1000); fade = true; } }```

The question remains: when does fade get set back to false? One likely solution is to reset the boolean when the sensor value falls below the threshold, i.e.

``` if (sensorVal > threshold && !fade) { player.shiftGain(-80, 13, 1000); fade = true; } else if (sensorVal < threshold) { fade = false; }```

Following is an example that does this with a double threshold (fading up above a value and fading down below a value). In addition, it offers some other improvements (such as having the sound fade from its current gain level). The mouseX location is the stand-in for a sensor value.

# Night #1: Zoom and Pan in 2D

This came up in my course “Introduction to Computational Media” this year. How does one pan and/or zoom in a 2D Processing world? We could certainly introduce P3D into the mix, but there is a nice, elegant way we can create the effect of panning and zooming and still live in 2D. Here’s how it works.

First, you need to make sure you translate to the center of your window.

` translate(width/2, height/2);`

Then you can use the scale() function to scale the world according to a percentage (i.e. 2.0 is 200%, 0.5 is 50%). We’ll use a variable called zoom.

``` float zoom = 1.5; // 150% scale(zoom);```

Then we can translate additionally to pan according to some offset.

``` float offsetX = 100; // Some arbitrary offset float offsetY = 0; translate(offsetX,offsetY);```

Here is an example (running in processing.js) that allows the user to pan around a design by dragging the mouse, and zoom in and out using key presses.

Source: PanZoom2D.zip

# OpenCV Matching Faces Over Time

One of the most common questions I get regarding blob tracking is “memory.” How do I know which blob is which over time? Computer vision libraries, for the most part, simply pass you a list of blobs (with x, y, width, and height properties) for any given moment in time. But the blobs themselves represent only a snapshot of that particular moment and contain no information related to whether the blobs existed before this very moment. This may seem absurd given that as human beings it’s so easy for us to watch a rectangle moving across a screen and understand conceptually that it is the same rectangle. But without additional information (such as color matching, an AR marker, etc.) there’s no way for an algorithm that analyzes one frame of video to know anything about a previous frame. And so we need to apply the same intuitions our brain uses (it was there a moment ago, it’s probably still there now) to our algorithms.

To illustrate one solution to this problem, I’ve created an example that tags an OpenCV face “rectangle” with an ID number and attempts to track that face over time, matching new faces that OpenCV finds with earlier ones. This example is somewhat of an oversimplification whose purpose is to demonstrate a particular technique — a new face is the same as the previous one that was closest to it. But there are certainly additional and more sophisticated ways that the match could be made. In addition, it’s likely useful to add some interpolation to the face’s movement and size changes so that it appears less jittery.

First, we need to establish our own Face class. OpenCV just gives us a new array of Rectangle objects every frame so we need our own Face object that persists (in an ArrayList).

```class Face {   // A Rectangle Rectangle r;   // Am I available to be matched? boolean available;   // Should I be deleted? boolean delete;   // How long should I live if I have disappeared? int timer = 127;   // Assign a number to each face int id;```

Our main program then needs an ArrayList to keep track of the Face objects that currently exist:

`ArrayList faceList;`

Finally, in draw(), OpenCV gives us an array of Rectangle objects, the faces it currently sees.

` Rectangle[] faces = opencv.detect();`

It’s our job to match these with any Face objects we have in our ArrayList. The way I see it, there are three scenarios.

1) We have nothing in our Face ArrayList. In this case, we add a new Face object for every single Rectangle in the faces array, i.e.

``` if (faceList.isEmpty()) { // Just make a Face object for every face Rectangle for (int i = 0; i < faces.length; i++) { faceList.add(new Face(faces[i].x,faces[i].y,faces[i].width,faces[i].height)); }```

2) OpenCV found more faces than we currently have in our list. In this case, we need to match our current Face objects with an OpenCV Rectangle and then add new Face objects for any remaining Rectangles.

```} else if (faceList.size() < = faces.length) { boolean[] used = new boolean[faces.length]; // Match existing Face objects with a Rectangle for (Face f : faceList) { // Find faces[index] that is closest to face f // set used[index] to true so that it can't be used twice float record = 50000; int index = -1; for (int i = 0; i < faces.length; i++) { float d = dist(faces[i].x,faces[i].y,f.r.x,f.r.y); if (d < record && !used[i]) { record = d; index = i; } } // Update Face object location used[index] = true; f.update(faces[index]); }```

Notice how in the above code boolean variables are used to keep track of which Rectangles have already been matched. We don't want two Face objects to think they are the same face!

3) Finally, the third scenario is that we have more Face objects than OpenCV has found. In this case, we need to match our existing Face objects and then mark any leftover ones for deletion.

``` } else { // All Face objects start out as available for (Face f : faceList) { f.available = true; } // Match Rectangle with a Face object for (int i = 0; i < faces.length; i++) { // Find face object closest to faces[i] Rectangle // set available to false float record = 50000; int index = -1; for (int j = 0; j < faceList.size(); j++) { Face f = faceList.get(j); float d = dist(faces[i].x,faces[i].y,f.r.x,f.r.y); if (d < record && f.available) { record = d; index = j; } } // Update Face object location Face f = faceList.get(index); f.available = false; f.update(faces[i]); }```

Full source is here: whichface.zip

# Nature of Code book: PVector Spring example

I’m working this week on Chapter 3 of my upcoming Nature of Code book. For the most part, if you are looking to connect particles with springs, I recommend the wonderful verlet physics of toxiclibs, and I have some examples for that here. Nevertheless, I am including an elementary implementation of a single “bob” connected to an “anchor” point via a “spring” force. The example implements Hooke’s Law (Spring Force = -k * displacement) with the PVector class, using the Euler integration model of all my other examples. Here it is below.

Source: _03spring.zip