Let there be light!

I had a couple of blog posts in my head that I wanted to put up here, one just from just a couple of days ago, but I don't have the pics handy...instead I'm sitting here waiting for my photon mapper to finish, so I thought I'd write a bit about that...kind of a technical post. I'll try to add a brief pictorial progression so you can see what I'm talking about. At left is a basic ray-traced image that we started with this semester (in a class I'm teaching). It's fairly simple in that we have two spheres, one (the blue one, well it's sort of blue, maybe more like chrome) more reflective than the other, which is more diffuse. There are three lights in the scene but they only show up when reflected (point light sources). The ray tracer demonstrates several concepts: object-oriented hierarchy (spheres and planes are objects), recursion (the rays shot into the scene are reflected recursively), list processing (all objects are on a list), and basic file input/output. Fairly simple, an image like that takes about 3 seconds to render.

The next image in the progression would have been the same as the first, as we explored parallelism. With chip makers now producing multi-core chipsets, one may wonder how to take advantage of the multiple cores or CPUs on the chip? The ray tracer is very well suited to this because each pixel is processed the same way. If we had as many CPU cores as pixels, we could assign each on a one-to-one mapping. My desktop machine in my office has 8 cores, so a simple speedup is to let each of the 8 cores process each of the h/8 rows of pixels. The trick here is to make sure to avoid race conditions, that is, don't let any more than one core write to a piece of shared memory. The ray tracer, in its original conception, had this problem, so this turned out to be a nice exercise, complete with garbage images if done incorrectly. The solution called for each ray to maintain its own state info, which makes perfect sense thinking in parallel. Once that's done, multi-core parallelism is pretty easy, requiring basically one line of #pragma compiler directive to use OpenMP and voila! An almost k-factor speedup for k cores available. Coincidentally, the solution also leads in to the next step of the ray tracer evolution, and that is getting transmission to work right, like you see at right: we not only have reflective objects but transmissive (transparent) ones now.

Once we have the notion of independent rays (in terms of memory access anyway), then it's not a huge conceptual leap to think of photons instead of rays. These are shot from the light sources within the scene in a stochastic (random) sort of way. They reflect or transmit from/through objects just like rays, except that there's a finite number of photons—each makes its way through the scene unlike rays which recursively spawn new rays at each intersection point. Based on random conditions, photons eventually stick to surfaces, like shown at left. One of the goals of this type of photon mapping is to be able to render caustics, or focused concentration of photons, more or less. When rendering, what's important is the number of photons per unit area (why not volume?), that is, their density is what we're after. (Note: for those of you observant enough, you'll see that the photon map I have here doesn't match the other images—you're correct; this photon map, with only one light source, is what I used for debugging. It was clearer using one light that the caustic was not showing up opposite to where the light source was—turns out I was calculating distance incorrectly, d'oh!)

Sum up the photons' "flux" per ray intersection point, divide by their squared radius, and presto! We have caustics. Photon mapping also demonstrates a key aspect of careful program design: at each intersection point one has to find a number of the closest photons. The image at right shows 20 photons sampled at each intersection point from 2,000 initially shot out (fairly small numbers all told). With these numbers the image is rendered in about a minute. Increasing those numbers by an order of magnitude to 100 samples from 10,000 photons initially shot yields about a 9-minute render time. Meanwhile, increasing yet again to 500,000 photons and 500 samples takes...I don't yet know, still waiting...on the order of hours I expect. Ding! Just done "baking": 188.6 minutes, yup 3.14 (pi?) hours. The key aspect of program design is this search for closest photons—the program uses a kd-tree to find the k-closest photons in O(log n) time. It has to do this for every intersection point, of which there is a very large number. If no kd-tree was used, then the search would take O(n) every time, and I suspect it would have taken a lot longer to complete, perhaps days. So was all that extra number-crunching time worth it? Below are two images (10,000 photons on the left 500,000 photons on the right) that match the photon map above. See the difference? One could argue that the caustic boundaries and the caustic itself are a bit crisper in the image at right, but are they worth three hours?

Happy New Year!

