Eric Butler’s Weblog

Hm… It’s been quite a while since my last post. School drains me of my time more than I expect…

Anyway, even though it’s already halfway through, I thought I might post about what I’m doing this summer. I decided against taking an internship in the software industry this year. Not because I didn’t enjoy it (working for Mozilla was amazing), but because I wanted to explore some other possible futures, specifically graduate school.

To that end, I decided to work on campus for a professor doing something reserachy this summer. At the same time, I really wanted to work on game development since that’s one of my big passions. So, I decided to do both: I’m working on a research videogame project, Foldit.

Solve Puzzles for Science!

You can read more details about the project here, but here’s a short version. Figuring out the most stable shape of a particular protein is hard. Really hard. There exist algorithms to find it, but the search space is enormous. It’s just a optimization problem, but a rather difficult one. But hey, humans are good at 3D spatial reasoning. Why not enlist their help in solving this problem? And, while we’re at it, why not disguise it as a game?

Thus Foldit was created. It presents the user with the problem of trying to fold a given protein to maximize their score, which equates to minimizing the energy. A server is used to store the results of the players, which can hopefully be used to improve search algorithms. Or a human might just even find the stable shape for a really important protein herself.

The project began at the University of Washington as a collaboration between the CS and Biochemistry departments. One of the creators, Dr. Adrien Treuille, is now a faculty member at Carnegie Mellon, and he brought the project with him. There a handful of students at CMU working on the project now, myself included.

What I’m Doing for the Project

My primary task is trying to improve the quality and performance of the rendering engine. Currently, some of the puzzles display very slowly on many computers, and some of the visualization has undesirable artifacts. Basically I’m rewriting as much of the 3D rendering engine as I want, which is a pretty sweet job. It’s all done in C++ and OpenGL, which means I’ll be getting much more familiar with OGL than I have ever before. I’ve never worked on or written such a large 3D engine, so I’m already learning a whole lot. My changes have already caused some big gains in a few areas. I may talk about in more detail in later posts.

So that’s what I up to, in case anyone was curious. I’m going to try to post more frequently this summer than I have been (namely, never). We’ll see if I can keep that up… Anyway, go check out Foldit!

Images courtesy of foldit’s website.

Friday marked the deadline of the first ever round of GCS competitions. One of the other things Andrew Fox and I wanted to try this year was small game competitions in addition to the normal semester-long projects. We messed a lot of things up with this run (as expected), but it was a surprising success, especially our game competition. You can check out the entries (and vote on the results) on our forums. We’ll be giving out prizes, too, like a free copy of Spore.

I entered a submission into both the game design and music competitions. The game compo’s theme was a one-button game, and the music compo’s theme was “airship cruising.” So being the lazy individual I am, I combined the two and wrote a little Game Maker game called Sky Sailing. The game music causes problems on some systems, so if it doesn’t run, try the one without music.

Download Game: Windows EXE, Windows EXE without music
Download Song: MP3, OGG

I was surprisingly pleased by how these turned out. The game mechanic involves using the space bar to control your ship and smash other enemies while avoiding mines. Tapping the space bar cause you to gain altitude while holding the space bar charges a “blast shot” that launches you forward and destroys enemies.

My personal goal was to explore the limits of how much information a game can extract from the player in a single button. Just how much complexity can you extract from a button while maintaining some sense of simplicity and usablitiy. I broke 2D movement down by distingusihing two parts of a button presses: how long you hold a button and how often you press the button. It gives you surprising field of movement all over the playing field, though the controls are still sluggish and clunky and could stand for more tuning.

Anyway, enjoy! And go check out the other entries. There were some really amazing ones.

Today marks the “official” kick-off of fall projects for Game Creation Society. They have one semester in which to develop and produce a game, which will then be released with much hurrah on the last day of classes. I’m doing one myself (which I’ll talk about someday soon) along with 8 other projects, all with distinctive goals and game designs. I’m pretty psyched to see what will happen this year.

This year I instigated and tested a radical change in the traditional pitch process which games undergo. The old one was rather terrible in my opinion. Students aspiring to be project leaders would craft an idea and then have an individual meeting with the development director to get the green light. Then they’d give a 10-minute presentation to the club pitching their project and begging for members.

