Embedding

"negative" area


The task is,
given a *triangle* surface mesh,

*click*

find a continuous bijective mapping between every point on the
mesh and a subset of the plane.
And as we usually work with *piecewise linear mappings* of triangle meshes,
this is the case whenever we find a position for each vertex,
such that no two triangles overlap.
So this is an embedding,

*click*

and this is not,

*click*

as this red flipped triangle with "negative" area overlaps other triangles.

This is a problem as lot of optimization methods that operate on embeddings,
require a correct initial embedding as input
otherwise the optimization fails.

Unfortunately this is not always the case.
-- ??

Tutte embedding [Tutte 1963]

boundary

flipped


Take for example the commonly used Tutte embedding.
Tutte embedding is a very simple and fast technique, but it
may generate flipped triangles.

In *theory* it should not as long
as the boundary in the plane is convex,
but due to floating point rounding errors it may fail.

Take for example this well triangulated mesh from Thingi10k
It contains less then 200 vertices

*click*
But if we pick the first triangle of the face list as the boundary
*click*
and let Tutte embed the rest of the mesh within it,
*click*
it generates 25 flipped triangles using double precision.

And this is the case for around 3% of the genus 0 meshes of Thingi10k.
Which is a problem. So lets solve it.

One simple solution would be, to take the mapping and redo the
embedding
*click*
using a different embedding technique.

But that may also suffer from rounding errors
and generates a completely different embedding,
which does not resemble the input mapping.

So we want to repair a mapping, without changing it to much.
-- 1:48

Progressive Embedding [Shen et al. 2019]

edge collapse

edge insertion


And there already exists a method that does exactly that
called progressive embeddings.
*click*

This method from 2019 identifies all flipped triangles
and removes them using edge collapses.
*click*
Then, after all flipped triangles are removed,
They are reintroduced,
*click*
while taking care that the newly introduced triangles are correctly orientated.

which works but I will now present
a completely different method,
which is *way* faster than progressive embedding
or even other embedding techniques including Tutte.
-- 2:19

Schnyder Embeddings [Schnyder 1990]

linear running time

$$b_i = \left(\htmlData{fragment-index=94}{\frac{1}{|T|}}\sum_{t\in \red{R_i^{\rr}}} 1, \htmlData{fragment-index=94}{\frac{1}{|T|}}\sum_{t\in \green{R_i^{\gg}}} 1, \htmlData{fragment-index=94}{\frac{1}{|T|}}\sum_{t\in \blue{R_i^{\bb}}} 1\right)$$

$$b_i = \left(\frac{1}{|\mathbf{w}|}\sum_{t\in \red{R_i^{\rr}}} w_t, \frac{1}{|\mathbf{w}|}\sum_{t\in \green{R_i^{\gg}}} w_t, \frac{1}{|\mathbf{w}|}\sum_{t\in \blue{R_i^{\bb}}} w_t \right)$$

complex boundary

holes


To explain our approach
I first need to explain an embedding technique coming from graph theory.

Its called Schnyder embedding and is
a bit restrictive regarding the input.

the input needs to be a maximal planar graph.
In computer graphics terms this means we assume a *triangulation* with disc topology
where the boundary is a *single triangle*.
So no complex boundaries
*click*
and no holes.
*click*

This is a major restriction,
but we can always add a triangle around our input
*click* *click*
and triangulate holes.
*click*

So lets assume we always have a triangle as boundary and
no holes in our input.

Note that in this visualization it seems that we already have an embedding given.
But the input is just the connectivity of this graph.
Not the vertex positions.

Ok, how is the Schynder embedding now defined?

It is based on a graph coloring called Schnyder labelings.
*click*
And I wish I could, but due to time constrains,
I'm not able to explain how the labeling is constructed or defined.

But the most important information for us is,
that given such a schnyder labeling,
we are able to separate all triangles into three colored regions, *per* vertex.
*click*
So each vertex divides all triangles into a red, green and blue region
like this, *click* this, *click* this or *click* this.

We will use these regions
*click*
for the embedding by defining
barycentric coordinates with respect to the boundary vertices.
*click*
So each vertex gets a barycentric coordinate which is defined as
the number of triangles in each region,
*click*
and of course we have to normalize this by dividing by the number triangles.
*click*
This vertex for example
its regions are given by
2 red triangles, 2 green triangles, and therefore 11 blue triangles.

And we can now set all vertices to their barycentric position,
with respect to the boundary triangle
*click*
we end up with these positions,
which is the *Schynder embedding*.

And Schnyder proved that this actually always leads to an embedding.
And he also showed that this can be calculated in linear time.
*click*
Including finding a labeling and counting the triangles in each region.
*click*

Which makes this 10 times faster than Tuttes method
using the cholmod library, for the solving step.
Which I find quite surprising.
*click*

But we do not want to find an embedding,
we want to fix it.
Therefore we have to extend this method.
-- ??

Weighted Schnyder Embeddings [Dhandapani 2010]

$$\mathbf{w} = \begin{bmatrix} \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00} \end{bmatrix} $$

$$\phantom{\mathbf{w} =} \begin{matrix} w_0\\ w_1\\ w_2\\ w_3\\ w_4\\ w_5\\ w_6\\ w_7\\ w_8\\ w_9\\ w_{10}\\ w_{11}\\ w_{12}\\ w_{13}\\ w_{14} \end{matrix} $$

linear time

$$b_i = \left(\frac{1}{|T|}\sum_{t\in \red{R_i^{\rr}}} 1, \frac{1}{|T|}\sum_{t\in \green{R_i^{\gg}}} 1, \frac{1}{|T|}\sum_{t\in \blue{R_i^{\bb}}} 1\right)$$

$$b_i = \left(\frac{1}{|\mathbf{w}|}\sum_{t\in \red{R_i^{\rr}}} w_t, \frac{1}{|\mathbf{w}|}\sum_{t\in \green{R_i^{\gg}}} w_t, \frac{1}{|\mathbf{w}|}\sum_{t\in \blue{R_i^{\bb}}} w_t \right)$$


*One* extension is to weight each triangle differently.
*click*

So we give each triangle a weight
*click*
and sum over the weights instead of simply counting.
*click*

Therefore uniform weights lead to a normal Schnyder embedding,
*click*
but we can change the weights to define different embeddings.

And as long as all weights are strictly *positive*
the proof of Schnyders still holds,
and we really end up with an embedding,
*click*
still in *linear time*.

*click*
But if we have a negative weight, triangles may flip.
-- 5:41

Transformation

Weights Space

$$\mathbf{w} = \begin{bmatrix} \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00}\\ \phantom{-0.00} \end{bmatrix} $$

Barycentric Coordinates Space

$$L \htmlData{fragment-index=50}{\in \{0,1\}^{N\times N}}$$

$$L^{-1} \htmlData{fragment-index=65}{\in \{-1,0,1\}^{N\times N}}$$

$$b_i = \left(\frac{1}{|\mathbf{w}|}\sum_{t\in \red{R_i^{\rr}}} w_t, \frac{1}{|\mathbf{w}|}\sum_{t\in \green{R_i^{\gg}}} w_t, \frac{1}{|\mathbf{w}|}\sum_{t\in \blue{R_i^{\bb}}} w_t \right)$$


Ok, so what do we have?
*click*
A homogeneous weight space
*click*
that can be transformed into a barycentric space.
And the transformation L is linear,
*click*
as for each barycentric coordinate we just sum over some weights.
Yes, we have to divide by the sum of weights,
but the sum of weights can be normalized to one or
we can just store the sum separately.
*click*
So we can represent L using a matrix containing only 0s and 1s.

And the cool thing is, that L is in fact regular
*click*
so we can invert this transformation.

And in our paper we also showed, that
this inverse transformation like the forward transformation
just takes linear time, as L inverse is sparse.
*click*
And its non-zero entries are only 1 or -1.

So we have an invertable linear transformation.

Which is cool,
because now instead of generating embeddings using the weight space,
*drag weights*
we can change the positions of our mesh
*drag vertex positions*
and get the corresponding weights.

So we could also input barycentric coordiantes
which come from inputs with flipped triangles.
*drag vertex positions*

And we know that the resulting weight vector must contain negative weights.
As an all positive weight vector would have lead to a valid embedding.
*hover negative weight*
This allows we have a very simple fixing strategy.
-- ??

Naïve Approach

flipped triangles

$$L$$

$$\begin{pmatrix} \red{-1.04}\\ 0.64\\ \red{-1.73}\\ \vdots \\ 0.98\\ \red{-0.32}\\ 0.80 \end{pmatrix} $$

$$\begin{pmatrix} \green{1}\\ 0.64\\ \green{1}\\ \vdots \\ 0.98\\ \green{1}\\ 0.80 \end{pmatrix} $$

$$L^{-1}$$


*click*
We take a mapping with flipped triangles,
*click*
convert it to weight space
*click*
set all negative weights to a positive weight.
*click*
Then transform it back and we have a fixed triangulation.

And this works and is really fast as each step only takes linear time,
*but* it also changes the triangulation quite a lot.
It does not resembles the input at all.

Which might be ok, as it is really fast,
but we can do better.
-- ??

Weight Space

$$\delta_{\text{unflip}} = \frac{1}{2}\left(\sqrt{\operatorname{tr}^2A-4\det A}-\operatorname{tr} A\right)$$

$$\delta_{\text{fully extend}} = \max\left\{\begin{aligned} \max\{b^{\rr}_{t^{\gg}}, b^{\rr}_{t^{\bb}}\}-b^{\rr}_{t^{\rr}},\\ \max\{b^{\gg}_{t^{\rr}}, b^{\gg}_{t^{\bb}}\}-b^{\gg}_{t^{\gg}},\\ \max\{b^{\bb}_{t^{\rr}}, b^{\bb}_{t^{\gg}}\}-b^{\bb}_{t^{\bb}}\phantom{,} \end{aligned}\right\}$$


Unfortunately the sign of the weight does not
allow any conclusions about the sign of the triangle area

A correctly orientated triangle can have negative weight,
*click*
while a flipped triangle can also have positive weight.

But we proved that,
given a flipped triangle,
*click*
by increasing the weight of this flipped triangle,
it will unflip.
*click*
And the necessary weight-difference is directly calculable.

Unfortunately, by increasing this weight,
we might flip other triangles.
So this triangle might also get flipped again,
if we increase other weights.

But we also showed that there is a second weight threshold,
*click*
after which a triangle will never be flipped again
as long as we only increase weights.

This allows for a different strategy:
-- 8:21

Better Strategy

Ours

flipped triangles

$$L$$

$$\begin{pmatrix} -1.04\\ \red{0.64}\\ -1.73\\ \vdots \\ 0.98\\ \red{-0.32}\\ 0.80 \end{pmatrix} $$

$$\begin{pmatrix} -1.04\\ \red{0.64+\delta_i}\\ -1.73\\ \vdots \\ 0.98\\ \red{-0.32+\delta_k}\\ 0.80 \end{pmatrix} $$

$$L^{-1}$$

repeat until all triangles are unfliped



Take the input mesh,
*click*
identify flipped triangles,
*click*
increase their corresponding weight
*click*
and repeat until all triangles are unflipped.
*click*

This is not linear anymore as we do not know how many repetitions we need,

but it is still very fast.
*click*

A suitable weight increasing strategy finishes within seconds,
while progressive embedding needs minutes and hours.
-- ??

Results

lower is better

Ours

Input

Output


And now the results look much better and closer to the input, then using the naive approach
*click*
which we also measured and compared to progressive embedding.

And we found that both methods have similar distortion errors.

Ok so are we done?
Not quite yet,
-- 9:06

Exact Arithmetic

$$L \in \{0,1\}^{N\times N}$$

$$L \in \Z^{N\times N}$$

$$L^{-1} \in \{-1,0,1\}^{N\times N}$$

$$L^{-1} \in \Z^{N\times N}$$

Weights Space

$$\R$$

$$\Z$$

Barycentric Coordinates Space

$$\R$$

$$\Z$$


I completely ignored one word of the title.
Which states, that we use exact arithmetic.
So far we have done everything using real values, therefore floating points.
Which again introduces rounding errors.

But if we recall our transformation matrices,
*click*
we can see, that they only contain integers.
*click*

So we can choose to use integers or rationals instead of real numbers
*click*
also to represent our weight space and barycentric space and
still convert between them lossless.

So as long as we do not overflow, we have exact arithmetic in integers.
-- 9:43

Conclusion

Input

Output

✔ Pros

Efficent Embeddings
in Exact Arithmetic

✘ Cons

Boundary is triangle
or not controllable
Works only with triangle meshes


So to conclude.
*click*
We have very efficient embeddings
*click*
in exact arithmetic
for fixing mappings.

with some limitations:
*click*
The boundary must be either a triangle
*click*
or is not controllable,
*click*
as after wrapping a non-triangular boundary
and increasing certain weights
we have no control over the shape of the original boundary.
*click*
*click*
And it *also only* works on triangle meshes,
no quad or tetrahedral meshes,

which would be an interesting future research topic.
But like I said, that is another topic

So thanks for your attention.
-- 10:11

Code available (soon™)

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

Efficient Embeddings

in Exact Arithmetic

Ugo Finnendahl, Dimitris Bogiokas, Pablo Robles Cervantes, Marc Alexa

SIGGRAPH 08.08.2023

Embedding

Tutte embedding [Tutte 1963]

Progressive Embedding [Shen et al. 2019]

Schnyder Embeddings [Schnyder 1990]

Weighted Schnyder Embeddings [Dhandapani 2010]

Transformation

Weights Space

Barycentric Coordinates Space

Naïve Approach

Weight Space

Better Strategy

Results

Input

Output

Exact Arithmetic

Weights Space

$$\R$$

$$\Z$$

Barycentric Coordinates Space

$$\R$$

$$\Z$$

Conclusion

Input

Output

✔ Pros

✘ Cons

Thank You!

Code available (soon™)

Code available (soon™)