Default OpenGL bilinear sampling on high-contrast edges

Using a shader to manually do the sampling in a linear color space

I recently ran into someone who was frustrated by the amount of stair-stepping that appeared along the edge of the fonts she was rendering in OpenGL. This reminded me of some of the hard-won lessons our team at Apple discovered trying to use GPUs for professional content creation, so I had to throw together a demonstration of one of the little-known tricks to improving your resampling quality. This one works especially well on high-frequency textures, like font letters with sharp edges.

All your image data is stored as color values between 0 and 255. The hard part to wrap your head around is that these don’t correspond well to the actual number of photons that will be output for that color by your monitor. Because the human eye evolved to see panthers lurking in the undergrowth, we’re a lot more sensitive to small changes in dark colors. Because we need to pack in as much detail as possible into those 256 slots, most of those values are predominantly allocated to the dark end of the scale. This is done using a gamma curve, where the physical measurement of the light’s brightness (produced from a camera CCD array for example) is put through a function to map it onto the output values written into the image file.

It took me a long time to wrap my head around gamma, it’s a very slippery concept, and if you really want to dig into it I recommend Charle’s Poynton’s FAQ to learn more. The main thing you need to understand for what follows to make sense is that a grey value of 128 isn’t half as bright as 255, it’s only a quarter as bright. Why does this matter? Because the bilinear filtering hardware that’s used for texture mapping just averages all the values together. This means that a pixel sitting on the edge of a completely white (255) pixel, and a completely black (0) pixel ends up with a value of 128. This makes it appears a lot darker than it should, and this bias greatly increases the effect of stair-stepping.

Luckily with modern hardware it’s possible to bypass the default bilinear sampling and write your own in a pixel shader. This means you can convert the input color values into something closer to the physical measurements, do the averaging calculations and then convert them back to gamma space for output. To be totally correct you’d need to use an API like ColorSync to handle that conversion, using the details of your particular monitor, but that’s too heavy-weight for a simple shader. As it happens doing a simple square root (on the normalized 0.0 to 1.0 rather than 0 to 256 values) gets you very close to the original linear space in most cases, so I wrote my example using that approximation.

Here’s the source code, with build scripts for OS X and Linux: Download linearexample.zip

You’ll need GLUT, which should be there by default on the mac, but you may have to install FreeGlut on Linux. Once built, it displays a texture containing 1 pixel wide white lines surrounded by black, slowly rotating to show off the staircasing. Every second it switches back and forth between the default bilinear filtering and my custom shader working in linear space, so you can see the difference it makes. If you’re using this for full 3D work, you’ll need to insert a perspective divide by w for the texture coordinates before you do the texture samples. It also doesn’t handle mip-maps, and another way to improve the quality would be to use a different sampling function rather than just linearly averaging.

Many thanks to both Greg Abbas and Garrett Johnson for teaching me everything I know about color and resampling theory. What I do understand is purely thanks to their patient explanations.

I seem to be out of town for most of the disasters that strike LA. I was doing an overnight concert near Palm Springs when the Simi wildfire came close to our house in ’03, and drove back at 6am to find the side of the freeway burning. The last noticeable earthquake we had I was up in Cupertino on business, so I had to settle for hearing about it from Liz. I was actually quite glad to be home when the latest one struck, both so I didn’t have to worry from a distance, and so I could feel more like a true Angeleno.

One thing that impressed me while watching the news roundup was the quality of the visualizations. There was one animation in particular that really gave a strong impression of how the earth moved, produced by a team at Caltech. They’re available for download from http://shakemovie.caltech.edu/ and I’ve uploaded the version above to YouTube since the original files are a bit inconvenient as .mpg’s.

It’s fascinating to match up the animation with our experience during the quake. You can see Simi Valley on the left side of the screen, and watch as the ground waves go past. We felt a strong jolt, followed by some strong but low frequency side to side movement. In the video you can see the waves flowing past us, amplified by the low valley, running much less coherently in the mountains that surround us. The map of peak ground acceleration shows how little the hills shake compared to the lowlands.

