Mesh Simplification

$\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 explore the simplication of a highly detailed mesh into a coarser one.

In [2]:

Random Edge Contraction

Simplest way to perform mesh simplification is through edge collapse. Each step replaces two vertex joined by an edge by a single vertex, and removes the edge.

Load a model.

In [3]:
name = 'venus'; = name;
[vertex,faces] = read_mesh(name);
n = size(vertex,2);

Display full quality.

In [4]:
shading faceted;

Initialize the simplification.

In [5]:
faces1 = faces;
vertex1 = vertex;

Compute the collection of edges.

In [6]:
edges = compute_edges(faces1);
nedges = size(edges,2);

Select an edge. Here selection is done at random.

In [7]:
k = floor(rand*(nedges-1))+1;
e = edges(:,k);

Change the vertex location, and remove one of the two vertices.

In [8]:
vertex1(:,e(1)) = mean( vertex1(:,e),2 );
vertex1(:,e(2)) = Inf;

Change the face indexing.

In [9]:
faces1(faces1==e(2)) = e(1);
a = sum( diff(sort(faces1))==0 );
faces1(:,a>0) = [];

Exercise 1

Perform iterative collapse to reach |p = round(2*n/3)| vertices. isplay

In [10]:
In [11]:
%% Insert your code here.

Exercise 2

As a post processing, find a way to remove from |faces1| and |vertex1| the unecessary information (remove vertex and faces that are not used).

In [12]:
In [13]:
%% Insert your code here.

Error Driven Edge Contraction

To ameliorate the quality of the output mesh, it is necessary to order to select the edge to collapse according to some quality priority.

Exercise 3

Perform iterative collapse to reach |p = round(2*n/3)| vertices. Use an ordering of the edge by their length. isplay

In [14]: