Practical Polygonal Mesh Modeling with Discrete Gaussian-Bonnet Theorem

E RGUN A KLEMAN Visualization Sciences Program J IANER C HEN Computer Science Department

Texas A&M University

Abstract
In this paper, we introduce a practical modeling approach to improve the quality of polygonal mesh structures. Our approach is based on a discrete version of Gaussian-Bonnet theorem on piecewise planar manifold meshes and vertex angle deections that determines local geometric behavior. Based on discrete GaussianBonnet theorem, summation of angle deections of all vertices is independent of mesh structure and it depends on only the topology of the mesh surface. Based on this result, it can be possible to improve organization of mesh structure of a shape according to its intended geometric structure.

Introduction

Our approach is based on the Gauss-Bonnet Theorem that says that the integral of the Gaussian curvature over a closed smooth surface is equal to 2 the Euler characteristic of the surface which is 2 2g [Weisstein 2005]. The theorem requires a smooth surface. In this section, we provide a simple proof for Gauss-Bonnet Theorem on Piecewise Linear Meshes.

2.1

Piecewise Linear Meshes

Motivation

Most professional modelers in animation and special effect industry slowly migrated subdivision surfaces. One of the crucial questions for practical modeling with subdivision surfaces is to identify the numbers and types of extraordinary vertices that needs to be used for a successful modeling. In the rst observation, this question seems easy to answer based on genus of the goal surface. Using Eulers formula, we can compute the number of extraordinary vertices and their valences (also the number of faces and their valences) for the given genus. However, extraordinary vertices do not result only from genus. In most practical cases, we need to consider the geometrical structure of the surface. Tree structures are especially the ones that cause problems. Tree structures are more common than real trees. For instance, even head of a human being can be considered genus1 tree that has at least 3 branches that include nose and 2 eyes. The one hole come from digestive track that start from mouth. It is possible to model the head as a genus-0 tree with at least four branches by include mouth as a branch. By relating topology and geometry, we give a framework to answer such problems coming from practical modeling. Our results justify some of the intuitively developed practices in current modeling approaches. For instance, the modelers introduce extraordinary vertices to model eyes, nose and mouth in facial modeling. Our results go further than and even dees common sense about subdivision modeling. We show that despite the common belief the quality of some surfaces can be improved by introducing extraordinary vertices.
Author: Program Coordinator, Visualization Sciences, Department of Architecture, College of Architecture. Address: 418 Langford Center C, College Station, Texas 77843-3137. email: ergun@viz.tamu.edu. phone: +(979) 845-6599. fax: +(979) 845-4491.
Corresponding

We say that a mesh M is piecewise linear if every edge of M is a straight line segment, and every face of M is planar. Piecewise linear meshes are useful since the surface of each face is well-dened [Williams 1972]. Most common piecewise linear meshes are triangular meshes. However, piecewise linear meshes are a signicant generalization of triangular meshes, which not only allow nontriangular faces, but also allow faces to have different face valence. In the discussion of the current paper, we will be focused on piecewise linear meshes. We start by some intuitions. Let M be a piecewise linear mesh such that all vertices of M have the same vertex valence m and all faces of M have the same face valence n (such a mesh is called a regular mesh). Suppose that M has v vertices, e edges, and f faces. By Euler Equation [Hoffmann 1989; Mantyla 1988], v e + f = 2 2g (1)

where g is the genus of the mesh M and from the equalities nv = m f = 2e, we derive e= nm(2 2g) , 2n + 2m nm v= 2n(2 2g) , 2n + 2m nm f= 2m(2 2g) 2n + 2m nm

We would like to generalize the above relations to piecewise linear meshes that are not regular. For this, we introduce the following denitions. Denition Let M be a piecewise linear mesh, with vertex set {1 , . . . , v } and face set {1 , . . . , f }. Moreover, for each i, 1 i v, let mi be the valence of the vertex i , and for each j, 1 j f , let n j be the valence of the face j . Then the average vertex valence m and the average face valence n are dened, respectively, to be m = ( mi )/v
i=1 v

and

n = ( n j )/ f
j=1

Note that m and n are not necessarily integers. Based on these new concepts, the number v of vertices, the number e of edges, and the number f of faces in a piecewise linear mesh can be given as functions in terms of the average vertex valence, the average face valence, and the genus of the mesh, as shown in the following lemma.

Lemma 2.1 Let M be a piecewise linear mesh. Suppose that M has v vertices, e edges, f faces, and genus g. Let m and n be the average vertex valence and average face valence, respectively, of the mesh M, then e= nm(2 2g) , 2n + 2m nm v= 2n(2 2g) , 2n + 2m nm f= 2m(2 2g) 2n + 2m nm

