Topographically Speaking

 

17 days to go. As promised, I've hacked together heightmap functionality; this one is based off the diamond-square algorithm. Next up: lighting, texturing, keyboard and mouse interaction, and some kind of sky (I'll probably go with skybox for that one.) Real-Time is coming along, albeit not as quickly as I had hoped. We're now working out an issue with the sensor modules; either the modules don't always send the right number of bytes, or we're dropping bytes somewhere in our serial drivers. Either way, we've got to figure this out and reliably track the movements of a single train to within a few centimetres by Monday.

Voronoi the Paranoid Android

Above: a cellular-based texture, Worley-style. Still implementing cool textures for my procedural content generation project; so far, I've got a couple of noise basis functions along with a framework for combining them into more complex textures. Next up: terrain generation. This will involve a few steps:

• Generate a heightmap. For a first pass rendering, midpoint displacement is dead easy to implement. Since heightmaps are textures, I can even slap this into my texture framework as another basis function (albeit one with a relatively heavy initialization time (although the midpoint values could be generated on demand!))
  
• Set up the OpenGL window. We've been using gtkmm for previous assignments; I see no reason to break that trend, as I can save time by slapping our old window setup code into the project.
• Issue OpenGL commands to render the heightmap. In its most basic form, this is just a series of GL_QUADS. If I was going after static rendering, I'd probably put the whole thing into a display list and use GL_QUAD_STRIPS instead; however, this will be interactive, so I'll need to do something smarter than shoving the whole terrain patch into a display list.

There are other considerations as well. For example, I might want to dynamically load blocks of terrain as the user walks around. Randomly generated terrain becomes a bit of a problem in this case - unless the blocks are "aware" of each other, there will be discontinuous jumps! I'll leave those problems for later.

Catch-22

22 days to go, and I'm putting the finishing touches on my raytracer. Above: my sample image, which features implicit surfaces and adaptive anti-aliasing. (Technical details? Bounded Newton-Raphson iterations, gradients for normal vectors. Simple. I'm told regula-falsi is preferred; if I had another day, I'd pop that in there. As for the adaptive anti-aliasing, I'm applying a Sobel operator to the luminance values from the first pass and randomly supersampling pixels above a certain threshold.) Unfortunately, the images seem to suffer from a good deal of noise; in raytracing, this is a sign of numerical instability. If I was pursuing a raytracer-based final project, I would investigate further and fix it, probably along these lines of attack: 

• The problem worsens with distance from the camera. This might be fixed by applying a projective transformation, but that would FUBAR angles for shadows and reflection.
  
• Some of the mesh models have wonky normals; it might be worth the time to recalculate them to the outside.
• I could probably eliminate a few spurious divisions and normalizations.

That said, I don't have time, so noisy images it is. Let's hope my final project is free of such trite errors!

Shady Business

 

Here's the same picture as before, with one important difference: the spheres look, well, spherical. Between dancing under the stars (and early-morning fog!) and class, I've somehow managed to find both the time and requisite sanity to implement Phong shading. Given libraries for vector operations, this is a relatively trivial task; nevertheless, it adds a whole new dimension (yeah, I couldn't resist) to rendered images. I'm also computing shadow rays to get the nice (albeit somewhat pixelated) shadows on the occluded parts of spheres. Next up: box and mesh intersections, supersampling, and hierarchical rendering. I'll keep posting progress images as I go along.

Here's Shooting a Ray at You, Kid

(Yes, I finally saw Casablanca a couple of weeks ago.) Exhibit A: the first meaningful image produced by my raytracer for CS 488 Assignment 4. It's a binary intersection image; it shoots a single ray from the eye through each pixel, rendering it white iff the ray intersects an object. I'll tackle Phong lighting next. For those outside the Graphics/CS bubble, Phong lighting is a relatively crude but efficient way to model the way light interacts with objects. As you can see from the Wikipedia page, it allows us to shade surfaces, thereby giving the impression of depth.

In general, raytracing is an attempt to model the way vision works. Production-quality raytracers will model reflection, refraction, transparency, scattered reflection from rough surfaces, and any number of other real-world phenomena to impart as much realism as possible to the final image. Maybe I'm strange, but I think that's cool - thanks to CS 488, I now have an appreciation for exactly how much programmer effort and CPU time go into, say, Pixar's rendering pipeline. (6-90 CPU-hours per frame, according to their site!)

One last note: although the raytracer project is by no means large, it's hefty enough that ad-hoc cp -r source control won't cut it. To that end, I've decided to give Git a spin. First impressions are positive: it's fast in all the ways that Subversion isn't, and it's ridiculously easy to set up over SSH.

On the Right Trackball

 

And here is the completed spherical Trogdor (of uniform density?) You might notice a circle drawn across his beautiful Phong-shaded polygons; that's part of a virtual trackball. Roughly speaking, this allows you to rotate the model as though the scene were contained in a sphere. (Also: that site uses a rather inefficient way to get the angle between the two projected vectors - can you think of a fast approximation?) Other user-interface goodies: you can select individual joints and rotate them, causing Trogdor to coil up or flex his shapely back-arm. You can also move Trogdor around.

Just remember: if you hear from me only sporadically this term, it's because I'm doing super-fantastic-awesome things like modelling Trogdor and driving model trains. All in the pursuit of higher education!

Burninate the Graphics Lab

 

It's CS 488 Assignment 3 time, which means I get to play around with hierarchical modelling - and what better way to do so than to construct the very likeness of Trogdor? (Yeah, it's a stretch. You try modelling anything with only transformed spheres.) BURNINATE!!!!!

