Bounds on the Dimensions of Trivariate Spline Spaces
The Tables referenced below give the dimensions, and bounds on those
dimensions for various configurations, and a range of values of
r and d. The bounds can be computed with
the 3DMDS package. Three bounds are given. Details of these bounds
will be described elsewhere, but here is an outline.
- l.b. A lower bound obtained by counting domain points and
smoothness conditions while building the configuration by adding one
tetrahedron at a time, joining it at 1, 2, or 3 faces. The lower
bound may be less than the dimension of the polynomial space. In that
case of course it can be easily augmented by setting it to the
polynomial dimension. However, the smaller value is shown since this
is a better indication of the quality of the bounds. Lower bounds below the
polynomial dimension are marked in Gray.
- c.o.b. A complex upper bound obtained as follows: Pick a
plane P that is not parallel to any (interior) face of any of the
tetrahedra. Intersect each face with that plane and translate the
intersections (without changing their slopes) so that they contain the
origin. Pick another line L in P that is not parallel to any of the
given lines and that does not contain the origin. Compute the
intersections of L with the intersections. On the resulting line
analyze the univariate spline space obtained by associating a
univariate polynomial with each tetrahedra and making those
polynomials join smoothly across the points on L corresponding to the
interior faces of those tetrahedra. Use those dimensions of
univariate spaces to obtain the upper bound on the trivariate space.
- s.o.b. A simple upper bound obtained by counting
domain points and smoothness conditions when building the
triangulation.
In the tables, background colors indicate the following circumstances:
- Green (Green)
The spline space is actually polynomial.
- Yellow (Yellow)
The dimension is greater than the polynomial dimension.
- Red (Red)
The bound gives the true dimension.
- Gray (Gray)
The lower bound is lower than the polynomial dimension.
- Cyan (Cyan)
The upper bound overestimates the dimension but it is better than the
other upper bound.
- Light Blue (Light Blue)
Some of the domain points do not enter any smoothness conditions.
Tables are available for the following configurations:
- Two tetrahedra sharing a common face.
- a 3-orange , three tetrahedra sharing an interior edge.
- a split of a cube into six tetrahedra about a space
diagonal, an analog of the two dimensional type-I
triangulation.
- The 3D Clough-Tocher Split.
- The 3D Morgan-Scott split.
- The regular octahedron .
- The Worsey-Farin split. The CT split is applied to the overall
tetrahedron, and to each of its faces. This gives a Powell-Sabin type split of a Tetrahedron.
- The double Clough-Tocher Split. The CT split is applied to
the overall tetrahedron, and then to each of the four
subtetrahedra.
- An analog of the 2D type-II triangulation, a tessellation
of a cubic by 24 tetrahedra sharing an interior point. This is sometimes called a "type IV" split.
- A generic version of the Morgan-Scott split .
- A generic Octahedron.
- A generic version of the Worsey-Farin split.
- A generic version of the double Clough-Tocher split.
- A generic type IV split .
- A slight modification of Rudin's example . This is a configuration
consisting of 41 tetrahedra and 14 points. It is the simplest example
of an unshellable triangulation in the sense that no unshellable
triangulation with fewer tetrahedra exists. "unshellable" means that
the configuration cannot be built by adding one tetrahedron at a time,
maintaining at each stage a configuration. (Removing any one tetrahedron
from the configuration leaves a set of tetrahedra whose union is
homeomorphic to a ball.) For details see Mary E. Rudin, An unshellable
triangulation of a tetrahedron, Bulletin of the AMS, 64 (1958),
90--91. Many arguments concerning configurations are based on
shelling, and this example may serve as a counter example. Note
that the configuration has no interior points. In this example the
angle of one degree used by Rudin is replaced by an angle of
approximately 12 degrees. The angle can be increased up to 19 degrees
without some of the tetrahedra beginning to overlap.)
- The Morgan-Scott Face Split , a tetrahedron where each face
has been split by the symmetric Morgan-Scott Split and every vertex on
the boundary of the tetrahedron connected to the centroid. Meant for
Macro design.
- The same as before, with the Wang version of the Morgan-Scott
Split on the faces.
- The double Clough-Tocher Face Split , similar to the
previous splits and the Worsey-Farin Element, except that each face is
split by the double Clough-Tocher split. A macro control panel is
available for this split.
- An 8-cell . Following bivariate notions, a cell is a
configuration with one interior vertex such that all boundary
vertices are connected to the interior vertex by an edge. The are
two topologically different cells consisting of 8 tetrahedra. One is
the octahedron, and this is the other one.
- aligned Powell-Sabin . Two Worsey-Farin Splits next to each other
such that the two edges meeting at the centroid of the common face are
collinear. Note that V4-V8-V9 are collinear. V3-V4-V8 are also aligned.
- unaligned Powell-Sabin . A version of the previous
configuration. Two Worsey-Farin Splits next to each other such that
the two edges meeting at the centroid of the common face are not
collinear. V4-V8-V9 are collinear, but V3-V4-V8 are not.
- generic Powell-Sabin . A generic version of the previous
configuration. Two Worsey-Farin Splits next to each other such that
the two edges meeting at the centroid of the common face are not
collinear. V4-V8-V9 are not collinear.
- inverted . A partition of a tetrahedron into 11 subtetrahedra: 4 vertex tetrahedra, 6 edge tetrahedra, and one inverted tetrahedron.
- T60 A partition of a tetrahedron into 60
tetrahedra. A geometrically unconstrained C1 cubic macro
element can be built on this split.
- T504. A partition of a tetrahedron into 504
tetrahedra. A geometrically unconstrained C1 quadratic
macro element can be built on this split.
- symmetric Worsey-Piper . Each face of a tetrahedron is
split into 6 triangles, using the centroid of the face, and the
midpoints of the edges. Thus the Powell-Sabin 6-split is applied to
each face. The tetrahedron is then split into 24 subtetrahedra all
sharing the barycenter of the tetrahedron.
- generic Worsey-Piper . A less symmetric version of the
previous split. The union of the 24 tetrahedra is still a
tetrahedron, but the split points are no longer in the centers of the
edges, faces, and the overall tetrahedron.
- symmetric MS cone . The planar Morgan-Scott split coned to three dimensions.
Thus the spline space decouples into d+1 bivariate spline spaces. This configuration can be used
to illustrate the fact that in order to obtain the dimension in three variables for any sufficiently large value
of d one has to get the dimension of bivariate spaces for all values of d.
- generic MS cone . A similar configuration built on the generic planar Morgan-Scott split.
The columns in the tables contain the following information:
- r is the degree of smoothness. (No supersplines are illustrated at present.)
- d is the polynomial degree.
- pol the dimension of the polynomial space, listed for reference and comparison.
- l.b. is the above mentioned lower bound.
- dim is the computed dimension.
- c.u.b. is the complex upper bound.
- s.u.b. is the simple upper bound.
- M is the initial number of equations.
- N is the initial number of unknowns.
- rank is the rank of the initial linear system.
- MDS is the number of active points (excluding those who do not enter any smoothness conditions at all) which need to be in a minimal determining set. This is also the number of rows in the reduced linear system.
- delta is the density of the reduced system, measured in percent.
- mods is the number of times a residual was computed in the generation of this particular line.