madbean

Some questions just cannot go unanswered. http://www.cenqua.com/forums/thread.jspa?threadID=1877.

A recent IM conversation:

matt: I'd better not have H5N1
bjd: I'd better not have I18N

Cracked me up, anyway. And in other news, I recommend pseudo-ephedrine plus a strong coffee for all your head-cold needs.

It is probably best to make clear that I’m a hard-core Civilization fan. I’ve spent large slabs of my life playing each of the first three versions, large slabs that are measured in metric tons. Everyone say it with me: just one more turn.

So it was always a given that I’d be buying Civilization IV when it came out. And that is not even taking into account how great it actually looks; Python-based mod’s, better multiplayer and team-play, civics, religion and … the removal of corruption!

Civ IV is due to be released Nov 3, suffice it to say I’ve pre-ordered my copy. But after pre-ordering, I thought I’d better check if I’ve got a beefy enough box to play it. That was an instant “D’oh” because I don’t have a DVD-ROM, but that is easly fixed for less than $40 at the weekend computer markets. Civ IV’s system requirements state you need “Video hardware transform & lighting”. Couldn’t quite work out if my tried-but-true GeForce4 MX 440 qualified, but didn’t want the game turning up and then not being able to play it instantly because of my grahics card.

That’s when I came across www.srtest.com. They sorted me out: yep, I do meet the minimum requirements.

Don’t bother emailing me in November.

So, I’ve finally got around to making another animation. Enjoy.

Things mentioned in the show:

• Artima.com podcast with Gavin King. Link
• Sun ad campaign story. Link

Oh, and yes I do know I am speaking too fast in some parts. But you get that (i.e. I’m not fixing it). For those that are curious, the phrase in the opening paragraph is “pure virtual function”.

And if you hadn’t noticed, the whole format of “the show” is from Comedy Central’s Daily Show. Link. (Love that show!)

I love IDEA’s Live Templates, and I often find myself using java.util.BitSet. The BitSet javadoc describes a neat way of iterating through the 1 bits, and I do this often enough that it warranted a custom Live Template. Now all I need to do is hit itbs<TAB> to have this code automagically appear.

The template looks like this:

for(int $INDEX$ = $BS$.nextSetBit(0); $INDEX$ >= 0; $INDEX$ = $BS$.nextSetBit($INDEX$ + 1)) {
  $END$
}

I’ve captured a few screenshots since you also have to setup variables for $INDEX$ and $BS$.

spuddy: O...M...G... the download for IBM/Rational RAD 6.0 (based on eclipse) is 1.4GB
bph: what the fucking fuck
spuddy: I think it includes websphere or some thing
bph: it would wanna have some kick ass easter eggs at that size. like a MMOG or something

They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety.

Benjamin Franklin ^{1 2 3}

This is a cautionary tale on the pitfalls of storing UI state in the session of a webapp.

Very occasionally we have a need to send out a bulk email to a bunch of people. For example: we had several hundred requests expressing genuine interest in The Commentator, one of our April Fools jokes this year, and we sent out a well-humoured email to them explaining it was a joke.

To help manage these mail-outs, we found and installed a nice little cgi webapp. And since I’m currently tracking a handful of people who are participating in the alpha program for FishEye 1.1 (with SVN support), I figured it would save me some time by just using this existing webapp.

Now this webapp is fairly slick: it has a nice-looking UI, plenty of features, and lots of different admin pages you can fiddle with. I went ahead and setup my alpha-program list, and composed an email announcing that the next alpha build was available. At the same time — in a different browser window — I opened up the admin pages for the Commentator list so I could check what settings we had used there. Switching back to the email-composition page, I pressed “submit”.

And suddenly 300 Commentator-hopefuls get an email about the FishEye 1.1 alpha.

And I became a spammer for a day.

And if you have ever written a webapp in-anger, then I’m sure you can guess what went on.

Upon entering the “fisheye-alpha” part of the site, it associated my session (or, more likely in this case, a cookie) with the “fisheye-alpha” list. When it presented the email-compose page, it titled the page “fisheye-alpha compose” because, obviously, that is what I was doing. However, when in another window I started clicking through the “commentator” section, my session became associated with the “commentator” list.