Serial Experiments Lisp

I was watching Serial Experiments Lain when I noticed a certain LISP keyword scroll across the screen. A few posters have uploaded the still frame. Reminds me of the nmap cameo.

Real-Time Psychotics

I'm now gearing up to tackle the implementation of this specification for an embedded microkernel in the infamous Real-Time Programming course at the University of Waterloo. To share the masochism, our team has started the PsychOS blog. We'll be posting about our exploits - favourable, frustrating, pants-less, or otherwise - there, so keep posted! I'll try to mirror particularly poignant posts here at Quizzical Quincunx as well.

In other news, I've solved We Are The Swarm from Facebook's Engineering Puzzles site. This one is pleasantly devious; out of respect for the puzzle-solving spirit, I'll refrain from posting any hints. Enjoy!

Best Malpractices

"I learned very early the difference between knowing the name of something and knowing something." -- Richard Feynman

With that in mind, here's a well-reasoned rant against Best Practices. The IT world is replete with buffoons - programmers, managers, CS students, whatever - who toss around terms like AJAX, ORM, XP/Agile, Web 2.0, RDBMS, DRY, NIH, and OOP without ever pausing to ask the real questions. What do they mean? What do they do? Where do they succeed - and where do they fall short?

Consider this: Google does not follow Best Practices. They solve problems. Period.

Scripted Reality

As promised, here are the scripts.

The Sound of Scraping

After sitting on my CBC Radio 3 metadata for just over a week, I finally got around to throwing together a decent downloading script. Actually, the scraper/downloader is a loose federation of scripts, deliberately kept in separate modules so as to allow nice things like, say, running multiple copies thereof concurrently. I'll post a link to the source in the near future, along with a few words of explanation. Maybe I'll even write a README - after all, although CBC Radio 3 is afloat for now, there's no telling how long it will survive the budget axes of doom.

(And, to prevent the inevitable smartasses from chiming in with "you forgot wget, n00b" - nope, it's in there somewhere. That said, I think you'll find these scripts go a tiny bit further...)

If It Floats Like An Octopus

"C++: an octopus made by nailing extra legs onto a dog."

C++ is often referred to as a statically-typed language - it aggressively checks types at compile time (and, in the case of anything STL-related, spews out monstrous-looking errors.) By comparison, many "scripting" languages (and I use that word cautiously, since these are proving to be powerful application development languages in their own right!) such as Python and PHP support what is known as duck typing. Many rail against this, arguing that it leads to unmaintainable code and nasty runtime errors.

That aside, C++ does have support for duck typing - in its template system. Consider:

#include <iostream>
using namespace std;
template <class T> void p(const T& t) { t.print(); }
struct A { void print() const { cout << "A!" << endl; } };
struct B { void print() const { cout << "B!" << endl; } };
struct C { };
int main() {
   A a; B b; C c;
   p(a);        // "A!"
   p(b);        // "B!"
   //p(c);      // compile-time error

}

The global function p() enforces no type restrictions on the template class T; all it requires is that T implement void T::print() const, as A and B do. Also, note that p(c) causes a compile-time error, not a runtime error! There is a tradeoff, naturally: the compiler creates a separate copy of p() for each type that it's invoked with (g++ -S for the gory details!), so extensive use of this technique can easily balloon your object files.

And the total is...

76302. Of course, this is just the metadata - I wouldn't be so reckless as to hammer the CBC Radio 3 servers with 200 GB worth of download requests in a day! (Nor would my bandwidth permit me to suck down that much data in anything less than a couple of weeks. Oh well.) Next up: filter it down to a list of songs that I might actually want.

2017 Songs and Counting

Your guess as to what this does:

#!/bin/bash

for i in `seq 0 25`; do

echo "http://radio3.cbc.ca/nmc/artists.aspx?offset=${i}"

done | tee -a artists.log |\

