PolyGNN: Polyhedron-based Graph Neural Network for 3D Building
  Reconstruction from Point Clouds
We present PolyGNN, a polyhedron-based graph neural network for 3D building
reconstruction from point clouds. PolyGNN learns to assemble primitives
obtained by polyhedral decomposition via graph node classification, achieving a
watertight, compact, and weakly semantic reconstruction. To effectively
represent arbitrary-shaped polyhedra in the neural network, we propose three
different sampling strategies to select representative points as
polyhedron-wise queries, enabling efficient occupancy inference. Furthermore,
we incorporate the inter-polyhedron adjacency to enhance the classification of
the graph nodes. We also observe that existing city-building models are
abstractions of the underlying instances. To address this abstraction gap and
provide a fair evaluation of the proposed method, we develop our method on a
large-scale synthetic dataset covering 500k+ buildings with well-defined ground
truths of polyhedral class labels. We further conduct a transferability
analysis across cities and on real-world point clouds. Both qualitative and
quantitative results demonstrate the effectiveness of our method, particularly
its efficiency for large-scale reconstructions. The source code and data of our
work are available at https://github.com/chenzhaiyu/polygnn.
Zhaiyu Chen, Yilei Shi, Liangliang Nan, Zhitong Xiong, Xiao Xiang Zhu
# PolyGNN: Polyhedron-based Graph Neural Network for 3D Building Reconstruction from Point Clouds

###### Abstract

