{"id":239,"date":"2015-05-12T09:49:20","date_gmt":"2015-05-12T13:49:20","guid":{"rendered":"https:\/\/blogs.mathworks.com\/graphics\/?p=239"},"modified":"2015-05-12T09:53:08","modified_gmt":"2015-05-12T13:53:08","slug":"patch-work","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/graphics\/2015\/05\/12\/patch-work\/","title":{"rendered":"Patch Work"},"content":{"rendered":"

Patch Work<\/h3>

Back before the internet, programmers collected xeroxed copies of old notes and papers. We traded these with our friends and coworkers, like samizdat<\/a>. I still have a large filing cabinet full of these.<\/p>

One of my favorites is:<\/p>

\r\n

\r\n  Patch Work\r\n  Rob Cook\r\n  Technical Memo #118\r\n  Computer Division\r\n  Lucasfilm Ltd\r\n<\/pre>\r\n<\/p>
You can find some of the other old Lucasfilm technical memos in Pixar's library<\/a>. But as far as I know, this one has never appeared on the internet.<\/p>
The \"Patch Work\" memo was a collection of useful tidbits about the different types of patches which were used for representing smooth surfaces. Rob collected these from work that had been done by Loren Carpenter<\/a>, Ed Catmull<\/a>, and Tom Duff<\/a>. If you worked with surface patches, it was really handy to have a single, short memo with all of this useful information collected in one place. That made this one of the more valuable graphics samizdats.<\/p>
Let's take a quick look at some of what's in this wonderful old memo.<\/p>
First we'll need some control points. All of these patches need a 4x4 matrix of control points. To make it easy to see what's going on, I'm going to spread these points out evenly in X & Y and give them different Z values, but you can use any points you like.<\/p>
[px, py] = meshgrid(1:4);\r\npz = magic(4) \/ 8;\r\n<\/pre>
First we'll draw them using stem3.<\/p>
p = stem3(px,py,pz,'filled'<\/span>);\r\ndaspect([1 1 1])\r\nax = gca;\r\nax.XTick = 1:4;\r\nax.YTick = 1:4;\r\ncolor = [.15 .15 .15];\r\np.Color = color;\r\n<\/pre>\"\" 
We can connect them into their 4x4  grid by using a surface with FaceColor='none'.<\/p>
hold on<\/span>\r\ncpts = surf(px,py,pz);\r\ncpts.FaceColor = 'none'<\/span>;\r\ncpts.EdgeColor = [.85 .85 .85];\r\n<\/pre>\"\" 
Now we're ready to create some patches. All of the patches take the same form. A pair of parameter values u & v yield a point when they're substituted into the following equation.<\/p>
\"$$x<\/p>
In this equation, the matrix P is our 4x4 matrix of control points, and the matrix M is called the \"basis matrix\" of the patch. The memo covers several different basis matrices, starting with our old favorite, the cubic Bézier patch<\/a>. This is the patch that we saw in my first blog post here<\/a> when we were looking at Newell's teapot. You'll also notice the similarities to the equation for the cubic Bézier curve we saw in my second post<\/a>.<\/p>
Mbezier = [-1  3 -3 1; ...<\/span>\r\n            3 -6  3 0; ...<\/span>\r\n           -3  3  0 0; ...<\/span>\r\n            1  0  0 0];\r\n<\/pre>
We can use that to generate a surface with one set of isoparameter lines like this:<\/p>
M = Mbezier;\r\n\r\n% U & V vectors<\/span>\r\nu = linspace(0,1,50);\r\nv = linspace(0,1,50)';\r\nu_powers = [u.^3; u.^2; u; ones(size(u))];\r\nv_powers = [v.^3, v.^2, v, ones(size(v))];\r\n\r\n% Multiply to get X,Y, & Z<\/span>\r\nxout = v_powers * M * px * M' * u_powers;\r\nyout = v_powers * M * py * M' * u_powers;\r\nzout = v_powers * M * pz * M' * u_powers;\r\n\r\n% Draw as a surface<\/span>\r\nhold on<\/span>\r\ns = surf(xout,yout,zout);\r\ns.FaceColor = 'none'<\/span>;\r\ns.MeshStyle = 'row'<\/span>;\r\n<\/pre>\"\" 
And then the show the other set of isoparameter lines like this:<\/p>
s.MeshStyle = 'column'<\/span>;\r\n<\/pre>\"\" 
or as a shaded surface with lighting.<\/p>
s.EdgeColor = 'none'<\/span>;\r\ns.FaceColor = 'interp'<\/span>;\r\ns.FaceLighting = 'gouraud'<\/span>;\r\ns.SpecularStrength = 5\/8;\r\nlight('Position'<\/span>,[9 -5 8])\r\n<\/pre>\"\" 
A coarser colormap will add \"waterlevel\" lines.<\/p>
colormap(lines(20))\r\n<\/pre>\"\" 
Notice that the Bézier patch has the same characteristics we saw in the earlier blog post about the curves. It passes through the 4 control points in the corners of the 4x4 set, it's tangent to the control point mesh at those corners, and it's completely contained within the bounds of the control point mesh. These are really useful properties and they make Bézier very easy to work with.<\/p>
The \"Patch Work\" memo includes the basis matrices for a number of other types of patches, but some of them are a little trickier to work with.<\/p>
Let's try the Catmull-Rom<\/a> patch.<\/p>
Mcatmullrom = [-1  3 -3  1; ...<\/span>\r\n                2 -5  4 -1; ...<\/span>\r\n               -1  0  1  0; ...<\/span>\r\n                0  2  0  0] \/ 2;\r\nM = Mcatmullrom;\r\ns.XData = v_powers * M * px * M' * u_powers;\r\ns.YData = v_powers * M * py * M' * u_powers;\r\ns.ZData = v_powers * M * pz * M' * u_powers;\r\n<\/pre>\"\" 
It's a little hard to see from that viewing angle, but the way a Catmull-Rom spline works is that it connects the inner 2x2 points of our control point mesh.<\/p>
view(-37.5,60)\r\n<\/pre>\"\" 
The other points in the control mesh of a Catmull-Rom patch simply control the tangents at the edges of the patch. The way you usually use these is to have two rows of control points be shared between neighboring patches. This ensures that the patches have a nice, smooth blend where they meet. It is possible to get the same effect with Bézier patches, but it is a little bit trickier.<\/p>
The basis matrix for the B-spline patch looks like this.<\/p>
Mbspline = [-1  3 -3 1; ...<\/span>\r\n             3 -6  3 0; ...<\/span>\r\n            -3  0  3 0; ...<\/span>\r\n             1  4  1 0] \/ 6;\r\nM = Mbspline;\r\ns.XData = v_powers * M * px * M' * u_powers;\r\ns.YData = v_powers * M * py * M' * u_powers;\r\ns.ZData = v_powers * M * pz * M' * u_powers;\r\nview(3)\r\n<\/pre>\"\" 
You can see that this patch also only covers the inner 2x2 of our control point mesh, and it doesn't even pass through those points. This property makes the B-spline patch kind of challenging to work with when you're trying to model something.<\/p>
But the \"patch work\" memo also shows how to convert the control points of one kind of patch to those of another kind of patch. To do this, we need what it calls \"to-from\" matrices. We can use this to convert our friendly Bézier patch control points into ones which work for the B-spline patch by using this matrix.<\/p>
Mtofrom = [6 -7  2 0; ...<\/span>\r\n           0  2 -1 0; ...<\/span>\r\n           0 -1  2 0; ...<\/span>\r\n           0  2 -7 6];\r\n\r\npxnew = Mtofrom * px * Mtofrom';\r\npynew = Mtofrom * py * Mtofrom';\r\npznew = Mtofrom * pz * Mtofrom';\r\n<\/pre>
If we compare the control points before and after this transformation, we can see that the ones for the B-spline patch extand way outside the ones for the Bézier patch, and the Z range is much wider.<\/p>
f2 = figure;\r\np1 = stem3(px,py,pz,'filled'<\/span>);\r\nhold on<\/span>\r\np2 = stem3(pxnew,pynew,pznew,'filled'<\/span>);\r\nsurf(pxnew,pynew,pznew,'FaceColor'<\/span>,'none'<\/span>,'EdgeColor'<\/span>,[.85 .85 .85])\r\nxlim([-inf inf])\r\nylim([-inf inf])\r\n<\/pre>\"\" 
But when we use these new points with the basis matrix for the B-spline patch, they will give us the same surface we got with the Bézier patch using the original control points.<\/p>
delete(f2)\r\ns.XData = v_powers * M * pxnew * M' * u_powers;\r\ns.YData = v_powers * M * pynew * M' * u_powers;\r\ns.ZData = v_powers * M * pznew * M' * u_powers;\r\n<\/pre>\"\" 
Being able to convert between different patch types is extremely useful because the different types have different properties which are useful in different situations.<\/p>
You can find all of the to-from matrices in this file<\/a>.<\/p>
But there are more goodies hiding in this memo. We saw when we talked about parametric curves<\/a> that being able to compute partial derivatives of the curves is very useful for creating tangents and normals. The same is true when you're working with surface patches, and this memo has a section on how to compute partial derivatives of the patches. To compute those, we need the following two matrices.<\/p>
du = [0 3 0 0; ...<\/span>\r\n      0 0 2 0; ...<\/span>\r\n      0 0 0 1; ...<\/span>\r\n      0 0 0 0];\r\n\r\ndv = [0 0 0 0; ...<\/span>\r\n      3 0 0 0; ...<\/span>\r\n      0 2 0 0; ...<\/span>\r\n      0 0 1 0];\r\n<\/pre>
We'll create a low-res parameterization.<\/p>
M = Mbezier;\r\nu = linspace(0,1,10);\r\nv = linspace(0,1,10)';\r\nu_powers = [u.^3; u.^2; u; ones(size(u))];\r\nv_powers = [v.^3, v.^2, v, ones(size(v))];\r\n\r\nxout = v_powers * M * px * M' * u_powers;\r\nyout = v_powers * M * py * M' * u_powers;\r\nzout = v_powers * M * pz * M' * u_powers;\r\n<\/pre>
And then we use the matrices du and dv like this:<\/p>
dxdu = v_powers * M * px * M' * du * u_powers;\r\ndydu = v_powers * M * py * M' * du * u_powers;\r\ndzdu = v_powers * M * pz * M' * du * u_powers;\r\ndxdv = v_powers * dv * M * px * M' * u_powers;\r\ndydv = v_powers * dv * M * py * M' * u_powers;\r\ndzdv = v_powers * dv * M * pz * M' * u_powers;\r\n<\/pre>
We could use the cross product of those two vectors to compute normals which are much smoother than what the surface command can create. Or we can use them directly to cover the surface with a bunch of tangent circles like this:<\/p>
xlim manual<\/span>\r\nylim manual<\/span>\r\nzlim manual<\/span>\r\ndelete(s)\r\nradius = .05;\r\ntheta = linspace(0,2*pi,72); % points around the circles<\/span>\r\nfor<\/span> i=1:numel(xout)\r\n    % c + r*(cos(theta)*dp\/du + sin(theta)*dp\/dv)<\/span>\r\n    cx = xout(i) + radius*(cos(theta)*dxdu(i) + sin(theta)*dxdv(i));\r\n    cy = yout(i) + radius*(cos(theta)*dydu(i) + sin(theta)*dydv(i));\r\n    cz = zout(i) + radius*(cos(theta)*dzdu(i) + sin(theta)*dzdv(i));\r\n    h = patch(cx,cy,cz,zeros(size(cx)));\r\n    h.FaceColor = [.875 .875 .875];\r\n    h.EdgeColor = 'none'<\/span>;\r\nend<\/span>\r\n<\/pre>\"\" 
Can you combine this with what we did in the teapot blog post<\/a> to create a picture that looks like this?<\/p>
\"\" <\/p>