Accelerating Evolutionary Construction Tree Extraction via Graph Partitioning

The problem of reconstructing a surface from a discrete point cloud has been the subject of much attention in computer graphics. The most popular methods include fitting implicit surfaces such as [OBA⁺03], or Poisson surface reconstruction [KH13], among others. The recent work of Berger et al. [BTS⁺17] presents a wide survey of the topic. Using these methods, the reconstructed objects lack information that can be used for inspection or re-use of the object in further modeling.

The goal of Reverse Engineering is the creation of consistent geometric models from point cloud data [VMC97, BMV01]. They usually output B-rep models made of parametric patches.
The conversion from B-rep to CSG was first investigated for two-dimensional, linear polygons, then later extended by Shapiro et al. for handling curved polygons [SV91b, Sha01]. The extension to three-dimensional objects was initially solved by Shapiro and Vossler in [SV91a, SV93] and later improved by Buchele and Crawford in [BC04]. These works rely on the fact that surfaces are composed of quadric surface patches. Another issue is the handling of inexact representations. These methods work under the assumption that the patches form a clean partition of the target solid. However, in practice, we are dealing with input point clouds that are potentially noisy, contain holes, or have additional details and thus the fitted primitives may not fit perfectly. This could impact the cellular classification on which these methods rely.

In [XF14], a greedy approach is used to build a CSG-representation with cuboids as primitives. This approach is limited to the reconstruction of buildings. Close to the proposed approach are methods that handle noisy and incomplete point clouds such as [SWK07] for fitting primitives and methods that try to convert them to a higher level representation such as [FP16], see also [BTS⁺17, Sections 7 and 8]. One of the goals of this work is to improve the running time of the Evolutionary Algorithm used in [FP16] via geometric consideration, i.e. the overlapping in space of primitives.

The extraction of a CSG-tree from a point cloud poses a complex problem which is usually solved with a processing pipeline that comprises the following steps:

1. 1.

   Point cloud generation and pre-processing: Point clouds are generated by laser scanners or tactile measurement devices. Other techniques use photogrammetric algorithms to gather depth information from (un-)calibrated camera images [HZ03]. Measured point clouds usually contain significant amounts of noise and outliers. These can be trimmed from the data-set using e.g. statistical approaches [RC11].

2. 2.

   Point cloud segmentation and primitive fitting: The point cloud must be segmented and primitive parameters have to be fitted to the corresponding points. Approaches that fulfill both tasks for simple geometric shapes are e.g. specialized variants of the Random Sample Consensus (RANSAC) technique [SWK07].

3. 3.

   CSG-tree generation: CSG-tree generation can be done with methods based on algorithmic geometry such as [SV93, BC04], or via evolutionary approaches such as [FP16] for handling inexact representations.

4. 4.

   CSG-tree optimization: The resulting CSG-tree might not be optimal in terms of size and depth. Additional optimization techniques can simplify the tree structure [SV91a].

Primitives are basic shapes located at CSG-tree leaves. A primitive $p$ is fully described by its signed distance function $f_{p}:\mathbb{R}^{3}\mapsto\mathbb{R}$. The surface of $p$ is implicitly defined by the zero-set of $f_{p}$: $\{x\in\mathbb{R}^{3}:f_{p}(x)=0\}$. Its surface normal at point $x\in\mathbb{R}^{3}$ is given by the gradient $\nabla f_{p}(x)$. If the gradient does not exist at $x$ or is too expensive to compute, finite difference approximations can be used.

The set-operations intersection, union, complement and subtraction are implemented using $\min$- and $\max$-functions [Ric73]:

• •

  Intersection: $S_{1}\cap S_{2}:=\min(f_{S_{1}},f_{S_{2}})$

• •

  Union: $S_{1}\cup S_{2}:=\max(f_{S_{1}},f_{S_{2}})$

• •

  Complement: $\overline{S}:=-f_{S}$

• •

  Subtraction: $S_{1}\setminus S_{2}:=S_{1}\cap\overline{S_{2}}$

where $S_{i}$ is the solid corresponding to the set $\{x\in\mathbb{R}^{3}:f_{S_{i}}\geq 0\}$ ($i=1,2$). In the following, the considered Boolean set-operations are intersection, union, complement and subtraction.

For expressing spatial relationships between primitives, the Primitive Overlap (PO)-graph is introduced. It represents spatial overlap between primitives using an undirected graph $G=(P,O)$, where $P=\{p_{1},\dots,p_{n_{p}}\}$ is the set of $n_{p}$ primitives as vertices and $O$ is the edge-set that contains $2$-tuples of overlapping primitives $o=(p_{i},p_{j})$, where $i,j\in\{1,\dots,n_{p}\}$ with $i\neq j$.
The PO-graph is generated based on the location, orientation and geometric shape of the primitives, see Fig. 2(b). Complex shapes can be approximated with simpler bounding volumes like Oriented Bounding Boxes or the convex hull of the corresponding point-set [PH77].
For better scalability, the computational complexity can be reduced from $\mathcal{O}({n_{p}}^{2})$ (overlap check between each primitive and each other primitive) to $\mathcal{O}(n_{p}\log(n_{p}))$ using hierarchical space partitioning schemes like e.g. Octrees [Mea82].

With known partitions, CSG-tree extraction is conducted for each partition separately in a divide-and-conquer manner. A variant of the GA described in [FP16] is used with the objective function

