Don Havey

Sunday is looking a little overcast, a little gloomy, and a lot like a good day to tackle a complicated tutorial: Voronoi diagrams.

I’m sure you’ve seen them before. Given a set of points, a Voronoi diagram defines a series of cells surrounding each point. Each cell contains all points that are closer to its defining point than to any other point in the set. Subsequently, the “borders” of the cells are equidistant between the defining points of adjacent cells. I’ll give you a diagram later.

I haven’t used my Voronoi class in an exciting applet yet, but it has plenty of uses… mostly functional, some aesthetic. Golan Levin did a series of portraits using Voronoi diagrams. More commonly, they’re used in mapping applications.

But first, the moment you’ve all been waiting for: The final result

And how we get there: Voronoi classes

More introduction

Say you have a map of your city, and on it you have located a set of points representing every fast food restaurant. Creating a Voronoi diagram from these points would enable you (on your walk through the city) to know which restaurant you’re closest to at any given time. Of course, an application that simple could be solved more efficiently via other methods, but let’s raise the stakes a bit. What if you want to know the percentage of your walk that will be closest to one particular McDonalds. Suddenly, without a Voronoi diagram, this is tricky. With a Voronoi diagram, however, it’s a simple matter of intersecting the line that represents your walk with the cell that surrounds that particular restaurant.

Voronoi diagrams can also be used to make maps, not just analyze them. Say you have a set of points that represent air quality sample locations. To quickly generalize the sample points into a local map… bam! Voronoi diagram!

There are other more abstract information processing uses for the diagrams as well, but I’m not going to get into them here.

A few more notes

• The most efficient way to create a Voronoi diagram is via Fortune’s sweepline method, which reminds me of how police departments use lines of people to do a walking search of an open area. We’re not going to use that method here. The math is less intuitive.
• The dual graph of the Voronoi diagram for a set of points is called a Delaunay triangulation. It’s a pretty great way of generating a mesh from a set of points, because it allows for an efficient non-uniform distribution of detail.
• All Voronoi cells are convex hulls, assuming that the boundary we are working within is a convex hull. This will be important.

Still alive?

Read more…

Here’s another brief tutorial. This one relates to object collisions and velocity transfers. Basically, we’re making simulated billiard balls: objects that bounce off each other and the sides of the applet. Not too much else to introduce, so I’ll just get started…

What it looks like

Here are the files: Collider classes

And here’s the final result: I’m a super collider

Click on the applet to rejuvenate each Collider’s y-velocity and prepare for another round of bouncy goodness. If you find the motion blur distracting, you can always look at this blur-free example.

What you’ll learn

Some of the math you’ll have to decipher yourself, but in general, I’ll touch on each of the following:

• Preventing circular shapes from overlapping.
• Constraining points within an area.
• Transferring velocities upon object collision.
• And I’ll show you how to do that cheesy motion blur trick… if you don’t already know.

Ready?

Read more…

Humans love maps. They love the mapping of any type of information, not strictly geographical. Maps are bursting with information. They transcend the boundaries of language. Maps are good.

I’m going to make a map today. Well, a globe. It’s going to be a very basic extension of our icosahedron-based sphere. We’ll translate a bunch of latitude/longitude pairs into three-dimensional coordinates to visually define the countries, then we’ll add a single marker on the globe that represents the user’s location, based on his or her IP address.

What it looks like

Here’s our completed Earth class: The final result

And here are the classes you’ll need: Earth classes

What you’ll learn

• Translating latitude/longitude pairs to Points
• Mapping an IP address to a physical location via Geobytes and PHP

Sounds like fun, right?

Read more…

A couple of years ago I was walking home from work and thinking about how writing to a blog is often a one-way process. Like talking to a wall. The most important part of the process, for most bloggers, is the creation of an entry: the release of words. The importance of readability decreases quickly after an entry has been written. Frequently it is an introspective process, like writing to a diary or talking to yourself.

I thought, I would like to create objects from blog entries. Objects that would contain the words in the entry and grow as more words are added, but remain illegible, thereby deemphasizing the creation of a document.

