Volume Enclosed by Subdivision Surfaces

Figure:

• Doo-Sabin subdivision of the unit cube defines a surface that encloses a volume of 6241 / 9920.
• The tetrahedron with all edges of length 1 generates a Loop subdivision surface with volume 44192429513855101 / (6865302375425894400 * sqrt(2)).
• The unperturbed and perturbed control mesh define different Catmull-Clark subdivision surfaces that enclose identical volume.
• In the fourth example, the volume of the initial mesh contracts by a factor of 0.675473... to the volume enclosed by the Catmull-Clark subdivision surface.

Abstract: We present a framework to derive the coefficients of trilinear forms that compute the exact volume enclosed by subdivision surfaces. The coefficients depend only on the local mesh topology, such as the valence of a vertex, and the subdivision rules. The input to the trilinear form are the initial control points of the mesh.

Our framework allows us to explicitly state volume formulas for surfaces generated by the popular subdivision algorithms Doo-Sabin, Catmull-Clark, and Loop. The trilinear forms grow in complexity as the vertex valence increases. In practice, the explicit formulas are restricted to meshes with a certain maximum valence of a vertex.

The approach extends to higher order momentums such as the center of gravity, and the inertia of the volume enclosed by subdivision surfaces.

Volume Enclosed by Subdivision Surfaces *	volume_enclo....pdf	980 kB
Volume Enclosed by Subdivision Surfaces (on viXra.org)	viXra:1405.0012	link
On the Volume of Sets Bounded by Refinable Functions **	on_the_volume..pdf	690 kB
On the Volume of Sets Bounded by Refinable Functions ***	j.amc.2015.06.050	link

* latest version, modified last on June 7th, 2014
** preprint 2695 at the faculty of Mathematics, Technical University Darmstadt/Germany, posted November 19th, 2014
*** accepted for publication June 10th, 2015

The first author dedicates this work to the memory of Andrew Ladd, Nik Sperling, and Leif Dickmann. The first author was partially supported by personal savings accumulated during his visit to the Nanyang Technological University/Singapore as a visiting research scientist in 2012–2013. He'd like to thank everyone who worked to make this opportunity available to him.

Supplemental material:

Examples for Doo-Sabin, Midedge, Catmull-Clark, and Loop	viXra:1405.0246	link
Subdivision and Volume Implementation (Mathematica 9)	subdiv_volume.zip	2.4 MB
Alternating forms in numeric m-format (Matlab)	alt_Y.m.zip	360 kB

The most punctual member of the household - Rocky, the German shepherd -
viewed Totto-Chan's unusual behavior with suspicion, but after a good stretch,
he positioned himself close to her, expecting something to happen.
from Totto-Chan

Presentation about the formula in practice:

[Peters/Nasri 1997] formulate an intuitive, iterative approximation of the volume: At each iteration step the computational effort remains constant, while the value converges at an exponential rate. At the time, they require "regular submeshes to have a polynomial parametrization" in order to derive the exact volume form for regular facets. For instance, volumes defined by the Loop Butterfly-scheme were not covered by their approach. Our new derivation allows to waive this constraint. For the Butterfly-scheme we demonstrate the derivation in Example 7 of our preprint. The approximation method by Peters/Nasri can now be used for a more general class of schemes. (Thanks to Jörg Peters for pointing this out to me.)

The approach by Bernd Schwald in his diploma Thesis Exakte Volumenberechnung von durch Doo-Sabin-Flächen begrenzten Körpern submitted in Stuttgart, 1999 already yields the exact volume enclosed by Doo-Sabin limit surfaces. The method evaluates infinite sums over the spline rings using a computer algebra system. There are restrictions on the subdivision weights. Neither infinite sums or restrictions on the weights occur in our new solution method.

The main finding of our publication is that the volume enclosed by subdivision surfaces is a trilinear form in the control points.

The volume enclosed by the surface defined by subdivision of a closed, orientable mesh M is of the form

The surface is parameterized by a partition of facets. A facet f is typically a quad, or a triangle. The coefficients of the trilinear forms

