# Essential Math WeblogThoughts on math for games

## 1/16/2007

### Mac OS X issues

Filed under: General — Jim @ 8:36 pm

I’ve had a couple reports of issues with the OS X libraries as shipped with the book.  The problem appears to be that the libraries are compiled for Mac OS 10.2, but don’t work so well with 10.3 and particularly 10.4 and up.  And the fact that they are compiled for a PowerPC architecture doesn’t help the new Intel machines.

The solution is simple: recompile the libraries.  To do so, you’ll need to make sure that all the files are writeable.  Open a terminal window and change to the “common” directory and then type:

make clean PLATFORM=OSX
make PLATFORM=OSX

If you still have issues after doing this, let me know and we’ll try to track it down.

Note that this is the same procedure you’ll have to follow for the Linux builds, except that the platform doesn’t need to be specified.  While the libraries are compiled under an older version of Mandrake, there is no guarantee that they will work for other Linux builds or versions.

## 5/16/2006

### Math Library discussion

Filed under: General — Jim @ 7:53 pm

For those who are interested in the process of construction of a math library, or perhaps are interested in other people’s opinions on how such a library would be constructed, or perhaps would like to share your own opinions on such a library… er, I’ll start again.

In the sweng-gamedev mailing list, Noel Llopis started up a thread regarding the creation of a industry-wide standard math library. This has led to a very long discussion of such a library, and the creation of a wiki page. As of yet I don’t have much of an opinion on this other than the discussion is extremely verbose and so I can’t keep up with it all. However, someone out there might, and so I share its existence with you all.

Some of this may meander into the next edition of the book, particularly the management of SIMD operations which is something I’m dealing with in my company’s library. However, I can say for certain that there will not be a separate Point class in the book’s library, because a) it’s simpler to manage and b) I trust people not to do dumb things with Vectors when they’re actually Points. This may be a foolish assumption on my part.

Addendum (05/19/06): there’s also a SourceForge page to deposit potential code for said library.

## 4/19/2006

### Second Edition

Filed under: General — Jim @ 8:04 pm

Just a quick note to say that a second edition for Essential Mathematics for Games… is in the works.  If you have items that you would like to see updated, expanded, or just plain included in a new edition, please let me know.  Also, if you’re an educator and you’re using this book as part of a course, please drop me a line as well.  We may be interested in having you do a detailed review of the first edition.
You can send me email at ‘jim’ at this domain, or use the form on the front page of the site.

## 12/11/2005

### Some Fun Science and Math Links

Filed under: General — Jim @ 10:13 pm

I had originally intended on writing up a post about some of the science and math I’ve been seeing on TV lately. However, as I got into it, I realized it was going to end up too long, too verbose and (more importantly) without a point. A boring rant for ranting’s sake, if you will. So… y’all (or youse guys, if you prefer) get this post instead: a series of fun math- and science-related links which provide a nice diversion on slow days.
(more…)

## 11/16/2005

Filed under: General,Personal — Jim @ 9:12 pm

First of all, my apologies for the lack of posts. Part of it was the demands of my paid work: For some time, I’ve been working on the PS2 version of Rainbow Six: Lockdown, and those of you in the know are aware that the ship date was pushed out from March to September. While most of that was just polish, doing that final 1% takes a fair amount of effort. So only recently have I felt like digging into new engineering challenges and blogging again. The other part was that I didn’t have much to write about, but I have some ideas which I’ll put up in the next few weeks.
(more…)

## 11/11/2005

### GDC Update

Filed under: General,Tutorial — Jim @ 8:51 pm

The GDC sessions have finally been announced, and I’m pretty excited about the tutorial this year. Instead of doing the usual 2-3 people talking about a variety of subjects, some of which is not their specialty, this year we have 6 people with a broad range of experience. This should allow us to have deeper coverage and present an overall better tutorial.

Here are the speakers, with their current proposed topics:

Jim Van Verth: Physics Engine Overview
Christer Ericson: Numerical Robustness
Squirrel Eiserloh: Relative Motion and Collision
Gino van den Bergen: Narrow (GJK) and Broad (Sweep and Prune) Phase Collision
Erin Catto: Constraints and Solvers
Marq Singer: Dynamic Destruction

The full session description can be found on the GDC 2006 site. Hope to see some of you there!

## 11/5/2005

### More errata

Filed under: Erratical — Jim @ 9:41 pm

A couple more errata have come in since the last update. From Tim Lowery comes:

“On page 117, the figures look mislabeled, or the axis is incorrect. For example, Figure 3.5a shows x-axis rotation, but the object is rotating around the y-axis. Likewise, for Figure 3.5b.”

In this case, the captions are correct (the intent is to go in xyz order), but the figures are reversed.

From k. avery comes:

“At the end of p. 623, cot theta should be csc theta / sec theta, not sec theta / csc theta.”

Indeed it should be. And I had thought I caught that one once before. Evasive devils, those cotangents.

## 7/29/2005

### Errata and Patch Files

Filed under: Erratical — Jim @ 10:13 pm

I’ve finally gotten around to creating a formal errata file, and a code update. The code update is an encrypted ZIP file; the password is the second word on page 37. The paths should be set up correctly to match the original CD. To use, simply unzip it to the directory where you copied the CD contents.

If there are issues, you can post a comment here, or write me by using my first name at this domain.

## 6/7/2005

### Reparameterizing a Curve, Part Three

Filed under: Erratical,Mathematical — Jim @ 9:08 pm

Now we come to the final part: merging Newton-Raphson and bisection together, and choosing the correct one depending on the situation.
(more…)

## 5/11/2005

### Reparameterizing a Curve, Part Two

Filed under: Erratical,Mathematical — Jim @ 9:11 pm

Due to preparing for a week of vacation, and then going on a week of vacation, and then recovering from a week of vacation, this blog has fallen from the wayside a bit. But I’m back, and I’ll try to wrap up this topic in a couple of postings.

When last we left our intrepid heroes, we were discussing Newton-Raphson root finding, how it’s used for reparameterizing a curve, and when it fails (namely when the speed on the curve approaches zero). The solution hinted at was the bisection method.
(more…)

## 4/13/2005

### Roundtable Notes

Filed under: General — Jim @ 10:47 pm

A bit of a digression here: the notes for the Future of Curved Surfaces roundtable are up in the publications area. Overall, a pretty good discussion. I don’t think anything was really resolved, but I certainly learned quite a bit. Hopefully others did too.

We now return you to your irregularly scheduled reparameterization discussion.

## 4/11/2005

### Reparameterizing a Curve

Filed under: Erratical,Mathematical — Jim @ 8:52 pm

I’m still optimizing memory and speed so nothing exciting to report under the lighting topic. Maybe later this week or next week.

So let’s look at a bit of code from the book, shall we?
(more…)

## 4/3/2005

Filed under: General — Jim @ 7:58 pm

I had a few more topics left over from GDC, but I left my notes at work. And I’ll be on lead engineer duty this week and a bit of next so I’m not optimistic I’ll have time to post anything from there.

So instead I’ll write a bit about some lighting research I’ve been doing. Lately I’ve been interested in doing some improvements to lightmap generation — both making it efficient (in both speed and memory) and improving the quality of the lighting solution.
(more…)

## 3/25/2005

### Angular Dynamics: Matrices or Quaternions?

Filed under: Mathematical,Tutorial — Jim @ 9:00 pm

One of the questions asked during the tutorial was whether matrices or quaternions were more efficient for angular rigid body dynamics. My response was that a matrix would be more efficient, because a quaternion requires a conversion to a matrix to compute the transformed inertial tensor matrix. If we analyze the operation count, this certainly appears to be true:
(more…)

## 3/22/2005

### Post GDC Notes: Part 3

Filed under: Mathematical,Tutorial — Jim @ 5:52 pm

Having promised to post about center-of-mass calculations, and subsequently having put it off for a week, I’m going to punt.

First, you can read the seminal Brian Mirtich paper on the subject. Then Dave Eberly responds with a more efficient method. Both rely computing solid integrals across a polytope of constant density by treating them as surface integrals across the polytope’s faces. In the end they end up with total mass (assuming a density of 1), center of mass, and the inertial tensor matrix for the polytope.

If those haven’t scared you off, Jonathan Blow has a more intuitive approach, noting that the solid integral is basically a volume calculation. By breaking the object into tetrahedrons, we can compute the total solid integral as a weighted sum of tetrahedral solid integrals. The tetrahedrons can be computed by selecting a single point — the origin or the centroid will work — and using that point together with the points on each triangular face. As he notes, it’s likely that the Eberly and Mirtich approaches are more efficient, but not as easy to understand from a geometric standpoint. Blow doesn’t provide an implementation, but you can grab a similar one from Stan Melax here.

Finally, Erin Catto pointed out to me after the tutorial that you can compute the center of mass by computing the centroids of the tetrahedrons and then performing a weighted sum of all the centroids, where the weight is the volume of a particular centroid’s tetrahedron divided by the total volume of the polytope. Blow also covers this in his paper as well. To get an intuitive sense of this, I recommend messing around with some origin-centered triangles (e.g. (1,0),(-.5,-.5),(0,-.5),(.5,-.5)) and using areas instead of volumes.

## 3/17/2005

### Quick Update

Filed under: General,Tutorial — Jim @ 8:26 pm

