Thursday, January 29, 2009

Are points and vectors (and normals) different?

I'm teaching a computer graphics course right now. This is an expanded version of an answer to a question posed by both a student and a very smart ta:

Are points and vectors different? We teach coordinate free geometry in our graphics course, so we say yes. The idea doesn't always sit well with people with a strong math background, as opposed to a geometry background.

It really depends on your point of view of the world. In graphics, we need to be careful about how we transform things, to make sure we transform them correctly.

From the mathematical vector space point of view, all points can be represented as vectors, with the implicit assumption that they have an origin at zero. So yes, points are vectors contained in a mathematical vector space.

When we transform geometry, we need to make a distinction between locations in space (points) and directional offsets with magnitude in space ("vectors"). It sort of overloads the terminology a bit, but the direction with magnitude does not change as we translate around, while the location does--this is why we make the distinction. This is all part of the coordinate free geometry point of view. It says that we establish points and vectors as separate entities and make them behave differently with transformations. Then, define the basic operations between them to keep the difference straight. So a location plus an offset in some direction with some magnitude gives you a new location. Normal vectors give you yet a third way of transforming things.

When you write code, you have two choices: make the distinction or don't. If you don't make the distinction, you have one 3-component data type usually called a "vector." And then, whenever you transform stuff, you have to make sure you transform it the correct way, so your code has to keep track what geometric thing you have stored in that vector. So you have to do some kind of type checking and make sure you get it right whenever you write new code that deals with transformations. Something like

if v is a vector:
v' = transformAsVector(v)
else if v is a point
v' = transformAsPoint(v)
else if v is a normal
v' = transformAsNormal(v)

Keeping track of what v is gets way more tedious when you are adding point-vectors to vector-vectors, and so on.

If you make different data types for points, vectors, and normals, you can write one transform operation that does this checking internally or through c++ operator overloading, and you never have to think about it again in your code. And if you implement operations like p+v = p correctly, you don't have to keep track of what geometric thing you have. Geometric algorithms do a lot of point-vector algebra, and keeping track of what's what inside your geometric code is tedious and bug-prone. And you get one line of code to transform something:
v' = transform(v)

We teach the CFG point of view because you need to know the difference to do geometry correctly, it can make your geometric derivations easier to think through, and it can make your code significantly shorter, easier to read, and a lot less bug-prone.

There's also another level to CFG that recommends encoding the space of the coordinates with the point and compensating for spatial difference inside, for example, the point + vector operation. This is rarely implemented (I have only seen it done in the paper below), since most geometric algorithms deal with all their data already in the same space.

In my code, I break one CFG rule. I allow point + point addition. Adding two locations is geometrically meaningless. I have some data filtering code that I want to be type-independent. The filtering, when you think about it, is really doing barycentric combinations of points. But then we're back to the question of "should the filtering code do type checking to call a barycentric combination operation when it encounters points instead of scalars or vectors?" Then the code gets hard to read, and it requires me so hunt down whatever I named the barycentric combination operation when I wrote it two years ago. So points can be added to points, and we still get to write a simple smoothing filter as:
s[i] = 0.5 * s[i] + 0.25 * s[i -1] + 0.25 s[i + 1]
(s is a point sample).

About CFG: A Coordinate Free Geometry ADT. Stephen Mann, Nathan Litke, Tony DeRose. 1997

No comments: