Updated 11 Jul 2001
- QuArK Information Base
- 4. The Source Code
- 4.9. Math Background
|[- - ]|
Here is a rather short introduction to vectors, in certain respects rather philosophical, but also with reference to QuArK's vector facilities. The first few chapters of books on 'vector calculus' are a good source for this kind of material, although fortunately there's little need to wade very far into them (I learned a lot from Marsen & Tromba (1976) Vector Calculus, Freeman and Co., the material here being covered in Chapter 1).
Vectors and Points
|tiglari - 11 Jul 2001||[ Top ]|
'Vector' means 'carrier' in Latin. Hence rats as plague vectors. In mathematics, the most basic meaning is a relationship between two points, namely, the displacement that would carry one into the other, and also a sequence of numbers representing that displacement, such as 2 units forward, 3 to the left and 1 up, giving the vector <2,3,1>, or quarkx.vect(2,4,1) in QuArK Python programming. We'll call the relationships between points 'geometric' vectors, the sequences of numbers 'sequence' vectors (this isn't standard terminology, but I find it useful). Since only the sequence vectors can be manipulated by computer programs, in a sense they are the only ones that are relevant, but on the other hand what the programs are doing is helping people to build their spatial imaginings, so I personally think it's helpful to have a solid grasp of the relationship between the sequence vectors and the geometrical ideas they represent.
Geometrical vectors can be 'added' in the sense of performing one displacement after another, and also multiplied by numbers, in the sense of performing the displacement a (possibly fractional or irrational) number of times. Similarly, the sequence vectors can be added by adding the numbers in the corresponding positions, or multiplying all the numbers by the same number:
In jargon, for sequence vectors, addition of vectors and multiplication of a vector by a 'scalar' (an ordinary number, in context where vectors are the focus of attention) are defined 'componentwise'.
<x, y, z> + <u, v, w> = <x+u, y+v, z+w> a*<x, y, z> = <a*x, a*y, a*z>
The components are of course the individual numbers, and if v is a QuArK vector, we can get its first, second and third components as v.x, v.y and v.z respectively (there are also 5-component vectors for use with bezier patches, with .s and .t in addition, but we won't worry about those here).
If we're using the number sequences to represent displacements, we can see that the algebraic definition agrees with our intuitive conceptions of how addition of displacements and the multiplication of a displacement by a number should work, and if you crank through the algebra you should be able to see that all of the standard sequence laws such as commutative and associative work, for those combinations to which they are applicable. For example:
Vector algebra or calculus textbooks will give complete lists, but basically it's just Junior Hi-level algebra.
(a+b)*(v+w) = a*b + a*w + b*v + b*w a*(b*v) = (a*b)*v = (b*a)*v = b*(a*v)
And in QuArK python, + works for vectors, and * will combine a vector and a float, the only difference from standard math notation being that you can also put the float second, or use the division symbol in the usual way:
(if v is a vector and a is a float).
(1/a)*v == v*(1/a) == v/a
It is also usual for vectors to be used to represent points, but there's a issue here: it makes no sense to add points to each other, or multiply them by numbers. What's going on is that to represent a point by a vector, we first need to pick a special point called the 'origin'. Then we can use vectors to represent other points as relationships to (i.e. displacements from) the origin.
So at this point we have three somewhat different kinds of things floating around:
To get a geometric vector from a point, we need an origin point; how do we get an sequence vector from a geometric one? What we need is three vectors of length one, all perpendicular to each other, taken in a definite order. This is called an 'orthormal basis', 'ortho-' meaning perpendicular, 'normal' meaning of length one, and 'basis' being a math term whose true meaning we won't reveal quite yet. The vectors in the basis are by convention associated with the x, y and z axes, and often designated as i, j and k in 3D math books. Given an orthonormal basis, we can represent a geometric vector by the sequence of numbers indicating how far you go in the direction of each vector of the basis, taken in order.
It's an essential point that the representation of geometrical vectors by sequence vectors has an arbitrary aspect: given a different choice of basis, there will be different numbers. Suppose for example we have an orthonormal basis i, j and k, and replace j with -j. What will happen to the sequence vector representing a given geometric one?
To represent a geometric vector with an sequence vector(in the standard way; there are some other possibilities), we need an orthonormal basis, but we don't need an origin. But to represent a point as an sequence vector, both an origin and an orthonormal basis is required: the origin lets us represent a point with a (geometric) vector, and the basis lets us represent the geometric vector with an sequence one. We find out more about this in the next section. an origin with an orthonormal basis is a 'coordinate system'.
Coordinate Systems and the Dot Product
|tiglari - 11 Jul 2001||[ Top ]|
The dot product (also sometimes called the 'inner product') might be the leading 'value for money' vector operation, since its definition is simple and its results extremely useful. For sequence vectors, we can define it like this:
In other words, to compute the dot product of two vectors, multiply their corresponding components, and add the results.
<x,y,z>*<p,s,t> = x*p + y*s + z*t
In QuArK python, the dot product is represented by the '*' symbol, so that if u and v are vectors, 'u*v' will be their dot product, a number. If you crank through the definition, you can work out that the dot product obeys many (but not quite all) applicable instances of the associative and commutative laws, such as (where u and v are vectors, and a is a number):
One that doesn't work is:
u*v = v*u a*(u*v) = (a*u)*v (a+b)*u = a*u + b*u a*(u+v) = a*u+a*v
where u, v w are all vectors.
(u*v)*w = (u*w)*v (NOT!!)
One aspect of the geometric significance of the dot product is that we can use it to compute the length of a vector:
This follows from the Pythagorean formula for the hypoteneuse (long side) of a right triangle, generalized to give the diagonal of a box. However we don't actually have to know this for QuArK Python, since the abs() function delivers the length of a vector. Also in QuArK Python, the square root function needs to be preceded by 'math.', since it's part of the math module, so we can render the above equation into an always-true QuArK Python statement as follows:
length(v) = sqrt(v*v)
This illustrates a very important feature of the dot product, which is that even though we compute it from coordinates, which depend on a choice of a basis, it is actually independent of the exact choice of basis: no matter what basis we chose to get an sequence vector w representing a geometric vector v, the dot product w*w will be the same. This means that we can think of the dot product as a property of geometric vectors, as well as sequence ones.
abs(v) == math.sqrt(v*v)
A further essential fact about the dot product is that if the dot product of two sequence vectors is zero, then the geometric vectors they represent, with respect to any coordinate system, will be zero. So we have a fast and easy to compute test for perpendicularity. A typical application is determining whether a point lies on a plane.
One way to represent a plane is to pick one vector p representing a point on the plane (it doesn't matter which one), and another vector n to represent a 'normal' to the plane, that is a line perpendicular to it. (If (If the plane is thought of as dividing space into an 'inside' and an 'outside', there is an essentially arbitrary convention that the normal sticks into the outside. So the direction handles sticking out of faces in QuArK are normals to the face plane, pointing in the conventional direction). The plane will then be defined as all points v such that the vector from v to p is perpendicular to n. And given a point v, we can test it for lying on the plane by seeing if n*(p-v) equals the 0 vector <0,0,0>.
The <0,0,0> vector evaluates to 'false' in a QuArK Python conditional, so a piece of code might be:
Recall that when we're using vectors to represent points (v and p), we're assuming a prior choice of origin, but n is a direction, so doesn't require an origin, and notice that p-v will be independent of the choice of origin, since if you move the origin by say some vector d, d will be addeed to both v and p, and so cancel out in their difference.
if not n*(p-v): # if v lies on the plane defined by p, n [do something]
The perpendicularity test provided by the dot product is a consequence of something more general, which we push on to investigate.
Suppose we have two vectors, u and v, which we represent as lines in space going from an arbitrarily chosen origin to the point that the vectors relate to that origin, and we draw a line from the end of u so that it intersects the line that v extends along, and is perpendicular to v. The relation between the origin and this intersection point is then a vector, which might point in the same direction as v, or the opposite one.
This vector is called 'the projection of v onto u'; note that it depends on the length and direction of v, and the direction of u, but not on the length of v. The big news is that projection of u onto v, which we've defined geometrically, can be computed algebraically using the dot product:
The ability to compute these projections is something we can put to use in various ways.
proj(u,v) = ((u*v)/abs(u))*u
Suppose we have a point v, and a plane defined by a point v and a normal vector n, and what we want to do is to 'project' the point v to the plane along the plane's normal, that is, find a vector that is perpendicular to the plane that will take v onto a point in the plane (this might be part of a routine to attach an object to a face, for example). Now we already have one vector (p-v) that will take p onto the plane, but this isn't the one we want because it might not be perpendicular to the plane. But we can fix this by projecting (p-v) onto the normal. The resulting vector will be parallel to the normal and therefore perpendicular to the plane, and the line connecting its end to v will also be perpendicular to the normal, so its satisfies the test above for being on the plane (you should try to visualize this too, to see intuitively that it makes sense).
And since plane normals, including the output of face.normal in QuArK Python, are by convention of length 1, we can drop the abs(u) term from the computation, and find the vector proj taking v onto the plane by computing:
And if we want the actual point, we just add proj to v.
proj = ((p-v)*n)*n
A more general version of this is to project a point to a plane along any normal; that's what the procedure projectpointtoplane in quarkpy.maputils does. The idea behind that code is to take two dot products of the plane normal, one with the vector from the point we're projecting from to the point that defines the plane, the other with the vector we're projecting along. These are used to compute a ratio, by which the 'along' vector is multiplied to produce the projection vector.
A final, easier, example is the 'perptonormthru' procedure, also in quarkpy.maputils. Here the idea is that we're given a 'source' point, a (sort of) 'destination' point, and a normal vector thru the destination point. The idea is to find vector that's perpendicular to the normal, going from source to a point on the line of that normal (so the destination) is only a sort-of destination. So the idea here is to compute the projection of (source-dest) onto norm, then subtract that from (source-dest) to get the desired answer. This procedure is used in various ways, for example in computing the circumference of prism-shaped brushes with irregular ends in the texture-wrapping code.
And finally we come to the most general and important application. Suppose u is coordinate axis of a basis. Then u*v is v's coordinate for that axis, w.r.t. the basis. So out of all of this we have gotten a way to compute the coordinates of a vector w.r.t a new coordinate system. This is very convenient. Suppose we've worked out the coordinates of a bunch of points, and suddenly decide that we need them w.r.t a different coordinate system. It would be annoying to have to pull out our surveying gear and measure everything again, but thanks to the dot product we don't have to. All we have to do is get the coordinates of the new origin (w.r.t the original coordinate system), call it o, and of the new basis vectors. If v is an sequence vector representing a point in the old coordinate system, and ax is an axis vector of the new basis, then (v-o)*ax will be v's ax-coordinate in that basis, also with three computations of this nature, one for each of the new axes, we can get the new coordinates.
The Cross Product
|tiglari - 06 Jul 2001||[ Top ]|
Now we move on to a rather more complicated operation, the cross product. What this is useful for is finding vectors that are perpendicular to other vectors. Unfortunately most of the applications of this in the code seem to be involved with more advanced things such as matrices, but hopefully these basic facts will be useful, especially that when a cross product is used, the motive is generally to find a vector that's perpendicular to two that are already in hand.
The full algebraic definition of the cross product is rather complicated, and for QuArK programming, there's no real reason to know it, since it's computed by the '^' operation: 'u^v' is the cross-product of u and v. But although we don't need to know how to compute it, we do have to know something about its properties.
The most important property is that if u and v don't lie on the same line (which implies that neither is the 0 vector), then u^v is perpendicular to both u and v. Otherwise u^v is the 0 vector (and isn't really useful for anything, afaik). Another useful fact is that if u and v are the unit vectors along the x and y axes, respectively, then u^v is the unit vector along the z axis. Since these unit vectors are standardly designated i, j and k, we have:
i ^ j = k
More generally, we'd like to know how to tell:
If you work through this you'll see that there is a consequence that u^v does not equal v^u, but point in the opposite direction, so we have:
There are other algebraic facts about the cross product to be found in math books, but I have yet to find them useful for QuArK Python.
u^v = -(v^u)
The cross product can not only be used to manufacture a z axis from suitable x and y axes, but it can also be used to make an orthonormal basis from any two non-colinear vectors. Suppose we have u and v, and want u to be the x axis, and v to lie in the xy plane. Then we can get the direction of the z axis by taking u^v, and given the z axis, we can get the direction of the y axis as (u^v)^u. Symbolically, using i, j, k as the unit vectors for the three axes:
i = u.normalized j = (u^v).normalized k = j^k (normalization not needed here)
Copyright (c) 2009, GNU General Public License by The QuArK (Quake Army Knife) Community - http://quark.sourceforge.net/
|[ Top - ]-|