Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can anyone explain to me these two facts which I don't get from Euler's formula for triangle meshes?

First, Euler's formula reads $V - E + F = 2(1-g)$ where $V$ is vertices number, $E$ edges number, $F$ faces number and $g$ genus (number of handles in the mesh). Now my book says

Since for most practical applications the genus is small compared to the number of elements, the right hand side of the equation can be assume to be negligible. Given this and the fact that each triangle is bounded by three edges and that each interior manifold edge is incident to two triangles, one can derive the following

  1. The number of triangles is twice the number of vertices $F \approx 2V$
  2. The number of edges is three times the number of vertices $E \approx 3V$
share|improve this question

migrated from gamedev.stackexchange.com Jun 21 '13 at 5:43

This question came from our site for professional and independent game developers.

1  
As @Nathan mentions, the primary observation is that, for a triangle mesh without boundary, we obtain the relation $2E = 3F$. This allows you to eliminate either $E$ or $F$ in Euler's formula. You may as well do it directly without making an approximation first, e.g., $2V = F + 4(1-g)$. In a typical graphics mesh, you might have thousands, or hundreds of thousands of triangle faces, but less than a dozen handles. –  yasmar Jun 21 '13 at 6:43

1 Answer 1

up vote 3 down vote accepted

Since we're talking about a triangle mesh, there is a fixed relationship between the number of edges and the number of faces. To derive this it's helpful to think of the mesh as being made of half-edges. A half-edge is a pair of an edge and a face it borders. The total number of half-edges in the mesh is $2E$, since each edge has two halves; and it's also $3F$, since each face touches three half-edges and this counts all the half-edges exactly once. Therefore $2E = 3F$.

By solving for $E$ or $F$ and substituting into the formula $V - E + F \approx 0$, we can easily derive your two facts:

  1. $E = \frac{3}{2}F, \qquad V - \frac{3}{2}F + F \approx 0, \qquad V - \frac{1}{2}F \approx 0, \qquad F \approx 2V$.
  2. $F = \frac{2}{3}E, \qquad V - E + \frac{2}{3}E \approx 0, \qquad V - \frac{1}{3}E \approx 0, \qquad E \approx 3V$.
share|improve this answer
    
Thank you I never thought those fact took into account the half-edge representation of the triangular mesh. Got it. –  BRabbit27 Jun 21 '13 at 8:10
    
There is an error en in the second formula, it has F = 2/3 F but it should read F = 2/3 E. I tried to edit but S.O. asked for more changes. –  BRabbit27 Jun 29 '13 at 13:24
    
@BRabbit27 Fixed. –  Nathan Reed Jun 30 '13 at 1:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.