Developable B-spline surface generation from control rulings

In some applications, one of the boundary curves of the developable surface is given and fixed. Given additionally a set of straight line segments serving as ruling lines, we need to construct the other boundary curve to obtain the developable surface $S$. This problem is specifically defined as follows. Suppose we are given a boundary curve, denoted by $C_{0}(t),t\in[0,1]$, and a sequence of line segments $L_{i}(i=0,...,K)$ emanating from points on $C_{0}(t)$. The problem of developable surface computation from the control rulings can be described by the constraints: the line segments $L_{i}$ are identical to $\overline{C_{0}(t_{i})P_{i}}$, $i=0,...,K$, with $t_{0}=0,t_{K}=1$ indicating the terminal interpolation constraint and $P_{i}$ being the data points in space.

As we have explained, this ruling fitting problem can be solved by curve fitting with particular constraints. The unknown variables are the control parameters of $C_{1}(t)$ whose endpoints are fixed to be $P_{0}$ and $P_{K}$. The objective is to make $C_{1}(t)$ approximate $P_{i},i=1,...,K-1$ with which the surface $S$ defined in Eq.(1) achieves a high degree of developability.

For arbitrary input rulings, there is generally no developable surface exactly interpolating the rulings. However, a B-spline surface with a large number of control points can provide enough degrees of freedom to construct a quasi-developable surface. We formulate this problem as a numerical optimization problem and obtain the resulting curve $C_{1}(t)$ and the developable surface $S$ by minimizing an objective function evaluating surface developability.

A prime-dual formulation of developability. The surface $S$ (Eq.(1)) bounded by $C_{0}(t)$ and $C_{1}(t)$ being a developable surface requires $S$ to meet the following constraints Tang2016Interactive .

Solution space regularization. The number of variables in optimization depends on the number of samplings on the surface. In fact, the number of samplings should be large enough to regularize the surface and it depends on the number of control points and the degree of the surface. In practice, to provide enough flexibility for maximizing surface developability, we use a large number of samplings (100). Existing works have shown that when there are many variables in an optimization problem, the shape of the solution space is often not good, which makes the optimization process unstable and even leads to an unsatisfactory solution in some cases. This problem can be solved by introducing a regularization term to control the shape of the solution space. Therefore, we introduce two shape-control terms as follows.

Interior shape control of the surface. In order to control the interior shape of the surface, we introduce the following term, taking the effects of internal control rulings into account.

By solving the minimization problem $F_{1}\rightarrow min$, we can obtain a quasi-developable surface. The variables in the optimization are the independent normal vectors $N_{k},k=0,...,M$ and the interior control points of curve $C_{1}(t)$ (the first and last control points remain fixed). This provides enough degrees of freedom, which enhances the ability to find a locally optimal quasi-developable surface. The algorithm is presented in Algorithm 1.

With the output of the algorithm $CP^{1}_{1},...,CP^{1}_{K-1}$, together with the fixed end points $CP^{1}_{0}$ and $CP^{1}_{K}$, a B-spline surface defined by Eq.(1) is obtained. Note that the normal vectors $N_{j}$,$j=0,...,M$ are auxiliary variables used for simplifying the developability constraint equations and are not used for generating the resulting developable surface. In the following, we show some experimental results.

Experiments (K=1). In some applications, the first and the last ruling lines of the surface are specified as hard constraints, in addition to a fixed boundary curve $C_{0}(t)$. When there are no more control rulings other than the first and the last one, this case is characterized by $K=1$ in our definition. The first and last ruling line can be defined by two additional data points $P_{0}$ and $P_{1}$ in space and are denoted by $\overline{C_{0}(0)P_{0}}$ and $\overline{C_{0}(1)P_{1}}$. This design model is conceptually similar to the design of a Hermite curve by specifying the end data points and associated tangent vectors. In this case, the energy term $F_{EnergyC_{1}}$ and the width variation control term $F_{Width}$ have an important effect on controlling the interior shape of the resulting surface which is illustrated by the experimental results in Fig. 3 and Fig. 4. The developability of the surface is evaluated by the warp angle between the normal vectors at the both ends of the ruling line. $\beta_{Max},\beta_{Ave}$ represent the maximum and average warp angle among a set of sampling rulings, respectively.

Observing the results in Fig. 3, we find that the energy term $F_{Energy}$ can efficiently control the shape of the boundary curve and avoid self-overlapping of the surface, without sacrificing the developability of the surface. In fact, the resulting surface achieves a higher degree of developability than the result without the energy term. This is because the energy term $F_{Energy}$ leads to a finer shape of the solution space and consequentially a stable optimization process which avoids unsatisfactory local minimums. Observing the results shown in Fig. 4, the width variation control term $F_{Width}$ makes the resulting surface have a smooth variation of the width of ruling lines with improved surface developability, owing to the same reason as the energy term $F_{Energy}$.

Experiments (K>1). When $K\textgreater 1$, the interior rulings other than the end ones can be used to control the interior shape of the resulting surface. The experiments in Fig. 5 show the difference between the results with and without the constraint of interior rulings. The upper boundary curve $C_{0}(t)$ in Fig. 5(a) is the given curve which is fixed. Fig. 5(b) and Fig. 5(c) show the developable surfaces without and with the constraint of interior rulings, respectively. The color coding in Fig. 5 indicates the magnitude of the warp angle. We also measure the distances from the endpoints of rulings to the final boundary curve. $D_{Max},D_{Ave}$ represent the maximum and average distance, respectively. We conclude from the experimental results that the resulting surface can be controlled by interior rulings without giving up much developability. However, the constraint of interior rulings indeed has negative effect on surface developability. This means the hard interpolations to the boundary curve $C_{0}(t)$ and two terminal rulings greatly restrict the solution space of developable surfaces. In Sec. 3.2 we will discuss the method relaxing the constraints of boundary conditions.

In many applications (such as ship-hull design), the input curves are not required to be the exact boundary curves of the resulting surface. A distance tolerance is often allowed whose value depends on specific applications. Therefore, a method which can find a surface with a high degree of developability with its boundary curves perturbed from the original design curves are more practically useful. We devise such a method in which both boundary curves are variables in optimization and solve for perturbed boundary curves to define a developable surface. The problem is described as follows.

Given a set of ordered rulings $L_{i}=(Q_{i},P_{i})(i=0,...,K)$, $Q_{i},P_{i}$ are the given data points. The objective is to construct the curves $C_{0}(t),C_{1}(t)$ fitting the data points $Q_{i},P_{i},(i=0,...,K)$, respectively, satisfying $C_{0}(0)=Q_{0},C_{1}(0)=P_{0},C_{0}(1)=Q_{K},C_{1}(1)=P_{K}$ so that the surface $S$ (Eq.(1)) bounded by $C_{0}(t)$ and $C_{1}(t)$ achieves a high degree of developability.

Viewing the two curves $C_{0}(t)$ and $C_{1}(t)$ as variables in optimization provides more degrees of freedom and increases the possibility of finding a surface with a higher degree of developability. As we have explained, this problem of fitting developable surfaces to a set of ruling lines is equivalent to fitting two curves to the data points $Q_{i}$ and $P_{i}$, $i=0,...,K$ with certain constraints. It is well-known that the parametrization of the data points is a key issue in curve fitting. In our specific problem, data parametrization is even more tricky than in ordinary curve fitting because the data points $Q_{i}$ and $P_{i}$ are required to have the same parameter, which is a requirement from Constraint 1. Therefore, the key issue is how to find the optimal parameter value $t_{i}$ for $Q_{i}$ and $P_{i}$. We propose an algorithm which solves for $C_{0}(t)$ and $C_{1}(t)$ and the parameters $t_{i}$ through an iterative process. The main steps of this algorithm are described as follows.

1. 1.

   Step1. Parametrize the rulings to make the data points $Q_{i},i=0,...,K$ and $P_{i},i=0,...,K$ have the same parameter values $t_{0},...,t_{K}$, respectively. We employ the centripedal parametrization to the data points $Q_{i},i=0,...,K$ and $P_{i},i=0,...,K$, and obtain the parameter values $u_{0},...,u_{K}$ and $v_{0},...,v_{K}$, respectively. Then the average parameter value of the two endpoints of a ruling is used for both endpoints. Precisely, $t_{i}=\frac{1}{2}(u_{i}+v_{i})$ is used as the parameter value for both $Q_{i}$ and $P_{i}$.

2. 2.

   Step2. Construct the interpolation B-spline curves $\widetilde{C_{0}}(t)$ and $\widetilde{C_{1}}(t)$ satisfying $\widetilde{C_{0}}(t_{j})=Q_{j}$ and $\widetilde{C_{1}}(t_{j})=P_{j},j=0,...,K$. Generally, the surface $S$ bounded by $\widetilde{C_{0}}(t)$ and $\widetilde{C_{1}}(t)$ as defined by Eq.(1) is not a developable surface. Therefore, we need to to improve the developability of the surface by relaxing the constraint of curve interpolation. We define the following closeness term.

   $$F_{Closeness}=\sum_{i=1...K-1}(\|C_{1}(t_{i})-P_{i}\|^{2}+\|C_{0}(t_{i})-Q_{i})\|)^{2}$$

   (6)

   Note that the end control points of both curves are fixed and are not treated as variables in optimization, to confirm hard interpolation to the specified terminal rulings. Then we define the following objective function.

   $\displaystyle F_{2}=F_{Dev}+\lambda_{Closeness}F_{Closeness}+\lambda_{Energy}(F_{EnergyC_{0}}+F_{EnergyC_{1}})+\lambda_{Width}F_{Width}$

   (7)

   where $F_{EnergyC_{0}}$ is an energy term for $C_{0}(t)$ whose definition is samilar to the definition of $F_{EnergyC_{1}}$ (Eq.(3)). For the definition of $F_{Width}$, refer to Eq.(4).

3. 3.

   Step3. Solve the minimization problem $F_{2}\rightarrow min$, we can obtain two updated curves $\widetilde{C_{0}}(t)$ and $\widetilde{C_{1}}(t)$ (the same symbols are used for the curves before and after update).

   In order to provide a termination criterion of the iterative process, we evaluate the developability of the surface $S$ bounded by the updated curves $\widetilde{C_{0}}(t)$ and $\widetilde{C_{1}}(t)$. If the developability requirements are met, or the improvement of developability by this iteration is ignorable, the algorithm can be stopped; Otherwise goto Step3.

4. 4.

   Step4. Update the parameter values of the data points. For the data point $Q_{j}$, a parameter value $u_{j}$ is obtained which is the parameter of the nearest point (foot point) on $\widetilde{C_{0}}(t)$. Similarly, for the data point $P_{j}$, the parameter value $v_{j}$ of the nearest point (foot point) on $\widetilde{C_{1}}(t)$ is computed. For foot point computation, a Newton-like iteration method is used Hoschek1993 . Then the value $t_{j}=\frac{1}{2}(u_{j}+v_{j})$ is used as the updated parameter for both $Q_{j}$ and $P_{j}$. Goto Step3.

The algorithm is summarized in Algorithm 2. The output of the algorithm combined with the fixed end points give us the control points of $C_{0}(t)$ and $C_{1}(t)$, i.e., $CP^{0}_{0}$,…,$CP^{0}_{K}$ and $CP^{1}_{0}$,…,$CP^{1}_{K}$. The surface $S$ is thus obtained by the definition of Eq.(1), bounded by $C_{0}(t)$ and $C_{1}(t)$.

An experiment is shown in Fig. 6. Given a set of rulings (Fig. 6(a)), we first construct two initial interpolation B-spline curves $\widetilde{C_{0}}(t)$, $\widetilde{C_{1}}(t)$ and the initial interpolation surface $S$ (Fig. 6(b)). Fig. 6(c) shows the result boundary curves and the resulting surface. Fig. 6(e) and Fig. 6(f) shows the color coding of warp angles of the surfaces in Fig. 6(b) and Fig. 6(c), respectively. Within the range of unit 1, the maximum distance from given data points to the resulting curves $C_{0}(t)$ and $C_{1}(t)$ is 0.025, and the average distance is 0.0089, indicating that the surface achieves high degrees of both developability and approximation to input ruling lines. Fig. 6(d) shows the difference between initial interpolation curves (dotted curves) and result boundary curves (solid curves). The convergence behaviour of our algorithm is shown in Fig. 6(g)(h). It can be seen that the algorithm in Sec.3.2 has high convergence rate and high stability.

The algorithms proposed in this work depend on a sequence of line segments serving as the control rulings of the surface. Basically, the lines can be specified in space freely by the designer. However, with arbitrary line segments in space, the distance between the control lines and the resulting developable surface may be large which is not desired in an interactive design process.

To reduce the difference between the original design rulings and the resulting surface, while still achieving a high degree of developability, additional constraints in the design of input rulings should be considered. It has been shown that planar quadrilateral strips can be viewed as the discretization of smooth developable surfaces Liu2006Geometric . Therefore, in the design process of the control rulings, we require that every pair of adjacent rulings be coplanar. Precisely, if the given rulings are denoted by $L_{i}=(P_{i},Q_{i}),i=0,...,K$, we require the quadrilaterals $P_{i}Q_{i}Q_{i+1}P_{i+1}$ bounded by two adjacent rulings $L_{i}$,$L_{i+1}$ to be coplanar.

In Fig. 7(a)-(c), the control rulings are designed arbitrarily and we observe that it is not always guaranteed that a resulting surface with a high degree of developability can meet the original design intention tightly. That is, a compromise between the original design intention of shape and a high degree of developability should be made.

Fig. 7(d)-(f) give the experimental results with the original control rulings similar to the one in Fig. 7(a), which however satisfy the coplanarity constraint. From the experimental results in Fig. 7(d)-(f), we observe that we can obtain a developable surface better meeting the original design intention with input lines forming a planar quadrilateral strip. The developability of the resulting surface based on coplanar lines is about an order of magnitude better than the results of non-planar lines with even better approximation quality to the control rulings.

From these experiments, we can suggest the following procedural way of control ruling design. Once the $i$th control ruling $L_{i}$ is ready, the $(i+1)$th ruling should be defined on the plane containing $L_{i}$. Note that although this process depends on a sequence of planes, this method is essentially different to the existing methods working with planes tangent to the developable surface in that our method works directly in the design space which has more geometric intuition than working in the dual space. This algorithm of control ruling design is presented in Algorithm 3.

Fig. 8 shows the experiments with one fixed boundary curve, using the algorithm in Sec. 3.1 to construct a developable surface. The inputs include two data points ${P_{0},P_{1}}$ and one fixed boundary curve $C_{0}(t)$ which is the same as the fixed curve in Fig. 4. The goal is to construct a B-spline boundary curve $C_{1}(t)$ whose endpoints are ${P_{0},P_{1}}$ and the surface $S$ bounded by $C_{0}(t)$ and $C_{1}(t)$ as defined by Eq.(1) achieves a high degree of developability. The boundary curve $C_{1}(t)$ are initialized by transforming the control points of $C_{0}(t)$ by rotation, translation and scaling operations such that the end points of the transformed curve coincide with $P_{0}$ and $P_{1}$. Fig. 5(b), Fig. 8 show surfaces of large developability with the same fixed boundary curve $C_{0}(t)$ and various positions of $P_{0}$ and $P_{1}$. The results demonstrate that by fixing one boundary curve and two terminal rulings, there are still enough degrees of freedom for generating a high degree of developability.

When more flexible control over the interior shape of the surface is desired, the interior rulings should be taken into consideration. This is characterized in our definition by $K>1$ and $\lambda_{Closeness}>0$. The experiment in Fig. 5 has shown that when interior control rulings are considered, fixing one boundary curve does not provide enough flexibility. In this case, the boundary curve interpolation constraints should be relaxed to provide a high possibility to find a surface with a high degree of developability, which is realized using the algorithm in Sec. 3.2.

In Fig. 9, we give a comparison between the performance of fixing one boundary curve (the algorithm in Sec. 3.1) and relaxing both curves (the algorithm in Sec. 3.2), with the same input control rulings, the same weight settings and termination conditions of the optimization. The results are shown in Fig. 9. For this experiment, adjacent lines in the input are coplanar as shown in Fig. 9(a). Using the given weight setting, the algorithm fixing one boundary curve makes only a small improvement on surface developability. The surface developability can be further improved by decreasing $\lambda_{Interior}$, but it will also decrease the fitting quality. For the same input and same initial curves, the method relaxing both boundary curves enables the resulting surface to achieve a much higher degree of developability. Moreover, the distance errors between the resulting surface and the given rulings are also smaller.

This experiment demonstrates that a tiny perturbation of control rulings provides a larger solution space of developable surfaces than fixing boundary curves. The optimization algorithm is thus able to find a much larger developability of the resulting surface without sacrificing the fidelity to original design intention. Since in real applications, a particular level of distance errors of the surface is always reasonable, the proposed method of curve perturbation is a practically useful method for generating developable surfaces with a high degree of developability from control rulings.

The algorithm in Sec. 3.1 is also useful when fixing one boundary of the surface is a hard rule, especially when there is no strict constraint introduced by interior rulings. We have shown that with the first and last rulings being strict interpolation rule, we can still achieve a high degree of developability and the surface shape can be nicely controlled. This has been demonstrated by the results in in Fig. 3,Fig. 4, Fig. 5, Fig. 8.

The minimization of the nonlinear functions Eq.(5) and Eq.(7) are solved with the L-BFGS algorithm ZHENG2012448 . The weight of each term in the objective function is determined empirically. To unify the weight settings in the objective function, all models are scaled into a unit box.

The developability is evaluated by the warp angle between the normal vectors at both ends of the rulings. The warp angle associated with the sampling parameter $t_{i}$ is defined by the angle between the vectors $N(t_{i},0)$ and $N(t_{i},1)$ where $N(t,s)$ is the normal vector at $S(t,s)$. Existing works have shown that the practical requirements of ship-hull design can be met when the maximum warp angle is less than 6 degree.

The proposed algorithms have been implemented with C++ on the Microsoft Visual Studio platform. All experiments are performed on a laptop with 2.6 GHz Intel Core i7 CPU and 16 GB 2400 MHz DDR4 memory. The running time ranges from 16s to 60s for the experiments shown in this paper.