This is wrong for a lot of reasons, the biggest of which, from a production standpoint, is that you can’t really determine if the project will be successful and give it approval before the project recruits members. You have no idea what interest will be like; they may attract no one and be unable to generate the resources necessary. Additionally, ideas are less refined when they only come from one person rather than a group. The design will be bound to change once the other group members get a hold of it. Basically, you can’t possibly tell whether or not a project is on sure footing nor provide useful design advice until the team has formed.

So instead this year we reversed it. At last week’s meeting I threw everyone in a room together and told them to get pitching and discussing. Andrew Fox called it a “concept fair.” So prospective leaders came in with ideas, mock ups, demos, (and in one case a tri-fold board with little origami cranes decorating it) and started attracting potential members and receiving feedback on their ideas. Only afterwards, once their ideas have been refined from feedback and they have a few more people on board the project, do we carry out the traditional pitch, in which they sit down with upper management (i.e. me) and convince the club to make them an official project, while the development director provides design advice, makes sure they have a legitimate schedule for production, and covers logistics.

And I think it was very successful, on the whole. Well, at least the general idea. The execution this year was kind of shoddy, as I’ve heard in feedback and observed myself. We were rather unprepared and were in a not at all appropriate room. We should choose a better location, preferably one with tables, much like a job fair. This would help with the other problem, which was that people couldn’t really tell who was pitching something. We should give each person pitching a minute or two on the floor to give a brief introduction.

We botched the description at the first meeting little, so I think people assumed you needed to be extremely prepared. They thought you needed to come with prototypes and boards and demos and detailed docs. But that’s not how I had envisioned the concept fair. To me, all you really need are ideas. It was supposed to be people getting together and sharing ideas, and then those ideas would morph and form into cool game ideas and some groups would form from them. This did happen, to some extent. And, of course, for those with more concrete plans, it’s a place to show off what they have and to get feedback and recruit people to their project.

So, next year, we need to do a better job getting a good room. We need to better explain that this is more about sharing ideas that existing work, and we should do a better job letting members know who’s planning what, both by utilizing the forums and site more effectively and by giving people a bit of floor time to introduce themselves. If you have any feedback, please go make a comment on how we can improve.

Why I Really Went into Computer Science

One will have noticed that Mozilla posts have rather died off over the past months. The cause behind this is that of school starting up as my internship ended. So Mozilla posts will periodically continue (the shadows patch is ready to land, btw), but the start of the new school year seems an appropriate time to begin talking about one of my major hobbies: game development.

Video games were, without a doubt, the reason I first became interested in computer science. As a kid, I had always imagined creating worlds, be it on paper, with blocks and toys, through music, or only in my mind. Amazed by the games I played as a child, I dreamed of being able to create some of my own, but it somehow never occurred to me that I should do something about it. However, during my senior year of high school, I finally decided that I didn’t want my dreams to be merely dreams, and taught myself programming so I could start writing games. Within 2 years I found myself to be a CS major spending nearly all his free time designing, programming, and making games. And I haven’t really looked back since.

Carnegie Mellon’s GCS

At Carnegie Mellon University, I help run a little game development club called the Game Creation Society. It’s purpose is rather straight forward: to provide an environment in which students can get together and have fun learning to develop video games. People get together in groups and develop a game over the course of a semester.

The organization is not related to the curriculum in any way: everyone who participates is doing so on a volunteer basis, entirely for the desire to make games. Some do it to build experience for the potential of going into the industry, and some do it to practice skills in the many areas involved with game development. Many others, like myself, do it simply because making games is damned fun.

GCS has so far been an invaluable experience for me. My skills in all areas (software engineering, sound design, art, game design, project management, etc.) have greatly improved from my experience on projects. Very few classes provide the experience of working with a sizable group on a sizable product and seeing that product all the way through the development cycle from brainstorming to release. I’ve learned and developed a lot, and I’m very grateful for what I’ve gotten out of the club. Also, and most importantly, it’s been a blast. I really can’t emphasize how enjoyable game making is.

