Sunday, November 06, 2005

Opinion: A Farewell to Angles

This story was on Slashdot recently. While the guy might be seen as a bit of a crackpot I'm coming round to his point of view. As a worker in the field of computer graphics I'm frequently faced with software that performs operations like finding the angle, theta, between two normalised vectors, by computing the inverse cosine of the dot product. And yet later down in the code the angle is used only as the argument to further trig functions. Trig functions are expensive to compute. If you know the cosine and the quadrant of an angle then you immediately also know the value of all of the angle's other trig functions by some elementary computations involving the four elementary operations and square roots. These are far cheaper to compute than trig functions. And yet programmers frequently insist on working with the angles themselves because they are familiar with them.

As an extreme example: I recently optimised a block of someone else's code in which a point (x,y) was rotated through an angle π around (0,0) by converting it to polar coordinates, adding π to the angle and then converting back to rectangular coordinates! (Incidentally, this block of code was hard-coded for this one particular rotation, and there were similar blocks of code for π/2 and -π/2 rotations.)

It seems to me that people learning computer graphics need to learn that there are many operations that can be performed without using angles. There needn't be a reflex action to convert any dot product to an angle. Converting to an angle this way may also have unfortunate numerical inaccuracies, especially when the angles are converted back to trig functions again later in the code. Maybe I'll put together a document with a list of things you can compute given the sines, cosines and tangents of angles without having to evaluate a single trig function.

The issue is that the word 'angle' has two meanings. One sense of the word 'angle' is a set of equivalence classes of intersections between two lines. The pair of intersecting lines (A,B) and the pair (C,D) are said to be equivalent if there is a rigid motion of space that transforms A to C and B to D. There are a number of easily computed invariants we can associate with these classes, but the most popular one is called 'the angle' and is often horrible to compute as it typically requires the use of transcendental functions. Unfortunately, as soon as people think 'angle' they also think 'the angle' and are led to use these functions unnecessarily. (It's worse than this, 'the angle' properly lives on S1 but people work with the cover of S1, R, leading to troublesome ambiguities.) It seems to me that other invariants besides 'the angle' ought also to be taught. And that is what this book seeks to do, despite its crackpot trappings.

No comments:

Blog Archive