are constant and only depend on the topology τ(f) of the facet f, for instance the valence of a non-regular vertex.

The coordinates in the neighborhood of facet f are enumerated as

and completely define the subdivision surface associated to facet f.

We show that the trilinear forms are not uniquely determined. The solution space is a 3-dimensional vector space for all three subdivision schemes that we investigate. If we demand additionally that the trilinear forms be alternating, there is a unique solution. The collection of alternating trilinear forms is available for download.

Defeat doesn't finish a man, quit does.
A man is not finished when he's defeated.
He's finished when he quits.
Richard M. Nixon

Volume formula for several subdivision schemes

Doo-Sabin

sum over all facets with 1-ring

For a Doo-Sabin mesh, the points are from the 4 faces adjacent to each vertex of the mesh. The midpoints of the 4 faces span a quad. Common topololgies are

The corresponding trilinear forms have dimensions 8x8x8, 9x9x9, ... . At the moment, we have calculated the trilinear forms for valences up to 12. Some solutions are only in numeric precision.

The contribution of each facet of a torus mesh to the global volume is color-coded.

Midedge

Two iterations of the Midedge subdivision by [Peters/Reif 1997] in the simplest-pure specification is equivalent to Doo-Sabin with modified weights: [2 1 0 ... 0 1]/4 for all valences. For instance, to contract a point in a triangle, the mask is [2 1 1]/4. To contract a point of a quad, the weights are [2 1 0 1]/4, etc.

The weights are rational. The alternating forms are established in symbolic form up to valence 12. Since the scheme is used only rarely in practice, the forms are available on request.

Catmull-Clark

sum over all facets with 1-ring

For a Catmull-Clark mesh the points are from the one-ring around a quad of the mesh. Common topololgies are

The corresponding trilinear forms have dimensions 14x14x14, 16x16x16, 18x18x18, ... . For valences up to 8, the straight forward approach is sufficient.

With the advanced formula presented in the preprint, we have calculated the trilinear forms for valences up to 16.

The mesh in the animation to the right is used as a showcase in our preprint. The initial control mesh consist of 4 unit cubes. The limit surface encloses an exact volume of

40180082442670051252900902177393516510211208965892170836569226629214212708997856639459
55070082910257403120169305663456114089964755513505550065666048314075696077889864924495
54641219821870336717316476247679551629672346929205592993625071348599372485886982248931
39701577318904153684167935446076618334003376802825747208498276611956468960741228369454
5858835385150366631268809254233132555169056767142562957502393768749712436004182071021 /
16046323710242313089909175392307959118108021410074742425376177351348347992382685285901
78569776586033890127193528209009943782818471786608583381312401834308895367788456365409
80388250356278333552494074499327159439890167562372988838107467187740355820288057315668
95736089226365074195187059803111007004229005368248251629007854376338913422782400877557
2142274115412160255773388520595334004563330096707755296887477615110463588476731392000

= 2.5040054761592054376437149098797625772569551310115694056260292100279...

For comparison, the approximation of the volume based on several rounds of subdivision, and evaluation of the volume of the piecewise linear surface is stated below:

3  ->  2.5205403043890737813...
4  ->  2.5081288596400819507...
5  ->  2.5050357452975922494...
6  ->  2.5042630141663386140...

The number of unique coefficients (up to sign) in the alternating form are approximately binomial(8+2v,3)/2. The divide by 2 is due to the mirror symmetry along the diagonal through the non-regular vertex of the facet.

The contribution of each quad of a torus mesh to the global volume is color-coded.

Loop

sum over all facets with 1-ring

For a Loop mesh the points are from the one-ring around a triangular facet. Common topologies are

The corresponding trilinear forms have dimensions 9x9x9, 10x10x10, ... . At the moment, we have calculated the trilinear forms for valences up to 12. Some solutions are only in numeric precision.

The contribution of each triangle of a torus mesh to the global volume is color-coded.

Future work

Applications

Possible applications of our new formula are

• the design of Doo-Sabin, Catmull-Clark, or Loop subdivision surfaces to enclose a specific volume,
• the deformation of these surfaces subject to volume preservation.

