ParSeNet: A Parametric Surface Fitting Network for 3D Point Clouds
Gopal Sharma Difan Liu Subhransu Maji Evangelos Kalogerakis Siddhartha Chaudhuri Radomír Měch
cs.CV cs.LG


headings



Sharma et al.
^1University of Massachusetts Amherst  ^2Adobe Research  ^3IIT Bombay
ParSeNet: A Parametric Surface Fitting Network for 3D Point Clouds
    Gopal Sharma^10000-0002-7492-7808Difan Liu^10000-0001-5971-2748Subhransu Maji^10000-0002-3869-9334

Evangelos Kalogerakis^10000-0002-5867-5735Siddhartha Chaudhuri^2,3 Radomír Měch^2

^1{gopalsharma, dliu, smaji, kalo}@cs.umass.edu, ^2{sidch,rmech}@adobe.com


    December 30, 2023
=======================================================================================================================================================================================================================================================================




  
We propose a novel, end-to-end trainable, deep network called that
decomposes a 3D point cloud into parametric surface patches, including
B-spline patches as well as basic geometric primitives. is trained
on a large-scale dataset of man-made 3D shapes and captures high-level
semantic priors for shape decomposition. It handles a much richer
class of primitives than prior work, and allows us to represent
surfaces with higher fidelity. It also produces repeatable and robust
parametrizations of a surface compared to purely geometric
approaches.
We present extensive experiments to validate
our approach against analytical and learning-based alternatives. Our source code is publicly available at: <https://hippogriff.github.io/parsenet>. 














































































A
B
C
D
E
F
G
H̋
I
J
K
ŁL
M
N
ØO
P
Q
R
S
T
U
V
W
X
Y
Z
ℝ
ℂ
ℤ
ℕ
d
ε
dist








§ INTRODUCTION



3D point clouds can be rapidly acquired using 3D sensors or
photogrammetric techniques. However, they are rarely used in this form
in design and graphics applications. Observations from the
computer-aided design and modeling literature
<cit.> suggest that designers
often model shapes by constructing several non-overlapping patches
placed seamlessly. The advantage
of using several patches over a single continuous patch is that a
much more diverse variety of geometric features and
surface topologies can be created. The decomposition also
allows easier interaction and editing.
The goal of this work is to automate the time-consuming process of
converting a 3D point cloud into a piecewise parametric surface
representation as seen in Figure <ref>.

An important question is how surface patches should be
represented. Patch representations in CAD and graphics are based on
well-accepted geometric properties: (a) continuity in their
tangents, normals, and curvature, making patches appear smooth, (b)
editability, such that they can easily be modified based on a
few intuitive degrees of freedom (DoFs), , control points or axes,
and (c) flexibility, so that a wide variety of surface
geometries can be captured. Towards this goal, we propose , a
parametric surface fitting network
architecture which produces a compact, editable representation of a
point cloud as an assembly of geometric primitives, including open or closed B-spline patches.




models a richer class of surfaces than prior work which
only handles basic geometric primitives such as planes, cuboids
and
cylinders <cit.>. While
such primitives are continuous and editable representations, they lack
the richness and flexibility of spline patches which are widely used
in shape design. includes a novel neural network () to estimate
an open or closed B-spline model of a point cloud patch. It is part of
a fitting module (Section <ref>) which can also fit
other geometric primitive types. The fitting module receives input from a decomposition module, which partitions a point cloud into segments, after which
the fitting module estimates shape parameters of a predicted primitive type for each segment (Section
<ref>). The entire pipeline, shown in
Figure <ref>, is fully differentiable and trained
end-to-end (Section <ref>). An optional geometric
postprocessing step further refines the output.

Compared to purely analytical approaches, produces decompositions
that are more consistent with high-level semantic priors, and are more
robust to point density and noise. To train and test , we leverage
a recent dataset of man-made parts <cit.>. Extensive
evaluations show that outperforms baselines (RANSAC and
SPFN <cit.>) by 14.93% and 13.13% respectively for
segmenting a point cloud into patches, and by 50%, and 47.64%
relative error respectively for parametrizing each patch for surface reconstruction
(Section <ref>).

To summarize, our contributions are:



  * The first proposed end-to-end differentiable approach for representing a raw 3D point cloud as an assembly of parametric primitives including spline patches.

  * Novel decomposition and primitive fitting modules, including , a fully-differentiable network to fit a cubic B-spline patch to a set of points.

  * Evaluation of our framework vs prior analytical and learning-based methods.





§ RELATED WORK


Our work builds upon related research on parametric surface
representations and methods for primitive
fitting. We briefly review relevant work in these areas. Of course, we
also leverage extensive prior work on neural networks for general
shape processing: see recent surveys on the
subject <cit.>.




  
Parametric surfaces. A parametric surface is a (typically
diffeomorphic) mapping from a (typically compact) subset of ^2 to
^3. While most of the geometric primitives used in computer
graphics (spheres, cuboids, meshes etc) can be represented
parametrically, the term most commonly refers to curved surfaces used
in engineering CAD modelers, represented as spline
patches <cit.>. There are a variety of formulations
– Bézier patches, B-spline patches, NURBS patches – with
slightly different characteristics, but they all construct surfaces as
weighted combinations of control parameters, typically the positions
of a sparse grid of points which serve as editing handles.

More specifically, a B-spline patch is a smoothly curved, bounded, parametric surface, whose shape
is defined by a sparse grid of control points ={_p,q}. The surface
point with parameters  and basis functions <cit.> b_p(u), b_q(v) is given by:


    (u,v)= ∑_p=1^P ∑_q=1^Q  b_p(u)b_q(v) _p,q

Please refer to supplementary material for more details on B-spline patches.



  
Fitting geometric primitives. A variety of analytical (not learning-based) algorithms have been devised to approximate raw 3D data as a collection of geometric primitives: dominant themes include Hough transforms, RANSAC and clustering. The literature is too vast to cover here, we recommend the comprehensive survey of Kaiser <cit.>. In the particular case of NURBS patch fitting, early approaches were based on user interaction or hand-tuned heuristics to extract patches from meshes or point clouds 
<cit.>. In the rest of this section, we briefly review recent methods that learn how to fit primitives to 3D data.

Several recent
papers <cit.>
also try to approximate 3D shapes as unions of cuboids or ellipsoids.
Paschalidou <cit.> extended
this to superquadrics. Sharma <cit.> developed a
neural parser that represents a test shape as a collection of basic primitives
(spheres, cubes, cylinders) combined with boolean operations. Tian
<cit.> handled more expressive construction rules (.
loops) and a wider set of primitives. Because of the choice of simple
primitives, such models are naturally limited in how well they align to complex
input objects, and offer less flexible and intuitive parametrization for user
edits.

More relevantly to our goal of modeling arbitrary curved surfaces, Gao <cit.> parametrize 3D point clouds as extrusions or surfaces of revolution, generated by B-spline cross-sections detected by a 2D network. This method requires translational/rotational symmetry, and does not apply to general curved patches. Li <cit.> proposed a supervised method to fit primitives to 3D point clouds, first predicting per-point segment labels, primitive types and normals, and then using a differential module to estimate primitive parameters. While we also chain segmentation with fitting in an end-to-end way, we differ from Li in two important ways. First, our differentiable metric-learning segmentation produces improved results (Table <ref>). Second, a major goal (and technical challenge) for us is to significantly improve expressivity and generality by incorporating B-spline patches: we achieve this with a novel differentiable spline-fitting network.
In a complementary direction, Yumer <cit.> developed a neural network for fitting a single NURBS patch to an unstructured point cloud. While the goal is similar to our spline-fitting network, it is not combined with a decomposition module that jointly learns how to express a shape with multiple patches covering different regions. Further, their fitting module has several non-trainable steps which are not obviously differentiable, and hence cannot be used in our pipeline.







§ METHOD



The goal of our method is to reconstruct an input point cloud by predicting a set of parametric patches closely approximating its underlying surface.  The first stage of our architecture is a neural decomposition module (Fig. <ref>) whose goal is to segment the input point cloud into regions, each labeled with a parametric patch type. Next, we incorporate a fitting module (Fig. <ref>) that predicts each patch's shape parameters. Finally, an optional post-processing geometric optimization step refines the patches to better align their boundaries for a seamless surface.

The input to our pipeline is a set of points = {_i }_i=1^N,
represented either as 3D positions _i = (x, y, z), or as 6D position + normal vectors _i = (x, y, z, n_x, n_y, n_z). The output is a set of surface patches {_k}, reconstructing the input point cloud. The number of patches is automatically determined. Each patch is labeled with a type t_k, one of: sphere, plane, cone, cylinder, open/closed B-spline patch. The architecture also outputs a real-valued vector for each patch defining its geometric parameters, center and radius for spheres, or B-spline control points and knots.




 §.§ Decomposition module



The first module (Fig. <ref>) decomposes the point cloud  into a set of segments such that each segment can be reliably approximated by one of the abovementioned surface patch types. To this end, the module first embeds the input points into a representation space used to reveal such segments. As discussed in Section <ref>, the representations are learned using metric learning, such that points belonging to the same patch are embedded close to each other, forming a distinct cluster.




  
Embedding network.
To learn these point-wise representations, we incorporate edge convolution layers (EdgeConv) from DGCNN <cit.>.
Each EdgeConv layer performs a graph convolution to extract a representation of each point with an MLP on the input features of its neighborhood. The neighborhoods are dynamically defined via nearest neighbors in the input feature space.
We stack 3 EdgeConv layers, each extracting a 256-D representation per point. A max-pooling layer is also used to extract a global 1024-D representation for the whole point cloud. The global representation is tiled and concatenated with the  representations from all three EdgeConv layers to form intermediate point-wise (1024 + 256)-D representations ={_i} encoding both local and global shape information. We found that a global representation is useful for our task, since it captures the overall geometric shape structure, which is often correlated with the number and type of expected patches. This representation is then transformed through fully connected layers and ReLUs, and finally normalized to unit length to form the point-wise embedding ={_i}_i=1^N (128-D) lying on the unit hypersphere.




  
Clustering.
A mean-shift clustering procedure is applied on the point-wise embedding to discover segments. The advantage of mean-shift clustering over other alternatives (, k-means or mixture models) is that it does not require the target number of clusters as input. Since different shapes may comprise different numbers of patches, we let mean-shift produce a cluster count tailored for each input. Like the pixel grouping of <cit.>, we implement mean-shift iterations as differentiable recurrent functions, allowing back-propagation. Specifically, we initialize mean-shift by setting all points as seeds ^(0)_i=_i,  ∀ y_i ∈ R^128. Then, each mean-shift iteration t updates each point's embedding on the unit hypersphere:


    ^(t+1)_i = ∑_j=1^N _j g(_i^(t), _j) / (∑_j=1^N g(_i^(t), _j))

where the pairwise similarities g(_i^(t), _j) are based on a von Mises-Fisher kernel with bandwidth β: g(_i, _j) = exp(_i^T_j / β^2) (iteration index dropped for clarity). The embeddings are normalized to unit vectors after each iteration.
The bandwidth for each input point cloud is set as the average distance of each point to its 150^th neighboring point in the embedding space <cit.>. The mean-shift iterations are repeated until convergence (this occurs around 50 iterations in our datasets). We extract the cluster centers using non-maximum suppression: starting with the point with highest density, we remove all points within a distance β, then repeat. Points are assigned to segments based on their nearest cluster center. The point memberships are stored in a matrix , where [i,k]=1 means point i belongs to segment k, and 0 means otherwise. The memberships are passed to the fitting module to determine a parametric patch per segment. During training, we use soft memberships for differentiating this step (more details in Section <ref>).




  
Segment Classification.
To classify each segment, we pass the per-point representation _i, encoding local and global geometry, through fully connected layers and ReLUs, followed by a softmax for a per-point probability P(t_i = l), where l is a patch type (, sphere, plane, cone, cylinder, open/closed B-spline patch). The segment's patch type is determined through majority voting over all its points.




 §.§ Fitting module



The second module (Fig. <ref>) aims to fit a parametric patch to each predicted segment of the point cloud. To this end, depending on the segment type, the module estimates the shape parameters of the surface patch.




  
Basic primitives. Following Li <cit.>, we estimate the shape of basic primitives with least-squares fitting. This includes center and radius for spheres; normal and offset for planes; center, direction and radius for cylinders; and apex, direction and angle for cones. We also follow their approach to define primitive boundaries.




  
B-Splines.

Analytically parametrizing a set of points as a spline patch in the presence of noise, sparsity and non-uniform sampling, can be error-prone. Instead, predicting control points directly with a neural network can provide robust results. We propose a neural network , that inputs points of a segment, and outputs a fixed size control-point grid. A stack of three EdgeConv layers produce point-wise representations concatenated with a global representation extracted from a max-pooling layer (as for decomposition, but weights are not shared). This equips each point i in a segment with a 1024-D representation _i. A segment's representation is produced by max-pooling over its points, as identified through the membership matrix  extracted previously:

    _k= max_i=1...N ( [i,k] ·_i).

Finally, two fully-connected layers with ReLUs transform _k to an initial set of 20×20 control points  unrolled into a 1200-D output vector. For a segment with a small number of points, we upsample the input segment (with nearest neighbor interpolation) to 1600 points. This significantly improved performance for such segments (Table <ref>). For closed B-spline patches, we wrap the first row/column of control points. Note that the network parameters to produce open and closed B-splines are not shared. Fig. <ref> visualizes some predicted B-spline surfaces.













 §.§ Post-processing module