What really impresses me about Caltech’s work is that this isn’t a one-off for this earthquake, they seem to have a production line going for all major quakes in southern California. They aim to get the animations online within 45 minutes of any local one with a magnitude more than 3.5. I’m betting we see a lot more of them next time we get hit, and I’d love to see them duplicate it into the Bay Area and other places with active seismology. They don’t have any information up about the technology they’re using, but I’ll be keeping an eye on their site to learn more once they do publish something on it.

Photo by Shoreline

I was at Denver International waiting for my flight to Burbank. It was already on the screens as over an hour late, and it was the last flight out, so I was feeling nervous. The lady at the gate came on the loud speaker and announced that while it wasn’t officially canceled, unofficially it looked likely it would be. Her advice for the 50 people waiting was to head to the one customer service desk they had manned and sort something out with them. "Discounted hotel rooms" was one of the less-than-appealing offers mentioned. That resulted in a stampede in that direction, but I remembered the advice I’d received from veterans of business flying. Avoid the service desk at all costs, because if you’re stuck, so are loads of others, and you’ll end up spending hours standing in line. I was determined to get home that night, so I started working on my other options.

There were no more flights to Burbank, but Liz was picking me up so I could fly into LAX instead, which opened up several direct flights. I figured out what the next one I could catch was, and tried to use my iPhone to book it through the internet. The United site wouldn’t let me book that close to departure, but Expedia appeared to. I went ahead and booked the flight I wanted, and then headed over to a bank of self-service check-in machines to print out a ticket. After some futzing trying to use my confirmation number, I realized Expedia had actually bumped me onto the flight at the same time the next day, ignoring the date I specified, and I’d missed that in my rush. Next up was a trip to the bank of phones that went direct to the United reservations system. They also couldn’t handle a booking that close to departure. At this point it was only 30 minutes before the flight I wanted left, so I was getting worried.

I walked past the customer service desk, and sure enough there was still a massive line. Finally, I went directly to the gate where the LAX flight was leaving from. There was only one person in line at the desk, also a Burbank refugee. She booked onto the flight, though her luggage wouldn’t be following. I walked up, and I only had carry-on, so the attendant was able to print me out a ticket and get me a seat in under a minute, all for no cost since I had my Burbank boarding pass. I so pleasantly surprised I was grinning the whole flight home.

My high hopes of technology didn’t work out, but that advice I’d got about avoiding those customer service lines definitely paid off.

There was a big earthquake just a few minutes ago. We’re on the west side of LA, so there’s no noticeable damage, but it looks like a 5.6 according to the USGS, so Pomona and that side may be hit pretty bad.

See here for more details: http://quake.usgs.gov/recenteqs/Maps/118-34.htm

I was feeling fairly cocky after the last few years of regular road-biking, and wanted to try something ambitious while I was here in Boulder. Climbing 2000 feet up Flagstaff Road and then taking the Walker Ranch Loop sounded like a good way of stretching myself. I didn’t count on quite how stretched I’d be by the end.

I got a 9:15am start, a bit later than I’d planned, but still not too hot. The ride up Flagstaff was tough, but I took it slow and drank plenty of water, since I knew I had a long way to go after that. The steepest section was the first half, before the auditorium turnoff, but it was a relentless grade all 7 miles to the top of the ridge. After catching my breath, I headed down the other side to find the Walker Ranch trailhead, and was a bit worried by how far I had dropped by the time I got there.

The entrance to the property was signed, but I ended up taking a wrong turn and getting scolded by a genuine cowboy at the historic homestead site for taking my bike in a no-bike zone. After being pointed in the right direction, I found the parking lot, and set off left to do the loop clockwise. The first mile or two was rocky single-track, which climbed a little before plunging down to Boulder Creek. As I was headed further and further down, I realized it would be a tough climb back out of the valley. Once I hit the creek, there was a bridge and I got to rest and enjoy the white water crashing down the canyon.

After the bridge, there was a really steep cliff climb of a few hundred feet. I had to carry my bike up steps for most of it, and that took its toll. Then there was a crawl up to another ridge, before heading back down again and crossing the creek again. By this point, I realized I was getting irritable for no good reason, a possible warning sign of dehydration, so I stopped again in the shade and made sure I drank plenty.

I was less than 2 miles from the trailhead, but a long way below. It was getting into the high 90’s by this point, and I walked a fair part of the final climb, taking plenty of breaks in the shade and getting through more water. When I finally made the parking lot, I crashed out under a tree for 20 minutes, and thought about my next move. I’m used to biking in the California summer, so I had brought a lot of water, but I finished off the last of it there. I only had a couple of miles of road-riding to make it to the ridge on Flagstaff and then I’d be able to coast back to Boulder, but I knew I without water my margin of safety was shrinking. In the end I decided to take it very easy up the road, with lots of breaks, and keep an eye on myself for signs of heat exhaustion or dehydration. In the worst case, it was a well-travelled route with houses nearby, and I might have to ask for help.

That last climb was just as tough as I’d feared, but taking it slow I was able to make it to the top of Flagstaff. That was such a great feeling, I shot back down to Boulder in less than half an hour. I returned my rented bike, and by an act of god there was a Coldstone Creamery next door. I don’t know if ice-cream is the best thing for dehydration, but I’ve never tasted anything so good.

What should have been a 4 hour ride turned into 6, and I made some rookie mistakes; failing to take into account the difference the altitude would make, not checking the weather forecast, bringing too little water for the conditions. If you’re looking for a tough ride out of Boulder, it has some amazing views and great technical single-track on the loop, but be smarter than me and make sure you’re prepared!

Everybody knows Boulder’s a great city for mountain biking, but I never realized there were even fatter tires on the Boulder Creek whitewater tubing course. All you need is a tire from the gas station on Arapahoe and Broadway, then head down to the creek at Eben G Fine Park, and take a wild ride.

If you’re visiting Boulder and want to explore the mountains on traditional fat tire, there’s a couple of options for renting one. Rob from Eventvue pointed me towards University Bicycles, right in the center of downtown on Pearl Street, but they were out of mountain bikes when I got there. They were kind enough to recommend the Boulder Bikesmith, about 1/2 mile from the city center, in the mall on the corner of Arapahoe and Folsom. They sorted me out with a Giant XTC1 in good condition, charging about $55 for two days. The lock and helmet were included, but there’s no cages on the pedals or bike computer, both of which I missed once I hit the climbs.

I had no clue where to go, so I hit the Boulder Book Store on Pearl Street and discovered Bicycling Boulder by Burt and Terry Struthers. This is a fantastic little guide to a whole bunch of local trails for road and mountain bikes, with short but clear descriptions, they’ve obviously spent a lot of time on the routes themselves. The only drawback is that their maps and elevation charts are obviously taken directly from their GPS systems, with a few very basic additions, so you may want to pick up a separate map. I didn’t, but there were a couple of points on my ride today where I was unsure if I was on the right path, and wished I had.

That evening I started out gently, taking the Boulder Creek trail. It runs alongside the stream for about 5 miles, from one end of Boulder to the other. With no street crossings and little grade it’s a smooth ride the whole way. It parallels Arapahoe, with ramps onto it from most of the side-street bridges that cross the creek.

Today I had some time free in the afternoon and wanted to go a bit further afield. I’d had lunch with Andy Sautins from Return Path, and he recommended the Poorman Road loop. In the Struthers book this is listed as a variant of the 9th ride on Sunshine Canyon, and is mostly asphalt with a couple of miles of gravel fire road. It’s close to town, so I was able to get to Mapleton Avenue and then continue west as it turned into Sunshine Canyon.

