So Part 1 and Part 2 laid the groundwork for rendering signed distance fields. Now I’ll present a general shader for doing so. This is a reimplementation that retraces the work originally presented by Qin, et al (basically, I missed that paper during my original research).

(more…)

## 3/29/2015

### Rendering Signed Distance Fields, Part 3

## 3/19/2015

### Rendering Signed Distance Fields, Part 2

So in Part 1 of this series, I talked about how to create a shader to render a distance field texture that only has uniform scale, rotation or translation applied — no shear or perspective transformations. So now one might expect (as I promised) that I’d talk about how to create a general shader for distance fields. After looking at what I wrote, however, I realized that a) I need to explain *why* you might want to use a signed distance field texture and b) to explain the rest I need to bring everyone up to speed on multivariable derivatives — namely gradients and the Jacobian. So I’ll cover those in this post, and finish up with the full answer next time. That said, I did fix the bug in Skia, so if you know all this or are impatient, you can skip ahead and look at the source code.

(more…)

## 3/15/2015

### Rendering Signed Distance Fields, Part 1

So at the end of my GDC 2015 presentation “How to Draw an Anti-Aliased Ellipse” I mentioned that you could extend the same techniques to signed distance fields (SDFs), in particular for text. However, some details might be helpful. Because SDFs encode distance directly, the approach is slightly different than for an implicit field like ellipses. I also made a grandiose statement that you should use the shaders in Skia because all the others don’t work properly. After prepping this post, I realized that was half right — the case that we see 99% of the time in Chrome is correct, but the case that you might see in a 3D world — e.g., a decal on a wall — is not. I’ll talk about a better way to handle that in Part Two.

So first, go look at the presentation linked above, just as a quick review. I’ll wait.

(more…)

## 4/1/2013

### GDC 2013

So GDC 2013 has come and gone, and with it another tutorial session. This year I did not run the Physics Tutorial, passing that on to Erin Catto’s more than capable hands. Instead, I organized the Math Tutorial for the first day, with the following lineup:

- Interpolation and Splines – Squirrel Eiserloh (The Guildhall at SMU)
- Matrix Transformations – Squirrel Eiserloh (The Guildhall at SMU)
- Understanding Quaternions – Jim Van Verth (Google)
- Dual Numbers – Gino van den Bergen (Dtecta)
- Orthogonal Matching Pursuit and K-SVD for Sparse Encoding – Robin Green (Microsoft) and Manny Ko (Imaginations Technologies)
- Computational Geometry – Graham Rhodes (Applied Research Associates Inc.)
- Interaction with 3D Geometry – Stan Melax (Intel)

Overall, I thought it was a good mix of beginning and advanced topics. So a big thank you to all the speakers — I learn something from them every year, and without them it wouldn’t be possible. And as time goes on, I’ll add links to the slides as they come in.

Before I close, I have one comment on my talk. As I was discussing the matrix form of the quaternion, I mentioned that multiplying by a rotation on the left is the same as multiplying by the inverse of the rotation on the right. As I think I made clear later, this is not true. I was trying to convey how I originally — and incorrectly — thought about it but I fear I may have misled some in the audience. What was thinking was that if you multiply a column vector on the right by a rotation matrix, i.e. **Rv**, this is the same as multiplying a row vector on the left by the inverse, i.e. **v**^{T}**R**^{-1}. But of course, we’re not multiplying vectors, we’re multiplying a matrix **Q** which represents a quaternion, which in turn represents a vector. So, not quite the same thing, and the end the result is not the same. I’ve modified the notes in the slides to make this clearer.

## 3/11/2012

### Updates and 2012 Tutorial Followup

So it’s been a while since I checked comments — it appears that email forwarding got broken at some point — and I see my last post had a large number of comments regarding errata. I believe the commenter also sent me a tweet about them as well, so no real excuses there. And it probably didn’t help that the site went down for a couple weeks. In any case, I’ll take a look today and address those.

As far as this year’s tutorials, I believe it was a success. There was a lot of interest after each presentation, and while it’s hard to judge based on just that (a bit of selection bias there), most people seemed to like what they heard. I will, this week, be putting up the latest slides for this year, as well as the missing ones from previous years.

One thing I’d like to do, now that I have some free time, is post some more on this blog. My presentation this year was a revamp of an orientation representation/quaternion talk I’ve given in past years, with a new section on 2D rotations. So I’m thinking I might do a series of posts expanding on complex numbers as a method for 2D rotation. I’m thinking it might be possible to store the cosine of the half angle and do some interesting things with that, as the sine of the half angle is always implied (when using half angles, you can stay within the upper semicircle and assume the sine is always positive sqrt(1 – cos^2(theta/2)). We’ll see how that goes.

An alternative is a series on the math behind Robin Green’s talk this year — though to keep off of his toes it might be a series on the math you need to know in order to *understand* Robin Green’s talk.

## 2/23/2011

### 2011 GDC Tutorial Lineup

Here’s the lineup for this year’s Physics for Programmers tutorial. Times are approximate, but should be pretty close:

10:00-10:10 – Introductions

10:10-11:00 – Squirrel Eiserloh – It’s All Relative

11:00-11:15 – BREAK

11:15-12:00 – Erwin Coumans – Game Physics Artifacts

12:00-12:30 – Jim Van Verth- Numerical Integration

12:30-14:00 – LUNCH

14:00-14:50 – Gino van den Bergen- Collision Resolution

14:50-15:25 – Takahiro Harada – GPU Physics

15:25-16:00 – Glenn Fiedler – Networked Physics

16:00-16:15 – BREAK

16:15-17:10 – Erin Catto – Soft Constraints

17:10-18:00 – Kees van Kooten- Fluids

I’m definitely looking forward to it, should be a great day of physics talks. Hope to see you Tuesday, March 1, in Room 3007, West Hall Moscone Center.

## 11/11/2005

### GDC Update

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!

## 3/25/2005

### Angular Dynamics: Matrices or Quaternions?

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

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

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

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.

## 2/5/2005

### Prepping For GDC

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