P ROOF. Suppose that the vertex set of M is {1 , . . . , v } and that the face set of M is {1 , . . . , f }. Moreover, suppose that for each i, 1 i v, the vertex i has valence mi , and that for each j, 1 j f , the face j has valence n j . Since each edge in the mesh M is used exactly twice in vertex valences and is used exactly twice in face boundaries, we have

i=1

mi = n j = 2e
j=1

On the other hand, by our denitions of the average vertex valence m and the average face valence n, we have mv =

i=1

mi

and

nf =

j=1

nj
Figure 1: Ilhan Komans Developable Sculptures.

Therefore, we still have mv = n f = 2e. Since the mesh M has genus g, Equation (1) holds. Combining Equation (1) and the equalities mv = n f = 2e, we get immediately e= nm(2 2g) , 2n + 2m nm v= 2n(2 2g) , 2n + 2m nm f= 2m(2 2g) 2n + 2m nm

(i ) = 0: then vertex i is planar. (i ) < 0: then vertex i is a saddle point. The actual values for (i ) 0 are not particularly useful, they simply tell how sharp is the convex or concave area. The upper limit for positive values is 2 and it corresponds to the sharpest convex or concave regions. For negative values there is no lower limit. In addition, the actual value of the number gives information about the type of saddle. Since there is no lower limit, saddle points can be very wild, as it can be seen from Ilhan Komans sculpture in Figure 2.

This proves the lemma.

2.2

Angle deection at a vertex

To understand the local behavior around a vertex of a piecewise linear meshes, angle deection are great tools. Angle deection at a vertex are formally dened based on the corner angles around a vertex, as follows. Denition Let i be a vertex on a piecewise linear mesh M. The angle deection at vertex i is dened as (i ) = 2 j
j=1 mi

where j is the internal angle of the j-th corner of vertex i and mi is the valence of the vertex i . The importance of angle deections to describe local behavior can be best understood by viewing developable sculptures [Koman 2005] of Sculptor Ilhan Koman. He created a set of sculptures by forcing the total angle in a given point larger than 2 [Koman 2005]. As shown in Figure 1, when the angle goes beyond 2, it is possible to create a wide variety of saddle shapes. We observe that Komans developable structures can give very useful information about the local behavior at a vertex for piecewise linear meshes. It is interesting to point out that the value of (i ) is somewhat related to curvature and based on the values of corner angles around the vertex i . More precisely, (i ) > 0: then vertex i is either convex or concave.

Figure 2: A close up view of Ilhan Komans highly complex Saddle Sculpture. This is not unexpected since the most popular discrete version of Gaussian curvature introduced by Calladine for triangular meshes uses angular deection [Calladine 1983]. Calladines discrete

Gaussian curvature given as Angular Deection Area Associated with Vertex

2.3

Sum of Angle Deections

Here, we will give a simple proof of discrete version of GaussBonnet theorem as Sum of angle deections (SAD), given as follows. Denition Let M be a piecewise linear mesh with a vertex set {1 , . . . , v }. The sum of angle deections (SAD) of the mesh M is dened as v (M) = (i )
i=1

Theorem 2.2 is independent of the number of vertices, the number of edges, the number of faces, and the average vertex and face valences. It depends only on the genus of the piecewise linear mesh M. As a result, any homeomorphic operation (operations that do not change topology, in this case genus) that converts a piecewise linear mesh to a new piecewise linear mesh does not change the SAD of the mesh. In other words, the effect of a homeomorphic operation on the SAD of a mesh will be zero, which means if we gain angle deections in some vertices, we will lose some angle deections in some other vertices. This is the important result for practical polygonal mesh modeling.

2.4

Visual Intuition

Note that the SAD of a piecewise linear mesh is closely related to the geometric shape of the mesh M. On the other hand, as we will prove in the following theorem, the SAD of a mesh is a topological invariant. Theorem 2.2 Let M be a piecewise linear mesh of genus g. Then the SAD (M) of the mesh M is equal to 2(2 2g). P ROOF. Let {1 , . . . , v }, {1 , . . . , e }, and {1 , . . . , f } be the vertex set, edge set, and face set of the mesh M, respectively. Moreover, for each i, 1 i v, let mi be the valence of the vertex i , and for each j, 1 j f , let n j be the valence of the face j . Let m and n be the average vertex valence and the average face valence, respectively, of the mesh M. Consider each face j of valence n j . Since j is a planar polygon, the sum ( j ) of inner angles of j is equal to (n j 2). Adding this up over all faces in the mesh M, we obtain

