1. The shape’s centre of rotation was wrong
2. Each edge was being drawn twice, once for each face containing that edge

Fixing the first was easy – just make sure the centroid of the shape gets calculated at load time. The centroid for a 3-dimensional shape is just the average of the X, Y and Z values respectively.

Fixing the second was a bit trickier. We want to keep a list of edges so we can mark off the ones that have been drawn as we go along. The shape data doesn’t contain edges (only faces and vertices), so we have to build the edge list when we load the shape. I decided to use a hash (or dictionary) to store a key for each edge in the shape, where each edge key is just a string built from the 2 vertex numbers. I made sure the smaller vertex number is first to make sure each edge is unique. Typical edge keys look like 10_17 or 7_21. At the start of each frame we set each edge value for each edge to false. When we draw the edge we set the edge value to true. If we go to draw an edge that has already been marked true, we skip it. This means that every edge only gets drawn once.

It’s a bit expensive to do this key checking every time, but it seems to be quicker than actually drawing the edge. I haven’t benchamarked this, it’s just subjective from running the code on an ipad. Benchmarks to follow. In the meantime, check out the demo (now with added asp!).

We decide which faces are pointing towards the viewer using a vector cross-product. The cross-product of 2 3-dimensional vectors is another vector whose direction is at right-angles to the first 2. So the cross-product of 2 vectors along a face points directly away from the face. If the cross-product vector has a negative Z-component, it is pointing towards the viewer (we define the positive direction of the Z axis as pointing into the screen) and thus we should be able to see the face.

The good news is that we’re only interested in the Z component of the cross-product, which simplifies matters considerably. Given a list of points (p0, p1, p2, ....) that define a face, we create 2 vectors A = p0 - p1 and B = p2 - p1. If the components of A and B are (ax, ay, az) and (bx, by, bz) then the Z component of A x B is

(A x B)z = ax * by - bx * ay

Substituting p₀ etc. back into the equation above, we get

z_component =
(p2[0] - p1[0]) * (p0[1] - p1[1]) - (p0[0] - p1[0]) * (p2[1] - p1[1])

This technique works well for convex shapes. A shape is said to be convex if a straight line can be drawn between any 2 points inside the shape without the line ever crossing the boundary of the shape. Because of this, I commented out the gun/antenna part of the ship – the remaining part of the ship is convex. Have a look at the results here.

There is still 1 important thing missing – perspective. At the moment, the ship is the same size no matter how far away from the viewer it is. We’ll have a look at this next time.

The previous version of the code was very simple – just take 4 points and join them all to each other. This gives you a tetrahedron provided all the vertices aren’t on the same plane. For the case where not every vertex is joined to every other vertex, we need something a little more sophisticated. I pretty much followed the layout given in Neil Wallis’s data set, which defines a shape as follows:

1. a list of vertices.
2. a list of lists of indices into the vertex list – each sublist defines one of the faces of the shape.

If you view the source of shape.js you can see what’s going on. The ALL_SHAPES variable is a dictionary – each key refers to a different shape. In turn, each key refers to a dictionary with 2 elements – the vertex list and the face list. This is doubtless not very efficient but it’s simple (and simple is good!). The draw() method of the shape class simply loops through each face and draws lines from the first vertex through to the last (and back to the first to close the loop), in order.

A problem with this simple way of drawing is that the boundary between 2 adjacent faces will be drawn twice (once for each face), which isn’t very efficient. For the moment we’re going to ignore this issue – making the code fast is something we can do once it is working the way we want it to.

The next thing to do is back-face culling (or hidden line removal) – that is, removing the faces of the ship that are pointing away from the viewer. This will make the ship look more solid. There’s a tiny bit of vector maths involved, but not much. Next time!

In homage to the old-skool world of 3d wireframe graphics (and in an effort to learn some stuff about how <canvas>) works, I’ve written a super-simple rotating tetrahedron script. I’m planning to build this up into something a bit more interesting over the coming days and weeks, including:

• hidden line removal
• perspective
• more interesting shapes (there’s only so long you can look at a tetrahedron)
• rotation about other axes
• keyboard control (fly the ship!)

