Category Archives: Math

Rounded Box Projection

Suppose you want a nice rounded box mesh. You know how to create a mesh for a tesselated box. You know how to get a nice sphere mesh from a tesselated box mesh - you just project the box's points to a sphere:

p' = normalize(p)

What about a rounded box? How can we take a tessellated box mesh and project it nicely to a rounded box? For a box spanning [-1, 1], with a rounding radius of r, you simply:

p_box = clamp(p, -vec3(1 - r), vec3(1 - r))
p' = p_box + r * normalize(p - p_box)

Clamp the point to a smaller box, project the remainder to a sphere, reconstruct. Note that, while I say 'vec3' here, it's good for 2D as well (or however many Ds you need).

I write this down both for myself, and since I didn't find anything by searching (yes, I'm a bit embarrassed that I tried searching this first...)

Distance Fields for Smoothed, Convex Polyhedra

Today was a very fun math day, and I want to share a bit of my experimentation.  Of all the things I did today, one of the most useful was to come up with a formula for the distance field of a convex polyhedron, defined by some set of planes.  I also implemented a smoothed version, which is the one I'll post, because it's quite interesting.

Disclaimer: I'm calling it a distance field because it looks like one and because I don't see many people properly differentiate (teehee?) between distance fields and things that look like distance fields but aren't actually.  So I'll join that club.  The 0-isosurface is the convex polyhedron (or smoothed version thereof), and it does exhibit a nice differentiable behavior, but I don't think that the scalar value actually represents a distance.  Certainly not a Euclidean one if it does.

Random, Smooth Convex Polyhedron

 

Suppose we have a set of k planes defined by normals {n_1, ..., n_k} and d-values (the dot product of some point on the plane with the plane normal) {d_1, ..., d_k}.  Define the shape factor, p, to represent how sharp the edges of the polyhedron are, where p = 2 corresponds to sphere-like edges, and p = \infty corresponds to hard edges.  This definition is a reference to the p-norm, to which the following formula is closely related.  The field value at a point x is given by:

f(x) = \left(\sum_i^k{\left({\frac{x \cdot n_i}{d_i}}\right)}^p \right)^\frac{1}{p} - 1

Just so we're clear, that inner bit is the dot product of the position in the field x and ith plane's normal, n_i. Intuitively, you can see that, with the \infty-norm, this gives the maximal (scaled) distance to any plane - 1, which will be 0 if we are on the polyhedron, and will fall off with the closest plane's distance.  This corresponds to our idea of what should happen for a hard-edged polyhedron.  For other norms, you can verify that it gives interesting, smooth results.

Now comes the real work.  This is great, but we also want analytic gradients for our fields, so that we can compute perfect normals for the surfaces rather than using ugly central differences.  Perfect normals go a long way towards making the polygonized result look good.  It's a bit painful, but if you just remember your multivariable calculus (I'll admit I struggled with trying to remember it for quite a while), it's not too terrible.  It's just application of a bunch of  rules.  I'm going to spare the derivation and give the result:

\nabla f(x) = \left(\sum_i^k{\left({\frac{x \cdot n_i}{d_i}}\right)}^p \right)^{\frac{1}{p}-1} \left(\sum_i^k n_i {\left({\frac{x \cdot n_i}{d_i}}\right)}^{p-1} \right)

The left side is a scalar factor, closely related to the field value.  The right side is the actual vector component, which is just a sum of scaled plane normals.  All of it can be easily implemented in a single loop over the planes!

With these formulas in hand, you can create lots of cool, smooth shapes. Boxes, discrete cylinders, prisms, etc...or just random convex shapes!

Smooth Convex Cylinder

Smoother Convex Cylinder

 

If you're wondering how I came up with these formulas, it was by studying and generalizing the field formula for a smooth box, which is pretty obvious. This polyhedron formula is less obvious, in my opinion, but is still basically just a straightforward generalization of the box formula.

PS ~ As usual, I invite any lurking mathies to speak up if I've made a blunder :)

PPS ~ I hope you like the Latex plugin that I installed, solely for the purpose of this post..

Stable Exponential Smoothing Under Variable Framerate

The title might sound fancy, but this post is about a very practical thing that you might encounter quite often. A great way to smooth any kind of changing feature in your game is to use linear interpolation each frame to interpolate between the current value and the target value, like so:

myVar = lerp(myVar, target, 0.5)

It's so easy! And it creates a very nice, smooth transition between the old value of myVar and the new value, target. If you think about it for a bit, you'll realize that this thing is somehow exponential, because the rate at which myVar approaches target is obviously dependent on the difference between myVar and target. Hence the "exponential smoothing" in the title.

Now, there's a bit of a problem: where did I get the value 0.5? I could have just played with the constant until I was pleased with the rate of smoothing. But there's a bigger problem than arbitrary constants here: this code is highly framerate-dependent. Why? Well, if we're running at 60fps, then this interpolation happens 60 times in a second, which will obviously leave myVar a lot closer to target than if we were running at 10fps and the interpolation happened 10 times. The end result? You will notice things happening faster when your framerate is higher, even if you're using the proper time differential for physics. The problem is that we didn't account for the time differential when we wrote this function.

I'm not going to put the full derivation in this post, since my blog doesn't support Latex yet...but I will give you the answer to this problem:

myVar = lerp(myVar, target, 1. - pow(.5, dt))

What exactly is going on here? You can see that I'm now using dt, which is the time differential between frames (hence, we are taking into account framerate). But what of the pow and the .5? It turns out that the .5 now has a very precise meaning - it means that for every second that passes, .5 of the difference between myVar and target will decay. So after 3 seconds, myVar will have come 87.5% of the way to target (measuring from the initial value of myVar). This gives you a very easy way to think about the constant!

Not only is this a great little math trick to have up your sleeves, but it turns out that it is intimately related to the solution for making linear drag framerate-independent, which is something that you will not achieve if you just do the obvious discrete physics. I'll probably post on that later :)