This last week saw SIGGRAPH 2010 in Los Angeles, sunny California. It was there that I gave my first talk at a real conference. One request that I had not anticipated was for the slides from the talk, and so I post them here now.
Pending some red tape resolution, I hope to post the live-working demos soon. Until then, I hope that this video from the original conference submission will whet your appetite!
For those particularly curious, feel free to contact me or refer to the abstract.
I’ve been working with WebKit a lot lately. Specifically, WebGL. It’s fantastic, and it has the potential to change a lot of important applications, but working with nightly builds is… well, frustrating.
I’ve been using a revision released in December. Some later revisions have weird behaviors and draw pixelated, but I’ve finally come across a problem with r52426 that I just can’t circumvent – floating-point textures. They just don’t seem to work properly. I had noticed the bug before, but it wasn’t absolutely crucial before. Rather, the real bug is that you can’t initialize floating-point textures from the JavaScript side.
They’ve fixed this in later versions, but many of these that have this bug fixed also have a problem with gl.viewport, which is pretty mission-critical. So now I’m sifting through the changelog, hoping to find a release somewhere in the middle that isn’t completely broken.
Update: Victory! If you’re going to be developing WebGL stuff on Mac, I’d recommend WebKit r53036. It seems to have everything I need (so far) fixed.
I’m working with WebGL and as such, I’m discovering some quirks about OpenGL ES 2.0. I have been using display lists as long as I’ve been using OpenGL, but WebGL doesn’t have support for them. So, I’m buckled down and familiarized myself with vertex buffer objects, the (perhaps better) alternative.
At any rate, I need to render a regular 2D grid, and as it doesn’t support quads, either, I was forced to use triangles. In the interest of getting things running, I just provided a wasteful list of discrete triangles. This is wasteful because it references many more vertices than necessary – I ended up declaring 
vertices when in reality there are only 
unique vertices. This worked fine, until I wanted to increase the resolution. It turns out, JavaScript doesn’t like large arrays.
That’s fair, because the implementation was pretty wasteful. A triangle strip was the best choice anyway. A triangle strip is a highly compact form of representing a mesh. For 
triangles, it requires only 
vertices defined. Well, that’s roughly true. We’ll see another case in a minute. It’s useful when many triangles share vertices, and perhaps I’ll let Wikipedia’s explanation stand.
It wasn’t immediately obvious how to define a grid out of a single triangle strip and so I got out a pen and paper. I kept in mind a neat trick: if in a triangle strip, you need to skip the use of a vertex, a vertex can be introduced twice in a row. That is, if I need triangles (6, 3, 7) and (7, 11, 6) in that order, you can just make your strip with 6, 3, 7, 7, 11, 6. You can think of it as if there are two triangles created (3, 7, 7) and (7, 7, 11), but they have no area and a degenerate case – a line. Furthermore, these lines lie on triangles already defined.
Perhaps the obvious choice doesn’t yield any results, and in fact in this layout, it can’t be easily done (you have to have vertices appear three times in a row):
This is a bad idea for a topology if you want to use a single triangle strip.
To better convince yourself, try to come up with a good way to put this in a triangle strip. I’ll make the case that it is pretty difficult with a claim from graph theory. In order for a triangle mesh to be turned into a triangle strip, each consecutive triangle must share an edge. We can then think of the mesh as a connectivity graph (the dual of the mesh) and then the problem will emerge more clearly:
The dual graph of the bad idea.
To make the triangle strip “nice,” we ought to be able to visit each node once and exactly once. There’s good and bad news in this – it’s the same problem as finding a Hamlitonian path which is NP complete. The good news is that if we find a solution to our small problem, we’ve found a solution to all such grids (with arbitrarily many triangles). Note that we don’t need an Eulerian path.
If you stare long enough at the above connectivity graph, you’ll hopefully convince yourself that there’s no way to traverse it visiting each node once and exactly once. Go ahead and try – it’s pretty infuriating.
Looking at how we would traverse one strip (triangles a, b, c, d, e and f) actually gives us a clue. A triangular strip for that case would be 0, 4, 1, 5, 2, 6, 3, 7, and happiness ensues and we should move onto the next row. Unfortunately, in the context of this new row, we’re starting in a different place (topologically) than we started with the first strip. Vertex 0 has two connected neighbors in its row – 1 and 4. Vertex 7 has three in its row: 6, 10 and 11. It turns out we can change up the topology to remedy this simply:
A much better topology for drawing this with a single triangle strip.
We can also see that this is a much better solution by looking at this new graph’s dual:
The dual of the better topological choice.
You can probably easily find a Hamlitonian path in this case. But this still leaves us with how to determine the vertex orderings. We decided that the first row ought to be 0, 4, 1, 5, 2, 6, 3, 7, but moving on from there we need a bit of “glue” to move onto the next row. We insert 7 again, and then continue on from there: 7, 11, 6, 10, 5, 9, 4, 8. A bit more glue for the third row: 8, 12, 9, 13, 10, 14, 11, and 15:
An alternative representation of the vertex ordering
Looking at the indices from the first row, starting at 0, we can get the next index by alternately adding 4 and then subtracting 3. On the next row, we’ll continue to add 4, but then alternately subtract 5. The 4 is derived as being the number of vertices on a side (if there are divisions, then there are 
vertices), and the 3 and 5 are explained by the fact that we need to change columns in the mesh, by one step at a time.
An clean implementation is not trivial, but not extremely difficult. In terms of results, I can fit more than 4 times as many vertices into the mesh than with a per-triangle implementation. And to boot, it has cut the work of the vertex shader a great deal.
I’ve mentioned WebGL before, and I think it could be very important. There is a competitor from Google, but like OpenGL and OpenCL, this API is managed by the Khronos Group and that fact appeals to me. Perhaps it’s that I’ve used it fairly extensively, but I really like OpenGL. Despite its quirks, it’s quite powerful.
The big “get” is that it gives programmers access to hardware-accelerated graphics from directly within the browser. There’s a lot of interest in this arena for game development as it would obviate much of the need for separate distributions based on operating system. (Skip to the end for more of an opinion on this subject.)
As such, I’ve been working with WebGL as opposed to the Google-proposed O3D. (I have every intention to explore O3D, time permitting, as there are some jagged edges to the current specification.) The result of this recent toil is a budding WebGL implementation of my OpenGLot project. It’s still in early stages, but in the coming weeks, it should develop even further. To whet appetites, I have a few pictures.
A scalar field, my persistent test function.
A 3D surface, again one of my usual test functions.
I seriously doubt that WebGL will every match the performance of OpenGL. Even though JavaScript interpreters are getting faster at a somewhat alarming rate, they won’t match the speed of C or C++. That said, if one can appropriately offload work onto the GPU, it won’t matter as much, but there will always be that overhead.
It won’t so much be a matter of having the same performance, but enough performance. If a person can go to a single webpage and get 60 frames per second performance in a game or tool without having to install software, that’s tremendous. Currently I’ve been getting between 60 and 90 frames per second with WebGLot, and I’m sure I can keep that number up as more features are added.
My hope is that this will be a tool and library that has a wide-enough feature set by the time WebGL is widely adopted that becomes often-used. But that’s just ego. The purer motivation is that if you’re a math teacher, and you want to have interactive demonstrations of Newton’s method, or parametric surfaces, or even flow fields, you can write an application in 20 minutes that does all the heavy lifting of graphing it for you. As long as you can describe the mathematical primitives, you should be able to render it. Of course there will be a general-purpose grapher available for any calculus student who’s having trouble visualizing this or that, too. Or a resourceful PDE student who need to solve his homework (the GPU-based PDE solver will take a little bit more time, but it’s very nearly complete).
In short, the strength of WebGL is that is has respectable performance, and in a year’s time, half the browsers (well maybe not half) on computers will support it, giving the average internet-user access to a wealth of media.
In the far-off year of 2009, there will be a series of tubes that connects people over great distances at tremendous speeds. You’ll interact with it with a browser – a veritable portal to the world. And it will be able to render 3D graphics efficiently.
WebGL is the future of the internet. I’ve been hoping for something like this to come out for a while, and in Firefox’s latest nightly builds, it’s included. You should read more about it straight from the horse’s mouth, but this is going to be amazing.
I love OpenGL, and to have a framework from which to call these commands I know and love for the web will be fantastic. No need to worry about system requirements beyond whether or not WebKit runs on your computer… no need to download the latest versions of some piece of software…