Tag: Points

Coordinate Systems

Believe it or not, all of the Math we’ve been discussing up until now has been leading us to this point. Now we have enough knowledge to introduce the Coordinate_space. In the Dubious Engine, a Coordinate_space represents an object’s position and rotation. Given what we’ve learned about Vectors, Points, and Quaternions, I hope it’s not surprising to see the data in the class:

class Coordinate_space {
    Point               m_position;
    Unit_quaternion     m_rotation;
};

That’s all we need to describe where an object is, and which way it’s facing. Before we take a look at how all the pieces come together to move one of these things around, let’s discuss “handedness.”

Right Handed Coordinate Space

I’ve been purposefully glossing over this subject up until now because I thought it was too much detail. But now that we’re finalizing our Math section, it’s time to discuss the ambiguity in our Z axis. From your earliest Math classes dealing with X and Y axis you’ve probably been told that the X axis goes from left to right, by which I mean +100 is further to the right then -100. Likewise you probably see the Y axis as going up (ie +100 is higher up then -100). But what about the Z axis? Does it point out of your computer screen towards you, or from you into the screen? Well it turns out that both systems are equally valid, and different Math packages use one way or the other. It’s not a big deal to convert between them, but it’s definitely a lot simpler to pick one and stick with it. OpenGL and Bullet Physics both use a system where the positive Z axis points from your screen out to you (ie your nose is +100 and the area behind your screen is -100). I decided I wanted my coordinate space to match OpenGL so it would be easy to draw what I was building in my Physics Engine.

What’s this have to do with hands? Well to help us give a name to the two different ways of orienting your Z axis, someone came up with a way to illustrate the X, Y, and Z using  your fingers. If you hold up your right hand and point your thumb along the +X Axis, and your index finger along the +Y Axis, you can then point your middle finger at your nose and call that the +Z Axis. This is a Right Handed Coordinate System. If you try to do the same thing with your left hand you’ll see that your middle finger points away from your nose, a Left Handed Coordinate System.

There’s one more hand trick that might even be more important when representing rotations using Axis and Angle. You may have noticed that up until now I’ve said that the Axis is the Vector you rotate around, and the Angle is the amount you rotate, but I never specified which direction to rotate. By using our hands we can finally answer that question. If you represent your Axis Vector as running along your thumb (the thumb nail is +100, palm is -100) then a positive rotation is the direction in which the rest of your fingers curl when you make a fist.

Let’s put all those bits together with an example. Let’s demonstrate a positive rotation around the +Z Axis using the Right Handed Coordinate System. Start by holding your right hand in front of your face with all of your fingers open and with your thumb pointing at your nose. Your thumb now represents the positive Z Axis. Curl your fingers into a fist, that is positive rotation. You should see your fingers curling counter clockwise. When you see information about a Right Hand Coordinate System online you’ll often see that positive rotation is counter clockwise.

If you’re trying that out and it’s not working as expected, re-read this and try again. It’s worth getting right because bugs in the direction of rotation are really hard to figure out. The more you understand it now, the easier your life will be.

Actions on a Coordinate_space

Turning our attention back to the Coordinate_space, let’s look at the functions it supports. At the core, it has some transform functions that serve to convert global Points and Vectors to local Points and Vectors, and vice versa. The usage of types makes these very transparent:

Vector        transform( const Local_vector& v ) const;
Local_vector  transform( const Vector&       v ) const;
Point         transform( const Local_point&  p ) const;
Local_point   transform( const Point&        p ) const;

The code that drives these is based on Quaternion magic, so I can’t pretend to understand everything about why it works, but I am comfortable that it does.

As you can see, there’s no need to specify in the function name what you’re transforming from and to, we just use the type system to do the right thing. This is another good argument for why a Vector and a Point should be different. Since Vectors have no position, the transform function simply rotates them. And since Points do have a position, the transform function rotates them and moves them. For example, if we have a Coordinate_space that is moved to (1,0,0) and rotated 90 degrees around (0,1,0), and we have a global point at (2,0,0), by now you should be able to reason that if we converted that Point into the Coordinate_space it would be at (0,0,1). Try out a bit of invisible knitting yourself, to see if you get the same result.

Aside from these helper type functions, a Coordinate_space has the usual translate and rotate things  you’d expect. I won’t dwell on those, they do what you’d expect, they move and rotate the Coordinate_space. Their implementation is straight forward with the help of the transform functions.

The last function is one that I find myself using a lot, it’s this:

std::tuple<Unit_vector,Unit_vector,Unit_vector> get_axes() const;

This one returns the global X, Y, and Z axis for the Coordinate_space. How is that useful? Let’s say you’re flying in your space ship and you want to fire a laser. What direction is the laser going to go? Clearly it is going to fly straight out from the front of your ship. And what direction is straight out? Well that would be along the +Z Axis. So with this simple function it’s easy to grab the direction in which the laser should fly. In normal usage you would create a new Laser object, drop it into your game, and set it’s velocity to be a Vector of some magnitude (the longer the faster) directly along the +Z Axis that this function returns.

So there you have it, our long journey through the Math of the Dubious Engine is now complete. We have created simple ways to deal with Points, Vectors, Rotations, and Coordinate_spaces. Now we have enough tools at our disposal to go ahead and start talking about the point of this whole thing: Physics.

 << Using Types Contents  Linear Motion >>

Points and Vectors

I’m gonna start off our discussion of Physics Engines with some posts about the Math that makes them tick. Don’t worry, I don’t have a degree in Math, so these posts will be long on rambling sentences, and short on Greek symbols. For this one I’m gonna skip the equations all together and just try to talk about the meaning of the most basic types in a Physics Engine: Points and Vectors.

There isn’t much that’s more fundamental to a Physics Engine then Points and Vectors. And for this reason, it’s important to spend some time getting them right. In my path to the Dubious Engine I have actually written a basic Vector library a handful of times. I even wrote one in Haskell to see if it did a better job of handling some of the awkward language edge cases that kept creeping up with C++. What is it about Points and Vectors that are so hard to get right? Well looked at from one angle, they’re pretty much exactly the same thing, 3 floats representing X, Y, and Z coordinates. But looked at from another angle, they have absolutely nothing in common. A Point represents a position in space, or where an object is. A Vector represents a direction and a magnitude, which isn’t really easy to summarize. Can you represent a Point with a Vector? Sure you can, like I said, they’re both 3 floats. But should you use the same class for both? I’d argue that you should not. Let’s discuss why.

Take a moment to consider addition. Does it make sense to add two Vectors together? Yes, absolutely, it’s entirely natural. If you had high school Physics I imagine you spent a lot of time adding Vectors. The mechanics are simple, you just add each of the three coordinates to each other. But what about Points? Does it make sense to add two Points? Surprisingly, no. Sure the math behind it is trivial, it’s the same as with a Vector. But does that have meaning? Let’s say you live in Philadelphia and I live in New York? Both of our positions in space can be represented as Points. But what does it mean to add Philadelphia to New York? It doesn’t mean anything. What would the locations of Philadelphia plus New York represent? I couldn’t even guess. So if addition of Points is meaningless, surely subtraction is too? Oddly enough, subtraction does have meaning. If you take Philly and subtract New York you are left with a Vector that defines the direction and distance from New York to Philadelphia. Remember that a Vector is a direction and magnitude. So this Vector’s direction would be South West, and the magnitude would be about 100 miles. Now if you start with the New York Point and you add this Vector, the result is the Philadelphia Point. Let’s summarize this:

  • Addition and subtraction of Vectors is correct
  • Addition of Points is meaningless
  • Subtraction of Points results in a Vector
  • Addition of a Point and a Vector results in a Point

This probably isn’t the result you were expecting when you first started thinking of Points and Vectors. I can tell you from experience that it took me many years to start thinking along these lines. Can you write a Physics Engine that ignores all of this and just uses a Vector for everything? Of course you can, my first few attempts did exactly this. However I found I was always creating bugs where I’d write an interface that expected a position, but I would eventually send it a Vector, and the whole thing would fail and I’d spend a lot of time trying to re-learn the algorithm to understand why. With this new representation I’m much clearer on the roles of Points and Vectors and it helps me keep things straight.

The Code

So with that in mind, how do we write the code? You could be tempted to just make them exactly the same thing, and just use a typdef to give them different names. After all, the actual mechanics of addition, subtraction, and equality are the same. But functions like get_length() make no sense with a Point, but are fundamental to a Vector, so it’s best to avoid this approach. You could be tempted to use inheritance, and move the common functionality to the base class Point and put the Vector specific functionality in the Vector. This is a little cleaner in that you can reuse common code, but the polymorphism is awkward because inheritance represents an “is-a” relationship, and as discussed above, a Vector is not a Point. Another trick you could try is composition, where a Vector just contains a Point, but this leads to circular dependencies in your code. In order to implement Point subtraction a Point must depend on a Vector, but in order to implement a Vector it must depend on a Point. This will really piss off your compiler, which is generally not a good thing to do.

So this leads us to the solution I ended up with, a third class called a Triple, which is nothing more then an abstract thing that contains 3 floats. This Triple isn’t even a class, it’s just a lowly struct, and it implements the absolute basics, addition, subtraction, and equality. Both a Point and a Vector contain a Triple, and a lot of their basic functions are implemented as a simple pass through. They both build on the Triple to implement their type specific functionality.

Now that you understand my reasoning behind Points and Vectors, it should be pretty easy to understand the code. Here are links to my Triple, Point, and Vector implementations. For now, ignore the templates, we will discuss their usage later.

  • Triple – Simple struct of 3 floats. Handles basic math and equality
  • Point – Represents a 3D point in space.
  • Vector – Represents a direction and magnitude.
 << See Also Contents  Vector Types >>