I’ll post my progress up here as I go along. I learned how to use canvas from the mozilla page and Bill Mill’s “how to build a breakout clone” canvas tutorial.
I’d recommend them both as places to start.

As you can see, there was a big spike around iterations 5 and 6 and a trough in iteration 9. The dip in iteration 9 was caused by paying off technical debt and resolving some deployment issues we hadn’t originally budgeted for. I hadn’t thought too much about what caused the surge in velocity around the middle of the project. At the time the attitude was “we’re going really fast, let’s just keep doing what we’re doing”. In hindsight I think the spike in velocity should have raised an alarm bell. Here’s why…

I am now working on a new project that reuses some of the work we did previously. Alas I have discovered that some of the code requires extensive refactoring. The current implementation of some features is both fragile and incomprehensible. There are methods that are hundreds of lines long (!) with no comments. There is hand-rolled code that duplicates the intent of library functions. Some functionality is poorly encapsulated and thus not reusable. All the usual suspects! SVN tells me that this code was committed when? That’s right, iterations 5 and 6 of the last project. It seems our gains in velocity came at the cost of maintainability.

All it not lost: the old code has pretty decent  test coverage, so at least the refactoring effort isn’t working blind. That said, I think our iteration retrospectives will in future check our velocity against our historical performance.  Up till now we’ve been pretty good at identifying the causes of slow iterations – from now on we’ll be having a look at what a fast iteration velocity is masking beneath the surface.

Django users will know that it’s possible to use callable objects instead of strings in URLconfs. One great use of this feature is to dispatch HTTP requests to different functions based on the HTTP verb. This turned out to be useful for me recently when I had to implement HTTP DELETE for some resources. Instead of having one big method like this

if 'GET' == request.method:
    ... do something ...
elif 'POST' == request.method:
    ... do something else ...
elif 'DELETE' == request.method:
    ... do somethign else ...

we can use python’s reflection capabilities and dispatch to different methods based on which HTTP verb was used. First we define a base class like this:

class HTTPVerbDispatcher:
    def __call__(self, request, *args, **kwargs):
        try:
            fn = getattr(self, "do_%s" % request.method)
        except AttributeError: # this method is not supported
            allowed_methods = [m.lstrip("do_") for m in dir(self) if m.startswith("do_")]
            return HttpResponseNotAllowed(allowed_methods)
        return fn(request, *args, **kwargs)

Any classes deriving from this will call a method called do_GET, do_POST etc. based on the value of request.method. We can create a class in views.py like this:

class BlogEntryView(HTTPVerbDispatcher):
    def do_GET(self, request, id):
        .... handle GET request - view object ...

    def do_POST(self, request, id):
        .... handle POST request - view object ...

    def do_DELETE(self, request, id):
        .... handle DELETE request - view object ...

Finally, we set up our URLconf to use the BlogEntryView callable:

from django.conf.urls.defaults import *

from myapp.views import BlogEntryView

urlpatterns = patterns('',
    (r'^(?P<id>d+)$', BlogEntryView()),
)

• changing the DocumentRoot
• using the Alias Directive
• using symbolic links from /var/www to the required location
• chmod -R go=rx path/to/my/files
• chown -R apache path/to/my/files
• Changing the User and Group apache runs under

All to no avail. By symlinking to my directory I could get apache to list directory contents, but trying to access any files within gave a 403 forbidden error. It turns out the problem was to do with SELinux – by default the security policy is set to ‘enforcing’. I changed the policy to ‘permissive’ and all was well.

It took me an embarrassingly long time to figure this one out – I thought it was caused by a combination of apache configuration and filesystem permissions, but it turned out the security policy had a role to play too.

The pictures in question appear in a slideshow on the site’s home page. There is a javascript component that fades the images into each other every 10 seconds or so. Using Live HTTP Headers I could see that every time the image changed a new HTTP request was being sent. On my machine I was getting a status code 304 and the image wasn’t being requested every time but it seems this wasn’t the case everywhere (local cache disabled? Badly-behaved browser? It’s hard to tell.). So, what to do?

