📄 tp4.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=iso-8859-1"><link rel=File-List href="index_files/filelist.xml"><title>Lecture 4 - Mesh Processing</title><link href="styles.css" rel="stylesheet" type="text/css"></head><body bgcolor="#FFFFFF" lang=FR><div > <h1>Lecture 4 - Mesh Processing</h1></div><blockquote> <blockquote> <blockquote> <blockquote> <blockquote> <p align="justify"><strong>Abstract : </strong>The goal of this lecture is to manipulate a 3D mesh. This includes the loading and display of a 3D mesh and then the processing of the mesh. This processing is based on computations involving various kinds of Laplacians. These Laplacians are extensions of the classical second order derivatives to 3D meshes. They can be used to perform heat diffusion (smoothing), compression and parameterization of the mesh.</p> </blockquote> </blockquote> </blockquote> </blockquote></blockquote><h2> Setting up Matlab. </h2><ul> <li>First download the Matlab toolbox <a href="matlab/toolbox_graph.zip"><font face="Courier New, Courier, mono">toolbox_graph.zip</font></a>. Unzip it into your working directory. You should have a directory <font face="Courier New, Courier, mono">toolbox_graph</font>/ in your path. Download also the set of additional meshes in .off format: <a href="matlab/meshes.zip">meshes.zip</a> and unzip this file into your directory.</li> <li>The first thing to do is to install this toolbox in your path.</li> <blockquote> <p><font face="Courier New, Courier, mono">path(path, 'toolbox_graph/');<br> path(path, 'toolbox_graph/off/');<br> path(path, 'toolbox_graph/toolbox/');<br> path(path, 'meshes/'); </font></p> </blockquote> <li>Recompile the mex file for your machine (this can produce some warning). If it does not work, either use the already compiled mex file (they should be available in <font face="Courier New, Courier, mono">toolbox_graph/</font> for MacOs and Unix) or try to set up matlab with a C compiler (e.g. gcc) using '<font face="Courier New, Courier, mono">mex -setup</font>'. </li> <blockquote> <p><font face="Courier New, Courier, mono">cd toolbox_graph<br> compile_mex;<br> cd ..</font></p> </blockquote></ul> <h2> Mesh Loading and Displaying. </h2> <ul> <li>You can load a mesh from a file and display it. Remember that a mesh is given by two matrix: <font face="Courier New, Courier, mono">vertex</font> store the 3D vertex positions and <font face="Courier New, Courier, mono">face</font> store 3-tuples giving the number of the vertices forming faces.</li> <blockquote> <p><font face="Courier New, Courier, mono">name = 'mushroom'; % other possibilities include 'venus'<br> %load from file<br> [vertex,face] = read_mesh([name '.off']);<br> % display the mesh<br> clf;<br> plot_mesh(vertex,face);<br> % remove the display of the triangle<br> shading interp; camlight; </font></p> </blockquote> <table width = "0" border="0" cellspacing="0" cellpadding="0" align="center"> <tr align="center"> <td> <img src="images/tp3/venus-mesh-display.jpg" height="300"/> <img src="images/tp3/mushroom-mesh-display.jpg" height="300"/> </td> </tr> <tr> <td align="center">Two examples of rendered triangle meshes.</td> </tr> </table> <li>A mesh can also be built by starting from a coarse triangulation and then subdividing it.</li> <blockquote> <p><font face="Courier New, Courier, mono">name = 'sphere'; % another choice could be 'L1'<br> j = 2; % number of subdivision levels<br> [vertex,face] = gen_base_mesh(name, 0); % the initial mesh<br> [vertex,face] = gen_base_mesh(name, j);<br> clf;<br> plot_mesh(vertex,face);</font></p> </blockquote> <table width = "1000" border="0" cellspacing="0" cellpadding="0" align="center"> <tr align="center"> <td> <img src="images/tp3/sphere-subd-0.jpg" height="200"/> <img src="images/tp3/sphere-subd-1.jpg" height="200"/> <img src="images/tp3/sphere-subd-2.jpg" height="200"/> <img src="images/tp3/sphere-subd-3.jpg" height="200"/><br/> <img src="images/tp3/L1-subd-0.jpg" height="200"/> <img src="images/tp3/L1-subd-1.jpg" height="200"/> <img src="images/tp3/L1-subd-2.jpg" height="200"/> <img src="images/tp3/L1-subd-3.jpg" height="200"/> </td> </tr> <tr> <td align="center">Two example of meshes computed by regular subdivision.</td> </tr> </table></ul><h2> Heat Diffusion on 3D Meshes. </h2><ul> <li>A Laplacian on a 3D mesh is a (n,n) matrix L, where n is the number of vertices, that generalize the classical laplacian of image processing to a 3D mesh. There are several forms of laplacian depending whether it is symmetric (L'=L) and normalized (1 on the diagonal) :<br> <table width="70%" align="center" border="0"> <tr> <td width="10%"> </td> <td>L0 = D + W </td> <td><em>(symmetric, normalized)</em></td> </tr> <tr> <td> </td> <td>L1 = D^{-1}*L0 = Id + D^{-1}*W</td> <td><em> (non-symmetric, non-normalized)</em></td> </tr> <tr> <td> </td> <td>L2 = D^{-1/2}*L0*D^{-1/2} = Id + D^{-1/2}*W*D^{-1/2}<em> </em></td> <td><em>(symmetric, normalized)</em></td> </tr> </table> Where W is a weight matrix, W(i,j)=0 if (i,j) is not an edge of the graph. There are several kinds of such weights<br> <table width="70%" align="center" border="0"> <tr> <td width="10%"> </td> <td>W(i,j)=1</td> <td><em>(combinatorial)</em></td> </tr> <tr> <td> </td> <td>W(i,j)=1/|vi-vj|^2</td> <td><em>(distance)</em></td> </tr> <tr> <td> </td> <td>W(i,j)=cot(alpha_ij)+cot(beta_ij)<em> </em></td> <td><em>(harmonic)</em></td> </tr> </table> where {vi}_i are the vertex of the mesh, i.e. vi=vertex(:,i), and (alpha_ij,beta_ij) is the pair of adjacent angles to the edge (vi,vj). A gradient matrix G associated to the laplacian L is an (m,n) matrix where m is the number of edges in the mesh, that satisfies L=G'*G. It can be computed as G((i,j),k)=+sqrt(W(i,j)) if k=j and G((i,j),k)=-sqrt(W(i,j)) if k=i, and G((i,j),k)=0 otherwise.</li> <li>In the following, you can compute gradient, weights and laplacian using the compute_mesh_xxx functions.<br> </li> <blockquote> <p><font face="Courier New, Courier, mono">% kind of laplacian, can be 'combinatorial', 'distance' or 'conformal' (slow)<br> laplacian_type = ...;<br> % load two different kind of laplacian and check the gradient factorization<br> options.symmetrize = 1;<br> options.normalize = 0;<br> L0 = compute_mesh_laplacian(vertex,face,laplacian_type,options);<br> G0 = compute_mesh_gradient(vertex,face,laplacian_type,options);<br> disp(['Error (should be 0): ' num2str(norm(L0-G0'*G0, 'fro')) '.']);<br> options.normalize = 1;<br> L1 = compute_mesh_laplacian(vertex,face,laplacian_type,options);<br> G1 = compute_mesh_gradient(vertex,face,laplacian_type,options);<br> disp(['Error (should be 0): ' num2str(norm(L1-G1'*G1, 'fro')) '.']);<br> % these matrices are stored as sparse matrix<br> spy(L0); </font></p> </blockquote> <li>In order to smooth a vector f of size n (i.e. a function defined on each vertex of the mesh), one can perform a heat diffusion by solving the following PDE<br> d F / dt = -L*f with F(x,t=0)=f <br> until some stopping time t.<br> When this diffusion is applied to each component of the positions of the vertices f=vertex(i,:), this smoothes the 3D mesh. Implement this PDE using an explicit discretization in time.<br> </li> <blockquote> <p><font face="Courier New, Courier, mono">% the time step should be small enough<br> dt = 0.1;<br> % stopping time<br> Tmax = 10;<br> % number of steps<br> niter = round(Tmax/dt);<br> % initialize the 3 vectors at time t=0<br> vertex1 = vertex;<br> % solve the diffusion<br> for i=1:niter<br> % update the position by solving the PDE<br> vertex1 = vertex1 + ...;<br> end </font></p> </blockquote> <table width="900" border="0" cellspacing="0" cellpadding="0" align="center"> <tr align="center"> <td> <img src="images/tp3/smoothing-elephant.png" width="800"/> <img src="images/tp3/smoothing-bunny.png" width="800"/> <img src="images/tp3/smoothing-skull.png" width="800"/> </td> </tr> <tr> <td align="center">Heat diffusion on a 3D mesh, at times t=0, t=10, t=40, ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -