Volume Enclosed by Subdivision Surfaces

by Jan Hakenberg, Ulrich Reif, Scott Schaefer, Joe Warren published as viXra:1405.0012 – May 2nd, 2014

Figure:

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.

volumecentroidinertia
valence# of coefficients # unique ±,≠0solution # unique ±,≠0solution # unique ±,≠0solution
38^3=512 30symbolic 464symbolic 1598symbolic
49^3=729 13symbolic 135symbolic 378symbolic
510^3=100063symbolic?numeric
611^3=133187symbolic1709symbolic
712^3=1728?numeric?numeric
813^3=2197147symbolic?numeric
914^3=2744?numeric?numeric
1015^3=3375221symbolic
1116^3=4096?numeric
1217^3=4913313symbolic

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.

valence# of coefficients# unique ±,≠0solution
314^3=2744 186symbolic
416^3=409671symbolic
518^3=5832 416symbolic
620^3=8000 580symbolic
722^3=10648782symbolic
824^3=138241026symbolic
926^3=175761316symbolic
1028^3=219521656symbolic
1130^3=270002050symbolic
1232^3=327682502symbolic
1334^3=393043016symbolic
1436^3=466563596symbolic
1538^3=548724246symbolic
1640^3=640004970symbolic

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.

volumecentroid
valence# of coefficients # unique ±,≠0solution # unique ±,≠0solution
39^3=729 46symbolic 639symbolic
410^3=1000 64symbolic 1004symbolic
511^3=1331 88symbolic ?numeric
612^3=1728 43symbolic 735symbolic
713^3=2197 ?numeric ?numeric
814^3=2744 188symbolic ?numeric
915^3=3375?numeric
1016^3=4096?numeric
1117^3=4913?numeric
1218^3=5832?numeric

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

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:

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.

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:

schemecenter of gravity (d=1)inertia (d=2)
Doo-Sabin 9^4=6561 9^5=59049
Catmull-Clark 16^4=6553616^5=1048576
Loop 12^4=2073612^5=248832

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

by Jan Hakenberg, Ulrich Reif, Scott Schaefer, Joe Warren published as viXra:1406.0060 – June 10th, 2014

Figure:

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.

topology# of coefficients# unique ±,≠0solution
1.19^3=72945symbolic
2.112^3=1728102symbolic
3.115^3=3375232symbolic
3.214^3=2744359symbolic
4.117^3=4913660symbolic
4.216^3=4096555symbolic
5.119^3=6859492symbolic
5.219^3=6859949symbolic
5.318^3=5832811symbolic
 

Loop


sum over all triangular facets

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

volumecentroid
topology# of coefficients# unique ±,≠0solution # unique ±,≠0solution
1.18^3=512 31symbolic 387symbolic
1.26^3=21611symbolic 104symbolic
1.36^3=2166symbolic 40symbolic
2.18^3=51256symbolic 756symbolic
3.110^3=1000 64symbolic 1002symbolic
3.29^3=729 43symbolic 631symbolic
4.111^3=1331161symbolic 2928symbolic
4.210^3=1000120symbolic 1980symbolic
5.112^3=1728115symbolic
5.212^3=1728216symbolic
5.311^3=1331165symbolic
6.113^3=2197282symbolic
6.213^3=2197282symbolic
6.312^3=1728220symbolic
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:

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.