Jump to content

  • Log In with Google      Sign In   
  • Create Account






Make a mathematical vector class already!

Posted by Splinter of Chaos, 22 August 2011 · 587 views

I can't count the number of times i've gone on to a forum and seen code like this: (Using a modified example from gafferongames.com)


posX = posX + velX * dt;
posY = posY + velY * dt;

velX = velX + (forceX/mass) * dt;
velY = velY + (forceY/mass) * dt;
I'm going to use this space to explain why such code is bad, especially in more complicated examples, and how simple it is to make it better. First, i think it would be clearest if i simply showed how this looks if posX and posY are represented by a vector, pos, and do they same for vel and force.

pos = pos + vel * dt;
vel = vel + (force/mass) * dt;
Obviously, this is simpler, cleaner, and more readable.


Why this code is bad.



You have to write twice as many lines of code than necessary, for 2D, and three times for 3D. Even using vectors, a complex physics equation, for example, might take 5 lines, which means 15 lines using 3D math without vectors. You have to make redundantly names variables (posX, posY; redundancy highlighted). It's harder for people to read your code, and for you to maintain it since the lines have to do the exact same thing.


Vectors basically take multidimensional equations and lets you evaluate them on one dimension.


What is a vector?


A vector is simply a piece of data representing both a direction and magnitude (or length). The most obvious way to represent that is through a polar vector. While out of the scope of this log, a polar vector is one around a pole, simple enough, with a distance from the center and an angle from an arbitrary axis.

A vector used more often in games is simply represented by an (using a 2D example) x and y like so: <x,y>. We can find the magnitude with sqrt( x*x + y*y ) (Pythagorean Theorem) and the direction from the x-axis by using atan2( y, x ). Even though it contains neither a magnitude or direction, directly, we can derive those values from x and y and thus they make a vector.

For an example of a vector: say you had a screen object at (1,1). That's the position vector, s, <1,1>. If next from you want it to move one unit left, that means its velocity vector, v, is <1,0>, 1 for one unit left and 0 for no movement in the y direction. s + v = the position next frame. s + v = <1,1> + <1,0> = <1+1,1+0> = <2,1>. If a = <x,y> and b = <q,w>, a + b = <x+q,y+w>,


Vectors are incredibly easy to write! (Without a lot of knowledge about math.)


The simplest vector implementation, in c++, is this:


struct Vector {
    float x, y;
};
With this, posX and posY become pos, but would not make the above example any prettier. What it does do is simplifies writing a class. One with a position and velocity should have two members (pos, vel), not four (posX, posY, velX, velY). To really see any gains, we need to start adding functions that do common calculations on vectors. For example, adding to vectors:
Vector add( Vector a, Vector b ) {
    return { a.x + b.x, a.y + b.y };
}

// ...

Vector velDt = { vel.x * dt, vel.y * dt };
pos = add( pos, velDt );
Although the intent of this code is not quite as clear as a simple "pos = pos + vel*dt", it still looks better than seeing two lines of "x = x + velX*dt". Many languages do not allow what's called operator overloading, but c++ does and we can simplify the code further by adding two functions:

Vector operator + ( Vector a, Vector b ) {
    return { a.x + b.x, a.y + b.y };
}

Vector operator * ( Vector a, float b ) {
    return { a.x * b, a.y * b };
}

// ...

pos = pos + vel * dt;


Useful Functions




Aside the already mentioned ones, you should be equipped with at least a dot and cross product, a function to find a vector's length. When you begin to look up vector equations, these functions will come up a lot. To learn their meanings and uses is outside the scope of this, but: A dot product is the sum of two vectors with their like components multiplied and returns a scaler (non-vector) value: <a,b> * <x,y> = a*x + b*y. A cross product is used to find a vector tangent to both a and b.

//Using a 3D Vector class:
int operator * ( Vector a, Vector b )
{
    return a.x*b.x + a.y*b.y + a.z*b.z;
}

// Crosses only make sense with 3D vectors.
Vector cross( Vector a, Vector b )
{
    Vector c;
    c.x = a.y*b.z - a.z*b.y;
    c.y = a.z*b.x - a.x*b.z;
    c.z = a.x*b.y - a.y*b.x;
    return c;
}

// The square of a vector, v*v, is the dot product of itself.
Vector square( Vector v )
{
    return v * v;
}

// This can also be named "length" or "size".
Vector magnitude( Vector v )
{
    // Pythorous' theorem states the answer is sqrt( v.x*v.x + v.y*v.y + v.z*v.z ).
    // Notice that v*v = v.x*v.x + v.y*v.y ... so the above is equal to sqrt( v*v ).
    return std::sqrt( v*v );
}
<br class="Apple-interchange-newline">// Another name for sqrt(v*v). Often written ||v||.
// Note that |-5| = sqrt((-5)*(-5)) = sqrt(25) = 5.
Vector abs( Vector v )
{
    return magnitude( v );
}


Going Further



A vector class can be built to hold ints or floats, but sometimes one is more convenient than another for different situations. That means either you can write a vector for each type or make it templated. You might want a 2D vector for a 2D game, or a 3D vector for a 3D game. Again, you can make a different class for both, but doing that and one for int and float means four classes! Of course, for most situations, you only need a 3D class and just set z to zero if you're making a 2D game, but what if you wanted to make a 4D vector, the fourth dimension perhaps being time?

