I''ve been working on an implementation for a point class. Lately my work has slowed down when I read the following dealing with operations one can and cannot perform on a point. What the hell, I always thought you could multiply points by scalars and not look back. Now i''m reading stuff about affine points blah, blah. Could someone please make sense of all this. Thank you. **************************************************************** For example, computing the midpoint of two points P and Q can be accomplished as: aPoint Mid = 0.5 * (P + Q); Don''t forget the "caution" note above. Recall that many of these operators are defined here for convenience and are not individually meaningful. It is up to the user of these tools to make sure that the overall expression is valid. The midpoint operation immediately preceding this paragraph uses invalid operations, for example. Using only the operations defined for points and vectors in affine spaces, we should have computed the midpoint as: aPoint Mid = P + 0.5*(Q - P); Allowing these and similar liberties for individual operations is often convenient. Multiplication of a point by a scalar, adding points, and similar invalid operations are defined below simply because using them is oftentimes the most convenient, clear, and even computationally efficient way to compute desired quantities. The price for this convenience, however, is that care must be taken to ensure that quantities ultimately computed for subsequent use are meaningful. ****************************************************************

Affine space is what lets two identical vectors have different end-points. With just 3D matrices, everything starts from an assumed origin (often called projective space). By using 4D matrices, we can place translations in the extra space. This allows a rotation to occur around a point that is not the origin and allows the shearing of an object (which is used in the perspective portion of the graphics pipeline).

So, if you are working in affine space, you''re not really working with 3D points, but 4D (affine) vectors.

The operations you perform on such a matrix (a list of vectors is a matrix), ought to be restricted to those that make sense, scaling, rotation, translation, shearing, etc... And each type of transformation has a particular matrix form, so that the correct components of the 4D affine vectors are manipulated by the correct values. i.e. to translate, you only affect one of the rows of the matrix (or column, depend on whether you have row-major or column-major matrices) not the whole thing.

So in game and graphic programming, when does this affine space stuff matter?

[edited by - kelaklub on July 21, 2003 12:45:21 PM]

The comment by Magmai Kai Holmlor is not right in some things. There is no need to add extra dimensions for affine geometry; it''s projective geometry that needs an extra dimension, but that doesn''t have anything to do with the original post. Let me try to clarify a little bit.

Linear algebra deals with vectors, which are things that can be added and scaled. The kind of vectors used in game development tipically represent "moves". Let''s think of a 2D game. Moving one meter in the North direction can be represented as (1,0), and moving one meter in the East direction as (0,1). (-1,0) would be moving one meter South, etc. You can add these moves, getting the composite move, like (2,0) + (-1,0) = (1,0) (moving two meters North and one South is like moving one meter North). You can also scale a move, multiplying both components by a scalar.

Notice that vectors represent moves, not positions in the map. Positions are represented by points, but now we need to introduce affine geometry.

In affine geometry, points and vectors are different things. Vectors have the usual operations on them (addition of two vectors and multiplication of a vector and a scalar). You can add a point and a vector, the result being another point. You can also substract two points, getting as the result the vector that, when added to the first point would give you the second. Adding points is not very meaningful (What''s the sum of where I am and where you are?).

How do we represent points? We take a reference point, which we call the origin. We can reach any other point by adding a vector to the origin, so we use the representation for that vector to represent the point. So in our map example, a point will also be a pair of real numbers, just like a vector. You may be tempted to add two points or to multiply a point by a scalar, because you can do those operations to the vectors that represent points. This has two problems: 1) The result is not very meaningful, and 2) The result depends on the selection of origin that we made.

There are some operations on points that are meaningful, like finding the middle of two points, A and B. This can be done by finding the vector B-A, scaling it by .5 and adding it to A.
M = A + .5*(B - A)
This is a good definition, because we have only used valid operations. If you look at what happens in terms of coordinates, you will see that you could have done this just by taking ".5*(A + B)". As I said, A + B is not well defined, because the result depends on the selection of origin. But when you compute .5*(A + B), the result doesn''t depend on the selection of origin.

When programming a game, you can either define one type for vectors and a separate type for points (with only legal operations defined on them), or you can use class vector to represent both (which I think most people do), although that allows you to write things that don''t make sense, like addition of two points. It''s mostly a trade-off of strict typing versus convenience.

Actually, I am working on a point and vector class, and the vector class will be able to access the point class and vice versa. So are you saying that if we wish to multiply a point by a scalar, we first get the vector from the origin to that point, then we multiply the vector by the scalar, and then add the scaled vector to the point?

[edited by - kelaklub on July 21, 2003 5:30:06 PM]

It simply doesn''t make sense to multiply a point by a scalar. It does make sense to multiply a vector by a scalar. When you think of multiplying a point by a scalar (an operation that doesn''t make sense) you are thinking of multiplying the vector from the origin to that point by a scalar, and the result is dependent on the position of the origin.

It is usually just easier to use vectors to represent points (just be sure to keep track of what is a vector and what is a point).

How would would one treat a vector as a point and at the same time differentiate a vector from a point?

I think what Anonymous Poster was suggesting is to use the same data structure to represent both points and vectors, and just keep in mind which instances represent points and which instances represent vectors.

---

To expand on what the others said:

An affine combination of, say, points A₁, A₂, ..., A_n, is any such sum

a₁A₁ + a₂A₂ + ... a_nA_n

(a₁, a₂, .., a_n are all scalars)

such that a₁ + a₂ + ... + a_n = 1.

Now, as others said, it makes little sense to add two points in the general case, since basic operations like addition no longer hold independant of the choice of origin.

E.g., say we have two Cartesian coordinate systems, one with origin O, and one with origin O''=[o''x,o''y,o''z] with respect to O. Thus to transform from the O-origin system to the O''-origin system, we use the following function:

f([x,y,z]) = [x-o''x,y-o''y,z-o''z]

And of course to go from the O''-origin system to the O-origin system:

g([x,y,z]) = [x+o''x,y+o''y,z+o''z]

Now say we have two points A and B. A''s co-ordinates in the O-origin system is P=[px,py,pz], and in the O''-origin system is P''=[p''x,p''y,p''z]. B''s co-ordinates in the O-origin system is Q=[qx,qy,qz], and in the O''-origin system is Q''=[q''x,q''y,q''z].

Now if we "add" A and B in the O-origin system, we get P+Q=[px+qx,py+qy,pz+qz], but if we transfer into the O''-origin system, perform the "addition", and transfer back into the O-origin system, (which should intuitively give the same answer) we get P+Q-O[px+qx-o''x,py+qy-o''y,pz+qz-o''z]. Thus addition (in the general case) depends on the choice of origin.

However there is a special case for which the result does not depend on the choice of origin -- affine combinations (you should be able to prove this yourself). Thus, in some cases addition does make sense. It can also be shown that an affine combination can be expressed as a sum of one point and some vectors. Geometrically, an affine combination of two points gives a point on the line segment joining the two points, an affine combination of three points gives a point in the triangle whose vertices are the three points, and so on.

As an aside, you may notice that homogenous co-ordinates satisfy this perfectly. If we represent a vector as [x y z 0] and a point as [x y z 1], then clearly any affine combination of points is another valid point.