Other schemes

Our framework makes it possible to obtain the trilinear forms that compute the volume enclosed by surfaces defined by three other well-known subdivision schemes:

• The Butterfly algorithm by [Dyn et al. 1990] is an interpolatory subdivision scheme for triangular meshes. A facet is a triangle of the two-times subdivided initial mesh. The surface associated to a facet is determined by the control points in the two-ring of the triangle. For instance, a regular facet has m(f)=27 control points.
• [Levin/Levin 2003] and [Schaefer/Warren 2005] define subdivision schemes for mixed triangle/quad meshes. The facets are the quads and triangles of the two-times subdivided initial mesh. For triangular facets away from mixed topologies, the trilinear forms derived for Loop apply. For quad facets away from mixed topologies, the trilinear forms derived for Catmull-Clark apply. For facets adjacent or close to tri-quad interfaces, additional trilinear forms need to be computed. The surface associated to these facets is determined by control points from more than just the one-ring. Different tri-quad configurations around non-regular vertices need to be investigated. Facets adjacent or close to non-regular vertices also have support larger than the one-ring.
• The sqrt(3) scheme by [Kobbelt 1996] is a subdivision scheme for triangular meshes. Within two rounds of subdivision, 1 triangle is subdivided into 9 triangles. The information for this refinement is drawn from the 2-ring of the original triangular facet.

Crease edges with sharpness parameter

Catmull-Clark and Loop subdivision allow B-spline curve subdivision along edge cycles. These edges are called crease edges. When the crease edges are sharp, i.e. the crease rule depth is infinite, new trilinear forms need to be derived in order to compute the enclosed volume. The surface near the sharp crease edges typically depends on fewer control points than for regular Catmull-Clark patches. Consequently, the trilinear forms have fewer coefficients. We treat sharp creases for Catmull-Clark and Loop in the next section.

• A popular tool in surface modeling is the use of crease edges with a finite sharpness parameter. B-spline subdivision for curves applies along crease edges only until a certain depth. The company Pixar is using these edges frequently in their animations. The technique gives flexibility to the artist without increasing the polygon count.

Moments of higher degree

The extension of our framework to moments of higher degree d is straightforward. Instead of trilinear forms, we have (d+3)-multilinear forms. This means however, that the number of coefficients grows steep in the degree of the momentum. Here is an overview for the regular topologies:

Since these numbers put a preliminary end to our exploration in 3D, we fallback to the 2D case: subdivision of curves. We describe how to compute area, centroid, and inertia of the subset in the plane enclosed by a subdivision curve. The derivation and examples are published here.

The experience from the 2D case give us a new perspective on the moments in 3D. By accounting for symmetries in the tensor coefficients, we are able to obtain the forms for the surface case after all. The approach and results are summarized here.

I have always tried to live in an ivory tower,
but a tide of shit is beating at its walls,
threatening to undermine it.
Gustave Flaubert

Volume Enclosed by Subdivision Surfaces with Sharp Creases

Figure:

• Four unit cubes glued together with the three cycles as sharp creases define a Catmull-Clark subdivision surface that encloses a volume of 2.9615786... The exact value is a fraction with 1558 digits.
• The tetrahedron with all edges of length 1 and one triangle boundary as crease defines a Loop subdivision surface that encloses a volume of 9835279661079132863588159 / (228340616075693288629862400 sqrt(2))
• Our formula also applies to more complex meshes with creases.
• The volume of the torus control mesh contracts to that of the Loop surface by a factor of 0.836059...

Abstract: Subdivision surfaces with sharp creases are used in surface modeling and animation. The framework that derives the volume formula for classic surface subdivision also applies to the crease rules. After a general overview, we turn to the popular Catmull-Clark, and Loop algorithms with sharp creases. We enumerate common topology types of facets adjacent to a crease. We derive the trilinear forms that determine their contribution to the global volume. The mappings grow in complexity as the vertex valence increases. In practice, the explicit formulas are restricted to meshes with a certain maximum valence of a vertex.

