What to study in prep for writing a physics engine?

[InvisibleMan1]

I'd like to first say that I'm not really sure which forum this is supposed to belong in. This one seems to fit best, but my question may be better in one of the math/physics forums...

I'm planning on going through the resources Chris Hecker recommends in his article Physics References, however that article (from what I gather) was written in around 1997: 14 years ago.

I suspect that there have been new developments since the article was put together, which brings us to the reason for this post: Do you guys have any additions/changes to the list he gives? For example, changing the order in which a topic is studied, a new and better book for a particular topic in the list, new topics to add to the study list (with accompanying book recommendations if you can), etc.

I like the fact that he discusses each set of books and the pros/cons. If you guys could provide similar notes with your recommendations, as well as when I should study that topic (right after reading the Calculus book? After reading everything else in that list?) and what I will be able to do in my physics engine after I study it (like his "milestones"), it would really help :)

To help you decide what recommendations to make, I'll do my best to describe where I am in math. I should note though that I am currently planning on going through each resource in that list (with exceptions to duplicates), including topics I am familiar with. The main reason for this (as you will probably see in the following) is that while I might know overall about a particular topic, I usually don't have a whole lot of experience mainly due to not studying from a textbook with problem sets.

Basic math

Addition, subtraction, multiplication, division, fractions...​

Algebra I

I learned this from a textbox, but unfortunately I do not have the title available to me at the moment.​

Geometry

I learned this from Geometry: Seeing, Doing, Understanding 3rd Edition by Harold R. Jacobs. Due to a lack of interest, and having other things to study, I only ever made it to chapter 9, lesson 1 (about half-way).​

Algebra II

I never studied this from a textbook, but I did pickup on parts of it by studying other areas of math and programming. Using http://library.thinkquest.org/20991/alg2/index.html as a reference for what is studied in Algebra II, I am familiar with the following:

• Solving Equations and Inequalities - I don't have much experience with inequalities, but I know how to work with them.
• Graphs and Functions
• Systems of Equations and Inequalities - I don't have much experience with solving systems, but I know the gist of it.
• Polynomials and Factoring - I don't have much experience with polynomials (I can't recite from memory the various methods of dealing with them), but I do know what they are and I am familiar with how to work with them.
• Fractional Expressions
• Powers and Roots
• Complex Numbers - I know what these are basically, but I have very close to zero experience with them.
• Quadratic Equations - Most of my experience with solving these is by using the quadratic formula (which I have derived for myself several times before, once by accident).
• Quadratic Functions - Most of my experience with these is from learning Calculus.
• Coordinate Geometry - I'm familiar with this, but I usually need to use a reference whenever I have need of it.
• Exponential and Logarithmic Functions - I get the terms "exponential function" and "power function" mixed up regularly, and I require references when working with logarithms (particularly natural log).
• Probability - As far as I know, I don't have direct experience or knowledge of this.

Trigonometry

I never studied this formally, but I picked up on parts of it from studying other things and programming. Using this page as a reference for what is studied, this is what I know:

• Angle measurement
• Chords - I am familiar with the term, but I don't have much experience or knowledge of the thing itself.
• Sines
• Cosines
• Tangents and slope - I am familiar with this only through studying Calculus.
• The trigonometry of right triangles - I know how to use the inverse functions, but I am not all that familiar with the rest.
• The trigonometric functions and their inverses - I'm not very familiar with the properties of sines and cosines, although I have looked them up and made use of them in the past.
• Computing trigonometric functions - As far as I know, I have no knowledge of this.
• The trigonometry of oblique triangles - I'm not familiar with the law of sines or cosines.
• Area of a triangle - I am familiar with a = bh/2 but not the method they describe in this section.
• Summary of trigonometric identities - I am familiar with SOH-CAH-TOA, but my situation with the trigonometric identities is the same as my situation with the properties.

Calculus

I learned this from the Calculus section at Brightstorm. I watched every single video in that section.​

Multivariable Calculus

I learned this by watching the 18.02 lectures at MIT OpenCourseWare. I made sure I understood each lecture by pausing and rewatching, but I did not do any of the homework assignments or exams, and I did not have the textbook.​

Differential Equations