produces an initial patch surface that approximates the points belonging to a segment. However, patches might not entirely cover the input point cloud, and boundaries between patches are not necessarily well-aligned. Further, the resolution of the initial control point grid (20 × 20) can be further adjusted to match the desired surface resolution. As a post-processing step, we perform an optimization to produce B-spline surfaces that better cover the input point cloud, and refine the control points to achieve a prescribed fitting tolerance.




  
Optimization. We first create a grid of 40×40 points on the initial B-spline patch by uniformly sampling its UV parameter space. We tessellate them into quads. Then we perform a maximal matching between the quad vertices and the input points of the segment, using the Hungarian algorithm with L2 distance costs. We then perform an as-rigid-as-possible (ARAP) <cit.> deformation of the tessellated surface towards the matched input points. ARAP is an iterative, detail-preserving method to deform a mesh so that selected vertices (pivots) achieve targets position, while promoting locally rigid transformations in one-ring neighborhoods (instead of arbitrary ones causing shearing/stretching). We use the boundary vertices of the patch as pivots so that they move close to their matched input points. Thus, we promote coverage of input points by the B-spline patches. After the deformation, the control points are re-estimated with least-squares <cit.>.




  
Refinement of B-spline control points. After the above optimization, we again perform a maximal matching between the quad vertices and the input points of the segment. As a result, the input segment points acquire 2D parameter values in the patch's UV parameter space, which can be used to re-fit any other grid of control points <cit.>. In our case, we iteratively upsample the control point grid by a factor of 2 until a fitting tolerance, measured via Chamfer distance, is achieved. If the tolerance is satisfied by the initial control point grid, we can similarly downsample it iteratively. In our experiments, we set the fitting tolerance to 5 × 10^-4. In Fig. <ref> we show the improvements from the post-processing step.




§ TRAINING



To train the neural decomposition and fitting modules of our architecture, we use supervisory signals from a  dataset of
3D shapes modeled through a combination of basic geometric primitives and B-splines.
Below we describe the dataset, then we discuss the loss functions
and  the steps of our training procedure.




 §.§ Dataset


The ABC dataset <cit.> provides a large source of 3D CAD models of mechanical objects whose file format stores surface patches and modeling operations that designers used to create them. Since our method is focused on predicting surface patches, and in particular B-spline patches, we selected models from this dataset that contain at least one B-spline surface patch.
As a result, we ended up with a dataset of 32K models (24K, 4K, 4K train, test, validation sets respectively). We call this .
All shapes are centered in the origin and scaled so they lie inside unit cube. To train , we also extract 32K closed and open B-spline surface
patches each from ABC dataset and split them into 24K, 4K, 4K train, test, validation sets
respectively. We call this . We report the average number of different patch types in
supplementary material.



  
Preprocessing. Based on the provided metadata in , each shape can be
rendered based on the collection of surface patches and primitives it contains
(Figure <ref>). Since we assume that the inputs to our architecture
are point clouds, we first sample each shape with 10K points randomly
distributed on the shape surface. We also add noise in a uniform range
[-0.01, 0.01] along the normal direction. Normals are also
perturbed with random noise in a uniform range of [-3, 3] degrees
from their original direction.






 §.§ Loss functions




We now describe the different loss functions used to train our neural modules. The training procedure involving their combination is discussed in Section <ref>.




  
Embedding loss. To discover clusters of points that correspond well to surface patches, we use a metric learning approach. The point-wise representations  produced  by our decomposition module after mean-shift clustering are learned such that point pairs originating
from the same surface patch  are embedded close to each other to favor a cluster formation. In contrast, point pairs
originating from different surface patches are pushed away from each other. Given a triplet of points (a, b, c), we use the triplet loss
to learn the embeddings:
c
where τ the margin is set to 0.9.
Given a triplet set T_ sampled from each point set  from our dataset , the
embedding objective sums the loss over  triplets:

    L_emb = ∑_∈1/|_|∑_(a, b, c) ∈_ℓ_emb(a, b, c).




  
Segment  classification loss.
To promote correct segment classifications according to our supported types,  we
use the  cross entropy loss:
 where p^i_t is the probability of the i^th point of shape  belonging to its ground truth type t, computed  from our segment classification network.





  
Control point regression loss. This loss function is used to train
. As discussed in Section <ref>, produces
20 × 20 control points per B-spline patch. We include a
supervisory signal for this control point grid prediction.
One issue is that B-spline patches have a variable number of control
points in our dataset.
Hence we reparametrize each patch by first sampling M=3600 points and
estimating a new 20× 20 reparametrization using least-squares
fitting <cit.>, as seen in the
Figure <ref>. In our experiments, we found
that this standardization produces no practical loss in surface reconstructions
in our dataset.
Finally, our reconstruction loss should be invariant to flips or swaps of control points grid in u
and v directions.
Hence we define a loss that is invariant to such permutations:

    L_cp =∑_∈1/|^(b)|∑_s_k ∈^(b)1/|_k|min_π∈Π || _k - π( _k ) ||^2