Volume Enclosed by Subdivision Surfaces w/ Sharp Creases	volume_enclo....pdf	* 630 kB
Volume Enclosed by Subdivision Surfaces w/ Sharp Creases	viXra:1406.0060	link
Examples for Catmull-Clark, and Loop w/ Sharp Creases	viXra:1405.0324	link
Subdivision and Volume Implementation (Mathematica 9)	subdiv_volume.zip	2.4 MB

* last modified on June 15th, 2014

Presentation about the formula in practice:

Surface subdivision schemes are tuned to produce surfaces that appear smooth everywhere. Creases are a simple extension that provide the option to model sharp features in the surface. Across the crease, the surface normal is generally not continuous, as can be seen in the illustration above.

In Piecewise smooth surface reconstruction Hoppe et al., 1994, extend the Loop subdivision scheme to handle sharp creases. In Subdivision Surfaces in Character Animation DeRose et al., 1998, present refinement of creases in Catmull-Clark meshes. The concept is the same in both algorithms: Along an edge cycle of the mesh that is designated as crease, cubic B-spline subdivision rules for curves apply. In particular, control points that are not part of the crease cycle do not affect the refinement of the crease. In the limit, the crease is identical to a cubic B-spline curve.

An early use of sharp creases in subdivision surfaces was to model the fingernails of the character Geri in Pixar's 1997 short film Geri's game. From then on, subdivision with creases has been a tool in surface modeling, and frequently used in animations, as explained in the video by Autodesk.

Die Laster stritten, wer von ihnen
am eifrigsten gewesen sei,
dem Bösen auf der Welt zu dienen;
den Preis erhielt die Heuchelei.
Johann Wilhelm Ludwig Gleim

Volume formula for two popular subdivision schemes

The Catmull-Clark subdivision scheme was published in 1978. The Loop scheme was introduced 1987.

One round of cubic B-spline subdivision for curves consists of vertex repositioning, and mid-edge vertex insertion. The subdivision rules along crease edge cycles in a mesh are illustrated in the following.

When f is adjacent to a crease, we denote the topology type by a tuple n.m. The first number n is the valence of the non-regular vertex (that also belongs to the crease). The second number m enumerates different configurations of the crease. All topology types are illustrated graphically. The subdivision weights are integer fractions. That means we can establish the trilinear forms in exact, symbolical notation. However, as the valence of the non-regular crease vertex increases, the volume forms become more difficult to establish because of computer memory constraints.

Catmull-Clark

sum over all quad facets

For the reader's convenience, we calculate the trilinear forms for crease facets with valences up to 5.

Loop

sum over all triangular facets

For the reader's convenience, we calculate the trilinear forms for crease facets with valences up to 6.

A teacher affects eternity:
he can never tell where his influence stops.
Henry Adams

Future work

We have derived the alternating trilinear forms for facets adjacent to sharp creases that are required to compute the volume enclosed by the subdivision surface. The forms are available up to a certain valence of the non-regular vertex. In the future, trilinear forms for greater valences may be computed.

The discussion in our article is restricted to meshes with pairwise disjoint crease cycles. [Hoppe et al. 1994] incorporates two other possibilities:

• A dart vertex is at the start (and end) of a sharp crease that is non-cyclic. Ordinary surface subdivision rules apply at dart vertices.
• A corner vertex is where two, or more creases intersect. A corner vertex is interpolated.

The contribution to the volume by a facet adjacent to a dart, or corner vertex is determined by yet other trilinear forms. The forms depend on the valence of the vertex and require an enumeration alike the one carried out in the previous chapter.

The great recurring themes of human history,
the balance between cooperation and conflict.
Matt Ridley

The first author was traveling in Vietnam during the time of this project. Here are photos of hotel rooms with spacious desks to place a laptop on. At the time, he was not affiliated to any academic institution.

Personal note from Jan: I was surprised to find that one needs endorsement to post on arXiv. Also, arXiv has many different categories, and selecting the right category for this work seems the hardest feat of all. So, I decided that viXra suits me better.