Essential Math Weblog Thoughts on math for games


Rendering Signed Distance Fields, Part 3

Filed under: Mathematical,Tutorial — Jim @ 1:59 pm

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


Rendering Signed Distance Fields, Part 2

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

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.


Rendering Signed Distance Fields, Part 1

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

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.


GDC 2013

Filed under: Tutorial — Jim @ 7:46 pm

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


Updates and 2012 Tutorial Followup

Filed under: General,Tutorial — Jim @ 11:04 am

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.


2011 GDC Tutorial Lineup

Filed under: Tutorial — Jim @ 10:06 pm

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.


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!


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:


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.


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.


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.


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

Powered by WordPress