I had to ride 2.5 miles up the asphalt to reach the Poorman fire road. My misery index was fairly high on that uphill, it’s only a 1000 feet gain but felt like more. I felt a bit lost without my cadence meter to help me keep a steady pace, I was missing my clips for getting back power on the upstroke and could feel the altitude in my breathing. Once I got to the turnoff though, I was actually a bit sorry I wasn’t carrying on up to finish the other half of Sunshine Canyon. The view was beautiful and getting better, I’d found my groove with the climb, and hadn’t been passed by any other bikers (though maybe no one else was crazy enough to do the uphill in the afternoon heat!)

Poormans is a dirt road, but it’s in very good shape. It started off level, and then headed more steeply downhill, but it was so smooth I had an exhilarating descent for 2 miles, hardly touching the brakes. That led to the Four Mile Drive asphalt road, which the joined Boulder Creek Road and came back into town.

Tomorrow I’m thinking about attempting Walkers Ranch, with 3,200 feet of gain, so if this is my last post, you’ll know why…

Photo by Concrete Jungler101

I ran across the Mistake Bank for the first time today (HT Tim Berry via Execupundit). It’s a Ning network where you can post stories of your memorable mistakes. Looking through the contributions drove home a lot of lessons, so I thought it was about time I gave back and shared some of my own screw-ups.

Back when I worked in the game industry, my first job in the US was at a small but established company. It was towards the end of a grueling project, everyone had been working long hours and there was a lot of discontent in the ranks. The manager of the project came into my office and closed the door. He asked if I wanted to join him and found a new company, explaining that I was key to his team, and most of my colleagues had signed on. He painted a picture of a family-friendly, creative environment where we could build games the way we’d always wanted to. He’d talked to some big publishers, and had a contract to produce an NCAA version of a popular NBA basketball game. I’d had dinner at his house, met his family, and felt a lot of affection and trust towards him, so I was excited by the idea and agreed.

With all the good-feeling I had towards him, and the way he always talked about ‘our company’, I never stopped to think about actual ownership. Since I was alone in the US for Christmas I even volunteered to help unpack and set up the office furniture over the vacation, throwing myself completely into making the company a success. The first week we all started it rapidly became ‘my company’, because after all he was the sole owner, and none of us had any stake. He’d needed our resumes to convince the publisher to give him the contract, but after that we were overhead, and far too fussy about quality. He bought a second house and a Mercedes in the first couple of months, and fired or pushed out the experienced artists to make way for untrained people keen to make it into the industry, willing to accept sub-$20,000 wages. He demanded relentless hours, with my personal best topping out at 92 in a week. I finally knew I had to leave when my parents visited for 2 weeks, and I was only able to see them twice in the evening. Another strong memory is seeing a colleague chewed out for being late on a Sunday! I stuck it out for a year, until the end of the project, and then left to start my own business away from games.

The lesson I learnt from this was to never make a deal that relies on good will and assurances. No matter how well you know someone as a friend, the pressures of money and power are very strong, so you need to look out for your own interests. Now when I’m evaluating an offer, I assume that everyone will work within the rules to maximize their own position. Looking back, my mistake was listening to his words instead of evaluating his actions, and not demanding anything concrete to verify he’d deliver on the lofty promises.

I recently discovered Permessa, a company that’s been dealing with enterprise email for the last 15 years, with an impressive range of customers, everyone from Toshiba to the US Army Corps of Engineers. The CEO, Stefan Mehlhorn, runs an occasional blog covering email issues.

Their products analyze email and IM data as it flows across the internal network, focusing on automating common admin tasks like tracking down performance problems or enforcing email use policies. They’ve got some smart ideas on improving on the standard rules, like working out the impact of a message by multiplying its attachment’s size by the number of recipients, rather than the usual blanket size limit. This makes it possible to send a 30MB attachment to a couple of people, but block a 2MB one that’s going to 200 recipients, which is handy because the latter takes up a lot more room.