2010 is history. Its last month was unseasonably cold. I'm not sure if that's official meteorologically speaking, but at least it seems that way to me. A cold December, with snow at Christmas. We've gotten spoiled by the hot summers and both long for the return of warmer temperatures. I remember when in years past Corey would be out mowing the lawn in December. Not this year; it's mostly a stay inside kind of winter. And at least two more months to go. Hopefully March will bring back nicer weather as it usually does.

And when inside, why not fire up the fire place, and take out a good book, and boil up some tea. That teapot is something Santa left last year. Our old "brown bettie" had chipped (mainly due to my clumsiness), so I wanted a replacement. I found this little cast iron pot and am quite pleased with it. Although a touch small, aesthetically I think it's very handsome, and being made of iron should be indestructible. As for reading, it's 2011, and it's the year of the electronic book. Just before Christmas the University was kind enough to equip me with an iPad, which I mainly intend to use for teaching purposes. Corey found a good app for this, PenUltimate, and I tested it with our home projector. I think with a decent stylus, I should be able to use this app for scribing lecture notes. The app produces electronic PDF notebooks of notes, which I put online for the benefit of my students. Another app, PDF Expert, has fairly nice SFTP transmission utilities which allows me to transfer PDFs from the iPad to my web server. So with both of these tools in hand, I think I'll be set for class when they start up again in just a couple of weeks. In the meantime, why not use the iPad's touted "killer app" for reading electronic books. Some say they can't seem to swtich to this style of reading, and prefer the traditional feel of paper in their hands. I thought I'd be like that too, but the iPad's iBook app (free) is growing on me rather quickly. It holds a small library of (free) books, the font is nice, its sepia coloring looks like a book, you can bookmark pages and highlight text. The highlighted text looks irregular and imprecise just like the real thing, except that the way in which you select text is precise to the letter. Very nice. This precise selection of words is also handy when looking up words in the dictionary—this feature I have to say is really well done. On the iPad you get a nice little window that pops up with the word's definition. I've already looked up a bunch of words having read several of Arthur Conan Doyle's Sherlock Holmes adventures, Rudyard Kipling's Rikki-Tikki-Tavi, and Philip K. Dick's The Eyes Have It—all pretty much short stories. Right now I'm reading Honoré de Balzac's The Marriage Contract. My brother suggested both Balzac and Descartes so I wanted to follow up on his recommendation—I've got Descartes' Discourse on the Method... bookmarked. It's a little profuse in its prose, but not bad for scientific observations made in the 17th century. The gist of it is: assume nothing, divide and conquer, verify each step. I suppose a fairly basic approach today, divide and conquer in particular is certainly a well known approach to algorithmic design. Still, I suppose someone had to write this down, and it's held up for over 400 years. Btw, the other nice feature of electronic books is that the bookmarks transfer over to your various ereaders: iBook is available on the iPhone as well, and when I transfer reading between the two devices, each "knows" where I left of previously. Quite convenient. No more dogearing paper books. The only nuisance with this is that you have to be on the grid...the net is becoming as much of a dependency as electricity...

Milford Sound

Our last stop on our New Zealand road trip was Milford Sound. There really isn't much there at Milford Sound apart from the lodge and campground (RV hookups for us) and the quay from which boat tours depart daily. On advice from the campervan people from whom we rented the vehicle I booked a powered site at the lodge (which we later found out was sold out). We also picked the smallest boat tour of Milford. The small boat was the best choice I think—not overcrowded and able to get close to the fjords (to see the waterfalls for example).

The fjords here are truly spectacular, although the weather can be somewhat unpredictable, meaning often cloudy and/or rainy, as it was when we visited. When sunny it must be really fantastic. The way the cliffs line up visually is also interesting: apparently when surveying the coastline, Cook (I think it was Cook) had missed the entry to Milford, not seeing it from the ship. One major annoyance here were the black (sand) flies. They were all over the place. They didn't bite, but were a real nuisance. The Maori legend had it that the flies were there so that tourists wouldn't stay too long and spoil the scenery.

