=Paper=
{{Paper
|id=Vol-3349/paper7
|storemode=property
|title=Symmetry-Based 3D Object Completion using Local
Geometry Features
|pdfUrl=https://ceur-ws.org/Vol-3349/paper7.pdf
|volume=Vol-3349
|authors=Daria Omelkina,Pavlo Hilei,Oles Dobosevych,Rostyslav Hryniv,Taras Rumezhak,Vladyslav Selotkin,Volodymyr Karpiv
|dblpUrl=https://dblp.org/rec/conf/cvww/OmelkinaHDHRSK23
}}
==Symmetry-Based 3D Object Completion using Local
Geometry Features==
https://ceur-ws.org/Vol-3349/paper7.pdf
Symmetry-Based 3D Object Completion using Local
Geometry Features
Daria Omelkina1, Pavlo Hilei1, Oles Dobosevych1, Rostyslav Hryniv1, Taras Rumezhak1,2,
Vladyslav Selotkin2 and Volodymyr Karpiv2
1
Ukrainian Catholic University ML Lab, Ukrainian Catholic University, Lviv, Ukraine
2
SoftServe, Ukraine
Abstract
3D scanning of real-world objects has become an integral step of many manufacturing processes and digital image processing
applications. Despite the impressive progress in modern 3D scanning technology, the produced 3D models often suffer
from defects due to occlusions, poor light conditions, special surface reflection properties, scanner displacements, imperfect
algorithms, etc. Point cloud completion is a standard post-processing step aiming at removing or smoothing such irregularities.
In this article, we propose a novel method for damage completion of 3D objects possessing reflection symmetry. Such
symmetries are identified by matching local shape features such as curvatures and edges in mesh and point cloud representa-
tions of the objects. We describe the pipeline of our method, justify its steps, and evaluate its performance on the ModelNet40,
a Princeton 3D object dataset. The results demonstrate comparable improvement in the damaged 3D object completion to
popular neural network-based and symmetry-based approaches.
Keywords
completion, point cloud, mesh, curvatures, reflection symmetry
1. Introduction ings that often suffer from significant time damage).
The main idea is that in mirror-symmetric objects, all
Advances in modern 3D scanning technology have led local shape features are also symmetrically distributed.
to a significant boost in computer vision post-processing For instance, the principal curvatures of symmetric
tools for 3D models. One of the standard tasks of 3D points are the same, and the principal directions enjoy
scanning is completing the obtained 3D models that suffer the same symmetry; likewise, all linear edges in symmet-
from poor light conditions, occlusions, surface reflection, ric objects can be split into symmetric pairs. The search
etc. This completion task has been approached in many for global mirror symmetries can be based on pairs of
different ways, in particular, using neural networks pre- points with similar curvatures and/or edges. Each such
trained on certain object classes. Although such methods pair creates a potential symmetry plane, and the majority
show good results for new objects from these classes, vote determines the best mirror symmetry. The latter
their performance on previously unseen object types is then used to compare and combine the object and its
drops significantly. Therefore, alternative algorithms mirror image and thus complete the missing or damaged
capable of completing previously unseen objects are of parts.
vital importance. That approach demonstrated competitive results in
In this paper, we suggest a novel approach to 3D model comparison to a known traditional symmetry-based
completion based on the geometric features of mirror- method of point cloud completion and three deep learn-
symmetric objects. Since this type of symmetry is typi- ing method. More details on the methods for comparison
cal in man-made environments, such an assumption is are given in the following sections.
not very restrictive. Finding plane symmetry in approxi-
mately symmetric 3D models is the most important step;
we then use it to complete any damages and holes which 2. Related work
could occur during scanning or were already present in
the real-life scanned object (e.g., in archaeological find- As mentioned above, damages in 3D objects can be re-
paired by using missing information from their symmetri-
26th Computer Vision Winter Workshop, Robert Sablatnig and Florian cally transformed images. There are two main directions
Kleber (eds.), Krems, Lower Austria, Austria, Feb. 15-17, 2023 for symmetry plane detection in 2D/3D data: classical
$ omelkina@ucu.edu.ua (D. Omelkina); p.hilei@ucu.edu.ua
(P. Hilei); dobosevych@ucu.edu.ua (O. Dobosevych);
and deep learning approaches. In this paper, we aim to
rhryniv@ucu.edu.ua (R. Hryniv); rumezhak@ucu.edu.ua extend the classical approach as more robust for previ-
(T. Rumezhak); vselo@softserveinc.com (V. Selotkin); ously unseen objects and thus review the corresponding
vkarpi@softserveinc.com (V. Karpiv) algorithms first.
© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0). One of the approaches for symmetry-based point cloud
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
1
Daria Omelkina et al. CEUR Workshop Proceedings 1–8
completion is discussed in [1], where the authors pro- block for modelling local geometries to the transformer.
pose a three-step algorithm consisting of symmetry plane We compare the performance of our method to the per-
estimation via Principal Component Analysis (PCA), it- formance of one traditional [1] and three deep learning
erative improvement of the symmetry plane via Iterative [12], [13], [14] methods.
Closest Point (ICP), and, finally, hole detection and filling.
The paper [1] has served as motivation for the current
work, in which we tried to make symmetry plane search 3. The completion algorithm
more geometry-aware and preserve the robustness and
The pipeline of the proposed method consists of the fol-
light weight of the algorithm (cf. Section 4.2 for perfor-
lowing steps (discussed below in more detail):
mance comparison).
The principal idea of our geometry-aware symmetry 1. 3D model representation: triangle mesh, point
detection is based on the paper [2]. In this paper, Mi- cloud and principal curvatures.
tra et al. used the so-called signatures of the geometric 2. Finding symmetry planes using the curvature-
shapes represented by principal curvatures, principal di- based algorithm.
rections, and normal vectors to detect local symmetries 3. Finding symmetry planes using the edge-based
in the objects. We borrow the idea of matching local algorithm.
geometries from [2] but also add edge-based symmetry 4. Mean Shift Clustering and determining the best
detection to the pipeline to include man-made objects of symmetry plane.
predominantly planar shape. The edge detection method 5. Using the best symmetry plane for 3D model com-
in point clouds suggested by Ahmed et al. in [3] uses pletion.
very simple and clear geometric arguments, and we have
implemented it in our algorithm. As a pre-processing step, we scale the meshes of 3D
The paper [4] by Mitra et al. is a detailed report on objects to boost the parameter tuning and to make the
different symmetry detection and application methods final results statistically interpretable.
for 3D objects. They include symmetry detection meth-
ods for meshes and/or point clouds: graph-based ap- 3.1. Principal curvatures and principal
proaches, RANSAC-based verification (e.g., sliding dock-
directions of the 3D model
ers approach in [5]), multidimensional scaling (e.g., in-
trinsic structure detection in [6]), voting for a symmetry The input of our method is a (scaled) triangular 3D mesh
transform (e.g., partial intrinsic reflection symmetries of an object, which is used to calculate the principal curva-
extraction in [7]), etc. tures and directions. Principal curvatures at a surface
Recently, deep learning algorithms have become state- point characterize locally extremal surface bending in
of-the-art solutions in different areas, especially for com- the respective principal directions in the tangent plane.
puter vision tasks. Various neural networks were pro- Principal curvatures and directions describe well the ap-
posed for symmetry detection, data completion, segmen- proximate local surface shape. For example, principal
tation, classification, and other tasks for processing 3D curvatures of a small absolute value represent a rela-
data. Examples of successful solutions include but are tively flat surface, while greater curvatures correspond
not limited to [8], [9], [10], [11] etc. to saddle-like or ellipsoid-like behavior. Abrupt changes
The authors of MSN (Morphing and Sampling Net- of principal curvatures indicate a possible edge.
work) thoroughly describe their model in [12]. Their ap- Under mirror symmetry, the pairs of symmetric points
proach to point cloud completion consists of two stages. share the same curvatures, while their principal direc-
Firstly, they use an auto-encoder to predict the completed tions and normals are mirror symmetric. As suggested
object by morphing the unit squares into a collection of in [2], this can be used to detect the mirror symmetry:
surface elements. Secondly, they merge that output with we cluster the points with equal (up to a threshold) prin-
the original damaged object and feed a subset point cloud cipal curvatures, single out those pairs of points that
to a residual network. After that second stage, they ob- have compatible principal directions, and then calculate
tain the final completed point cloud. The approach in potential plane symmetry for each compatible pair. If
[13] is also based on residual networks. They use 3D this plane symmetry passes the patch symmetry check
grids as an intermediate representation of point clouds (i.e., if the plane mirrors these points into one another
and introduce two novel gridding layers. This approach along with some of their neighborhoods), we approve it
allows using 3D convolutions on the unordered and ir- to participate in the further majority voting for the most
regular point cloud data. The authors of [14] introduce optimal plane.
PoinTr – a transformer encoder-decoder model. They We use the principal_curvature function from
represented point clouds as unordered groups of points the libigl library [15] to calculate the principal curvatures
with position embeddings and added a geometry-aware
2
Daria Omelkina et al. CEUR Workshop Proceedings 1–8
Figure 1: Overview of the main pipeline steps.
of the mesh. As suggested in [16], this function first fits neighborhood search in later stages. Also, for each ver-
locally a quadratic polynomial tex xi , we calculate the corresponding principal curva-
(i) (i)
2 2
f (x, y) = ax + 2bxy + cy + dx + ey (1) tures k1 , k2 and save the results in a separate file as
a dictionary with keys xi and principal curvatures as
to the surface and then computes the principal curva- values.
tures and directions as eigenvalues k1 , k2 and eigenvec-
tors d1 , d2 of the corresponding shape operator (a 2 × 2 3.2.2. Curvature-based point clustering
matrix) explicitly given in terms of the parameters a to e.
Observe that signs of the principal curvatures depend on Candidates for symmetry planes are collected by detect-
the surface orientation: if d1 and d2 are interchanged, ing symmetric patches in the point cloud. We start with
then the curvatures k1 , k2 become −k2 , −k1 . We, there- two compatible points, determine their symmetry plane,
fore, order the principal curvatures so that k1 ≥ |k2 |. and then verify if it matches some neighborhoods of these
We would like to mention that the points. Since symmetric patches have symmetric local
principal_curvature function does not allow shapes, we run through point pairs with close principal
small triangle clusters (i.e., sets of triangles connected in curvatures. We cluster the vertices of the point cloud
a mesh). Therefore, before computing curvatures, we with similar curvatures using the Mean Shift algorithm.
extract information about triangle clusters in the mesh To speed up bandwidth estimation for the Mean Shift al-
and delete the clusters of size less than 10. gorithm, we fix the quantile at 0.005 and use only point
samples of size 500; we also enable the bin_seeding op-
tion for the Mean Shift algorithm to decrease its running
3.2. Curvature-based algorithm
time.
Curvature-based algorithm uses principal curvature
information to match potentially symmetric points on 3.2.3. Within-cluster symmetry plane detection
the point cloud representing the 3D object. It proceeds and validation
in the following steps:
For each cluster, we iterate through all point pairs A
1. Data preparation
and B and first check that their principal curvatures
2. Curvature-based point clustering
3. Within-cluster symmetry plane detection and val-
idation
The result of these steps is an array-like structure of
approved planes that take part in the final best symmetry
plane voting described in Section 3.4.
3.2.1. Data preparation
Figure 2: Curvature-based algorithm diagram. For demon-
Given a 3D mesh with vertices xi , i = 1, . . . , n, we stration purposes, only a couple of point pairs are shown
form the point cloud and then create a k-d tree for fast
3
Daria Omelkina et al. CEUR Workshop Proceedings 1–8
(𝑘1,𝐴 , 𝑘2,𝐴 ) and (𝑘1,𝐵 , 𝑘2,𝐵 ) are approximately equal,
in the sense that
⃒ 𝑘1,𝐴 ⃒ 𝑘2,𝐴
⃒ ⃒ ⃒ ⃒
− 1 ⃒ ≤ 𝜀1 , − 1 ⃒ ≤ 𝜀1 , (2)
⃒ ⃒
𝑘1,𝐵 𝑘2,𝐵
⃒ ⃒
with some predefined curvature closeness threshold 𝜀1 ; if
|𝑘1,𝐵 | ≤ 𝜀1 or |𝑘2,𝐵 | ≤ 𝜀1 , then we require instead that
|𝑘1,𝐴 | ≤ 𝜀1 or |𝑘2,𝐴 | ≤ 𝜀1 , respectively. Figure 3: Edge-Based algorithm diagram.
For each point pair 𝐴, 𝐵 that has passed the above test,
we draw the median perpendicular plane 𝜋 and represent
it via its Hough coordinates—the unit normal vector n 3.3.1. Data preparation and parameter tuning
and the (signed) distance 𝑑 to the origin. The mirror
reflection 𝑆𝜋 is then given by Here we work directly with the point cloud representa-
⊤
tion of the 3D object. The point cloud is obtained from
𝑆𝜋 (x) = (𝐼3 − 2nn )x + 2𝑑n, (3) the mesh using the Poisson Disc Sampling algorithm
where 𝐼3 is the 3 × 3 identity matrix. We fix the direction implemented in the Open3D library [17].
of n so that its first non-zero entry is positive; the signed The edge-based algorithm requires several parame-
distance 𝑑 is then the scalar product of d and the vector ters; most remain default (see Section 4.3). However, the
−−→ following need to be tuned for each model:
𝑂𝐶 from the origin 𝑂 to the midpoint 𝐶 of 𝐴 and 𝐵.
In the next step, we perform the patch symmetry • quantile in the edge point clustering affects the
validation of 𝑆𝜋 . We form patches 𝑃𝐴 and 𝑃𝐵 of the number of clusters and thus the number of fitted
points 𝐴 and 𝐵 consisting of their closest 𝑚 = 200 lines;
points of the point cloud. Then we mirror reflect 𝑃𝐴 to • line closeness threshold 𝜀2 sets tolerance within
get 𝑃𝐴′ = 𝑆𝜋 (𝑃𝐴 ) and check if adding it to 𝑃𝐵 does which two lines are considered parallel or inter-
not significantly change the geometry of the latter. We secting and thus influences mirror symmetry pre-
transform 𝑃𝐴′ ∪ 𝑃𝐵 into a mesh, recalculate the cur- cision;
vatures (𝑘1′ (x), 𝑘2′ (x)) of each point x ∈ 𝑃𝐵 in this
• line expansion option leads to improvement in
larger mesh, and compare them with the initial curva-
some models;
tures (𝑘1 (x), 𝑘2 (x)). If the mean squared error (MSE)
• edge detection threshold parameter 𝜆 can be left
1 ∑︁ (︀ ′ at the default value for most 3D objects, but, in
mse(𝜋) = |𝑘1 (x)−𝑘1 (x)|2 +|𝑘2′ (x)−𝑘2 (x)|2
)︀
𝑚 x∈𝑃
𝐵
some cases, a smaller value (allowing more edge
(4) candidates) leads to better performance.
does not exceed some threshold 𝐾, then the potential
symmetry plane 𝜋 is validated, gets the weight 𝑤(𝜋) := 3.3.2. Edge point detection and clustering
1/mse(𝜋), and is passed to the final majority vote.
To speed up the algorithm, we keep an array of planesIn the first step, we iterate over points in the point cloud
that have already been rejected, and if a new plane 𝜋 isand apply the detection algorithm of [3] to find potential
edge points. The algorithm is based on the observation
very close to one in the array, we skip the patch symmetry
step and update the array with 𝜋. To transform point that if the surface is smooth around its point p, i.e., can
clouds into meshes, we used the Ball Pivoting algorithm be represented in local coordinates via (1), then the differ-
from the Open3D library [17]. ence between p and the centroid of 𝑘 nearest neighbors
(kNN) of p is of the second order of the 𝑥𝑦 span of these
neighbors.
3.3. Edge-based algorithm Following this observation, we fix 𝑘 = 200, denote
Many man-made objects have edges or planar parts, for by 𝒩 (p) the kNN of p, by c(p) the centroid of 𝒩 (p),
which curvatures are not well-defined or are uninfor- introduce the spacing parameter
mative. However, the edge lines in mirror-symmetric
objects are also symmetric and can be used for symmetry 𝑟 := min ‖p − q‖, (5)
q∈𝒩 (p)
detection. The edge-based algorithm exploits this and
proceeds as follows: and declare p a potential edge point if
1. Data preparation and parameters tuning ‖p − c(p)‖ > 𝜆𝑟 (6)
2. Edge point detection and clustering
3. Line fitting and expansion with edge detection threshold parameter 𝜆. In that case, p
4. Finding symmetry planes is added to the list of potential edge points.
4
Daria Omelkina et al. CEUR Workshop Proceedings 1–8
In the next step, we apply the Mean Shift cluster- If the lines ℓ1 and ℓ2 have been declared parallel,
ing algorithm to detect clusters in the set of potential then their symmetry plane 𝜋 is determined by
edge points, which will be fitted to lines. We enable its point 𝐶 that is the midpoint of 𝑂1 and 𝑂2
bin_seeding for speed-up and use a predefined set of the and the unit normal vector n that is collinear to
quantile parameters for bandwidth estimation. q − (q · d1 )d1 ; the distance 𝑑 from the plane 𝜋 to
the origin in the Hough parametrization is then
−−→ −−→
3.3.3. Line fitting and expansion 𝑑 = (𝑂𝑂1 + 𝑂𝑂2 ) · n/2.
3. Intersecting lines: Once the lines ℓ1 and ℓ2 have
For each cluster of potential edge points of size at least 3,
been found coplanar, not coincident, and not par-
we run RANSAC with the LineModelND least square
allel, they are considered intersecting. Then there
estimation [18] to fit a line. The algorithm returns a
are two symmetry planes through the intersec-
point on the fitted line and its unit direction vector. We
tion point 𝐷 and with the unit normal vectors
save the number of inliers for each fitted line to be used
n collinear to d1 + d2 or d1 − d2 , respectively.
as weights during the final symmetry plane voting. To
We identify 𝐷 as the midpoint of the interval
ensure reproducibility, we set 100 as a predefined random
𝐷1 𝐷2 of the shortest length when 𝐷1 ∈ ℓ1
state in RANSAC.
and 𝐷2 ∈ ℓ2 . We find 𝐷1 = 𝑂1 + 𝑠1 d1 and
If the line expansion option is on, for each fitted line ℓ, −−−→
𝐷2 = 𝑂2 +𝑠2 d2 by noting that the vector 𝐷1 𝐷2
we calculate the largest distance 𝛿 from ℓ to its inliers
must be orthogonal to d1 and d2 , so that
from the respective potential edge points cluster, then
find all the points of the point cloud that are within 𝛿- (q + 𝑠2 d2 − 𝑠1 d1 ) · d1 = 0, (10)
neighbourhood of ℓ, join them to the inlier set, and refit (q + 𝑠2 d2 − 𝑠1 d1 ) · d2 = 0. (11)
the line ℓ to this enlarged inlier set using LineModelND.
Line expansion often helps in cases where edge detec- Solving this linear system for 𝑠1 and 𝑠2 , we find
tion is not accurate and some of the points on edges are 𝐷1 , 𝐷2 , their midpoint 𝐷, and thus the two sym-
missing. metry planes.
Symmetry planes 𝜋 constructed this way get their
3.3.4. Finding symmetry planes weights 𝑤(𝜋) equal to the smaller inlier numbers for the
lines ℓ1 and ℓ2 . After all symmetry planes have been
At this point, we have a set of lines fitted to the edges of found, we start the final symmetry plane voting.
the 3D object, each parametrized by one of its points and
unit direction vector d. Now we iterate through all line
pairs, for those that are parallel or intersect, construct 3.4. Voting for the best symmetry plane
the corresponding symmetry planes, and skip pairs of In the previous two steps, we constructed lists of poten-
skew lines. tial symmetry planes for the 3D object using curvature-
Assume that given are the lines ℓ1 (𝑂1 , d1 ) and based and edge-based approaches. The best symmetry
−−−→
ℓ2 (𝑂2 , d2 ); we set q = 𝑂1 𝑂2 and perform the following plane can now be chosen in three different ways: among
steps. the curvature-based planes only, among the edge-based
planes only, or the best in the combined list. In the latter
1. Coplanarity check: The lines ℓ1 and ℓ2 are consid-
case, some preprocessing is needed to eliminate the effect
ered coplanar if the mixed product of the vectors
of different scales of plane weights generated by the two
d1 , d1 , and q is sufficiently small, in the sense
methods.
that
The first option is to take 𝑛 best symmetry planes from
|(d1 × d2 ) · q| < 𝜀2 ‖q‖ (7)
each list, where 𝑛 is the smaller of two sizes, and the
with line closeness threshold 𝜀2 . Otherwise, the planes are ordered by their weights, from the largest
lines are considered skew and thus are skipped. to the smallest one. The second option is to rescale the
2. Parallel lines: The lines ℓ1 and ℓ2 are parallel if weights for the curvature-based planes so that the total
their direction vectors d1 and d2 are collinear up weights in both sets become equal. Experiments show
to some tolerance, e.g., if that for some 3D objects, the first option is better, while
for others—the second one, so we try both during the
|d1 · d2 | > 1 − 𝜀2 ; (8) grid search of parameters.
Given the list of potential symmetry planes, we apply
to make sure the lines do not coincide, we require the Mean Shift clustering algorithm to determine the
that also ‖q‖ > 𝜀2 and largest cluster. As a pre-processing step, we rescale the
Hough coordinate 𝑑 for the planes to
|d1 · q| < (1 − 𝜀2 )‖q‖. (9)
˜ := 𝑑/(max |𝑑|)
𝑑 (12)
5
Daria Omelkina et al. CEUR Workshop Proceedings 1–8
so that it should lie within the interval [−1, 1]. The rea-
son is that the normal vectors of the planes are of the unit
norm while their distances 𝑑 to the origin are typically
on the scale from −104 to 104 and thus would dominate
during the voting. As before, we use the Mean Shift clus-
tering with the enabled bin_seeding option and estimate
the bandwidth using the predefined quantile parameter
set.
Now we choose the biggest cluster ℒ and take its
weighted average as the best symmetry plane:
∑︀ ∑︀ Figure 4: Comparing different approaches to object comple-
𝜋∈ℒ 𝑤(𝜋)n(𝜋) ˜* = ∑︀ 𝜋∈ℒ 𝑤(𝜋)𝑑(𝜋)
n* = 𝑐 ∑︀ , 𝑑 ; tion: [13], [14], [12], [1], ours.
𝜋∈ℒ 𝑤(𝜋) 𝜋∈ℒ 𝑤(𝜋)
(13)
we then rescale 𝑑˜* to its actual value 𝑑* = 𝑑
˜* · (max |𝑑|),
makes the resulting metrics better comparable. In some
cf. (12).
cases, we performed subdivision of triangles of original
meshes to create more realistic damages.
3.5. Model completion
After the best hypothetical mirror symmetry 𝑆𝜋 for the 4.2. Results and analysis
point cloud 𝒞 has been chosen, we use it to fill in the miss-
We evaluated the developed algorithm on the generated
ing or damaged parts of 𝒞 following the steps described
dataset. For each object, we used a grid search with a time
in [1]. We form the mirrored object 𝒞 ′ := 𝑆𝜋 (𝒞), and
limit to find optimal parameters for solo and combined
for each point p in 𝒞 ′ decide if it should be added to 𝒞.
versions of the algorithm (see Section 4.3). With those
We do that if and only if there are no points of 𝒞 among
optimal parameters, we ran the algorithm to produce
the 𝑘 = 6 nearest neighbors of p in the combined point
the symmetry planes and the corresponding completion
cloud 𝒞 ∪ 𝒞 ′ . To speed up the kNN search, a k-d tree from
metrics and saved the best results for solo and combined
this combined point cloud is constructed beforehand.
algorithms. We used following metrics for result evalua-
If the ground truth model 𝒞0 is available, we can decide
tion:
on the quality of completion using the Chamfer distance
between 𝒞0 and the completed 𝒞; otherwise, some other 1. The Chamfer distance between the original un-
measures are used (see Section 4.2). damaged object and the completed object. This
metric tells us how well the damaged object was
completed by our algorithm.
4. Algorithm evaluation results 2. Improvement rate metric shows how much better
is completion 𝒞 * relative to leaving the object
4.1. Dataset 𝒞 uncompleted. When we get 0 it means that
The suggested completion algorithm described in Sec- there was no completion, positive values indicate
tion 3 uses both mesh representation of objects as well successful completion, and negative shows that
as point clouds created from these meshes. We chose during completion, points were added in places
the Princeton ModelNet40 3D object dataset [19] for al- where they originally did not belong, and the
gorithm evaluation. It offers objects in 40 different cat- object was deformed to some extent. With 𝐶𝐷
egories. We selected 5 objects from each category that standing for the Chamfer distance and 𝒞0 the
visually seemed symmetric. In this 200-object dataset, original (undamaged) object, this value is
we transformed every mesh into a point cloud (of 50,000 100 * (1 − 𝐶𝐷(𝒞, 𝒞0 )/𝐶𝐷(𝒞 * , 𝒞0 )). (14)
points each) so that each original undamaged object is
represented both by a mesh and a point cloud. Statistics, such as mean, median, minimum, and maxi-
To make 3D objects suitable for the completion task, mum values of the improvement rate, are presented in
we inflicted damage to each of the meshes. From each Table 1. It should be noted that for testing, we used
object, a random number (between 1 and 10) of randomly models pretrained on ShapeNet, which were available
placed regions of random size totaling approximately to us; thus, it can be expected that methods that require
15% of the original size was removed; in addition, for the training, showed smaller improvement metrics than tra-
curvature computing algorithm to work, we removed all ditional methods, meant for unseen data. In general, our
small triangle clusters. Before damaging, each mesh was algorithm performed similarly to the traditional method
scaled to have approximately a unit surface area; this from [1].
6
Daria Omelkina et al. CEUR Workshop Proceedings 1–8
Statistics of Improvement rate (in %)
Completion Method (without skipping) (skipping results ≤ 0%)
Mean Median Min Max Mean Median Min Max
MSN [12] -224.2 -187.5 -1031.8 22.9 6.5 3.8 1.6 13.7
PoinTr [14] -9.2 -6.4 -103.7 36.9 10.8 8.6 0.1 36.9
GRNet [13] -10498 -4690 -118744 -8.1 - - - -
Symmetry-Based [1] -2751.4 0.5 -132980 85.5 27.2 23.8 0.1 85.5
Edge-based -202.1 -29.4 -1389 71.8 22.5 20.6 0.1 71.8
Our Curvature-based -386.8 5.3 -24147 85.6 27.1 24.8 0.2 85.6
Combined -177.0 -9.4 -13893 82.1 26.4 25.3 0.1 82.1
Table 1
Comparison of methods: statistical results with the improvement rate metric.
4.3. Parameter tuning edge detection. Small quantiles create more edge
clusters but slower computation; too big quan-
There are several parameters that control different as-
tiles lead to fewer clusters and make the algorithm
pects of the method. Some can only slightly alter preci-
less accurate. Predefined range: 0.001, 0.00525,
sion, while others significantly affect the performance of
0.007, 0.01, 0.0125, 0.025, 0.03, 0.035, 0.0375,
the algorithm. To fine-tune the most important parame-
0.05, 0.07, 0.075, 0.1, 0.125, 0.15, 0.2.
ters for each object, we performed a grid search over a
• Line closeness threshold 𝜀2 decides when points
set of predefined choices established in numerous exper-
are considered coplanar and direction vectors
iments on different meshes from several datasets; here is
collinear (absolute tolerance). Predefined range:
the resulting list:
0.0001, 0.001, 0.003, 0.007, 0.01, 0.025, 0.0375,
• Curvature closeness threshold 𝜀1 controls the 0.05, 0.075, 0.1, 0.525, 0.7, 1, 1.5, 2.
strictness of the comparison of curvatures of two • In RANSAC and linear model for line fitting, we
points. The smaller it is (e.g., 0.001), the fewer used a default value 10 for error and limited max-
points will be used to create symmetry planes, but imum number of iterations by 1000.
the accuracy can be better. Usually, the real-world • The boolean Enabling/disabling line expansion de-
data contain noise and damages, so it is better to termines if the algorithm will perform an addi-
use a less strict threshold (e.g., 0.1) and mostly tional refitting step for each line or not.
rely on a symmetry plane check on a neigh- • Symmetry plane clustering quantile for bandwidth
boring patch of the points. Predefined range: estimation, used during Mean Shift clustering for
10−8 , 10−3 , 10−3 , 0.01, 0.05, 0.07, 0.1, 0.8, 1. best symmetry plane detection; should not be too
• Surface patch closeness threshold defines how big as otherwise plane averaging over the largest
strict the patch symmetry verification is. We cluster will suffer from noise. Predefined range:
mirror reflect a neighbourhood (the kNN with 0.0005, 0.001, 0.005, 0.008, 0.01, 0.015, 0.02,
𝑘 = 200) of the point 𝐴, superimpose it with 0.05, 0.08, 0.1, 0.15, 0.2, 0.25, 0.3, 0.5, 0.7, 0.8,
a neighbourhood of its symmetric candidate 𝐵, 1, 1.1, 1.5, 2, 2.5.
and detect a change in the geometric shape. The
threshold bounds from above the MSE of curva- Predefined sets of parameters, which we used for the
tures in the neighbourhood of 𝐵 and thus con- grid search, were established through numerous experi-
trols the number of planes that pass. Predefined ments, including manual fine-tuning, modified bisection
range: 0.001, 0.01, 0.05, 0.08, 0.1, 0.5, 0.8, 1, search, incrementing, etc. The grid search was then per-
1.2, 1.5, 1.8, 2, 2.5, 3. formed on each object from the dataset.
• Number of neighbours in edge detection (200 by
default) gives the size of a neighbourhood of a
point p to determine if it is an edge point or not. 5. Conclusions
• Edge detection threshold parameter 𝜆 (default 3
or 0.1 ) determines which points are regarded as In this paper, we proposed, described, and evaluated a
edge points. Smaller 𝜆 softens the condition and four-stage pipeline (curvature matching, edge matching,
increases the number of edge points. symmetry plane voting, object completion) of solving the
• Edge points clustering quantile for bandwidth esti- completion task for previously unseen 3D objects pos-
mation is used during Mean Shift clustering for sessing global mirror symmetry. This method uses the
7
Daria Omelkina et al. CEUR Workshop Proceedings 1–8
local geometries of an object represented by principal [9] H. Xie, H. Yao, S. Zhou, J. Mao, S. Zhang, W. Sun,
curvatures and/or edges. We presented the results by solo Grnet: Gridding residual network for dense point
algorithms (based on curvatures matching or on edges cloud completion, 2020.
matching) and a combined algorithm (that performs the [10] Y. Zhou, S. Liu, Y. Ma, Nerd: Neural 3d reflection
voting on a combined set of weighted planes) on the part symmetry detector, 2021.
of the ModelNet40 dataset with random occlusions. The [11] W. Yuan, T. Khot, D. Held, C. Mertz, M. Hebert, Pcn:
approach demonstrates competitive results in compari- Point completion network, 2018.
son with the best deep learning and a symmetry-based [12] M. Liu, L. Sheng, S. Yang, J. Shao, S.-M. Hu, Mor-
method. phing and sampling network for dense point cloud
Limitations of the proposed method are that completion, Proceedings of the AAAI Conference
on Artificial Intelligence (2020).
(a) the object must possess a mirror symmetry;
[13] H. Xie, H. Yao, S. Zhou, J. Mao, S. Zhang, W. Sun,
(b) if missing parts are mirror symmetric or have a
Grnet: Gridding residual network for dense point
large intersection with their mirrored image, the
cloud completion, 2020.
object cannot be reconstructed by the algorithm;
[14] X. Yu, Y. Rao, Z. Wang, Z. Liu, J. Lu, J. Zhou, Pointr:
(c) when the symmetry plane is found rather poorly
Diverse point cloud completion with geometry-
(e.g., due to incomplete parameter tuning), then
aware transformers, 2021.
the completion is performed poorly as well;
[15] A. Jacobson, D. Panozzo, et al., libigl: A simple C++
(d) there is a significant number of parameters, some geometry processing library, 2018.
of which must be fine-tuned for each separate [16] D. Panozzo, E. Puppo, L. Rocca, Efficient multi-scale
object, making our method less robust. curvature and crease estimation, in: 2nd Interna-
tional Workshop on Computer Graphics, Computer
References Vision and Mathematics, GraVisMa 2010 - Work-
shop Proceedings, 2010.
[1] T. Rumezhak, O. Dobosevych, R. Hryniv, V. Selotkin, [17] Q.-Y. Zhou, J. Park, V. Koltun, Open3D: A modern
V. Karpiv, M. Maksymenko, Towards realistic library for 3D data processing, arXiv:1801.09847
symmetry-based completion of previously unseen (2018).
point clouds, in: Proceedings of the IEEE/CVF In- [18] S. Van der Walt, J. L. Schönberger, J. Nunez-Iglesias,
ternational Conference on Computer Vision (ICCV) F. Boulogne, J. D. Warner, N. Yager, E. Gouillart,
Workshops, 2021. T. Yu, scikit-image: image processing in Python,
[2] N. J. Mitra, L. J. Guibas, M. Pauly, Partial and ap- PeerJ (2014).
proximate symmetry detection for 3d geometry, in: [19] Z. Wu, S. Song, A. Khosla, F. Yu, L. Zhang, X. Tang,
ACM SIGGRAPH 2006 Papers, 2006. J. Xiao, 3d shapenets: A deep representation for
[3] S. M. Ahmed, Y. Z. Tan, C. M. Chew, A. A. Mamun, volumetric shapes, in: Proceedings of the IEEE con-
F. S. Wong, Edge and corner detection for unorga- ference on computer vision and pattern recognition,
nized 3d point clouds with application to robotic 2015.
welding, in: 2018 IEEE/RSJ International Con-
ference on Intelligent Robots and Systems (IROS),
2018.
[4] N. J. Mitra, M. Pauly, M. Wand, D. Ceylan, Sym-
metry in 3d geometry: Extraction and applications,
Comput. Graph. Forum (2013).
[5] M. Bokeloh, M. Wand, V. Koltun, H.-P. Seidel,
Pattern-aware shape deformation using sliding
dockers, ACM Trans. Graph. (2011).
[6] N. J. Mitra, A. Bronstein, M. Bronstein, Intrinsic reg-
ularity detection in 3d geometry, in: K. Daniilidis,
P. Maragos, N. Paragios (Eds.), Computer Vision –
ECCV 2010, 2010.
[7] K. Xu, H. Zhang, A. Tagliasacchi, L. Liu, G. Li,
M. Meng, Y. Xiong, Partial intrinsic reflectional
symmetry of 3d shapes, ACM Trans. Graph. (2009).
[8] P. Ji, X. Liu, A fast and efficient 3d reflection symme-
try detector based on neural networks, Multimedia
Tools and Applications (2019).
8