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 >>

See Also

I think it’s typical to put the Bibliography at the end. However for this series of posts, I’m putting it right at the start. The reason for this is because the Dubious Engine is in no way an original piece of work. I did not invent any of the Physics that powers it. I’d like to think that I’ve organized it in a way that makes it easy to understand and write about, but I certainly didn’t come up with any new algorithms. Everything here has been described somewhere else. Unfortunately I started this so long ago that I’ve lost track of all the things I’ve read, but here are the ones that I can remember:

  • allenchou.net – This is the big one, I must have read and re-read every post here dozens of times. If he had source code to post I probably wouldn’t have bothered writing anything.
  • 3D Game Engine Programming – The site that finally got me to understand Quaternions. That alone makes it priceless, all the other great articles are just a bonus.
  • box2d.org – The simplest code to understand, primarily because it’s in 2D. It’s almost a requirement that you get it running and familiarize yourself with it while creating your own Physics Engine. While it is not 3D, the concepts are familiar enough. Also contains some papers that you have to be much smarter then I am to understand.
  • bulletphysics.org – An actual, working Physics Engine, complete with source code. It does everything. Unfortunately it’s very difficult to read through and the documentation is sparse. Still, if you have the time to really truly go digging, the answer is in there.
  • Molly Rocket – In 52 minutes you can understand what the GJK algorithm is. Other articles can help you refine it, but really there is no quicker path to understanding.
  • Code Cave – Second only to Allen Chou for understanding GJK and EPA. Bonus points for representing 3D concepts using sticks and putty. I may very well rip that off.
  • dyn4j.org – More great information about GJK and EPA
  • Matrix and Quaternion FAQ – One of those ancient pages out of Internet history (hello purple.com). I can’t find the original version I used to use, but this seems like it’s pretty much the same thing. This is where I was introduced to Quaternions, and my first implementations came from this page. It was so freaking painful.
 << Introduction Contents  Points and Vectors >>

Building a Physics Engine

“You’re Building a What Now?” Before thinking about building a Physics Engine, you have to stop and ask yourself a very important question, “why on Earth would you want to build a Physics Engine?” In many respects, a Physics Engine is a solved problem. There are really good ones available, open source, for free (thank you Bullet). Unless you’re a PhD with some fancy new algorithm to try out, you’re not gonna beat any of the existing engines. So why bother?

I didn’t start out trying to build a Physics Engine. I started out (back in 2001) trying to build a really cool space dog fighting game. I didn’t have any really original ideas, but I wanted to combine all of my favorite bits from various games of the genre, and see what I could make. I knew I would never be able to complete it, but I thought it would be interesting to try. As different aspects of the game started coming together, I would occasionally read people mentioning Physics Engines, but I always figured they just weren’t very smart. Everyone knows Physics, right? v=d/t like from High School. I just coded that up and got back to work. But as the game started to take shape, I noticed that ships didn’t move right. Like if you shot a missile into a wing tip, the whole ship would lurch backwards, instead of going into a spin. So I started reading a bit more about the mysterious Physics Engines. Eventually I became so engrossed I stopped working on the game at all, and just learned Physics.

So this brings us to today. I have found that the world of Physics Engines falls into two categories:

  1. Well written articles, but not enough detail and no code.
  2. Code with absolutely no explanation.

So here’s the pitch. I have written a basic but functional Physics Engine. Now I’d like to write about it. The goal is to produce blog posts, that together with the source, will create the world’s first understandable explanation of a Physics Engine. This should be the guide I always wished was available to me.

Let me throw out some buzzwords to explain what it is I have to write about. I’ve written a Rigid Body, Discrete Engine. I use GJK and EPA to do my collision detection. And I wrote a Sequential Constraint Solver to do collision resolution. If you don’t know what any of those terms mean, that’s fine, we’ll go over them all. If you’ve come here looking for information on any of those, then you’re in luck, ’cause that’s what I got.

I call it the Dubious Engine. The full source is available online at: https://github.com/SaintDubious/DubiousEngine. I will try to refer to the actual source with each blog post, so you can see working code, and follow along with the reasoning behind each piece. I hope you find this information useful as you work to create your own Physics Engine. As for my initial question, “Why on Earth would you want to build a Physics Engine?” Simple answer really, it’s a lot of fun.

Contents  See Also >>

Table of Contents

Welcome to the Dubious Engine. This series of blog posts is my attempt to fully explain how to write a basic Physics Engine. The full source is available at: https://github.com/SaintDubious/DubiousEngine

Table of Contents

  1. Introduction
  2. See Also: References
  3. Math
    1. Points and Vectors
    2. Vector Types
    3. Vector Math
    4. Rotations
    5. Using Types to Your Advantage
    6. Coordinate Systems
  4. Physics
    1. Linear Motion
    2. Angular Motion
  5. Collision Detection
    1. Collision Detection – GJK 1
    2. Collision Detection – GJK 2
    3. Collision Detection – GJK 3

That’s all for now. Writing these takes time, so it might be a while, but here are some other ideas:

  1. Collision Detection – EPA
  2. Collision Detection – Contact Manifolds
  3. Collision Response – Constraint Solver
  4. Collision Response – Friction
  5. Broad Phase Collision Detection
  6. Cheats – Baumgarte and Coefficient of Restitution
  7. Cheats – Warm Starting
  8. Optimization – OpenCL