When I then submitted the email form, the browser posted to the webapp the email subject and body. But there was no hidden parameter saying for which mail-list this email was for. Instead, the webapp looked up the mail-list from my session, which was the “commentator” list, and sent them the mail.

The pain! The guilt!

So the moral of this story is simple. If you are using both session-state and request-data when handling a page submit, make sure the scope of the session-state matches the scope of the page.

Imagine some data-collection that is spread over a sequence pages. You can store the data from previous pages in the session: but don’t store them globally in the session. Instead associate them with this instance of the page-sequence. Make up a unique id for this instance on the first page of the sequence, put the page-data in a hashmap (indexed by this id) in the session, and use that id has a hidden parameter on every page.

It’s not that hard. And you might be surprised: make the scope of page-data explicit in your webapp, and it may actually make your code easier to follow.

In 1996, I completed an honours year attached to my Comp. Sci. This involved a thesis, in which I choose to investigate a certain optimization technique in computer graphics. The impressive title of my thesis was: Space-time ray-tracing using ray-classification. I occasionally get the odd email about it, and the ftp server at Macquarie Uni that housed my paper, code and animations is now gone, so I decided it was about time to do a little data dump of my honours project.

The General Idea

Ray-tracing is a neat and elegant algorithm for producing photo-realistic images. Think about what happens when a camera takes a picture in real life: various light sources (the Sun, light globes, etc) bath the scene in photons, which bounce around as they are absorbed and re-emmited by objects. Some of these photons eventually end up passing through the lens of the camera and strike the film. You could easily imagine an algorithm that simulated this by tracing these rays of light forward from light-sources. The problem is that a vast majority would never hit the camera, and you end up tracing rays that never contribute to the scene.

Backward ray-tracing (or just “ray-tracing”) does the opposite: it traces rays out of the camera, bouncing rays backwards through the scene to see if they hit any light sources. This bouncing of rays allows many real-world visual artifacts to be modeled: transparency/refraction (bounce rays through objects), reflection (bounce rays along a perfect angle), diffusion (bounce rays along many angles), shadows (rays bounced towards lights are instead occluded by intervening objects).

There are various models and heuristics for bouncing rays backwards off objects. The real problem is calculating which object a ray hits. The brute force approach is to test for intersection of the ray with every object in the scene, then pick the intersection that occurred closed to the root of the ray. It is easy to see that this will be the bottleneck of the algorithm. Much of the research into ray-tracing has gone into improving the search for the object with which a ray first intersects.

The Specific Idea

My honours thesis concerned a technique for speeding up the ray-intersection calculation that also took into account time (animated scenes). If you really want to know the details you can read the paper, but the general gist goes like this: a ray is defined by 5 parameters, its (x, y, z) origin, and two angles that describe its direction. This means each ray exists as a point in a 5D space. Add time into the equation, and you end up with a 6D space. Subdivide this 6D space, and associate with each cell all the object that might intersect rays from that cell. This reduces the number of objects you need to consider when doing a ray-intersection test.

That might sound complicated, but it is that tried and true technique: convert your problem into a mathematical space and adaptively subdivide the space to reduce the work you need to do.

The Thesis

The (original) PostScript version of my thesis is available here: thesis.ps.gz (384KB). I have since converted it to PDF, which should be clearer to read on screen: thesis.pdf (348KB). An entry for this paper can be found in CiteSeer here: http://citeseer.ist.psu.edu/quail96space.html.

The abstract is as follows:

Throughout the history of computer graphics, a very active area of research has been the attempt to create convincing, life-like images. Ray tracing is a technique for generating photorealistic images, and can easily support a wide range of natural phenomenon. However, producing a ray traced image is very expensive; and producing a ray traced animation is often prohibitively expensive.

This thesis looks at two techniques for efficiently producing ray traced animations; Glassner’s space time hierarchical bounding volume technique, and my space time extension of Arvo and Kirk’s ray classification. The results show that my method is more efficient; however Glassner’s technique has much better memory performance. Based on some of the ideas of my method, some ways of improving Glassner’s technique are suggested.

57 pages.

The Code

I shudder at the thought of making this code public, but here it is: src.tgz. I wrote that code a long time ago, long before I’d been introduced to the concept of common coding conventions. I’ve made a few tweaks to the original source so that it at least compiles without errors on a modern C++ compiler.

The code contains an API for defining the scene to be rendered. So it doesn’t take in a “scene description” text file, you actually define the scene with some C++ code. This works quite elegantly, as the API is designed so that your scene description looks mostly declarative anyway.

Because the scene definition needs to be compiled into the program, you can’t just “run” the ray-tracer. So there is a little rend shell script to mange this process. For example, you can render the “mount” animation like so:

./rend out.txt strcom.cc test/mount.cc

Statistics about the rendering are saved to out.txt. The ray/object intersection algorithm is plugable, strcom.cc is my space-time ray-classifier. There is also a naive (brute force) algorithm, and an implementation of Glassner’s hybrid SS/HVB technique (for comparison). You will want to do a make clean if you change scenes.

The Animations

I created three animations for testing the performance of the ray-tracer. The output of the ray-tracer was a series of TGA files, one for each frame. At the time, I converted these to FLI files (loss-less). I have since converted the FLI files to MOV (Quicktime, lossy). Both are included below.

FLI (376KB) MOV (44KB)

This is a short animation of 3 crystal balls doing a donut above a randomly generated “mountain”. Technically, this tests the ray-tracer’s ability to handle animated transparency.

FLI (2.8MB) MOV (248KB)

“Night City” is my favorite; it is the most complicated (in terms of shapes and movement), and is cinematically the most interesting. It depicts traffic in some kind of “particle city”. Lights above illuminate the roads, and the cross-lines on the intersections control the traffic. The camera in the animation follows one “particle” as it makes its way towards a building.

“Night City” was not that difficult to create because objects can be created procedurally. For example, each building could be created with a call like create_building(floors, width, length, colour). The hardest part was modeling the path of the camera as a mathematical function. The goal of this animation was to test both camera movement and object movement.

FLI (156KB) MOV (84KB)

This last animation is designed to emphasize the “space-time” notion: the motion of objects through time. The motion-blur should be evident.

The End

I look back on my honours year with fondness, but at the same time it was a lot of hard work. I remember making a mental note to think very, very hard before embarking on something like that again (such as a Ph.D.).

As amateur foodies, one of our goals during our trip to JavaOne this year was to sample the fine cuisine San Francisco had to offer.

Our initial strategy was acknowledged as stupid: leave the hotel without advice and without our travel-guide book, and try to find some good food by wandering around. This returned some mediocre results the first two nights, but we hit the jackpot on the third night: Ponzu (104 Taylor St). Its logo of “Eat, Drink, Lounge” is the perfect description: a choice blend of sofas, bevies (Aussie slang for beverages: great beers and some killer sake cocktails), and amazing food. The calamari was heavenly, with lashings of salt and pepper with a beaut’ sauce, as was every other dish we ordered from their Asian tapas-style menu.

However, without a doubt, the highlight of the culinary experience was Tuesday night, when jag took us to the Thang Long “Crab House” restaurant. The entrée included calamari (of course) which was just exquisite, but the crab-and-cheese filled deep-fried pastry “things” were unreal. Then there was the crab. Oh the crab. When we arrived (after 8 hours at the Cenqua booth, with no lunch or breakfast), we informed James that we were, well, starving. So James ordered the food for us. First the waiters brought out some noodles, and enough crabs for one-between-four. After our first taste, we thought “Great, this is awesome!”. Then they bought out some more crabs, enough for half-each. Awesome! But the crabs kept on coming: I’m sure I had more than 1.5 portions of beautiful, garlicy, salt-and-peppery crabby goodness. YUM!

But the foodie expedition didn’t end there. After the last general session on Thursday (today), we went out to lunch with Pamela to a pretty swish (or “shi shi”) mexican restaurant on Geary St (a special thanks to Pamela: you are a champ!). But then our resident tour-guide Terrence Parr took over the reins (Terrence had previously taken us out to dinner at the First Crush (very nice) and to brunch). First stop was the Zeitgeist on Valencia St; the pub that combines pot-smoking beatniks and Netscape millionaires. Much beer was had. Then it was to the Limón peruvian restaurant. Some quality calamari was had there too. I had some paella-style thing which was good, but the pork chop that Brendan and Terrence had was about 3cm thick and looked delicious.

Its been a pretty good run, but we fly back tomorrow night; we will see if we can do any better.