Parameter-Free Connectivity for Point Clouds
Diana Marin a, Stefan Ohrhallinger b and Michael Wimmer c
Institute of Visual Computing & Human-Centered Technology, TU Wien, Austria
Keywords: Proximity Graphs, Point Clouds, Connectivity.
Abstract: Determining connectivity in unstructured point clouds is a long-standing problem that has still not been ad-
dressed satisfactorily. In this paper, we analyze an alternative to the often-used k-nearest neighborhood (kNN)
graph - the Spheres of Influence Graph (SIG). We show that the edges that are neighboring each vertex are
spatially bounded, which allows for fast computation of SIG. Our approach shows a better encoding of the
ground truth connectivity compared to the kNN for a wide range of k, and additionally, it is parameter-free.
Our result for this fundamental task offers potential for many applications relying on kNN, e.g., parameter-free
normal estimation, and consequently, surface reconstruction, motion planning, simulations, and many more.
1 INTRODUCTION
In recent times, point clouds have gained popular-
ity as a data representation, owing to advancements
in scanning technology. However, the initial state
of disorganized points necessitates further process-
ing to reconstruct the original surface’s connectiv-
ity from which they were sampled. This connec-
tivity allows for the estimation of surface properties
such as neighborhoods or normals. Various meth-
ods are available for estimating the intrinsic proper-
ties of point clouds, but they often rely on selecting
the appropriate parameters tailored to the specific data
type. For instance, this includes determining neigh-
borhood connectivity using the user-specified ‘k’ in
k-nearest neighbor (kNN) calculations. Additionally,
point cloud sampling can be non-uniform due to the
acquisition method or tainted by artifacts like noise
and outliers. These conditions make the process of
parameter selection for scanned data a challenging
and time-consuming endeavor.
Extracting connectivity from point clouds is a
significant research challenge, not only due to its
essential role as a first step in surface reconstruction
but also because it forms the foundational input for
graph-based learning tasks involving point clouds.
Regarding surface reconstruction, connectivity
graphs serve as the fundamental structure on which
triangles are constructed, and as a computation base
for normals, which are sometimes required as part
of the reconstruction process. For learning-based
a https://orcid.org/0000-0002-8812-9719
b https://orcid.org/0000-0002-2526-7700
c https://orcid.org/0000-0002-9370-2663
tasks, establishing a method for connecting the input
points that closely aligns with the original surface is
imperative, since the creation of an actual surface is
not necessary.
We propose a fast computation of the spheres-of-
influence graph (SIG) and we analyze its properties
as a proximity graph. This graph recovers the original
connectivity of the surface better than the widely
used kNN graph, as it can be seen in Figure 1, while
dropping the need for users to search for a suitable
parameter that typically varies depending on the input
and its local properties. Our method achieves the
best results on various models with different features.
Hence, our method offers a good scaffolding for
further processing of point clouds, such as normal
estimation, surface reconstruction, or graph convo-
lutional neural networks. We show that our method
not only encodes the original connectivity better than
kNN but, as an application, provides a good base for
normal estimation, while remaining parameter-free.
We present the following contributions:
• We introduce an effective method for construct-
ing the spheres-of-influence graph, proving novel
spatial constraints for this parameter-free graph.
• Our method is evaluated against ground truth
meshes, demonstrating superior connectivity rep-
resentation with a reduced space requirement
when compared to traditional kNN graphs.
• As an application, we offer an analysis of nor-
mal computation on point clouds, highlighting our
method’s ability to deliver competitive results.
SIG. 6NN.
10NN. 20NN.
Figure 1: Results of our SIG and the kNN graphs for k = {6,10,20} for the connectivity of the Buddha statue from the
Stanford repository. Our graph captures the connectivity well, without many redundant edges, and without the need for a
parameter compared to the kNN graphs. The original surface is shown in light gray, with the various graphs overlaid in black.
2 RELATED WORK
Connectivity. Determining the neighborhood of
unstructured points in 3D requires a local descrip-
tion of the points’ relations depending on their dis-
tance. A k-neighbourhood is strongly influenced by
the choice of the parameter k, which could result in
over-smoothing if the covered area is too large, or
sensitivity to noise for small areas. Hence, picking
a value depends heavily on the particular type of data
and how it is sampled. Being able to choose k usu-
ally requires more time to find a suitable value, but it
allows the freedom of dealing with varied data types.
Various subsets of the Delaunay triangulation can
be used as connectivity graphs, such as the rel-
ative neighborhood graph, the Gabriel Graph, the
α-complex (Edelsbrunner et al., 1983), and the β-
skeleton (Kirkpatrick and Radke, 1985). For an edge
pq to exist in the relative neighborhood graph, there
cannot exist another point r that is closer to p or q
than they are to each other. In the Gabriel graph, two
points - p,q, are connected if the closed disc with di-
ameter pq, passing through p and q, contains no other
samples. The α-complex contains all simplices of the
Delaunay triangulation that can be enclosed with a
circle of radius 1/α, empty of other samples. The
β-skeleton has been introduced as a scale-invariant
version of α-shapes, where the edge pq is part of
the graph if angles prq are bound by a threshold - β.
However, we do not include these graphs in our eval-
uation, since, as subsets of the Delaunay triangula-
tion (Jaromczyk and Toussaint, 1992b), they are com-
puted by pruning the triangulation, which is slower
than both kNN and SIG computations. Furthermore,
since the triangulation computation is a prerequisite
for these methods, one could directly reconstruct the
surface, bypassing the need for a proximity graph.
Normal Estimation. An important application of
connectivity retrieval is represented by normal esti-
mation. Normal estimation for point clouds has been
a heavily researched area of computer graphics, as
it usually represents a first step or requirement in
surface reconstruction, e.g., for Poisson reconstruc-
tion (Kazhdan et al., 2006) or data-driven approaches
such as Point2Surf (Erler et al., 2020). One of the ba-
sic methods for computing normals for unstructured
point clouds is using Principal Component Analysis
(PCA). This method considers a local patch of ver-
tices and finds the axis of variance with the least
amount of variance since the points should vary the
least in the normal direction. The relation between
neighborhood choice and normal estimation has been
extensively studied (Mitra and Nguyen, 2003). Other
methods improve on the tangent plane estimation by
using a weighted approach when considering the local
neighborhood (Pauly et al., 2003) or by fitting alge-
braic spheres (Guennebaud and Gross, 2007). How-
ever, these methods all require a good parameter for
choosing an appropriate neighborhood size, which we
do not need with our simple parameter-free method.
Another avenue for estimating normals for point
clouds has been developed with the concept of
poles (Amenta and Bern, 1999). This method is based
on computing the Voronoi diagram on the input points
and extracting the normals as the line connecting each
sample point and the farthest Voronoi vertex to their
Voronoi cell (the pole). This method is sensitive to
noise, but it has been improved to handle noisy sam-
ples (Dey and Goswami, 2006) where it requires ad-
ditional parameters.
Data-Driven Approaches. Recently, multiple data-
driven approaches have been developed, which usu-
ally take advantage of large data repositories to learn
the geometric relations between the point clouds’
structure and their expected normals. Here (Boulch
and Marlet, 2016), they are using a Hough transform
to estimate normals. PCPNet (Guerrero et al., 2018)
builds on the PointNet architecture (Charles et al.,
2017) and uses local patches to estimate the properties
of point clouds with various noise levels and sampling
densities. However, these types of methods require a
long processing time and possible re-training depend-
ing on the type of data.
An alternative to dealing with noise in the ex-
isting point clouds is to first denoise them and then
use a connectivity/normal computation approach that
works well on clean data. In this direction, data-
driven approaches have been dealing with noise in
(Rakotosaona et al., 2020), where they build on PCP-
Net to classify outliers and then reproject noisy sam-
ples on the original surface. (Luo and Hu, 2021) use
a noisy point distribution model to estimate scores
and the direction of the surface. Classical, analytical
approaches for denoising include filtering in various
forms, such as the bilateral filter that takes normals
into account (Digne and de Franchis, 2017) or voting
schemes for feature detection that later help in normal
repositioning (Liu et al., 2020). This kind of prepro-
cessing could enable our method to also connect noisy
point clouds since it is designed as an interpolating
method to recover the connectivity.
Moreover, connectivity retrieval has applications
in other data-driven approaches. Methods that use
graph convolutional neural networks on point clouds
for various purposes, such as reconstruction or seg-
mentation, create a graph on the input points (and
sometimes on the deeper layers of the network as
well) and use it to learn about the data and infer the
surface or various labels on the input points (Shi and
Rajkumar, 2020; Wang et al., 2019). Usually, they use
kNN or a fixed radius neighbor search as their con-
nectivity encoding, which could be replaced by our
method to improve results.
Spheres-of-Influence. The spheres-of-influence
graph (SIG) has been introduced as a clustering
method (Toussaint, 1988). Two vertices are con-
nected in the SIG if their distance is less or equal to
the sum of the distances to their respective nearest
neighbors. This graph was previously used for
estimating local densities for surface reconstruc-
tion (Klein and Zachmann, 2004), but our method
aims to recover connectivity, not a surface. Moreover,
the rarely used SIG has recently gotten attention
in reconstruction methods (Marin et al., 2022; de
Figueiredo and Paiva, 2022) where combined with
the Delaunay graph it showed promising results for
curve and region reconstruction.
3 METHOD
We define a mesh as a collection of ver-
tices - V = {p ∈ R3} and triangulated faces -
T = {(a,b,c)|a,b,c ∈ V,a ̸= b ̸= c ̸= a}. Using
only the set of unstructured points V = {p ∈ R3},
we aim to recover a set of edges that connect the
given samples as similar as possible to the original
connectivity of the mesh which is encoded in T . We
define similarity here as edge connectivity, instead
of the exact triangulation of the original mesh. Our
method uses the spheres-of-influence graph, and we
provide an improved algorithm to efficiently compute
this proximity graph. We are using the vertices of
triangulated meshes as our input in order to have
access to a ground truth connectivity to which we can
compare our results.
Spheres-of-Influence Graph. The SIG contains all
the edges (v0,v1) such that for their respective end-
points, v0 and v1, the following holds:
∥v0,v1∥ ≤ nn(v0)+nn(v1), (1)
where ∥a,b∥ represents the Euclidean distance be-
tween points a and b, and nn(a) represents the dis-
tance between a and its nearest neighbor. This con-
dition can be interpreted visually as centering a ball
at each vertex, with radius equal to the distance to
the nearest neighbor of that vertex, and connecting
all points whose balls intersect, as it can be seen in
Figure 2. This graph encodes the spatial proximity of
vertices well, without the need for a parameter. It con-
tains the Nearest Neighbor graph (Toussaint, 1988),
as the edge between points and their respective near-
est neighbor will always satisfy the condition.
Figure 2: Visual representation of the SIG connectivity - the
intersections of circles generate the set of SIG edges.
Various properties of the sphere-of-influence
graph have been investigated, such as the bound on
the size of the graph (Dwyer, 1995) or its behav-
ior under different metric spaces (Michael and Quint,
1999). However, even if the number of edges has been
proven to be linear, algorithms to efficiently compute
the graph have not yet been researched, especially
considering that SIG is not included in the Delaunay
triangulation and hence, the latter cannot be used as a
starting point for pruning (Jaromczyk and Toussaint,
1992a). We show that the neighbors of each vertex in
SIG are bounded inside a fixed radius - Figure 3, and
we use this spatial constraint to improve the speed of
the computation.
Theorem 1. For all vertices a ∈ V , all SIG edges
(a,b),b ∈ V,a ̸= b, are contained in a radius of at
most 2nn(a) from a or in a radius of at most 2nn(b)
from b, where nn(v) is the distance between v and its
nearest neighbor, for v ∈V .
Proof. We will prove the statement by contradiction.
Let us compute the distance to the nearest neighbor
for each vertex and store the result as nn(v) for all
vertices v ∈ V . For each vertex v, retrieve all the ver-
tices within 2nn(v) distance of v and only store the
edges that satisfy the SIG criterion. Let us call the
obtained graph FastSIG (FSIG).
Since we are trying to prove Theorem 1 by con-
tradiction, we assume that there exists at least an edge
that is outside the range boundaries we have defined
(within 2nn(a) for each vertex). This means that there
has to exist an edge (a,b) which is in SIG but not in
a
b
c
Figure 3: We illustrate the spheres of influence of vertices
a and b in 2D as outlined circles, with a radius equal to the
distance to their respective nearest neighbor. The bound-
ing radius of the incident SIG edges are colored disks with
dashed borders of radius equal to twice the SIG radius. We
can observe that even if b is not in the incidence radius of
a, a is contained in b’s radius, showing that SIG edges are
contained in at least one of the endpoints’ incidence radii.
FSIG. Hence,
∥a,b∥ ≤ nn(a)+nn(b), (2)
since (a,b) ∈ SIG and
∥a,b∥> 2nn(a), (3)
from (a,b) ̸∈ FSIG, while checking a’s neighbours
which do not include b and
∥b,a∥> 2nn(b), (4)
from (a,b) ̸∈ FSIG, while checking b’s neighbours
which do not include a. Summing the last two equa-
tions, we get:
2∥a,b∥> 2nn(a)+2nn(b), (5)
since ∥a,b∥= ∥b,a∥. Dividing by 2, we get:
∥a,b∥> nn(a)+nn(b), (6)
which contradicts our assumption of (a,b) ∈ SIG.
Since we have arrived at a contradiction, we have
proved that all SIG edges are in FSIG as well.
Having proved that SIG edges live in a fixed
boundary from every node, we use this information
to retrieve all the neighboring nodes within the given
radius using a kdtree, as presented in Algorithm 1.
4 RESULTS
We are aiming to provide an alternative for kNN that
is parameter-free, fast to compute, efficient to store,
Data: V = {v ∈ R3}
Result: SIG={(a,b) : a,b ∈V,a ̸= b, ||a,b|| ≤
nn(a)+nn(b)}
SIG={};
create kd-tree KT of V ;
for v ∈V do
find nn(v) using KT ;
end
for v ∈V do
N = KT .findNbrInRange(2nn(v));
for u ∈ N do
if ||u,v|| ≤ nn(u)+nn(v) then
SIG += (u,v);
end
end
end
Algorithm 1: Fast SIG computation.
and achieves better or similar surface properties to
kNN for a wide variety of data. In this section, we will
show how SIG satisfies all these requirements, repre-
senting a good, parameter-free alternative to kNN for
estimating unstructured point clouds’ connectivity.
We have tested our method on a varied dataset
of points clouds exhibiting various features, such as
various types of non-uniform sampling and sharp
edges. We compared our results to the kNN neigh-
borhood for connectivity recovery, for usual values
of k = {6,10,20}. We did not use k-values lower
than 6 since this is the average degree of vertices in
triangulated meshes, as can be shown using Euler’s
formula. As an application, we have also computed
normals using PCA from our graph and from the
kNN graphs and compared these with the face-based
normals of the original meshes.
Dataset. We have used a subset of the
Thingy10K (Zhou and Jacobson, 2016) dataset
of meshes that are manifold and have less than 1k
vertices for our quantitative results, consisting of
around 3k different models. Most of these meshes
exhibit CAD-like features in the form of having
samples mainly along edges, with thin and long
faces. This type of sparse sampling affects the
results of our connectivity measures, as, on average,
none of the investigated connectivity graphs can
perfectly capture the original connectivity, but we
have chosen to include this type of data as well to test
the resilience of our method in the presence of sparse
sampling. For qualitative results, we have included
some of the meshes from the Stanford repository
(https://graphics.stanford.edu/data/3Dscanrep/) -
the resulting graphs using the Stanford bunny are
presented in Figure 4.
(a) SIG edges computed for the Stanford bunny. The
edges mostly follow the original triangulation, with ad-
ditional diagonals, but without any edges that incorrectly
connect the input samples.
(b) 6NN graph of the Standford bunny. The close-up
shows that not all edges of the face are captured, but ad-
ditional edges appear close to the ears.
(c) 10NN graph of the input samples. Redundant edges
are visible around the ears.
(d) 20NN graph of the input points. Many redundant
edges are visible on the ears and the body.
Figure 4: Results of our graph and kNN for k = {6,10,20} on the Stanford bunny, where the original surface is presented in
gray, with various connectivity graph edges overlaid in black.
Connectivity. The connectivity of the ground truth
is what our graph aims to reconstruct. However, the
original edge set is not a unique representation of the
intrinsic connectivity of points, as it is highly depen-
dent on the chosen triangulation, e.g., edges may flip,
as can be visible in Figure 5. Hence, we do not aim to
reproduce the exact edges of the ground truth meshes
(i.e., comparing the 1-ring of each vertex), but to cre-
ate a good approximation of the connectivity of the
entire surface.
In order to quantify how close our graph is to
the original connectivity, we used the DeltaCon met-
ric (Koutra et al., 2016), where a value of 0 means
the graphs are completely different and a score of 1
implies identical graphs. DeltaCon computes a ma-
trix of node-to-node influence for each graph and the
final score is a difference between these two n2 matri-
ces. This is equivalent to using m-ring neighborhoods
(m ∈ [1,n]) for each vertex with decreasing weights
as we move farther from the current node. Moreover,
this metric benefits from edge awareness - discon-
necting changes are penalized more than removing an
edge from a complete graph, and this is a property that
highly influences the type of connectivity we want to
measure for our method. For a detailed definition of
the metric and its implementation, we direct to the
original works (Koutra et al., 2016).
We have computed DeltaCon for the initial 3431
meshes from Thingy10K, with various numbers of
vertices and different sampling densities. The results
are presented in Figure 6, where SIG consistently ob-
tains higher scores than the kNN graphs. The re-
sults are clustered in equally sized buckets depend-
ing on the number of vertices. For each bucket, we
present the averaged DeltaCon measurement over all
inputs with the total number of vertices in the spec-
ified range. Even if the metric does not achieve 1,
as the graphs are not identical (as we do not aim for
this), our graph manages to encode the original con-
nectivity better than the kNN graphs. The maximum
DeltaCon value achieved by all methods is also lower
than 1 due to the sparse sampling of the dataset, as
mentioned previously.
Figure 5: Local changes in the triangulation choice - such as edge flips, do not affect the overall connectivity of the mesh.
The four highlighted vertices create the same connected surface in both figures.
Figure 6: DeltaCon graph similarity metric - a higher value
corresponds to a closer similarity to the original graph.
Storage. Low storage represents another requirement
for our method, since we try to use the minimum
amount of edges that preserve the connectivity by
making use of the spatial proximity properties of SIG.
The total number of edges for each graph can be seen
in Figure 7, where the results are presented with re-
spect to the number of vertices. Our method achieves
the lowest number of edges and hence, has the lowest
storage requirement. Our number of edges is lower
than the ground truth since the ground truth number
of edges is extracted from triangulated meshes, which
contain some redundant edges with respect to connec-
tivity.
Surface Approximation: Geodesic. We are also
comparing the distance between pairs of nodes in our
graph to the geodesic distance over the ground truth
surface, computed using the Heat Method (Crane
et al., 2017). This way, we measure how close the
graph edges follow the surface. For all pairs of nodes
in the original mesh, we compute the ratio between
the geodesic distance over the original mesh and the
shortest distance between the same nodes in SIG and
between the same nodes in the kNN graphs. The re-
Figure 7: Number of edges in graphs plotted against the
number of vertices. We consistently obtain the smallest
number of edges by a large margin, while still correctly pre-
serving the original connectivity.
sults are shown in Figure 8, where we present the ratio
of distances in relation to the number of vertices in the
input. The differences between buckets are due to the
varying number of input datasets in each bucket, as
well as the type of meshes - a single mesh with close
sheets and sparse sampling, such as the one presented
in Figure 9 highly increases the error for the connec-
tivity graphs. We aim to obtain a resulting ratio of
1, as values lower than 1 indicate longer paths in the
proximity graphs, while values higher than 1 would
imply the existence of shortcuts (too many edges) in
the connectivity graphs. Our method is consistently
close to the desired ratio of 1 across the tested meshes,
without the need to tune any parameters. Even if
for some of the tested input ranges some of the kNN
graphs have better results, these are not universal and
the user would need to adjust k depending on the us-
age, which is an issue solved by our method.
Application: Normal Estimation. We propose SIG
as a connectivity graph that encodes surface proper-
ties well, and can act as an alternative for the com-
monly used kNN graphs. One usual application is
Figure 8: Ratio of the geodesic distance traced on the sur-
face to the shortest path in the computed graph, ideally 1.
Figure 9: Sparse sampling of close sheets (the parallel
tower-like structures in the center) generates edges across
the surface. These skew our measurement of the geodesic
ratio to the shortest distance, as the surface originally fol-
lows the U-structure, while our graph shortcuts it through
the edge connecting the two towers, highlighted in blue.
However, similar behavior is exhibited by the kNN graphs,
since all of them are distance-based.
normal computation for unstructured point clouds us-
ing PCA. Even though more advanced normal com-
putation methods have been developed, constructing
them using PCA on a connectivity graph still repre-
sents a widely used method and good results in this
direction indicate an overall good representation of
the underlying surface. Moreover, we are not aiming
to improve the normal computation in general, but to
show that our graph can be used in similar applica-
tions as kNN.
For each vertex, we computed the covariance
matrix using its neighbors and extracted the normal
as the normalized eigenvector corresponding to the
smallest eigenvalue. We do not consistently orient
the normals, as this can be done in a post-processing
step and we are only interested in the angle difference
Figure 10: Angle variation between normals computed us-
ing PCA over connectivity graphs and original, face-based
normals. We compute the mean and the standard deviation
of the angle difference, and the root mean square error. All
of the methods achieve similar deviations. The overall error
is high due to the sharp angles in the input dataset.
(a) Ground-truth normals computed using the incident
faces of each vertex.
(b) Normals computed with PCA using the SIG con-
nectivity. The sparse sampling creates parallel lay-
ers and normals are oriented accordingly since the top
vertices do not get connected across layers. However,
this is an issue encountered by distance-based meth-
ods in general.
Figure 11: Example of how CAD-like models with sparse
sampling affect the computed connectivity, and hence, the
normal computation.
(a) Ground-truth normals computed using the incident
faces of each vertex.
(b) PCA normals computed using SIG are very close
to the ground truth. Normals are computed for every
vertex, but since we do not orient them consistently,
some of them are facing the other way and are not
visible. Note that for our evaluation, orientation does
not matter, and consistency is usually achieved with a
post-processing step.
Figure 12: Improved normal computation of our method for
more uniformly sampled meshes.
when compared to the ground truth, which can
be computed without the consistent orientation.
For the original meshes, we used the triangulated
faces to compute the normals. We do not use the
ground truth edge graph since that would bias the
normal computation in the direction of a specific
triangulation. Instead, face-based normal computa-
tion takes into account more information about the
surface, and not only a specific 1-ring. Then, we
computed the average angle deviation for SIG and
the kNN graphs when compared to the ground truth
normals. Results are presented in Figure 10, where
the difference among the various tested graphs is less
than 1 degree for all the metrics. Since the chosen
dataset contains surfaces that are sparsely sampled,
the normal computation achieved high errors for
all graphs. Thus, for this metric, we resampled the
chosen dataset (adding new vertices along edges
longer than a specified threshold and retriangulating),
obtaining models with up to 7k vertices. An example
of how sparse sampling, which is also an issue in
LIDAR scans, can cause problems, is presented in
(a) 6NN creates bridges between the two hemi-
spheres, since the graph does not consider local densi-
ties. Increasing the k value only aggravates the issue,
as more bridge edges will be constructed.
(b) SIG only creates edges on each hemisphere, with-
out crossing the gap between the two surface sheets.
Figure 13: Different sampling densities on two surface
sheets that are close together - the two hemispheres are not
connected as ground truth.
Figure 11, where there is not enough information
for the vertices placed on edges to have their normal
computed correctly. However, for well-sampled
models, the normals are close to the ground truth -
Figure 12. The overall angle deviation is still high
for all methods, since some of the meshes exhibit
sharp angles, for which the normal computation is
also erroneous for all graphs.
Timings. Due to the proved bounded radius in which
SIG neighbors are found, our method’s timings are
comparable to kNN, as can be observed in Figure 14.
We observe a linear increase in the computational
time with the number of vertices, which is expected
due to the linear nature of our algorithm. Our method
is only slightly slower than 6NN, but achieves better
results overall and manages to do so with many fewer
edges.
All experiments have been performed using
an AMD Ryzen 7 5800 processor. Both kNN
and SIG graphs have been implemented using the
Figure 14: Timings of our method compared to kNN graphs
for inputs with various numbers of vertices.
Figure 15: Parallel layers of sampling result in disconnected
ring-like structures as can be observed on the spider’s body
and legs. However, kNN graphs exhibit similar issues if the
sampling is too sparse and nodes are clustered in layers.
scipy.spatial.KDTree in python.
Limitations. Since our method depends on distances,
non-uniform sampling may negatively affect the re-
sult, as is commonly the case with connectivity re-
construction. An example can be seen in Figure 15,
where the spider’s legs and top of the body are uni-
formly sampled along parallel layers. For real-world
point clouds, LIDAR scans can produce such arti-
facts. These configurations are difficult to handle for
all methods, as they may fail to connect subsets of
the point cloud. Such issues could be mitigated by
employing an incremental SIG - using the next near-
est neighbors until a specific vertex degree or average
neighbor angle has been reached for the current graph.
However, in the case of different sampling densi-
ties on distinct parts of the same object, our method
has an advantage over kNN. Our method is less likely
to create edges between surface sheets that are geo-
metrically close, but geodesically distant (Figure 13).
(a) Noisy. (b) Denoised. (c) SIG.
Figure 16: Denoising pipeline that would allow our method
to give good results on noisy point clouds. The noisy point
cloud of a cube is denoised in 16b using the Bilateral Fil-
ter (Digne and de Franchis, 2017), and then used as input
for our SIG computation, resulting in a graph that closely
approximates the original cube.
Our method is not robust to noise by design, as
it computes a distance-based neighborhood, exhibit-
ing similar drawbacks as kNN graphs. Noisy point
clouds could still be used with our method, provided
they have been cleaned in a pre-processing step us-
ing, for example, PointCleanNet (Rakotosaona et al.,
2020), the Bilateral Filter (Digne and de Franchis,
2017) or Score-Based Denoising (Luo and Hu, 2021),
as demonstrated in Figure 16.
5 CONCLUSIONS
We present an alternative to the commonly used
kNN graphs for establishing the connectivity of point
clouds: the SIG, a parameter-free proximity graph. In
our work, we introduce novel spatial constraints for
the extent of SIG edges, leveraging this new property
to enhance its computational efficiency. We demon-
strate the SIG’s improved connectivity representation
that is parameter-free. Moreover, as a sparse graph,
it has a lower edge count, thus minimizing storage
requirements. Consequently, it offers three key
advantages over kNN: no need for parameter tuning,
sparsity, and improved connectivity encoding. As an
incidental application, we have shown that computed
normals are of competitive quality to kNN.
Future Work. We aim to utilize the advantage of
parameter-free improved connectivity for surface re-
construction. Moreover, we are planning to use the
SIG neighborhood (with possible extensions to nth
nearest neighbor) in graph-convolutional networks for
learning from 3D point cloud data. We also plan to in-
vestigate how our method can create an advantage in
other fields, such as motion planning and simulations.
ACKNOWLEDGMENTS
This work has been partially funded by the Austrian
Science Fund (FWF) project no. P32418-N31 and
by the Wiener Wissenschafts-, Forschungs- und Tech-
nologiefonds (WWTF) project ICT19-009.
REFERENCES
Amenta, N. and Bern, M. (1999). Surface reconstruction by
voronoi filtering. Discr. & Comp. Geom., 22:481–504.
Boulch, A. and Marlet, R. (2016). Deep learning for ro-
bust normal estimation in unstructured point clouds.
Computer Graphics Forum, 35(5):281–290.
Charles, R. Q., Su, H., Kaichun, M., and Guibas, L. J.
(2017). Pointnet: Deep learning on point sets for 3d
classification and segmentation. In 2017 IEEE CVPR,
pages 77–85.
Crane, K., Weischedel, C., and Wardetzky, M. (2017).
The heat method for distance computation. Commun.
ACM, 60(11):90–99.
de Figueiredo, L. H. and Paiva, A. (2022). Region recon-
struction with the sphere-of-influence diagram. Com-
puters & Graphics, 107:252–263.
Dey, T. K. and Goswami, S. (2006). Provable surface recon-
struction from noisy samples. Computational Geom-
etry, 35(1):124–141. Special Issue on the 20th ACM
Symposium on Computational Geometry.
Digne, J. and de Franchis, C. (2017). The bilateral filter for
point clouds. Image Processing On Line, 7:278–287.
Dwyer, R. A. (1995). The expected size of the sphere-of-
influence graph. Comp. Geometry, 5(3):155–164.
Edelsbrunner, H., Kirkpatrick, D., and Seidel, R. (1983).
On the shape of a set of points in the plane. IEEE
Transactions on Information Theory, 29(4):551–559.
Erler, P., Guerrero, P., Ohrhallinger, S., Mitra, N. J., and
Wimmer, M. (2020). Points2surf learning implicit sur-
faces from point clouds. In Computer Vision–ECCV
2020, Proceedings, Part V, pages 108–124. Springer.
Guennebaud, G. and Gross, M. (2007). Algebraic point set
surfaces. ACM Trans. Graph., 26(3):23–es.
Guerrero, P., Kleiman, Y., Ovsjanikov, M., and Mitra,
N. J. (2018). Pcpnet learning local shape properties
from raw point clouds. Computer Graphics Forum,
37(2):75–85.
Jaromczyk, J. and Toussaint, G. (1992a). Relative neigh-
borhood graphs and their relatives. Proceedings of the
IEEE, 80(9):1502–1517.
Jaromczyk, J. W. and Toussaint, G. T. (1992b). Relative
neighborhood graphs and their relatives. Proc. IEEE,
80:1502–1517.
Kazhdan, M., Bolitho, M., and Hoppe, H. (2006). Poisson
Surface Reconstruction. In Symposium on Geometry
Processing. The Eurographics Association.
Kirkpatrick, D. G. and Radke, J. D. (1985). A framework
for computational morphology. Machine Intelligence
and Pattern Recognition, 2:217–248.
Klein, J. and Zachmann, G. (2004). Point cloud surfaces us-
ing geometric proximity graphs. Computers & Graph-
ics, 28(6):839–850.
Koutra, D., Shah, N., Vogelstein, J. T., Gallagher, B., and
Faloutsos, C. (2016). Deltacon: Principled massive-
graph similarity function with attribution. ACM Trans.
Knowl. Discov. Data, 10(3).
Liu, Z., Xiao, X., Zhong, S., Wang, W., Li, Y., Zhang, L.,
and Xie, Z. (2020). A feature-preserving framework
for point cloud denoising. Computer-Aided Design,
127:102857.
Luo, S. and Hu, W. (2021). Score-based point cloud denois-
ing. In 2021 ICCV, pages 4563–4572.
Marin, D., Ohrhallinger, S., and Wimmer, M. (2022). Sigdt:
2d curve reconstruction. CGF, 41(7):25–36.
Michael, T. and Quint, T. (1999). Sphere of influence graphs
in general metric spaces. Mathematical and Computer
Modelling, 29(7):45–53.
Mitra, N. J. and Nguyen, A. (2003). Estimating surface
normals in noisy point cloud data. In Proceedings of
the Nineteenth Annual Symposium on Computational
Geometry, SCG ’03, page 322–328, New York, NY,
USA. Association for Computing Machinery.
Pauly, M., Keiser, R., Kobbelt, L., and Gross, M. (2003).
Shape modeling with point-sampled geometry. ACM
SIGGRAPH 2003 Papers, SIGGRAPH ’03.
Rakotosaona, M.-J., La Barbera, V., Guerrero, P., Mitra,
N. J., and Ovsjanikov, M. (2020). Pointcleannet:
Learning to denoise and remove outliers from dense
point clouds. Comp. Graph. Forum, 39(1):185–203.
Shi, W. and Rajkumar, R. (2020). Point-gnn: Graph neural
network for 3d object detection in a point cloud. In
Proc. of the IEEE/CVF conference on computer vision
and pattern recognition, pages 1711–1719.
Toussaint, G. T. (1988). A graph-theoretical primal sketch.
In Machine Intelligence and Pattern Recognition, vol-
ume 6, pages 229–260. Elsevier.
Wang, L., Huang, Y., Hou, Y., Zhang, S., and Shan, J.
(2019). Graph attention convolution for point cloud
semantic segmentation. In 2019 CVPR, pages 10288–
10297.
Zhou, Q. and Jacobson, A. (2016). Thingi10k: A dataset of
10,000 3d-printing models. arXiv:1605.04797.