SplineGen: a generative model for B-spline approximation of unorganized points

Parametrization methods. Because of the importance of parameterization in B-spline approximation, many research studies on this topic have been carried out. Recently, Scholz and Jüttler provided an informative summary on the classification and development of those methods in their paper [17]. Basically, heuristic methods are the dominant means of parameterization, e.g., uniform [16], chord length [18], centripetal [19], universal [34], and Foley-Nielson [20], among many others. Such basic versions have also been used as an initial guess for the parameterization and then optimized to achieve better approximation results, e.g., [35]. Typically, this leads to a highly non-linear constrained optimization problem. One line of relevant research studies focuses on the solving algorithms for this optimization problem, e.g., particle swarm optimizers [36, 37], and global optimizers [38]. The other line designs various error metrics to control the “goodness” of the final parameterization, e.g., squared distance errors [39] and angular speed uniformness [40].

Knot placement methods. Existing knot placement methods may be classified into two types: knot assignment that computes the whole knot vectors simultaneously; and knot refinement that iteratively modifies initial knots until an error threshold is met. To reflect the distribution of data points and guarantee that every knot span includes at least one parameter, there are knot assignment methods like AVG (averaging technique) (for point number $m$ = control point number $n$) and KTP (knot placement technique) (for point number $m>$ control point number $n$) [16]. Because KTP will have stability issues when $m$ is slightly greater than $n$. Piegl and Tiller [22] proposed a stability-enhanced version (NKTP) of KTP by using an averaging method. Like in parameterization, these methods have also been used as initial guesses and then optimized by iterative knot insertion [41, 42]. The essential task here is to determine when and where to insert the new knots. Several heuristics have been developed, such as angle variations [43], curvatures [44], and minimum knot size [45]. Evolutionary optimization algorithms [46, 47] and neural network-based optimization [48] have also been used to determine the knot insertion position.

The methods discussed above have proven effective in many applications, but due to their heuristic nature, they cannot provide acceptable results in all of the potential cases. This motivates the recent use of machine learning methods to carry out parameterization and knot placement, in an end-to-end manner.

Parametrization methods. The objective here is to learn a neural network to directly map data points to their corresponding parameters. The method presented in [24] appears to be the first to do so. A standard FCNN with a fixed input size of 100 data points and three hidden layers, each with 1,000 nodes, was used to construct the mapping. Because the input size is fixed, up-sampling or down-sampling is needed to run the model if the given number of data points is not equal to 100. Moreover, the training and inference of the model are time-consuming. To overcome this limitation, Scholz and Jüttler [17] replaced FCNN with ResNet, which has a fixed input size of $2d+1$ data points if the underlying curve is of degree $d$. Multiple models need to be trained, each for a degree. Each model can only parameterize $2d+1$ data points. If there are more than $2d+1$ data points, heuristical down/up-sampling is required. By contrast, the method in this paper can directly parameterize an arbitrary number of data points.

Knot placement methods. In the same paper [24], FCNN is also used to predict knot positions. The model has a fixed input size of 100 data points and three hidden layers, each with 500 nodes. It assumes that knots are a subset of parameters. Under this assumption, predicting knot positions is converted to an easier classification problem on parameters. A similar idea has also been used in [49], where a support vector machine is used to carry out the classification instead of FCNN. It is, however, arguable to snap knots onto parameters since knots and parameters do not have a shared relationship in many cases. In addition, their method’s input size is kept fixed.

3D generative methods. The proposed method in this work makes use of generative models, so it is closely related to the emerging field of generative 3D modeling [50]. Generative models have been successfully applied to a series of shape representations such as voxels [51], point clouds [52], neural implicit fields [53, 54], meshes [2], and solids [3, 4]. However, there has been limited use of generative models for B-spline modeling. Despite this, the way they designed the networks is very inspiring to this work. In particular, SplineGen has the same high-level network architecture (i.e., encoder-decoder) as most existing generative models, the low-level design of the encoder module and decoder module is different though.

Existing learning-based parameterization and knot placement methods have proven that they can be a promising alternative to the traditional heuristic methods in B-spline approximation. And reduced approximation errors were demonstrated. Nevertheless, there is still room for improvement, especially in extending the applicability and increasing accuracy. Following what has been done in [24, 17], this work presents a generative parameterization and knot placement, with added features of unorganized data points, size-independent, point permutation invariant, knot-parameter alignment, and high robustness.

Rather than directly inputting raw point coordinates into the network (as in existing methods [24, 17]), SplineGen first seeks a neighborhood-aware high-dimensional embedding for each data point, see the left part of Fig. 2. This is done with the help of the attention mechanism in transformer [1]—it allows every data point to attend to all data points in the input sequence. (This is the primary reason this work chooses transformer as the backbone.) SplineGen combines it with an additional masking mechanism to force each data point to attend more to its neighborhood regardless of how points are organized. Specifically, we use masking to simulate point embedding corruption and ask the remaining point embeddings to yield the same curve as before. As such, each point embedding carries its neighborhood’s information. To facilitate the alignment of parameters and knots, we force shared point embeddings between parameter generation and knot generation through the use of a shared autoencoder model. By doing so, we hope to capture the interplay between parameterization and knot placement in the high-dimensional embeddings.

Having point embeddings in place, two decoders are used to decode them into knots and parameters, respectively. See the middle part of Fig. 2. The knot decoder autoregressively predicts the next knot based on already generated knots until it thinks enough of them are generated, indicated by an “EOS” token. This essentially determines the number of knots and their placement simultaneously and automatically. Parameters are generated in a similar way, but with a self-organization module included in its decoder to ensure that the number of generated parameters and their order are in line with the input data points. To align these two generative models, a new module called internal cross-attention is added to the two decoders so that their attention modules are directly bundled together during knot and parameter generation. Lastly, the two decoders are further equipped with a masking mechanism to simulate data point removal/addition. It enforces a robust generation of knots and parameters (and therefore a robust approximation of the same curve) when some data points are missing or added.

SplineGen’s last module is a physics-informed neural network (PINN) layer appended to the above two decoders. PINN is a machine learning technique allowing governing equations (e.g., Eqs. (3) and (4)) to be respected during training [55]. In this regard, the added PINN layer can directly use Eq. (4) to guide the alignment of knot and parameter generation, capturing more subtle interplay between parameterization and knot placement than those obtained with shared embeddings and internal cross-attention. This module can be viewed as the final fine-tuning of the generative model.

The shared autoencoder model has three components, an encoder and two decoders, as shown in Fig. 3. The encoder takes as input the data points $P=\{p_{i}\in\mathbb{R}^{3}\}$ with their coordinates as 3-channel features for each point. These data points are not passed to the encoder directly but go through an intermediate step consisting of a positional encoding (on coordinates) function $\Gamma:\mathbb{R}^{3}\rightarrow\mathbb{R}^{d_{PE}}$ [56] and a linear projection, as follows:

where $W_{P}\in\mathbb{R}^{d_{emb}\times{d_{PE}}}$ is a learnable matrix, with $d_{emb}=512$ and $d_{PE}=12$ for all cases in this work.

The above preliminary embeddings $h_{P}$ are then passed to a transformer encoder E, followed by a linear layer, to obtain the final point embeddings $E_{P}$:

where $\theta_{E}$ denote trainable parameters of the transformer encoder. Note that our transformer is not equipped with a position encoding, since input points are unorganized and the point embeddings should be permutation invariant.

To train $E$ and obtain embeddings $E_{P}$ meaningful for parameterization and knot placement, an encoder-decoder scheme is used, with two transformer decoders: one for recovering knots from $E_{P}$, and the other for recovering parameters from $E_{P}$. Fig. 3 shows the network. The specific procedures of training $E$ follow the autoregressive scheme [1]. Specifically, assume that the two decoders have already generated $i$ knots and parameters, denoted by $\{\hat{k_{0}},\dots,\hat{k_{i}}\}$ and $\{\hat{p_{0}},\dots,\hat{p_{i}}\}$, they will predict the next knot and parameter from the same point embeddings $E_{P}^{\prime}$ using:

where $\theta$ is the network parameters of its argument, <SOS> is the starting token, $k_{i+1}$ and $p_{i+1}$ is the next predicted knot and parameter, respectively.

Instead of directly passing $E_{P}$ to the decoder, an additional masking mechanism is used to force each data point to attend more to its neighborhood regardless of how points are organized. Specifically, we randomly mask some embeddings to simulate point embedding corruption and ask the remaining point embeddings $E_{P}^{\prime}$ to yield the same results as before (except for the masked embeddings’ corresponding parameters). As such, each point embedding carries its neighborhood’s information.

The whole encoder-decoder pipeline is trained using the weighted sum of two losses, $L_{K}$ and $L_{P}$, which are the mean squared losses between ground truth($\hat{K}$ and $\hat{P}$) and predicted sequence($\bar{K}$ and $\bar{P}$), respectively.

From point embeddings, SplineGen decodes them into knots and parameters, again in an autoregressive way. Two problems need particular attention: how to ensure that the number of generated parameters and their ordering are in line with the input data points; and how to align parameterization and knot placement. This work solves these problems with several extensions to the transformer decoder. In a nutshell, the proposed decoder fuses two sub-decoders through a module called internal cross-attention (Fig. 4); one of the sub-decoders is a vanilla transformer decoder, and the other is a modified version with an additional self-organization module.

Knot sub-decoder. SplineGen uses the same transformer decoder as the one used in Sec. 4.2. It generates knots autoregressively, starting from the <SOS> token, predicting the next knot, and stopping at the <EOS> token. The number of knots is determined by the network automatically.

To facilitate the training of this sub-decoder, we slightly modify the representation of knots. They are first sorted in non-decreasing order, then prefixed with the start token <SOS> and suffixed with the stopping token <EOS>. After inserting these special tokens, the knot sequence $K^{seq}=\{\verb|<SOS>|,k_{0},k_{1},\dots,k_{|K|-1},\verb|<EOS>|\}$ is of length $|K_{seq}|=|K|+2$. Rather than using a real value for the knots, we add another two dimensions to indicate the probability of being <SOS> and <EOS> token, respectively.

Given all the point embeddings $E_{P}$ of given data points and the previously output knots $K^{seq}_{i-1}$ at step $i$, the goal is to model the next output knot token, denoted by $k_{i}$. The input to the transformer decoder is derived from each of the tokens in $K^{seq}_{i-1}$ by adding positional encoding followed by a linear project, and then the transformer decoder $\textbf{D}_{K}$ followed by another linear projection takes this input to predicts the next token. The model is trained to minimize the mean squared loss between predicted knots and the ground truth.

Parameters sub-decoder. For the parameter sub-decoder, the primary task is to make the output parameters’ ordering in line with the input data points. To do so, a parameter-point associative decoder is designed out of the transformer decoder used in Sec. 4.2. It adds an index prediction module so that the decoder can output not only the parameter values but also the positional indices of their corresponding points in the input. Specifically, the decoder takes the learned point embeddings $E_{P}$ as input into its cross-attention part and autoregressively outputs parameter values and indices. Let the decoder be denoted by $\textbf{D}_{T}(E_{P};\theta_{\textbf{D}_{T}})$ and its output embeddings be $E_{T}$, we let each autoregressively generated embedding $E^{i}_{T}$ to learn a probability distribution $p_{i}$ over the indices of the point encodings $P^{\prime}$ so that the one with the largest probability will correspond to the generated parameter in this iteration.

A common way to define $p_{i}$ is expressing it in terms of a dot product operation between $E^{i}_{T}$ and encoded points $P^{\prime}$, followed by a normalization operation with softmax, as follows [57]:

where $W_{Q}\in\mathbb{R}^{d_{emb}\times d_{emb}}$ and $W_{K}\in\mathbb{R}^{d_{emb}\times d_{emb}}$ are learnable matrices. The encoded points $P^{\prime}$ are simply latent codes of the input data points, and they are generated by a transformer encoder. The purpose of using $P^{\prime}$ instead of the input data points is to add more trainable parameters.

Combining the trainable decoder $\textbf{D}_{T}$ and Eq. (6) , the index prediction module essentially learns the following distribution:

where $I_{t}=\{\verb|<SOS>|,i_{0},i_{1},\dots,i_{t}\}$ denotes the already predicted indices until step $t$ and $\theta_{\textbf{D}_{T}}$ is the decoder’s parameters.

To avoid some indices being repeatedly predicted, we mask the corresponding entry in the dot product operation every time a new index is reached. This also guarantees that all elements in $P^{\prime}$ will be visited because the prediction step is executed exactly $|E|$ times.

To generate the intended parameter values, each embedding after the translation is passed to a 2-layer MLP to decode it into a parameter value. Combined with the previously generated index, we can obtain a parameter value, and meanwhile know its position in the final parameter array altogether. It should be noted that, to ensure the decoder generates as many parameters as the input data points, the generation process will be interrupted once enough parameters are output. This is different from the generation process for knots.

Internal cross-attention. Cross-attention has proven effective in model associativity between multimodal data [58]. This inspires us to add an attention-based module to fuse the decoders described above and then align the knot generation and parameter generation processes. Different from most existing cross-attention models, which operate on an attention module’s outputs (e.g., [4]), the internal cross-attention module here directly operates on its internal key/value/query matrices. This internal way of working can model the interplay between knots and parameters more conveniently.

The design of the internal cross-attention module is illustrated in Fig. 4. It activates only after the knots have all been generated. Upon reaching the final generation step of the knot sub-decoder ( with a token length denoted as $N_{k}$), both the key vectors $K\in\mathbb{R}^{N_{k}\times d_{attn}}$ and the value vectors $V\in\mathbb{R}^{N_{k}\times d_{attn}}$ have been generated in the self-attention module. These vectors are subsequently utilized in the upcoming internal cross-attention step. Consider the parameter generation at the time step $t$. At the $i^{th}$ level of the parameter sub-decoder, the output of $i-1^{th}$ decoder layer $X^{i-1}_{P}$ is transformed into query vectors $Q\in\mathbb{R}^{(t+1)\times d_{attn}}$ via a multiplication operation with a learnable matrix $W_{Q}\in\mathbb{R}^{d_{emb}\times d_{attn}}$. Employing these prepared keys, values, and queries within the cross-attention framework, an output vector is computed. This output is then combined with the preceding $X_{P}^{i-1}$ to yield a refined representation ${X^{i-1}_{P}}^{\prime}$. The network module that follows uses this refined representation as its input instead of the original $X_{P}^{i-1}$.

Masking. Lastly, the two decoders are further equipped with a masking mechanism to simulate data point removal/addition. Different from the masking mechanism used in Sec. 4.2, here we randomly remove a small proportion of points from the input data while keeping the generated knots and parameters for the remaining data points unchanged. This method enforces a robust generation of knots and parameters when some data points are missing or added, thereby giving a robust approximation of the same curve.

To directly use Eq. (4) to guide the alignment of knot and parameter generation, a PINN layer is further added to SplineGen when training it. This layer accepts the outputs from both the knot and parameter sub-decoders and computes a series of control points. The layer first calculates B-spline basis functions with an adapted version from the NURBS-Diff method presented in [55], then solves Eq. (4), resulting in a set of control points $P$, which define the intended curve $C$. Utilizing the generated curve $C$, the parameters $u$, and the corresponding 3D points $D$, we evaluate the approximation error through the following loss function:

where the maximum loss is employed instead of the mean loss to ensure that all predicted points consistently stay close to their target positions.

It should be noted that training a network with PINN layers is not easy. The derivatives of the PINN loss w.r.t the PINN input $u$ (i.e., parameters and knots in our case) need to be explicitly given to the network. The NURBS-Diff method [55] has provided a detailed derivation of those derivatives. We omit the details in this work.

Dataset. A dataset of 500,000 B-spline curves with their control points, knot vectors, and sampled points has been compiled. Self-intersecting curves were eliminated using a specialized detection program. For data processing, we normalize control points to $[0,1]^{3}$ and utilize masked arrays for neural network training consistency, refer to Supplementary Material for more details. A test dataset of above 5,000 curves is generated in the same way. We will make these datasets publically available upon publication of this paper.

Training. SplineGen has been implemented using PyTorch. We trained it on an NVIDIA RTX 3090 GPU and with the Adam solver, having a batch size 256 for 500 epochs and a fixed learning rate $lr$=$10^{-4}$. The dataset is split into 8:2 for training and validation.

Given the input data points $P$ and the reconstructed curve $C$ and predicted parameters $t$ for $P$, we evaluate the performance of SplineGen with the following three most commonly used metrics.

Maxium of Euclidian distances. We first evaluate the points in $C$ according to $t$ and compute the Euclidian distances of corresponding points. We use the max of these distances as our metrics, which is the same as Eq. (8) to measure the maximum approximation distance:

MSE of Euclidian distances. In addition, we also evaluate the mean square of these distances:

Hausdorff distances. We also evaluate the Hausdorff distance between point set $P=\{C(t_{i})\}_{i=0}^{N}$ and $Q=\{P_{i}\}_{i=0}^{N}$, which measures the greatest distance between any point in one set to its closest point in the other:

Some sampling results of using SplineGen to approximate data points are given in Figs. 5 and 6, with increasing shape complexity from top to bottom. To further show the capability of SplineGen, Fig. 7 gives some approximation examples of very complex shapes. As can be seen from the figure, although these shapes are not practical and have unreasonably complex shapes, our SplineGen can still generate quality results.

An ablation study has been conducted on SplineGen’s major modules, including the internal cross-attention module, the shared encoder module, and the masking module. Its setup is as follows:

1. (a)

   All: The proposed SplineGen network, with all modules included.

2. (b)

   w.o. Cross attention: The internal cross-attention module is removed when training the parameter decoder, which means the parameter decoder is not informed with the knots information.

3. (c)

   w.o. Shared encoder: The shared point encoder module is replaced with a simple linear layer to encode the points.

4. (d)

   w.o. Masking: The masking module is removed when training the decoders.

The ablation study results are shown in Table 1. They show that SplineGen, only when all modules are included, can give the best performance. This confirms the effectiveness of the pipeline outlined in Fig. 2. Also, as each optionally removed module is related directly to the functions of parameter-knot alignment and robustness, the ablation study results validate SplineGen’s features claimed in Sec. 1. Note that the features of size-independent and point permutation invariant are automatically ensured by the generative nature of SplineGen.

Table LABEL:tab:qualitative_comparison shows a qualitative comparison between SplineGen with existing learning-based methods (i.e., Jüttler [17] and PARNET [24]). SplineGen is the only method that can generate parameters and knots with unordered and non-fixed-size inputs. Table 2 presents a quantitative comparison of SplineGen with existing methods. Considering that all those existing methods require ordered data points as input, we have pre-sorted the input accordingly to make the comparison fair. Besides learning-based methods, we also compared with various classical parametrization and knot placement methods. Specifically, the chord-length and centripetal methods have been chosen for parametrization; NKTP [22], KTP [16], DOM [44] and uniform knots [16] have been chosen for knot placement. All of their combinations have been analyzed, as shown in Table 2.

The results indicate that SplineGen outperforms other methods in terms of maximum error (Max), mean squared error (Mse), and Hausdorff error (Hsdff). Table 3 further provides statistics of comparing SplineGen with existing methods on four curves chosen from the examples in Fig. 5. Fig. 8 shows the resulting approximate B-spline curves from these methods. SplineGen is seen to give competitive results in terms of both accuracy and generality. Only in the Mse error of Curve 3, SplineGen is less accurate than the method using the centripetal method for parametrization and the uniform method for knot placement. However, the result of SplineGen is very close to the best result, with only a 1e-4 difference.

From the comparisons shown in Figs. 5-8, and Tables 2 and 3, SplineGen can consistently give competitive approximation results, with lower error and better robustness. Large improvements have been confirmed for classic parametrization and knot placement methods (except for one case), see Fig. 8. Even for the state-of-the-art learning-based method, the proposed method is still able to reduce the maximum error by a notable percentage, above 88%, depending on the specific data points being considered.

Numerical issues in solving Eq. (4) have also been observed. An in-depth analysis showed that the reason lies in the distribution of the parameters generated by SplineGen. It has been known that it is better to have parameters filled in every knot span, and empty knot spans will result in a poorly conditioned coefficient matrix [59]. To completely solve this issue, a network that can evenly distribute parameters over knot spans is needed. Such a network remains unknown, and further development is required.