where ^(b) is the set of B-spline patches from shape , _k is the predicted control point grid for  patch _k (|_k|=400 control points),  π( _k ) is permutations of the
ground-truth control points from the set Π of 8  permutations for open and 160 permutations for closed B-spline.




  
Laplacian loss.  This loss is also specific to
B-Splines using . For each ground-truth B-spline patch, we
uniformly sample ground truth surface, and measure the surface Laplacian
capturing its second-order derivatives. We also uniformly sample
the predicted patches and measure their Laplacians.
We then establish Hungarian matching between sampled points in the ground-truth and predicted
patches, and compare the Laplacians of the ground-truth
points _m and corresponding predicted ones
_n to improve the agreement between their derivatives as follows:

    L_lap =  ∑_∈1/|^(b)| · M∑__k ∈^(b)∑__n ∈ s_k 
    ||(_n) -  (_m)  ||^2

where (·) is the  Laplace operator on patch points, and M=1600 point samples.




  
Patch distance loss. This loss is applied to both basic
primitive and B-splines patches.
Inspired by <cit.>, the loss measures average distances
between predicted primitive patch s_k and uniformly sampled points
from the ground truth patch as:

    L_dist =  ∑_∈1/K_∑_k=1^K_1/M__k∑_n ∈_k
    D^2( _n, _k),

where K_ is the number of predicted patches for shape , M__k is number of sampled points _n from ground patch _k, D^2( _n, _k) is the squared distance from _n to the predicted primitive patch surface _k. These distances can be computed analytically for basic primitives <cit.>. For B-splines, we use an approximation based on Chamfer distance between sample points.




 §.§ Training procedure



One possibility for training is to start it from scratch using a combination of all losses. Based on our experiments, we found that breaking the training
procedure into the following steps leads to faster convergence  and to
better minima:




  * We  first pre-train the networks of the decomposition module
using with the sum of embedding and classification losses:
L_emb+L_class. Both losses are necessary for point cloud decomposition and classification.


  * We then pre-train the using for control point prediction exclusively on  B-spline patches using L_cp+L_lap+L_dist.
We note that we experimented training the B-spline patch prediction
only with the patch distance loss L_dist but had  worse
performance. Using both the L_cp and L_lap loss yielded better
predictions as shown in  Table <ref>.


  * We then jointly train the decomposition and fitting module end-to-end
  with all the losses. To allow backpropagation from the
  primitives and B-splines fitting to the embedding network, the mean
  shift clustering is implemented as a recurrent
  module (Equation <ref>). For efficiency, we use 5
  mean-shift iterations during training.
  It is also important to note that during training,
  Equation <ref> uses soft
  point-to-segment memberships, which enables backpropagation from the
  fitting module to the decomposition module and improves reconstructions.
The soft memberships are computed based on the point embeddings
  {_i} (after the mean-shift iterations) and  cluster center
  embedding  {_k} as follows:

    [i,k] = exp( _k^T _i / β^2 ) /∑_k'exp( _k'^T _i ) / β^2 )





Please see supplementary material for more implementation details.




§ EXPERIMENTS






Our experiments compare our approach to alternatives in three parts:
(a) evaluation of  the quality of segmentation and segment
classification
(Section <ref>), (b) evaluation of
 B-spline patch fitting, since it  is a major contribution of our work
 (Section <ref>), and (c) evaluation of
 overall reconstruction quality (Section <ref>).
 We
 include evaluation metrics and results for each of the three parts
 next.




 §.§ Segmentation and labeling evaluation




  
Evaluation metrics. We use the following metrics for evaluating the point cloud segmentation and segment labeling based on the test set of :



  * Segmentation mean IOU (“seg mIOU”): this metric measures the similarity of the predicted segments with ground truth segments. Given the ground-truth point-to-segment memberships  for an input point cloud, and the predicted ones , we measure:
    1/K∑_k=1^KIOU([:, k], h([:, k]))

    where h represents a membership conversion into a one-hot vector, and K is the number of ground-truth segments.

  
  * Segment labeling IOU (“label mIOU”): this metric measures the classification accuracy of primitive type prediction averaged over segments:

    1/K∑_k=1^Kℐ[ t_k = t̂_k ]
        where t_k and t̂_k is the predicted and ground truth primitive type respectively for k^th segment and ℐ is an indicator function. 


We use Hungarian matching to find correspondences between predicted segments and ground-truth segments.





  
Comparisons. We first compare our method with a nearest neighbor (NN) baseline:
for each test shape, we find its most similar shape from the training
set using Chamfer distance. Then for each point on the test shape, we
transfer the labels and primitive type from its closest point in
^3 on the retrieved shape.