I decided to take a belt-and-braces approach on this to prevent a recurrence (and to avoid incurring the wrath of the nice people at blacknight). The first thing was to have a look at the javascript and stop it requesting images unnecessarily. The original slideshow code worked like this:

1. clone the DOM node containing the first image in the slideshow
2. put the new image under the old one (using z-index and absolute positioning)
3. change the src attribute of the lower image to contain the URL of the next image in the slideshow
4. wait a few seconds
5. fade the upper image to 0 opacity
6. swap the Z position of the 2 images
7. set the lower image to full opacity
8. go to step 3

I could see that a new HTTP request was going out at step 3 above, even when it was reloading an image that had previously been displayed. So I changed the code to this:

1. clone the original image node N-1 times (for a slideshow with N images)
2. hide all but 2 images
3. put the visible images 1 on top of the other (using z-index and absolute position)
4. wait a few seconds
5. fade the upper image to 0 opacity
6. hide the upper image and increase the z-index of the lower image
7. unhide the next image
8. go to step 3

The new code loads all the images at once and makes no more requests once they are loaded. There are some obvious problems with this code

• what happens if there are hundreds of images?
  • there will be a stampede of HTTP requests which will inevitably lead to timeouts and missing images
  • potentially unlimited amounts of memory will be used to store all the images
• what if the wait period between displaying images is shorter than the time it takes to load them all?
  • once again there will be partially loaded/missing images

However, I’m a firm believer in the agile mantra “You’re not gonna need it“. For this application there are no more than 6 images in any slideshow, the images are all under 50kB and the wait time is about 10 seconds so the above problems shouldn’t arise. If I need to refactor in future, so be it.

Finally, I realised that I hadn’t configured apache to set the Expires header on images to a date far in the future. I added a couple of lines in the top-level .htaccess fileto make the images expire in 5 years. This means that on repeat visits to the site, if there is a copy of an image in your browser cache, the browser won’t even check to see if the image has been modified.

At my previous employer, ammado, we used an agile/XP hybrid approach to manage our work. It started off well but we ran into some pitfalls:

• the team got too big to manage effectively with a self-organising process.
  • the usual rule-of-thumb for agile is that it works for teams of up to about 8 or10 people. We had over 20.
• fetishisation of index cards.
• short-termism of agile allowed us to ignore architectural issues. Over the course of several iterations we built up substantial technical debt which caused progress to slow significantly.
• cultural resistance to pair programming led to less refactoring and more code duplication than we would have liked (pair programming keeps you honest!).

There were some positive points too:

• constant emphasis on shipping working code. Before we adopted the agile approach we spent a year making exactly zero releases. Afterwards we were releasing once a month.
• retrospectives after every iteration helped change my mindset (I can’t speak for the whole team, but I would like to think I’m not the only one who got this)  from ticking-off-items-on-a-requirements-list to how-can-I-make-this-team-work-better.

We are adopting a similar process here in ticket-text. We would like to maximise the positives and avoid the pitfalls outlined above. I’m going to keep track of how we are progressing here – hopefully we’ll all learn something.

* in case one of my millions of readers leaks it to the competition. Lolz!

class Pet:
    name = models.CharField("name", max_length=100)
    owner = models.ForeignKey(Owner, verbose_name=_(u"owner"))

class Toy:
    name = models.CharField("name", max_length=100)
    owner = models.ForeignKey(Pet, verbose_name=_(u"owner"))

This represents pet owners, each of whom may have zero or more pets. Each pet in turn may have zero or more toys. So far, so simple. Now suppose we want the owner to have a property saying how many toys in total she owns (the pets don’t really own the toys!). There are a whole bunch of ways to do this, but one neat way python/django makes possible is to change the definition of Owner to this:

class Owner:
    name = models.CharField("name", max_length=100)
    toy_count = property(fget=lambda self:sum([pet.toy_set.count() for pet in self.pet_set.all()]))

There are a couple of things going on here: properties, lambdas, list comprehensions and many-to-one relationships as expressed by django’s O/R mapper. Together they allow for some concise yet powerful constructs like the one above.