Mathematische Visualisierung WS 2010/11

Integrating functions

Posted on January 27, 2011 by Ulrich Pinkall

A volume form on a discrete surface $M$ is a 2-form $dA$ such that $\textrm{vol}(\varphi):=dA(\varphi)>0$ for all faces $\varphi \in F$ . The interpretation is that a volume form assign an area $\textrm{vol}(\varphi)$ to each face $\varphi$ . The total area of $M$ is then defined as

$\displaystyle \textrm{vol}(M):=\int_M dA = \sum_{\varphi \in F} \textrm{vol}(\varphi)$

Given a volume form $dA$ , we can define the integral of a dual function $f\in \Omega_0(M^*)$ :

$\displaystyle \int_M f :=\int_M f\,dA= \sum_{\varphi \in F} f|_\varphi\,\textrm{vol}(\varphi)$ .

Here we have used the notation

$f|_\varphi := f(\varphi)$

for the evaluation of dual 0-forms on faces (recall they are to be viewed as functions that are constant on faces).

We can use this to make $\Omega_0(M^*)$ into a euclidean vector-space by defining a scalar product

$\displaystyle \langle \! \langle f,g \rangle \! \rangle =\int_M fg\, \,dA$ .

One way to view such a scalar product is that it defines an isomorphism $\star_2^{-1}$ into the dual space:

$\star_2^{-1}: \Omega_0(M^*) \rightarrow \Omega_0(M^*)^*=\Omega_2(M)$

$\displaystyle \langle \star_2^{-1}(f), g \rangle := \langle \! \langle f,g \rangle \! \rangle= \int_M gf \, dA$ .

Thus $\star_2^{-1}(f) = f \, \sigma$ . Setting $\star_2^{-1}(f)=:\tau$ this implies $\tau(\varphi)= \star_2(\varphi) \sigma(\varphi)$ for all $\varphi \in F$ or

$\displaystyle (\star_2 \tau)|_\varphi = \frac{1}{\textrm{vol}(\varphi)} \int_\varphi \tau$

Similarly, a volume form on $M^*$ allows to integrate functions $f \in \Omega_0(M)$ , now seen as functions that are constant on each dual cell. Then we also have a euclidean scalar product on $\Omega_0(M)$ . Now it seems unreasonable to choose $\sigma$ and $\sigma^*$ in a completely independent way. For example, a natural demand seems to be that $M$ and $M^*$ have the same area:

$\textrm{vol}(M^*) = \textrm{vol}(M)$ .

We can ensure this and other natural properties by deriving both $\sigma$ and $\sigma^*$ from a volume-form on the kite complex of $M$ . This is a discrete surface that kind of mediates between $M$ and $M^*$ . The kite complex has vertices at the vertices of $M$ , the vertices of $M^*$ and the “centers” of the edges of $M$ (understood combinatorially). Its faces (the kites) are all quadrilaterals and correspond to the intersections of faces of $M$ (the so-called primal faces) with faces of $M^*$ (the so-called dual faces). In the picture below, the triangle is a primal face and is the union of three kites. Each of the three dual faces is a union of six kites.

It is a nice exercise to construct the Kite complex as a discrete surface $M^K=(E^K,s^K,\rho^K)$ . What is clear is that (up to a canonical bijection) the set of faces of $M^K$ is

$F^K = \{(v,\varphi)\in V \times F \,|\, v \cap \varphi \neq \emptyset\}$ .

Here the intersection of $v$ and $\varphi$ is to be understood as subsets of $E$ .

Posted in Uncategorized | Leave a comment

Gradient of scalar functions

Posted on January 17, 2011 by Ulrich Pinkall

Suppose we have a piecewise linear real-valued function $g$ on a triangle mesh. $g$ is completely determined by its values $g_i$ at vertices. Although it is not really important we imagine that the mesh is embedded in $\mathbb{R}^3$ . Let $\sigma$ be a triangle with vertices $i,j,k$ and $a,b,c$ the edge vectors of the embedding.

The restriction of $g$ to the triangle is a linear function. Its gradient is constant vector in the plane of the triangle. It is characterized by the fact that

$\begin{align*}\langle \textrm{grad}\,g,e_{jk} \rangle &= g_k-g_j \\[5] \langle \textrm{grad}\,g, e_{ki} \rangle &= g_i-g_k.\end{align*}$

Because of $c=-a-b$ , the third identity

$\langle \textrm{grad}\,g, e_{ij} \rangle = g_j-g_i$

is a consequence of the two above.

The normal vector $N$ to the triangle is given by

$\displaystyle N=\frac{1}{2A}\,e_{jk}\times e_{ki}=\frac{1}{2A}\,e_{ki}\times e_{ij}=\frac{1}{2A}\,e_{ij}\times e_{jk}$

where $A = \frac{1}{2} |a\times b|$ denotes the area of $\sigma$ . Then one can verify that the vector

$\displaystyle v:= \frac{1}{2A} N\times (g_i e_{jk}+g_j e_{ki}+g_k e_{ij})$

solves the above equations. For example,

$\begin{align*} \langle v , e_{jk} \rangle &= \frac{1}{2A} \langle N \times (g_i e_{jk}+g_j e_{ki}+g_k e_{ij}),e_{jk} \rangle\\[5]&= \frac{1}{2A} (g_j<br /> \langle e_{ki} \times e_{jk},N\rangle +g_k \langle e_{ij} \times e_{jk},N \rangle)\\[5]&= g_k-g_j.\end{align*}$

Therefore $\textrm{grad}\,g=v$ . The gradient of $g$ rotated by $90\circ$ in the plane of the triangle is obtained by an even nicer formula than $\textrm{grad}\,g$ itself:

$\displaystyle N \times \textrm{grad}\,g =-\frac{1}{2A}( g_i e_{jk}+g_j e_{ki}+g_k e_{ij}).$

Here we just take a linear combination of the edge vectors with the value of $g$ at the opposing vertex as the respective coefficient.

Posted in Uncategorized | Leave a comment

The cotan formula

Posted on December 6, 2010 by Ulrich Pinkall

The norm of an $m\times n$ -matrix $A$ is defined as

$\displaystyle ||A||^2 = \textrm{tr}(A^t A) = \sum_{i,j} a_{ij}^2$ .

It stays the same if we multiply $A$ from the left or from the right by an orthogonal matrix $R$ :

$||RA||^2 =\textrm{tr}((RA)^t(RA)) =\textrm{tr}(AR^t RA)=||A||^2$

$||AR||^2 = \textrm{tr}((AR)^t(AR)) = \textrm{tr}(R)^{-1} A^t A R))=||A||^2$ .

Note that the identity matrix has norm one.

For a a smooth map $f: U \rightarrow \mathbb{R}^m$ from some compact domain $U \subset \mathbb{R}^n$ into $\mathbb{R}^m$ we define the Dirichlet energy of $f$ as

$\displaystyle E(f) := \int_U ||df||^2$ .

We think of $U$ as made of some ideal elastic material that wants to contract to a point. The Dirichlet energy is then the elastic energy needed to stretch $U$ via the map $f$ into some given shape. Note that the identity map on $U$ has the volume of $U$ as its Dirichlet energy.

We are interested in the case where $U$ is a triangle in $\mathbb{R}^2$ and $f$ is an affine map. Then $df$ is constant on $U$ . Denote by

$D=\{(x,y)\in\mathbb{R}^2 \,|\, 0\leq x,y,1-x-y \}$ .

the “standard” triangle in $\mathbb{R}^2$ with edge vectors $e_1,e_2$ . Denote by $\varphi$ an affine map that maps $D$ onto $U$ . Then $\psi:=f\circ \varphi$ also is an affine map. Define vectors

$v:= d\varphi(e_1)\in \mathbb{R}^2$

$w:= d\varphi(e_2)\in \mathbb{R}^2$

$a:= d\psi(e_1) = df(v) \in \mathbb{R}^m$

$b:= d\psi(e_2)= df(w)\in \mathbb{R}^m$ .

Thus we have the following picture:

Then we have

$\displaystyle d\psi^t d\psi = \left( \begin{array}{cc} \langle a,a\rangle & \langle a,b\rangle \\ \langle a,b\rangle &\langle b,b\rangle \end{array} \right)$

$\displaystyle d\varphi^{-1} (d\varphi^{-1})^t = \frac{1}{4A^2}\left( \begin{array}{rr} \langle w,w \rangle & -\langle v,w \rangle \\ -\langle v,w \rangle &\langle v,v \rangle \end{array} \right)$

where

$\displaystyle A := \frac{\det d\varphi}{2}$

is the area of $U$ . From

$df = d\psi \circ d\varphi^{-1}$

we then obtain

$\displaystyle ||df||^2 \\\\= \textrm{tr} ((d\varphi^{-1})^t d\psi^t d\psi d\varphi^{-1})\\\\=\ \textrm{tr} (d\psi^t d\psi d\varphi^{-1}(d\varphi^{-1})^t)\\\\=\frac{1}{4A^2}(\langle a,a\rangle \langle w,w \rangle-2\langle a,b\rangle\langle v,w \rangle+\langle v,v \rangle\langle b,b\rangle)\\\\=\frac{1}{4A^2}((\langle w,w \rangle-\langle v,w \rangle)|a|^2+(\langle v,v \rangle-\langle v,w \rangle)|b|^2+\langle v,w \rangle|c|^2)\\\\=\frac{1}{4A^2}(\langle w-v,w \rangle |a|^2+\langle v,v-w \rangle|b|^2+\langle v,w \rangle|c|^2)\\\\=\frac{1}{2A}(\cot \alpha \,|a|^2 + \cot \beta \,|b|^2+ \cot \gamma \,|b|^2).$

Here we have used

$c=b-a$

$-2\langle a,b\rangle=|c|^2-|a|^2-|b|^2$

$\displaystyle \cos \gamma = \frac{\langle v,w \rangle}{|v|\,|w|}$

$\displaystyle \sin \gamma = \frac{2A}{|v|\,|w|}$

and similar formulas for $\alpha$ and $\beta$ . Thus we arrive at the following

Theorem (cotan formula): For an affine map $f$ between triangles we have

$E(f) = \frac{1}{2}(\cot \alpha\, |a|^2 + \cot \beta\, |b|^2+ \cot \gamma \,|b|^2)$ .

Posted in Uncategorized | Leave a comment

Combinatorial metric on 1-forms

Posted on November 29, 2010 by Ulrich Pinkall

Imagine a rubber band stretched out between two points $p,q \in \mathbb{R}^n$ . We assume that the rubber band is an ideal one, which means that it would really contract to a point when released and that the energy stored in the rubber satisfies Hooke’s law of elasticity perfectly. The the elastic energy of the stretched band is

$\displaystyle E=\frac{c}{2}|q-p|^2$

Here $c$ is some constant. It is called the spring constant, since we could also imagine springs instead of rubber bands. For the moment we will assume $c=1$ . If we keep $q$ fixed and try to move $p$ we experience a force $F$ at $p$ which is minus the gradient of the energy:

$\displaystyle F = -\textrm{grad }(p\mapsto E(p)=\frac{1}{2}|q-p|^2) = q-p$ .

Suppose now we have a discrete surface and a map

$f: V \rightarrow \mathbb{R}^n$

from the set of vertices into $\mathbb{R}^n$ . Think of the edges of the graph as realized by rubber bands trying to pull the points $f(\textrm{start}(e))$ and $f(\textrm{end}(e))$ together. Then the total energy stored in the configuration $f$ will be

$\displaystyle E(f) = \frac{1}{2} \sum_{e \in \hat{E}} |f(\textrm{end}(e))-f(\textrm{start}(e))|^2 = \frac{1}{2} \sum_{e \in \hat{E}} |df(e)|^2$ .