I can understand why their services are very popular at large companies. The performance and reliability of your email systems are insanely critical to running a business, so anything that helps optimize the messaging backbone is worth buying. Looking at the big picture though, it’s depressing that we have to worry about 20MB attachments when a 1TB hard drive costs $200.

The web approach of throwing large numbers of cheap boxes at a problem
has massive advantages compared to having a handful of super-pimped and
expensive Exchange servers. You can actually take advantage of the cheapness of storage, rather than being stuck prioritizing performance over capacity as Microsoft recommends for Exchange. Individual boxes can fail and you don’t have to go into Exchange recovery hell while your boss and all of your coworkers fume. As your requirements change, you can incrementally add or alter hardware.

Twitter’s troubles make it clear that handling communication between large networks of people is still a really hard problem even with a modern cloud architecture, but just like the killer micros ate up the mainframe business, large networks of cheap servers are going to consume Exchange.

Photo by Ben Romberg

The single best thing about PHP is how easy it is to embed HTML within your source files. This makes writing user-interface oriented code incredibly easy, since you can prototype both the presentation and the logic of your pages in the same file.

As always though, there’s a price, as I discovered after some serious head-scratching yesterday. All the executable code in a PHP file is enclosed in special <?php … ?> blocks. A typical project will have a bunch of included PHP files, with the each file internally enclosed in one of these tags. Anything in those files that’s outside the tag is printed verbatim to the standard output, usually the user’s web browser. That means if you have a new line after the closing tag in an include, that will be printed to the output.

Normally that’s not a problem, floating carriage returns are generally treated as whitespace and ignored in HTML, so it doesn’t make a difference. What if you’re actually trying to pass binary data to the user though? In my case, I’m fetching a mail attachment from a database, setting up the appropriate MIME content type and then printing it to standard output to be downloaded. That nearly invisible new line at the end of one of the include files gets output first, which royally confuses most binary formats, making them unrecognizably corrupted.

Once I figured out what was going on, I did a sweep through my includes and removed any trailing new lines, but I could also have called ob_clean() to wipe the output buffer before I wrote out the file data. There’s a good treatment of the whole topic of file downloads in PHP here, but it feels like the deeper lesson is about using the right tool for the job. PHP is extremely fast to prototype web apps in because it is totally focused on the task of producing HTML pages, but once you’re dealing with arbitrary data, Perl or Python sure start to look pretty.

Photo by Illetires

I’ve been downloading email from my Google account onto a local machine to do data analysis, using their IMAP interface. About an hour ago, I suddenly started getting failed connections with the message ‘Lockdown in sector 4 (Failure)’. After a bit of googling, I discovered that’s their whimsical way to indicate that they’ve detected something in your access patterns they dislike, and IMAP access to that account is dead for up to a day.

I’m assuming the algorithm that triggers this is related to the amount of downloads you attempt in a given period of time, and they’re trying to prevent overloading of their servers or hacking attempts. It’s unfortunate that the criteria they use are unpublished, my usage today seemed reasonable, and no different from other times I’ve done something similar.

I’d expect Google to have mechanisms like this in place to protect themselves but it highlights what a scary prospect basing a business on IMAP access is. Any service like Xoopit could trip over Google’s hidden rules, and even if they’ve reverse-engineered their current state, there’s no guarantee that the triggers won’t change. And that’s just assuming that Google don’t want to be evil, if they decide that they don’t like their users handing over their passwords to third-parties, it would be easy enough to block their services in just the same way.

The real answer would be a proper gmail interface for third-party applications, rather than reusing the IMAP transport protocol with its reliance on sharing passwords, but this doesn’t seem like a high priority for Google. Until then, I’m going to keep my main focus on the Exchange world. The APIs may be scary, but at least Microsoft offers unfettered access to the data once you’re installed as an add-on.