ARAP Revisited

Discretizing the Elastic Energy
using Intrinsic Voronoi Cells

Ugo Finnendahl, Matthias Schwartz, Marc Alexa


As the title suggests, let's revisit ARAP. ARAP stands for "as-rigid-as-possible" and is a family of energies that measure how locally rigid a transformation is.

ARAP Revisited


There are a ton of applications possible, one was yesterday presented by Theodore Kim. But in this presentation we will focus on shape deformation, where you have an input mesh, here on the left,

and we constrain a subset of vertices, on the right, colored in orange
And optimizing the ARAP energy results in the rest of the mesh deforming, as rigidly as possible.

The optimization can be done using a local/global scheme, or also called block coordinate descent.
This is fast enough for interactive modeling.

ARAP Revisited

$$\f\colon S\subset\R^3\to\R^3$$

$$E(\f) = \htmlData{fragment-index=2}{\frac{1}{2}\int_{S}} \htmlData{fragment-index=5}{\min_{R\in\text{SO(3)}}} \htmlData{fragment-index=5}{\lVert J_\f - R \rVert^2} \htmlData{fragment-index=2}{dS}$$ $$E(\f,R) = \frac{1}{2}\int_{S} \lVert J_\f - R \rVert^2 dS$$

$\min E(\f)$ $\text{s.t. } \f(\mathbf{x}) = \htmlStyle{color: orange;}{\mathbf{b}_{\mathbf{x}}}$
$\forall \mathbf{x}\in \text{constrained set}$ $\min E(\f,R)$ $\text{s.t. } \f(\mathbf{x}) = \htmlStyle{color: orange;}{\mathbb{b}_{\mathbf{x}}}$
$\forall \mathbf{x}\in \text{constrained set}$

$$\f$$ $$S$$ $$\tilde{S}$$


Let me now focus on how the energy is defined.

We start with a smooth input surface, here denote as S.
This surface gets mapped to the resulting surface S tilde by a function f.
Note that the surface is immersed in 3D. So we map from a subset of R3 to R3.

The as-rigid-as-possible energy is then defined

as the integral over the whole surface,

where at each point we measure how much the deformation f differs from a rigid transformation.

This is typically done by measuring the distance of the Jacobian of f to the optimal rotation R with respect to some norm,
usually in the Frobenius norm of the matrices representing the transformations.

So ARAP than searches for a function f that minimizes the energy with respect to some boundary conditions, again colored in orange.

And as we minimize the energy we can get rid of the second *inner* minimization by making R an input parameter.
So now we are *not* only search for an optimal f but also for the rotations R.

Ok, this is a continuous energy over a smooth surface. But in geometry processing we usually operate on meshes.
So how to discretize this energy?
*This is what this presentation is mainly focusing on. We will derive different discretizations of this smooth energy.*

Discretizing ARAP

$$\f\colon S\subset\R^3\to\R^3$$ $$\f\colon M\subset\R^3\to\R^3$$

$$\frac{1}{2}\int_{S} \lVert J_\f - R \rVert^2 dS \phantom{ = \frac{1}{2}\sum_{t\in T}\int_{M} \lVert J_\f - R \rVert^2 dM}$$

$$\frac{1}{2}\int_{M} \lVert J_\f - R \rVert^2 dM \htmlData{fragment-index=3}{ = \frac{1}{2}\sum_{t\in T}\int_{t} \lVert J_\f - R \rVert^2 dt}$$