All of this is (among other things) why I wanted to give back to GCS, and took on the position of Director of Development, which essentially entails managing all the active projects, and ensuring to the best of my abilities that everyone has the resources they need to learn and create awesome games, and have fun doing so. This post served as a little introduction to the organization and what’s it’s all about. In the near future I will talk more about games, both about personal projects on which I am working as well as my experiences running a game development club.

The patch for the last of the major outstanding bugs with the WHATWG Canvas text API landed in time for a nearly spec compliant implementation to make it into Firefox 3.1 Alpha 1. I am pleased to say that Canvas now supports right-to-left text and bidirectional text resolution on its text drawing functions.

Canvas has undergone and will be undergoing some other changes, as well. I went through and cleaned up a lot of old code so that, among other things, Canvas uses Mozilla’s Thebes API instead of directly calling into Cairo. Philip Taylor has created a new set of unit tests for Canvas which are more extensive than before. Additionally, a patch has been sitting around for a while that adds shadow support to Canvas, which I hope to push to completion soon.

I have reached the end of an over 3-week exploration into the possibility of gaining a nominal speed improvement in Firefox page load times on Linux. Vlad asked me to look into using the Xlib Shared Memory Extension (XShm) for image rendering. I have created an extension to Cairo that can use XShm and plugged that into Firefox’s image library, but now that it is working, the performance results are mixed and I am unsure what to do with it.

Let me explain exactly for what XShm would be useful in Firefox: Faster rendering of images while they are decoding. Some readers of my last post seemed to be under the impression that static images were being drawn using XPutImage and the plan was to use XShmPutImage instead, which given the way I wrote the article (namely, badly), I can’t really blame them. Let me rectify.

In Firefox, while images are being decoded, the partial image is constantly being drawn to the screen. Once the image is complete, it is of course optimized into a pixmap on the server, but until that time, it’s constantly being sent to the server via XPutImage. This is where XShm could conceivably help.

However, there is one hitch in this process. Due to the asynchronous nature of X, setting up the XShm image can fail under a certain chain of events, so the application has to synchronize with X (by calling XSync) before destroying the image. This throws a major wrench in application speed if these images are created all the time.

When I ran Talos on a Firefox that used XShm for images, timings were all over the place. Some web pages showed a noticeable improvement in performance, while others showed a noticeable regression in performance. Fiddling with the code, I was able to get it to the point where there was a sizable overall performance improvement on my machine, but I really can’t be sure that will translate into the same thing on most Linux machines.

So I am now at the quandary of deciding what the heck to do with all this work. It seems so close to being something very useful, yet I can’t seem to draw consistent results out of it. There would most likely be regressions across the board for certain machines or web sites. I suppose I’ll let it sit around for a while until I decide how I can improve it.

Update: As mentioned in a comment, XShm isn’t always available, for any number of reasons (most usually a remote X server). In this case the program would fall back to the normal method of images. This is why I choose to implement the XShm as a separate surface. The surface creation will fail if XShm isn’t available,  so the application can fallback to a more suitable surface. (And yes, the fact that it’s faster is bloody obvious; I’m as surprised as anyone that Cairo didn’t use it already. )

Maybe I’m just naive, but designing a graphics API such that all image data had to be sent over a socket to another process every time the image needed to be drawn seems like complete idiocy. Unfortunately, that is precisely what the X Window System forces a program to do, and exactly what Cairo does when drawing images in Linux—a full copy of the image data, sent to another process no less, every time it is drawn. One would think there would be some room for improvement.

Unsurprisingly, others felt the same way about X, and decided to write an extension, Xlib Shm or XShm for short, that allows images to be placed in a shared memory segment from which the X server reads which allows the program to avoid the memory copy. GTK already makes use of the XShm extension, and it seems like a good idea to see if Gecko couldn’t do the same.

An Xlib Shm Surface

There have been previous talks about putting such an extension into Cairo, but none of them have gone farther than a proposed patch. So over the past couple weeks I’ve looked into exploring XShm and Cairo to see whether a clean API can be made for Cairo and to measure just how real the potential speed improvements are.

I implemented a new back end surface for Cairo, cairo_xlib_shm_surface_t. It is designed with one specific use case in mind: the fast rendering of images loaded from files. Generally, one would create the XShm surface, and decode the image directly into the surface, then paint the surface to the screen. It is minimally invasive on the Xlib surface back end, adding only one if block into a single function, and so should have no impact on performance when compiled into Cairo but not used.