The waterfalls pictured above was one of three (if I remember correctly) to which the boat came close to. So close in fact that at one of them I got pretty soaked when standing on the bow (just for fun). The boat also got close to some of the wildlife in the area. There were supposed to be penguins, and I think I saw three in the distance, but I wasn't sure if they were penguins or seagulls. We did get close to some seals lounging on the rocks. They found a fairly windy perch, which we were told they did to keep the flies off.

Horsing Around Te Anau

A couple more pics from Te Anau (this was me trying to shoot behind me with my left hand). When we were in Queenstown we saw an ad for horseback riding, but since we went on the jetboat, we didn't have time to go on a "horse trek" as they call it. So when we checked in to our campsite in Te Anau, Corey noticed a horseback riding pamphlet and so I called them. We were going to go for a late afternoon ride, but when we called they said they'd pick us up in 15 minutes! So we quickly changed, and walked out to wait for the pickup. I wasn't sure what to expect, since most other "rent-a-horses" I've been on have basically been lazy...they were hard to control and would only pick up some enthusiasm on the return leg. The place we went to, Westray Farm provided me with the best horseback riding experience I've ever had. Not only was the horse nice, responsive to my gentle steering with the reigns, but the trek itself was excellent—it wasn't just a out-and-back half-hour walk, this was a long, circular trek up a hill and around a couple of animal herds. We first walked through a herd of curious cows, and on the way back we split a group of sheep. The terrain was also the most challenging I've ever been on horseback—on the way down there were a few steep parts where I felt I really had to lean back in the saddle. The horses were rescued from a former life of racing. Perhaps that was why they were fairly nice: maybe they were grateful for their new life. Mind you, perhaps because they were race horses in their former life, a few of them were a little flighty. I may have been laughing in the pic below because Corey's horse was one of these (she got stuck with the type of horse that I usually get). She eventually switched with the farm owner's horse who then had to discipline the misbehaving horse (had to give it a whack on the neck to stop acting up :)

Road to Te Anau

After our brief stop in Bluff, we went in search of our next campsite. It was supposed to be some sort of Holiday Road campground close to the beach. The online description sounded good, but when we got there, boy was it ever a dump! And of course only one set of toilets was opened, making them unisex. Corey said no way was she going to be showering there and so off we went in search of the other campground in the proximity that offered a "farm experience". The farm experience was night and day difference—very well maintained place, nice toilets, and baby sheep! So Corey made the right call moving us to this place, as it was most pleasant. The lambs were quite friendly, especially when hungry.

Lamb feedings were at 8am and 6pm (sharp!) with the lambs bleeting rather loudly, reminding everyone when it was time. The lambs got milk bottles while the goat and adult sheep got solid food in pellet form. The farmer/campgroundskeeper gave us quite a bit of info about his farm, number of sheep, etc. One new factoid was that sheep are born with a long tail. But as they are rather poor self-cleaners, the tail gets bobbed, either at birth with some kind of hot iron, or like these lambs, they get a rubber band tightened on the tail, which, due to lack of circulation, eventually drops off. I dunno which method is less painful. On the one hand hot-knifing the tail would hurt, but it'd be over quickly. On the other hand the rubber band has to be worn for a while, and I'm sure it can't be very pleasant. Another interesting observation was that sheep have horizontally-slit eyes (unlike cats who have vertically-slit pupils, weird huh?).

After our most pleasant stay on the farm, we got on the road to Te Anau, which would be something of a staging point for our trip to Milford Sound. It's a good idea to do this as the road to Milford is fairly tricky (think old road to Whistler, especially that old 13 or 17 mile stretch that used to be fairly crappy to drive), and there are no gas stations at Milford. On the way to Te Anau we stopped at this outlook to take a look at the Tasman Sea. It was a pretty blustery day. Later in Te Anau the fellow whose horses we rode told us that out here fishermen can only go out 56 days of the year due to these high winds. Btw, as you can deduce, most of the pictures were taken by Corey.  She got mad at me the other day for using her photos that she took with my camera.  I don't know what the big deal was, but truth be told she does take really good photos, and I've neglected to give credit where it's due.  Sorry about that, hopefully I've now corrected this omission.