It is enough to know this energy in the case $n=1$ (the whole graph is stretched out on a line) since in the general case the energy is just the sum of the energies of the $n$ different components of $f$ . In the 1-dimensional case it is clear that we basically are dealing with a euclidean scalar product $\langle \!\langle \,,\rangle \!\rangle$ on the vector space $\Omega_1(M)$ whose norm is given by

$||\omega||^2=\sum_{e \in \hat{E}} |\omega(e)|^2$ .

With this notation we then have

$E(f) =\frac{1}{2}||df||^2$

and it is clear how to extend these definitions to the case of $\mathbb{R}^n$ -valued 1-forms and functions. We call $E(f)$ the combinatorial Dirichlet energy of $f$ .

Imagine that we fix some vertices (maybe those on the boundary) and let the interior vertices find positions such that the stretching energy $E$ achieves a minimum value.

In such an equilibrium position the forces at each vertex have to balance out, i.e. their they must sum up to zero.

These forces are exactly the values of the 1-form $df$ on the outgoing edges at the vertex. Thus it seems that the mentioned sum is just the value at the vertex of the dual 1-form obtained by re-interpreting the values of the 1-form $df$ on edges as defining a dual 1-form, call it $*df$ .

How do we get there? First note that we can use the euclidean scalar product to define a vector space isomorphism

$*:\Omega_1(M) \rightarrow \Omega_1(M)^* = \Omega_1(M^*)$ .

$\displaystyle \langle *\omega, \eta \rangle = \langle \!\langle \omega, \eta \rangle \!\rangle$ .

When we work out what this means we arrive at

$(*\omega)(e):=\omega(e)$ .

Now the force balancing condition can be formulated as

$\partial*df=0$ .

Posted in Uncategorized | Leave a comment

Classification of surfaces

Posted on November 22, 2010 by Ulrich Pinkall

From the results of the last post it is clear that a surface $M$ is topologically equivalent either to a sphere with exactly two oriented edges or to a surface with at least four oriented edges but only one face and only one vertex.

In the last case the number of oriented edges must be divisible by four (since the Euler characteristic is even). In fact this number must be four times the genus. From here one can procede (we will not show the details here) by clever applications of splitting, erasing and contraction to finally arrive at a normal form where the edges along the single face come in the following order:

$a_1, b_1, \rho(a_1), \rho(b_1),\ldots ,a_g, b_g, \rho(a_g), \rho(b_g)$

This “normal form” then yields the following

Theorem: Two discrete surfaces are topologically equivalent if and only if they have the same genus.

Here are some surfaces of genus up to two:

Posted in Uncategorized | Leave a comment

Topological equivalence

Posted on November 22, 2010 by Ulrich Pinkall

Let $M$ be a connected surface with at least four oriented edges (if there only two edges then we know we have a sphere). Suppose we have an edge $e \in E$ with

$\textrm{left}(e) \neq \textrm{right}(e)$

We want to delete $e$ and $\rho(e)$ from $E$ and define permutations $\bar{s},\bar{\rho}$ on the set

$\bar{E}=E-\{e,\rho(e)\}$

of remaining edges. We will not touch $\rho$ , so

$\bar{\rho} := \rho|_{\bar{E}}$ .

What about $\bar{s}$ ?

If all the edges are gone after the deletion (because each of them were either $e$ or $\rho(e)$ ) then $\{e,\rho(e)\}$ would have been a subset of $E$ invariant under both $s$ and $\rho$ . Since $M$ is connected, this subset would have been the whole of $E$ , contradicting our assumption that we had at least four edges.

Let us look at the case where $s^{-1}(e)$ is one of the remaining edges (the other cases are similar). Also $s(e)$ is then still alive because it cannot have been equal to $\rho(e)$ (which belongs to a different face) and if it would have been $e$ it would have been equal to $s^{-1}(e)$ , which we assumed is still there. If $s\circ \rho(e)$ is gone, then it must have been equal to $\rho(e)$ (since $e$ belongs to a different face). This means that $s^{-1}\circ \rho(e)$ is also gone. Nothing is then left of the face containing $\rho(e)$ . We then define

$\bar{s}(s^{-1}(e)):=s(e)$ .

