Automatic Knotclouds Placement Algorithm for Quadratic DMS-spline Function

Tento článek se zabývá algoritmem přidělování přídavných bodů pro kvadratickou DMS-splajnovou funkci s ohledem na splnění podmínek normality. Řešení tohoto problému je předpokladem pro použití této funkce v modelově orientované videokompresi.

---

Automatic Knotclouds Placement Algorithm for Quadratic DMS-spline Function

This article deals with automatic knotclouds placement algorithm for quadratic DMS-spline function with regard to fulfillment of condition of normality. Solving this problem is a prerequisite for using this function in a model-based video cooding.

Keywords: Quadratic DMS-spline function; Surface approximation; Human head model; Automatic knotclouds placement.

---

Introduction

In computer graphics, a crucial aspect is to create the 3D scene using the smallest number of polygons, while maintaining a realistic scene. A small number of polygons is necessary because it allows for faster transmission of the given scene, more precisely with low bit rate. However, the objects represented by a small number of polygons seem to be discontinuous (unrealistic). This disadvantage of discontinuity can be well-compensated for by the approximation of polygonal surfaces (smoothing) by employing various approximation methods. One of these methods is the DMS-spline function.

The following figure (Fig. 1) shows an example of an approximated surface using the quadratic DMS-spline function.

Figure 1: Example of quadratic DMS-surface.

Surfaces in computer graphics

In geometric modelling surfaces are often represented by a set of n functions N_i: R² → R with 0 ≤ i < n and corresponding control point c_i ∈ R³ [1], [2], [3], [4]. Also a domain Ω ⊂ R² is defined. A point on the surface corresponding to a point c_i ∈ Ω is then defined as:

(1)

Some desired properties of these surfaces are:

• affine invariance: if all control points are affinely transformed by a matrix M and vector v the resulting surface should be the original surface transformed by the same matrix M and vector v formally:

(2)

for all x ∈ Ω, which is true if for all x ∈ Ω.

• convex hull property: all points on the surface lie within the convex hull of the control points. This property is convenient for rendering and estimating a bounding box.
  This property can be obtained by establishing:

(3)

for all x ∈ Ω.

• local control: one control point only influences a part of the surface, hence N_i(x)=0 for all x ∈ Ω \ Γ_i where Γ_i is the area of influence of control point i with 0 ≤ i < n.

• continuity: the surface should not contain any "cracks" hence if x ∈ Ω and x + εd ∈ Ω for all ε with 0 < ε ≤ γ for some γ then lim_ε→0 F (x + ε d) − F (x) = 0.

Several surface classes (dependent on the choice of the blending functions N_i are used in com-puter graphics. Many of those are defined piecewise, i.e. the surface is constructed by defining smaller parts of the surface, called patches, each defined over a part of the domain which are then put together to form the total surface. The patches typically have rectangular or triangular domains. Triangular domains are sometimes preferred because they allow modelling surfaces with arbitrary polygonal domain (very polygon can be triangulated, but not all polygons can be build with rectangular domains).
In most cases the patches are defined over mutually exclusive domains and therefore cannot guarantee continuity along the patch boundaries in general. For triangular Bézier patches for instance the continuity has to be established by assuring that certain control points of adjacent patches are equal. If one wants to have a smooth connection between the patches (C¹ continuous) one also has to place certain triples of control points at regular distance along one line.

DMS-spline function

DMS-splines were developed and first published in 1992 by W. Dahmen, C. A. Micchelim and H. P. Seidel; The name DMS is derived from the initials of their surnames [2], [5], [6], [7], [8], [9]. DMS-splines are functions that combine global smoothness of linear splines with the possibility of local control, thus the pleasant features of B-patches. DMS-splines are due to the complexity of their definition unattractive to conventional modelling. However, global smoothness makes them suitable for variable modelling because we do not achieve by adding restrictions to the location of control points. DMS-spline surface is like many other surfaces a weighted sum of control points. The weight of control points is given by blending function. DMS-splines as weighted functions use triangular spline functions. For DMS-spline surface of degree ν_i, each control point is weighted by triangular spline degree n and by multiplication constant. In order to define DMS-spline the domain triangular spline and other parameters need to define as well:

• The domain of a DMS-spline surface is proper triangulation I ⊂R². The triangulation is called proper if it consists of a set of non-degenerate triangles which are connected and any two triangles in the triangulation are either disjoint, share a vertex or an edge.
• In every vertex νi of the triangulation a list of n + 1 knots is defined, denoted as {t_i0, ... , t_in} with t_i0 = t_i. This set of vertices is called a knotclouds of i^th vertex t_i. We will need these knotclouds to define the knotsets of the simplex splines. The knotcloud is considered to be a list (hence is ordered), but denoted as a set. This is done, because we also use intersections and unions on these lists, in which case we consider the knotcloud as if it were a set. The elements however are always considered in a fixed order during the computations.
• For a degree n surface we have to define for each triangle I of triangulation I a set of control points in R³. We denote those control points as c^I_β where β is a triple β (β₀, β₀, β₀) with |β| = β₀ + β₀ + β₀ = n. There are exactly (n+1)(n+2)/2 such β_j, as is usual for degree n surfaces (Bézier patches for instance have the same amount of control points). The bigger value of β_j the closer the control point c^I_β is drawn to vertex t_ij of triangle I = {t₀, t₁, t₂}. Of course this geographical placement has no real semantics: the control points can be placed anywhere within R³, they do not lay in the plane R². The location however indicates where the biggest influence of the control point on the surface will be.

After we have provided these parameters, we can define a DMS-spline surface. Each control point c^I_β is weighted by a simplex spline. The knotset of this simplex spline will contain n + 3 knots, hence the simplex spline will have degree n. The knotset of the simplex spline to weight c^I_β consists of a union of pre fixes of knotclouds defined in the vertices of the triangle I. The closer c^I_β lays to a vertex t_j of I, the more knots are taken from the corresponding knotcloud. Formally we have as definition

. The simplex spline M(.|V^I_β ) times a constant is then used as blending function for control point c^I_β. Let the set M(u|V^I_β) be a triangle that consists of the last knots of the heads of the knotclouds of which consists, hence . The constant is then defined as . This constant is necessary to obtain affine invariance of the surface. The point on a surface, corresponding to a point u in the domain can now be expressed as:

(4)

To guarantee affine invariance and the convex-hull property of DMS-splines we have to show that

. To guarantee affine invariance and the convex-hull property for surfaces requires more restrictions on the knot-placement than for infinite surface which is describing in next sections. A triangle I∈I may have non-zero influence (Fig. 2) outside the half open convex hull of the triangle I. This is a fundamental difference with usual surface constructions like B-patches. This interference of triangles triangulation ensures global DMS-spline functions smoothness.

Figure 2: A single triangle I ∈I with its supports (green).

Evaluation of Quadratic DMS-spline Function

Quadratic DMS-spline functions have degree n = 2. The weights of control points, which depend on the evaluation point u, use quadratic triangular spline functions. In the non-generalized case of quadratic DMS-spline function, control points are a scalar value (r-coordinate).

Quadratic DMS-spline Element

Quadratic DMS-spline element is defined as contribution of one triangle (t₀₀, t₁₀, t₂₀) of triangulation I to final DMS-spline function. Support of this element is a dedicated set of points V = {t₀₀, t₀₁, t₀₂, t₁₀, t₁₁, t₁₂, t₂₀, t₂₀, t₂₂}. (See Fig. 2)

Quadratic DMS-spline element is defined as:

(5)

where M(u|V^I_β) are quadratic spline function, c^I_β are control points and are the normalized quadratic simplex spline. Sets, which are defined over each triangular splines, are listed in Tab. 1.

Table 1: Definition of quadratic triangular spline sets.

Number of quadratic triangular splines and number of control points is (n+1)(n+2)/2 = (2+1)(2+2)/2 = 6, from which 3 are placed near the vertices of triangle I after their orthographic projection to the plane (h, v). Control point, placed on vertex of the triangle, is called vertex control point and the one placed on the edge is called side control point. Figure 2 illustrates support of the triangle I interference to other triangles in the triangulation I at given vertex and knotclouds position.

Quadratic DMS-spline Function

The final DMS quadratic spline function over the triangulation I is formed by contribution of quadratic DMS-spline elements. Support of this function is determined as conjunction support of particular elements. Each vertex t_i0 of triangulation I has two knotcloud points t_i1 and t_i2 assigned. If two or more triangles have common vertex then they also have common knotclouds. Number of control points c^I_β is defined as I-multiple of control points for single quadratic DMS element; ((n+1)(n+2)/2)I = ((2+1)(2+2)/2)I = 6I. And also, if two or more triangles have common vertex or edge then their control points have the same value. Final non-generalized DMS-spline function is defined as:

(6)

If the point u at which we calculate the function, will be located in two or more supports of triangular spline, then at that point contributions of individual elements add together. This interference leads to global smoothness of DMS-spline function at whole triangulation without additional limitations of control point's positions (while complying with conditions of normality for knots placement).

Quadratic DMS-surface over Arbitrary Triangulation

Calculation of DMS-surface is based on generalizations of DMS-spline function. When calculating the quadratic DMS-spline functions, only r-coordinates of control points weighted by corresponding triangular splines are used. On the other hand, when calculating DMS-surface, this function is divided to three separate components and h-,v- and r- are weighted separate. In this case control points lay in R³. The result of DMS-function calculation in u is point of DMS-surface defined by its three coordinates. Quadratic DMS-surface is then defined as:

(7)

where F(u) is point of DMS-surface, is u a point, where we are compute quadratic DMS-surface and c^I_β are control points of triangle I. Calculations of the components of the surface coordinates are given by:

(8)

Condition of Normality

Condition of normality is valid over whole triangulation I only for some allocations of knots. Knots must comply with following conditions:
Conditions of normality for all vertices
General conditions for all knotclouds (Fig. 3):

• Knots may not lay on a line determined by any on an edges of the triangles, where vertex t_i0 is one of the triangle vertices. (Fig. 3, case A and B)
• Knots may not lay collinear with one of triangle's vertices where vertex t_i0 is one of the triangle vertices. (Fig. 3, case C)

Figure 3: Conditions of normality - general. (Non-accepted positions)

• Knot may not lay inside of another triangle, where vertex t_i0 is not one of the triangle vertices. (Fig. 3, case A)

Additional condition for vertex t_i0 inside of a triangulation (i.e. vertex t_i0 is not boundary vertex of triangulation):

• Knot may not lay in support of other triangles, where vertex t_i0 is not one of the triangle vertices. (Fig. 3, case B)

Figure 4: Conditions of normality - inside of triangulation. (No accepted positions)

• Knots must lay in green areas illustrated in the Fig. 5 except dotted lines.
  - Case A: Vertex t_i0 is vertex of two triangles.
  - Case B: Vertex t_i0 is vertex of more triangles and internal angle between boundary edges is less than 180^◦.
  - Case C: Vertex t_i0 is vertex of one triangle only.
  

Figure 5: Knotclouds placement for vertices t_i0 on a triangulation border.

Automatic Knotclouds Generation

This method is enhancement of the heuristic univariate Monte Carlo algorithm [10]. This method has one degree of freedom, i.e. the distance of knots from the vertex t_i0 which they belong to (with regard to additional conditions described herein before).

Knotclouds inside the triangulation

1. Find all triangle where vertex t_i0 is one of triangular vertices (Fig. 6).

Figure 6: All triangles where vertex t_i0 is one of its vertices. (red circles)

2. Determine two lines p₁ and p₂ passing trough vertex t_i0 and axes of the largest angle α₁ and the second largest α₂ of these triangles. (Fig. 7, A)

Figure 7: Knotclouds placement technique for vertex t_i0 inside the triangulation I.

3. Define lengths D₁ and D₂. Length D₁ as approximately one third of shorter edge length d₁ of triangle with the largest angle and with vertex t_i0 and length D₂ as approximately one third of shorter edge length d₁ of triangle with the second largest angle and with vertex t_i0. (Fig. 7, B)

4. Placement of knots t_i1 and t_i2 on line p₁, resp. p₂ in distance D₁, respectively D₂ rom vertex t_i0 inside of the triangle with the largest angle, respectively second largest angle. (Fig. 7, C)

5. Check if conditions of normality for knotclouds are met. If not, then reduce distance (in case, if knots extend to other triangles supports, where vertex t_i0 is one of triangle vertices), respectively change line p₁ (p₂) angle (in case, if knots are collinear with any vertex or one knot lay on the edge of a triangles). If after these steps, do not reached the conditions of normality over the whole triangulation, the triangulation is inconvenient and needs to control.

Next figure (Fig. 8) illustrates knotclouds t_i1 and t_i2 placement of vertex t_i0. (Note: Connection between these points is only illustrative for better orientation in triangulation scheme.)

Figure 8: Knotclouds placement for vertex t_i0 inside the triangulation I.

Knotclouds on the border of the triangulation (The vertex t_i0 lay on the border of triangulation)

1. Find all triangles where vertex t_i0 is one of triangle's vertices (Fig. 6). If there is only one triangle proceed to:
- Determine two lines p₁ and p₂ passing thought vertex t_i0 and divide internal angel α by vertex t_i0 to (1/3) α₁ and (2/3) α₂ (Fig. 9, A ). (Note: Order-independent)

Figure 9: Determine of lines p₁, p₂ and edges d₁, d₂ single triangle.

- Define lengths D₁ and D₂ Length D₁ as approximately one third of edge d₁ length of triangle with vertex t_i0 and closer to line p₁. Length D₂ as approximately one third of edge d₂ length of triangle with vertex t_i0 and closer to line p₂. (Fig. 9, A).
- Placement of knots t_i1 and t_i2 on line p₁, respectively p₂ in distance D₁, respectively. D₂ from vertex t_i0 outside of the triangle (outside of triangulation) (Fig. 9, B).
- Next, continue at step 5.

2. Determine external angle γ which contain triangles edges, where is t_i0 one of vertices (Fig. 10).

Figure 10: Determine of angle γ.

If external angle γ > 180° continue:
- Determine two lines p₁ and p₂ passing thought vertex t_i0 and divide external angel γ to (1/3) γ₁ and (2/3) γ₂ (Fig. 10, A). (Note: Order-independent)

Figure 11: Determine of lines p₁, p₂ and edges d₁, d₂ (multiple triangles, angle γ > 180°).

- Define lengths D₁ and D₂. Length D₁ as approximately one third of edge d₁ length of triangle with vertex t_i0 and closer to line p₁. Length D₂ as approximately one third of edge d₂ length of triangle with vertex t_i0 and closer to line p₂ (Fig. 10, B).
- Next, continue to step 5.

3. Determine two lines p₁ and p₂ passing thought vertex t_i0 and axes of the largest angle α₁ and second largest α₂ these triangles. (Fig. 12, A)

Figure 12: Determine of lines p₁, p₂ and edges d₁, d₂ (multiple triangles, angle γ < 180°).

4. Define lengths D₁ and D₂. Length D₁ as approximately one third of shorter edge d₁ length of triangle with vertex t_i0 and largest angles. Length D₁ as approximately one third of shorter edge d₁ length of triangle with vertex t_i0 and second largest angles. (Fig. 12, B)
5. Placement of knots t_i1 and t_i2 on line p₁, respectively p₂ in distance D₁, respectively D₂ from vertex t_i0 outside of the triangle (outside of triangulation) (Fig. 2.10, B).
6. Check if all the conditions of normality for knotclouds are met are satisfy. If not, then reduce distance (in case, if knots extend to other triangles supports, where vertex t_i0 is one of triangle vertices), respectively change line p₁ (p₂) angle (in case, if knots are collinear with any vertex or one knot lay on the edge of a triangles). If after these steps, conditions of normality are not fulfilled over the whole triangulation, the triangulation is faulty and needs to be corrected.

Next figure (Fig. 13) illustrates knotclouds t_i1 and t_i2 placement of vertex t_i0. (Note: Connection between these points is only illustrative for better orientation in triangulation scheme.)

Figure 13: Knotcloud placement for vertex t_i0 on the border the triangulation I.

Influence of Knotclouds Placement to Approximation Surface of Human Head

Knotclouds influence the approximated surface in particular triangulation triangles’ supports intersection, where vertex having these knotclouds assigned is one of vertices. The knotclouds have the greatest influence in the area of the vertex to which they are assigned. After meeting conditions of knotclouds placement described in section Condition of Normality the approximated surface can be formed. Influence of knotclouds placement of approximated surface is exemplified on displacement of knots ti1 and ti2 of vertex ti0 (Fig. 14) in the left eyebrow area of CANDIDE 3-1-6 model [11]. Figure (Fig. 15) shows knotclouds placement generated by the method described in section Automatic Knotclouds Generation and approximated DMS-surface.

Figure 14: Triangulation with knotclouds placement. A: initial position of knots; B: Detail A - placement of knots t_i1 and t_i2 of vertex.

Figure 15: Initial position of knotclouds and approximated surface: A: left eyebrow area; B, C: approximated surface - front view filled (unfilled)triangulation after second interpolation and first DMS approximation with lighting and with averaging of normal vectors of particularly triangles. D, E: Approximation surface - left view filled (unfilled) triangulation after second interpolation and first DMS approximation with lighting and with averaging of normal vectors of particularly triangles.

Following figures (Fig. 16) show described affects of placement knotclouds. - Type A: Triangulation a knotclouds placement t_i1 and t_i2 of vertex t_i0.
- Type B: Approximated surface - front view filled triangulation after second interpolation and first DMS approximation with lighting and with averaging of normal vectors of particular triangles.
- Type C: Approximated surface - front view unfilled triangulation after second interpolation and first DMS approximation.
- Type D: Approximated surface - left view filled triangulation after second interpolation and first DMS approximation with lighting and with averaging of normal vectors of particularly triangles.
- Type E: Approximated surface - front view unfilled triangulation after second interpolation and first DMS approximation.

Figure 16: Example of displacement of knotclouds.

The following figure (Fig. 17) shows incorrect placement knot t_i2 which interferes in support of triangle out of the area defined by triangles where vertex is one of vertices.

Figure 17: Example of incorrect knotclouds placement: A: left eyebrow area; B, C: approximated surface – front view filled (unfilled) triangulation after second interpolation and first DMS approximation with lighting and with averaging of normal vectors of particularly triangles. D, E: Approximation surface – left view filled (unfilled) triangulation after second interpolation and first DMS approximation with lighting and with averaging of normal vectors of particularly triangles.

Following figures (Fig. 18 and 19) show the example of using DMS-spline approximation with texture mapping. The CANDIDE 3-1-6 model used with texture of an attractive woman face, which is a research result at University of Regensburg [12] is shown in the folowing figures:

Figure 18: Process of approximation and texture mapping (front view). A: Basic triangulation; B: Control points mesh for quadratic DMS-surface; C: Approximated triangulation; D: Real human head texture mapped on a 3D model.

Figure 19: Process of approximation and texture mapping (left view). A: Basic triangulation; B: Control points mesh for quadratic DMS-surface; C: Approximated triangulation; D: Real human head texture mapped on a 3D model.

Summary and Conclusions

The main goal of this work was to propose an effective way of using the quadratic DMS-spline function to approximate surface area. The use of the quadratic DMS-spline function requires solving of automatic knotclouds and side control point placement. In this article I propose a solution for the problem of automatic knotclouds placement with regard to fulfillment of condition of normality over the whole triangulation. Furthermore, the article shows usage of DMS-spline function to approximate triangular mesh of CANDIDE 3-1-6 human head model. Proposed algorithm includes six steps which lead to the placement of knotclouds to the position to ensure normality of the whole triangulation with respect to surface smoothness.
Combination of global smoothness of linear splines and possibilities of local control of DMS-spline functions surface, seems to have good application in 3D model-based video coding. The possibility of local animation of human head surface model (CANDIDE 3-1-6 and/or M-4A) using FAP units (defined in MPEG-4) allows to apply DMS-spline approximation in model-based video coding. Furthermore, using DMS-spline functions improves the quality (more precisely approximation of real human head) and after enhancing local animation brings in addition flexibility and output video scenes increased computing speed.

Acknowledgments

This article has originated thanks to the support from the Ministry of Education, Youth and Sports of Czech Republic within the project MSM6840770014.

Bibliography

[1] Piegl L. and Tiller W. The NURBS Book. Springer-Verlag, 2nd edition, 1997.
[2] Dahmen W., Gasca M., and Micchelli Ch. A. Computation of curves and surfaces. Kluwer Academic Publisher, Netherlands, 1990.
[3] Žára J., Beneš B., Sochor J., and Felkel P. Moderní počítačová grafika. ISBN: 80-251-0454-0. Computer Press, a.s., 2nd edition, 2004.
[4] Dunn F. and Parberry I. 3D math primer for graphics and game development. Wordware Publishing, Inc, Los Rios Boulevard Plano, Texas, USA, 1st edition.
[5] Dahmen W. and Micchelli C. A. On the linear independence of multivariate B-splines, I. triangulations of simploids. SIAM Journal of Numerical Analysis, pages 993–1012, 1982.
[6] Dahmen W., Micchelli C. A., and Sedel H.-P. Blossoming begets B-spline bases built better by B-patches. Mathematics of Computation, 59:97–115, 1992.
[7] Fong P. and Seidel H.-P. An implementation of triangular B-spline surfaces over arbitrary triangulations. Computer Aided Geometric Design, 10:267–275, 1993.
[8] Greimer G. and Seidel P.-H. Modeling with triangular B-spline. Computer Graphics and Applications, IEEE, 1994.
[9] Feanssen M., Veltkamp R. C., and Wesselink W. Efficient evaluation of triangular B-spline surfaces. Computer Aided Geometric Design, 2000.
[10] Dahmen W., Gasca M., and Micchelli Ch. A. Multivariate splines: a new constructive approach. San Jose IBM. Research division, 1982.
[11] Rydfalk M. CANDIDE: A parameterized face. PhD thesis, University of Linkping, Sweden, 1978.
[12] Beautycheck - schonheit ist messbar!, 2007. http://www.beautycheck.de/, 07. 08. 2007. [on-line]