We present PolyGNN, a polyhedron-based graph neural network for 3D building reconstruction from point clouds. PolyGNN learns to assemble primitives obtained by polyhedral decomposition via graph node classification, achieving a watertight, compact, and weakly semantic reconstruction. To effectively represent arbitrary-shaped polyhedra in the neural network, we propose three different sampling strategies to select representative points as polyhedron-wise queries, enabling efficient occupancy inference. Furthermore, we incorporate the inter-polyhedron adjacency to enhance the classification of the graph nodes. We also observe that existing style-building models are abstractions of the underlying instances. To address this abstraction gap and provide a fair evaluation of the proposed method, we develop our method on a large-scale synthetic dataset covering 500K+ buildings with well-defined ground truths of polyhedral class labels. We further conduct a transferability analysis across cities and on real-world point clouds. Both qualitative and quantitative results demonstrate the effectiveness of our method, particularly its efficiency for large-scale reconstructions. The source code and data of our work are available at [https://github.com/chenhaiyu/polygn](https://github.com/chenhaiyu/polygn).

## 1 Introduction

Three-dimensional (3D) building models constitute an important infrastructure in shaping digital twin cities, facilitating a broad range of applications including urban planning, energy demand estimation, and environmental analysis (Biljecki et al., 2015; Opoku et al., 2021). Therefore, efficient reconstruction of high-quality 3D building models is crucial for understanding an urban environment and has been a long-standing challenge.

Most reconstruction methods are dedicated to detailed surfaces represented by dense triangles (Kazhdan and Hoppe, 2013; Erler et al., 2020; Stucker et al., 2022), irrespective of the ubiquitous piecewise planarity in the built environment. Instead, a compact polygonal representation with sparse parameters can adequately capture the geometry of urban buildings. To reconstruct compact polygonal building models, three categories of methods are commonly employed in practice. Model-based reconstruction methods (Zhou and Neumann, 2010; Li et al., 2016) represent buildings by utilizing a library of pre-defined templates. However, the limited variety of available templates constrains the expressiveness of these methods. Geometric simplification methods (Bouzas et al., 2020; Li and Nan, 2021) aim to obtain compact surfaces by simplifying dense triangle ones. These techniques, however, necessitate an input model that is precise in both its geometry and topology to ensure a faithful approximation. Primitive assembly methods (Nan and Wonka, 2017; Huang et al., 2022) produce polygonal surface models by pursuing an optimal assembly of a collection of geometric primitives. However, these methods often entail the use of handcrafted features and thus possess limited representational capacity.

Despite the successes in various other applications, learning-based solutions for reconstructing compact building models have been largely unexplored, where Points2Poly (Chen et al., 2022) is a pioneering effort with the primitive assembly strategy, which learns building occupancy based on an implicit representation followed by a Markov random field to promote compactness. By the design, the occupancy learning is agnostic of the primitive-induced hypothesis, resulting in the lack of efficiency and therefore hindering its application at scale.

In this paper, we introduce PolyGNN, a polyhedron-based graph neural network, for reconstructing building models from point clouds. PolyGNN utilizes the decomposition of a building's ambient space into a set of polyhedra as strong priors. It learns to assemble the polyhedra to achieve a watertight, compact, and weakly semantic reconstruction formulated as end-to-end graph node classification. The neural network can be efficiently optimized, enabling building model reconstruction at scale.

Our key idea lies in coupling occupancy estimation with the polyhedral decomposition by primitive assembly. Instead of learning a continuous function with traditional deep implicit fields, we opt for learning a piecewise planar occupancy function from the polyhedra. There, one challenge involves consistently representing the heterogeneous geometry of arbitrary-shaped polyhedra. To this end, we propose sampling a set of representative points inside the polyhedron as queries. Conditioned on the latent building shape, these polyhedron-wise queries then collectively describe the
building occupancy. We propose three sampling strategies, namely volume sampling, boundary sampling, and skeleton sampling, and assess their respective performances.

Moreover, we observe that existing 3D city models are abstracted from real-world buildings, and they typically lack geometric details. Thus, using existing mesh models as ground truths is inherently inadequate due to systematic "errors". To facilitate a supervised learning setup for PolyGNN, we resort to creating a large-scale synthetic dataset comprised of simulated airborne LiDAR point clouds and building models. The synthetic dataset enables reliable one-to-one mapping between the two sources, effectively addressing the potential abstraction gap. Subsequently, we evaluate the transferability of our method across cities and on real-world point clouds.

The main contributions of this paper are summarized as follows:

* We introduce PolyGNN, a polyhedron-based graph neural network for reconstructing compact polygonal building models from point clouds. PolyGNN achieves end-to-end optimization through graph node classification.
* We propose three sampling strategies for representing arbitrary-shaped polyhedra in the neural network and assess their respective performances.
* We introduce a large-scale synthetic LiDAR dataset for developing learning-based urban building reconstruction methods, which consists of over 500k buildings with polyhedral class labels.

## 2 Related work

In this section, we discuss two categories of methods used for polygonal building model reconstruction: model-based reconstruction and primitive assembly. Following this, we introduce the line of research in neural implicit representation, from which we draw inspiration for our work.

### Model-based reconstruction

Model-based reconstruction methods represent a building by utilizing a library of common building components, in the form of pre-defined templates.

Although satellite data offers prospects for global building models, they often lack the necessary level of detail (LoD) and quality, and thus are primarily limited to 3D models at LoD1 (Zhu et al., 2022; Sun et al., 2022). The Manhattan-world assumption restricts the orientation of building surfaces in the three dominant directions and represents buildings with axis-aligned polycubes (Ikehata et al., 2015; Li et al., 2016, 2016). Another common practice is restricting the output surface to specific disk topologies. For example, the 2.5D view-dependent representation (Zhou and Neumann, 2010) can generate building roofs with vertical walls connecting them from LiDAR measurements. Xiong et al. (2014, 2015) exploit roof topology graphs for reconstructing LoD2 buildings from predefined building primitives, which is extended by Mwangangi (2019) for UAV images. Similarly, Li et al. (2016) present a workflow to reconstruct building mass models from UAV measurements. Kelly et al. (2017) formulate a global optimization to produce structured urban reconstruction from street-level imagery, GIS footprint, and coarse 3D mesh. The model-based approaches simplify the reconstruction with uniformity assumptions and are thus efficient to implement. However, they only apply to specific domains as a limited variety of the models constrains the expressiveness of these methods. Our reconstruction method, instead, does not rely on a model library, thus remaining generic.

### Primitive assembly

Primitive assembly methods can produce compact polygonal surface models by pursuing an optimal assembly of a set of geometric primitives.

Connectivity-based approaches (Chen and Chen, 2008; Van Kreveld et al., 2011; Schindler et al., 2011) address the assembly by extracting proper geometric primitives from an adjacency graph built on planar shapes. While efficient in analyzing the graph, these methods are sensitive to the quality of the graph. Linkage errors contaminating the connectivity can compromise the reconstruction. A hybrid strategy proposed by Lafarge and Alliez (2013); Holzmann et al. (2018) represents high-confidence areas by polygons and more complex regions by dense triangles. Arikan et al. (2013) presents an interactive optimization-based snapping solution, which requires labor-intensive human involvement in handling complex structures.

Slicing-based approaches are more robust to imperfect data with the hypothesis-and-selection strategy. In practice, planar primitives can be detected from RANSAC (Schnabel et al., 2007), region growing (Rabbani et al., 2006), and via neural networks (Li et al., 2019; Le et al., 2021). With the primitives, Chauve et al. (2010); Mura et al. (2016); Nan and Wonka (2017); Bauchet and Lafarge (2020) partition the 3D space into polyhedral cells by extending the primitives to supporting planes, transforming the reconstruction into a labeling problem where the polyhedral cells are labeled as either inside or outside the shape or equivalently by labeling other primitives. Li and Wu (2021) extend PolyFit (Nan and Wonka, 2017) to leverage the inter-relation of the primitives for procedural modeling. Huang et al. (2022) further extend PolyFit by introducing a new energy term to encourage roof preferences and two additional hard constraints to ensure correct topology and enhance detail recovery. Fang and Lafarge (2020) propose a hybrid approach for reconstructing 3D objects by successively connecting and slicing planes identified from 3D data. A combined approach of rule-based and hypothesis-based strategies is proposed by Xie et al. (2021). Our method inherits primitive assembly while achieving selection by a graph neural network with the polyhedra from convex decomposition.

### Implicit neural representation

Recent advances in deep implicit fields have revealed their potential for 3D surface reconstruction (Park et al.,
2019; Peng et al., 2020; Erler et al., 2020; Yao et al., 2021; Williams et al., 2022), and also specifically for buildings (Stucker et al., 2022). The crux of these methods is to learn a continuous function to map the input, such as a point cloud, to a scalar field. The surface of an object can then be extracted using iso-surfacing techniques like Marching Cubes (Lorensen and Cline, 1987). To learn a more regularized field, Rella et al. (2022) and Yang et al. (2023) both propose to learn the displacements from queries towards the surface and model shapes as vector fields. However, these methods still require iso-surfacing to extract the final surfaces. Though iso-surfacing is effective in extracting smooth surfaces, it struggles to preserve sharp features and introduces discretization errors. Consequently, deep implicit fields alone are not inherently suitable for reconstructing compact polygonal models. By incorporating constructed solid geometry, Chen et al. (2020) and Deng et al. (2020) both introduce implicit fields to reconstructing convexes obtained via binary space partitioning. The inputs to these neural networks are images and voxels, while we focus on point clouds.

Points2Poly (Chen et al., 2022) is a pioneering learning-based effort for polygonal building reconstruction. The key enabler is a learned implicit representation that indicates the occupancy of a building, followed by a Markov random field for a favorable geometric complexity. By its design, Points2Poly is composed of two separate parts, hence cannot be optimized end-to-end. The occupancy learning is agnostic of the hypothesis. This limits its exploitation of deep features, and in turn, limits its efficiency. The prohibitive complexity hinders its application at scale. In contrast, our method directly learns to classify the polyhedra with an end-to-end neural architecture, underpinning great efficiency.

## 3 Methodology

### Overview

We formulate building reconstruction as a graph node classification problem. As shown in Figure 1, we first decompose the ambient space of a building into a cell complex of candidate polyhedra following binary space partitioning. PolyGNN represents the cell complex as a graph structure and classifies the polyhedral nodes into two classes: _interior_ and _exterior_. Finally, the building surface model can be extracted as the boundary between the two classes of polyhedra.

The above procedure can be formulated as follows. Given an unordered point set \(\mathcal{X}=\{x_{1},x_{2},...,x_{q}\}\) with \(x_{i}\in\mathbb{R}^{3}\) as input, we first decompose the ambient space into an undirected graph embedding \(\mathcal{G}=(\mathcal{V},\mathcal{E}\mid\mathcal{X})\), where \(\mathcal{V}=\{v_{1},v_{2},...,v_{m}\}\) and \(\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\) represent non-overlapping convex polyhedra and their edges, respectively. \(\mathcal{G}\) serves as a volumetric embedding, from which we seek an appropriate subset of \(\mathcal{V}\) to align with the occupancy of the underlying building instance. The surface reconstruction is therefore transformed into an assignment problem which we address with a graph neural network \(\vec{f}\):

\[\vec{f}\approx f(\mathcal{V}\mid\mathcal{X},\mathcal{E})=Y, \tag{1}\]

where \(Y=\{y_{1},y_{2},...,y_{m}\}\subseteq\{0,1\}\). Figure 2 illustrates the architecture of PolyGNN for solving the graph node classification problem, which consists of two stages:

* **Polyhedral graph encoding**. A graph structure is constructed from polyhedral decomposition, with polyhedra being graph nodes. Node features are formed by conditioning polyhedron-wise queries on a multi-scale shape latent.
* **Graph node classification**. With the encoded node features and inter-polyhedron adjacency, graph nodes are classified for building occupancy estimation.

PolyGNN is end-to-end optimizable for polyhedra classification. In the following, we elaborate on the two main components of the network.

### Polyhedral graph encoding

#### 3.2.1 Polyhedral graph construction

We adopt the adaptive binary space partitioning approach introduced by Chen et al. (2022). We first identify a set of planar primitives from the input point cloud that comprises the building and partition the ambient 3D space to generate a linear cell complex of non-overlapping polyhedra that complies with the primitives. As illustrated in Figure 3, vertical primitives and primitives with larger areas are given higher priority. The tessellation is spatially adaptive therefore being efficient and respective to the building's geometry. The partitioning also involves the construction of a binary tree, which records the hierarchical information of polyhedra and their inter-polyhedron adjacency.

Figure 1: Reconstruction by polyhedra classification. Candidate polyhedra (a) are generated by polyhedral decomposition and are classified by PolyGNN into _interior_ ones and _exterior_ ones (b). The surface (c) is extracted in between pairs of polyhedra of different classes. (d) (e) (f) are illustrations of 2D cross sections of (a) (b) (c), respectively.
#### 3.2.2 Point cloud encoding

By adaptive binary space partitioning, the polyhedral embedding \(\mathcal{G}\) is produced in the Euclidean space, from which we seek an appropriate subset of \(\mathcal{V}\) to align with the occupancy of the underlying building instance. In addition, we obtain the shape latent \(\mathbf{z}\) embedded in the feature space, via a graph neural network.

We transform \(\mathcal{X}\) into a neural feature representation, a process which, in principle, can be achieved through any point cloud encoder. We experimented and chose a lightweight yet efficient one. Specifically, multi-level features are encoded with layers of dynamic edge convolutions (Wang et al., 2019):

\[g^{l}_{x_{i}}=\sum_{x_{j}\in\mathcal{N}(x_{i})}\Phi\left(\left[h^{l}_{x_{i}},h^ {l}_{x_{j}},e_{x_{i},x_{j}}\right]\right), \tag{2}\]

where \(g^{l}_{x_{i}}\) is the feature representation of point \(x_{i}\) at layer \(l\). \(\mathcal{N}\left(x_{i}\right)\) is the set of neighboring points of \(x_{i}\). \(h^{l}_{x_{i}}\) and \(h^{l}_{x_{j}}\) are the feature representation of point \(x_{i}\) at layer \(l\) and that of point \(x_{j}\) at layer \(l\), respectively. \(e_{x_{i},x_{j}}\) is the edge feature between \(x_{i}\) and \(x_{j}\), and \(\Phi\) is a multi-layer perceptron (MLP) that maps the concatenated input to a new feature space. These multi-level features are further concatenated and aggregated by an MLP, followed by a max pooling operator to form a global latent feature denoted as \(\mathbf{z}\):

\[\mathbf{z}=\Phi\max_{i=1}^{n}\left(\left[g^{1},g^{2},\ldots,g^{L}\right] \right), \tag{3}\]

where \(L\) represents the maximum level, i.e., the number of edge convolution layers.

#### 3.2.3 Query sampling

To encode an arbitrary-shaped polyhedron, one challenge lies in consistently describing the heterogeneous polyhedral geometry. To address this, we propose sampling representative points from inside the polyhedron and coerc

Figure 3: Illustration of adaptive binary space partitioning. During partitioning, a binary tree is dynamically constructed to analyze inter-polyhedron adjacency. \(t\) denotes iteration.

Figure 2: Architecture of PolyGNN. Given an input point cloud, a graph structure is constructed from polyhedral decomposition, with polyhedra being graph nodes. Node features are formed by conditioning polyhedron-wise queries on a multi-scale shape latent. With the encoded node features and inter-polyhedron adjacency, graph nodes are classified for building occupancy estimation.
the geometry into fixed-length queries of size \(k\). It is clear that the more representative the sampled points are, the more information they convey about the polyhedron. We evaluate three sampling strategies, namely volume sampling, boundary sampling, and skeleton sampling, as illustrated in Figure 4. The volume variant randomly takes points inside the volume of a polyhedron, carrying relatively the least amount of geometric information about the polyhedron. The boundary variant samples points on the boundary of a polyhedron with area-induced probability as outlined in Algorithm 3.1. This variant can better depict polyhedral occupancy with boundary information. Furthermore, as described in Algorithm 3.2, the skeleton variant picks samples from both vertices and principal axes, arguably offering the most efficient description of a polyhedron among the three variants. Vertices, because of their prominence in describing sharp geometry, are prioritized over points along the axes when a low \(k\) value is given.

```
Input: Vertices \(\mathcal{V}\), facets \(\mathcal{F}\), and #samples \(k\) Output: Representative points \(\mathcal{S}\)
1\(\mathcal{S}\), \(\mathcal{T}\), \(a\leftarrow\) init \(\emptyset\);
2for\(i\gets 1\) to \(|\mathcal{F}|\)do
3\(\mathcal{T}_{i}\leftarrow\) triangulate(\(\mathcal{V}_{\mathcal{T}_{i}}\)) ;
4\(a_{i}\leftarrow\) area(\(\mathcal{T}_{i}\)) ;
5\(\mathcal{T}^{\prime}\leftarrow\) sample\({}^{a}_{k}\) (\(\mathcal{T}\)) ;
6for\(j\gets 1\) to \(k\)do
7\(S_{j}\leftarrow\) sample(\(\mathcal{T}^{\prime}_{j}\)) ;
8
9return\(\mathcal{S}\)
```

**Algorithm 3.1**Boundary sampling (\(\mathcal{V}\), \(\mathcal{F}\), \(k\))

The representative points obtained by all three sampling strategies reduce the complexity of an arbitrary-shaped polyhedron to a fixed-size feature vector \(\mathcal{S}=\{s_{1},s_{2},...,s_{k}\}\) that can be consumed by the neural network while preserving geometric information to different extents. These representative points then serve as queries against \(\mathbf{z}\), resulting in the formation of polyhedron-wise features. Intuitively, these queries are used to jointly describe the occupancy of the underlying polyhedron. A performance comparison of the three sampling strategies is provided in Section 5.

#### 3.2.4 Forming polyhedron-wise features

Inspired by the recent advance in 3D shape representation learning (Park et al., 2019; Yao et al., 2021), we

Figure 4: Sampling representative points from a polyhedron. (a) - (c) visualize different strategies to sample the polyhedron highlighted in (d). **Volume**: Points are sampled randomly from inside the volume. **Boundary**: Points are sampled from the boundary as described in Algorithm 3.1. **Skeleton**: Points are sampled along the polyhedral skeleton as described in Algorithm 3.2. Representative points are colored by their parent polyhedra.

Figure 5: Fusion of shape latent and polyhedral queries to form shape-conditioned queries and subsequently polyhedron-wise features.
form a shape-conditioned implicit representation \(\mathbf{z}_{v}\) of the polyhedron by concatenating the coordinates of queries \(S_{v}\) with the latent feature \(\mathbf{z}\):

\[\mathbf{z}_{v}=\Phi\left(S_{v}\mid\mathbf{z}\right)=\Phi\left(\left[s_{1},s_{2},...,s_{k},\mathbf{z}\right]\right), \tag{4}\]

where \(\Phi\) represents an MLP. Figure 5 illustrates the formation of polyhedron-wise features. This formulation allows modeling multiple building instances with a single neural network. Intuitively, \(\mathbf{z}_{v}\) is a discrete occupancy function that, given a polyhedron, outputs the likelihood of the polyhedron being occupied by the building. Such a representation can be interpreted as a spatial classifier for which the decision boundary is the surface of the building. Note that instead of approximating a continuous implicit function by exhaustive enumeration, our discretized formulation takes geometric priors of individual polyhedra into account, which drastically reduces computational complexity and solution ambiguity, while being end-to-end optimizable. Figure 6 demonstrates such a distinction using a 2D example.

### Graph node classification

The polyhedron-wise features produced by Equation 4 do not yet consider inter-polyhedron adjacency. This adjacency provides additional information that can enhance the classification of individual polyhedra. To incorporate this topological information and thereby enhance the classification, we utilize another stack of graph convolution layers for graph node classification as outlined in Equation 1. Specifically, we employ topology-adaptive graph convolution (Du et al., 2017) for its adaptivity to the topology of the graph and computational efficiency. It utilizes a set of fixed-size learnable filters for graph convolution, defined as follows:

\[\mathbf{G}^{l+1}=\sum_{k=0}^{K}\left(\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{- 1/2}\right)^{k}\mathbf{G}^{l}, \tag{5}\]

where \(\mathbf{G}^{l+1}\) and \(\mathbf{G}^{l}\) denote the node features before and after the convolution at the \(l\)-th layer, respectively. \(\mathbf{A}\) is the adjacency matrix implied by \(\mathcal{E}\) in Equation 1, and \(\mathbf{D}=\text{diag}[\mathbf{d}]\) with the \(i\)-th component being \(d\) (\(i\)) = \(\sum_{j}\mathbf{A}_{i,j}\). \(K\) is the number of filters, whose topologies are adaptive to the topology of the graph as they scan the graph to perform convolution.

Multiple graph convolution layers defined in Equation 5 are stacked to increase the receptive field of the neural network. The feature of the \(i\)-th node \(G_{i}\) is then fed into a binary classification head with the softmax activation function to produce the likelihood of the polyhedron \(v_{i}\) being _interior_:

\[\hat{y}_{i}=\text{softmax}\left(\Phi\left(G_{i}\right)\right), \tag{6}\]

where \(\Phi\) represents an MLP.

We train the network by minimizing the discrepancy between the prediction and the ground truth. Since the non-building polyhedra dominate the candidate space, we employ focal loss to alleviate the class imbalance:

\[\begin{split}\mathcal{L}=-\frac{1}{N}\,\sum_{i=1}^{N}\big{[}y_{i }\cdot(1-\hat{y}_{i})^{\gamma}\log(\hat{y}_{i})\\ +(1-y_{i})\cdot\hat{y}_{i}^{\gamma}\log(1-\hat{y}_{i})\big{]}, \end{split} \tag{7}\]

where \(y_{i}\) represents the \(i\)-th element of the ground truth label vector, \(\hat{y}_{i}\) is derived from Equation 6. \(N\) is the total number of polyhedra, and \(\gamma\) is the focusing parameter. The network can be optimized end-to-end without any auxiliary supervision.

In the testing phase, given a building instance, we predict the occupancy of the candidate polyhedra. Then the surface lies in between pairs of polyhedra \(\{v_{i},v_{j}\}\) with different class predictions, i.e., \(y_{i}\neq y_{j}\), as shown in Figure 1.

## 4 Experimental settings

### Datasets

Unlike other applications that adhere to rigorous definitions of ground truths, reconstructing large-scale polygonal buildings presents a challenge due to the abstraction of existing building models, resulting in inevitable deviations from actual measurements, as shown in Figure 7. This abstraction would impede a supervised learning algorithm due to its inherent biases. To overcome this abstraction gap, we create a synthetic dataset comprised of simulated airborne LiDAR point clouds and their corresponding building mesh models. This dataset enables a reliable mapping between the two sources, thus contributing to the orthogonality of the proposed method with respect to classification.

Formally, let \(\mathcal{X}_{r}\) and \(Y_{m}\) be a real-world point cloud and its corresponding building model, respectively. Due to

Figure 6: Instead of learning a continuous function underpinned by points with traditional deep implicit fields (left), PolyGNN learns a piecewise planar occupancy function from polyhedral decomposition (right).
the abstraction gap, the mapping \(f\): \(\mathcal{X}_{r}\to Y_{m}\) cannot be accurately learned by a neural network. Instead, we opt to learn an auxiliary mapping \(f^{\prime}\): \(\mathcal{X}_{m}\to Y_{m}\) where \(\mathcal{X}_{m}\) is derived from \(Y_{m}\) by synthesizing \(\mathcal{X}_{r}\). Once \(f^{\prime}\) is learned, it can be applied to \(\mathcal{X}_{r}\) to obtain the corresponding output \(Y_{x}^{\prime}=f^{\prime}(\mathcal{X}_{r})\). Using synthetic data in our task offers two-fold advantages. First, it enables the learning of the desired mapping by circumventing the abstraction, allowing the classifier to be trained and evaluated independently of potential data discrepancies. Moreover, it facilitates the exploration of a large volume of "free" training data, which benefits the learning algorithm at large.

We utilize the _Helios++_ simulation toolkit (Winiwarter et al., 2022) to simulate airborne LiDAR scanning. LoD2 building models from Bavaria, Germany are used as references for their high quality and coverage (State of Bavaria, 2022). Artifacts such as noise and inter-building occlusions are intentionally included in the scanning process, to assimilate the distribution of \(\mathcal{X}_{m}\) and \(\mathcal{X}_{r}\), thereby enhancing the robustness of the neural network against real-world measurements. The virtual sensor closely emulates the characteristics of _Leica HYPERION2+_, utilizing an oscillating optics system with a pulse frequency of 1.5 MHz and a scan frequency of 150. We simulate an airborne survey performed by a _Cirrus SR22_ aircraft flying at an altitude of 400 m with a strip interval of 160 m. Our training dataset includes 281k+ buildings in Munich, Germany, with an additional 10k buildings reserved for evaluation. To assess the cross-city transferability of PolyGNN, we also synthesize data from 220k+ buildings in Nuremberg, Germany. In addition to the synthetic data, we apply the trained model directly to a real-world airborne LiDAR point cloud dataset containing 1,452 buildings. For an individual building, we generate a set of polyhedra with inter-polyhedron adjacency as pre-processing (see Section 3.2.1), and use ray tracing to determine the ground truth occupancy label for every polyhedron.

### Evaluation metrics

We utilize multiple criteria to evaluate the performance of the reconstruction. The classification accuracy directly impacts the fidelity of the reconstruction and is therefore evaluated. Furthermore, since the ground truths are reliably defined in our setting, we quantify the surface discrepancy between the reconstructed surface and the ground truth by calculating the Hausdorff distance \(H(A,B)\):

\[H(A,B)=\max\left\{\sup_{a\in A}\inf_{b\in B}d(a,b),\sup_{b\in B}\inf_{a\in A}d(a,b)\right\}, \tag{8}\]

where \(d(a,b)\) represents the distance between points \(a\) and \(b\). We randomly sample 10k points from both the reconstructed surface and the ground truth and calculate both the absolute and relative distances. For fair comparisons in the context of large-scale reconstruction, in the event of an unsolvable reconstruction (e.g., due to the absence _interior_ polyhedra, or a timeout), we assign the length of the largest side of the bounding box as the absolute distance, and 100% as the relative distance. Additionally, we measure the geometric complexity of the reconstructed building models concerning the number of faces they comprise and measure the computational efficiency with respect to the running time with a 5-min timeout for an individual building.

### Implementation details

For point cloud encoding, we set the number of layers of dynamic edge convolutions \(L\) to 3. The same setting also applies to the graph convolutions for node classification. We implemented adaptive space partitioning with robust Boolean spatial operations from _SageMath_(The Sage Developers, 2021). The size of the global latent feature \(t\) is set to 256. For query sampling, we set the number of samples per polyhedron \(k\) to 16 for all three sampling strategies, to balance the representativeness and computational complexity. Leaky ReLU is used as the activation function. Although our implementation supports variable-length input point clouds with mini-batching, unless otherwise specified, the input point clouds are downsampled to 4,096 points for efficiency. Point clouds are normalized before being fed into the network and are rescaled for computing the Hausdorff distance. All experiments are optimized by the Adam with a base learning rate \(10^{-3}\) and weight decay \(10^{-6}\), using 4 \(\times\) NVIDIA RTX A6000 GPUs with batch size 64. The network variants are trained for 50 epochs for the ablation experiments and continue until 150 epochs for the best model.

## 5 Results and analysis

### Reconstruction performance

PolyGNN achieves an average accuracy of 96.4% for polyhedra classification and an average error of 0.81 m Hausdorff distance on the held-out Munich evaluation set. Notably, we observe a strong correlation between these two metrics. On building instances of similar levels of geometric complexity, accurate classification often leads to lower

Figure 7: Examples of abstraction gaps between real-world point clouds \(\mathcal{X}_{r}\) and existing building models \(Y_{m}\). Instead of learning \(f\): \(\mathcal{X}_{r}\to Y_{m}\), we learn an auxiliary mapping \(f^{\prime}\): \(\mathcal{X}_{m}\to Y_{m}\), where \(\mathcal{X}_{m}\) is derived from \(Y_{m}\) by synthesizing \(\mathcal{X}_{r}\). Point clouds are rendered by their height fields.
geometric errors. The reconstructed building models, as shown in Figure 8, demonstrate conformity to the distribution of the point clouds while maintaining compactness for potential downstream applications. Buildings with simpler geometry are of more regularity in the reconstruction. Furthermore, following space partitioning, the reconstruction demonstrates weak semantic associations, as depicted by the colored polyhedra in Figure 8.

To evaluate the transferability of PolyGNN, we applied the model trained on Munich data to reconstruct the buildings in Nuremberg. Figure 9 showcases the reconstruction of the downtown area of Nuremberg. Quantitatively, the classification accuracy achieves 96.3%, and the Hausdorff distance measures 0.78 m. The comparable accuracy demonstrates a commendable cross-city transferability of our approach when confronted with buildings that may vary in architectural styles. The prediction takes about 4 min for 4,185 buildings in the downtown area, highlighting the efficiency of our approach for large-scale reconstruction.

Figure 10 depicts the reconstruction results obtained by directly applying the model trained exclusively on synthetic data to a real-world point cloud in Munich. As expected, there is a domain gap between synthetic and real-world data, resulting in suboptimal reconstructions for certain buildings, especially those with architectural styles that are less represented in the training data. Nevertheless, it is noteworthy that the majority of the reconstructed buildings align well with the distribution of the input point clouds. Figure 11 further demonstrates cases where we apply the trained model with extracted planar primitives by RANSAC. By learning the underlying mapping, the reconstruction can approximate the point cloud distribution better than the ground truth, which validates the effectiveness of learning the auxiliary mapping.

### Ablation study

As shown in Table 1, among the three sampling strategies presented in Figure 4, skeleton sampling demonstrates superiority in terms of both classification accuracy and geometric accuracy, followed by boundary sampling. This finding aligns with the fact that both skeleton sampling and boundary sampling leverage more explicit geometric information compared to the volume counterpart, and the skeleton of a polyhedron captures the most critical information conveyed by its vertices and principal axes.

\begin{table}
\begin{tabular}{c c c} \hline Query sampling & Accuracy (\%) \(\uparrow\) & Error (m) \(\downarrow\) \\ \hline Random & 94.5 & 1.20 \\ Boundary & 94.7 & 1.12 \\ Skeleton & **95.5** & **1.08** \\ \hline \end{tabular}
\end{table}
Table 1: Impact of query sampling strategy on model performance.

Figure 8: Reconstruction examples on Munich data. From top to bottom: input point cloud, polyhedra classified as building components (colored randomly), reconstructed model, and the ground truth model. Point clouds are rendered by their height fields.
The individual contributions of the classification head and the adjacency information to the reconstruction performance are analyzed through another ablation experiment, as presented in Table 2. Removing the classification head and replacing it with a regression head causes the network to collapse completely, leading to the prediction of every polyhedron as an _exterior_ one. In this case, the classification accuracy represents the average proportion of _interior_ polyhedra. The high dominance of in-building polyhedra (87.3%) justifies the use of focal loss in our network design. Furthermore, the results provide clear evidence that incorporating inter-polyhedron adjacency information significantly enhances the reconstruction performance compared to relying solely on monotonic polyhedral information (95.5% vs. 93.7%). This improvement suggests that PolyGNN effectively exploits neighborhood information for occupancy estimation. Additionally, Figure 12 visually demonstrates the effectiveness of such information where the network utilizes adjacency information to achieve a more regularized reconstruction. This regularization is analogous to the MRF employed in Chen et al. (2022), while with PolyGNN this regularization is integrated into the feature space, avoiding any additional computational overhead.

PolyGNN is designed to be agnostic to the number of points, allowing for point clouds with different sizes as inputs with advanced mini-batching. In Table 3, we present a comparison of three different point cloud sampling options: random sampling, coarse grid sampling with a resolution of 0.05 within a unit cube, and fine grid sampling with a resolution of 0.01 within the same unit cube. The results demonstrate that random sampling outperforms grid sampling with both resolutions in terms of accuracy. It is worth noting that our random sampling strategy is dynamic, where different random points are selected in different epochs during training. This dynamic random sampling can also be considered a form of data augmentation. Although computationally more efficient, coarse grid sampling does not entail sufficient details for the input point cloud. Interestingly, fine grid sampling leads to significantly longer training times, yet it yields lower accuracy compared to random sampling. This inferiority can be attributed to the inherent difficulty of encoding the global shape descriptor \(\mathbf{z}\) from inputs of different sizes.

\begin{table}
\begin{tabular}{c c c c} \hline Classification & Adjacency & Accuracy (\%) \(\uparrow\) & Error (m) \(\downarrow\) \\ \hline ✗ & ✗ & 87.3 & - \\ ✓ & ✗ & 93.7 & 1.80 \\ ✓ & ✓ & **95.5** & **1.08** \\ \hline \end{tabular}
\end{table}
Table 2: Impact of classification head and adjacency information on the model performance. “-” indicates complete failure where no model is reconstructed.

Figure 9: Reconstruction of Nuremberg downtown buildings with PolyGNN trained on the Munich data.
### Comparison with state-of-the-art methods

Table 4 presents a comparison between our method and state-of-the-art methods in urban reconstruction, while Figure 13 showcases examples for visual comparison. The 2.5D DC method (Zhou and Neumann, 2010) was unable to represent building models with a concise set of parameters. In contrast, the other three methods exhibit compact reconstructions. Compared to the traditional optimization-based approach City3D (Huang et al., 2022), our method demonstrates the capability to handle more complex buildings commonly found in large-scale urban scenes. City3D adopts exhaustive partitioning, leading to a larger candidate space for searching. It only managed to reconstruct 9,887 out of 10,000 buildings within a 5-min timeout using its Gurobi solver (Gurobi Optimization, LLC, 2023), resulting in inferior reconstruction accuracy as measured by the balanced Hausdorff distance. In contrast, our approach utilizes adaptive space partitioning, resulting in a more compact candidate space that enhances both efficiency and overall accuracy. Furthermore, in comparison to the learning-based method Points2Poly (Chen et al., 2022), our method leverages an end-to-end neural architecture that underpins efficiency, while achieving comparable geometric accuracy.

Figure 11: Reconstruction from real-world point clouds with extracted planar primitives by RANSAC. From left to right: input point cloud colored by height field, the same input colored by primitives, cell complex, reconstructed model, ground truth. Note how the reconstruction approximates the point cloud distribution more than the ground truth does. Point clouds are rendered by their height fields.

Figure 12: Impact of adjacency in PolyGNN reconstruction. From left to right: input, reconstructed model w/o adjacency, reconstructed model w/ adjacency, ground truth. The errors are measured by Hausdorff distance. The point cloud is rendered by its height field.

\begin{table}
\begin{tabular}{c c c} \hline Point sampling & Accuracy (\%) \(\uparrow\) & Time train (h) 1 \\ \hline Grid (res. 0.05) & 94.6 & **0.7** \\ Grid (res. 0.01) & 94.8 & 24.6 \\ \hline Random & **95.5** & 2.1 \\ \hline \end{tabular}
\end{table}
Table 3: Impact of point cloud sampling strategy on model performance. “res” represents grid resolution relative to a unit cube.

Figure 10: Reconstruction from a real-world point cloud in Munich with PolyGNN trained exclusively on the synthetic data.
Figure 14 presents the running time comparison among the different methods, highlighting the superior efficiency of our approach. City3D, which relies on an integer programming solver, experiences computational bottlenecks when the number of planar primitives increases. As a result, for certain complex buildings, the reconstruction cannot be solved within a feasible time frame of 24 hours. Points2Poly requires approximately 4 days for 1 epoch of training, whereas our method only takes 2 hours (50\(\times\) faster). The longer inference time of Points2Poly, on the other hand, comes mostly from two factors. Firstly, more efforts are required for its occupancy estimation. Table 5 presents the comparison with the learning-based method Points2Poly, for reconstructing the building in Figure 2 with 60 planar segments. Points2Poly enumerates queries with signed distance values to learn a smooth boundary,

\begin{table}
\begin{tabular}{c c c c c} \hline \hline Method & Learning & Accuracy (\%) \(\uparrow\) & Error (m) \(\downarrow\) & Error (\%) \(\downarrow\) \\ \hline
2.5D DC & ✗ & - & - & - \\ City3D & ✗ & - & 1.10 & 6.0 \\ Points2Poly & ✓ & 96.4 & 0.83 & 4.7 \\ \hline PolyGNN (ours) & ✓ & **96.4** & **0.81** & **4.7** \\ \hline \hline \end{tabular}
\end{table}
Table 4: Accuracy comparison with 2.5D DC (Zhou and Neumann, 2010), City3D (Huang et al., 2022), and Points2Poly (Chen et al., 2022). The errors are measured by Hausdorff distance, which does not apply to 2.5D DC.

Figure 13: Qualitative comparison with state-of-the-arts. From left to right: input point cloud, 2.5D DC (Zhou and Neumann, 2010), City3D (Huang et al., 2022), Points2Poly (Chen et al., 2022), and PolyGNN (ours). The errors are measured by Hausdorff distance, which does not apply to 2.5D DC. Point clouds are rendered by their height fields.

\begin{table}
\begin{tabular}{c c c c c c} \hline \hline Method & Label type & \#Queries _train_ & \#Queries _test_ & Efficiency _train_ & Efficiency _test_ \\ \hline Points2Poly w/ exh. & Class + value & 2,600,000 & 14,146,600 & 1x & 1x \\ Points2Poly w/ ada. & Class + value & 2,600,000 & 1,127,100 & 1x & 13x \\ \hline PolyGNN (ours) w/ exh. & Class & 174,112 & 174,112 & 15x & 81x \\ PolyGNN (ours) w/ ada. & Class & 13,872 & 13,872 & 187x & 1020x \\ \hline \hline \end{tabular}
\end{table}
Table 5: Efficiency comparison between Points2Poly (Chen et al., 2022) and ours, two learning-based methods. The building in Figure 2 with 60 planar segments is taken for calculating the number of queries. Efficiency is a calculated factor based on the number of queries, and the actual gain may differ due to parallelization.
while ours only requires discrete binary-class queries directly describing the piecewise planar surface. Meanwhile, the adaptive strategy significantly reduces the number of queries for both training and testing of our method as fewer polyhedra need to be considered as candidates. Secondly, the interface computation, which is necessary for assigning graph edge weights, contributes to the longer running time of Points2Poly. In contrast, PolyGNN can reconstruct a building directly by inferring the polyhedral occupancy, benefiting from parallelization within GPU.

### Applications and limitations

We have designed our framework to be generic. In principle, our proposed method can also be extended to handle other types of point clouds, such as photogrammetric ones. PolyGNN can also be used for the reconstruction of generic piecewise planar 3D objects beyond buildings.

For the evaluation to be orthogonal, we assume the availability of high-quality planar primitives extracted from point clouds. This assumption may not always be fulfilled with real-world measurements and therefore is considered a limitation of the proposed method and those of its kind. Figure 15 shows some failure cases. When reconstructing buildings with complex structures, PolyGNN encounters challenges in capturing fine details, such as intricate rooftop superstructures. This failure can be attributed to two factors. Firstly, the complexity of a building implies a larger and more intricate polyhedral embedding, which poses challenges to the network's prediction. Secondly, the training dataset predominantly consists of buildings with simple shapes, leading to an underrepresentation of complex structures. As a result, the network may have limited exposure to and understanding of complex architectural elements during training, contributing to the difficulties in capturing fine details during reconstruction.

## 6 Conclusion

We have introduced PolyGNN, a novel framework for urban building reconstruction with a polyhedron-based graph neural network. Instead of learning a continuous function with traditional deep implicit fields, our approach learns a piecewise planar occupancy function derived from polyhedral decomposition. We evaluated three sampling strategies for representing an arbitrary-shaped polyhedron within the neural network, where the skeleton variant exhibits superior performance. PolyGNN is end-to-end optimizable with simplicity and efficiency in design. Furthermore, we have developed PolyGNN on a large-scale synthetic building dataset comprised of 500k+ buildings furnished with comprehensive polyhedral labels and analyzed the transferability of our method on various data. We also evaluated the transferability of our methodology across varied data types. Qualitative and quantitative results demonstrate the effectiveness of PolyGNN, particularly in terms of efficiency.

Finally, we emphasize that there is still a performance gap between synthetic and real-world point clouds. In future work, we plan to further bridge the gap, enabling learning-based reconstruction methods to overcome abstraction and leverage a vast volume of training data more effectively. We will also investigate how to incorporate additional geometric attributes to enrich the polyhedral graph and to incorporate plane extraction into the end-to-end neural architecture.
