Your graphics puzzle for the day

Just the other day, I wrote a trivial geometry shader to tesselate cubic 2D Bezier curves on the fly, so we get nice curved edges for free. Remembering that the geometry shader sits between the vertex shader and the fragment shader, and its purpose is to create new geometry on the fly, the code looked like this (my apologies to the direct threedeese readers – I only speak OpenGL):

vec4 pp[4] = ... // control points
for (int i=0; i<=10; ++i) {
  float u = i / 10.0f // interpolation control
  float omu = 1.0f-u;
  vec4 spline_p = pp[0] * omu * omu * omu +
                  pp[1] * omu * omu   * u +
                  pp[2] * omu   * u   * u +
                  pp[3] * u   * u   * u;
  EmitVertex();
}

This worked nicely, generated really good looking splines, and was fast. Then I wanted to backport this to the CPU in case the user doesn’t have geometry shaders. We could be using OpenGL evaluators, but it seemed simple enough, right? Like this:

float pp[4][2] = // control points
for (int i=0; i<=10; ++i) {
  float u = i / 10.0f // interpolation control
  float omu = 1.0f-u;
  float spline_p[2] = {
    pp[0][0] * omu * omu * omu +
    pp[1][0] * omu * omu * u +
    pp[2][0] * omu * u   * u +
    pp[3][0] * u   * u   * u,
    pp[0][1] * omu * omu * omu +
    pp[1][1] * omu * omu * u +
    pp[2][1] * omu * u   * u +
    pp[3][1] * u   * u   * u}
  glVertex2fv(spline_p);
}

No matter what I tried, this wouldn’t work – the lines come out garbled. The endpoints are in the right places, but the interior vertices tend to bend towards a common point. The bug is fairly obvious: the second and third cubic Bernstein polynomials are wrong (I was missing a factor of 3 there).

Now for the puzzle: why did the lines look right on the geometry shader?

Advertisements

The Euler characteristic of product spaces

The Euler characteristic is a nifty function that pops up all over the place in math and geometry, and has all kinds of neat properties. It gives any topological space (think triangle meshes and simplicial complexes, their n-dimensional friends) an integer, and, more importantly, it is a topological invariant: if two spaces can be bent into one another, then they will have the same Euler characteristic. The traditional formula for the Euler characteristic is an alternating sum of simplices, so for a triangle mesh M, \chi(M) = V - E + F. If you have tetrahedra, pentatopes, etc. in your mesh, they would just keep alternating signs. The Euler characteristic kind of looks like the cardinality of a set. First, it obeys the straightforward property that \chi(A \cup B) = \chi(A) + \chi(B) - \chi(A \cap B) (keeping the intuition of triangle meshes: simply count up the simplices).

Amazingly, it also shares the following property of set cardinality: \chi(A \times B) = \chi(A) \chi(B). This formula makes sense for finite sets (using the cartesian product), but is sort of crazy for more general spaces because it’s easy to come up with spaces of negative Euler characteristic. If you dig up the proofs for this, however, they tend to be a lot more complicated and give very little intuition. So here’s a simple proof that works for cw-complexes. CW complexes are sort of like simplicial complexes, but we let things like “4-sided triangles” exist. We define the “d-simplices” (they’re actually called d-cells) by saying that 1) points are just like 0-d simplices and 2) n-d cells are bent “hypercubes of n dimensions” that must have a union of (n-1)-d cells as their boundaries.

For CW complexes, the Euler characteristic is computed by an alternating sum of d-cells in the same way as for simplicial complexes. No big surprise, since simplicial complexes are CW complexes. In addition, products of CW complexes are much easier to think about than products of simplicial complexes. For example, consider two spaces A and B each consisting of a single edge and two vertices. The product AxB should be, intuitively, a “square” with 4 vertices, 4 edges, and an internal face. A simplicial complex can only have 2-dimensional triangles, and so the calculation becomes a little more complicated.

Now let’s raise the abstraction level just a little bit. Instead of thinking about the Euler characteristic directly as an alternating sum, we will think of it as an evaluation of a specially crafted polynomial computed from the space. This polynomial is really pretty idiotic: for the case of the spaces A and B above, the polynomial will be P(A) = P(B) = 2 + 1.d, that is, the degree of the monomial represents the dimension, and the coefficient represents the number of cells of that dimension. The Euler characteristic, then, is found by simply evaluating this polynomial at value d=-1.

Now for the cool part. Look at the polynomial P(A \times B) = 4 + 4d + d^2. If you think about how to create the product space, you will see that you get one (a+b)-dimensional cell for every a-dimensional cell in A and every b-dimensional cell in B. The simplest way to express this is as a product between the two polynomials! So P(A \times B) = P(A) P(B), and since I hopefully convinced you that the Euler characteristic is obviously just an evaluation of P, it is “obvious” that \chi(A \times B) = \chi(A)\chi(B). So the “magic” comes from the rule used to create the product space. Really neat.

(Props to Jacob for giving me the original idea for this)

2-adic integers are awesome

Over at A Neighborhood of Infinity, Dan Piponi has a post about a little bit of magic that happens when you ask gcc to do a division by 7.

This would have nothing to do with visualization aside from the realization I had in the shower, just the other day, that I believe the right way to pick good numbers for an axis scale is to think about the problem in the p-adic sense. “Small”, in this case, means pretty much exactly “close to a round number”. The usual descriptions of the algorithms (at least as I remember them!) for coming up with a good set of axis markings are pretty nasty; maybe p-adic numbers can help.

Fun with my iPad

