{"id":274,"date":"2015-07-22T10:08:24","date_gmt":"2015-07-22T14:08:24","guid":{"rendered":"https:\/\/blogs.mathworks.com\/graphics\/?p=274"},"modified":"2015-07-22T10:08:24","modified_gmt":"2015-07-22T14:08:24","slug":"implicit-surface-intersections","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/graphics\/2015\/07\/22\/implicit-surface-intersections\/","title":{"rendered":"Implicit Surface Intersections"},"content":{"rendered":"

Implicit Surface Intersections<\/h3>

We talked about implicit surfaces here back in March<\/a>. Recently, there was an interesting question about them<\/a> on MATLAB Answers.<\/p>

Dr. Vyas has a surface which is defined by the following equation.<\/p>

$$y - x*tan(z) = 0$$<\/p>

It apparently comes from a problem involving polarization of light by crystals.<\/p>

He has already figured out how to compute the surface ...<\/p>

[x3, y3,z3] = meshgrid(linspace(-1.25, 1.25, 150), ...<\/span>\r\n                       linspace(-1.25, 1.25, 150), ...<\/span>\r\n                       linspace(0, 2*pi, 150));\r\nf2 = y3-x3.*tan(z3);\r\nhel = isosurface(x3, y3, z3, f2, 0);\r\n<\/pre>
... and draw it using the technique we talked about in that blog post.<\/p>
patch(hel,'FaceColor'<\/span>,[1 .5 0],'EdgeColor'<\/span>,'none'<\/span>);\r\nview(3)\r\ncamlight\r\nax = gca;\r\nset(ax,'XLim'<\/span>,[-inf inf],'YLim'<\/span>,[-inf inf],'ZLim'<\/span>,[-inf inf],'DataAspectRatio'<\/span>,[1 1 1])\r\nbox on<\/span>\r\nxlabel('x(mm)'<\/span>)\r\nylabel('y(mm)'<\/span>)\r\nzlabel('\\Lambda[rad]'<\/span>)\r\n<\/pre>\"\" 
But now he wants to compute the interesection of that surface and the cylinder defined by this equation:<\/p>
$$x^2 + y^2 = 1$$<\/p>
In general, computing the interestion of implicit surfaces is a fairly challenging problem. There are three basic approaches.<\/p>
  1. Find an analytic solution for the intersection.<\/li>
  2. Find an intersection point, and then use a tracing scheme to generate the curve.<\/li>
  3. Calculate the intersection on the grid we're using to draw the surfaces.<\/li><\/ol><\/div>
    The first two approaches can be fairly involved in some cases, but the third approach generally isn't too hard to implement. Let's walk through that approach in detail.<\/p>
    First we take the vertices we got from the isosurface, and create a logical mask of all of the vertices which are outside the cylinder. To do that, we just need to compute the radius for each vertex, and then compare that to 1.<\/p>
    r = sqrt(hel.vertices(:,1).^2 + hel.vertices(:,2).^2);\r\ncylrad = 1;\r\nmask = r>cylrad;\r\n<\/pre>
    For each triangle, count the number of vertices which are outside the cylinder.<\/p>
    outcount = sum(mask(hel.faces),2);\r\n<\/pre>
    If the number of outside vertices is 0 or 3, then we don't care about the triangle. That's because those triangles are completely inside or completely outside the cylinder. This means that they can't contribute to the intersection curve.<\/p>
    If the number of outside vertices is 1 or 2, then the triangle crosses the cylinder. These are the triangles we're interested in.<\/p>
    cross = (outcount == 2) | (outcount == 1);\r\ncrossing_tris = hel.faces(cross,:);\r\n<\/pre>
    Let's take a quicky look at those triangles.<\/p>
    cla\r\nct = patch('Vertices'<\/span>,hel.vertices,'Faces'<\/span>,crossing_tris,'EdgeColor'<\/span>,[1 .5 0],'FaceColor'<\/span>,[.5 1 .5]);\r\n<\/pre>\"\" 
    That looks pretty close. If we zoom in we can see that we have a thin band of triangles which go around the part of the surface which crosses the cylinder.<\/p>
    xlim([-.375 .375])\r\nylim([-1 -.75])\r\nzlim([1.3 1.8])\r\n<\/pre>\"\" 
    Now we need to take each of those triangles and turn it into a line segment which shows the intersection.<\/p>
    The math for calculating the intersection actually involves terms which cancel out so that the calculation for the 1-out and 2-out triangles look the same. So at this point we'll simplify things by flipping all of the 1-out triangles around so that they look like 2-out triangles. That way we only have to deal with one type of triangle.<\/p>
    out_vert = mask(crossing_tris);\r\nflip = sum(out_vert,2) == 1;\r\nout_vert(flip,:) = 1-out_vert(flip,:);\r\n<\/pre>
    Here's where things get a little messy. Each row of out_vert contains one 0 and two 1's. We want to draw a line between the edges of the triangles which connect the vertex with the 0 with each of the two vertices with a 1.<\/p>
    I'm sure there's a cleaner way to do this, but here's what I came up with.<\/p>
    ntri = size(out_vert,1);\r\novert = zeros(ntri,3);\r\nfor<\/span> i=1:ntri\r\n    v1i = find(~out_vert(i,:));\r\n    v2i = 1 + mod(v1i,3);\r\n    v3i = 1 + mod(v1i+1,3);\r\n    overt(i,:) = crossing_tris(i,[v1i v2i v3i]);\r\nend<\/span>\r\n<\/pre>
    It's all downhill from there!<\/p>
    Next we need to calculate where each of those two edges of the triangle cross the cylinder.<\/p>
    We've already computed the radius at each vertex, so we can compute u & v parameters for linear interpolation like this:<\/p>
    u = (cylrad - r(overt(:,1))) .\/ (r(overt(:,2)) - r(overt(:,1)));\r\nv = (cylrad - r(overt(:,1))) .\/ (r(overt(:,3)) - r(overt(:,1)));\r\n<\/pre>
    And then use those to do the linear interpolation to compute the position where the edge crosses the cylinder like this:<\/p>
    uverts = repmat((1-u),[1 3]).*hel.vertices(overt(:,1),:) + repmat(u,[1 3]).*hel.vertices(overt(:,2),:);\r\nvverts = repmat((1-v),[1 3]).*hel.vertices(overt(:,1),:) + repmat(v,[1 3]).*hel.vertices(overt(:,3),:);\r\n<\/pre>
    Next we use the 3-row with nan trick I described in this post<\/a> to convert those pairs of vertices into one line object.<\/p>
    x = nan(3,ntri);\r\nx(1,:) = uverts(:,1)';\r\nx(2,:) = vverts(:,1)';\r\ny = nan(3,ntri);\r\ny(1,:) = uverts(:,2)';\r\ny(2,:) = vverts(:,2)';\r\nz = nan(3,ntri);\r\nz(1,:) = uverts(:,3)';\r\nz(2,:) = vverts(:,3)';\r\n<\/pre>
    OK, now we'll draw the resulting lines on top of the triangles we had earlier.<\/p>
    h = line(x(:),y(:),z(:));\r\n<\/pre>\"\" 
    And then zoom back out.<\/p>
    delete(ct)\r\nset(ax,'XLim'<\/span>,[-inf inf],'YLim'<\/span>,[-inf inf],'ZLim'<\/span>,[-inf inf],'DataAspectRatio'<\/span>,[1 1 1])\r\nh.Color = ax.ColorOrder(5,:);\r\nh.LineWidth = 2;\r\n<\/pre>\"\" 
    Next we can add the helical surface back in, and turn it so we can see things a little more clearly.<\/p>
    p = patch('Vertices'<\/span>,hel.vertices,'Faces'<\/span>,hel.faces,'EdgeColor'<\/span>,'none'<\/span>);\r\np.FaceColor = ax.ColorOrder(2,:);\r\nlight('Position'<\/span>,[-7 -8 90])\r\nlight('Position'<\/span>,[-1 1 .25])\r\nset(p,'SpecularStrength'<\/span>,.6,'DiffuseStrength'<\/span>,.85,'AmbientStrength'<\/span>,.15,'BackFaceLighting'<\/span>,'reverselit'<\/span>)\r\nset(ax,'CameraPosition'<\/span>,[-4 7 15],'CameraUpVector'<\/span>,[-1 0 0])\r\n<\/pre>\"\" 
    And we can add the cylinder like this:<\/p>
    f1 = x3.^2+y3.^2-1;\r\ncyl = patch(isosurface(x3, y3, z3, f1, 0),'EdgeColor'<\/span>, 'none'<\/span>);\r\ncyl.FaceColor = ax.ColorOrder(1,:);\r\nset(cyl,'SpecularStrength'<\/span>,.6,'DiffuseStrength'<\/span>,.85,'AmbientStrength'<\/span>,.15,'BackFaceLighting'<\/span>,'reverselit'<\/span>)\r\n<\/pre>\"\" 
    Finally, let's look at it with just the cylinder and the intersection curve.<\/p>
    xlim([-1.25 1.25])\r\nylim([-1.25 1.25])\r\np.Visible = 'off'<\/span>;\r\n<\/pre>\"\" 
    If you're working with implicit surfaces, you'll probably find that this is a useful technique to have in your toolbox. You can also modify it to do a number of other interesting things. For example, if I had just kept the triangles with a outcount of 0, I would have gotten just the portion of the surface which lies on the inside of the cylinder.<\/p>
    cla\r\nax = gca;\r\ncrossing_tris = hel.faces(outcount==0,:);\r\np = patch('Vertices'<\/span>,hel.vertices,'Faces'<\/span>,crossing_tris,'FaceColor'<\/span>,ax.ColorOrder(2,:),'EdgeColor'<\/span>,'none'<\/span>);\r\nview(3)\r\nset(ax,'XLim'<\/span>,[-inf inf],'YLim'<\/span>,[-inf inf],'ZLim'<\/span>,[-inf inf],'DataAspectRatio'<\/span>,[1 1 1])\r\nbox on<\/span>\r\nlight('Position'<\/span>,[-7 -8 90])\r\nlight('Position'<\/span>,[-1 1 .25])\r\nset(p,'SpecularStrength'<\/span>,.6,'DiffuseStrength'<\/span>,.85,'AmbientStrength'<\/span>,.15,'BackFaceLighting'<\/span>,'reverselit'<\/span>)\r\nset(ax,'CameraPosition'<\/span>,[-4 7 15],'CameraUpVector'<\/span>,[-1 0 0])\r\nxlabel('x(mm)'<\/span>)\r\nylabel('y(mm)'<\/span>)\r\nzlabel('\\Lambda[rad]'<\/span>)\r\n<\/pre>\"\" 
    To do a really nice job of this, we would need to trim the triangles which cross the cylinder. The math for that would be similar to what we did to generate those lines.<\/p>
    We could extend this even further and trim each of the surfaces against the other. Then we'd get the region bounded by those surfaces without any extraneous bits.<\/p>
    Can you think of other things you could do with this technique? Do you have some interesting implicit surfaces you could use this on? I'd love to see what you can create with it.<\/p>