To give a visual intuition about sum of angle deections, we can relate it to critical points in Morse theory [Milnor 1963]. Consider the 3-D objects in Figure 3. The rst two objects have genus g = 0, the next two objects have genus g = 1, while the last object has genus g = 2. If we assign +1 to each minima/maxima (convex/concave) type critical point and 1 to each saddle type of critical point (as marked in the gure), the total adds up to (2 2g), as shown in Figure 3.

j=1

( j ) = (n j 2) = n j 2 f
j=1 j=1

= n f 2 f (2) Figure 3: The total adds up to (22g) if we assign minima/maxima points +1 and saddles 1. Figure 3 also give a visual explanation of the sum of angle deections. In gure, we assume that all angle deections occur only at critical points. If that were really the case, the angle deection in each critical point would have been +2 for minima/maxima and 2 for each saddle point. So, the total will be equal to 2(2 2g), which is the sum of angle deections. It is also clear from Figure 3 why branches do not change the total angle deections. Each branch induces the same numbers of saddle points and maxima/minima points; so total effect becomes zero. On the other hand, each handle (i.e., each hole) introduces two saddle type critical points, which decreases the total angle deections by 4.

where we have used the denition of the average face valence n = f ( j=1 n j )/ f . On the other hand, by the denition of angle deections, the sum of corner angles around each vertex i of the mesh M is equal to 2 (i ). Adding this up over all vertices in the mesh M, we get (2 (i )) = 2v (M)
v

i=1

This value should be equal to the value in (2) since both of them are the sum of the total corner angles in the mesh M. Therefore, we get (M) = 2v n f + 2 f = 2(v n f /2 + f ) By the denition of the average face valence n = ( j=1 n j )/ f , and noticing that 2e = j=1 n j , we get immediately n f /2 = e. This gives (M) = 2(v e + f ) By Euler Equation (1), we get (M) = 2(2 2g) This proves the theorem.
f f

Homogenous Operations

For branch creations, professional modelers usually use extrusion [Landreneau et al. 2005] and wrinkle operations (see Section 4). These operations are homogenous, i.e. they do not change mesh topology. Subdivision schemes, which are commonly used to create smooth surfaces, are also homogenous operations.

To understand why homogenous operations do not change the total angle deections, it is insightful to look at them from a mesh topological point of view. Let us assume that the number of faces, edges and vertices of a mesh increase in each application of homogenous operations. Based on this assumption, let us consider the practice in which when homogenous operations are applied to a mesh while the genus of the mesh stays the same, the numbers of faces, edges and vertices of the mesh increase without a limit. Remark 1. This is not an unrealistic assumption. In fact, all subdivision schemes, extrusions and wrinkle operations increase the number of faces, edges and vertices. To analyze repeated applications of homogenous operations we can again use the Euler equation. Let us consider specically meshes of genus g. Let n and m be the average face valence and the average vertex valence of a mesh of genus 1. Using Euler equation (1) and equations in Lemma 2.1, we have 2 2g 2 2 = + 1 e m n By our assumption e can be arbitrarily large but the mesh genus stays the same, thus 2 2 + 1 0 m n which gives m 2n n2

Implications on Practical Modeling with Homogenous Operations

Our results are particularly insightful for modeling better mesh structures for surfaces that include branches. We do not create branches only for modeling trees. Branches are important for modeling and they are everywhere. Even a simple genus-0 human face model must include branches such as eye sockets, nose and mouth. Remark 3 With better mesh structures, we mean faces are convex and as regular as possible. It is not always possible to make faces regular. For instance, we cannot get an angle deection larger than with regular convex faces. However, it is still possible to make faces as regular as possible by using appropriate valence. For instance, if we force the regular mesh structures such as (4, 4), we cannot avoid irregular faces. By introducing saddle and minima/maxima type of critical points we can obtain better mesh structure. In practice, that is what professional modelers do very efciently. Based on our results, it is easy to introduce saddles and minima/maxima. If we use the same type of faces, assuming that all the faces are almost regular, all we have to do is to carefully control the valences of vertices. For instance, if we work only with triangles, we have to choose 3, 4 and 5 valent vertices in places we want to obtain minima or maxima. For saddle points, we have to choose valences of vertices larger than 6. Based on how complicated we want to design a saddle point, we can increase the valence. Changing the valence can even improve the mesh structure of genus-1 surfaces. The Figure 4 shows an example of mesh improvement by decreasing and increasing valence in appropriate regions.