I learned this by watching the first 4-7 (I don't remember the exact lecture I stopped on) 18.03 lectures at MIT OpenCourseWare. I did not have the textbook, and I did not do the homework assignments or exams.​

Linear Algebra

I learned this from reading 3D Math Primer for Graphics and Game Development.​

Set Theory

I know the basics, mostly from an introduction I had in between basic math and algebra I, as well as from studying other things.​

Graph Theory

I am currently studying this from Introductory Graph Theory by Gary Chartrand.​

Topology

I plan on studying this using Introduction to Topology 3rd Edition by Bert Mendelson, possibly after I am through the graph theory book.​

Abstract Algebra

I plan on studying this using A Book of Abstract Algebra 2nd Edition by Charles C. Pinter, possibly after I am through the topology book. The order may vary depending on if I find that one book is dependent on the other, or I find that I am missing some prerequisite.​

Linear/Quadratic Programming and LCP

I know of their existence and a tiny bit about what they are as well as what they are used for in a physics engine. I do not have any experience with these or knowledge of how to work with them.​

Physics

I started learning this from the Physics Tutorial at The Physics Classroom. I did all exercises and I read up to and through the chapter "Circular Motion and Satellite Motion". It became a bit too vague however, so I switched to learning from here: http://electron9.phys.utk.edu/phys135d/Modules.asp. I went through each module up to and including "Rotational Motion", doing all of the problems in addition to understanding what was being taught.​

Physics Simulation

I have read through most of the papers by David Baraff, although I did not completely understand them. I have also gone through various other papers including "Nonconvex Rigid Bodies with Stacking" and "A Unified Framework for Rigid Body Dynamics", the latter being the most helpful. I have also gone through Erin Catto's GDC2006 slides and the source for Box2D Lite. I have glanced through some of the chapters in Game Physics 2nd Edition by David H. Eberly, as well as Chris Hecker's Game Developer Magazine columns sans the one on 3D physics. I have also written several physics engines, however they have not worked very well.​

Collision Detection

Most of what I know about collision detection I have learned from Real-Time Collision Detection by Christer Ericson. I have not read the book cover to cover though.​

 

[chiro]

Hey there InvisibleManI

If you want to write a physics engine some things that stand out include having a good numerical integration package, good collision detection, and on top of that your actual physics code.

My advice to you is to try and understand what the math is doing. See the forest from the trees. Chances are you might copy some code and modify it, but you may not know what you are doing, and that's not what you want to do.

I've outlined some ideas for you and if you understood what they are and why I said them, you will probably be able to go from there and understand what's being used and more importantly why it is being used and improvements or design decisions for its used.

First I will talk about collision detection.

Collision detection is really really critical. Not only does it have to be fast, it needs to be accurate. Typically when you deal with collision of objects you usually define separate "collision primitives" like spheres, cylinders, boxes, or hulls (convex hulls).

So the first thing you need to do is figure out what kind of collision primitives you want to use. There are plenty of code examples out there that have optimal routines for a variety of primitives.

As you might see, there is a tradeoff between what the primitive describes and the object it is referring to.

If you want to do "exact" collision detection with detailed solid objects and you don't care if the output is "real-time", then you can use the actual model data as your primitive. If your data is just a bunch of triangles, I would suggest you convert concave objects to convex hull representations. One reason is that your hull has correct orientation, and the checking mechanism can be optimized in many situations.

So let's say you have really solid CD routines. You will need numerical integration routines to calculate numerical integral representation of physical variables. If you are stuck with this look the available code that takes in arrays and performs numerical integration with your array as your argument.

So with this you can implement your physics. Some important things to keep track of include inertia tensors as well as physical variables that are both translational and rotational.

If you combine all of the above, you will get a really basic physics engine.

If you want to model things like deformations accurately, like for example an engineering grade simulation, then you will have to use more advanced models and data structures. One thing that springs to mind for this kind of thing is finite element analysis. For this you will need new data structures and a lot more processing power. I haven't coded any FEM simulation or physics code, so I can't really tell you any specifics.

So those three things CD, numerical calculus solvers, and physics specific are the basics. If your using this for a game, you need to optimize the interaction of these components so that the real-time performance is acceptable. Now most modern day games actually build a lot of collision data right into map and object data, and have the physics engine inter-weaved everywhere as to get good performance.

Of course you will need other libraries like math libraries with vector and matrix routines (maybe even quaternion routines too) along with hit-detection (think ray detection). Think about a moving object, and you want to gauge the chance of it hitting another moving or static object.

Another thing for optimization is that you typically have two types of objects: static and dynamic. The static ones don't move (like buildings for example) and dynamic do.
For static geometry, BSP-trees are good for a variety of reasons and one of them is collision detection. The drawback of using these though is that they use a lot of indirection (pointers, like the way linked-lists store their internal data).

BSP (or Binary Space Partitioning) is a polytype classification system. It works by using a plane and splitting the space in two parts, the positive side and the negative side. A point is positive when the inner product with a point and the plane's normal plus the distance to the plane from the origin is positive (ie <p,n> + d > 0). It's negative when <p,n> + d < 0). It's on the plane when <p,n> + d = 0.

