Alex Beutel's Mental Masturbation, Musings, and Methods

Interactive Voronoi Diagrams with WebGL

Alex — Mon, 02 Aug 2010 06:20:49 +0000

Within computational geometry, the Voronoi diagram is a relatively simple concept with a wide-range of applications. Everything from physics research to the “snap-to” feature in GUI-design uses Voronoi diagrams as a simple underlying data structure to decompose space. I have been working with Voronoi diagrams for the past few months, as my research has focused on interpolation, specifically scalable natural neighbor interpolation. Because the interpolation I have been doing (and the demo I have created) focuses on Voronoi diagrams in a plane, I will only discuss the Voronoi diagrams in 2D space. However, the mathematical concepts can be extended to higher dimensions.

If you already know all about Voronoi diagrams or simply don’t care about the math and just want to play, jump to here or go straight to my Voronoi diagram generator application.

The Voronoi Diagram

I would first like to briefly describe what precisely the Voronoi diagram is, along with how nearest neighbor and natural neighbor interpolation make use of this data structure. The Voronoi diagram is the division of plane into discrete Voronoi cells. Given a set of input points S, we would like to divide the plane such that for any given position in the plane, we know the nearest input point. This is the nearest neighbor problem. A Voronoi cell Vor(p,S) represents the region of the plane for which the given point p is the closest input point from the set of input points S. Mathematically the Voronoi cell Vor(p,S) is defined as

In the Voronoi diagram below, we color each Voronoi cell with a unique color. For the entire region covered by each cell, the input point within the cell is the closest point from the set of input points. You can also easily observe that the boundaries between neighboring cells is the set of points equidistant between two nearby input points.

Interpolation with the Voronoi Diagram

Given this understanding of the Voronoi diagram, we can easily answer a nearest neighbor query. Given a point q at position (x,y) we need only check which Voronoi cell it is within to see which input point is closest to it. Thus, if each input point also has some height z we could roughly interpolate the height of q by taking the height of its nearest neighbor.

A more complex interpolation scheme, known as natural neighbor interpolation, is to take a weighted average of all of the nearby input points. This is done by inserting the query point into the Voronoi diagram and observing how much area the Voronoi cell of the query point steals from the neighboring Voronoi cells in the original Voronoi diagram. Specifically, the fractional weight assigned to each natural neighbor is the area stolen from that nearest neighbor’s original Voronoi cell divided by the total area of the Voronoi cell of the query point. Mathematically this interpolation can be defined as:

While more complicated than nearest neighbor interpolation, natural neighbor interpolation offers a higher quality interpolation and produces smooth results.

Approximating the Voronoi Diagram in OpenGL

As explained briefly in the OpenGL Red Book, we can compute the Voronoi diagram easily in OpenGL by rendering cones at each input point and using the depth buffer to figure out the boundaries between Voronoi cells. Specifically, if we place a right angle cone with the apex at a point, the height of the cone at a given position is equal to the distance form the point in the x,y plane. As such, if we place all the cones in the plane and look at them from below, we will only see the lowest cone at any given point and thus only the cone for which the point it represents is closest. This is known as taking the lower envelope. (For more information, you can read Hoff et. al.’s paper on how this works.)

Therefore, by merely drawing the cones and placing the viewpoint appropriately within OpenGL, the framebuffer will store the Voronoi diagram. Naturally, when doing computations with OpenGL, the diagram will be discretized into pixels. Additionally, OpenGL can not draw cones, only triangles. Therefore, we approximate a cone with a f-sided pyramid. With a reasonably large value for f, we will not notice the effect of the discretization, but making f a small value like 4-10 can be interesting. Both of these discretizations of course create some deviation from the previously defined Voronoi diagram.

I have used this method, implemented in WebGL, the Javascript API to OpenGL, to create the following interactive Voronoi diagram generator.

Enough Math