Under the assumption that m 3 and n 3, and replacing the above approximation by an equality, we will get 3n6 This result says that the average face valence cannot exceed 6 regardless of what we do (if we do not allow valent-2 vertices and polygons with two sides). In other words, if our homogenous operations create only quadrilateral faces (i.e., n = 4), then the average vertex valence m goes to 4. If the homogenous operations create only triangles (i.e., n = 3), then the average vertex valence m goes to 6. For pentagons (i.e., n = 5), the average vertex valence approaches to 10/3 and for hexagons (i.e., n = 6) it goes to 3. Any mixed use of different face types will create a rational number for the average vertex valence. This also explain why most subdivision schemes provide (3, 6) [Kobbelt 2000; Loop 1987], (4, 4) [Doo and Sabin 1978; Catmull and Clark 1978; Peters and Reif 1997; Sabin 2000] and (6, 3) [Claes et al. 2002; Oswald and Schr der 2003; Akleman and Srinivasan o November 2002] regular regions in which integer tuple (n, m) sat2 isfy the equation m + 2 1 = 0. Note that in these subdivisions the n number of regular vertices and faces (i.e vertices with valence m and faces with valence n) increases, while the number of extraordinary vertices and faces stays the same in each iteration. As a result, the regular regions dominate the mesh. Remark 2. To guarantee that subdivided mesh is at least G1 continuous each face of subdivided mesh must approach a convex planar surface. So, we can say that most subdivision surfaces consist of piecewise linear approximations of curved faces. Piecewise linear approximations usually are (3, 6), (4, 4) or (6, 3) regular regions for most subdivision schemes [Akleman et al. 2004].

Top part is a Regular (4,4) Structure

A Non-Regular Structure

Another Non-Regular Structure

Figure 4: This example shows that introducing non-regular structures can improve the mesh structure even for a simple genus-1 surface. See the thin quadrilaterals exists in regular (4, 4) structure on the left model. By increasing the valence of some vertices in saddle region and decreasing the valence of some vertices in convex region, release the tension and quadrilaterals look more regular.

For professional modeling quadrilateral modeling is a particularly important. In quadrilateral modeling, for minima and maxima, we have only one choice, 3 valence vertices. For saddles we can use any valence higher than 4. Extrusions and wrinkle operations as shown in Figures 5 and 6 introduce minima/maxima and saddle points simultaneously and therefore, they are commonly by professional modelers used to create branches.

Initial mesh

Wrinkle Operation and Vertex Valences

Initial mesh

Extrusion Operation and Vertex Valences

Figure 5: Branch creation with extrusion operation. Before extrusion we have a quadrilateral with 4-valent vertices. After extrusion 4 vertices have 5 valence and another 4 vertices have 3 valence. Average vertex valence added is 4.

Subdivided by Catmull-Clark

One more iteration of Catmull-Clark

Conclusions and Future Work

In this paper, we have introduced an approach to improve mesh structures to use in practical modeling with homogenous operations. We show that vertex angle deection can give a powerful insight about local geometric behavior to professional modelers. Based on a discrete version of Gauss-Bonnet theorem, we have shown that it is be possible to improve the organization of mesh structures of shapes according to their geometric structure. Based on the results in this paper, it is possible to automatically create a better mesh from a given mesh. We think that vertex angle deections can also be used to smooth the surfaces. Despite the similarity, angle deections are different than Gaussian curvature and its discrete versions. For instance, unlike sum of angle deections, sum of discrete Gaussian Curvature may not be equal to 2(2 2g). Both Gaussian curvature and angle deections are rotation and translation invariant. However, Angle deection is also scale invariant which can make it useful for shape retrieval. An unexpected result coming from vertex angle deection is paper folding. Since we know that the total angle will always stay constant, we can shape papers simply using staples1 . Using this insight, we were able to shape papers intuitively. And we were able to create a variety of paper sculptures. Figure 7 shows two examples of paper sculptures we have created based on the insight coming from our result.

Figure 6: Branch creation with wrinkle operation. After wrinkle operation, 4 vertices have 4 valence, 2 vertices have valence 3 and another 2 vertices have 5 valence. So, added average vertex valence is 4. Subdivided version shows how an eye or wrinkle is automatically created with this operation.