Due to sickness and unexpected work, I haven’t had a chance to do some of the updates I’d planned. I’m working on a write-up about computing center of mass, since I botched that badly during the presentation. I still need to do a little more research to make sure I got it right, though. The Mirtich and Eberly presentations are mostly formula manipulation, and not intuitive from the geometric standpoint.

Until then, here’s an article by Joe van den Heuvel and
Miles Jackson regarding sphere collision: Pool Hall Lessons. Someone recommended it as an alternative method for dynamic sphere-sphere collision. Looking at it, it appears that it might be faster than the one I came up with; certainly so in the average case, as it culls out obvious misses early. But again, I haven’t had a chance to do an in-depth analysis of it.

## 3/14/2005

### Post-GDC notes: Part 2

Filed under: General,Tutorial — Jim @ 8:09 pm

The Win32 sample code has been updated to match what was shown at GDC. The ZIP file also includes the old Mac base code because someone (didn’t catch your name, sorry) expressed an interest in porting it. If you’ve downloaded the code previously, it includes three new examples: an integration methods demo which shows the effect of using three different integration techniques with a spring force; a resting contact demo using impulses to resolve the collision; a resting contact demo which uses contact forces to resolve the collision. For the last two, I have commented out the code which slows it down to 10 fps, so it should look fairly smooth in both cases. If you want to uncomment it, it’s in Game::Update().

For those who picked up the book, there are two code demos in the Chapter 11 folder that are also apropos. The first shows the bounding hierarchy for a simple submarine model. The second shows a one-dimensional example of the use of sweep and prune.

## 3/13/2005

### Post-GDC notes: Part 1

Filed under: General — Jim @ 10:01 pm

I’ve uploaded the latest tutorial slides to the site. I made a few changes, mostly removing demo links (which require specific paths and wouldn’t necessarily work) and replacing some of them with direct web links. I also fixed the positive and negative elements in the collision response slides. In case I missed one or two, basically if the relative velocity along the normal or the relative force along the normal is positive, then the objects will be pushed together. So the correction (either impulse or constraint force) is in the opposite direction of the normal, and needs to be negative.

I’ll be doing a few more updates throughout the week. Tomorrow I’ll upload the latest demo code, at least for Windows. There was also a lot of good conversation during the breaks and after the talk, so I’ll post some comments, corrections and clarifications based on that. So stay tuned.

## 2/5/2005

### Prepping For GDC

Filed under: General,Tutorial — Jim @ 11:07 pm

Just finished rewriting the basic collision response demo to make use of a new dynamic collision model. Originally it determined whether collision is occurring in the current frame, pushed the objects apart, and then reset the velocities for the next frame. Now it determines whether a collision will occur interframe, advances to that timestep and computes the collision response, and then continues movement for the remainder of the frame. Took a bit to deal with the vagaries of floating point, but it appears to work. I’ll write up a bit more detail on this tomorrow; it’s late.

Tomorrow I work on slides and explore the world of resting forces. Also known as “fun with LCP.”

## 12/29/2004

### Errata: Tensor Product

Filed under: Erratical,Mathematical — Jim @ 10:31 pm

William Brennan points out that on page 84, the equation

$(\mathbf{u}\bullet\mathbf{v})\mathbf{w} = \mathbf{u}(\mathbf{v}\otimes\mathbf{w})$

is not correct. There are two ways to rewrite this. In one the intended order is correct, but is missing the transpose operator to indicate that it’s a row vector:

$(\mathbf{u}\bullet\mathbf{v})\mathbf{w} = \mathbf{u}^T(\mathbf{v}\otimes\mathbf{w})$

Alternatively, you can generate the same result with a column vector by doing:

$(\mathbf{u}\bullet\mathbf{v})\mathbf{w} = (\mathbf{w}\otimes\mathbf{v})\mathbf{u}$

In Chapter 3, we simplify the Rodrigues formula (page 123) and general planar reflections (page 128) by using the tensor product. Since the arguments of the tensor product are the same in these cases, the ordering doesn’t matter. However, the ordering of the arguments needs to be reversed in the shear matrices on page 132, so

$\mathbf{H}_{\hat{\mathbf{n}},\mathbf{s}} = \left[\begin{array}{cc}\mathbf{I}+ \mathbf{s}\otimes\hat{\mathbf{n}} & \mathbf{0} \ \mathbf{0}^T & 1 \end{array}\right]$

and

$\mathbf{H}^{-1}_{\hat{\mathbf{n}},\mathbf{s}} = \left[\begin{array}{cc}\mathbf{I}- \mathbf{s}\otimes\hat{\mathbf{n}} & \mathbf{0} \ \mathbf{0}^T & 1 \end{array}\right]$

Other tensor product arguments may need to be reversed elsewhere in the text, though I can’t find any at this time.