# Mesh Deformation¶

$\newcommand{\dotp}[2]{\langle #1, #2 \rangle}$ $\newcommand{\enscond}[2]{\lbrace #1, #2 \rbrace}$ $\newcommand{\pd}[2]{ \frac{ \partial #1}{\partial #2} }$ $\newcommand{\umin}[1]{\underset{#1}{\min}\;}$ $\newcommand{\umax}[1]{\underset{#1}{\max}\;}$ $\newcommand{\umin}[1]{\underset{#1}{\min}\;}$ $\newcommand{\uargmin}[1]{\underset{#1}{argmin}\;}$ $\newcommand{\norm}[1]{\|#1\|}$ $\newcommand{\abs}[1]{\left|#1\right|}$ $\newcommand{\choice}[1]{ \left\{ \begin{array}{l} #1 \end{array} \right. }$ $\newcommand{\pa}[1]{\left(#1\right)}$ $\newcommand{\diag}[1]{{diag}\left( #1 \right)}$ $\newcommand{\qandq}{\quad\text{and}\quad}$ $\newcommand{\qwhereq}{\quad\text{where}\quad}$ $\newcommand{\qifq}{ \quad \text{if} \quad }$ $\newcommand{\qarrq}{ \quad \Longrightarrow \quad }$ $\newcommand{\ZZ}{\mathbb{Z}}$ $\newcommand{\CC}{\mathbb{C}}$ $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\EE}{\mathbb{E}}$ $\newcommand{\Zz}{\mathcal{Z}}$ $\newcommand{\Ww}{\mathcal{W}}$ $\newcommand{\Vv}{\mathcal{V}}$ $\newcommand{\Nn}{\mathcal{N}}$ $\newcommand{\NN}{\mathcal{N}}$ $\newcommand{\Hh}{\mathcal{H}}$ $\newcommand{\Bb}{\mathcal{B}}$ $\newcommand{\Ee}{\mathcal{E}}$ $\newcommand{\Cc}{\mathcal{C}}$ $\newcommand{\Gg}{\mathcal{G}}$ $\newcommand{\Ss}{\mathcal{S}}$ $\newcommand{\Pp}{\mathcal{P}}$ $\newcommand{\Ff}{\mathcal{F}}$ $\newcommand{\Xx}{\mathcal{X}}$ $\newcommand{\Mm}{\mathcal{M}}$ $\newcommand{\Ii}{\mathcal{I}}$ $\newcommand{\Dd}{\mathcal{D}}$ $\newcommand{\Ll}{\mathcal{L}}$ $\newcommand{\Tt}{\mathcal{T}}$ $\newcommand{\si}{\sigma}$ $\newcommand{\al}{\alpha}$ $\newcommand{\la}{\lambda}$ $\newcommand{\ga}{\gamma}$ $\newcommand{\Ga}{\Gamma}$ $\newcommand{\La}{\Lambda}$ $\newcommand{\si}{\sigma}$ $\newcommand{\Si}{\Sigma}$ $\newcommand{\be}{\beta}$ $\newcommand{\de}{\delta}$ $\newcommand{\De}{\Delta}$ $\newcommand{\phi}{\varphi}$ $\newcommand{\th}{\theta}$ $\newcommand{\om}{\omega}$ $\newcommand{\Om}{\Omega}$

This tour explores deformation of 2D mesh using Laplacian interpolation. The dense deformation field is obtained from a sparse set of displaced anchor point by computing harmonic interpolation.

In [2]:
addpath('toolbox_signal')


## Mesh Creation¶

We create a simple mesh with fine scale details.

We generate point on a square.

In [3]:
p = 150;
[Y,X] = meshgrid(linspace(-1,1,p),linspace(-1,1,p));
vertex0 = [X(:)'; Y(:)'; zeros(1,p^2)];
n = size(vertex0,2);


We generate a triangulation of a square.

In [4]:
I = reshape(1:p^2,p,p);
a = I(1:p-1,1:p-1); b = I(2:p,1:p-1); c = I(1:p-1,2:p);
d = I(2:p,1:p-1); e = I(2:p,2:p); f = I(1:p-1,2:p);
faces = cat(1, [a(:) b(:) c(:)], [d(:) e(:) f(:)])';


Width and height of the bumps.

In [5]:
sigma = .03;
h = .35;
q = 8;


Elevate the surface using bumps.

In [6]:
t = linspace(-1,1,q+2); t([1 length(t)]) = [];
vertex = vertex0;
for i=1:q
for j=1:q
d = (X(:)'-t(i)).^2 + (Y(:)'-t(j)).^2;
vertex(3,:) = vertex(3,:) + h * exp( -d/(2*sigma^2)  );
end
end


Display the surface.

In [7]:
clf;
plot_mesh(vertex,faces);
view(3);


Compute its geometric (cotan) Laplacian

In [8]:
W = sparse(n,n);
for i=1:3
i1 = mod(i-1,3)+1;
i2 = mod(i  ,3)+1;
i3 = mod(i+1,3)+1;
pp = vertex(:,faces(i2,:)) - vertex(:,faces(i1,:));
qq = vertex(:,faces(i3,:)) - vertex(:,faces(i1,:));
% normalize the vectors
pp = pp ./ repmat( sqrt(sum(pp.^2,1)), [3 1] );
qq = qq ./ repmat( sqrt(sum(qq.^2,1)), [3 1] );
% compute angles
ang = acos(sum(pp.*qq,1));
u = cot(ang);
u = clamp(u, 0.01,100);
W = W + sparse(faces(i2,:),faces(i3,:),u,n,n);
W = W + sparse(faces(i3,:),faces(i2,:),u,n,n);
end


Compute the symmetric Laplacian matrix.

In [9]:
d = full( sum(W,1) );
D = spdiags(d(:), 0, n,n);
L = D - W;


## Boundary Modification¶

We modify the domain by modifying its boundary.

Select boundary indexes.

In [10]:
I = find( abs(X(:))==1 | abs(Y(:))==1 );


Compute the deformation field (zeros outsize the handle, proportional to the normal otherwise).

In [11]:
Delta0 = zeros(3,n);
d = ( vertex(1,I) + vertex(2,I) ) / 2;
Delta0(3,I) = sign(d) .* abs(d).^3;


Modify the Laplacian to take into account the fixed handles.

In [12]:
L1 = L;
L1(I,:) = 0;
L1(I + (I-1)*n) = 1;


Compute the full deformation by solving for Laplacian=0 on each coordinate.

In [13]:
Delta = ( L1 \ Delta0' )';


Compute the deformed mesh.

In [14]:
vertex1 = vertex+Delta;


Display it.

In [15]:
clf;
plot_mesh(vertex1,faces);
view(-100,15);


Exercise 1

Perform a more complicated deformation of the boundary. eform isplay it.

In [16]:
exo1()

In [17]:
%% Insert your code here.


Exercise 2

Move both the inside and the boundary.

aplacian eform isplay it.

In [18]:
exo2()

In [19]:
%% Insert your code here.


Exercise 3

Apply the mesh deformation method to a real mesh, with both large scale and fine scale details.

In [20]:
exo3()

In [21]:
%% Insert your code here.


## Non-linear Deformation¶

Linear methods give poor results for large deformation.

It is possible to obtain better result by applying the linear deformation only to a low pass version of the mesh (coarse scale modifications). The remaining details are then added in the direction of the normal, in a local frame that is rotated to match the deformation of the coarse surface.

Exercise 4

Apply the deformation to the coarse mesh |vertex0| to obtain |vertex1|. Important: you need to compute and use the cotan Laplacian of the coarse mesh, not of the original mesh! ompute laplacian

aplacian eform isplay it.

In [22]:
exo4()

In [23]:
%% Insert your code here.


Compute the residual vector contribution along the normal (which is vertical).

In [24]:
normal = compute_normal(vertex0,faces);
d = repmat( sum(normal .* (vertex-vertex0)), [3 1]);


Exercise 5

Add the normal contribution |d.*normal| to |vertex1|, but after replacing the normal of |vertex0| by the normal of |vertex1|. isplay it.

In [25]:
exo5()