Compass Belt

Over the last week I have been assembling a compass belt. It is a belt lined with ten motors controlled by an arduino. The motor closest to north vibrates so that the person wearing the belt always knows which direction is north. I am not the first person to build a compass belt:

• Wired magazine article
• North Paw directional anklet kit
• Haptic compass

Here is a list of all the parts I used:

• 10 motors $49.50
• Compass $34.95
• Arduino Uno $29.95
• Soldering iron $9.95
• Belt $8.99
• Soldering iron stand $5.95
• Wire $5
• Multiplexer $4.95
• Wire strippers $4.95
• USB cable $3.95
• Breadboard $3.95
• Battery holder $2.95
• Flush cutter $2.95
• Proto boards $2.50
• Solder wick $2.49
• Solder $1.95
• Headers $1.50
• transistor $0.75
• capacitor $0.25
• 1k resistor $0.25
• 33 ohm resistor $0.25
• diode $0.15

Total cost: $174.13 (although a subset of this cost is for tools - just the belt components would be $143.89). Thanks to dllu for helping me design the circuit. It turned out to be a lot more time consuming to build than I was anticipating. I blame it mostly on the terrible soldering iron (which doesn't get hot enough). Here I am wearing the belt:

Here is a picture of the inside:

The belt seems to work well - it is quiet, accurate, and updates instantly when I turn around. I haven't actually found it useful yet - it seems pointless to wear it in places that I am already familiar with (and it looks silly). Even if I don't end up using it, it was fun to build and I learned a lot about electronics.

Belousov-Zhabotinsky Reaction

http://www.byronknoll.com/reaction.html

Time Series Forecasting

Today I released an open source project for time series prediction/forecasting: https://code.google.com/p/predcast/

Unlabeled Object Recognition in Google+

Google+ released an amazing feature that uses object recognition to tag photos. Here is a Reddit thread discussing it. Generalized object recognition is an incredibly difficult problem - this is the first product that I have seen which supports it. This isn't a gimmick - it can recognize objects in pictures without *any* corresponding text information (such as in the filename, title, comments, etc). Here are some examples on my photos (none of these photos contain any corresponding text data to help):


At first I thought this last one was a misclassification, until I zoomed in further and saw a tiny plane:


Of course, there are also many misclassifications since this is such a hard problem:

This squirrel came up for [cat]:

This train came up for [car]:

This goat came up for [dog]:

These fireworks came up for [flower]:

This millipede came up for [snake]:

PAQclass

I have released an open source classification algorithm called PAQclass: https://code.google.com/p/paqclass/. I originally created PAQclass when I was working on my master's thesis but I never got around to releasing it until now. PAQclass does classification via data compression. It uses one of the best compression programs available: PAQ8. Although it is very slow, I think PAQclass is probably close to state of the art for text categorization tasks.

Fathauer Fractal Tessellation

I have implemented a fractal in HTML5 canvas: http://www.byronknoll.com/kites.html. It is based on a fractal discovered by Robert Fathauer. Here is a zoomed-in view of the top of my fractal:



The fractal seems to have some interesting properties. Near the center of the zoomed-in image above you can see a "tunnel" of consecutively smaller triangles. There are an infinite number of these tunnels (and I think they exist in every direction). Along the vertical you can see there is pattern to the location of the tunnels. The distance between the tunnels is a geometric sequence with a common ratio of 1/3. As you travel into a tunnel, the hypotenuse length of consecutive triangles is also a geometric sequence with the same common ratio of 1/3.

O(n log n)

I have released a new version of my visibility polygon library. I improved the time complexity from O(n^2) to O(n log n) (where n is the number of vertices). O(n log n) is actually the *optimal* time complexity for this problem (since this problem can be reduced to sorting, and we know sorting is O(n log n)).

A high level description of the algorithm: First, sort all vertices according to their angle to the observer. Now iterate (angle sweep) through the sorted vertices. For each vertex imagine a ray projecting outwards from the observer towards that vertex - all we need to compute is the closest "active" line segment in order to construct the visibility polygon. The closest active line segment must be computed in O(log n) time (for each vertex). I used a special type of heap to accomplish this. The heap keeps track of all active line segments (arranged by distance to the observer). The closest line segment is at the root of the heap. Since line segments don't intersect (a constraint in the problem definition), the heap remains consistent. This property is essential - if the distance ordering between two line segments could change depending on the angle, then a heap would no longer work. So, we can find the closest segment in O(1) time and insert new segments in O(log n) time. The reason the heap I used is "special" is because it also allows removing line segments (when they are no longer active) in O(log n) time. Inactive line segments can't just be ignored and left in the heap - they need to be removed to maintain a consistent distance ordering. In a standard heap, removing an arbitrary element takes O(n) time (since it takes linear time just to find the element). My heap contains an additional map structure from element value to heap index, so elements can be found in O(1) time. Once an element is found, we swap in the last element in the tree and propagate it either up or down (which takes O(log n) time) to maintain heap correctness. Hooray!

Visibility Polygons

I have released an open source JavaScript library for computing visibility polygons: https://code.google.com/p/visibility-polygon-js/

Demo: http://www.byronknoll.com/visibility.html

I don't think there are any other JavaScript libraries which compute visibility polygons. A few years ago I released a Java game that used visibility polygons.

Google Bikes

An article about Google Bikes is currently on the homepage of wired.com. If you watch the video about conference bikes, I am one of the riders (facing backwards).

Canvas Demo

http://www.byronknoll.com/geb.html

I didn't use webgl for this demo - just canvas polygons. This is actually the first time I have made a 3D rendering engine. For the simple model in this demo the framerate appears to be high (even on my phone).

3D Prints

Here are some more 3D prints I ordered from Shapeways:







So, the second version of my monostatic body actually works! You can order the design from Shapeways.

Monostatic Body

I received the 3D print of the one-sided die that I designed. Unfortunately it sometimes gets stuck upside-down on the unstable equilibrium. I have designed a new version which I think should fix the problem: http://www.shapeways.com/model/979729/monostatic-body.html. This version has a ridge on top which should make the unstable equilibrium... less stable:


The ridge causes the center of mass to raise a bit (to 0.9mm below the cylinder's center). I feel confident that this version of the shape should work - it will take about two weeks until I get the printed copy from Shapeways.

One-sided die

Today I designed a one-sided die: http://www.shapeways.com/model/979729/one-sided-die.html

I have ordered a 3D print of the model.

A sphere does not make a very good one-sided die because it takes a long time to stabilize after rolling. The shape I designed has some interesting properties. It has only one stable equilibrium, so it will always rest in the same position on a flat surface. It is also homogeneous and convex. A gömböc is another shape with these properties. Unlike a gömböc, my shape has multiple unstable equilibrium points.

My shape is similar to a monostatic polytope described in 1969 by J.H. Conway, M. Goldberg and R.K. Guy. Here is a video demonstrating their shape:



Unlike Conway's shape, my design is smooth everywhere except a flat surface on the bottom. I added the flat surface to help it stabilize faster. It is actually very easy to construct my shape - it is the intersection of a sphere with a cylinder (ignoring the flat bottom). For the design I uploaded to Shapeways, the cylinder has a radius of 10mm and the sphere has a radius of 30mm. It was modeled using Rhino:


The highlighted point in the screenshot is the center of mass - it is 1.059mm below the cylinder's center. I am hoping that the center of mass is low enough so that the actual physical object always reaches the same resting point. Theoretically any center of mass below the cyclinder's center would work, but in practice inaccuracies in the 3D printing process could cause problems.

Gyroid

I ordered a 3D print of a gyroid from Shapeways. The material is alumide. I am very impressed with the quality of the print - I plan to create some of my own models soon.

RIP Google Reader

Google has announced that they are shutting down Google Reader. This is a sad day.

HTML5 Goomba

[link]

HTML5 Foosball

[link]

Rocket Launch

This weekend I launched a low-powered rocket at NASA Ames. The event was organized by the local rocketry club. My rocket was designed by my older brother. Here are some pictures:



NASA is definitely the coolest venue imaginable for launching rockets :). I am guessing there were 50-100 people at the event, with about one rocket launching every minute. One rocket actually fell on me while I was setting up my rocket. Its parachute didn't deploy due to a malfunction. Luckily its terminal velocity was not very fast, so it didn't hurt me. Here is a video of my first launch:

We determined that fire/ember from the engine traveled up the body of the rocket, burning the parachute and snapping the rubber cable which connects the two rocket segments. So the bottom rocket segment crashed without any parachute, causing the four fins to break off. After repairing the rocket with super glue we made a second launch attempt. The second launch was slightly better, but the parachute got tangled and did not fully deploy.

Blob Balance

I have created a simple game based on the blob demo I made yesterday: http://www.byronknoll.com/balance.html

The blob will become harder to control as your score increases (caused by changes to a "fluidity" parameter).

HTML5 Blob

Today I made a blob in HTML5 canvas: http://www.byronknoll.com/blob.html

You can interact with the demo by moving your cursor. This is the second time I have made a blob. My first blob was for a game I made called Time Stop. Since Box2D has a JavaScript port, I was planning to use Box2D for this project (here is a Box2D demo in HTML5 canvas).

However, I decided not to use Box2D when I stumbled across this amazing demo: http://www.ewjordan.com/processing/VolumeBlob/. ewjordan discovered a technique for simulating blob physics that is computationally efficient (much faster than Box2D), realistic, and extremely simple to implement. My demo is basically just a port of ewjordan's Processing code to JavaScript.