So, if you really need a robust vector class it needs to be templated by size, and type is convenient.

template< int Size, typedef T >
struct Vector
{
    // Provide typedefs to be able to reference the types this class uses, externally.
    typedef T value_type;

    // Do the same for the size.
    // static_size is barrowed from std::array.
    enum { static_size = Size }

    // Since the number of dimensions are variable, we must hold an array instead of individual members.
    value_type dims[ static_size ];

    // Overload [] so that dims can be accessed more conveniently.

    T&   	operator [] ( int i )   	{ return *(data + i); } 
    const T& operator [] ( int i ) const { return *(data + i); } 
};
Now, defining the operators on this class can be a little difficult. At times, i've written the operators as normal, templated, free function, but depending on the calling code, thanks to standard C++ function lookup rules, you'll get a weird error. Take this example, using the above class.

template< class T, int X >
Vector<T,X> operator * ( Vector<T,X> v, T a )
{
    Vector<T,X> vec = v;
    
    for( int i=0; i < X; i++ )
        vec[i] *= a;
}

int main()
{
    Vector<int,2> v; v[0] = 1; v[1] = 1;
    Vector<int,2> x = v * 5.4;
}
The error received on g++, version 4.2, is "error: no match for ‘operator*’ in ‘v * 5.4000...0625e+0’". It doesn't know to convert 5.4 to an int to match the function signature. When a conversion is required, neither the left nor right operator takes precedence. We can see that the float should be converted to a float, but the compiler doesn't know it shouldn't convert the vector to a Vector<double,2>!

We could rewrite it to let the second argument be a different type, but we don't want that. In the + operation, a conversion has to take place whether vec[i] needs conversion to a float, then to be converted back to an int for storage, or a has to convert to an int. It just makes sense that the conversion should happen when the function calls.

I wish i could give a link that explains this problem better, or that explains why the solution i'm about to give works, but i don't. What needs to happen is the operator needs to be defined outside the class, but as a friend of it, defined inline. Again, this has to do with lookup rules.

The class must be defined like this:

template< class T, int X >
struct Vector
{
    T data[X];

    T* begin() { return data;   }
    T* end()   { return data+X; }

    T&    operator [] ( int i )      { return *(data + i); }
    const T& operator [] ( int i ) const { return *(data + i); }

    template< class T, int X >
    friend Vector<T,X> operator * ( Vector<T,X> v, T a )
    {   	
        Vector<T,X> vec = v;
 
        for( int i=0; i < X; i++ )
            vec[i] *= a;    
    }   	

    // More operators...
};

This is how i wrote my own class for my game. The code can be found at https://github.com/splinterofchaos/Orthello/blob/master/Vector.h




The problem I have with vector classes is that everyone has one. I've got projects on my drive that link to three or more libraries that all include their own vector classes. Whose vector class do I use? When I write a stand-alone library that can be used by others, do I include yet another vector class? What about gluing various libraries together? Do I need to write converters to convert between vector classes to ensure that alignments between implementations are the same? And so forth. I really want One Vector Class To Rule Them All, and for everyone to use it.
I have settled on using CML for everything, on that basis. Of course, I still have to translate a little at library boundaries, but it at least means that all my projects going forward are consistent...

The problem I have with vector classes is that everyone has one. I've got projects on my drive that link to three or more libraries that all include their own vector classes. Whose vector class do I use? When I write a stand-alone library that can be used by others, do I include yet another vector class? What about gluing various libraries together? Do I need to write converters to convert between vector classes to ensure that alignments between implementations are the same? And so forth. I really want One Vector Class To Rule Them All, and for everyone to use it.


Well if you're using DX, the obvious choice would be to use D3DX, which gives you vectors, matrices, the whole package.
I haven't touched DX in 10+ years or so, maybe longer. That won't be changing any time soon. ;)
CML seems interesting. Looks like it has features to facilitate inter-operation with other math libraries. Thanks for the link, swiftcoder.
Interesting that Vector types came up as "featured member journal" topic twice in a row now :D. I also tried to find an established vector library to base my tools on, since it's kinda nonsensical to choose a vector class from a "non math" library. Why would you base a Quadtree that also has uses outside of graphics stuff on a vector type that depends on say DirectX... that just doesn't make sense to me. For a short while I tried using Eigen. But Eigen has the advantage/constraint that it uses vectorization and therefore needs aligned data which makes it nontrivial to use as members of classes and in containers. Using my own Vector class actually IS my solution to coping with the heterogeneous library landscape since I can provide a way to connect all the different libraries I use myself.

Shameless plug: I also added a short section about this to my second journal entry about Vector and Matrix classes
Wow, i'm really surprised this got read at all! I only wrote it to link to whenever i'm in a discussion with someone not using them and it's unfinished and doesn't have a "further reading" section or anything. Thanks for the comments!

The problem I have with vector classes is that everyone has one. I've got projects on my drive that link to three or more libraries that all include their own vector classes. Whose vector class do I use?


I know what you mean. This bugged me when i used DX and again when i tried Irrlitch. I try to use my own whenever possible because it's more generic than any ive seen before it. Though Japro's looks similar.


September 2014 »

S M T W T F S
 123456
78910111213
1415 16 17181920
21222324252627
282930    
PARTNERS