Infinite Procedural Generation: 2 -- Chunk Indexing

In my last post, I discussed how chunk-based generation of Minecraft's infinite world works (on a very basic level). In this post I want to talk about implementing such a system in practice.

In fact, I want to try and lay out a very general way of thinking about chunk-based infinite generation. One that works on 2d and 3d grids of any type, irregular partitioning of the plane, and much more.

Chunk Indexes

Indexing chunks seems trivial, but I promise there's somewhere interesting to go here.

We need to pin down a system for identifying chunks. There are two reasons for this:

1. Chunk indexes are generally used as keys when storing chunks
2. Chunk indexes implicitly provide a system for transitioning between world coordinates and their associated chunk.

The simplest chunking system is axis aligned squares, as discussed last post. Here, the chunk index is a tuple of integers, and can easily be found via integer division.

index(x,y) := (x//16, y//16)

We can also reason about which points belong to each chunk (cx, cy).

16cx <= x < 16(cx+1), 16cy <= y< 16(cy+1)

There are other conceivable systems though. For instance, we could use a hexagonal grid to make chunks. Natural indexes for hexagons are also tuples, but the mapping is a bit more complicated.

There's also the potential for more irregular chunking systems. It's conceivable that some aperiodic tiling or other irregular partitioning could produce good results. Tiles could be Voronoi regions of some arbitrary infinite graph, or correspond to simulated geopolitical boundaries. In these systems, there might be some arbitrary function to create chunk indexes from world points.

Chunks could also parameterize non-euclidean spaces! For instance, we might be looking at the surface of a large sphere. Technically this system is finite, but it could be prohibitive to generate and serve the entire world at once, so applying infinite generation techniques is desirable. We can also imagine some game taking place in a hyperbolic space that truly is infinite. In these systems, the world coordinates are more complex than just normal tuples.

We can even think about more exotic world coordinates. Perhaps the world coordinates are discrete, and each world coordinate corresponds to a node in an infinite graph. Chunks are small collections of "nearby" nodes. We could handle this case by embedding the graph in some other world coordinate system and using chunks in that system, but we don't technically have to, as long as we have some system for partitioning the world coordinates.

Some definitions

In general, let's create the following conventions for our abstraction.

We have some space of world coordinates, W. A specific member of this set is denoted by w∈W. We also have a set of (discrete) chunk indexes, C, with  c∈C. We'll also define a "boundary" type, b∈B. This boundary denotes a contiguous set of world coordinates. 

We'll also define two related functions to map between these domains.

index: W↦C

boundary: C↦W

These functions must obey that ∀w, ∀p∈boundary(index(w)), index(w) == index(p).

In plain English, index / boundary should partition the world coordinates into discrete, predictable chunks.

Chunks and Layers

Something I kind of glossed over in my last post is that world generation, typically, doesn't happen all at once. There are intermediate steps.

When I discussed cave generation, I mentioned that during each chunk's generation process, it would need to look at cave seeds in surrounding chunks, but these chunks may not be generated yet! How can we find the cave seeds without generating them (which in turn would generate all their neighbors, ad infinitum)?

There are a few different answers here, but in my view the most extensible one is to think of world generation happening in layers.

In this case, we can generate cave seeds in a separate layer, that depends on nothing else. It's just random points, say 2-5 selected per chunk index. This "cave seed layer" doesn't need to look at any other chunks during generation. It just is. When the "world with caves" layer is generated, we can look only at this "cave seed layer" -- we don't need to know, and therefore don't need to generate, the full content of the neighbor chunks.

These world generation layers need to form a pre-determined directed acyclic graph, with higher order layers depending on only layers below them. Some layers don't have any external dependencies and can be generated completely independently. Others will require exploring other layers and neighboring chunks.

Note that both the nodes and edges in this graph have interesting interpretations.

In one sense, nodes contain data -- there's a mapping between the index of the chunk and the contents of that chunk. In another, it's helpful to think of the node as simply being a function which takes in the contents of its dependencies and outputs this data.

Edges don't just note that we need to look at the contents of a layer, they also contain a rule about which relative chunk indexes to look at. I call these mappings "chunk index transfer functions".

Chunk Index Transfer Functions

Given a chunk index in one layer, the transfer function maps us onto  

chunk_transfer: C↦𝒫(C)

Note that while the above definition, we're implicitly assuming that all layers use the same chunk index system. That isn't required. We could use different indexes for each layer, in which case, the slightly more general statement for the edge between layer a and layer b is:

chunk_transfer: C_a ↦𝒫(C_b)

Example

For instance, we can imagine a chunk transfer function for Minecraft caves. Given a chunk index, we need to select all chunks within the maximum cave length. We can express this distance in terms of the size of a chunk, a quantity I'll denote L.

within(L)((i,j)) := {(i+di, j+dj) ∀ di∈[-L,L], dj∈[-L,L] }

Note that we could tighten this substantially -- we're finding all chunks within Manhattan distance L, where we probably in fact want chunks within Euclidean distance L.

Memoizing Chunk Contents

To make this work, we'll probably want to memorize the contents of most, if not all chunk contents on each layer. For right now, let's assume that the contents of each chunk are some arbitrary data.

Each layer can be memoized separately, ore we could put them all into a single dictionary. For right now, let's keep them separate.

A world can be therefore memorized in a Dict[Layer, Dict[ChunkIndex, ArbitraryWorldData]], or any equivalent data structure. There are definitely interesting choices to be made here, since there are clear patterns in how chunk contents get read. For now, I won't explore this further.

World Generation

Putting this altogether suggests a simple approach to world generation.

For a given  desired world coordinate, lookup the associated chunk. Optionally, extend to all nearby chunks.

Now, follow the transfer function edges to determine which chunks need to be generated for each dependent layer. Where possible, pull from the memoized cache. Each chunk that doesn't exist is generated and cached.

It's also possible to batch generations for each layer, if there are efficiency gains to be had.

In the next post, I'll discuss one of the simplest non-trivial applications of this work, generating Poisson Discs, and hopefully share some actual code.

Infinite Procedural Generation: 1 -- Introduction and Problem Statement

I know it's been forever since I've posted. Maybe I'll write another post about why I'm coming back now sometime. Regardless, I plan to try and make shorter, more regular posts.

Procedural Generation of infinite game worlds is hard. It's hard because it presents challenging technical problems. It's hard because an infinite world can make things seem very same-y. It can cause challenges in structuring player progression. Finally, it's hard because a lot of the really cool techniques and algorithms people use for procedural generation are hard to adapt to infinite worlds.

It's this last point I want to explore in this series. How can we apply procedural generation techniques typically used in smaller examples to an infinite world? Which work well? Which can be reliably composed together?

I believe I have a compelling framework to do this. I've seen some early success adapting some pretty interesting techniques, and I want to share my progress as I go along.

In this post, I want to take some time to discuss how existing systems, particularly Minecraft and Factorio, approach this problem. I picked these examples because they're successful games with procedural worlds at their core, and both are fairly well documented, with active modding communities that deeply understand the world generation systems.

I'm going to stay high level in this post, just giving some context. In future posts, we'll take a closer look at some of the implementation details.

Chunks

First, these systems break the infinite world up into "Chunks" -- finite tiles that can be independently loaded and processed. Both of these games use a 2D Chunk system, but there's nothing inherently special about that. It would be just as sensible to for Minecraft to use 3D chunks, and it would be reasonable for a side scrolling game (e.g. something like Terraria) to use 1D chunks. 

Really the relevant thing to think about here is how many dimensions of the world are infinite -- in Minecraft, for instance, the world extends infinitely in all horizontal directions, but there's a finite amount of vertical space. You can't mine infinitely deep, or climb infinitely high into the sky.

In Minecraft, these chunks are fairly small relative to the player -- just 16x16 blocks. Factorio isn't much different -- only 32x32 tiles. For most applications, it makes sense to keep the Chunks small. As we'll see, Chunk size doesn't have a lot of effect on what algorithms you can use during generation; it's mostly a practical choice for in game performance.

You want to be able to load and save chunks to the disk quickly, so the relevant tradeoff is more about keep chunks small enough to make loading fast, but large enough that you're not going to be doing potentially expensive disk seek operations too often. Both of these games have picked a chunk size such that the player can traverse across a chunk in about 3.5 seconds of real time.

Both of these games have also selected axis-aligned square chunks, which are easy to index and translate into screen / game coordinates. As we'll probably discuss in a future post, I don't think this choice is always the best during the generation process, but it makes a lot of sense for performance and simplicity when actually serving up an infinite world in game.

Chunk Generation Order Shouldn't Affect the Result

We should be able to generate chunks individually and in any order.

In theory, we could envision other systems. A sweepline / sweepcircle algorithm starting at the origin would enforce the order in which chunks are generated. Alternatively, we could imagine a system when each new chunk is based directly its already generated neighbors, so that two players, starting with the same seed, would see different worlds based on the order in which they explored.

But these systems have undesirable behavior -- in the first, world generation becomes more and more expensive as the player moves away from the origin. In the second, we risk creating boundary conditions that are unsatisfiable or absurd -- Imagine two players approaching the same chunk from opposite directions. Player A is on top of a huge mountain, Player B is sailing on a massive ocean. The world generation system would be forced to construct a massive cliff within a 16-tile region in order to bridge the gap.

It's better to add the constraint that, in some sense, the world is fixed by the seed, and we can just peek at only the parts we need at any given moment. This means that we need to ensure that

1. Generating any chunk, regardless of its position, is approximately as expensive as generating any other.
2. The order in which we generate chunks should not matter.

Bounded Reach Effects

In order to compute the contents of a chunk, you should only have to look at a small neighborhood around that chunk. As an example, let's think about how Minecraft's caves used to work. Newer updates have made caves into a much fancier system, but the old system is easier to understand, so I'm going to start there.

Classic Minecraft caves are basically Perlin Worms. Let's not get bogged down in the specifics yet; each cave is a long, wiggly line, which starts from some point, and extends up to some maximum distance. Let's assume that we can find all the places a cave should start within a chunk (I'll call this a cave seed), and that we've got some way to actually generate the cave itself -- given a cave seed, we can determine which blocks we should carve out.

The core observation here is that because a cave has a maximum length, when we're generating a chunk, we only have to look in a fairly small radius around that chunk for the cave seeds. If each individual cave can extend at most 256 blocks, then we only need to look at the Cave seeds less than 16 chunks away. That set of cave seeds will tell us which blocks in our chunk we need to remove.

Because of the way caves can intersect each other, we will end up with systems of caves that intersect each other, and extend further than 256 blocks -- potentially infinitely -- but each individual chunk only needs to look at its immediate neighborhood during generation.

Many algorithms only care about the immediate neighbors of a chunk. Others, like cave generation, need to look at a larger, but still constant, set of neighbors. I'll talk about how I've come to abstract these sorts of relationships in a future post.

Perlin Noise and other Infinite Functions

Perlin Noise, Simplex Noise, and other similar coherent noise functions are a mainstay of procedural generation. part of the reason is that they naturally obey a lot of the properties we've been talking about above.

Imagining we have some mathematical function f(x,y,z) with closed form, we can evaluate that function at any point, in any order, and get consistent results. Methods like Perlin noise operate by summing up small, local wavelets. That means that, to compute the noise value at a specific point, it's possible to examine a small, finite amount of wavelets -- just like the cave seeds. It's a natural fit -- and that's even ignoring the fact that many applications work by summing noise at multiple octaves, which may mean it's possible to create infinite, apparently non-periodic noise just by sampling a small number of finite textures.

Regardless, there are a bunch of clever ways to use noise functions to create features of infinite worlds. You can threshold the value to create ore patches. You can multiply or sum noise with simple or even linear functions to create terrain surfaces, or enforce difficulty curves (e.g. Factorio ore patches get richer as you move further out -- but so do the density and intensity of biter nests). You can use the same noise channels for different things, leading to correlations among the generated features (e.g. richer ore under mountains). You can create coherent biomes by using noise to generate temperature, rainfall, and "geology", and then apply simple functions on top of those values.

In fact, it's tempting to think you can do everything this way! In a general sense, perhaps you can, but in my opinion, this approach comes with pitfalls. In particular, it's hard to enforce structure on a world generated this way. It defies simple mid-generation modifications, and it can be hard to interpret and reason about behavior.

It also pushes things towards an interpretation where the underlying world is being sampled from a continuous function. That's a good fit for some applications, but it breaks down around things that are supposed to look designed or sensible. It's easier to make an organic, natural environment that works this way than a city, or highway system.

Pre-generated Structures and Sub-Generators

One way to augment noise based generation is to take inspiration from our Cave seeds from earlier -- what if we used the noise to place structure seeds? Then we could stamp down pre-created structures on these seeds, or even invoke smaller, finite, procedural generation sub-routines to create complex structures for each of these seeds. As long as we know in advance what the maximum size of a generated structure is, we can use the same approach as caves to stamp them down.

Minecraft works exactly like this. Desert Temples, Villages, Mineshafts, Ruined Portals and more are effectively small, self contained generators that operate after the basics of the world are laid down. They give a lot of control and structure to the world. 

In my opinion, they're also one of the weakest aspects of Minecraft's world generation. Procedural generation of "designed" structures is hard, but Minecraft's villages tend to feel incredibly same-y. There's only one type of Desert temple, and once you've encounter it, you know them all. Structures never interact with each other, or tell a broader story. You might come across a village and a mineshaft just blocks away from each other, but they won't influence each other -- there won't be more mining-related jobs in the village, and you won't find a mineshaft that even attempts to look like it's in active use.

People are still great at coloring in the blanks and telling a story, but it helps a lot if the world makes some attempt to help or hint at depth. Minecraft doesn't do that, and one of the big reasons is this seed system -- every structure seed needs to be generated independently, and in a specific order. They don't get an opportunity to "talk" to each other in a meaningful way.

In a future post, I hope to talk about alternatives that approach the same problem a bit more cohesively. I think embracing the idea of small, structured "stories" like "this village uses the nearby mine to create goods for export" is essential to getting a good result.

Wrap up and Conclusion

I think this is a good place to call it for today. I've mostly discussed how Minecraft's world generation system works at a 1000ft view -- use noise to generate a bunch of big continuous natural world functions, add discrete seeds various places, then use sub-generators to make structures within that world of small finite size.

As long as you follow some simple, and not too restrictive rules, you'll be able to generate the world, chunk-by-chunk, in any order you want. And once you have those chunks, you'll be able to serve and modify them without worrying about world generation at all. The pitfall is that sometimes these restrictions keep you from creating easy wins, and they make certain types of cross-chunk structure hard to create.

There are a lot of important details involved in implementing this system. My next post will probably be about how to think about creating the abstractions needed to implement, and extend on this system, because I think the seeds of greatness are tied up in the details here. I'll then start to talk about how to make some (imo) interesting "toy" infinite generation systems that challenge what's possible.

Extending SRP's guarantees to validated registration

This post is about work done jointly with Michael Sanders and Jacob Hurwitz for 6.858 (One of MIT's Computer System's Security courses).

The Stanford Remote Password Protocol is a really amazing little piece of cryptography. Like almost every great crypto-system, it provides seemingly impossible guarantees. Namely, it allows a server to recognize a client without having any real usable information about them.

In most authentication systems, the server is at some point in time privy to sufficient information to impersonate the user: perhaps you send your password to Google, Microsoft, or Facebook, or perhaps you send a hash. Regardless, as some point in the process, the server sees enough information about your password to fake a login later. With SRP, this isn't the case. To quote the SRP website:

SRP is a secure password-based authentication and key-exchange protocol. It solves the problem of authenticating clients to servers securely, in cases where the user of the client software must memorize a small secret (like a password) and carries no other secret information, and where the server carries a verifier for each user, which allows it to authenticate the client but which, if compromised, would not allow the attacker to impersonate the client. In addition, SRP exchanges a cryptographically-strong secret as a byproduct of successful authentication, which enables the two parties to communicate securely.

 Still, there is a slight problem with SRP, if you're willing to crimp down your tinfoil hat a little.

It's been a while!

I haven't forgotten about this blog! I've just been a tad busy recently.

I've got a bunch of projects (mostly classwork, I confess) I plan to post soon, so check back in a week or so!

~Ninjinuity

Voice Controlling Hexy

(This post is a bit rough, but I figured I should get it out there, since I won't be working on Hexy for a little while.)
Before we get started:

1. The code used to make this all work is on Github. I'm new to ROS, so I don't claim that it's set up correctly.
2. To get things to ROSLaunch nicely, I had to make some pretty hacky changes to how PoMoCo deals with directories. Basically, it now has to use full paths to every directory ( these paths are created at runtime using __file__ ). I haven't seen it fail yet, and I can't think of a specific failure mode, but it makes me very uncomfortable, and I'm looking for a way to change it.
3. ROSPoMoCo isn't a full substitute for PoMoCo yet. Offsets, for instance, can't be set in ROS, though they are loaded from the .cfg file.

After a bit of hacking, I've ported most of PoMoCo over to run as a ROS Node. This node listens for new moves on the /moves topic and runs them if it is able to (If it can't find the move, it issues a Warning and ignores it).

At this point, it's time to take advantage of ROS to do neat stuff with Hexy. At first, I wasn't sure what exactly I wanted to do, but some Googling brought up this blog post, in which an iRobot create is controlled by voice. The package used to do this is perfect for controlling something like Hexy -- pocketsphinx will broadcast any recognized phrase on the \output topic, and the set of recognized phrases can be set with a text file.

Starting out with ROS

This is going to be a pretty short post with the purpose of motivating future posts on related subjects.

I've got a lot of really cool robotics equipment now; a stock Hexy, a Cyclone Quadrotor, a Kinect, and a MakerBot Thing-O-Matic top the list, at the moment.

Unfortunately, a lot of these pieces of Hardware come with relatively  little software behind them. Hexy, for instance, has the short-but-sweet PoMoCo software to start. PoMoCo is great, but it's not very functional; by default, it allows only for interpolation between pre-programmed sequences of joint angles. It's very easy to pick the wrong combination of moves and get Hexy stuck in some contorted pose ( and you can forget about variable speed gaits ).

This isn't really PoMoCo's fault. Like Hexy, PoMoCo is designed to be a lightweight tool for beginners who can go on to use the platform for other things.

So, what's next for me on the Software side of Hexy? First off, I want to integrate Hexy with ROS (more on ROS in a later post). At first, I'm just going to hook PoMoCo into ROS and control it from the command line, but I plan on splitting PoMoCo into three ROS nodes, with the eventual goal of augmenting one of them with good gait generation and motor planning, and replacing the other with a series of ROS services to utilize Hexy from any ROS interfaced program.

In any case, I'll be working on Hexy when I  don't have to tool, and tooling when I can to get as much work in on Hexy. I'll keep you posted.

Voroni Diagrams and Graphs IV: Efficient Computation of the Graph and it's simplexes.

Before we jump into algorithms, a few things. The algorithm I'm about to lay out is a version of the Bowyer-Watson algorithm I've referenced in a previous post. It's been pretty heavily modified since, and it was not my initial intent for it to be thins similar. Nonetheless, I think that my implementation has better asymptotic time than any implementation of the original I've yet seen, since (as we'll see) the most intensive parts of the algorithm (most of which were related to searches over the point set) have been offloaded to a simple graph search. We'll also be looking at things through the lens of the Voroni Graph, rather than the Delaunay Triangulation.

A Simple 2D Graphics Engine Powered by OpenGL/GLUT.

In the course of coding up my ideas on the Voroni Graph, it became apparent that a CLI wasn't going to cut it. I needed some sort of graphical library, both for the final visualization, and for debugging. For this, I've chosen to use OpenGL with my own wrappers on top. This is a log of what I've been working on for the past few evenings.

This is, without the slightest doubt, overkill for what I'm doing right now (2D, very few colors, order of 100 different positions.). Screw that, I'm using OpenGL anyways. Why? I want the experience, and I want to write my own graphics engines that won't be limited by the underlying platform.

In any case, the process of getting to where I am now has been fairly frustrating. The documentation for all sorts of things involving OpenGL on the web is scant and often contradictory. Some things didn't work, other important aspects of a simple program had been depreciated. Getting even a blank screen to compile was a significant achievement.

In any case, this was all difficult enough to warrant a post and some preliminary code. Below is a sort of black box on the whole process, written as I worked through everything. For this reason, please excuse the weird tenses.

Prelude and Fugue

There's a long story behind these: Basically, they were written for me in about 10 minutes during orientation after an off comment that I played the cello. Yes this is in pen (though I did enhance the contrast). Hit the break to see scans...

Voroni Diagrams and Graphs III: The Dual.

In this post, I'll write about the geometric significance of the dual of the Voroni graph and try to convince you that we can extend our discussion, which has so far focused on two dimensions, up to three-dimensions with only some minor changes ( I'll conjecture that the relationships I'm about to lay out extend much beyond that, but I don't have much proof of this ).


First, though, we need to discuss what a dual is.


The dual of a graph is itself another graph. Basically every face in the graph is a node in the dual, and two nodes in the dual have an edge between them if ( and only if ) their two corresponding faces share an edge (corners don't count).

The dual of a planar graph is itself a planar graph, and I claim that the dual of the dual of a graph is the graph itself (with the caveat that we discuss in the next paragraph). The figure below hints at a proof for this (note the crossing edges), though I'm not going to formalize it.

Voroni Diagrams and Graphs II: Some Applications of the Voroni Graph.

In this post, I'll further discuss the concept of the Voroni graph we talked about last time, and talk about some uses. We'll see more uses in the next post, where I'll talk a bit about a related graph.

Supposing we know the Voroni Graph of a set of points, what can we do with it?

First, we can use it to check if a point p is in the Voroni cell of some point in our set q. If we find all the neighbors of q ( points that have an edge to q in the Voroni Graph ) we only have to check to make sure that p is closer to q than any of these points, since we already know that these neighbors alone are sufficient to define the cell of q.

Let's briefly look at how much of an improvement this is over a normal check. Let's assume we have a set of n randomly distributed points, and n is very large (AKA we can neglect the effects of the outermost border of the points, and we're not going to get anything unusual in our graph).

If we have to check each point to see if p is closest to q, then we'll take O(n) time. This isn't bad, but if we assume we have access to the Voroni graph, we can do much better.

We need to find how many neighbors a typical Voroni diagram has.We know that the Voroni graph is planar, so it will obey Euler's formula ( V − E + F = 2 ). If the points are fairly random, then almost all of the "faces" of the graph will be triangles ( A non triangular face, we'll see later, implies that at least four of the points lie on a single circle, which is in general not true. ). Because of this F = 2E / 3 ( each triangle is bounded by three edges, and each edge divides two triangles ).

V - E + (2/3) E = 2

V - 2 = (1/3) E

E/V = 3 - 6 / V
2E/V = 6 - 12 / V

The quantity 2E/V represents the average number of neighbors of each vertex (we double the number of edges so that both ends can count it). Thus, as the number of vertices becomes large, each vertex will have on average only 6 neighbors. Thus, if we can use the Voroni Graph, we can check our point in only O(1) time!

It's worth noting of course, that this isn't quite as good as it seems. After all, we still have to compute the Voroni Graph, and we'll need to store it in such a way as to allow ourselves to look up a given vertex quickly. Still, it's an achievement, and it lets us know that if we're going to be checking lots of points, we'd be better off investing our time in making the Voroni graph rather than brute forcing the problem.

Even better, because p is in the cell of q if and only if it is closer to q than q's neighbors, it is also painless to find out which point is closest to p. We simply pick a starting point q₁, and check if that point is closest to p. If it is not, we call the neighbor of q₁ q₂, and check if it is closest. This continues until we find that p is closest to q_n relative to its neighbors Because of the nice properties of the Voroni graph, we can say that q_n will be the point in our point set which is closest to p. In other words, having the Voroni graph lets us do a greedy search to find the Voroni cell to which a point belongs.

I would love to analyse the run-time of this particular algorithm, given a large set of points and a randomly chosen starting point, but I must confess I am not clever enough to put down any of my thoughts on paper at this point. I'll continue to think on it, but my money is on O( n^1/2 ) for 2D ( and more generally O( n^1/d ) for dimension d ). I think this is how the average euclidean distance between two randomly selected points scales as the number of points increases.

In any case, it is a great improvement over the naive approach, which would require us to check the distance to every point, and thus would have O( n ) run-time.

That's it for this post. I've got two more queued up and ready to go as soon as I have time to edit them and add figures, so expect more on this topic soon.

The Hough Transform I: Finding Lines

I've made reference to the Hough Transform in several previous posts, but I haven't ever done posts on what the transform is in a general sense, and how I've used it (and tried to improve it) in the past. In this series of posts, I'll try to rectify that.

The most basic implementation of the Hough transform is used to find lines in an edge image like the one below.  In this post I'll walk through the basic process of using the Hough transform to find lines in this image.

An image of machinery with edge detection applied. This image would be a good candidate for further processing with the Hough transform. (Source: Wikipedia)

Underlying the Hough transform is the idea that each pixel in an an image tells us something about the chances of there being certain lines in the entire image. If we have a pixel at point p, then it would make sense to look at all the lines that pass through p, and see if any of them happen to pass very close many other points in the image. If a particular line through p passes close to an unusual number of points, then it's a pretty reasonable to assume that this line constitutes an actual feature in the image.

MIT Library Scanning...

...turns out to be a great way to scan figures. It's a ton faster than using my own scanner, and the resolution isn't too much worse. I'm writing a few math-oriented and cs-oriented posts with figures right now, and the book scanner means I can just box figures in my notebooks and use Gimp / Picasa Web Albums to crop things down and clear up the colors. It's a much faster pipeline than what I had before, and I'll hopefully make use of it to put lots of pretty figures in my posts.

Voroni Diagrams and Graphs I: Introduction

Suppose we have a set of points { p₀, p₁, ..., p_n }, each of which lives in R². A Voroni Diagram is a partitioning R² into regions { [p₀], [p₁], ..., [p_n] } so that any point q in [p_i] is at least as close to p_i as any other p_j. Note that, for most points, this should mean that q is strictly closest to p_i, but we're also going to include the boundaries of these regions, so they'll all be closed sets ( If it were to strike your fancy, you could also use open sets. We'll use the closed property a bit later on, but it's mostly personal preference. ).

This is all a perfectly good definition of what Voroni Diagrams are, but it doesn't explain how to find them in practical situations or what they're useful for. In this post, I'll explain a basic approach for finding a Voroni Diagram, and present an (inefficient) algorithm I made up to find what I call the Voroni graph: a graph whose vertices are the { p₀, p₁, ..., p_n }, and whose structure describes the diagram (and provides a quick way to check if q is in a given [p_i], among other things ).

Quaternions I: Overview

What are quaternions? Let's start with what quaternions once were: an attempt to extend Complex numbers to three dimensions.

Back when the geometric interpretation of complex numbers as a plane was reasonably fresh, Sir William Hamilton became interested in finding a system of algebra that would allow him to express three dimensional space in the same way. To do this, Hamilton needed a way to add and multiply points in 3 dimensional space together.

Addition came easy. Picking some arbitrary origin and axes 1, i, and j to work with, Hamilton just defined (a + bi +cj) + (d + ei +fj ) = ( a + d ) + ( b + e )i + ( c  + f )j.

Multiplication, though, was a problem. Assuming that these new quantities were distributive, Hamilton needed to define ij in such a way that various other properties still held. Despite his best efforts, he couldn't do it.

SPLASH!

These are all the materials I used/planned to use in class. I'll also put some links below for topics/sites I find interesting. Hope it helps! If you leave comments, I can try to get back to you and direct you to resources.
Happy Coding!
~Will

Where to go in order to...

• Install Python
• Install Notepad++ (A good text editor for working with python on windows. On Linux/Mac, you should be able to use whatever you have on hand.)
• Learn Python
• Do fun problems!

Stuff I wrote for the class (I'm planning on teaching this class again next year, so I may write more worksheets...):

• Expressing the (almost) Infinite
• Project Euler Problems

Neat Topics

• http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
• http://en.wikipedia.org/wiki/Collatz_conjecture
• http://en.wikipedia.org/wiki/Genetic_algorithm
• and more...

Imaging Exoplanets: Out of this world pictures

   Back in 2008, the image at left was plastered across the front page of many science related publications. For the first time, scientists had directly imaged an exoplanet (a planet which orbits another star) with visible light.
   Exoplanets themselves were nothing new.  In late 2008, 333 exoplanet canidates were known, and 8 of those had been detected using direct imaging. In fact, Fomalhaut b itself, the planet pictured, was actually not truly a new discovery. Since 2004 scientists had been reasonably confident it existed because of the sharp inner edge of the band of dust around the star Formalhaut. The thought was that a large planet (namely Fomalhaut b) was sweeping the material from the inside of the band into itself.

Of mice, men, and microRNAs.

   Although RNA is most famous for acting as an intermediate between DNA and Protein, we've come to understand that RNA's role in the cell goes far further in recent years. Some kinds of RNA, like miRNAs, actually change the balances of proteins made, leading to a wide variety of effects.
  What exactly is a miRNA? miRNAs or microRNAs are tiny segments of RNA. Where most RNA segments are about 1,400 nucleotides long, miRNAs are typically only about 22 nucleotides long. While miRNAs are sometimes written out by themselves on DNA (as in the video above), it's more common to see miRNAs created as a byproduct of the creation of other kinds of RNA. Unlike many other types of RNA, miRNAs don't encode for proteins or assist in their transcription of RNAs to protein. Instead, miRNAs prevent proteins from being made from mRNAs by latching onto them before they can be transcribed. In the past few years, miRNAs have been implicated in certain types of cancer, and been used as biomarkers to help detect and diagnose diseases.
   All of this is very exciting on its own, but more exciting still is a paper recently published in Nature Cell Research which suggests that miRNAs can actually travel from material in the digestive system of an organisms you eat into its bloodstream. Scientists at Nanjing University, China found a certain miRNA from rice, called MIR168a, in the bloodstreams of both humans and mice. By varying the diets of lab mice, they were subsequently able to show that the miRNAs found in mouse blood were being ingested.
   This alone is an important discovery, but the researchers further "hypothesized that [plant miRNAs] may play a role in regulating the functions of mammalian cells and organs". Looking through the known sequences of mouse and human mRNAs, they identified about 50 proteins which MIR168a was likely to interfere with, including LDLRAP1, a gene that codes for a liver protein in both humans and mice. By exposing a certain type of liver cell (HepG2) to increased miRNAs, they determined that "Plant MIR168a...significantly decreased the LDLRAP1 protein level in the recipient HepG2 cells" while LDLRAP1 mRNA levels remained unaffected. In other words, the miRNA was preventing the transcription of the LDLRAP1 mRNA, as expected.
   Why care about this result? It further clouds the waters regarding the role environment plays gene expression, an area of much of interest in biology right now. In addition, if miRNA uptake turns out to be common (or at least easy to induce) in humans then it could lead to whole new classes of oral drugs that target the expression of specific proteins.

E≈Mc^2?

   If there's one result worth posting about from this week, it is the now famous (and in some circles infamous) exchange of neutrinos between CERN and OPERA, two European physics laboratories. Neutrinos are pretty cool as is, but what's really of interest here is what the neutrinos (muon-neutrinos, to be exact) appear to be doing on their trip from their creation at CERN to their detection at OPERA. They're arriving ever so slightly early: 60 nanoseconds early to be precise. For reference, quick calculation shows that light only travels 24 meters (just under 80 feet) in that time.
   How fast light travels is actually exactly what's at issue here; the neutrinos seem to be arriving at OPERA before light traveling along the same path would. If it is true this is the most significant find in physics for a century at least. For all practical purposes though, getting a result like this is a really good reason to check your equipment for obvious problems.

What is about to happen.

Starting next week (and possibly this week for practice) you can expect to see two new articles per week (posted on Saturdays?)on current events in science along with some reasons you should care.
As part of my first semester at MIT, I'm taking a Science Journalism class. Part of this class is the creation (and weekly updating) of a blog on science, medicine, technology, and related topics.