Note that $s$ is still bijective. If on the other hand $s\circ \rho(e)$ is still available, then (by similar arguments as above) so is $s^{-1}\circ \rho(e)$ and we can we define

$\begin{align*}\bar{s}(s^{-1}(e))&:=s\circ\rho(e)\\ \bar{s}(s^{-1}\circ \rho(e))&:=s(e)\end{align*}$

In both of the above cases we end up with a new surface $\bar{M}$ (still connected) having two edges less, the same number of vertices and the number of faces has been reduced by one. We call this process “erasing” an edge.

Suppose we have an edge $e \in E$ with

$\textrm{start}(e) \neq \textrm{end}(e)$

Then a similar process as above leads to a new surface $\bar{M}$ (still connected) having two edges less, the same number of faces and the number of vertices has been reduced by one. We call this process “contracting” an edge.

When $\bar{M}$ is obtained from $M$ by erasing an edge we say that $M$ is obtained from $\bar{M}$ by “splitting a face”. Similarly we use for the opposite of “contracting an edge” the name “splitting a vertex”.

Definition: Two discrete surfaces $M,\tilde{M}$ are said to be topologically equivalent if $\tilde{M}$ can be obtained from $M$ through a sequence of erasing or deleting edges or splitting faces or vertices.

Note that two topologically equivalent surfaces have the same Euler characteristic $\#V-\#\tilde{E}+\#F$ . So the genus of a surface is a topological invariant.

Posted in Uncategorized | Leave a comment

Euler characteristic and genus

Posted on November 19, 2010 by Ulrich Pinkall

Let $M$ be a connected discrete surface. From a previous post we know

$\textrm{dim Im }d_1=\#F-1$

and we already knew

$\textrm{dim Ker }d_0=1$ .

From

$\textrm{Im }d_0 \subset \textrm{Ker }d_1$

we see that the first Betti number

$\beta_1(M) := \textrm{dim Ker }d_1 -\textrm{dim Im }d_0$

is non-negative. Let us apply the dimension formula for linear maps to $d_0$ and $d_1$ :

$\beta_1=\#\tilde{E}-\textrm{dim Im }d_1-(\#V-\textrm{dim Ker }d_0)=2+\#\tilde{E}-\#F-\#V$ .

Thus the so-called Euler characteristic

$\chi(M):=\#V – \#\tilde{E} + \#F$

satisfies

$\chi(M) \leq 2$ .

Theorem: $\chi(M)$ is an even number.

Proof: Since the permutation $\rho$ of $E$ consists of $\#\tilde{E}$ transpositions, its parity is