./url-dumper 1.0 |\

egrep -o "/bands/[^\"]*" | uniq |

while read line; do

b=`basename "$line"`

echo "/play/band/${b}"

done | uniq | tee -a bands.log | ./cbc3-get-music-info 1.0

(Yes, I've left out some details - like what exactly those scripts do under the covers. I'll post about that when it's finished!)

Better make that 3156 songs. And counting.

Miscellaneous Perverse Tree Tricks

Unless you're Google, SQL-based relational databases are the de facto standard for storing web application data. Trouble is, MySQL et al. are great at storing relations - lists and sets, essentially - and are absolutely horrible for everything else, right?
Well, not quite. Tree structures are easily and efficiently stored using modified preorder traversal, which relies on nested intervals. This alone is enough to tackle many problems, like ACL-style permissions. I've seen the adjacency list method in use - if you like scalability, don't do it.

(For the truly masochistic: you can even pull off a decent directed acyclic graph implementation by computing the transitive closure.)

Yay for Efficiency!

(Caveat: This post is somewhat C++-centric, but its main points translate to any language.)

I've been continuously optimizing my first project so that I can run ever-larger experiments. The project boils down to two main problems:

• searching a list of high-dimensional sparse vectors for nearest-neighbour pairs; and
• keeping track of the sets generated by merging those pairs.

In the process, I've cut the runtime for runs against the GALE 2008 Chinese-English corpus from something like millions of years to a couple of hours.

(If the preceding part made absolutely no sense, you might want to stop reading now.)

Lesson The, er, Zeroth. Take advantage of sparse data.

This should be obvious - if I can ignore the holes in my data rather than trudging through each one, it can only help efficiency.

Lesson The First. boost::tr1::unordered_map is not always preferable to map.

The latter beats the former hands-down in iteration, and the ordering property of a map permits more efficient linear sweeps for a variety of iteration-based algorithms - sparse-vector arithmetic, for example. In some cases, a sorted array might be better still.

Lesson The Second. Use the structure that fits the problem best.

The second problem above is a classic use case for the disjoint sets structure. Using anything else is a recipe for gross inefficiency - you can't beat the amortized inverse Ackermann cost for all operations.

Lesson The Third. You can make file output faster.

std::endl flushes the write buffer - unless you need the output immediately, use "\n" instead. Dump large structures in compact binary formats where possible. If you go this route, test that your read/write operations undo each other; this sanity check prevents most nasty surprises. If you're really in a pinch, use <cstdio> instead of <iostream>.

Lesson The Fourth. Consider using heuristics.

Do you really need an exact answer? Most of the time - especially when dealing with massive datasets - the answer is no. Look for small assumptions or shortcuts that work for your dataset. For instance, when performing the nearest-pair search, I only consider pairs that have non-zeros in the same coordinate at least once. This works well with the sparse representation, allowing me to search over a sub-quadratic number of pairs.

So You Think You Can Sort

Selection sort. Insertion sort. Quicksort. Mergesort. All are standard fare in your average basic-level CS class; the first two are inefficient but conceptually simple, whereas the last two are decent general sorting algorithms. This is all good and well, but no one uses them for performance-critical applications:

• Often, a sort is not required; what you really want in most large-scale cases are the top k results for some relatively small k.
  
• Real-world data has patterns that general algorithms like your standard library quicksort fail to exploit.
• Comparisons and swaps aren't always cheap.
  

For you C++ programmers, the first point means little more than the difference between sort and partial_sort. The second point, however, is slightly more subtle.

As a simple example, suppose you have a billion integers to sort, but you know that each one is between 1 and 100. With that restriction alone, you can easily sort them in O(n) time. Other examples:

• The data are k-sorted (i.e. A[i] >= A[i-k].)
• The data aren't quite sorted, but they are unique; furthermore, abs(A[i] - A[i-1]) < k.

The third point might seem like a dubious proposition, especially that part about swaps. How can swaps be expensive? If I want to swap complex structures, I use pointers. Simple, right?

A while ago, I wrote a DHTML table sorter (for fun, naturally!) For reference, here's a standard quicksort implementation. Ignoring the horrendous colour scheme for a moment, why is the first one so much faster? Simple - it avoids swapping DOM elements. (There's a reason it's called permutation quicksort!)

Fine. So we can guarantee O(n) swaps in exchange for linear memory overhead. How do you limit comparisons? Remember that second point - notice patterns.

At Last!

Yeah, I know. Problem 117 is easy. IMHO, it's ranked "harder" than other problems simply because the requisite formulae for many of these questions are easily found using a combination of Wikipedia, MathWorld, and Sloane - which is not to say that the implementation part is always trivial!

So close!

98 questions, 2 to go.