Integrating functions

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

vol(M):=MdA=φFvol(φ)

Given a volume form dA, we can define the integral of a dual function fΩ0(M):

Mf:=MfdA=φFf|φvol(φ).

Here we have used the notation

f|φ:=f(φ)

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 Ω0(M) into a euclidean vector-space by defining a scalar product

f,g=MfgdA.

One way to view such a scalar product is that it defines an isomorphism 21 into the dual space:

21:Ω0(M)Ω0(M)=Ω2(M)

21(f),g:=f,g=MgfdA.

Thus 21(f)=fσ. Setting 21(f)=:τ this implies τ(φ)=2(φ)σ(φ) for all φF or

(2τ)|φ=1vol(φ)φτ

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

vol(M)=vol(M).

We can ensure this and other natural properties by deriving both σ and σ 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 MK=(EK,sK,ρK). What is clear is that (up to a canonical bijection) the set of faces of MK is

FK={(v,φ)V×F|vφ}.

Here the intersection of v and φ is to be understood as subsets of E.

Gradient of scalar functions

Suppose we have a piecewise linear real-valued function g on a triangle mesh. g is completely determined by its values gi at vertices. Although it is not really important we imagine that the mesh is embedded in R3. Let σ 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

gradg,ejk=gkgjgradg,eki=gigk.

Because of c=ab, the third identity

gradg,eij=gjgi

is a consequence of the two above.

The normal vector N to the triangle is given by

N=12Aejk×eki=12Aeki×eij=12Aeij×ejk

where A=12|a×b| denotes the area of σ. Then one can verify that the vector

v:=12AN×(giejk+gjeki+gkeij)

solves the above equations. For example,

v,ejk=12AN×(giejk+gjeki+gkeij),ejk=12A(gjeij×ejk,N+gkeij×ejk,N)=gkgj.

Therefore gradg=v. The gradient of g rotated by 90 in the plane of the triangle is obtained by an even nicer formula than gradg itself:

N×gradg=12A(giejk+gjeki+gkeij).

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

The cotan formula

The norm of an m×n-matrix A is defined as

||A||2=tr(AtA)=i,jaij2.

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

||RA||2=tr((RA)t(RA))=tr(ARtRA)=||A||2

||AR||2=tr((AR)t(AR))=tr(R)1AtAR))=||A||2.

Note that the identity matrix has norm one.

For a a smooth map f:URm from some compact domain URn into Rm we define the Dirichlet energy of f as

E(f):=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 R2 and f is an affine map. Then df is constant on U. Denote by

D={(x,y)R2|0x,y,1xy}.

the “standard” triangle in R2 with edge vectors e1,e2. Denote by φ an affine map that maps D onto U. Then ψ:=fφ also is an affine map. Define vectors

v:=dφ(e1)R2

w:=dφ(e2)R2

a:=dψ(e1)=df(v)Rm

b:=dψ(e2)=df(w)Rm.

Thus we have the following picture:

Then we have

dψtdψ=(a,aa,ba,bb,b)

dφ1(dφ1)t=14A2(w,wv,wv,wv,v)

where

A:=detdφ2

is the area of U. From

df=dψdφ1

we then obtain

||df||2=tr((dφ1)tdψtdψdφ1)= tr(dψtdψdφ1(dφ1)t)=14A2(a,aw,w2a,bv,w+v,vb,b)=14A2((w,wv,w)|a|2+(v,vv,w)|b|2+v,w|c|2)=14A2(wv,w|a|2+v,vw|b|2+v,w|c|2)=12A(cotα|a|2+cotβ|b|2+cotγ|b|2).

Here we have used

c=ba

2a,b=|c|2|a|2|b|2

cosγ=v,w|v||w|

sinγ=2A|v||w|

and similar formulas for α and β. Thus we arrive at the following

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

E(f)=12(cotα|a|2+cotβ|b|2+cotγ|b|2).

Combinatorial metric on 1-forms

Imagine a rubber band stretched out between two points p,qRn. 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

E=c2|qp|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:

F=grad (pE(p)=12|qp|2)=qp.

Suppose now we have a discrete surface and a map

f:VRn

from the set of vertices into Rn. Think of the edges of the graph as realized by rubber bands trying to pull the points f(start(e)) and f(end(e)) together. Then the total energy stored in the configuration f will be

