# Hybrid MBlur: A Systematic Approach to Augment Rasterization with Ray
Tracing for Rendering Motion Blur in Games

Anonymous
Yu Wei Tan  , Xiaohan Cui  and Anand Bhojan
School of Computing, National University of Singapore, Singapore
{yuwei<EMAIL_ADDRESS><EMAIL_ADDRESS>
https://orcid.org/0000-0002-7972-2828 https://orcid.org/0000-0002-6152-1665
https://orcid.org/0000-0001-8105-1739

###### Abstract

Motion blur is commonly used in game cinematics to achieve photorealism by
modelling the behaviour of the camera shutter and simulating its effect
associated with the relative motion of scene objects. A common real-time post-
process approach is spatial sampling, where the directional blur of a moving
object is rendered by integrating its colour based on velocity information
within a single frame. However, such screen space approaches typically cannot
produce accurate partial occlusion semi-transparencies. Our real-time hybrid
rendering technique leverages hardware-accelerated ray tracing to correct
post-process partial occlusion artifacts by advancing rays recursively into
the scene to retrieve background information for motion-blurred regions, with
reasonable additional performance cost for rendering game contents. We extend
our previous work with details on the design, implementation, and future work
of the technique as well as performance comparisons with post-processing.

##  1 INTRODUCTION

We showcase a novel real-time hybrid rendering technique for the Motion Blur
(MBlur) effect that combines ray tracing and post-processing, exploiting ray-
traced information within a selection mask to reduce partial occlusion
artifacts in post-processed MBlur. We provide a thorough illustration and
evaluation of hybrid MBlur, extending our published work (Tan et al., 2020b, )
with the following additions:

  * •

Extensive discussion of the design and implementation details of hybrid MBlur.

  * •

Visual quality and performance evaluations of our technique in comparison to
post-processing.

  * •

Explanation of presented extensions and future work to the approach.

###  1.1 Background Information

####  1.1.1 Hybrid Rendering

Ray tracing is a common approach to produce realistic effects like glossy
reflections, depth of field, and motion blur. However, its high computation
time has limited its use mostly to offline rendering. On the other hand, many
post-process techniques have been devised to approximate these effects on
rasterized images to meet the constraint of interactive frame rates for games,
albeit with limited visual quality.

Given recent developments in hardware acceleration, it is now the time to
marry ray tracing with rasterization for games. Ray tracing can be employed to
correct certain visual flaws originating from pure post-process approaches,
while still adhering to the performance budgets of real-time rendering. This
results in more realistic and convincing graphics while keeping the gaming
experience interactive, enhancing the overall immersion of the player in the
game.

####  1.1.2 MBlur

MBlur is the streaking or smearing effect of objects in the direction of
relative motion with respect to the camera. It is employed in cinematics to
emphasize the relative speed of moving objects, producing a blurring effect as
shown in Figure 1. The MBlur effect has been used to express the speed of
rapid movement, the disoriented state of mind of a character, or the dreamlike
quality of a scene.

Figure 1: MBlur effect. Image from authors.

In cameras, MBlur is produced with the choice of exposure time or shutter
speed, which is the duration for which the camera shutter is open per second.
This duration directly correlates to the amount of time the camera sensor is
exposed to light. Hence, when the exposure time is long, every resulting image
does not represent an instantaneous moment but rather, an interval consisting
of successive moments in time. An object moving in relation to the camera will
therefore appear on multiple areas of the sensor over time, resulting in a
directional blur effect of the object corresponding to its motion.

As described in Jimenez, (2014), moving objects blur both outwards and inwards
at their silhouettes, making the region around their silhouettes appear semi-
transparent. Outer blur represents an object’s blur into its neighbouring
background while inner blur applies to the blur produced within the silhouette
of the object itself. According to Cook et al., (1984), accurate motion
blurring takes into account areas of background geometry occluded by any
blurred foreground. Hence, realistic MBlur should have accurate partial
occlusion by recovering true background colour in inner blur regions instead
of approximating this colour like many post-process approaches. Background
colour recovery in MBlur also helps to prevent inaccuracies between real and
approximated backgrounds for sharp and blurred regions respectively. Hence, we
employ ray tracing in our approach to retrieve the exact colour of occluded
background.

##  2 RELATED WORK

###  2.1 Hybrid Rendering

The use of ray tracing to complement rasterization techniques to achieve high
graphics quality while maintaining interactive frame rates has been attempted
for several visual effects over the years. In Beck et al., (1981) and Hertel
et al., (2009), shadow mapping is employed to mark shadow boundaries and
reduce the actual number of shadow rays to be traced, of which only rays from
regions deemed potentially inaccurate by shadow mapping are traced in
Lauterbach and Manocha, (2009) to generate precise and alias-free shadows. For
realistic reflections, Macedo et al., (2018) invokes ray tracing only on
pixels with reflections that cannot be solved with just screen space
information. In Marrs et al., (2018), traditional temporal anti-aliasing (TAA)
is also extended with ray-traced supersampling for regions with a high chance
of TAA failure.

In Cabeleira, (2010), diffuse illumination is computed via rasterization while
reflections and refractions are handled by ray tracing. In more general
pipeline approaches, Chen and Liu, (2007) substitutes the generation of
primary rays in recursive ray tracing (Whitted,, 1979) with rasterization for
improved performance. This approach is extended in Andrade et al., (2014)
which adheres to a render time limit by tracing rays only for objects of the
highest importance.

###  2.2 MBlur

Current implementations of MBlur include the use of an accumulation buffer.
Within the exposure time when the camera shutter is set to be open, a series
of discrete snapshots rendered at multiple time offsets from the actual time
value of the image is integrated to produce MBlur such as in Korein and
Badler, (1983) and Haeberli and Akeley, (1990). However, as discussed in
McGuire et al., (2012), this approach is computationally expensive in terms of
shading time. Furthermore, in the case of undersampling, this method can lead
to a series of disjoint ghosting artifacts in the direction of motion instead
of a continuous blur.

Stochastic sampling (Cook,, 1986) for MBlur is a Monte Carlo technique based
on Halton, (1970) in which sampling is performed in a randomized and
nonuniform manner along the time dimension. McGuire et al., (2010)
incorporates stochastic sampling with ray tracing by conservatively estimating
the total convex hull bound for the area of each moving triangle during the
exposure time, leveraging hardware rasterization. Stochastically distributed
rays are then shot into the scene within this bound for shading. This approach
makes use of distributed ray tracing (Cook et al.,, 1984), where rays are
distributed in time and the colour at each hit point is averaged to produce
the final image.

Cook et al., (1987) translates micropolygons for each sample according to a
jittered time. On the other hand, Fatahalian et al., (2009) and Sattlecker and
Steinberger, (2015) achieve efficiency in performance by extending the
bounding box of each micropolygon to consider its pixels and their associated
velocities instead. Hou et al., (2010) is an approach that makes use of 4D
hyper-trapezoids to perform micropolygon ray tracing. Methods of approximating
the visibility function to sample have also been devised such as in Sung et
al., (2002). However, as explained in Sattlecker and Steinberger, (2015), at
low sample rates, these methods will also exhibit ghosting artifacts whereas
increasing the number of samples would lead to noise.

To produce the right amount of blur, some real-time approaches like Rosado,
(2007), Ritchie et al., (2010) and Sousa, (2013) make use of per-pixel
velocity information by accumulating samples along the magnitude and direction
of velocities in the colour buffer. Other techniques in Korein and Badler,
(1983), Catmull, (1984) and Choi and Oh, (2017) accumulate the colours of
visible passing geometry or pixels with respect to a particular screen space
position while Gribel et al., (2011) makes use of screen space line samples
instead. Potmesil and Chakravarty, (1983) represents the relationship between
objects and their corresponding image points as point-spread functions (PSFs),
which are then used to convolve points in motion. Leimkühler et al., (2018)
splats the PSF of every pixel in an accelerated fashion using sparse
representations of their Laplacians instead. Time-dependent edge equations, as
explained in Akenine-Möller et al., (2007) and Gribel et al., (2010), and 4D
polyhedra primitives (Grant,, 1985) have also been used for MBlur geometry
processing. Recently, a shading rate-based approach involving content and
motion-adaptive shading in Yang et al., (2019) has also been developed for the
generation of MBlur.

In particular, attempts to simulate nonlinear MBlur include Gribel et al.,
(2013) and Woop et al., (2017). Our hybrid technique only considers linear
inter-frame image space motion for now, but we intend to provide support for
higher-order geometry motion in the future. We also assume mainstream ray
tracing acceleration architecture widely available in modern gaming
workstations. The GA10x RT Core of the newest NVIDIA Ampere architecture
provides hardware acceleration for ray-traced motion blur (NVIDIA
Corporation,, 2021) but is only found in the premium GeForce RTX 30 Series
graphics cards.

##  3 DESIGN

Our hybrid MBlur approach, as illustrated in Figure 2, compensates for missing
information in post-processed MBlur with the revealed background produced by a
ray trace-based technique.

Figure 2: Hybrid MBlur rendering pipeline.

A Geometry Buffer (G-Buffer) is first generated under a deferred shading set-
up, rendering textures containing per-pixel information such as camera space
depth, screen space velocity and rasterized colour. The same depth, velocity
and colour information for background geometry is produced by our novel ray
reveal pass within a ray mask for pixels in the inner blur of moving
foreground objects. A tile-dilate pass is then applied to these 2 sets of
buffers to determine the sampling range of our gathering filter in the
subsequent post-process pass. Both the ray-revealed and rasterized output are
blurred by this post-process pass and lastly composited together.

###  3.1 Post-process

The McGuire et al., (2012) post-process MBlur renders each pixel by gathering
sample contributions from a heuristic range of nearby pixels. We adapt this
approach to produce a motion-blurred effect separately for rasterized and ray-
revealed information.

As suggested in Rosado, (2007), motion vectors are given by first calculating
per-pixel world space positional differences between every frame and its
previous frame, followed by a translation to screen space. By using the motion
vector between the last frame and the current frame, we simulate the exposure
time of one frame. Then, we follow the approach of McGuire et al., (2012) in
calculating the displacement of the pixel within the exposure time by scaling
the inter-frame motion vector with the frame rate of the previous frame as
well as the exposure time. Considering the full exposure as one unit of time,
this displacement can be interpreted as a per-exposure velocity vector. This
approach uses the assumption that the motion vector of each pixel between the
previous frame and the current frame remains constant throughout the exposure
time.

Jimenez, (2014) is a technique that is based on McGuire et al., (2012). As
described in Jimenez, (2014), the major problems to be addressed when
producing a post-processed MBlur are the range of sampling, the amount of
contribution of each sample as well as the recovery of background geometry
information for inner blur. With our method for calculating per-exposure
velocities, we adopt McGuire et al., (2012)’s approach in determining the
magnitude of the sampling range and representing different amounts of sample
contribution, as illustrated in the Appendix for completeness. As shown in
Figure 3, McGuire et al., (2012) centers the sampling area at the target
pixel, creating a blur effect both outwards and inwards from the edge of the
object. Although this produces a more uniform blur for thin objects and the
specular highlights of curved surfaces, it poses the problem of having to
smoothen the transition between the inner and outer blur. Hence, we let the
pixel be at the end of the sampling area instead, so inner and outer blur can
be considered separately without much change to the pipeline. We also enhance
the inner blur with ray-revealed background information.

Figure 3: Range of samples for each pixel.

###  3.2 Ray Reveal

McGuire et al., (2012) approximates the inner blur region of objects with
colour information of nearby samples. This is based on the reasoning that
approximate background information is still better than the absence of any
background. With our ray reveal algorithm, we ray trace to obtain true
background information for the inner blur.

####  3.2.1 Ray Mask

We adopt selective rendering (Chalmers et al.,, 2006) in generating a ray mask
that determines regions of inner blur corresponding to geometry edges and only
shoot rays within the mask for better performance like in adaptive frameless
rendering (Dayal et al.,, 2005).

For every pixel with a nonzero speed, we first translate it by its velocity
for one magnitude of its estimated displacement within the exposure time to
predict its next screen space position at the end of the exposure duration and
compare their mesh ID and depth. A target pixel is filtered out of the mask if
the following conditions are not met:

$m_{n}\neq m_{t}$ (1) $z_{n}-z_{t}>{\rm SOFT\\_Z\\_EXTENT}$ (2)

$m_{n}$ and $m_{t}$ refer to the corresponding mesh ID of the pixel’s next and
current positions respectively. We assume that every object has uniform speed
throughout its geometry, so we reject the case when the $m_{n}$ and $m_{t}$
are equal. $z_{n}$ and $z_{t}$ refer to the camera space depth of the pixel’s
next and current position respectively. For a target pixel to be in the inner
blur region of a foreground object, it would have to be shallower than its
next position. Hence, $z_{n}$ has to be deeper than $z_{t}$ by a value greater
than SOFT_Z_EXTENT, a scene-dependent variable with a positive value as
introduced in the McGuire et al., (2012) paper for calculating sample
contribution.

For pixels that are not filtered out, they are passed through a $5\times 5$
Sobel convolution kernel which estimates how extreme an edge is. The kernel is
applied to the G-Buffer to obtain an approximate derivative of the gradient
associated with each pixel, based on the depth and surface normal information
of its vicinity readily accessible from the deferred shading stage. The depth
derivatives identify the divide between overlapping objects where the colour
of one object might be revealed through the other, while the normal
derivatives can locate pronounced differences in the orientation of primitive
faces within objects themselves near their silhouettes. The output of each
pixel from this filter is hence computed as follows:

$x=\delta_{d}+\delta_{n}$ (3)
$x_{n}=\textnormal{{saturate(}}\textnormal{\emph{$1-\frac{1}{x+1}$}}\textnormal{{)}}$
(4)

Here, $\delta_{d}$ and $\delta_{n}$ refer to the depth derivative and length
of normal derivatives respectively from the Sobel operator. The normalized
$x$, $x_{n}$, is subsequently evaluated against an edge threshold $e$, which
is set to be high in order to effectively eliminate non-edges from the mask.
Only pixels that pass the threshold test will be marked in the edge mask.

Lastly, a range check pass is applied. Each pixel with a nonzero speed then
samples along the direction of its velocity. If any of its samples is marked
in the edge mask, the pixel passes into the final ray mask.

####  3.2.2 Recursive Ray Tracing

To obtain more accurate information behind foreground objects for compositing
inner blur, our ray tracing approach, as illustrated in Figure 4, adapts the
idea of recursive ray tracing (Whitted,, 1979) where we shoot rays and
iteratively advance them deeper into the scene until a different object is
found. At the end of the recursion, the occluded background is then revealed
with the final hit point. Revealing more layers deeper into the scene with
this method increases the accuracy of our motion-blurred background but at
diminishing returns. Hence, we limit the ray reveal process to only one
background layer and post-process (i.e. approximate using neighbour
information) it instead.

Figure 4: Ray tracing approach.

For every pixel marked in the ray mask, we shoot a ray from the camera into
its world space position and immediately spawn a second ray along the same
direction after the first hit. Currently, we use a simple indicator, the
difference in luminance, to identify different objects. Hence, we terminate
the recursion when the latest hit point reads a luminance different from the
first hit or the maximum number of recursions is reached.

##  4 IMPLEMENTATION

To implement our hybrid MBlur approach, we made use of the NVIDIA Falcor real-
time rendering framework (Benty et al.,, 2020) on DirectX 12 for ray tracing
acceleration. The scenes used for testing our approach are The Modern Living
Room (commonly referred to as Pink Room) (Wig42,, 2014), UE4 Sun Temple (Epic
Games,, 2017) and the interior scene of Amazon Lumberyard Bistro (Bistro
Interior) (Amazon Lumberyard,, 2017).

For our post-process tile-dilate pass, we followed McGuire et al., (2012)’s
approach of taking a neighbourhood size of $n=3$ but found that a tile size of
$m=40$ generally worked better than $m=20$ for us in our test scenes with
fast-moving foreground objects. This is because the tile length scales the
amount of blur we can observe in the final image, and we require a substantial
amount of blur to expose and inspect the quality of semi-transparencies of
foreground silhouettes through which background geometry is revealed. Hence,
we also tested our scenes at long exposure times or low shutter speeds of
$1/60$ s, against high frame rates of 100 to 300 fps so as to scale our per-
exposure velocities effectively. As for our sample count, we took 15 samples
along the magnitude of the dominant neighbourhood velocity as recommended in
McGuire et al., (2012). Our SOFT_Z_EXTENT was 3 cm (Pink Room and Sun Temple)
and 5 mm (Bistro Interior), which are also within the suggested range of
values from McGuire et al., (2012).

As for our ray mask, we employed a strict edge threshold $e$ of 0.9 (Pink
Room), 0.98 (Sun Temple) and 0.96 (Bistro Interior) which were effective in
detecting the intricate edges of scene objects while rejecting non-edges well.
For the ray tracing pass, we limited the recursion level to 5. However, for
complex scenes with concave objects that lead to a significant amount of self-
occlusion, this level can be increased.

When the target pixel is deeper than its sample by at least SOFT_Z_EXTENT in
the post-process pass, we artificially magnify $w_{f}$ by 30 for a smooth
colour transition from the object’s edge to its outer blur. On the other hand,
we deem the pixel to be in the inner blur region based on whether it is marked
in the ray mask. If the pixel is in the mask, we also optionally magnify its
overall background colour weight ($w$ in background colour) and diminish its
foreground colour weight ($w$ in foreground colour) accordingly by the same
magnitude of 3, so background geometry can be observed more clearly through
the silhouette of foreground objects with partial occlusion.

##  5 RESULTS

Our hybrid MBlur approach (d) aims to improve the visual quality of the post-
process technique in McGuire et al., (2012) with reasonable additional
performance cost. Besides the original rasterized colour (a) and an adapted
version of the post-process technique at the new sampling range as shown in
Figure 3 (b), we also evaluate our approach against state-of-the-art post-
process MBlur from Unreal Engine 4 (UE4) (c), which adopts a similar technique
to McGuire et al., (2012). UE4 also produces MBlur by comparing the velocity
of each pixel to that of its neighbours (Epic Games,, 2020). The ground truth
is given by the distributed ray tracing approach from Cook et al., (1984) (e).
Our demo video (link) provides more detailed comparisons of the results.

(a)  (b)  (c)  (d)  (e)

Figure 5: Comparison of partial occlusion quality.

###  5.1 Graphics Quality Comparison

Post-process MBlur inaccurately reconstructs the background by reusing
neighbouring information available in the initial sharp rasterized image,
which creates artifacts such as mismatched patterns when the background
contributing to the inner blur is not of a uniform colour. In Figure 5, we
choose a shot from Pink Room with a moving red vase in front of a white sofa
with a pink cushion on it. For the adapted post-process MBlur from McGuire et
al., (2012), the silhouette of the cushion incorrectly terminates at the edge
of the vase. While the pink colour from the cushion should extend towards the
bottom right direction into the geometry of the vase, it is blocked by a
horizontal division created by motion vector-based sampling. This artifact is
more noticeable for UE4, where the background colour within the inner blur is
practically a linear translation from the left of the edge, as shown in the
yellow circle. However, our hybrid method samples what is behind the inner
blur of moving objects, hence we can obtain the desired background, which in
this case is the extension of the cushion silhouette in the green circle
corresponding to the ground truth.

However, it can be seen that hybrid MBlur does not achieve as much semi-
transparency as compared to the ground truth, where the background colour is
more visible within the silhouette of the vase. Nonetheless, the rendering
time of the ground truth is 13 fps at 200 rays per pixel (rpp), which is a lot
slower than 205 fps for hybrid MBlur. In practice, it is not common to use
distributed ray tracing to render MBlur in real-time as it is difficult to
meet interactive frame rates, while reducing the rpp to achieve ideal
performance will introduce a significant amount of sampling noise.

Against the ground truth, our hybrid MBlur method performs well in objective
visual metrics PSNR and SSIM when compared to other state-of-the-art post-
process methods, as presented in Table 1. It is also interesting to note that
the improved MBlur method implemented in the latest version of UE4 does not
fare as well as the basic adapted post-process method from McGuire et al.,
(2012).

Table 1: Comparison of similarity to ground truth. | PSNR | SSIM
---|---|---
Adapted Post-Process | 24.20 | 0.91
UE4 Post-Process | 12.32 | 0.68
Hybrid MBlur | 25.69 | 0.92

###  5.2 Performance

Although the Falcor framework helped facilitate the implementation of our
technique by taking care of scene loading, pipeline set-up and the creation of
ray tracing acceleration structures, the abstraction of many low-level details
from Direct3D makes it difficult to optimize rendering. However, even without
substantial optimization, we have managed to achieve relatively interactive
frame rates and pass durations, as shown in Table 2 based on shots of varying
geometric complexity in Figure 6. Our measurements are taken with the Falcor
profiling tool on an Intel Core i7-8700K CPU at 16GB RAM with an NVIDIA
GeForce RTX 2080 Ti GPU.

Table 2: Pass durations (in ms) and frame rates. Shot | Processor | PR | ST | BI
---|---|---|---|---
| CPU | 0.26 | 0.54 | 1.74
G-Buffer | GPU | 1.19 | 3.54 | 6.43
| CPU | 0.05 | 0.05 | 0.06
Ray Mask | GPU | 0.33 | 0.38 | 0.33
| CPU | 1.13 | 2.27 | 2.99
Ray Trace | GPU | 0.59 | 0.65 | 0.62
| CPU | 0.05 | 0.06 | 0.08
Tile-Dilate | GPU | 1.48 | 1.44 | 1.43
| CPU | 0.03 | 0.04 | 0.04
PP-Composite | GPU | 0.85 | 0.82 | 0.82
| CPU | 3.14 | 4.67 | 3.48
Others | GPU | 0.39 | 0.42 | 0.29
| CPU | 4.66 | 7.63 | 8.39
Total Duration | GPU | 4.83 | 7.25 | 9.92
Frame Rate | 205 | 148 | 112

(a) Pink Room (PR) (b) Sun Temple (ST) (c) Bistro Interior (BI)

Figure 6: Shots used for profiling.

Hybrid MBlur, which contains an additional ray reveal process, is expectedly
slower than the adapted post-process McGuire et al., (2012) approach that has
a frame rate of 295 fps for PR. As seen in Table 2, the creation of the ray
mask and the ray trace pass are the major components of the ray reveal
algorithm. The ray trace pass increases in duration on the CPU with the
geometric complexity of each shot. As such, it is expected that the G-Buffer
pass aligns with this trend as it is where deferred shading is carried out.
However, the durations of the other passes appear to be independent of this
geometric complexity.

###  5.3 Limitations and Future Work

Since our work is focused on the main idea of real-time hybrid MBlur, some
common spatial sampling constraints in MBlur are used for simplicity
considerations. These constraints include linear inter-frame motion and stable
lighting within the exposure time, as well as moderate screen space velocity
for a reasonable tile size. However, it is possible to accommodate nonlinear
MBlur at low cost with a curve-sampling scatter approach, as demonstrated in
Guertin and Nowrouzezahrai, (2015).

Additionally, the ideal indicator for termination in our ray reveal algorithm
should be the difference in velocity and not luminance. However, it is
inefficient to check the velocity of a hit point during the ray tracing
process. Hence, as a future improvement to our approach, we hope to
incorporate GeometryIndex from DirectX Raytracing Tier 1.1, which will enable
the ray tracing shader to distinguish geometries. This will be more suitable
than luminance in scenes with multiple overlapping moving objects of the same
luminance value.

Moreover, it is possible to improve the efficiency of our pipeline by
restricting the computation of velocities to a user-defined depth for the
scene, if geometry movement is localized. We also intend to integrate hybrid
MBlur with other real-time hybrid rendering effects, such as depth of field
(Tan et al., 2020a, ) where we mitigate similar problems of partial occlusion
from post-processing approaches.

##  6 CONCLUSION

We present a real-time hybrid motion blur rendering technique that produces
more accurate partial occlusion semi-transparencies on the silhouettes of
moving foreground geometry as compared to state-of-the-art post-processing
techniques. By leveraging hardware-accelerated ray tracing within a ray mask,
we have achieved relatively interactive frame rates for real-time rendering in
games without extensive optimization. We aim to integrate and optimize
multiple hybrid rendering techniques including depth of field into our hybrid
rendering engine, which will be open-sourced for the benefit of the research
community and industry.

## ACKNOWLEDGEMENTS

We thank Wyman, (2018) for the Falcor scene file of The Modern Living Room (CC
BY) as well as the NVIDIA ORCA for that of UE4 Sun Temple (CC BY-NC-SA) and
Amazon Lumberyard Bistro (CC BY). This work is supported by the Singapore
Ministry of Education Academic Research grant T1 251RES1812, “Dynamic Hybrid
Real-time Rendering with Hardware Accelerated Ray-tracing and Rasterization
for Interactive Applications”.

## REFERENCES

  * Akenine-Möller et al., (2007) Akenine-Möller, T., Munkberg, J., and Hasselgren, J. (2007).  Stochastic rasterization using time-continuous triangles.  In Segal, M. and Aila, T., editors, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware, GH ’07, pages 7–16, Goslar, DEU. The Eurographics Association.
  * Amazon Lumberyard, (2017) Amazon Lumberyard (2017).  Amazon lumberyard bistro, open research content archive (orca).
  * Andrade et al., (2014) Andrade, P., Sabino, T. L., and Clua, E. (2014).  Towards a heuristic based real time hybrid rendering - a strategy to improve real time rendering quality using heuristics and ray tracing.  In Proceedings of the 9th International Conference on Computer Vision Theory and Applications - Volume 3: VISAPP, (VISIGRAPP 2014), volume 3, pages 12–21. The Institute for Systems and Technologies of Information, Control and Communication (INSTICC), SciTePress.
  * Beck et al., (1981) Beck, S., Bernstein, A. C., Danch, D., and Fröhlich, B. (1981).  Cpu-gpu hybrid real time ray tracing framework.  volume 0, pages 1–8. The Eurographics Association and Blackwell Publishing Ltd.
  * Benty et al., (2020) Benty, N., Yao, K.-H., Clarberg, P., Chen, L., Kallweit, S., Foley, T., Oakes, M., Lavelle, C., and Wyman, C. (2020).  The Falcor rendering framework.
  * Cabeleira, (2010) Cabeleira, J. P. G. (2010).  Combining rasterization and ray tracing techniques to approximate global illumination in real-time.  Master’s thesis, Portugal.
  * Catmull, (1984) Catmull, E. (1984).  An analytic visible surface algorithm for independent pixel processing.  SIGGRAPH Comput. Graph., 18(3):109–115.
  * Chalmers et al., (2006) Chalmers, A., Debattista, K., and dos Santos, L. P. (2006).  Selective rendering: Computing only what you see.  In Proceedings of the 4th International Conference on Computer Graphics and Interactive Techniques in Australasia and Southeast Asia, GRAPHITE ’06, pages 9–18, New York, NY, USA. ACM.
  * Chen and Liu, (2007) Chen, C.-C. and Liu, D. S.-M. (2007).  Use of hardware z-buffered rasterization to accelerate ray tracing.  In Proceedings of the 2007 ACM Symposium on Applied Computing, SAC ’07, pages 1046–1050, New York, NY, USA. ACM.
  * Choi and Oh, (2017) Choi, J. and Oh, K. (2017).  Real-time motion blur based on per pixel fragment list.  In Proceedings of the International Conference on Research in Adaptive and Convergent Systems, RACS ’17, pages 132–135, New York, NY, USA. Association for Computing Machinery.
  * Cook, (1986) Cook, R. L. (1986).  Stochastic sampling in computer graphics.  ACM Trans. Graph., 5(1):51–72.
  * Cook et al., (1987) Cook, R. L., Carpenter, L., and Catmull, E. (1987).  The reyes image rendering architecture.  SIGGRAPH Comput. Graph., 21(4):95–102.
  * Cook et al., (1984) Cook, R. L., Porter, T., and Carpenter, L. (1984).  Distributed ray tracing.  SIGGRAPH Comput. Graph., 18(3):137–145.
  * Dayal et al., (2005) Dayal, A., Woolley, C., Watson, B., and Luebke, D. (2005).  Adaptive frameless rendering.  In ACM SIGGRAPH 2005 Courses, SIGGRAPH ’05, New York, NY, USA. ACM.
  * Epic Games, (2017) Epic Games (2017).  Unreal engine sun temple, open research content archive (orca).
  * Epic Games, (2020) Epic Games (2020).  Unreal Engine 4 Documentation: 1.12 - Motion Blur.
  * Fatahalian et al., (2009) Fatahalian, K., Luong, E., Boulos, S., Akeley, K., Mark, W. R., and Hanrahan, P. (2009).  Data-parallel rasterization of micropolygons with defocus and motion blur.  In Proceedings of the Conference on High Performance Graphics 2009, HPG ’09, pages 59–68, New York, NY, USA. Association for Computing Machinery.
  * Grant, (1985) Grant, C. W. (1985).  Integrated analytic spatial and temporal anti-aliasing for polyhedra in 4-space.  SIGGRAPH Comput. Graph., 19(3):79–84.
  * Gribel et al., (2011) Gribel, C. J., Barringer, R., and Akenine-Möller, T. (2011).  High-quality spatio-temporal rendering using semi-analytical visibility.  ACM Trans. Graph., 30(4).
  * Gribel et al., (2010) Gribel, C. J., Doggett, M., and Akenine-Möller, T. (2010).  Analytical motion blur rasterization with compression.  In Doggett, M., Laine, S., and Hunt, W., editors, Proceedings of the Conference on High Performance Graphics, HPG ’10, pages 163–172, Goslar, DEU. The Eurographics Association.
  * Gribel et al., (2013) Gribel, C. J., Munkberg, J., Hasselgren, J., and Akenine-Möller, T. (2013).  Theory and analysis of higher-order motion blur rasterization.  In Proceedings of the 5th High-Performance Graphics Conference, HPG ’13, pages 7–15, New York, NY, USA. Association for Computing Machinery.
  * Guertin and Nowrouzezahrai, (2015) Guertin, J.-P. and Nowrouzezahrai, D. (2015).  High Performance Non-linear Motion Blur.  In Lehtinen, J. and Nowrouzezahrai, D., editors, Eurographics Symposium on Rendering - Experimental Ideas & Implementations. The Eurographics Association.
  * Haeberli and Akeley, (1990) Haeberli, P. and Akeley, K. (1990).  The accumulation buffer: Hardware support for high-quality rendering.  In Proceedings of the 17th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’90, pages 309–318, New York, NY, USA. Association for Computing Machinery.
  * Halton, (1970) Halton, J. H. (1970).  A retrospective and prospective survey of the monte carlo method.  SIAM Review, 12(1):1–63.
  * Hertel et al., (2009) Hertel, S., Hormann, K., and Westermann, R. (2009).  A hybrid gpu rendering pipeline for alias-free hard shadows.  In Ebert, D. and Krüger, J., editors, Eurographics 2009 Areas Papers, pages 59–66, München, Germany. The Eurographics Association.
  * Hou et al., (2010) Hou, Q., Qin, H., Li, W., Guo, B., and Zhou, K. (2010).  Micropolygon ray tracing with defocus and motion blur.  ACM Trans. Graph., 29(4).
  * Jimenez, (2014) Jimenez, J. (2014).  Advances in real-time rendering in games, part i: Next generation post processing in call of duty: Advanced warfare.
  * Korein and Badler, (1983) Korein, J. and Badler, N. (1983).  Temporal anti-aliasing in computer generated animation.  SIGGRAPH Comput. Graph., 17(3):377–388.
  * Lauterbach and Manocha, (2009) Lauterbach, C. and Manocha, D. (2009).  Fast hard and soft shadow generation on complex models using selective ray tracing.  Technical report, University of North Carolina at Chapel Hill.
  * Leimkühler et al., (2018) Leimkühler, T., Seidel, H.-P., and Ritschel, T. (2018).  Laplacian kernel splatting for efficient depth-of-field and motion blur synthesis or reconstruction.  ACM Trans. Graph., 37(4).
  * Macedo et al., (2018) Macedo, D. V. D., Serpa, Y. R., and Rodrigues, M. A. F. (2018).  Fast and realistic reflections using screen space and gpu ray tracing—a case study on rigid and deformable body simulations.  Comput. Entertain., 16(4).
  * Marrs et al., (2018) Marrs, A., Spjut, J., Gruen, H., Sathe, R., and McGuire, M. (2018).  Adaptive temporal antialiasing.  In Proceedings of the Conference on High-Performance Graphics, HPG ’18, pages 1:1–1:4, New York, NY, USA. ACM.
  * McGuire et al., (2010) McGuire, M., Enderton, E., Shirley, P., and Luebke, D. (2010).  Real-time stochastic rasterization on conventional gpu architectures.  In Proceedings of the Conference on High Performance Graphics, HPG ’10, pages 173–182, Goslar, DEU. The Eurographics Association.
  * McGuire et al., (2012) McGuire, M., Hennessy, P., Bukowski, M., and Osman, B. (2012).  A reconstruction filter for plausible motion blur.  In Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, I3D ’12, pages 135–142, New York, NY, USA. ACM.
  * NVIDIA Corporation, (2021) NVIDIA Corporation (2021).  Nvidia ampere ga102 gpu architecture.  White paper.
  * Potmesil and Chakravarty, (1983) Potmesil, M. and Chakravarty, I. (1983).  Modeling motion blur in computer-generated images.  SIGGRAPH Comput. Graph., 17(3):389–399.
  * Ritchie et al., (2010) Ritchie, M., Modern, G., and Mitchell, K. (2010).  Split second motion blur.  In ACM SIGGRAPH 2010 Talks, SIGGRAPH ’10, pages 17:1–17:1, New York, NY, USA. ACM.
  * Rosado, (2007) Rosado, G. (2007).  Chapter 27. motion blur as a post-processing effect.  In Nguyen, H., editor, GPU Gems 3, chapter 27. Addison-Wesley Professional, 1st edition.
  * Sattlecker and Steinberger, (2015) Sattlecker, M. and Steinberger, M. (2015).  Reyes rendering on the gpu.  In Proceedings of the 31st Spring Conference on Computer Graphics, SCCG ’15, pages 31–38, New York, NY, USA. Association for Computing Machinery.
  * Sousa, (2013) Sousa, T. A. (2013).  Advances in real-time rendering in games, part ii: Graphics gems from cryengine 3.
  * Sung et al., (2002) Sung, K. H., Pearce, A., and Wang, C. (2002).  Spatial-temporal antialiasing.  IEEE Transactions on Visualization and Computer Graphics, 8(2):144–153.
  * (42) Tan, Y. W., Chua, N., Biette, N., and Bhojan, A. (2020a).  Hybrid dof: Ray-traced and post-processed hybrid depth of field effect for real-time rendering.  In ACM SIGGRAPH 2020 Posters, SIGGRAPH ’20, New York, NY, USA. Association for Computing Machinery.
  * (43) Tan, Y. W., Cui, X., and Bhojan, A. (2020b).  Hybrid mblur: Using ray tracing to solve the partial occlusion artifacts in real-time rendering of motion blur effect.  In ACM SIGGRAPH 2020 Posters, SIGGRAPH ’20, New York, NY, USA. Association for Computing Machinery.
  * Whitted, (1979) Whitted, T. (1979).  An improved illumination model for shaded display.  SIGGRAPH Comput. Graph., 13(2):14–.
  * Wig42, (2014) Wig42 (2014).  The modern living room.
  * Woop et al., (2017) Woop, S., Áfra, A. T., and Benthin, C. (2017).  Stbvh: A spatial-temporal bvh for efficient multi-segment motion blur.  In Proceedings of High Performance Graphics, HPG ’17, New York, NY, USA. Association for Computing Machinery.
  * Wyman, (2018) Wyman, C. (2018).  Introduction to directx raytracing.  In ACM SIGGRAPH 2018 Courses, SIGGRAPH ’18.
  * Yang et al., (2019) Yang, L., Zhdan, D., Kilgariff, E., Lum, E. B., Zhang, Y., Johnson, M., and Rydgård, H. (2019).  Visually lossless content and motion adaptive shading in games.  Proc. ACM Comput. Graph. Interact. Tech., 2(1).

## APPENDIX

### Post-process Sampling Range

McGuire et al., (2012) uses the dominant velocity within a neighbourhood of
pixels as a heuristic. It first produces a per-exposure velocity from an
inter-frame motion vector, then applies a tile-dilate pass to select the
dominant velocity in the neighbourhood with the largest magnitude. Here, the
per-pixel velocities are clamped at the length of each tile for the tile-
dilate pass to capture the maximum velocity from all possible contributions,
preventing tiling artifacts.

For the tile-dilate pass, tile-dominant velocities are first selected for
tiles of length $m$ in pixel units, where $m$ is a common factor of the width
and height of the image buffer resolution. Then, neighbour-dominant velocities
are selected for kernels of length $n$ in tile units. For example, if we take
$m$ = 40, the size of each tile is hence $40\times 40=1600$ pixels. If we then
dilate each tile with $n$ = 3 based on its 8 direct neighbours, our dilated
tile will take the maximum pixel velocity from 9 tiles $\times$ 1600
pixels/tile = 14400 pixels in total.

Compared to approaches that use per-pixel velocities directly for gathering
like Ritchie et al., (2010), this dominant neighbour velocity approach
prevents issues such as sharp silhouettes as well as moving objects shrunk in
size, as illustrated in McGuire et al., (2012). Following its idea, the
direction of sampling at each pixel is along the dominant velocity of its
neighbourhood, and the range of samples is within one magnitude of this
velocity.

### Post-process Sample Contribution

McGuire et al., (2012) performs a weighted average $w$ of all corresponding
samples for each target pixel.

$w=w_{f}+w_{b}+w_{s}{}$ (5)
$w_{f}=\textnormal{{saturate(}}\textnormal{\emph{$1+z$}}\textnormal{{)}}\times\textnormal{{saturate(}}\textnormal{\emph{$1-\frac{\Delta
s}{v_{s}}$}}\textnormal{{)}}$ (6)
$w_{b}=\textnormal{{saturate(}}\textnormal{\emph{$1-z$}}\textnormal{{)}}\times\textnormal{{saturate(}}\textnormal{\emph{$1-\frac{\Delta
s}{v_{t}}$}}\textnormal{{)}}$ (7)
$w_{s}=\textnormal{{cylinder(}}\textnormal{\emph{$v_{s}$, $\Delta
s$}}\textnormal{{)}}\times\textnormal{{cylinder(}}\textnormal{\emph{$v_{t}$,
$\Delta s$}}\textnormal{{)}}\times 2$ (8)

where

$z=\frac{z_{t}-z_{s}}{\rm SOFT\\_Z\\_EXTENT}$ (9)
$\textnormal{{cylinder(}}\textnormal{\emph{$v$,
$s$}}\textnormal{{)}}=1-\textnormal{{smoothstep(}}\textnormal{\emph{$0.95v$,
$1.05v$, $s$}}\textnormal{{)}}$ (10)

In the above formulae, $z$ represents the extent that the target pixel is
deeper into the scene than its sample (negative when the pixel is shallower),
while $\Delta s$ refers to the distance between the screen space positions of
the target pixel and its sample. $v_{t}$ and $v_{s}$ are the screen space
speeds of the target pixel and its sample respectively, while $z_{t}$ and
$z_{s}$ are their camera space depths. SOFT_Z_EXTENT is a positive-valued
scene-dependent variable as introduced in McGuire et al., (2012) used for the
classification of samples into the foreground or background of the target
pixel.

#### Case 1: Blurry Sample in Front of Any Target

$w_{f}$ considers the first case where outer blur is present: a shallower
sample of speed larger or equal to its offset from the target pixel in screen
space can contribute to the pixel’s colour as part of the foreground. The
sample contributes as foreground by covering the target pixel within the
exposure time. On the other hand, since a sample deeper than the target pixel
stands a higher chance to be blocked during the exposure time, the first
factor in Equation 6 smoothly filters out contribution from deeper samples.
Given that faster pixels also contribute less for each unit (in our case it is
the length of one pixel) in their trail, a comparison between the sample’s
speed and its distance to the target pixel is performed as the second factor
of Equation 6.

#### Case 2: Any Sample behind Blurry Target

As for inner blur, the target pixel is moving and deeper samples within its
velocity range are selected to fill the transparency left by it. Hence, for
$w_{b}$, the depth comparison is done reversely to filter out shallower
samples. Since Jimenez, (2014) illustrates that the edge of a motion-blurred
object should be a smooth gradient, a comparison between the target pixel’s
speed and its distance to the sample is also performed as part of the second
factor of Equation 7 to assign a lower weight to further samples.

(a) $w_{s}$ excluded (b) $w_{s}$ included

Figure 7: Specular highlight in McGuire et al., (2012) post-processed MBlur
(one-directional).

#### Case 3: Simultaneously Blurry Target and Sample

A sample at any depth can contribute to the target pixel’s colour as part of
the foreground or background when both the sample and the pixel are located in
each other’s velocity range. $w_{s}$ blurs the target pixel and its sample
into each other as a supplement to the cases not handled well by the first two
terms in Equation 5. Since further samples have been assigned lower weights in
$w_{f}$ and $w_{b}$, the area of the resulting MBlur for regions of high
variance appears to shrink as the target pixel gets further from these
regions. For instance, in the case of specular highlights, as shown in Figure
7, the resulting blur appears to be triangular-shaped with the base at the
exact specular highlight in the sharp rasterized image, while the desirable
case should be rectangular-shaped. Since $w_{s}$ will produce a positive value
when the distance between the target pixel and its sample is not significantly
higher than the speed of either of them, it creates a more reasonable blur
effect by enlarging the shrinking region.


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

Qiang Zou<EMAIL_ADDRESS>Lizhen Zhu  State Key Laboratory of CAD&CG,
Zhejiang University, Hangzhou, 310027, China

###### Abstract

This paper presents a learning-based method to solve the traditional
parameterization and knot placement problems in B-spline approximation.
Different from conventional heuristic methods or recent AI-based methods, the
proposed method does not assume ordered or fixed-size data points as input.
There is also no need for manually setting the number of knots. It casts the
parameterization and knot placement problems as a sequence-to-sequence
translation problem, a generative process automatically determining the number
of knots, their placement, parameter values, and their ordering. Once trained,
SplineGen demonstrates a notable improvement over existing methods, with a one
to two orders of magnitude increase in approximation accuracy on test data.

###### keywords:

CAD; B-spline; Approximation; Parameterization; Knot Placement; Generative
Modeling

††journal: Elsevier

##  1 Introduction

Generative artificial intelligent (AI) models have proven to be very powerful
in natural language processing, computer vision, and computer graphics [1]. In
particular, there is emerging use for the synthesis of 3D shapes lately, such
as meshGPT [2], SolidGen [3], and ComplexGen [4]. However, there has been
limited use of these models, or even the broader deep learning models, in
computer-aided design (CAD) modeling. This is mainly because those models are
probabilistic (and therefore inherent uncertainty therein), while all CAD
algorithms require high certainty and accuracy. This work aims to show that,
despite this gap, generative models offer considerable potential for improving
classic CAD algorithms by replacing the expertise-based, heuristic parts in
classic algorithms with data-driven methods.

Approximating a set of data points with a B-spline curve [5] is the algorithm
of choice. It is a fundamental algorithm in CAD/CAM, underlying many high-
level modeling operations such as boundary evaluation, Booleans, features,
tool path generation, reverse engineering, shape optimization etc. [6, 7, 8,
9, 10, 11, 12, 13, 14, 15]. The approximation involves three main procedures:
parametrization, knot placement, and approximation error minimization [16].
The first two are prerequisites for running the third. Parametrization means
associating each data point with a parameter value. Knot placement refers to
the choice of the number of knots and their locations for constructing spline
bases. It is well known that the parameterization and knot placement have a
significant impact on the final approximation accuracy [17].

Existing parameterization and knot placement methods basically fall under two
different strategies. The first strategy heuristically chooses a
parameterization and knot placement a posteriori for given data points.
Typical examples include uniform parameterization [16], chord length
parameterization [18], centripetal parameterization [19], and Foley-Nielson
parameterization [20], among many others [21]. For knot placement, uniform
knots [16], the knot placement technique (KTP) [16] and the new KTP (NKTP)
[22] are typical examples. These methods have also been augmented by
incorporating various optimization techniques, e.g., [23]. Like all heuristic
methods, those mentioned above can provide acceptable results in many but not
all of the potential cases. The second strategy learns a neural network to
directly map data points to their corresponding parameters and knots, in an
end-to-end manner [17]. Fully connected neural networks (FCNN) [24] and
residual networks (ResNet) [17] have been used for this purpose so far.
Reduced approximation errors were demonstrated, but the application of these
methods is consistently limited to ordered and fixed-size data points.

In this work, we propose to cast the problems of parameterization and knot
placement as a generative sequence-to-sequence translation problem, where
unorganized input becomes possible. Rather than directly adopting existing
networks (e.g., FCNN and ResNet), this work develops an extended version of
the existing Transformer network [1] to meet the specific needs of B-spline
approximation. The new generative model, SplineGen, can automatically
determine the number of knots, their placement, parameter values, and their
ordering. More specifically, SplineGen has the following features:

  1. (1)

Size-independent. Restricting input data points, parameters, and knots to a
fixed size would limit the practical significance of learning-based methods.
The point partitioning trick as used in [17, 24] may help but cannot solve the
problem altogether. By contrast, the proposed method provides a principled way
to handle variable-size input data points, parameters, and knots through the
use of autoregressive models.

  2. (2)

Point permutation invariant. In many practical scenarios, input points may not
be in a well-ordered position as required by most existing methods. As a
result, a B-spline approximation-oriented neural network should exhibit
permutation invariance over the input. That is, the output parameters and
knots remain unchanged when input data points are permuted. This problem is to
be solved by extending the transformer network with an additional self-
organization module.

  3. (3)

Parameter-knot alignment. Many existing methods consider parameterization and
knot placement problems separately. However, they correlate highly with each
other, and lower approximate errors will be achieved if they work in a
cooperative way, refer to Section 3 for more details. This necessitates a
neural network that can align the generation of parameters and knots. To do
so, this work uses a shared autoencoder model to learn shared point embeddings
for both tasks. Furthermore, we add a new module called internal cross-
attention to the parameter decoder and the knot decoder to explicitly align
parameter generation and knot generation.

  4. (4)

High robustness. For a set of input data points, removing some of them or
adding more sample points from the same curve should not affect the output
significantly, if not completely identical. This simply means robustness
towards data point removal or addition (of course, without changing the
unknown underlying curve). To achieve this, we further extend the transformer
network by adding a masking mechanism for simulating point removal/addition
and predicting the corresponding output masks.

The remaining content is organized as follows: Sec. 2 provides a review of
related research studies. Sec. 3 states the problem to be solved, and Sec. 4
elaborates the proposed SplineGen network. Examples and comparisons with
existing methods are provided in Sec. 5, followed by conclusions in Sec. 6.

##  2 Related Work

Spline techniques are fundamental to the modeling of curves, surfaces,
structures, as well as semantic shapes such as tool paths, in CAD/CAM
applications [25, 26, 27, 28, 29, 30, 31, 32, 33]. For this reason, a ton of
related studies have been presented in the literature. They may be divided
into two categories: the traditional and the recent learning-based. Because
there have already been excellent reviews on the method in the traditional
category, e.g., [17, 18], this paper will only gives a brief summary of those
methods.

###  2.1 Traditional methods

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.

###  2.2 Learning-based methods

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.

##  3 Problem statement

Mathematically, a B-spline curve is:

$C(u)=\sum_{i=0}^{n}N_{i,p}(u)P_{i}$ (1)

where $u$ is a varying parameter in $[0,1]$, $N_{i,p}(u),\ i=0,\dots,n,$ the
B-spline basis functions of degree $p$, and $P_{i},\ i=0,\dots,n,$ the control
points. The basis functions $N_{i,p}(u)$ are generated using a knot vector
$T=[t_{0},\dots,t_{n+p+1}]$, as follows:

$\displaystyle N_{i,0}(u)=\begin{cases}1,\quad&t_{i}\leq{u}<t_{i+1}\\\
0,\quad&otherwise\end{cases}$ (2) $\displaystyle
N_{i,p}(u)=\frac{u-t_{i}}{t_{i+p}-t_{i}}N_{i,p-1}(u)+\frac{t_{i+p+1}-u}{t_{i+p+1}-t_{i}}N_{i+1,p-1}(u)$

Approximating data points ${D_{j}},\ j=0,\dots,m,$ with a B-spline curve is to
solve the following optimization problem:

$\min_{P_{0},\dots,P_{n}}\sum_{j=0}^{m}||D_{j}-\sum_{i=0}^{n}N_{i,p}(u_{j})P_{i}||^{2}_{2}$
(3)

where $u_{j}$ is the parameter value corresponding to the data point $D_{j}$.
Constructing the mapping from $D_{j}$ to $u_{j}$ is the so-called
parameterization.

The above optimization problem is a least square problem, and its solution can
be obtained by solving the following linear system:

$(N^{T}N)P=N^{T}D$ (4)

where $P=[P_{0},\dots,P_{n}]^{T}$, and

$N=\begin{bmatrix}N_{0,p}(u_{0})&\dots&N_{n,p}(u_{0})\\\
\vdots&\ddots&\vdots\\\ N_{0,p}(u_{m})&\dots&N_{n,p}(u_{m})\end{bmatrix}$

It is obvious that the coefficient matrix $N$ is solely determined by three
factors:

  1. 1.

Parametrization. Each parameter $u_{j}$ indicates the position where to
evaluate the B-spline basis function $N_{i,p}(u_{j})$ and then determines all
entries in the $j-$row of $N$. Fig. 1a shows that parametrization can
significantly affect the final result.

  2. 2.

Knot placement. The knot vector $T$ determines each B-spline basis function
$N_{i,p}(u)$, which in turn determines all entries in the $i-$column of $N$.
Fig. 1b shows that the choice of knot positions can affect the approximation
accuracy a lot.

  3. 3.

Parameter-knot alignment. Each entry of $N$ is collectively determined by
parameters and knots. Leaning towards either side will not give good results.
Fig. 1c shows that, if these two are not aligned well, a high approximation
error occurs.

Besides the above three factors, it is also needed to determine the number of
knots, adaptively. When input data points do not assume any ordering a priori,
the parameters’ order also needs to be determined automatically. This does not
mean sorting the parameter values, which is simple, but organizing the output
parameters in a way consistent with the input data points.

Figure 1: Influence of parameters, knots, and their alignment on approximation
accuracy: (a) results from two different parameters; (b) results from two
different knots; and (c) results of matched (top) and unmatched (bottom)
cases.

##  4 Methods

###  4.1 Network architecture

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.

Figure 2: The overall architecture of SplineGen.

###  4.2 Learning point embeddings

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:

$h_{P}=\\{p_{i}\rightarrow W_{P}\times\Gamma(p_{i})\\},$

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.

Figure 3: The network for learning point embeddings. The right grayed part is
only used in the training phrase, not in the inference phrase.

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}$:

$E_{P}=\textbf{E}(h_{P};\theta_{\textbf{E}})$

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:

$\displaystyle k_{i+1}$
$\displaystyle=\bar{\textbf{D}}_{K}(\\{\hat{k}_{0},\hat{k}_{1},\dots,\hat{k}_{i}\\},\textbf{E}_{P}^{\prime};\theta_{\bar{\textbf{D}}_{K}},\theta_{\textbf{E}})$
(5) $\displaystyle p_{i+1}$
$\displaystyle=\bar{\textbf{D}}_{P}(\\{\hat{p}_{0},\hat{p}_{1},\dots,\hat{p}_{i}\\},\textbf{E}_{P}^{\prime};\theta_{\bar{\textbf{D}}_{P}},\theta_{\textbf{E}})$

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.

###  4.3 Generating knots and parameters

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.

Figure 4: The network for generating knots and parameters. Left: The pipeline
of knots and decoder generation. After random masking, the input points are
sent to a transformer encoder, yielding the point embeddings. Both the knot
decoder and parameter decoders take the embeddings for generation. Besides,
point embeddings are gathered as input of the parameter decoder. For each
layer of the parameter decoder, internal cross-attention is applied. Right:
The details of the internal cross attention. The key and value in the self-
attention module at the last layer of the knot decoder are used for the
internal cross-attention with query vectors converted from $X_{P}^{i}$. Here,
$X_{k}^{n}$ denotes the output of the last layer of the knot decoder, and
$X_{P}^{i}$ denotes the output of $i^{th}$ layer of parameter decoder.

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]:

$p_{i}=softmax((W_{Q}E^{i}_{T})^{T}\cdot W_{K}P^{\prime})$ (6)

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:

$p(I_{t}|E_{P};\theta_{\textbf{D}_{T}},W_{Q},W_{K})=\prod_{j=1}^{t}p(i_{j}|i_{0},\dots,i_{j-1},E_{P};\theta_{\textbf{D}_{T}},W_{Q},W_{K}),$
(7)

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.

###  4.4 PINN-based fine alignment

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:

$L=\max_{i=1}^{N}\|C(u_{i})-D_{i}\|_{2},$ (8)

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.

##  5 Results

###  5.1 Setup

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.

###  5.2 Evaluation Metrics

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:

$\max_{i=1}^{N}\|C(t_{i})-D_{i}\|_{2}$

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

$\frac{1}{N}\sum_{i=1}^{N}\|C(t_{i})-D_{i}\|_{2}$

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:

$\max\left\\{\max_{p\in P}\min_{q\in Q}\|p-q\|_{2},\max_{q\in Q}\min_{p\in
P}\|p-q\|_{2}\right\\}$

Figure 5: Results of 2D parametrization, knot placement, and B-spline
approximation. Figure 6: Results of 3D parametrization, knot placement, and
B-spline approximation. Figure 7: Results of approximating complex input data
points. These shapes are rarely seen in practice, and they are only used to
show the capability of SplineGen.

###  5.3 Examples

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.

###  5.4 Ablation Studies

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 1: Stats of ablation studies. Model |  Param loss |  Ordering loss
---|---|---
All |  8.14e-3 |  3.18e-2
w.o. Cross- attention |  1.54e-2 |  3.38e-2
w.o. Shared encoder |  9.90e-3 |  3.58e-2
w.o. Masking |  8.68e-3 |  3.83e-2
|  |
Table 2: Quantitative comparisons with existing methods, both learning-based methods and classical ones. Model |  Max Error |  MSE |  Hausdoff
---|---|---|---
SplineGen |  8.66e-3 |  2.81e-3 |  8.51e-3
Jüttler [17] |  7.71e-2 |  2.48e-2 |  5.54e-2
PARNET [24] |  1.01e-1 |  2.24e-2 |  5.84e-2
Centripetal+DOM |  1.55e-1 |  8.04e-3 |  4.50e-2
Chord+DOM |  1.65e-1 |  1.01e-2 |  4.48e-2
Centripetal+Uniform |  6.01e-1 |  3.91e-2 |  1.44e-1
Chord+Uniform |  6.04e-1 |  4.11e-2 |  1.47e-1
Centripetal+KTP |  1.61e-1 |  1.21e-2 |  5.07e-2
Chord+KTP |  1.70e-1 |  1.04e-2 |  4.50e-2
Centripetal+NKTP |  1.57e-1 |  1.08e-2 |  4.71e-2
Chord+NKTP |  1.67e-1 |  9.06e-3 |  4.66e-2
|  |  |
Table 3: Sampling comparisons with existing methods on the curves of Fig. 8. Model | Curve 1 | Curve 2 | Curve 3 | Curve 4
---|---|---|---|---
|  Max |  Mse |  Hsdff |  Max |  Mse |  Hsdff |  Max |  Mse |  Hsdff |  Max |  Mse |  Hsdff
SplineGen |  1.2e-2 |  2.7e-3 |  1.2e-2 |  1.1e-2 |  4.9e-3 |  1.1e-2 |  9.1e-3 |  3.3e-3 |  7.7e-3 |  1.0e-2 |  4.7e-3 |  1.0e-2
Jüttler [17] |  4.7e-1 |  2.9e-1 |  8.4e-2 |  4.2e-1 |  2.2e-1 |  8.4e-2 |  3.8e-1 |  1.2e-1 |  8.0e-2 |  3.6e-1 |  2.0e-1 |  6.9e-2
PARNET [24] |  3.6e-2 |  1.2e-2 |  3.6e-2 |  6.5e-2 |  1.9e-2 |  4.5e-2 |  8.8e-2 |  1.7e-2 |  8.8e-2 |  4.9e-1 |  3.4e-2 |  2.0e-1
Centri + DOM |  2.8e-2 |  8.9e-3 |  2.8e-2 |  5.0e-2 |  1.3e-2 |  5.0e-2 |  2.3e-2 |  5.2e-3 |  2.3e-2 |  5.1e-1 |  2.2e-2 |  2.0e-1
Chord + DOM |  6.5e-1 |  2.6e-2 |  7.4e-2 |  4.7e-2 |  1.2e-2 |  4.7e-2 |  6.7e-1 |  3.0e-2 |  1.1e-1 |  2.6e-2 |  8.9e-3 |  2.6e-2
Centri + Uniform |  3.3e-2 |  7.9e-3 |  3.3e-2 |  3.1e-2 |  8.8e-3 |  3.1e-2 |  9.3e-3 |  3.2e-3 |  9.3e-3 |  5.1e-1 |  1.8e-2 |  2.0e-1
Chord + Uniform |  6.5e-1 |  2.6e-2 |  7.4e-2 |  3.3e-2 |  8.2e-3 |  3.3e-2 |  6.7e-1 |  2.7e-2 |  1.1e-1 |  1.9e-2 |  5.1e-3 |  1.9e-2
Centri + KTP |  3.6e-2 |  1.3e-2 |  3.6e-2 |  5.2e-2 |  1.5e-2 |  5.2e-2 |  2.8e-2 |  6.7e-3 |  2.8e-2 |  5.1e-1 |  2.2e-2 |  2.0e-1
Chord + KTP |  6.5e-1 |  3.1e-2 |  7.7e-2 |  5.4e-2 |  1.4e-2 |  5.4e-2 |  6.7e-1 |  2.7e-2 |  1.0e-1 |  3.3e-2 |  1.0e-2 |  3.3e-2
Centri + NKTP |  3.0e-2 |  1.0e-2 |  3.0e-2 |  4.7e-2 |  1.3e-2 |  4.7e-2 |  2.4e-2 |  6.9e-3 |  2.4e-2 |  5.1e-1 |  2.2e-2 |  2.0e-1
Chord + NKTP |  6.5e-1 |  2.8e-2 |  7.4e-2 |  4.5e-2 |  1.2e-2 |  4.5e-2 |  6.7e-1 |  2.7e-2 |  1.1e-1 |  2.3e-2 |  9.6e-3 |  2.3e-2
|  |  |  |  |  |  |  |  |  |  |  |

###  5.5 Comparisons

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.

Figure 8: Comparisons of Spline with various existing methods on curves from
Fig. 5.

###  5.6 Discussion and limitations

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.

##  6 Conclusion

A generative model called SplineGen has been presented to solve the
traditional parameterization and knot placement problems in B-spline
approximation. The main features of this model include input data point size-
independent, point permutation invariant, aligned knots and parameters, and
robustness, cumulatively giving a highly accurate parameterization and knot
placement method. These features are essentially attained by casting the
parameterization and knot placement problems as a sequence-to-sequence
translation problem, together with several extensions to the existing
transformer network to account for the special needs of parameterization and
knot placement. A notable improvement over existing methods has been
demonstrated in various experiments.

It should, however, be noted that SplineGen only represents a first step
towards generative spline modeling, and much more work remains to be done.
Most notably, extending SplineGen to the problem of surface fitting of
unorganized points is among the most important improvement directions. Our
preliminary results show that the primary challenge in this extension is to
handle scattered data points assuming no tensor product grids or rectangular
topology (i.e., the underlying surfaces are trimmed splines). There is no
obvious solution to this challenge, and this seems to be the main reason why
there is no successful application of learning-based methods to surface
fitting.

For the current SplineGen, there is still room for improvement. During the
implementation, it was found that a small error in the parameter-point
associative module could yield a large error in the final results. This is
mainly because SplineGen uses a global way to generate the associativity. This
will have issues when the number of input data points is large. For such
cases, a parameter-point associative network that can attention to local
neighborhoods is preferred. Then those local associativity can be assembled to
attain the overall associativity. Developing such a network module is
practically beneficial. Another interesting improvement lies in controlling
the distribution of generated parameters. It is known that good
parameterization distributes parameters evenly in individual knot spans;
otherwise, numerical issues would happen when solving Eq. (4). Incorporating
this knowledge into SplineGen is among the research studies to be carried out
in the future.

## Acknowledgements

This work has been funded by NSF of China (No. 62102355), the “Pioneer” and
“Leading Goose” R&D Program of Zhejiang Province (No. 2024C01103), NSF of
Zhejiang Province (No. LQ22F020012), and the Fundamental Research Funds for
the Zhejiang Provincial Universities (No. 2023QZJH32).

## References

## References

  * [1] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, I. Polosukhin, Attention is all you need, in: Advances in neural information processing systems, Vol. 30, 2017.
  * [2] Y. Siddiqui, A. Alliegro, A. Artemov, T. Tommasi, D. Sirigatti, V. Rosov, A. Dai, M. Nießner, MeshGPT: Generating triangle meshes with decoder-only transformers, arXiv preprint arXiv:2311.15475.
  * [3] P. K. Jayaraman, J. G. Lambourne, N. Desai, K. Willis, A. Sanghi, N. J. W. Morris, SolidGen: An autoregressive model for direct B-rep synthesis, in: Transactions on Machine Learning Research, 2023.
  * [4] H. Guo, S. Liu, H. Pan, Y. Liu, X. Tong, B. Guo, ComplexGen: CAD reconstruction by B-rep chain complex generation, ACM Transactions on Graphics 41 (4) (2022) 1–18.
  * [5] C. De Boor, On calculating with b-splines, Journal of Approximation theory 6 (1) (1972) 50–62.
  * [6] I. Stroud, H. Nagy, Solid modelling and CAD systems: how to survive a CAD system, Springer Science & Business Media, 2011.
  * [7] Q. Zou, H.-Y. Feng, S. Gao, Variational direct modeling: A framework towards integration of parametric modeling and direct modeling in cad, Computer-Aided Design 157 (2023) 103465.
  * [8] S. Liu, T. Liu, Q. Zou, W. Wang, E. L. Doubrovski, C. C. Wang, Memory-efficient modeling and slicing of large-scale adaptive lattice structures, Journal of Computing and Information Science in Engineering 21 (6) (2021) 061003.
  * [9] Q. Zou, H.-Y. Feng, Push-pull direct modeling of solid CAD models, Advances in Engineering Software 127 (2019) 59–69.
  * [10] H. Wang, Q. Zou, H. Lin, A quasi-optimal shape design method for electromagnetic scatterers based on nurbs surfaces and filter-enhanced gwo, IEEE Transactions on Antennas and Propagation.
  * [11] Q. Zou, Length-optimal tool path planning for freeform surfaces with preferred feed directions based on Poisson formulation, Computer-Aided Design 139 (2021) 103072.
  * [12] Q. Zou, J. Zhang, B. Deng, J. Zhao, Iso-level tool path planning for free-form surfaces, Computer-Aided Design 53 (2014) 117–125.
  * [13] M. Li, C. Lin, W. Chen, Y. Liu, S. Gao, Q. Zou, Xvoxel-based parametric design optimization of feature models, Computer-Aided Design 160 (2023) 103528.
  * [14] Q. Zou, Y. Gao, G. Luo, S. Chen, Meta-meshing and triangulating lattice structures at a large scale, Computer-Aided Design (2024) 103732.
  * [15] C. Su, X. Jiang, G. Huo, Q. Zou, Z. Zheng, H.-Y. Feng, Accurate model construction of deformed aero-engine blades for remanufacturing, The International Journal of Advanced Manufacturing Technology 106 (2020) 3239–3251.
  * [16] L. Piegl, W. Tiller, The NURBS Book, 2nd Edition, Springer-Verlag, New York, NY, USA, 1996.
  * [17] F. Scholz, B. Jüttler, Parameterization for polynomial curve approximation via residual deep neural networks, Computer Aided Geometric Design 85 (2021) 101977.
  * [18] J.-J. Fang, C.-L. Hung, An improved parameterization method for B-spline curve and surface interpolation, Computer-Aided Design 45 (6) (2013) 1005–1028.
  * [19] E. T. Lee, Choosing nodes in parametric curve interpolation, Computer-Aided Design 21 (6) (1989) 363–370.
  * [20] T. A. Foley, G. M. Nielson, Knot selection for parametric spline interpolation, in: Mathematical methods in computer aided geometric design, Elsevier, 1989, pp. 261–CP4.
  * [21] C. Balta, S. Öztürk, M. Kuncan, I. Kandilli, Dynamic centripetal parameterization method for B-spline curve interpolation, IEEE Access 8 (2019) 589–598.
  * [22] L. A. Piegl, W. Tiller, Surface approximation to scanned data, The Visual Computer 16 (2000) 386–395.
  * [23] Z. Yong, H. Kang, Z. Yang, Y. Gu, The unimodality of initial B-spline approximations in spline fitting, Communications in Mathematics and Statistics 10 (2) (2022) 331–352.
  * [24] P. Laube, M. Franz, G. Umlauf, Deep learning parametrization for B-spline curve approximation, in: 2018 International Conference on 3D Vision, 2018, pp. 691–699.
  * [25] Q. Zou, H.-Y. Feng, A robust direct modeling method for quadric b-rep models based on geometry–topology inconsistency tracking, Engineering with Computers 38 (4) (2022) 3815–3830.
  * [26] Y. Zhao, Q. Zou, G. Luo, J. Wu, S. Chen, D. Gao, M. Xuan, F. Wang, Tpms2step: error-controlled and c2 continuity-preserving translation of tpms models to step files based on constrained-pia, Computer-Aided Design (2024) 103726.
  * [27] Q. Zou, H.-Y. Feng, A decision-support method for information inconsistency resolution in direct modeling of cad models, Advanced Engineering Informatics 44 (2020) 101087.
  * [28] Z. Wang, S. Liu, L. Liu, Q. Zou, X.-M. Fu, Computing smooth preferred feed direction fields with high material removal rates for efficient cnc tool paths, Computer-Aided Design 164 (2023) 103591.
  * [29] Q. Zou, H.-Y. Feng, Variational b-rep model analysis for direct modeling using geometric perturbation, Journal of Computational Design and Engineering 6 (4) (2019) 606–616.
  * [30] G. Luo, Q. Zou, A simple point-based iso-scallop tool path planning method for noisy point clouds with high robustness and controlled errors, Computer-Aided Design 163 (2023) 103560.
  * [31] Q. Zou, J. Zhao, Iso-parametric tool-path planning for point clouds, Computer-Aided Design 45 (11) (2013) 1459–1468.
  * [32] J. Ding, Q. Zou, S. Qu, P. Bartolo, X. Song, C. C. Wang, Stl-free design and manufacturing paradigm for high-precision powder bed fusion, CIRP Annals 70 (1) (2021) 167–170.
  * [33] Q. Zou, Robust and efficient tool path generation for machining low-quality triangular mesh surfaces, International Journal of Production Research 59 (24) (2021) 7457–7467.
  * [34] C.-G. Lim, A universal parametrization in B-spline curve and surface interpolation, Computer Aided Geometric Design 16 (5) (1999) 407–422.
  * [35] J. Gao, C. Tang, V. Ganapathi-Subramanian, J. Huang, H. Su, L. J. Guibas, DeepSpline: Data-driven reconstruction of parametric curves and surfaces, arXiv preprint arXiv:1901.03781.
  * [36] A. Iglesias, A. Gálvez, M. Collantes, Bat algorithm for curve parameterization in data fitting with polynomial Bézier curves, in: 2015 International Conference on Cyberworlds (CW), 2015, pp. 107–114.
  * [37] A. Iglesias, A. Gálvez, M. Collantes, Four adaptive memetic bat algorithm schemes for Bézier curve parameterization, Transactions on Computational Science XXVIII: Special Issue on Cyberworlds and Cybersecurity (2016) 127–145.
  * [38] T. Speer, M. Kuppe, J. Hoschek, Global reparametrization for curve approximation, Computer Aided Geometric Design 15 (9) (1998) 869–877.
  * [39] W. Wang, H. Pottmann, Y. Liu, Fitting B-spline curves to point clouds by curvature-based squared distance minimization, ACM Transactions on Graphics 25 (2) (2006) 214–238.
  * [40] J. Yang, D. Wang, H. Hong, Improving angular speed uniformity by reparameterization, Computer Aided Geometric Design 30 (7) (2013) 636–652.
  * [41] J. Luo, H. Kang, Z. Yang, Knot calculation for spline fitting based on the unimodality property, Computer Aided Geometric Design 73 (2019) 54–69.
  * [42] D. Michel, A. Zidna, A new deterministic heuristic knots placement for B-spline approximation, Mathematics and Computers in Simulation 186 (2021) 91–102.
  * [43] W. Li, S. Xu, G. Zhao, L. P. Goh, Adaptive knot placement in B-spline curve approximation, Computer-Aided Design 37 (8) (2005) 791–797.
  * [44] H. Park, J.-H. Lee, B-spline curve fitting based on adaptive curve refinement using dominant points, Computer-Aided Design 39 (6) (2007) 439–451.
  * [45] H. Kang, F. Chen, Y. Li, J. Deng, Z. Yang, Knot calculation for spline fitting via sparse optimization, Computer-Aided Design 58 (2015) 179–188.
  * [46] F. Yoshimoto, T. Harada, Y. Yoshimoto, Data fitting with a spline using a real-coded genetic algorithm, Computer-Aided Design 35 (8) (2003) 751–760.
  * [47] J. Luo, H. Kang, Z. Yang, Knot placement for B-spline curve approximation via l$\infty$, 1-norm and differential evolution algorithm, Journal of Computational Mathematics 40 (4) (2022) 589.
  * [48] Z. Wen, J. Luo, H. Kang, The deep neural network solver for B-spline approximation, Computer-Aided Design 169 (2024) 103668.
  * [49] P. Laube, M. O. Franz, G. Umlauf, Learnt knot placement in B-spline curve approximation using support vector machines, Computer Aided Geometric Design 62 (2018) 104–116.
  * [50] Z. Shi, S. Peng, Y. Xu, A. Geiger, Y. Liao, Y. Shen, Deep generative models on 3D representations: A survey, arXiv preprint arXiv:2210.15663.
  * [51] K. Schwarz, A. Sauer, M. Niemeyer, Y. Liao, A. Geiger, VoxGRAF: Fast 3D-aware image synthesis with sparse voxel grids, Advances in Neural Information Processing Systems 35 (2022) 33999–34011.
  * [52] X. Zeng, A. Vahdat, F. Williams, Z. Gojcic, O. Litany, S. Fidler, K. Kreis, LION: Latent point diffusion models for 3D shape generation, in: Advances in Neural Information Processing Systems, Vol. 35, Curran Associates, Inc., 2022, pp. 10021–10039.
  * [53] J. Gao, T. Shen, Z. Wang, W. Chen, K. Yin, D. Li, O. Litany, Z. Gojcic, S. Fidler, GET3D: A generative model of high quality 3D textured shapes learned from images, Advances In Neural Information Processing Systems 35 (2022) 31841–31854.
  * [54] Y.-C. Cheng, H.-Y. Lee, S. Tulyakov, A. G. Schwing, L.-Y. Gui, SDFusion: Multimodal 3D shape completion, reconstruction, and generation, in: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023, pp. 4456–4465.
  * [55] A. D. Prasad, A. Balu, H. Shah, S. Sarkar, C. Hegde, A. Krishnamurthy, NURBS-diff: A differentiable programming module for NURBS, Computer-Aided Design 146 (2022) 103199.
  * [56] Z. Wang, S. Wu, W. Xie, M. Chen, V. A. Prisacariu, NeRF–: Neural radiance fields without known camera parameters, arxiv preprint arXiv:2102.07064.
  * [57] O. Vinyals, M. Fortunato, N. Jaitly, Pointer networks, Advances in Neural Information Processing Systems 28.
  * [58] C.-F. R. Chen, Q. Fan, R. Panda, CrossViT: Cross-attention multi-scale vision transformer for image classification, in: Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 357–366.
  * [59] G. E. Farin, Curves and surfaces for CAGD: a practical guide, Morgan Kaufmann, 2002.