where $t$ is the tree candidate, $S$ is the point-set corresponding to the partition’s primitives and $\text{size}(t)$ is the number of nodes in tree $t$ weighted by a factor $\alpha$. $d_{i}(t)=\beta\cdot f_{t}(s_{i})$ is the signed distance between point $s_{i}$ and the surface defined by tree $t$ weighted by a factor $\beta$. $\theta_{i}(t)=\gamma\cdot\arccos(\nabla\hat{f_{t}}(s_{i})\cdot n_{i})$ is the angle between the point normal $n_{i}$ and the normalized gradient at position $s_{i}$ weighted by a factor $\gamma$. $\alpha,\beta$ and $\gamma$ are user-controlled parameters. The first term in Equation 1 (under the sum) estimates how close the surface induced by $t$ matches the point cloud, while the second term penalizes trees with a large number of nodes. The given objective function has to be maximized for $t$.
Initially, the population $T_{0}$ is filled with $n_{T}$ randomly generated trees with a height $\leq h_{max}$. For the maximum tree height, the approximation

is used, where $n_{pp}$ is the number of primitives in the partition. It is based on the average height of binary trees for a given number of internal nodes [FO82] and achieved good results in all experiments carried out.
Each GA iteration $i$ contains the following steps:

1. 1.

   The population of the previous iteration $T_{i-1}$ is ranked according to Equation 1.

2. 2.

   The current population is initialized with the $n_{b}$ best candidates from $T_{i-1}$.

3. 3.

   As long as $T_{i}$ has not reached maximum population size $n_{T}$, two candidates are selected from $T_{i-1}$ via Tournament Selection parameterized with $k_{ts}$ (the size of the set of randomly chosen population members from which the best member is selected) [MG95]. During crossover, the two selected candidates exchange randomly selected subtrees with a probability of $\gamma_{cr}$. Then, with a probability of $\gamma_{mu}$, each resulting tree is mutated. Either a randomly chosen subtree is replaced with a new randomly generated subtree with a probability of $\mu_{mu}$. Or, with a probability of $1-\mu_{mu}$, the whole tree is replaced with a new randomly generated tree.

4. 4.

   The termination condition is met if the score of the best CSG-tree candidate of an iteration does not improve over $n_{tc}$ iterations.

The most computationally expensive step in GA-based CSG-tree recovery is the evaluation of Equation 1 for each element of a candidate-set. Since evaluations can be conducted for each candidate independently, parallel processing schemes can be applied efficiently. In addition, the solution space partitioning allows for a per-partition parallelization strategy. Both options were implemented for multi-core processors. Their evaluation is discussed in Section 6.

The merge process has an asymptotic computational complexity of $\mathcal{O}(|L|^{2})$ since in the worst case $L$ has to be traversed for each merge.

Timings for baseline and search space partitioning variants were measured for all models with high- and low-detail sampling (except for model M$3$ for which only a single point cloud exists). Measurements vary significantly for the same benchmark setting due to the stochastic behavior of GA-based methods. In order to deal with this variance, each experiment was repeated $5$ times.
In the following, timing results for all methods in combination with high-detail sampling are discussed. See Fig. 6 and 7 for an overview of the results. For model M$0$, SMTGA is the fastest method. It outperforms the baseline by a factor of $15.3$ (single-threaded, BST) and $7.5$ (multi-threaded, BMTGA) on average. For model M$1$, search space partitioning performs worse than baseline: The fastest baseline method (BMTGA) is on average $1.4$ times faster than the best-performing search space partitioning variant (SMTGA). This can be explained by the relatively small number of primitives ($4$) and partitions ($2$) in model M$1$, which reduces the need for partitioning. For model M$2$, single-threaded partitioning is $38.3$ times faster than single-threaded baseline and multi-threaded partitioning variants are between $43.4$ and $46.6$ times faster than multi-threaded baseline. The considerable difference is due to the relatively high number of partitions ($12$) and their equally distributed size (all contain $4$ primitives). For model M$3$, SMTGA is again the fastest method. Compared to multi-threaded baseline it is $3.0$ times faster on average.
Search space partitioning with GA parallelization (SMTGA) is in general faster than their per-partition counterparts (SMTP, SMTPGA) for all models. This is due to the granularity and regularity of the parallelization: For SMTGA, the task of ranking a population can be splitted into $n_{T}$ parts, with each part having similar execution times. For per-partition variants, granularity is determined by the (potentially lower) number of partitions, and per-partition execution times may vary significantly depending on partition sizes.
Results for per-partition variants do not show timings for the different pipeline steps since in all experiments, per-partition CSG-tree extraction is by far the most dominant factor. Timings for PO-graph generation, search space partitioning and tree merge make less than $1{}^{\text{o}}\mkern-5.0mu/\mkern-3.0mu_{\text{oo}}$ of the total runtime.

Fig. 9 contains average depths and sizes of resulting trees for baseline and partitioning variants. For the latter, tree depths have increased by $25.0\%$ (model M$1$) to $285.0\%$ (model M$2$) compared to the input tree, while for baseline approaches, an increase of $0.0\%$ (model M$1$) to $125.0\%$ (model M$2$) is visible. Tree sizes show similar behavior: Partitioning variants produce $46.1\%$ (model M$2$) to $68.2\%$ (model M$0$) larger trees, while baseline approaches increase tree size by only $0.0\%$ (model M$0$) to $16.7\%$ (model M$2$). Comparing tree sizes between partitioning and baseline approaches directly reveals that the former results in $25.2\%$ (model M$2$) to $88.6\%$ (model M$3$) larger trees.
This adverse behavior shown by partitioning variants is due to the final merge step: In each iteration, the two trees that are close to each other in the tree list and have a common subtree of at least size $1$ are merged instead of the two trees with the largest common subtree of all tree pairs in the merge list. Since the focus of this work is on performance, this is acceptable. In addition, the tree optimization strategy described in Section 5.4 (step $1$) was also applied to baseline results for better comparability, which has positive impact on resulting tree depths and sizes.