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

6 thoughts on “Distance Fields for Smoothed, Convex Polyhedra”

  1. My math skills are too low to understand the formulae, but I understand what you're doing. To me it seems that by making a shape with a formula you're not only make it mathematically correct, but you also save yourself the time of having to manually draw hundreds of shapes.
    Now I'm wondering how much time and money you're actually saving doing it this way. Even if we don't think about the infinite possibilities.

    Supposed you get this to work the way you want... How difficult would it be to display ships being cut in half by lasers, or getting pierced/chunks blown out?

    1. Exactly, my infatuation with procedural stuff isn't because of the math or anything like that - it's because of how much time it saves. There's just no other way that a team of one could make this game.

      For the second question, I'm glad you asked! Actually, that kind of thing becomes effortless when everything is described with formulae. I've already done some tests and built some destroyed ship models. It's amazing, because I never could have done it the old way. But yes, now I can pretty much do whatever I want - ships being blown to pieces (that actually fit together properly), cut in half, chunks blown out of the hull, etc.

      Very exciting possibilities :D

  2. Absolutely fascinating Josh, you seem adept at reducing complexity in favour of simple elegant solutions, always a thrill to read. Also enjoying the daily dev diary.

    I hope you are making multiple back ups of this amazing game, achieving all this with a one man team is great, but make sure you have a cloud back up or something set apart, that does not get fried if you have some local inclement weather!

  3. simply amazing..., josh congrats on getting this working man!, so basically this system eliminates the polygon count? or it doesn't use polygons at all to render 3D models? but rather bendy pieces of 2D faces? thanks for showing this amazing piece of work which i swear have not seen anything like it in other games!

  4. Impressive Josh, I'm amazed with your work and... well... another possibility, i guess, if you change the formulas shaping the geometry on the fly... you would get dynamic deformations.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>