Creating haptics using Signed Distance Functions (SDF)

One of the most important steps when doing interactive haptics is calculating collisions between the object that user is touching and all the points of interaction of the haptic device. While most force feedback devices (such as the ones from Sensable) have only one, others (like many vibrotactile gloves) have more than ten.

A important limitation we must be aware of is that the algorithm in charge of calculating the haptic response needs to run in real time up to 1000 times per second, therefore it is mandatory to speed up all the calculations as much as possible.

The use of bounding boxes is a popular solution to save valuable computation time. Taking one point in space and checking if it’s inside the bounding box can be done very efficiently. However if the point is inside the bounding box we still need to calculate the distance to the surface in order to generate a force or a tactile stimulli.

One of the most efficient ways of calculating this distance is using Signed Distance Functions (SDF). A SDF is a function that given a 3D point in space outputs the distance to the nearest surface. The distance is usually signed positive if the point is inside any object, negative if it’s outside and zero if it’s on the boundary.

For geometric figures we can define SDF’s using mathematical expressions. The great advantage of this is that the computation complexity is constant O(1) as we don’t need to loop through any data structure. Furthermore, this implicit representation is continuous and exact, unlike if it was defined with a polygonal mesh.

SDF’s of Regular Shaped Objects

The following functions in C# can be used in Unity to calculate the SDFs of regular shaped objects. As stated earlier the value is:

• > 0 the point is inside the object
• 0 the point is on the surface
• < 0 the point is outside the object

Note that we consider the objects centered at the origin of their coordinate system.

Sphere

This is the easiest one. The function returns the exact value.

float SphereSDF (Vector3 p, float radius)
{
  return radius - p.magnitude;
}

This is the visual representation of the field with isolines in the XY and XZ planes. Isolines represent regions of space where the value of the function is the same.

Cube

The following function is a simplification that provides the exact boundary. However, the distance values on the outside are approximations, as we can see in the sharp edges of the iso-lines. Depending on the application, these sharp edges of the isolines can be useful.

float CubeApproxSDF (Vector3 p, float side)
{
  return side * 0.5f - Mathf.Max( Mathf.Abs(p.x), 
         Mathf.Max( Mathf.Abs(p.y), Mathf.Abs(p.z) ) );
}

The following function calculates the exact SDF. Note the curved edges of the isolines on the outside.

float CubeExactSDF(Vector3 p, float side)
{
  Vector3 s = new Vector3(side, side, side) * 0.5f;
  Vector3 q = Abs(p) - s;
  return -Max(q, 0.0f).magnitude - 
    Mathf.Min(Mathf.Max(q.x, Mathf.Max(q.y, q.z)), 0f);
}

Cylinder

Like in the previous case, this is the function with sharp isolines:

public static float CylinderApproxSDF(Vector3 p, float radius, float height)
{
  return Mathf.Min( radius - Mathf.Sqrt(p.x * p.x + p.z * p.z), 
        height * 0.5f - Mathf.Abs(p.y) );
}

Function with the exact SDF:

public static float CylinderExactSDF(Vector3 p, float radius, float height)
{
  float l = (new Vector2(p.x, p.z)).magnitude;
  Vector2 v = new Vector2(l, p.y);
  Vector2 w = new Vector2(radius, height * 0.5f);
  Vector2 d = Abs(v) - w;			
  return Mathf.Min(Mathf.Max(d.x, d.y), 0.0f) + Max(d, 0.0f).magnitude;
}

Cone

Function with sharp isolines:

public static float ConeApproxSDF(Vector3 p, float radius, float height)
{
  return Math.Min(radius * (0.5f - p.y / height) - Mathf.Sqrt(p.x * p.x + p.z * p.z), height * 0.5f - Math.Abs(p.y));
}

Function with the exact SDF

float ConeExactSDF(Vector3 p, float h, float r)
{
  Vector2 q = new Vector2(new Vector2(p.x, p.z).magnitude, p.y);
  Vector2 k1 = new Vector2(0f, h);
  Vector2 k2 = new Vector2(-r, 2f * h);
  Vector2 ca = new Vector2(q.x - Mathf.Min(q.x, q.y < 0f ? r : 0f), Mathf.Abs(q.y) - h);
  Vector2 cb = q - k1 + k2 * Mathf.Clamp01(Vector2.Dot(k1 - q, k2) / k2.sqrMagnitude);
  float s = (cb.x < 0f && ca.y < 0f) ? -1f : 1f;
  return s * Mathf.Sqrt(Mathf.Min(ca.sqrMagnitude, cb.sqrMagnitude));
}

Pyramid

Function with sharp isolines

public static float PyramidApproxSDF(Vector3 p, float side, float height)
{
  return Mathf.Min(side * 0.5f * (0.5f - p.y / height) - Mathf.Max(Mathf.Abs(p.x), Mathf.Abs(p.z)), height / 2f - Mathf.Abs(p.y));
}

For the sake of completeness, I’ve used the following functions in the SDF implementations:

static Vector3 Abs(Vector3 p)
{
  return new Vector3(Mathf.Abs(p.x), Mathf.Abs(p.y), Mathf.Abs(p.z));
}
static Vector3 Max(Vector3 p, float v)
{
  return new Vector3(Mathf.Max(p.x, v), Mathf.Max(p.y, v), Mathf.Max(p.z, v));
}
static Vector3 Min(Vector3 p, float v)
{
  return new Vector3(Mathf.Min(p.x, v), Mathf.Min(p.y, v), Mathf.Min(p.z, v));
}
static Vector2 Abs(Vector2 p)
{
  return new Vector2(Mathf.Abs(p.x), Mathf.Abs(p.y));
}
static Vector2 Max(Vector2 p, float v)
{
  return new Vector2(Mathf.Max(p.x, v), Mathf.Max(p.y, v));
}
static Vector2 Min(Vector2 p, float v)
{
  return new Vector2(Mathf.Min(p.x, v), Mathf.Min(p.y, v));
}

Moving, Rotating and Scaling SDFs

We can move, rotate and scale these mathematical primitives changing any point defined in world coordinates to the local coordinate system of the SDF.

Considering a SDF with arbitrary rotation q, position v, and scale s, the following function gets the local coordinates of point.

Vector3 WorldToLocalCoordinates(Quaternion q, Vector3 v, Vector3 s, Vector3 point)
{
  Vector3 sInv = new Vector3 (1f/s.X, 1f/s.Y, 1f/s.Z);
  return sInv * ( Quaternion.Inverse(q) * (point - v) );
}

Combining SDFs

SDF can be combined and transformed in many ways. For instance, we can do Constructive Solid Geometry defining the following operations:

Union

float Union (float a, float b)
{
  return Mathf.Max(a, b);
}

Intersection

float Intersection (float a, float b)
{
  return Mathf.Min(a, b);
}

Difference

float Difference (float a, float b)
{
  return Mathf.Min(-a, b);
}

More Information

Find more interesting SDF definitions and transformations at the website of Inigo Quilez.

Visualizations have been made with a modified version of the SDF Inspector, powered by ShaderToy.