national Symposium on Computer and Information Sciences, vol. 17, 137141. A KLEMAN , E., S RINIVASAN , V., M ELEK , Z., AND E DMUND SON , P. 2004. Semi-regular pentagonal subdivision. In Proceedings of the International Conference on Shape Modeling and Applications, 110118. C ALLADINE , C. R. 1983. Theory of Shell Structures. Cambridge University Press, Cambridge. C ATMULL , E., AND C LARK , J. 1978. Recursively generated bspline surfaces on arbitrary topological meshes. Computer Aided Design, 10, 350355. C LAES , J., B EETS , K., AND R EETH , F. V. 2002. A corner-cutting scheme for hexagonal subdivision surfaces. In Proceedings of Shape Modeling International2002, Banff, Canada, 1317. D OO , D., AND S ABIN , M. 1978. Behavior of recursive subdivision surfaces near extraordinary points. Computer Aided Design, 10, 356360. DYN , N., L EVIN , D., AND S IMOENS , J. 2002. Face-value subdivision schemes on triangulations by repeated averaging. In Curve and Surface Fitting: Saint-Malo 2002, 129138. F ERGUSON , H., ROCKWOOD , A., AND C OX , J. 1992. Topological design of sculptured surfaces. In Proceedings of SIGGRAPH 1992, ACM Press / ACM SIGGRAPH, Computer Graphics Proceedings, Annual Conference Series, ACM, 149156. F OMENKO , A. T., AND K UNII , T. L. 1997. Topological Modeling for Visualization. Springer-Verlag, New York.

References
A KLEMAN , E., AND S RINIVASAN , V. November 2002. Honeycomb subdivision. In Proceedings of ISCIS02, 17th Inter1 Since papers are developable surfaces, we can think that papers are piecewise linear meshes that consist of thin stripes of planes. So our theorem applies to papers.

TAKAHASHI , S., S HINAGAWA , Y., AND K UNII , T. L. 1997. A feature-based approach for smooth surfaces. In Proceedings of Fourth Symposium on Solid Modeling, 97110. W EISSTEIN , E. W. 2005. Gauss-Bonnet Formula. From MathWorldA Wolfram Web Resource. http://mathworld.wolfram.com/Gauss-BonnetFormula.html. W ELCH , W., AND W ITKIN , A. 1994. Free-form shape design using triangulated surfaces. In Proceedings of SIGGRAPH 1994, ACM Press / ACM SIGGRAPH, Computer Graphics Proceedings, Annual Conference Series, ACM, 247256. W ILLIAMS , R. 1972. The Geometrical Foundation of Natural Structures. Dover Publications, Inc. Z ORIN , D., AND P. S CHR ODER , E ., 2000. Subdivision for modeling and animation,. ACM SIGGRAPH 2000 Course #23 Notes, July. Figure 7: Paper sculptures. Cat mask is created from a 8.5 11 paper that is cut into one square and one rectangular pieces. These pieces are later stapled together to create the cat mask. Swan is created from a shaped and folded paper using only three staples. Z ORIN , D., AND S CHR ODER , P., 2002. A unied framework for primal/dual quadrilateral subdivision schemes. Computer Aided Geometric Design, CAGD.

G ROSS , J. L., AND T UCKER , T. W. 1987. Topological Graph Theory. John Wiley & Sons, New York. H OFFMANN , C. M. 1989. Geometric & Solid Modeling, An Introduction. Morgan Kaufman Publishers, Inc., San Mateo, Ca. KOBBELT, L. 2000. 3-subdivision. In Proceedings of SIGGRAPH 2000, ACM Press / ACM SIGGRAPH, Computer Graphics Proceedings, Annual Conference Series, ACM, 103 112. KOMAN , F. 2005. Ilhan Koman - Retrospective. Yapi ve Kredi Kulture Sanat yayincilik, Beyoglu, Istanbul, Turkey. L ANDRENEAU , E., A KLEMAN , E., AND S RINIVASAN , V. 2005. Local mesh operations, extrusions revisited. In Proceedings of the International Conference on Shape Modeling and Applications, 351 356. L OOP, C. 1987. Smooth Subdivision Surfaces Based on Triangles. Masters thesis, University of Utah. M ANTYLA , M. 1988. An Introduction to Solid Modeling. Computer Science Press, Rockville, Ma. M ILNOR , J. 1963. Morse Theory. Princeton University Press. O SWALD , P., AND S CHR ODER , P., 2003. Composite primal/dual 3-subdivision schemes. Computer Aided Geometric Design, CAGD. P ETERS , J., AND R EIF, U. 1997. The simplest subdivision scheme for smoothing polyhedra. ACM Transactions on Graphics 16, 4, 420431. P RAUTZSCH , H., AND B OEHM , W., 2000. Chapter: Box splines. The Hanbook of Computer Aided Geometric Design. S ABIN , M., 2000. Subdivision: Tutorial notes. Shape Modeling International 2001, Tutorial, May. S RINIVASAN , V., AND A KLEMAN , E. 2004. Connected and manifold sierpinski polyhedra. In Proceedings of Solid Modeling and Applications, 261266.