{"id":437,"date":"2016-03-07T11:22:26","date_gmt":"2016-03-07T16:22:26","guid":{"rendered":"https:\/\/blogs.mathworks.com\/graphics\/?p=437"},"modified":"2016-03-07T11:22:26","modified_gmt":"2016-03-07T16:22:26","slug":"signed-distance-fields","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/graphics\/2016\/03\/07\/signed-distance-fields\/","title":{"rendered":"Signed Distance Fields"},"content":{"rendered":"\r\n

Recently I heard from a MATLAB user who was trying to draw tubes along a curve using this blog post<\/a> I wrote a while back. Unfortunately her curve was a bit more complex than the ones I used in that post. That approach of sweeping a 2D shape along a curve has a number of interesting edge cases that you'll encounter when your curves are complex.<\/p>

In particular, her curve actually had a \"fork\" in it. This is a particularly tough case for the sweep approach. You basically need to sweep each of the two halves of the fork, and then slice off the parts of one sweep that are inside the other one. The math for this gets rather tricky.<\/p>

Luckily there's another approach to this problem. This one is fairly compute intensive, but it's quite a bit simpler to implement. It's called signed distance fields<\/a>. Let's take a look at how you would solve this problem using an SDF.<\/p>

First we'll need some sample data. Here's one I made. I have 4 vertices.<\/p>

verts = [-1    0 0; ...<\/span>\r\n        1\/2    0 0; ...<\/span>\r\n          2  3\/4 0; ...<\/span>\r\n          2 -3\/4 0];\r\nradius = .5;\r\n<\/pre>
And I have 3 line segments which connect the four vertices.<\/p>
segments = [1 2; 2 3; 2 4];\r\n<\/pre>
Let's draw the segments.<\/p>
for<\/span> i=1:size(segments,1)\r\n    line(verts(segments(i,:),1),verts(segments(i,:),2),verts(segments(i,:),3))\r\nend<\/span>\r\nbox on<\/span>\r\ndaspect([1 1 1])\r\nview(3)\r\n<\/pre>\"\" 
So we want a tube-like surface which follows those line segments, and smoothly blends between two which fork off to the right.<\/p>
The first thing we'll do is build a 3D grid over the space we're interested in. The bigger you make the grid, the better your surface will be, but the amount of memory you’re using will climb quickly.<\/p>
[y,x,z] = ndgrid(linspace(-1.25,1.25,90),linspace(-1,2.25,90),linspace(-0.75,0.75,45));\r\n<\/pre>
And now we'll create a 4th array to hold our signed distance field.<\/p>
d = zeros(size(z));\r\n<\/pre>
Now we loop over all of the grid points. At each point in the grid, we'll loop over all of the line segments and calculate the distance from the grid point to the closest point on the line segment. We'll keep the smallest distance and save it in d.<\/p>
for<\/span> i=1:numel(z)\r\n    p = [x(i),y(i),z(i)];\r\n\r\n    % Intialize our distance to inf.<\/span>\r\n    closest = inf;\r\n\r\n    % Loop over all of the line segments.<\/span>\r\n    for<\/span> j=1:size(segments,1)\r\n        q1 = verts(segments(j,1),:);\r\n        q2 = verts(segments(j,2),:);\r\n\r\n        % For line segment q1 + t*(q2-q1), compute the value of t where<\/span>\r\n        % distance to p is minimized. Clamp to [0 1] so we don't go off<\/span>\r\n        % the end of the line segment.<\/span>\r\n        invlen2 = 1\/dot(q2-q1,q2-q1);\r\n        t = max(0,min(1,-dot(q1-p,q2-q1)*invlen2));\r\n        v = q1 + t*(q2-q1);\r\n\r\n        % Is that  the smallest we've seen for this grid element?<\/span>\r\n        closest = min(closest, norm(v-p)-radius);\r\n    end<\/span>\r\n\r\n    % Insert the distance into the array.<\/span>\r\n    d(i) = closest;\r\nend<\/span>\r\n<\/pre>
Notice that the value I saved into the array d was the distance from that grid point to a line segment, minus the radius of the surface at that point on the line segment. That means that anywhere in our grid that d is less than 0 is inside the tube, and anywhere that d is greater than 0 is outside the tube. As we saw in this post<\/a> about implicit surfaces, this is a job for the isosurface function<\/a>.<\/p>
isosurface(x,y,z,d,0)\r\ncamlight\r\n<\/pre>\"\" 
And we can see that this surface lines up nicely with our original model, and does a nice job of blending that fork.<\/p>
Let's delete the lines and change the view so we can see inside the fork. See how tidy that intersection is? That would be hard to do with the other approach.<\/p>
Also notice how it rounds off the ends. We can see inside because I made the grid pretty tight. If my grid had been a bit larger, then each of the three ends would be capped by a hemisphere. This is characteristic of the signed distance fields approach.<\/p>
delete(findobj(gca,'Type'<\/span>,'line'<\/span>))\r\nview([41 18])\r\n<\/pre>\"\" 
But what if we had a different radius at each vertex, and wanted the tube to interpolate between the radii at the end of each segment?<\/p>
Let's say that we wanted the following radii at each vertex.<\/p>
radii = [.5 .45 .125 .25];\r\n\r\ncla\r\nfor<\/span> i=1:size(segments,1)\r\n    line(verts(segments(i,:),1),verts(segments(i,:),2),verts(segments(i,:),3))\r\nend<\/span>\r\n[xs,ys,zs] = sphere;\r\nfor<\/span> i=1:size(verts,1)\r\n    surface(verts(i,1)+radii(i)*xs, ...<\/span>\r\n            verts(i,2)+radii(i)*ys, ...<\/span>\r\n            verts(i,3)+radii(i)*zs, ...<\/span>\r\n        'FaceColor'<\/span>,'yellow'<\/span>,'EdgeColor'<\/span>,'none'<\/span>);\r\nend<\/span>\r\ncamlight\r\n<\/pre>\"\" 
This is a little trickier, but it's basically just a matter of changing our distance function. We can no longer use the simple formula for the distance between a point and the centerline.<\/p>
I found a distance function that will do the job in this paper<\/a>:<\/p>
\r\n\r\n
Fast distance computation between a point and cylinders, cones,\r\n  line swept spheres and cone-spheres<\/td><\/tr>\r\n
Aurelien Barbier and Eric Galin<\/td><\/tr>\r\n
LIRIS - CNRS<\/td><\/tr>\r\n
Universite Claude Bernard Lyon 1<\/td><\/tr>\r\n
69622 Villeurbanne Cedex, France<\/td><\/tr>\r\n<\/table>\r\n<\/p>
The authors call this primitive with a centerline and a radius at each end the \"cone-sphere\" primitive.<\/p>
This distance equation is more complex, so I'll precompute some terms to help with performance.<\/p>
nsegments = size(segments,1);\r\ninvlen2 = zeros(1,nsegments);\r\ntrange = zeros(nsegments,2);\r\nadj_radii = zeros(nsegments,2);\r\nfor<\/span> i=1:nsegments\r\n    q1 = verts(segments(i,1),:);\r\n    q2 = verts(segments(i,2),:);\r\n    len2 = dot(q2-q1,q2-q1);\r\n    invlen2(i) = 1\/len2;\r\n\r\n    r1 = radii(segments(i,1));\r\n    r2 = radii(segments(i,2));\r\n    delta = r1-r2;\r\n    s = sqrt(len2 - delta^2);\r\n\r\n    dl = delta * invlen2(i);\r\n    sl = s * sqrt(invlen2(i));\r\n\r\n    trange(i,1) = r1 * dl;\r\n    trange(i,2) = 1 + r2 * dl;\r\n    adj_radii(i,1) = r1 * sl;\r\n    adj_radii(i,2) = r2 * sl;\r\nend<\/span>\r\n<\/pre>
Now we can repeat our loop with this new distance formula.<\/p>
for<\/span> i=1:numel(z)\r\n    p = [x(i),y(i),z(i)];\r\n\r\n    closest = inf;\r\n    for<\/span> j=1:size(segments,1)\r\n        q1 = verts(segments(j,1),:);\r\n        q2 = verts(segments(j,2),:);\r\n        r1 = radii(segments(j,1));\r\n        r2 = radii(segments(j,2));\r\n\r\n        t = -dot(q1-p,q2-q1)*invlen2(j);\r\n        if<\/span> t<trange(j,1)\r\n            v = q1;\r\n            r = r1;\r\n        elseif<\/span> t>trange(j,2)\r\n            v = q2;\r\n            r = r2;\r\n        else<\/span>\r\n            v = q1 + t*(q2-q1);\r\n            adj_t = (t-trange(j,1)) \/ (trange(j,2)-trange(j,1));\r\n            r = adj_radii(j,1) + adj_t*(adj_radii(j,2)-adj_radii(j,1));\r\n        end<\/span>\r\n\r\n        closest = min(closest, norm(v-p)-r);\r\n    end<\/span>\r\n\r\n    d(i) = closest;\r\nend<\/span>\r\n<\/pre>
And then we can use isosurface, just like we did before.<\/p>
isosurface(x,y,z,d,0)\r\n<\/pre>\"\" 
See how the surface lines up with the spheres? Now we'll delete them to get a better look.<\/p>
delete(findobj(gca,'Type'<\/span>,'line'<\/span>))\r\ndelete(findobj(gca,'Type'<\/span>,'surface'<\/span>))\r\n<\/pre>\"\" 
Here's another isosurface I made from these 6 edges of a tetrahedron using this technique.<\/p>
verts = randn(4,3);\r\nsegments = nchoosek(1:4,2);\r\nradii = 5\/8 * rand(1,4);\r\n<\/pre>
\"\" <\/p>
That took quite a while to compute, but it would have been awful tricky to draw it with the sweep approach.<\/p>
Whenever you want to wrap a surface around a complex shape, then signed distance functions are a technique that you should consider.<\/p>