While math is necessary to precisely describe these concepts, it is not always the best way to convey some of the nuances of the geometric behavior. As a result, one night, both to play with WebGL and to better understand Voronoi diagrams, I implemented some of these concepts in the browser. Below is a short screencast of me playing with the tool, which may be useful if either you don’t have a WebGL-enabled browser or you want to learn some of the features of tool; or just play with it for yourself.

On Code

Not much to say here. To make this small application, I used two canvases overlaid, one with WebGL and one with just the 2D-context. This allowed me to draw over the Voronoi diagram (such as the points). Following the learningwebgl.com tutorials, I used the Sylvester library for Matrix math as well as the glUtils library from the tutorials.

WebGL is still a little buggy and memory management can be an issue, among other things. But overall, it samples a good portion of OpenGL. Unfortunately, getting started can take a little effort. For example, unlike OpenGL in C++, you must write your own shader programs; I suggest using samples from learningwebgl.com at least to get started. However, once you have a functioning WebGL canvas, it is easy to pick up speed. I also went slightly overboard on the movement functions, but it was a good chance to play with Javascript closures.

Some cool Voronoi diagrams

And finally, here are some Voronoi diagrams I have generated that I find interesting, cool, or merely pretty.

Similar kinetic Voronoi diagram but with only 6-sided pyramids used.

Below, the same set of input points are plotted with two different types of cones. The first uses a 50-sided pyramid. The second only uses 6-sided pyramids, creating the jagged effect between neigboring Voronoi cells.

The following two Voronoi diagrams show the Voronoi cells and area stolen for a natural neighbor query.

CMake, OpenGL, and GLX on OS X

Alex — Wed, 28 Jul 2010 23:24:32 +0000

As you may know, I am staying at Duke this summer for research. My research, which I started last semester and am going to be doing for a while, focuses on scalable algorithms. While that is pretty broad, I am currently working on using the graphics card to speed up processing. Again, here are some technical notes on code.

In doing my work I have come to have to write and run C++ OpenGL code on both OS X and Ubuntu. To make this easier, CMake has been great for both having readable make files and for being able to keep the files consistent across both platforms. Additionally, while GLUT is great for cross-platform OpenGL coding, I needed more control over the environment. Being able to run X11 on OS X has allowed me to test GLX natively without always testing on Linux. However, to get this set up on OS X without XCode can be a little tricky. So, two snippets of CMake files for using OpenGL on OS X and Linux.

If you want to run OpenGL with the standard OS X libraries, CMake generally finds the correct frameworks, but it can’t hurt to specify them more precisely. A basic example of the CMakeLists is shown below:

IF(APPLE)
   INCLUDE_DIRECTORIES ( /System/Library/Frameworks )
   FIND_LIBRARY(COCOA_LIBRARY Cocoa)
   FIND_LIBRARY(GLUT_LIBRARY GLUT )
   FIND_LIBRARY(OpenGL_LIBRARY OpenGL )
   MARK_AS_ADVANCED (COCOA_LIBRARY
                     GLUT_LIBRARY
                     OpenGL_LIBRARY)
   SET(EXTRA_LIBS ${COCOA_LIBRARY} ${GLUT_LIBRARY} ${OpenGL_LIBRARY})
ENDIF (APPLE)
target_link_libraries(main ${EXTRA_LIBS})

With this, your C++ should have the following includes:

^?View Code CPP

#include 
#include 
#include 
#include

If, however, you are looking to run your code also on a Linux machine or simply want to use GLX rather than CGL, you will need to have X11 installed (which your OS X installation disk contains) and specifically point CMake at the X11 libraries. The CMake code for this is shown below:

include_directories(/usr/X11R6/include/)
link_directories(/usr/X11R6/lib)
SET(EXTRA_LIBS GL X11 GLU glut)
target_link_libraries(main ${EXTRA_LIBS})

When using the X11 libraries, you must also change the includes as the folder structure for X11 is different than that natively for OS X:

^?View Code CPP

#include 
#include 
#include 
#include 
#include 
#include

That is all. Not terribly complicated, but hopefully this saves you some time if you are doing development with CMake, OpenGL, or X11. Look for some new slightly more exciting posts soon.

Convert Quicktime Screencasts with FFmpeg

Alex — Wed, 28 Jul 2010 00:42:05 +0000

I was trying to convert a Quicktime screencast (saved as .mov) to a format my professor could more readily use. For those who don’t know, FFmpeg is an amazing tool with a wide range of applications, including converting between video formats and ripping audio from a video. Anyway, this took me a little to get quite right (and maintain output quality) so I thought I’d post it here both for others and a place to save it for myself. Although it looks really simple in hindsight:

ffmpeg -i screencast.mov -f avi -vcodec mpeg4 -sameq -ac 2 -ab 128k screencast.avi

It is necessary to specify a video codec because AVI can be used with multiple codecs. To maintain video quality use -sameq. When converting screencasts, it may also be useful to crop out parts of the screen since Quicktime only does full screen capture. For this, you can use the -croptop, -cropbottom, -cropright, and -cropleft arguments. Last, make sure the arguments come before the output file; otherwise they are not applied.

Maybe I will later do a more full post of the different ways I use FFmpeg. But for now, that is all.

Rankophilia and Rankophiliacs

Alex — Thu, 28 Jan 2010 03:24:26 +0000

For my CPS 182S class, we have an assignment which is a competition among groups of students (and the professor) to have the highest ranking page on Google for the terms rankophilia and rankophiliac. As such, I have created a page at rankophilia.dorm.duke.edu to be my group’s main page on Google. For now, there is not much interesting on there, and I am merely posting it here in an attempt to increase the PageRank. I am considering adding more interesting content and submitting it around online rather than just spamming. I will post updates (probably at least a few for links) as the contest goes on.

SQL Injection at Duke TechExpo 2009

Alex — Mon, 12 Oct 2009 19:56:07 +0000

I gave my first public talk today at Duke’s TechExpo 2009. I along with my coworker Artem Kazantsev discussed the risks of SQL Injection. The presentation gives a good overview of the capabilities of SQL injection along with how to prevent such vulnerabilities. I also gave a demo of performing a SQL injection attack on a vulnerable site during the talk. For any web programmers who aren’t familiar with SQL injection, take a look at the code for the demo to see exactly how and why it is vulnerable, along with how to fix these vulnerabilities.

SQL Injection Presentation

SQL Injection Demo

Additionally, earlier in the year I worked with Duke’s ITSO to write up examples of good coding practices to protect against a variety of web application security issues. This referenced is linked on Duke ITSO’s site here: http://www.security.duke.edu/ITSO_Web_Application_Security_Standard_v1.pdf

Drag and Drop off the Desktop in Duke Webfiles

Alex — Mon, 05 Oct 2009 23:07:39 +0000

While on break, I’ve been playing around with Mozilla’s File API and integrating it with Duke Webfiles, which I work on for OIT. This is only a proof of concept since the spec has not been completed and I only implemented it in the icon view of Webfiles. Regardless, I think it is pretty cool and makes the application much easier to use. Here is a screencast to see it in action:

To do this I used examples from here for the new File API and here for the AJAX upload. Obviously this could be expanded upon by implementing it in all three file views in Webfiles and by showing progress bars for each file. Additionally, there are some small bugs with uploading large files. However, if you are a Duke student and want to give it a try, follow the instructions below. Please note, this is a alpha version of the software, and you may run into some bugs when using it.

Make sure you are using Firefox 3.6 Alpha – Namoroka.
Go to our development version of Webfiles and log in.
After you are logged in, go here to turn on the new drag and drop feature.

Please, give it a try and let me know your thoughts. Thanks.

Hilbert Curve with the Canvas element