$\textrm{sgn } \rho =(-1)^{\#\tilde{E}}$ .

The parity of a cyclic permutation

$\sigma: \{1, \ldots ,n\} \rightarrow \{1, \ldots ,n\}$

$\sigma(k) = k+1 \quad \textrm{mod }n$

is given by

$\textrm{sgn } \sigma =(-1)^{n-1}$ .

From this we see

$\textrm{sgn } s=(-1)^{\#E+\#F}=(-1)^{\#F}$ .

Similarly,

$(-1)^{\#F}(-1)^{\#\tilde{E}}= (\textrm{sgn } s)(\textrm{sgn } \rho)=\textrm{sgn } s\circ \rho=(-1)^{\#V}$ .

$\square$

Thus also $\beta_1(M)$ is even and we can write

$\beta_1(M) = 2g$

for a natural number $g$ called the genus of $M$ . The genus is related to the Euler characteristic by

$\chi= 2-2g$ .

Posted in Uncategorized | Leave a comment

Where bunnies come from

Posted on November 1, 2010 by Ulrich Pinkall

The Stanford bunny that I use for many pictures is the most common 3D-model used for test purposes in Computer Graphics. It was obtained with a 3D-scanner not from a living bunnie but from this thing:

The resulting scan data are available here and look like this:

The actual cell-decomposition I use for pictures comes from a project to automatically generate cut-out sheets for paper models. Here is the relevant research paper and here is the paper model:

Researchers in computer graphics continue to always find new ways to do horrible things to the bunny. Here are just a few examples:

$fractureBunny$

Posted in Uncategorized | Leave a comment

Poincaré duality

Posted on October 31, 2010 by Ulrich Pinkall

In our context Poincaré duality means that we can apply facts we know in general about discrete surfaces to the dual surface $M^*$ and obtain information about $M$ in this way.

A discrete surface $M$ is connected if and only if $E$ has no proper subsets that are invariant under both $s$ and $\rho$ (see an earlier post). Using this characterization of connectedness it is easy to see that for connected $M$ also $M^*$ is connected.

As an immediate application, we note that for a connected $M$ the kernel of $\partial_2$ is one-dimensional: it consists of the constant dual 0-forms and these can also be viewed as ordinary 0-forms on $M^*$ . Now the image of a linear map between vector spaces is always the orthogonal complement of the kernel of its adjoint map. In our case this yields

$\textrm{Im }d_1=(\textrm{Ker }\partial_2)^\perp$ .

Theorem: A 2-form $\sigma$ on a connected surface $M$ is exact if and only if

$\int_M \sigma = 0$ .

In particular

$\textrm{dim(Im }d_1) = \#F-1$ .

Posted in Uncategorized | Leave a comment

Dual 2-forms and derivatives of dual 1-forms

Posted on October 31, 2010 by Ulrich Pinkall

A function $f\in \Omega_0(M)$ assigns a function value to each vertex $\varphi\in V$ . One way to picture this is that this function value is only given at some choosen point in the face . Another interpretation (which we prefer right now) is to see $f$ as a function on the surface that is constant on each face of the dual surface $M^*$ .

Think about the colors in the above picture as color-coding the function values (which are real numbers) as various colors.

We can proceed in a similar way as we did for 2-forms and dual 0-forms: If $f$ is a 0-form and $\sigma^*$ a dual 2-form we can define a pairing

$\displaystyle \langle \sigma^* , f \rangle = \int_{M^*} f \, \sigma^* = \sum_{v \in V} f(v)\, \sigma^*(v)$ .

This exhibits the space $\Omega_2(M^*)$ of all dual 2-forms as the dual vector space of $\Omega_0(M)$ :

$\Omega_2(M^*)=\Omega_0(M)^*$ .

We define the derivative of a dual 1-form just by applying the standard definition of the derivative of a 1-form to the dual surface:

$\partial_1: \Omega_1(M^*) \rightarrow \Omega_2(M^*)$

$\displaystyle \partial_1 \eta(v) = \sum_{e \in v} \eta(e)$

We show that $\partial_1$ is the adjoint of $d_0$ :

$\begin{align*}\langle \partial_1 \eta, f \rangle &=\sum_{v \in V} f(v)\,\sum_{e \in v} \eta(e)\\[5]&=\sum_{v \in V} \,\sum_{e \in v} f(v) \eta(e)\\[5]&=\sum_{e \in E} f(\textrm{end}(e)) \, \eta(e)\\[5]&=\frac{1}{2} \left( \sum_{e \in E} f(\textrm{end}(e)) \, \eta(e)+\sum_{e \in E} f(\textrm{end}(\rho(e))) \, \eta(\rho(e))\right)\\[5]&=\frac{1}{2} \sum_{e \in E}( f(\textrm{end}(e)) – \textrm{start}(e)))\, \eta(e)\\[5]&=\sum_{e \in \hat{E}} df(e)\, \eta(e)\\[5]&=\langle \eta, df\rangle.\end{align*}$

Thus indeed

$\partial_1 = d_0^*$ .

Posted in Uncategorized | Leave a comment

Mathematische Visualisierung WS 2010/11

Integrating functions

Gradient of scalar functions

The cotan formula

Combinatorial metric on 1-forms

Classification of surfaces

Topological equivalence

Euler characteristic and genus

Where bunnies come from

Poincaré duality

Dual 2-forms and derivatives of dual 1-forms

Recent Posts

Recent Comments

Archives

Categories

Meta

Powered by