The patch was created relative to the git repository for Cairo, taken out on June 10, 2008. You can find the patch at http://www.ericbutler.net/demos/mozilla/2008/cairo-xshm-test/xshm.diff. Configure with the flag --enable-xlib-shm to build it, and include cairo-xlib-shm.h for the functions to create an XShm surface.

Testing

A C program was used to test the new backend for speed. The test compared rendering speeds of painting an image surface on an Xlib surface (the current method of rendering images in Firefox) to painting an Xlib Shm surface on an Xlib surface. The test allocates space for some number of images and fills them all with data. It then draws all the images to the screen, syncs with the X server to make sure drawing is complete, and lastly destroys all the images.

The test was run with images of various sizes, with alpha blending and without. The tests were run on an HP nc8430 laptop with an ATI card running Ubuntu 8.04 using the fglrx drivers. Two different items were measured:

1. The total time to create, draw, and destroy all the images.
2. Only the time to draw the images.

Results

Each chart indicates the size of the image, video driver used, measurement taken, and bit depth. The x-axis represents the number of images rendered each test, and the y-axis is the total time of the operation in milliseconds, averaged over 100 tests. The “image” category is a Cairo image surface, and “xshm” is my Cairo Xlib Shm surface. Only a small sampling is shown here, a page with more results can be found at http://www.ericbutler.net/demos/mozilla/2008/cairo-xshm-test/results.html.

Analysis

There are a few observations that can be made instantly from the data:

• Drawing with XShm is a lot faster. The average speed of the drawing with XShm for any image size was somewhere between 40 and 70 percent the speed of a standard image, which is a pretty good improvement. Image-heavy sites could potentially see a noticeable decrease in page draw time.
• Creating an XShm surface costs more than an image surface. There appears to be a constant (or at least sub-linear) but noticeable cost to creating a shared memory segment. The total time results for the small image are actually quite worse for XShm, which seems to indicate that there is some lower bound where the cost of setting up the shared memory segment outweighs the benefits gained from the draw call. However, even for images as small as 200×200, even if the image is only drawn once, XShm still provides a net gain in performance. And, of course, the more an image is drawn per creation, the less this overhead matters.

So it seems that XShm is worth pursuing. Further research will need to be done to see how XShm performs with other video drivers such as vesa. I will be exploring how to use this surface in Thebes and image library. Hopefully this can result in a speedup for Firefox on Linux and any and some other Cairo applications that use the Xlib backend.

X11 logo image taken from http://commons.wikimedia.org/wiki/Image:X11.svg.

I am currently employed by the Mozilla Corporation as a summer intern. I work primarily on Gecko, the layout engine. I started at the end of May 2008, and so far it’s been a blast. I am working with Vlad Vukićević as my mentor on graphics work for the Mozilla platform.

My first project was to hack on the HTML canvas element, a new edition in the upcoming HTML 5 specification. Firefox has a Mozilla-specific API, written by Rob Arnold, to add much-needed text rendering capabilities to canvas for Firefox 3. But since then the WHATWG have proposed a text API, and so I implemented much of that specification.

The spec is missing some of the cooler features that the moz-specific one has (namely text along a path) but it has a few other useful things such as the ability to anchor the text by any alignement or baseline as well as having support for rtl fonts. And, of course, the Mozilla-specific one is still around.

Here is the rendering of a sample I made, showing how the anchor points and transformation matrices can be used to generate a bar graph dynamically on the client side. Click on the image to see the actual html file and source code. This was my first time writing javascript, so my apologies for any oddities in the code. Note that this will only render correctly with one of the more recent nightlies.

Another awesome demo that uses canvas text rendering is Paul O’Shannessy’s LOLcanvas, a bookmarklet that takes Flickr pages and LOLifiies them.

So there’s a little description of some of the things I have done so far. It looks like I’m really going to enjoy the rest of my summer here, and I look forward to the other projects on which I will get to work.

Hello and welcome to my weblog. Succumbing to peer and employer pressure, I have decided to start a blog on which to talk about my work, specifically programming and game development. See you next post!