The reason BSP is good is because it can discard the objects that will never have collision detection such as ones that are behind a wall for example.

Typically you need some decent spatial classification system and data structure like BSP, but BSP alone is usually not enough. This is an active area of research and I'm sure you'll find many articles, ideas, and implementations that talk about this specifically.

 

[InvisibleMan1]

First off, thanks for the detailed reply. Unfortunately though, I am already familiar with what you described. As I said in my first post, I have written three physics engines before, they were just error prone, unstable, and lacked some features.

I'm looking for recommendations on what to add/change with the research list presented by Chris Hecker. I suppose I should also note that the actual programming side of things is under control since I have been coding in general for 11 years. From what I understand, coding math into a program is a topic all to itself (for example, numerical integrators) and I don't have much experience with it.

 

[chiro]

First off, thanks for the detailed reply. Unfortunately though, I am already familiar with what you described. As I said in my first post, I have written three physics engines before, they were just error prone, unstable, and lacked some features.

I'm looking for recommendations on what to add/change with the research list presented by Chris Hecker. I suppose I should also note that the actual programming side of things is under control since I have been coding in general for 11 years. From what I understand, coding math into a program is a topic all to itself (for example, numerical integrators) and I don't have much experience with it.

In your previous engines, what numerical routines do you use? Do you use any particular DE solver, or have you written your own from scratch?

Personally since you've been coding for a while, it's probably overkill doing textbook exercises: I would just look for code that solves the appropriate calculus problem. When I say code, ultimately you will have to implement it in the language your engine is written on, but if you do a bit of research you should find articles and code examples that discuss instability of the engine, and this should lead to discussions of your numerical routines.

I'm not an expert in physics engines, so I can't tell you anything specific about how to get rid of instabilities, but I would bet that if you want specific knowledge about numerical instability for physics engines, that you should read specific stuff related to that rather than doing a few textbook exercises on DEs: you'd be wasting a lot of time IMO (I'm nearly finished a math double major).

By the way, what numerical scheme have you used in your existing engines?

 

[InvisibleMan1]

In your previous engines, what numerical routines do you use? Do you use any particular DE solver, or have you written your own from scratch?

I think the integrator I am using is called "Euler", or something similar. x = x + v*dt I wrote the code from scratch.

Personally since you've been coding for a while, it's probably overkill doing textbook exercises: I would just look for code that solves the appropriate calculus problem. When I say code, ultimately you will have to implement it in the language your engine is written on, but if you do a bit of research you should find articles and code examples that discuss instability of the engine, and this should lead to discussions of your numerical routines.

I'm not all that interested in doing copy+paste coding. I'd rather understand what it is that I am doing. On a related note, why would doing the textbook exercises be a waste of time simply because I have been coding for a while? Having a lot of experience writing programs doesn't mean you have a lot of experience with math

By the way, what numerical scheme have you used in your existing engines?

I don't know what a numerical scheme is.

 

[chiro]

I think the integrator I am using is called "Euler", or something similar. x = x + v*dt I wrote the code from scratch.

That will cause huge problems. You need to use more terms of the taylor series expansion. Euler method only use one derivative term, and this is going to be a big issue in instability.

If I were you I would research things like Runge-Kutta numerical schemes. They use more terms and hence more stable. They also take more computation power, but in terms of nowadays computing power, you can afford to do that.

On a general scale, schemes with higher order error terms are more accurate.

I'm not all that interested in doing copy+paste coding. I'd rather understand what it is that I am doing. On a related note, why would doing the textbook exercises be a waste of time simply because I have been coding for a while? Having a lot of experience writing programs doesn't mean you have a lot of experience with math