We also compare against efficient RANSAC algorithm
<cit.>. The algorithm only handles basic primitives
(cylinder, cone, plane, sphere, and torus), and offers poor
reconstruction of B-splines patches in our
dataset. Efficient RANSAC requires per point normals, which we provide
as the ground-truth normals.
We run RANSAC 3 times and report the performance with best coverage.

We then compare against the supervised primitive fitting (SPFN)
approach <cit.>. Their approach produces per point segment
membership, and their network is trained to maximize relaxed IOU
between predicted membership and ground truth membership, whereas our
approach uses learned point embeddings and clustering with
mean-shift clustering to extract segments.
We train SPFN network using their provided code on our training set
using their proposed losses. We note that we include B-splines patches
in their supported types.
 We train their network in two input settings: (a) the network takes
 only point positions as input, (b) it takes  point and normals as input. We
 train our on our training set in the same two settings using our loss functions.

The performance of the above methods are shown in Table
<ref>. The lack of B-spline fitting hampers the
performance of RANSAC. The SPFN method with points and normals as
input performs better compared to using only points as input.
Finally, with only points as input performs better than all other
alternatives. We observe further gains when including point normals in
the input. Training end-to-end gives 13.13% and 8.66% improvement in segmentation
mIOU and label mIOU respectively over SPFN with points and normals as input.  The
better performance is also reflected in Figure <ref>,
where our method reconstructs patches that correspond to more
reasonable segmentations compared to other methods.  In the
supplementary material we evaluate methods on
the TraceParts dataset <cit.>, which contains only  basic  primitives (cylinder,  cone,  plane,  sphere, torus). We outperform
prior work also in this dataset.














 §.§ B-Spline fitting evaluation




  
Evaluation metrics. We evaluate the quality of our
predicted B-spline patches by computing the Chamfer distance between
densely sampled points on the ground-truth B-spline patches and
densely sampled points on predicted patches. Points are uniformly
sampled based on the 2D parameter space of the patches. We use 2K
samples. We use the test set of our for evaluation.



  
Ablation study.
We evaluate the training of using various loss functions while
giving 700 points per patch as input, in Table <ref>.
All losses contribute to improvements in performance.  Table
<ref> shows that upsampling is effective for closed
splines.  Figure <ref> shows the effect of
optimization to improve the alignment of patches and the adjustment
of resolution in the control point grid.
See supplementary material for more experiments on 's robustness.










 §.§ Reconstruction evaluation




  
Evaluation metrics.
Given a point cloud = {_i}_i=1^N, ground-truth
patches {∪_k=1^K_k} and predicted patches
{∪_k=1^K_k} for a test shape in , we evaluate the
patch-based surface reconstruction using the following:



  * Residual error (“res”) measures the average distance of input
  points from the predicted primitives following <cit.>:
  L_dist = ∑_k=1^K1/M_k∑_n ∈_k  D(_n, _k)
  where K is the number of segments, M_k is number of
  sampled points _n from ground patch _k, D(_n, _k) is the distance of _n from predicted
  primitive patch _k.


  * P-coverage (“P-cover”) measures the coverage of predicted
  surface by the input surface also following <cit.>:
  1/N∑_i=1^N[min_k=1^KD(_i, _k) <
    ϵ] (ϵ=0.01).



    We note that we use the matched segments after applying
  Hungarian matching algorithm, as in Section <ref>, to compute these metrics.



  
Comparisons. We report the performance of RANSAC for geometric primitive fitting
tasks. Note that RANSAC produces a set of geometric primitives, along
with their primitive type and parameters, which we use to compute the
above metrics. Here we compare with the SPFN network <cit.> trained
on our dataset using their proposed loss functions.
We augment their per point primitive type prediction to also include open/closed
B-spline type. Then for classified segments as B-splines, we use our to fit
B-splines. For segments classified as geometric primitives, we use their
geometric primitive fitting algorithm.



  
Results. Table <ref> reports the performance of our method, SPFN and RANSAC. The residual error and
P-coverage follows the trend of segmentation metrics. Interestingly, our method outperforms SPFN even for geometric primitive predictions (even without considering B-splines and our adaptation). Using points and normals, along with joint end-to-end training, and post-processing optimization offers the best performance for our method by giving 47.64% and 50% reduction in relative error in comparison to SPFN and RANSAC respectively.



§ CONCLUSION