Alex — Thu, 01 Oct 2009 22:56:48 +0000

For my discrete math course (CPS 102) this semester, I had to create a space-filling curve for one of my homework assignments. I decided to take this as an opportunity to play with HTML5′s canvas element since I’ve yet to had a legitimate use for it in any programming yet. I think it came out decently well (and it’s kind of fun to play with), so I thought I’d post it. Here is a link to it on my Duke account http://duke.edu/~amb79/fillSpace.html Like I said, nothing huge but fun to program and cool to watch.

I am on fall break now, and will be spending the weekend at home. Hopefully I’ll do something cool while I’m home and will post if anything comes out good.

Ubiquity Scripts

Alex — Thu, 30 Jul 2009 07:17:58 +0000

After playing with the Jetpack API and having an increasing desire to procrastinate my Spanish homework, I decided to give the Ubiquity API a shot too and make a few small scripts just to make my life easier. The first extension I made was a script to do look ups of IP addresses and get more information about them. This is useful mainly if you are looking at raw logs from a web server. After realizing how easy it was to make these scripts, I made two more for bit.ly links which I frequently come across on Twitter. The first can get more info and stats about a link (the number of clicks) and easily send you to the bit.ly info page for that link. The second script can be used to quickly expand the links from their compressed bit.ly form to their original form. I know there are other scripts that can do this across an entire page, but felt I’d rather keep short links with a quick and easy way to find out what the link contains. If any of these sound interesting/useful or if you just want to see some simple examples of how to code Ubiquity extensions, you can check the scripts out here. I have also included screenshots for each of these scripts below.

Image Aliasing of Plane Propellers in Photos and Video

Alex — Fri, 24 Jul 2009 05:33:27 +0000

Recently, while flying between Durham and New York, I decided to take a picture of the propeller during take off. I don’t know what prompted to me to do this, but when I pointed my iPhone camera at the propeller out my window I noticed very odd pattens. I took multiple pictures throughout the flight with my iPhone, and in some cases at the same time took pictures/video with my Canon camera. To clarify the specs of the two cameras: I have an iPhone 3G (8 GB) and a Canon SD700 IS. As you will see in the pictures below, the iPhone’s picture simply makes no sense with the blades appearing to be disconnected vertical lines. The photo from the Canon seems reasonable, but as you will see in the video the propeller appears to be going fairly slowly, when in real life all I could see was a blur because of how fast it was moving.

Plane Propeller Photo from iPhone 3G

Canon SD700 IS Plane Propeller Photo

Update: here is a video taken from my iPhone 3G of the propeller.

This got me thinking about why the images looked the way they did. I assumed they were related to frame rate and as a result wondered if I could work backwards to find the speed of the propeller. When I got back to Duke, I talked it over with some of my friends. We discussed one theory that explained the slow spinning in the video from my Canon. I later found out is similar to the Wagon-wheel effect, and will go into more detail on this later. We also discussed possible distortions and other possible causes but couldn’t figure out exactly what was causing the odd pattern in the iPhone photo. Eventually, I decided to search around the internet and found that I was not the only one to notice this oddity. I also stumbled upon this great post explaining clearly and graphically why the iPhone photo looks the way it does. In short, most cameras save pixels from all parts of the lens at once, while the iPhone camera goes through the lens saving pixels linearly over time, similar to watching a scanner save the page of a book. (If anyone has an iPhone 3GS and can snap a picture and/or video of a propeller, please let me know. I’m very intrested to see if Apple’s upgraded camera still behaves this way. Please let me know if you find out.) The writer of the post also demonstrated this in a cool video made from a Matlab script:

Personally, I think this is really cool so I decided to play around with it some more. As I mentioned earlier, my friends and I had discussed the wagon-wheel effect or the stroboscopic effect, so I thought I’d modify his script to demonstrate it more clearly since the Wikipedia pages on the two topics both seemed a bit lacking. First, it is necessary to explain the general concept. The stroboscopic effect explains if you only see flashes or quick individual frames of a moving object at regular intervals you can get a distorted view of the motion, especially if the motion of the object that is being watched is cyclic or has a frequency. The relationship between the frequency of the flashes or frames and the frequency of the motion is what determines the perceived motion. The most common case of this is seeing a wheel which you know to be rolling forward, but it looks to be spinning backwards slowly. I modified the previous Matlab code to create a basic example of this with the propeller (download the code here). As you will see, the propeller on the left will spin counterclockwise at a moderate speed and every 8 frames the image on the right will update with a copy of the image on the left. This out of sync updating will make the propeller on the right appear to rotate clockwise.

Click the image to view the video

I also decided to show this more mathematically by plotting these movements in Mathematica. In the following examples I graph both the y-coordinate of the tip of the propeller and the angle that the blade has rotated in radians. In the graph of y the coordinate, there are three sinusoidal functions representing 3 propellers, each offset from the previous by 120 degrees (thus equally spaced). These lines and their colors correspond to the colored lines on the radian vs. time graph. The red lines mark a flash or frame and the dot on the line shows the top-most propeller. As you vary the spacing of the lines and thus change the frame rate, you can see the propeller will appear to stay still, then go backwards, then flip back and forth with no perceived motion, then go forwards, until it appears to stand still again. Below are pictures showing each of these stages, followed by a video fluidly showing these variations.

Here is the propeller appearing to stand still. This is due to the fact that the spacing of the frames is twice the period.

The graphs below show the propeller appearing to go backwards. Here we see that the frame rate is just below two periods of the propeller. The downward slope on the radian graph is a simple quick way to see the direction of the propeller rotation.

Propeller appearing to flip repeatedly:

This example shows the propeller appearing to rotate forwards. Again, the upwards slope of the points on the radian graph is an easy way to see the direction of rotation.

Last, here is the propeller appearing to stand still again. Unlike the first case of the propeller standing still, the spacing of the frames is not a multiple of the period. Rather, we see here that it is a multiple of 1/3 the period. It is only necessary that the spacing be a multiple of 1/3 the period because there are three blades and the blades are indistinguishable.

And finally, putting it all together:

The Mathematica code can be viewed here or downloaded here, and a printout of the entire Mathematica worksheet can be found here. Last, if one had a camera which could vary the frame rate just so slightly as to find two nearest frame rates to show the propeller standing still, the frequency of the propeller could be calculated as shown below.

As for the iPhone picture, a single image (and knowing the number of blades) is enough to roughly approximate the speed of the propeller as shown below.

However, just as a warning both of these are back of the envelope calculations and it is very possible I made a mistake (if so please let me know). That is all for now. Nothing ground breaking, but as the title suggests, it was a good chance for some mental masturbation, playing with Mathematica and Matlab.

Duke LDAP on the iPhone

Alex — Sun, 19 Jul 2009 23:11:41 +0000

I got an e-mail this morning from someone who saw my post on Twitter about using LDAP on the iPhone here at Duke. The person said they followed the tutorial but couldn’t quite get it to work. So I figured it may be useful to post a few quick instructions on setting it up. As the post on Twitter explains, the basic instructions for getting to adding an LDAP account can be viewed here and Duke’s LDAP server settings can be found here. Once you are set to add the LDAP account, simply set the server to ldap.duke.edu, no need for a username or password. Once you click next you will want to turn off SSL and change the Search settings for duke,edu to have a base value of “ou=People,dc=duke,dc=edu” (leave the scope at subtree). And that’s it. To use it, which turned out to be the issue for the person emailing me, go to write a new email and start to type in the name of the person to search. You should see a throbber show up at the top of your screen, showing that it is connecting to the server. There is a bit of a lag but it should eventually return the contacts for people by that name. Below are some pictures of the settings and the search. Let me know if you run into any issues.