I think I may have not said the right thing: I didn't want to say to copy and paste, but rather to see the structure of certain code which you can interpret and understand and then adapt in whatever way you want to how you want it in your engine. Kind of like how you would get example problems in physics for example.

With regard to textbook exercises, they mostly deal with analytic problems, and your problem is numerical. Most understanding of numerical problems comes when using packages (like MATLAB, or maple) and using different quadrature schemes to get results. One part of the learning is understanding the scheme, and the other is implementing it, either on some platform like MATLAB, or in a lower level environment like C++.

The textbook will be useful for understanding the concepts behind different schemes and with understanding of taylor series, you'll be able to see what the different schemes used in that context. If you understand that, coding will be straightforward.

I don't know what a numerical scheme is.

A scheme is just a way of describing your particular numerical solver. Euler is the simplest scheme. Others like Runge-Kutta require more computation but are more accurate.

 

[InvisibleMan1]

That will cause huge problems. You need to use more terms of the taylor series expansion. Euler method only use one derivative term, and this is going to be a big issue in instability.

If I were you I would research things like Runge-Kutta numerical schemes. They use more terms and hence more stable. They also take more computation power, but in terms of nowadays computing power, you can afford to do that.

On a general scale, schemes with higher order error terms are more accurate.

I compared the two when developing one of the engines, but I didn't notice enough of a difference for it to be worth the extra overhead and complexity. I'm sure this will change when I go to simulate more advanced things though.

With regard to textbook exercises, they mostly deal with analytic problems, and your problem is numerical. Most understanding of numerical problems comes when using packages (like MATLAB, or maple) and using different quadrature schemes to get results. One part of the learning is understanding the scheme, and the other is implementing it, either on some platform like MATLAB, or in a lower level environment like C++.

The textbook will be useful for understanding the concepts behind different schemes and with understanding of taylor series, you'll be able to see what the different schemes used in that context. If you understand that, coding will be straightforward.

The fourth step in this section http://chrishecker.com/Physics_References#Constraints appears to cover at least some of this. Do you have any study recommendations in addition to what Chris Hecker recommends?

 

[chiro]

http://chrishecker.com/Physics_References#Constraints[/url] appears to cover at least some of this. Do you have any study recommendations in addition to what Chris Hecker recommends?

I just had a look at the site and it looks fairly comprehensive.

I think what the author said is true: basically you will look through some resources and they will link to other resources, which will link to other resources and so on.

It's good that the author has included both the physics, maths, and also the simulation or computational aspect (ie the numerical linear algebra and related stuff).

One thing I will mention though is that some engines put stuff in that fix instability issues as "side note" code in the repository, and it might be hard to find articles that specifically detail the issue and how they solved it (in other words, you're not likely to find it on google or in a book), so keep that in mind. If you do decide to look at existing implementations, like open source ones, there will probably be some code that is added to aid stability. It might look like its a "hack" in some cases, but at least you can gauge for yourself how useful and effective these additions really are.

 

[InvisibleMan1]

Alright, thanks for the information.

 

[rcgldr]

I think the integrator I am using is called "Euler", or something similar. x = x + v*dt I wrote the code from scratch.

If acceleration is considered constant during a time step, that would be ok, but position should be updated using average velocity:

new_velocity = old_velocity + a * dt

new_position = old_position + 1/2 * (old_velocity + new_velocity) * dt

If acceleration is allowed to vary during a time step, and if acceleration is affected by velocity (aerodynamic drag) and/or position (gravity) then acceleration is a function of forces (divided by mass), velocity, and position. You could use average acceleration per time step, but you'd need an iterative method to converge on the "new_acceleration".

http://en.wikipedia.org/wiki/Predictor-corrector_method#Euler_trapezoidal_example

 

[InvisibleMan1]

If acceleration is considered constant during a time step, that would be ok, but position should be updated using average velocity:

new_velocity = old_velocity + a * dt

new_position = old_position + 1/2 * (old_velocity + new_velocity) * dt

If acceleration is allowed to vary during a time step, and if acceleration is affected by velocity (aerodynamic drag) and/or position (gravity) then acceleration is a function of forces (divided by mass), velocity, and position. You could use average acceleration per time step, but you'd need an iterative method to converge on the "new_acceleration".

http://en.wikipedia.org/wiki/Predictor-corrector_method#Euler_trapezoidal_example

I remember taking acceleration into account to calculate velocity, but using an average is a new idea. Thanks :)