E(f)=12eE^|f(end(e))f(start(e))|2=12eE^|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 , on the vector space Ω1(M) whose norm is given by

||ω||2=eE^|ω(e)|2.

With this notation we then have

E(f)=12||df||2

and it is clear how to extend these definitions to the case of Rn-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

:Ω1(M)Ω1(M)=Ω1(M).

ω,η=ω,η.

When we work out what this means we arrive at

(ω)(e):=ω(e).

Now the force balancing condition can be formulated as

df=0.

Classification of surfaces

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:

a1,b1,ρ(a1),ρ(b1),,ag,bg,ρ(ag),ρ(bg)

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 I found by Google image search::

Topological equivalence

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 eE with

left(e)right(e)

We want to delete e and ρ(e) from E and define permutations s¯,ρ¯ on the set

E¯=E{e,ρ(e)}

of remaining edges. We will not touch ρ, so

ρ¯:=ρ|E¯.

What about s¯?

If all the edges are gone after the deletion (because each of them were either e or ρ(e)) then {e,ρ(e)} would have been a subset of E invariant under both s and ρ. 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 s1(e) is one of the remaining edges (the other cases are similar). Also sρ is then still alive because it cannot have been equal to ρ(e) (which belongs to a different face) and if it would have been e it would have been equal to s1(e), which we assumed is still there. If sρ(e) is gone, then it must have been equal to ρ(e) (since e belongs to a different face). This means that s1ρ(e) is also gone. Nothing is then left of the face containing ρ(e). We then define

s¯(s1(e)):=s(e).

Note that s is still bijective. If on the other hand sρ(e) is still available, then (by similar arguments as above) so is s1ρ(e) and we can we define

s¯(s1(e)):=sρ(e)s¯(s1ρ(e)):=s(e)

In both of the above cases we end up with a new surface 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 eE with

start(e)end(e)

Then a similar process as above leads to a new surface 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 M¯ is obtained from M by erasing an edge we say that M is obtained from 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,M~ are said to be topologically equivalent if 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#E~+#F. So the genus of a surface is a topological invariant.

Euler characteristic and genus

Let M be a connected discrete surface. From the last post we know

dim Im d1=#F1

and we already knew

dim Ker d0=1.

From

Im d0Ker d1

we see that the first Betti number

β1(M):=dim Ker d1dim Im d0

is non-negative. Let us apply the dimension formula for linear maps to d0 and d1:

β1=#E~dim Im d1(#Vdim Ker d0)=2+#E~#F#V.

Thus the so-called Euler characteristic

χ(M):=#V#E~+#F

satisfies

χ(M)2.

Theorem: χ(M) is an even number.

Proof: Since the permutation ρ of E consists of #E~ transpositions, its parity is

sgn ρ=(1)#E~.

The parity of a cyclic permutation

σ:{1,,n}{1,,n}

σ(k)=k+1mod n

is given by

sgn σ=(1)n1.

From this we see

sgn s=(1)#E+#F=(1)#F.

Similarly,

(1)#F(1)#E~=(sgn s)(sgn ρ)=sgn sρ=(1)#V.

◻

Thus also β1(M) is even and we can write

β1(M)=2g

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

χ=22g.

Where bunnies come from

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:

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

Poincaré duality

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 ρ (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 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

Im d1=(Ker 2).

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

Mσ=0.

In particular

dim(Im d1)=#F1.

Dual 2-forms and derivatives of dual 1-forms

A function fΩ0(M) assigns a function value to each vertex φ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 σ a dual 2-form we can define a pairing

σ,f=Mfσ=vVf(v)σ(v).

This exhibits the space Ω2(M) of all dual 2-forms as the dual vector space of Ω0(M):

Ω2(M)=Ω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:

1:Ω1(M)Ω2(M)

1η(v)=evη(e)

We show that 1 is the adjoint of d0:

1η,f=vVf(v)evη(e)=vVevf(v)η(e)=eEf(end(e))η(e)=12(eEf(end(e))η(e)+eEf(end(ρ(e)))η(ρ(e)))=12eE(f(end(e))start(e)))η(e)=eE^df(e)η(e)=η,df.

Thus indeed

1=d0.