To make a long story short: I decided that a tree would be an appropriate object: it grows in a recognizable fashion and can expand nearly indefinitely. The lettertree concept was born.

This tutorial will explain how I approached the lettertree problem. It relies on our existing Tree class. We’ll create paths from the root of the tree to each “bud” and randomly select one of these paths to carry a letter. We’ll also increase the thickness of the tree branches as the thing grows.

Here’s what it looks like: The final result

Here’s what you need: Lettertree classes

Note that like many of the applets I post, I’ve switched the rendering method from OpenGL to P3D for the in-browser sample. The OpenGL results will look way better and (typically) run faster within the Processing environment, but the latest version of the Java plugin is so immensely bloated that P3D seems to render faster in a browser.

Ready to begin?

Read more…

This quick tutorial will show a more reasonable alternative to the electronsphere, which addressed the problem of distributing points evenly on a sphere. We’ll be creating a geodesic sphere (like at the Epcot center) using a subdivided icosahedron. It’s a relatively simple script and inexpensive in terms of CPU usage. Much more efficient than the electronsphere approach, though not quite as interesting.

Here’s where we’re headed: The final result

And here are the classes you’ll need: Icosahedron classes

About the geodesic sphere

The geodesic dome and sphere are often credited to Buckminster Fuller, although it is generally acknowledged that he did not invent the shape or concept, but rather investigated and expanded upon them. Read more in the Wikipedia article on geodesic spheres.

There is no one standard way to create a geodesic, but in general, the process is as follows:

1. Create a Platonic solid. We’ll be using the icosahedron.
2. Subdivide the faces of the Platonic solid to the desired level of resolution.
3. Project the points of each subdivided face to the surface of a sphere.

Additionally, the term buckyball is used to describe the truncated counterpart to the geodesic sphere. Buckyballs are found frequently in molecular science… and also in soccer. We’ll take a look at how to convert one to the other.

Why create a geodesic sphere?

If you need to create a sphere in Processing just for decoration or whatnot, by all means, use the sphere() command. You do not need this level of complexity.

But let’s say that you need a sphere that can transform itself into a different shape, or warp itself according to some input variable, or behave like a blob… then you’ll probably want to use a geodesic. As I mentioned, its one of the most straightforward ways to create an array of points on a sphere.

Of course, you could also use this script in more physical applications: the coordinates it defines could be used to construct a real-life geodesic structure. You’d probably want to drop the points into Rhino and unfold the thing first.

What you’ll learn

I’ll touch upon the following issues in this tutorial:

• Subdividing a face to an arbitrary level of resolution.
• Constraining points to a sphere.
• Finding the centroid of a face.
• And of course, more about geodesics.

Still sound interesting?

Read more…

Today’s tutorial is going to be shorter and sweeter than the last.

The problem we’ll address is how to structure a tree-like object in a way that’s similar to a real-life tree. It must contain a set of user-defined variables that affect the “species” of tree, but still allow some random variation within the tree’s growth.

I created something similar to this a couple years ago, but have reworked it to be simpler and more efficient. We’ll be using this Tree object in the “Lettertree” tutorial to come…

Here’s the finished product: Recursive tree

And here are the classes: Recursive tree classes

Let’s take a look at what we’ll be learning:

• Transforming points in three dimensions
• Randomizing variables
• How to structure a recursive object

And now why would we want to learn it…

The use for a recursive tree

The most obvious reason to write a tree generating script is… to generate trees. It would be fairly simple to export the coordinates of this tree into any 3D modeling software. Texture mapping and such would be tricky, because as you’ll see, this script uses segments as branches, not three-dimensional shapes. But nevertheless, it would be a nice addition to your next architectural project: some non-generic, bare trees in the landscape.

Of course, branching structures are used in more than just trees. Let me know if you think of other uses. Maybe something like… plotting three-dimensional decision making graphs? Where the sum of a user’s choices is represented by a single point within a cloud of possible outcomes? That could be a nice way of comparing the results of a survey in three dimensions.

And now, let the games begin…

Read more…