New Algorithm for Local Shape Preservation T-Spline Surface Skinning

Show more

1. Introduction

Skinning (or lofting) is a prevailing method in surface generation by passing through a series of curves, wherein the curves are called cross section curves [1]. This method is widely used in the design phase in industries such as ship building, auto production or aircraft manufacturing, for the benefit of precisely controlling of the surface profile. Based on the method of how to fit the cross section curves, the skinning can be classified into interpolation approach and approximation approach. In the existing NURBS based CAD systems, skinning is a basic function for the generative shape design for its flexibility and adaptivity in different situations as well as the ability of precisely representing a variety of shape features. The basic procedure in the skinning algorithm involves the unifying treatment of the cross section curves and the reverse computation of the surface’s control vertices, and the resulting surface is a tensor-product form NURBS surface [2].

With the emergence of T-Spline technology, which allows non-rectangular topology structure of the surface by introducing the T-junctions [3], superiorities over NURBS such as local refinement, watertight tessellation and more efficient data compression are obvious [4]. Thus the T-Spline is attractive for a substitution of the NURBS. By far T-Spline has been successfully used in the freestyle design software like Rhinocero, which makes full use of the free topology structure of T-Spline and offers much more freedom for the designer to exert their creativity. But in the engineering field where the precision and fidelity are emphasized, T-Spline modeling is still short of mature and complete algorithms. T-Spline skinning will be one of the corner-stones for such new modeling system, and researches on this topic have been unfolded in recent. A. Nasri raised a T-Spline skinning method capable of local refinement, in which intermediate section curves are inserted between cross section curves then the T-Spline topology mesh in parametric domain can be deduced from the knot vectors of both cross section curves and intermediate section curves [5]. By rearranging the coordinates of control vertices, the surface will satisfy the interpolation requirements. While if the neighboring cross section curves have too few common knot values, the intermediate section curves’ shape will differ from that of the cross section curves too much and wiggles then occur frequently. X. Yang et al. explored the T-Spline skinning on an approximation basis [6]. Y. Li et al. improved Nasri’s method and proposed the periodic T-Spline skinning method using a semi-NURBS form [7], in which more common knots of cross section curves can be obtained by knot insertion. Surface wiggles can thus be reduced for the improvement of the intermediate section curves. He also provided a 4-point interpolatory subdivision scheme to alleviate the surface wiggles and improve the surface smoothness. But the wiggle problem still can’t be excluded by these means. So M. Oh et al. offered a new way to generate the intermediate section curves. This method increases the number of intermediate curves, but by exploiting the error between the intermediate section curves and the surface, it can regulate the shape of the surface and obtain comparatively smooth T-Spline skinning surface [8]. This method can solve the wiggle problem in general cases with more computation tradeoff. In this paper, based on the method of M. Oh et al., a new T-Spline skinning algorithm is proposed with less computation cost.

The paper is structured as follows. In Section 2, preliminaries of T-Spline surface are reviewed. Section 3 is dedicated to the introduction of A. Nasri’s local T-Spline surface skinning with shape preservation method. Section 4 gives the thorough details of M. Oh’s method and introduces this paper’s main contribution for the improvement of this method. Section 5 is about the results and discussion of this paper’s main innovation.

2 Preliminaries of T-Spline Surface

T-Spline surface is a generalization of NURBS surface with the introduction of T-junctions. By the advantage of T-junctions, the surface is no longer limited to a topology as the tensor-product surface requires, so greatly increases the topology flexibility. In theory, one single T-Spline surface can represent any complex models. To define the T-Spline surface, a T-mesh is firstly used. By mapping this T-mesh into parameter domain, the pre-image of it can be obtained. The T-mesh in physical space and that in parameter domain contain the same topology information of the T-Spline, only in that the T-mesh in physical space contains the geometry information (i.e. the coordinates of control vertices). For convenience in the following the two T-meshes in different spaces will not be differentiated and will be called uniformly as T-mesh. The T-Spline surface’s description is as Equation (2.1).

$P(s,t)=\frac{{\displaystyle \underset{i=0}{\overset{n}{\sum}}{\phi}_{r,i}{V}_{r,i}{B}_{r,i}(s,t)}}{{\displaystyle \underset{i=0}{\overset{n}{\sum}}{\phi}_{r,i}{B}_{r,i}(s,t)}}$ (2.1)

In (2.1), each control vertex ${V}_{r,j}$ corresponds with a weight represented as ${\phi}_{r,j}$ and a blending function ${B}_{r,j}(s,t)$ . In this paper, all the weights are assumed to be 1. The definition for blending function ${B}_{r,j}(s,t)$ is:

${B}_{r,j}(s,t)={M}_{r}(s){N}_{j}(t)$ (2.2)

${M}_{r}(s)$ and ${N}_{j}(t)$ means cubic B-Spline basis functions derived from knot vector $[{s}_{r-2},{s}_{r-1},{s}_{r},{s}_{r+1},{s}_{r+2}]$ in horizontal direction and $[{t}_{j-2},{t}_{j-1},{t}_{j},{t}_{j+1},{t}_{j+2}]$ in vertical direction, respectively. The knot vectors can be computed from T-mesh. By knot insertion algorithm the T-Spline blending function can be refined and this procedure is called the local refinement of T-Spline.

3. Local T-Spline Surface Skinning

A. Nasri raised the local T-Spline surface skinning method [5], which is called local regulatable T-Spline skinning in this paper. Here the local regulatable means the skinning procedure can be solved in local areas, or for each cross section curve, the solution process only refers to the local area about this cross section. If this cross section curve is changed, there’s no need for a global regulation for the T-Spline skinning surface. Two typical phases comprise the local regulatable T-Spline skinning method: 1) the topological mesh generation phase; 2) the geometrical phase. In order to avoid configurations with fewer vertices, A. Nasri use the method of insert additional curve called intermediate section curve in the middle of the two cross section, the details of insert method and topological mesh generation phase can refer to [5]. The details of the geometrical phase are as the following.

Assuming $P(s,t)$ is the T-Spline surface that interpolates curve ${C}_{r}(t)$ , which is an iso-parametric curve on surface and corresponds with the horizontal knot value ${s}_{r}$ , then

$P({s}_{r},t)={C}_{r}(t)$ (3.1)

From the local support property of B-Spline curve, it’s obvious for cubic B-Spline curve that at a certain knot there are at most three basic functions whose value differs 0. As Figure 1 shows, at knot ${s}_{6}$ , only the three functions intersect with the dash line have values not equal 0, and a, b, care used to denote the values of these 3 functions. The local support property of B-Spline curve determines that only part of the curves on surface are referenced when regulating control vertices of one certain cross section curve, which is the source of local refinement.

So for cross section curve ${C}_{r}(t)$ , equation as (3.2) indicating the relationship of the curve and its equivalent position on the T-Spline surface can be deduced:

$\begin{array}{c}{C}_{r}(t)={\displaystyle \underset{j\in {I}_{r}}{\sum}{V}_{j}{\stackrel{^}{N}}_{j}}(t)=P({s}_{r},t)\\ ={\displaystyle \underset{j\in {I}_{rl}}{\sum}{X}_{r-1,j}{B}_{r-1,j}}(t)+{\displaystyle \underset{j\in {I}_{r}}{\sum}{W}_{r,j}{B}_{r,j}}(t)\text{+}{\displaystyle \underset{j\in {I}_{rl}}{\sum}{Y}_{r+1,j}{B}_{r+1,j}}(t)\\ =a{\displaystyle \underset{j\in {I}_{rl}}{\sum}{X}_{r-1,j}{N}_{j}^{rl}}(t)+b{\displaystyle \underset{j\in {I}_{r}}{\sum}{W}_{r,j}{N}_{j}}(t)\text{+}c{\displaystyle \underset{j\in {I}_{rl}}{\sum}{Y}_{r+1,j}{N}_{j}^{rr}}(t)\end{array}$ (3.2)

In (3.2), ${W}_{r,j}$ denotes the control vertices after regulation, ${I}_{r}$ , ${I}_{rr}$ denote the control vertices’ subscript index set of left intermediate section curve, cross section curve and right intermediate section curve. In this method, one prerequisite is ${I}_{rl}\subseteq {I}_{r}$ , ${I}_{rr}\subseteq {I}_{r}$ , which means the cross section curve ${C}_{r}(t)$ has more knots than both the left and right intermediate section curves, for this guarantees that the basic functions of these two intermediate section curves can be expressed as the linear combination of ${C}_{r}(t)$ ’s basis functions thus Equation (3.2) is solvable [5]. If the two intermediate section curves on the left and right have the same knot vector as the section curve, then the basic functions ${N}_{j}^{rl}(t)$ , ${N}_{j}^{rr}(t)$ and ${N}_{j}(t)$ are coincident, under which (3.3) can be simplified as a linear equation in (3.3):

${V}_{j}=a{X}_{j}+b{W}_{j}+c{Y}_{j}(j\in {I}_{r})$ (3.3)

For the situation that the intermediate section curves and the cross section curve have different knot vector, knot insertion in [6] can be used to express the ${N}_{j}^{rl}(t)$ and ${N}_{j}^{rr}(t)$ as the linear combination of ${N}_{j}(t)$ . Then Equation (3.4) can be given.

${V}_{j}=a{X}_{j}^{\text{'}}+b{W}_{j}^{\text{'}}+c{Y}_{j}^{\text{'}}(j\in {I}_{r})$ (3.4)

Here ${X}_{j}^{\text{'}}$ and ${Y}_{j}^{\text{'}}$ are the new control vertices of intermediate curves computed by knot insertion. By the solution of Equations (3.3) and (3.4), the surface’s new control vertices can be obtained which can define the T-Spline surface interpolating the given cross section curves.

Figure 1. Cubic B-Spline basis function.

Drawback of Local T-Spline Skinning

Obviously in the scheme given above that the intermediate section curves’ control vertices play an important role in T-Spline surface modeling. A. Nasri [5] gave a method to generate the intermediate section curves by cross section curves. But this method has its defects: usually the number of control vertices of the intermediate section curves is not enough to embody the surface’s shape feature between section curves, resulting in wiggles on the final surface, which are difficult to eliminate just by regulating the surface’s control vertices. As the case shown in Figure 2, dramatic wiggles appear on the skinning surface and the shape of the final surface is far from that of the designer’s expectation [8].

4. Shape Preservation Local T-Spline Surface Skinning

4.1. Key Points of Shape Preservation

Focus on the existing problem in the above method, M. Oh et al. raised local T-Spline skinning method capable of shape preservation [8]. The key points of this method rely in that for each cross section curve, add one more intermediate section curve on both its left and right. The knot vector of the intermediate section curves is the same as that of the cross section curve. In Figure 3 one example of the T-mesh capable of shape preservation is demonstrated. In this T-mesh, the blue knot vectors are those of cross section curves, and red ones are of intermediate section curves.

(a) (b)

Figure 2. Surface wiggles and the ideal skinning surface. (a) Surface wiggles; (b) The ideal skinning surface.

Figure 3. T-mesh example of the shape preservation T-Spline surface skinning.

The introduction of two intermediate section curves makes it easier to control the T-Spline surface’s shape around the cross section curve. The positions of intermediate section curves’ control vertices are still very important, and in this method they can be regulated locally to achieve the wanted smoothness of T-Spline skinning surface. Compared with A. Nasri’s work, this method is superior in the follows: 1) The shape of the T-Spline surface around cross section curves are easier to control. More knots mean more degrees of freedom, and more flexibility for surface morphing. 2) The surface can keep the shape of cross section curves effectively. The information of intermediate section curves reflects the shape variation tendency of the surface between two cross section curves. 3) Easy implementation of the control vertices’ regulation algorithms. For intermediate section curves exist on both the left and right of the cross section curve, and the knot vector of the intermediate section curve is the same as the cross section curve’s, only the linear equation as (3.3) is enough for the problem solving.

4.2. The Generation of Intermediate Section Curves and the Shape Keeping

How to generate the intermediate section curves is the most important mission in the local T-Spline surface skinning capable of shape preservation. M. Oh raised an intermediate section curve generation algorithm based on linear interpolation [8]. The main point of this algorithm can be illustrated in Figure 4. The first step is to calculate sample points on cross section curve in the direction of parameter t, i.e. calculate the coordinates of a series of points on cross section curve with given knots. The knots can be given evenly, and more sample points can be obtained with less knot interval. Then linearly interpolating these sample points in the direction of s parameter to calculate more points as the points on intermediate section curves. At last, fit these points to obtain the control vertices of the intermediate section curves.

On general occasions the above method can have satisfying results. But wiggles can also occur on some occasions, for the control vertices of intermediate section curves calculated by reverse algorithm may not reflect the coordinates of the cross section curves’ control vertices properly, thus the surface will be stretched for some degree in these areas and leads to wiggles.

Figure 4. Sample and linear interpolation process for fitting the intermediate curves.

As in Figure 4, considerate distances between ${V}_{r,j}$ and ${V}_{r,j}^{\text{'}}$ may appear and this will result in the situation in Figure 5, i.e. severe wiggles appear in surface’s locals. To alleviate this phenomenon, M. Oh raised an algorithm of iterative reverse calculation [8], which will compute the distance between surface and intermediate section curve and by regulating the control vertices’ coordinates to minimize the wiggles. This method can derive good results but when the wiggles are heavy the iteration and regulation will increase the computation work needed for surface skinning.

Aiming to further improve the above method, a new algorithm for shape preservation T-Spline skinning surface is proposed below, which simplifies the generation of intermediate section curves, and at the same time minimizes the wiggles. Usually no iteration and reverse computation work is needed and if on some occasions is in need, the workload is lighter compared with the existing method.

As in Figure 6, ${C}_{r}$ and ${C}_{r+1}$ are two cross section curves, of which the control vertices are denoted as ${V}_{r,i}(i=0,1,\mathrm{...},5)$ and ${V}_{r,j}(j=0,1,\mathrm{...},6)$ . In order to insert the left intermediate section curve ${I}_{r+1}^{1}$ (The green curve in the figure is intermediate section curve, wherein the superscript 1 denotes the left intermediate section curve and 2 denotes right one, the subscript r + 1 means that this intermediate section curve corresponds with the $(r+1)$ th cross section curve), sample points on curve ${C}_{r}$ are firstly computed, then these points are used to fit a curve, of which the number of control vertices are the same as that of the curve ${C}_{r+1}$ , and obtaining control vertices ${V}_{r,j}^{\text{'}}(j=0,1,\mathrm{...},6)$ . The intermediate section curve’s control points can be computed by the linear interpolation of ${V}_{r,j}^{\text{'}}$ and ${V}_{r+1,j}$ . At last, the knot vector of intermediate cure is required to be the same as that of ${C}_{r+1}$ , then the left intermediate section curve ${C}_{r+1}$ is achieved.

So the equation for determining the above intermediate curve’s control vertices is in (4.1), wherein ${V}_{r+1,j}^{1}$ denote the control vertices of ${I}_{r+1}^{1}$ , ${c}_{1}$ and ${c}_{2}$

are coefficients. ${c}_{1}=\frac{1}{3}$ and ${c}_{2}=\frac{2}{3}$ can be used for equidistance interpolation.

${V}_{r+1,j}^{1}={c}_{1}{V}_{r,j}^{\text{'}}+{c}_{2}{V}_{r+1,j}(j=0,1,\mathrm{...},6)$ (4.1)

(a) (b)

Figure 5. Surface wiggles of M. Oh’s method. (a) T-mesh in 3D space; (b) T-Spline skinning surface.

Figure 6. Insertion of intermediate section curve ${I}_{r+1}^{1}$ .

In the same way, Figure 7 demonstrates the process of inserting ${I}_{r}^{2}$ as ${C}_{r}$ ’s right intermediate curve. The first step is to compute the sample points on curve ${C}_{r+1}$ , then fitting these sample points, on condition that the number of fitting curve’s control vertices is the same as that of ${C}_{r}$ , at last compute intermediate section curve ${I}_{r}^{2}$ ’s control vertices by linearly interpolation of fitting curve’s control vertices ${V}_{r+1,i}^{\text{'}}$ and ${C}_{r}$ ’s control vertices ${V}_{r,i}$ . The knot vector of intermediate section curve is the same as curve ${C}_{r}$ .

Repeat the above operation on all the cross section curves then all the curves needed for T-mesh generation are obtained. Using this method to compute the intermediate section curves can keep the shape trend of cross section curves’ control vertices, thus reducing the wiggles in M. Oh’s method and reflect the cross section curves’ shape in the final surface. It is noticed that M. Oh’s method on Figure 8 doesn’t perform the algorithm in reference [8].

5. Results & Discussion

Several examples are given below to show the effectiveness of the shape preservation local T-Spline skinning method proposed in this paper (Figure 9 and Figure 10).

In this paper, a new algorithm for shape preservation local T-Spline skinning is given. In this algorithm, new intermediate section curves are to be inserted between cross section curves. By sampling points on the cross section curves, and use them to reverse compute control vertices, the intermediate section curves’ control vertices can be obtained by linear interpolating these control vertices, and their knot vectors are the same with the corresponding section curves. An error decided by the fitting algorithm will be introduced in the process of control vertices’ reverse computation. The advantage of this algorithm exists in that it sharply minimizes the possibility of the wiggles and its computation workload is light. And comparing with the method of A. Nasri [5], this method increases the number of control vertices.

Considering the traditional NURBS skinning, wherein the number of cross section curves is k, and each curve includes n control vertices averagely, the surface’s total number of control vertices can be as high as $O({k}^{2}n)$ , the method in

Figure 7. Insert intermediate section curve ${I}_{r}^{2}$ .

(a) (b)

Figure 8. Comparison of the two methods. (a) M. Oh’s method; (b) This paper’s method.

(a) (b) (c)

Figure 9. T-Spline skinning surface: example 2. (a) T-mesh in 3D space; (b) T-Spline skinning surface; (c) T-mesh and T-Spline surface.

(a) (b) (c)

Figure 10. T-Spline skinning surface: example 2. (a) T-mesh in 3D space; (b) T-Spline skinning surface; (c) T-mesh and T-Spline surface.

this paper can result in a T-Spline skinning surface of which the number of control vertices is $O(3kn)$ [2]. Usually the number of cross section curves are over 3, so even the algorithm here increases the number of control vertices than A. Nasri’s method, it’s still less than in the traditional NURBS skinning. And the newly increased control vertices firmly decrease the surface wiggles as well as provide more flexibility in the surface representation. Also the computation workload is decreased in this method, and no knot insertion is needed for the surface smoothing.

In future work, more cases will be tested, and if for some occasions the smoothness cannot be satisfying, maybe special work for surface smoothing will be combined with this method to improve its adaptability.

Acknowledgements

The authors would like to acknowledge the support by the Natural Science Foundation of China (Project No.61572056).

References

[1] Piegl, L. and Tiller, W. (2010) The NURBS Book. Tsinghua University Press, Beijing.

[2] Piegl, L.A. and Tiller, W. (2002) Surface Skinning Revisited. Visual Computer, 18, 273-283. https://link.springer.com/article/10.1007/s003710100156
https://doi.org/10.1007/s003710100156

[3] Sederberg, T.W., Zheng, J., Bakenov, A., et al. (2003) T-Splines and T-NURCCs. ACM Transactions on Graphics, 22, 477-484.
https://www.researchgate.net/publication/234827617_T-splines_and_T-NURCCs
https://doi.org/10.1145/882262.882295

[4] Sederberg, T.W., Cardon, D.L., Finnigan, G.T., et al. (2004) T-Spline Simplification and Local Refinement. ACM Transactions on Graphics, 23, 276-283.
https://www.researchgate.net/publication/234780696_T-spline_simplification_and_local_refinement
https://doi.org/10.1145/1015706.1015715

[5] Nasri, A. (2012) Local T-Spline Surface Skinning. Visual Computer, 28, 787-797.
https://link.springer.com/article/10.1007/s00371-012-0692-1
https://doi.org/10.1007/s00371-012-0692-1

[6] Yang, X. and Zheng, J. (2012) Approximate T-Spline Surface Skinning. Computer-Aided Design, 44, 1269-1276. https://doi.org/10.1016/j.cad.2012.07.003
https://www.researchgate.net/publication/256688182_Approximate_T-spline_surface_skinning?ev=prf_high

[7] Li, Y., Chen, W., Cai, Y., et al. (2015) Surface Skinning Using Periodic T-Spline in Semi-NURBS Form. Journal of Computational and Applied Mathematics, 273, 116-131. https://doi.org/10.1016/j.cam.2014.05.026
https://www.researchgate.net/publication/264913022_Surface_skinning_using_periodic_T-spline_in_semi-NURBS_form

[8] Oh, M.J., Roh, M.I. and Kim, T.W. (2018) Local T-Spline Surface Skinning with Shape Preservation. Computer-Aided Design.
https://www.researchgate.net/publication/325065815_Local_T-spline_surface_skinning_with_shape_preservation