Distance Fields for Smoothed, Convex Polyhedra

January 23, 2013 General News 6 Comments

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