$$\htmlData{fragment-index=14}{E(\f,R)}\htmlData{fragment-index=4}{\overset{\htmlData{fragment-index=14,class=fade-out}{\text{[PP93]}}}{=}} \htmlData{fragment-index=5}{\frac{1}{4}\sum_{t\in T}\sum_{\e_{ij}\in t} \cot(\htmlStyle{color: #0089b6}{\alpha}) \lVert \f(\htmlStyle{color: #298d00}{\e_{ij}}) - R_t(\htmlStyle{color: #298d00}{\e_{ij}}) \rVert^2}$$

$$\min E(\f)$$ $\text{s.t. } \f(\v_i) = \htmlStyle{color: orange;}{b_i},$
$\forall \v_i\in \text{constrained vertices}$

$$\f$$ $$M=(V,T)$$ $$\hat{M}=(\hat{V},T)$$ $$R_t$$

$$\f$$ $$S$$ $$\tilde{S}$$


Now, what changes in the discrete setting?

Instead of a smooth surface, we have a mesh consisting of vertex positions and triangles that get mapped by f to different vertex positions
while still retaining the same connection between vertices.
And the idea is that we assume that this mesh describes a piecewise linear surface.

So f affinely maps each triangle to the corresponding triangle.
So we can represent f such that it only operates on vertices...
One should aware, that this surface is not smooth at vertices and along edges and therefore the jacobian is not defined there.

But we can still integrate over the whole area, as *edges* are *zero sets*, and therefore we can calculate the energy triangle wise.
So we have to sum over the integral, per triangle.

And if we assume the rotation is constant for each triangle,

we can even write this energy as a *weighted sum* of the three edges of each triangle.

For each edge, we have to multiply the cotan of the angle with the length of the image of the opposite edge, minus the rotated edge.
The exact formula is not important at the moment, but keep in mind that we sum over the
ne that was unkown to me,
these

three

(angle, edge) pairs colored in blue and green.

So to complete this disretization

we also have to consider the constrains. These are simply defined for the vertices now.

ARAP Overview

Continuous

Discrete

Properties

$$E(\f,R) = \int_S \lVert J_\f - R \rVert^2 dS$$

constant $R_t$ over
each triangle

Face ARAP [LZXGG08]

$$\frac{1}{4}\sum_{t\in T}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_t(\e_{ij}) \rVert^2$$

no bending
penalty

$$R_1$$ $$R_2$$


Perfekt. So to conclude:

if we assume a picewise affine function f and constant rotations R_t over each triangle,

we end up with our first discrete version of the energy, commonly called Face ARAP.

But as I said we have ignored the singularities at the edges and vertices.
The consequence is that we did not penalize any bending across the edges.
So this example transformation has 0 energy as we only rotate one triangle

For that reason this discrete energy is usually not used for interactive deformation of 3D surfaces but rather combined with other energies to incorporate bending or other objectives.
But we can adopt the energy to incorporate bending.

Different Regions (1)

Face wise

$$E(\f,\{R_t\})=\frac{1}{4}\sum_{t\in T}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_t(\e_{ij}) \rVert^2$$

$$E(\f,\{\htmlClass{blue-highlight}{R_t}\})=\frac{1}{4}\htmlClass{blue-highlight}{\sum_{t\in T}}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - \htmlClass{blue-highlight}{R_t}(\e_{ij}) \rVert^2$$

$$E(\f,\{R_t\})=\frac{1}{4}\sum_{t\in T}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_t(\e_{ij}) \rVert^2$$

$$R_0$$ $$R_1$$ $$R_2$$ $$R_3$$ $$R_4$$ $$R_5$$ $$R_6$$ $$R_7$$ $$R_8$$ $$R_9$$

Vertex star wise

$$E(\f,\{R_{\v}\})=\frac{1}{4}\sum_{\v\in V}\sum_{t\in N(\v)}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

$$E(\f,\{\htmlClass{blue-highlight}{R_{\v}}\})=\frac{1}{4}\htmlClass{blue-highlight}{\sum_{\v\in V}}\sum_{t\in N(\v)}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - \htmlClass{blue-highlight}{R_{\v}}(\e_{ij}) \rVert^2$$

$$E(\f,\{R_{\v}\})=\frac{1}{4}\sum_{\v\in V}\sum_{t\in N(\v)}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

$$E(\f,\{R_{\v}\})=\frac{1}{4}\sum_{\v\in V}\sum_{t\in N(\v)}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\frac{1}{2}\e_{ij}) - R_{\v}(\frac{1}{2}\e_{ij}) \rVert^2$$

$$E(\f,\{R_{\v}\})=\frac{1}{4}\sum_{\v\in V}\sum_{t\in N(\v)}\sum_{\e_{ij}\in t} \cot(\alpha) \frac{1}{4} \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

$$E(\f,\{R_{\v}\})=\frac{1}{16}\sum_{\v\in V}\sum_{t\in N(\v)}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

$$R_1$$ $$R_2$$ $$R_3$$


In the last discretization we assumed that the rotations are defined per triangle.

If we instead assume a constant rotation per vertex star, we can still use the same discretization,

but instead of optimizing for rotations per triangle, we optimize the rotations per vertex.
This means we now sum over each vertex neighborhood.

But if we really would consider the vertex star for each vertex, then these regions overlap.
This means points within a triangle are considered multiple times but with different rotations.
This makes no sense. But we can remedy this problem

by scaling the regions associated to a vertex by a factor of 1/2.
This means we scale all edges by the same factor, while the angles stay the same.
And as f is affine and R linear we can pull this factor out.

So scaling the edges has no influence on the minimum.
But note that the resulting energy is not really an integral over the whole surface, as we do not cover the white triangle in the middle.
This may be odd, but we'll accept that.

ARAP Overview

Continuous

Discrete

Properties

$$E(\f,R) = \int_S \lVert J_\f - R \rVert^2 dS$$

constant $R_t$ over
each triangle

Face ARAP [LZXGG08]

$$\frac{1}{4}\sum_{t\in T}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_t(\e_{ij}) \rVert^2$$

no bending
penalty

constant $R_{\v}$ over
each vertex star

Spokes-and-rims ARAP [CPSS10]

$$\frac{1}{16}\sum_{\v\in V}\sum_{t\in N(\v)}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$


So

by assuming constant rotations over different areas we arrive at a different energy.

Because we sum over all edges of the vertex star and vertex link, it is usually called spokes-and-rims ARAP. So the spokes are the incident edges and the rim is the vertex link.
Because rotations are considered per vertex start, the energy increases when the surface is bent.

Result


and we can use it to model mesh deformations.
As we can see here.

For organic shapes like the armadillo this produces good results.

But unfortunately the energy has some problems.
For example, if we take a regular quad mesh and consistently triangulate the quads,
the deformation exhibits some twisting.
So, although the surface and the constrains are symmetric, because we only moved them from here to here, the output is not.
This is undesirable.

And this becomes even clearer for this cube.
We again have symmetric constrains, but the result is very asymmetric.

ARAP Overview

Continuous

Discrete

Properties

$$E(\f,R) = \int_S \lVert J_\f - R \rVert^2 dS$$

constant $R_t$ over
each triangle

Face ARAP [LZXGG08]

$$\frac{1}{4}\sum_{t\in T}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_t(\e_{ij}) \rVert^2$$

no bending
penalty

constant $R_{\v}$ over
each vertex star

Spokes-and-rims ARAP [CPSS10]

$$\frac{1}{16}\sum_{\v\in V}\sum_{t\in N(\v)}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

(asymmetries)


So we may have unwanted asymmetries.

And it should be clear where these asymmetries come from.

Different Regions (2)

Constant $R$ per vertex star

Constant $R$ per Voronoi cell


The input is really a regular quad mesh, and we have to decide, which of the two possible diagonals are part of the triangulation.
If they are all aligned like here,

the parts of the surface that are associated to a vertex are all tilted in the same direction.
This is what leads to the asymmetries.

A better local region associated to vertices would be the Voronoi cell.
As this area is independent of the choosen diagonals.

And the Voronoi cells cover the whole surface.

Orthogonal dual

Constant $R$ per Voronoi cell

Constant $R$ per orthogonal dual cell

Assumption: Delaunay mesh


Ok so lets discretize our energy over the Voronoi cell. How is that area defined?

If we assume that our mesh is Delaunay. The Voronoi cell coincide with the orthogonal dual.

The orthogonal dual is defined as the polygon of all the circumcenters of the neighboring triangles.

Now we want to integrate over this well defined area.
And as we know how to integrate the continuous energy over a sum of triangles, we triangulate the polygon, by connecting each circumcenter with the center vertex.

But note that a circumcenter might be outside of the original triangle.
And therefore our Voronoi triangles might span over multiple neighbouring triangles.
This is especially tricky in our embedded case in 3D. Where these triangles would get folded.

Discretization

Non-conforming Crouzeix-Raviart basis
for finite element method

Input

Output

Energy over a triangle:

$$\frac{1}{4}\sum_{\e_{ij}\in t} \cot(\htmlStyle{color: #0089b6}{\alpha}) \lVert \f(\htmlStyle{color: #298d00}{\e_{ij}}) - R_t(\htmlStyle{color: #298d00}{\e_{ij}}) \rVert^2$$

$$\frac{1}{4}\sum_{\v\in V}\sum_{\e_{ij}\in N(\v)} \cot(\alpha) \lVert \f(\frac{1}{2}\e_{ij}) - R_{\v}(\frac{1}{2}\e_{ij}) \rVert^2$$

$$\frac{1}{16}\sum_{\v\in V}\sum_{\e_{ij}\in N(\v)} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

$$\f$$ circumcenters

Assumption: Delaunay mesh


So we will do a trick that avoids considering these cases completely..
The trick is to allow f to be discontinuous.
This sounds weird but please bear with me.
....So we say that

vertices get mapped to vertices

edges get mapped to the linear interpolation of the corresponding vertices. So the resulting mesh stays the same.

And additionally we say that all those small triangles we just created by the triangulation of the othorgonal dual need to be continuous,
but nothing more.

This results in a discontinuous function f where the red circumcenters can get mapped potentially to six different positions.

And although this looks weird non-conforming functions are not unusual. For example, Krusä-Raviar basis function for finite elements have been applied in geometry processing as well. They effectively

result in discontinuous functions that only agree on edge midpoints.

But that is not important here.

So back to our discontinous function.
We still have to integrate our energy over the orthogonal dual, here again in colored in green.

Remember that the energy over a triangle was defined as the sum over

these

three

(edge, angle) pairs.

We first see, that this angle, as the name othorgonal dual suggests, is always 90 degrees, resulting in a cotan of 0.

So we can ignore this edge.

And for this edge, as f minimizis this sum and we have the position of the circumcenter as a independent degree of freedom, we can position the circumcenter in a way, that the differences of the mapped edges vanish as well.

Leaving us with only this edge angle pair.

Interesstingly this inscribed blue angle is the same angle as the corner angle of big triangle by the inscribed angle theorem.

So the resulting energy is very similar to the spokes-and rims-version. But instead of considering all spokes and rim edges, we only consider these five spoke edges.
To be precise actually just half of the edge, but

we can again pull the factor to the front and end up with our third discretization of the smooth energy.

ARAP Overview

Continuous

Discrete

Properties

$$E(\f,R) = \int_S \lVert J_\f - R \rVert^2 dS$$

constant $R_t$ over
each triangle

Face ARAP [LZXGG08]

$$\frac{1}{4}\sum_{t\in T}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_t(\e_{ij}) \rVert^2$$

no bending
penalty

constant $R_{\v}$ over
each vertex star

Spokes-and-rims ARAP [CPSS10]

$$\frac{1}{16}\sum_{\v\in V}\sum_{t\in N(\v)}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

triangulation
dependent
(asymmetries)

constant $R_{\v}$ over
each orthogonal dual
and $\f$ is discontinous

Orginal ARAP [SA07]

$$\frac{1}{16}\sum_{\v\in V}\sum_{\e_{ij}\in N(\v)} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

Assumption: Delaunay mesh


This time

we have a constant rotation per orthogonal dual and allow f to be discontinuous.

And we actually end up with the original ARAP formulation of Sorkine-Hornung and Alexa. So we found a derivation for their initially only discretely defined energy.

Result

Assumption: Delaunay mesh


And the results are indeed symmetrical.

Here the spike mesh for example.
So it seems that the original ARAP formulation is an improvement over the Spokes-and-rims version.
But what happens if the mesh is not Delaunay?

Non Delaunay meshes

Constant $R$ per orthogonal dual cell

Assumption: Delaunay mesh


So let's get rid of this assumption.

And see that if we have a non delaunay mesh, like for example if i pull this vertex to the left. We see that the othorgonal dual differs from the voronoi cell as we get a triangle with negative area, resulting in negative cotan weights as both angles are over 90 degrees. This leads to weird results.

Artifacts and divergence


For example in this bunny mesh we do not constrain the vertices to a different position. Therefore choosing f to be the identity leads to 0 energy.

But the vertices still move. Because the energy can become negative here, due to the negative cotan weights.

And sometimes this energy even completely diverges for example in this stool mesh.

ARAP Overview

Continuous

Discrete

Properties

$$E(\f,R) = \int_S \lVert J_\f - R \rVert^2 dS$$

constant $R_t$ over
each triangle

Face ARAP [LZXGG08]

$$\frac{1}{4}\sum_{t\in T}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_t(\e_{ij}) \rVert^2$$

no bending
penalty

constant $R_{\v}$ over
each vertex star

Spokes-and-rims ARAP [CPSS10]

$$\frac{1}{16}\sum_{\v\in V}\sum_{t\in N(\v)}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

triangulation
dependent
(asymmetries)

constant $R_{\v}$ over
each orthogonal dual
and $\f$ is discontinous

Orginal ARAP [SA07]

$$\frac{1}{16}\sum_{\v\in V}\sum_{\e_{ij}\in N(\v)} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

may diverge
if not Delaunay


So the original ARAP energy may diverge if the mesh is not Delaunay.

And this is the current state. The spokes-and-rims version and the original version have advantages and disadvantages and therefore both are implemented in libraries like libigl and cgal.
In our work we try to fix this and get the best of both worlds.

Orthogonal dual $\neq$ Voronoi cell

Constant $R$ per orthogonal dual cell

Constant $R$ per Voronoi cell

Constant $R$ per orthogonal dual cell of Delauany triangulation


To do so, we need to get rid of the negative area.

As initially planned assume constant rotations per Voronoi cell and not the orthogonal dual.
As the Voronoi cell is the orthogonal dual of the Delaunay triangulation,

we could simply work with the Delaunay triangulation, by flipping non Delaunay edges. Here colored in blue.

Intrinsic Delaunay triangulation


This can also be done on the piecewise linear surface, and is called the intrinsic Delaunay triangulation. Non Delaunay edges, like the one in the front,

get flipped, such that the

the orthogonal dual*s* of the intrinsic Delaunay triangulation are the intrinsic Voronoi cells.
Note that the resulting intrinsic edges are polylines over the surface.
So they might change direction extrinsically.
They kind of bend over the surface.
But intrinsically they are still straight.

Intrinsic ARAP

Original ARAP

$$\frac{1}{16}\sum_{\v\in V}\sum_{\e_{ij}\in N(\v)} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

$$\frac{1}{16}\sum_{\v\in V}\sum_{\htmlClass{blue-highlight}{\e_{ij}\in N(\v)}} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

$$\frac{1}{16}\sum_{\v\in V}\sum_{\htmlClass{blue-highlight}{\e_{ij}\in N(\v)}} \cot(\htmlClass{green-highlight}{\alpha}) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

$$\frac{1}{16}\sum_{\v\in V}\sum_{\htmlClass{blue-highlight}{\e_{ij}\in N(\v)}} \cot(\htmlClass{green-highlight}{\alpha}) \htmlClass{red-highlight}{\lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2}$$

$$\v_i$$ $$\v_k$$ $$\v_j$$

We need to "externalize" intrinsic edges:

$$ \begin{align*} \htmlData{fragment-index=40}{s_{ik}^t} &\htmlData{fragment-index=40}{=} \htmlData{fragment-index=35}{((1-a)\v_m+a\v_n)}\htmlData{fragment-index=40}{-(b\v_o+(1-b)\v_p)}\\ &\htmlData{fragment-index=45}{= Vb_{ik}^t} \end{align*}$$ $\f(s_{ik}^t) = \f(V)b_{ik}^t$

Intrinsic ARAP

$$\frac{1}{16}\sum_{\v\in V}\htmlData{fragment-index=20}{\sum_{\htmlClass{blue-highlight}{\e_{ik}\in N_i(\v)}}} \htmlData{fragment-index=25}{\cot(\htmlClass{green-highlight}{\alpha})}\htmlData{fragment-index=55}{\sum_{\s_{ik}^t\in \e_{ik}}} \htmlData{fragment-index=60}{\htmlClass{opaque}{\sigma_{ik}^t}} \htmlData{fragment-index=55}{\htmlClass{red-highlight}{\lVert \f(\s_{ik}^t) - R_{\v}(\s_{ik}^t) \rVert^2}}$$

$$s_{ik}^1$$ $$s_{ik}^2$$ $$\v_i$$ $$\v_k$$ $$\v_n$$ $$\v_m$$

So the idea is to reformulate the orginal ARAP energy using the intrinsic Delaunay triangulation instead of the extrinsic triangulation.

We can still sum over all vertices.

But now instead of summing over all extrinsic neighbors we just sum over all intrinsic neighbors.

The cotan weight can also be copied and we have to consider the intrinsic angle not the extrinsic angle.

But now it becomes tricky. Because we have extrinsic quantities measured here. The image of the edge and the rotated edge are extrinsically defined.

Sure, we could take the extrinsic connection between the intrinsic neighbors, but that is the same as simply remeshing the input, which is not what we want, because it would generate a different geometry.

What we rather want to do is to "externalize" the intrinsic edges.
Let's take a look at the polyline describing an intrinsic edge.

It can be divided into linear segments.
These segments start and end on either an extrinsic edge or vertex.

We can represent every endpoints as a convex combination of these two vertices.
And as a segment is just the difference between two endpoints, we can represent these segments as a linear combination of the initial vertices.

If we write the vertices columnwise this is a simple matrix vector product.

And as we still assume that f maps extrinsic edges to the linear interpolation of their mapped vertices, we also say that the mapped segments retain the same linear combination, after applying f.

In this way we can sum over the segments in each edge.
And measure the difference of the mapped segments and the rotated segments.

The only missing element for the full energy is a weight distribution factor sigma.
I will not explain it in detail, but we need to distribute the cotan weight to each segment,
depending on the length of the segment and the length of the full intrinsic edge.

Results


Now, we can optimize this energy using the exact same local/global approach as the other ARAP energies.

And actually the initial bunny deformation was made with our intrinsic ARAP method. So we get similar results to the spokes-and-rims method.

And we also have no asymmetries, like in the cube mesh.
Actually this result is in fact the same as for the original ARAP method.
And this makes sense, because for Delaunay meshes the two methods coincide as the intrinsic Delaunay triangulation is the extrinsic triangulation.

And we also do not touch the unconstrained bunny.

And the stool mesh also deformes

nicely.

Speed and convergence

S&R ARAP

iARAP

OG ARAP

S&R ARAP

iARAP

OG ARAP


The new approach comes with the additional costs of calculating the intrinsic triangulation and tracing out the intrinsic edges.
This is done in a prec-omputation step.
In the solving step we need to iterate over the segments of an intrinsic edge instead of just each edge.
These differences slightly increases the runtime per iteration as there are generally more segments than edges.

But, by and large, the method is comparable in terms of runtimes as you can see here.

As convergence per iteration is usually fast or even faster than the other methods.

ARAP Overview

Continuous

Discrete

Properties

$$E(\f,R) = \int_S \lVert J_\f - R \rVert^2 dS$$

constant $R_t$ over
each triangle

Face ARAP [LZXGG08]

$$\frac{1}{4}\sum_{t\in T}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_t(\e_{ij}) \rVert^2$$

no bending
penalty

constant $R_{\v}$ over
each vertex star

Spokes-and-rims ARAP [CPSS10]

$$\frac{1}{16}\sum_{\v\in V}\sum_{t\in N(\v)}\sum_{\e_{ij}\in t} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

triangulation
dependent
(asymmetries)

constant $R_{\v}$ over
each orthogonal dual
and $\f$ is discontinous

Orginal ARAP [SA07]

$$\frac{1}{16}\sum_{\v\in V}\sum_{\e_{ij}\in N(\v)} \cot(\alpha) \lVert \f(\e_{ij}) - R_{\v}(\e_{ij}) \rVert^2$$

may diverge
if not Delaunay

intrinsic Delaunay triangulation

Intrinsic ARAP

$$\frac{1}{16}\sum_{\v\in V}\sum_{\e_{ij}\in N_i(v)}\sum_{\s_{ij}^t\in \e_{ij}} \sigma_{ij}^t\cot(\alpha) \lVert \f(\s_{ij}^t) - R_{\v}(\s_{ij}^t) \rVert^2$$

best of
both worlds


So to conclude our overview

we have four discretizations of the continuous elastic energy depending on over which area we assume constant rotations.

Our contribution to this set of methods is that we first provide the missing derivation of the original ARAP energy.

And then we fixed the original method by working with the intrinsic Delaunay triangulation instead of the extrinsic triangulation. Resulting in a method combining the best of both commonly used methods at slightly increased run-time costs.

Yet another Laplacian

Skiped


And one last note for those interested in Laplacians. I do not have time to talk about it here, but if you want to know what this all has to do with Laplacians, feel free to ask me about in the upcming Q&A.

Thank You!


Thank you!

Code available!

https://cybertron.cg.tu-berlin.de/projects/iARAP/


And Code is available.

Backup

Yet another Laplacian

$$\min E(\f,R) = \min \int_{\tilde{S}} \lVert J_\f - R \rVert^2 dS$$

Necessary condition [CSSP10]: $$\Delta\f = \text{div} R$$

Global step in FARAP, S&R-ARAP and OG ARAP ➜ leads to cotan-Laplace.

iARAP leads to a different Laplace: $L_{ei}$.

Properties of [WMKG07]

symmetric

weak

strong

linear precision

positive weights

PSD

local

$L_{ei}$

✔

✘

✔

✘

✔


Ok. For the minimum of the continous energy

it is a necessary condition that the Laplacian of f is equal to the divergence of the rotations.

This equality is the global step in each of the presented ARAP methods.
And the discretizations of the Face, Spokes-and-rims and original ARAP method all lead to the cotan Laplace.

Our discretization leads to a different, new Laplacian.

We analyzed it according to Wardetzki et al. and found that it has similar properties as the cotan Laplacian. We also derived it using the stokes theorem and found that it linearly approximates the intrinsic Laplacian using only the extrinsic neighborhood information.

ARAP Revisited

Discretizing the Elastic Energyusing Intrinsic Voronoi Cells

Ugo Finnendahl, Matthias Schwartz, Marc Alexa

ARAP Revisited

ARAP Revisited

Discretizing ARAP

ARAP Overview

Continuous

Discrete

Properties

Face ARAP [LZXGG08]

Different Regions (1)

Face wise

Vertex star wise

ARAP Overview

Continuous

Discrete

Properties

Face ARAP [LZXGG08]

Spokes-and-rims ARAP [CPSS10]

Result

ARAP Overview

Continuous

Discrete

Properties

Face ARAP [LZXGG08]

Spokes-and-rims ARAP [CPSS10]

Different Regions (2)

Constant $R$ per vertex star

Constant $R$ per Voronoi cell

Orthogonal dual

Constant $R$ per Voronoi cell

Constant $R$ per orthogonal dual cell

Discretization

Non-conforming Crouzeix-Raviart basisfor finite element method

Input

Output

Energy over a triangle:

ARAP Overview

Continuous

Discrete

Properties

Face ARAP [LZXGG08]

Spokes-and-rims ARAP [CPSS10]

Orginal ARAP [SA07]

Result

Non Delaunay meshes

Constant $R$ per orthogonal dual cell

Artifacts and divergence

ARAP Overview

Continuous

Discrete

Properties

Face ARAP [LZXGG08]

Spokes-and-rims ARAP [CPSS10]

Orginal ARAP [SA07]

Orthogonal dual $\neq$ Voronoi cell

Constant $R$ per orthogonal dual cell

Constant $R$ per Voronoi cell

Constant $R$ per orthogonal dual cell of Delauany triangulation

Intrinsic Delaunay triangulation

Intrinsic ARAP

Original ARAP

Intrinsic ARAP

Results

Speed and convergence

S&R ARAP

iARAP

OG ARAP

S&R ARAP

iARAP

OG ARAP

ARAP Overview

Continuous

Discrete

Properties

Face ARAP [LZXGG08]

Spokes-and-rims ARAP [CPSS10]

Orginal ARAP [SA07]

Intrinsic ARAP

Discretizing the Elastic Energy
using Intrinsic Voronoi Cells

Non-conforming Crouzeix-Raviart basis
for finite element method