We presented a method to reconstruct point clouds by predicting geometric primitives and surface patches common in CAD design.
Our method effectively marries 3D deep learning with CAD modeling practices.
 Our architecture predictions are editable and interpretable. Modelers can refine our results based on standard CAD modeling operations. 
 In terms of limitations, 
 our method often makes mistakes for small parts,  mainly because clustering merges them with bigger patches.  In high-curvature areas, due to sparse sampling, may produce more segments than ground-truth.
 Producing seamless boundaries is still a challenge due to noise and sparsity in our point sets. Generating training point clouds simulating realistic scan noise is another important future direction.  



  
Acknowledgements.
This research is funded in part by NSF (#1617333, #1749833) and Adobe.
Our experiments were performed in the UMass GPU cluster funded by the MassTech Collaborative. 
We thank
Matheus Gadelha for helpful discussions.


splncs04
   
#1S: #1


§ SUPPLEMENTARY MATERIAL

In our Supplementary Material, we:

  
  * provide background on B-spline patches;
  
  * provide further details about our dataset,
    architectures and implementation;
  
  * evaluate the robustness of as a function of point
    density;
  
  * evaluate our approach for reconstruction on the ;
  
  * show more visualizations of our results; and
  
  * evaluate the performance of our approach on the
    TraceParts dataset <cit.>.




 §.§ Background on B-spline patches.

A B-spline patch is a smoothly curved, bounded, parametric surface, whose shape is defined by a sparse grid of control points ={_p,q}. The surface point with parameters  is given by:


    (u,v)= ∑_p=1^P ∑_q=1^Q  b_p(u)b_q(v) _p,q

where b_p(u) and b_q(v) are polynomial B-spline basis
functions <cit.>.

To determine how the control points affect the B-spline, a sequence of
parameter values, or knot vector, is used to divide the range of
each parameter into intervals or knot spans. Whenever the
parameter value enters a new knot span, a new row (or column) of
control points and associated basis functions become active.
A common knot setting repeats the first and last ones multiple times (specifically
4 for cubic B-splines) while keeping the interior knots uniformly
spaced, so that the patch interpolates the corners of the control
point grid. A closed surface is generated by matching the control
points on opposite edges of the grid. There are various
generalizations of B-splines , with rational basis functions or
non-uniform knots. We focus on predicting cubic
B-splines (open or closed) with uniform interior knots, which are
quite common in CAD <cit.>.



 §.§ Dataset

The is a subset of the ABC dataset obtained by first selecting
models that contain at least one B-spline surface patch.
To avoid over-segmented shapes, we retain those with up to 50 surface patches.
This results in a total of 32k shapes, which we further split into training
(24k), validation (4k), and test (4k) subsets. Figure <ref>
shows the distribution of number and type of surface patches in the dataset.





 §.§ Implementation Details of 



  
Architecture details. Our decomposition module is based on a dynamic edge convolution network
<cit.>.
The network takes points as input (and optionally normals) and outputs
a per point embedding Y∈ R^N × 128 and primitive type T∈
R^N × 6.  The layers of our network are listed in Table
<ref>.
The edge convolution layer (EdgeConv) takes as input a per-point
feature representation f ∈ℝ^N × D,
constructs a kNN graph based on this feature space (we choose k=80
neighbors), then forms another feature representation h ∈ℝ^N× k× 2D, where h_i,j = [f_i,
  f_i-f_j], and i,j are neighboring points.
This encodes both unary and pairwise point features, which are further
transformed by a MLP (D→ D'), Group normalization and
LeakyReLU (slope=0.2) layers.
This results in a new feature representation: h' ∈ℝ^N× k × D'.
Features from neighboring points are max-pooled to obtain a per point
feature f' ∈ℝ^N× D'.
We express this layer which takes features f ∈ℝ^N× D and
returns features f' ∈ℝ^N × D' as EdgeConv(f, D,
D').
Group normalization in EdgeConv layer allows the use of smaller batch
size during training.
Please refer to <cit.> for more details on edge convolution
network.


is also implemented using a dynamic graph CNN.
The network takes points as input and outputs a grid of spline control points
that best approximates the input point cloud.
The architecture of is described in
Table <ref>.
Note that the EdgeConv layer in this network uses batch normalization
instead of group normalization.



  
Training details. We use the Adam optimizer for training with learning rate 10^-2 and
reducing it by the factor of two when the validation performance
saturates. For the EdgeConv layers of the decomposition module, we use
100 nearest neighbors, and 10 for the ones in . For
pre-training on , we randomly sample 2k points from the
B-spline patches.  Since ABC shapes are arbitrarily oriented, we
perform PCA on them and align the direction corresponding to the
smallest eigenvalue to the +x axis. This procedure does not
guarantee alignment, but helps since it reduces the orientation
variability in the dataset. For pre-training the decomposition module
and we augment the training shapes represented as points by using
random jitters, scaling, rotation and point density.



  
Back propagation through mean-shift clustering. The W
matrix is constructed by first applying non-max suppression (NMS) on
the output of mean shift clustering, which gives us indices of K
cluster centers. NMS is done externally outside our
computational graph. We use these indices and Eq. 9 to compute the W
matrix. The derivatives of NMS w.r.t point embeddings are zero or
undefined (i.e. non-differentiable). Thus, we remove NMS from the
computational graph and back-propagate the gradients through a partial
computation graph, which is differentiable. This can be seen as a
straight-through estimator <cit.>. A similar approach is used
in back-propagating gradients through Hungarian Matching in
<cit.>. Our experiments in
Table 1 shows that this approach for end-to-end training is
effective. Constructing a fixed size matrix W will result in
redundant/unused columns because different shapes have different
numbers of clusters. Possible improvements may lie in a continuous
relaxation of clustering similar to differentiable sorting and ranking
<cit.>, however that is out of scope for our work.







 §.§ Robustness analysis of 



Here we evaluate the performance of as a function of the point
sampling density. As seen in Figure <ref>, the
performance of is low when the point density is small (100
points per surface patch).
is based on graph edge convolutions <cit.>, which
are affected by the underlying sampling density of the network.
However, upsampling points using a nearest neighbor
interpolation leads to a significantly better performance.



 §.§ Evaluation of Reconstruction using Chamfer Distance

Here we evaluate the performance of and other
baselines for the task of reconstruction using Chamfer distance on
.
Chamfer distance between
reconstructed points P and input points P̂ is defined as:

    p_cover = 1/|P|∑_i∈ Pmin_j ∈P̂i-j^2,



    s_cover = 1/|P̂|∑_i∈P̂min_j ∈ Pi-j^2,


    CD = 1/2(p_cover + s_cover).

Here |P| and |P̂| denote the cardinality of P and P̂
respectively. We randomly sample 10k points each on the predicted and ground
truth surface for the evaluation of all methods. Each predicted surface patch is
also trimmed to define its boundary using bit-mapping with epsilon 0.1
<cit.>. To evaluate this metric, we use all predicted
surface patches instead of the matched surface patches that is used in
Section 5.3.

Results are shown in Table <ref>. Evaluation using Chamfer
distance follows the same trend of residual error shown in Table 1. and SPFN with points as input performs better than NN
and RANSAC. and SPFN with points along with normals as input performs better
than with just points as input. By training end-to-end and also using post-process optimization results in the best performance. Our full gives
35.67% and 49.53% reduction in relative error in comparison to SPFN and
RANSAC respectively. We show more visualizations of surfaces reconstructed by in Figure
<ref>.








 §.§ Evaluation on TraceParts Dataset

Here we evaluate the performance of on the TraceParts dataset, and compare
it with SPFN. Note that the input points are normalized to
lie inside a unit cube.
Points sampled from the shapes in TraceParts
<cit.> have a fraction of points not assigned to any
cluster.
To make this dataset compatible with our evaluation approach, each
unassigned point is merged to its closest cluster. This results in evaluation score to differ from the reported score in their paper <cit.>.

First we create a nearest neighbor (NN) baseline as shown in the Section
5.3. In this, we first scale both training and testing shape an-isotropically such that each dimension has unit length. Then for each test shape, we find its most similar shape from the training
set using Chamfer Distance. Then for each point on the test shape, we
transfer the labels and primitive type from its closest point in
^3 on the retrieved shape.  We train on the training set of
TraceParts using the losses proposed in the Section 4.2
and we also train SPFN using their proposed losses.
All results are reported on the test set of TraceParts.

Results are shown in the Table <ref>. The NN approach achieves
a high segmentation mIOU of 81.92% and primitive type mIOU of 95%.
Figure <ref> shows the NN results for a random set of shapes
in the test set. It seems that the test and training sets often contain
duplicate or near-duplicate shapes in the TraceParts dataset. Thus the
performance of the NN can be attributed to the lack of shape diversity in this
dataset. In comparison, our dataset is diverse, both in terms of shape variety
and primitive types, and the NN baseline achieve much lower performance with
segmentation mIOU of 54.10% and primitive type mIOU of 61.10%.


We further compare our with SPFN with just points as input.
achieves 79.91% seg mIOU compared to 76.4% in SPFN.
achieves 97.39% label mIOU compared to 95.18% in SPFN.
We also perform better when both points and normals are used as input to and
SPFN.

Finally, we compare reconstruction performance in the Table
<ref>. With just points as input to the
network, reduces the relative residual error by 9.35% with
respect to SPFN. With both points and normals as input reduces
relative residual error by 15.17% with respect to SPFN.