I’ve had it for a week now. There are many iPad reviews, but this one is mine.

Screen, web browsing, reading

The contrast on the screen is much better than I expected it to be, and if you’re indoors, pictures look better on the iPad than they do on decent 8″x10″ prints. Reading text is also fine, and I have mostly been using it for that. Browsing the web is perfectly fine, and there’s something strangely pleasant about scrolling down a webpage by “grabbing” the page itself. It’s hard to describe it, because the same type of interaction was there with the iPhone, but the iPad makes it feel qualitatively different. I suspect it’s a combination of responsiveness and physical display size. Apple marketing catchphrases are at times fairly idiotic, but interacting with the iPad is really a different experience compared to the iPhone. The one letdown about reading on the iPad is that the PDF rendering does not use LCD-aware hinting a la ClearType (and whatever OS X has). This means your fonts will be slightly blurrier than you might be used to, although the increased pixel density (~150DPI vs ~100DPI for large LCD screens nowadays) means you might not notice it.

Watching movies on iPad works fine (I watched Fargo for the first time on it), and the Netflix app is incredibly cool (all the streaming videos are available). However, if you’re annoyed by letterboxing or cropping, remember that the screen is 4:3. The NPR, BBC and New York Times apps have become my main news source, which is nice, because they actually employ people interested in journalism. We now only tune in for Jeopardy (that’s right, I’m a nerd): together with Netflix, it means I’ll be canceling my cable TV subscription.

Keyboard

The on-screen keyboards for the two orientations feel completely differently from each other, much in the same way that the iPhone keyboards do. The vertical keyboard on the iPad is good enough for thumbing, but the horizontal keyboard is simply too large. However, after having a couple of weeks of practice, I can now mostly touch-type on the horizontal keyboard. I suspect that in a couple of months I will be typing at a serviceable rate. However, typing on a real keyboard is much nicer, and I have bought the keyboard dock. There’s no way I could use the onscreen keyboard to write this blog post, for example.

PDF Annotation: the killer app for nerds

Even before the iPad was announced, I had been looking for a way of keeping track of all the PDFs I print and annotate. A tablet of some sort seemed like a great fit: I could carry many PDFs with me, annotate them directly on the screen, and then save the resulting files in a safe, searchable place, so (say) I never lose a paper I reviewed again (making the inevitable second round of reviews much more convenient).

Originally, I had planned to write my own iPad PDF annotation software, and eventually I might come around to doing that. However, I need to read papers right now, and iAnnotate exists right now (and it only costs $9.99 or so). iAnnotate has a quirky user interface, but when you get past that, it is a serviceable, fast PDF reader in which you can add your own notes, highlight pieces of text (works well on the LaTeX PDF outputs I tried, but some people have had some issues), scribble comments, etc. Right now, the only way to get files out of iAnnotate is via their (free as in beer) Aji Reader Service, available for Macs and Windows. My current setup for automatically saving the annotated files in the right place is a combination of Aji Reader Service, Dropbox, and some homebrew hacks with inotify. Not pretty, but functional (email me if you’re interested)

Multitasking

My only use case for multitask has always been Pandora, and this continues to be the case. However, most people will want to use instant messaging while they browse the web and listen to Pandora, so I can see it annoying them. Does not bug me much.

Keynote

I am a big fan of the Desktop version of Keynote, Apple’s presentation software. I have not yet played around with the iPad version too much, but I have started to create a talk on it to see how far I can get. It is fairly painful to not have easy access to arbitrary pieces of LaTeX via LaTeXIt, so I’m not sure how much use this will end up getting. Getting files in and out of Keynote for iPad is also ridiculously dumb and complicated – it needs serious fixing. All iPad apps in general have this insular feel (which is part of the reason for the above dropbox/inotify hacks). If this annoys you, stay away from iPad 1.0.

Overall

So, is it ultimately worth $630? Probably not for everyone. I would be willing to pay $1000 for a tablet with integrated decent PDF annotation and management, but not everyone would. If you read a couple of papers every day, though, I cannot recommend it strongly enough. I have tried reading research papers on the Kindle DX – it’s just not as good. And have I mentioned plants vs zombies?

Ubuntu 10.04 beta 2, NVIDIA, x86_64

Are you testing Ubuntu’s latest beta on a 64-bit machine with an NVIDIA video card? Chances are you’ve hit the bug where the proprietary drivers won’t install correctly. It turns out that the nouveau kernel module steals the nvidia device, which in turns prevents nvidia.so from loading successfully, which makes the installer think the whole process failed (even though it didn’t, aside from actually loading the module). So you need to add nouveau and vga16fb to your kernel module blacklist configuration file, as described here.

No longer a mountain blog

Someone should write an article here every once in a while.

Three months, three submissions. I figure I should change that header to something closer to the vistas around here, so there you have it. I have been with AT&T for more than six months, after all (wow). According to the baby websites, I should have doubled my baby weight, and have discovered myself in the mirror. Supposedly I should be happy talking anytime now. Personally, I’m blaming the lack of happy talk on the Vis deadline (I hope all your submissions went well!)

If you haven’t yet done so, you should read Robert’s spot-on post on the visualization cargo cult. If we don’t define what we mean by effective visualizations, someone else will. We won’t like the result.

The cost of a sample

Over at “Please scoop me”, Jonathan Chang analyses the optimal number of samples one should use to estimate an expectation, when you assume that obtaining samples incurs cost.

Someone should write a paper looking at the implications of this type of analysis for distribution ray tracing and Metropolis light transport.