SpaceMesh: A Continuous Representation for Learning Manifold Surface Meshes

Much recent work has specifically studied approaches for generating surfaces meshes in learning-based pipelines.

Volumetric 3D Reconstruction. See Point2Surf [Erler et al. 2020], POCO [Boulch and Marlet 2022], NKSR [Huang et al. 2023] and BSPNet [Chen et al. 2020], etc. These methods focus on reconstructing the geometric shape, rather than the mesh structure; output connectivity is always a marching-cubes mesh (or a union-of-planes in BSPNet). Our approach instead focuses on fitting particular discrete mesh connectivity structures from data. Figure 8 and 9 include a few representative methods from this family, although they generally target significantly different goals. A parallel class of methods leverages Voronoi/Delaunay-based formulations  [Maruani et al. 2023; 2024]), but again these focus on fitting a surface’s geometric shape, rather than the particular mesh connectivity.

Direct Mesh Learning. See IER [Liu et al. 2020b], PointTriNet [Sharp and Ovsjanikov 2020], Delaunay Surface Elements (DSE) [Rakotosaona et al. 2021], DMesh [Son et al. 2024]. Like ours, these approaches aim to directly learn structured mesh connectivity. However, our approach offers a guarantee of manifoldness, and can encode general polygonal meshes. Additionally, we demonstrate the ability to encode concise artist/CAD-like tessellation via coupled learning of vertex positions and connectivity, rather than generating faces among a rough uniformly-sampled point set. Conversely, some of these methods scale to high resolution outputs, compared to our small-medium meshes. Figure 2 includes comparisons to DMesh [Son et al. 2024] as a representative method from this family, see also additional results from DSE in Figure 14 in the same setting.

Sequence Modeling. See Polygen [Nash et al. 2020], PolyDiff [Alliegro et al. 2023], MeshGPT [Siddiqui et al. 2023], and the concurrent MeshAnything [Chen et al. 2024]. These approaches use large-scale architectures to emit a mesh one face or vertex at a time. Unlike our method, they generally do not offer any guarantees of connectivity or local structure, and all but Polygen produce triangle soup, connecting faces together only by generating vertices at coarsely-discretized categorical coordinates. However, by building on proven paradigms from language modeling, these models have been successfully trained at very large scale. Additionally, many of these approaches support only unconditional generation, and some are not publicly available. We include a gallery of qualitative comparisons in Figure 15.

Our approach draws inspiration from graph learning representations, which have shown success for graphs including gene expression [Marbach et al. 2012], molecules [Kwon et al. 2020], stochastic processes [Backhoff-Veraguas et al. 2020], and social networks [Gehrke et al. 2003]. Based on the seminal work of Gromov [1987], Nickel and Kiela [2017] showed that hyperbolic embedding has fundamental properties which Euclidean embedding lacks (a relationship which has been well-studied in physics [Bombelli et al. 1987; Kronheimer and Penrose 1967; Meyer 1993]), to exploit the geometry of spacetime to represent graphs. In this paper, we leverage spacetime embeddings [Law and Stam 2020; Law and Lucas 2023] to put this perspective to work for generating meshes.

Manifold Surface Meshes. A surface mesh \(\mathcal {M}= (\mathcal {V},\mathcal {E},\mathcal {F})\) consists of vertices \(\mathcal {V}\), edges \(\mathcal {E}\), and faces \(\mathcal {F}\), where each vertex \(v\in \mathcal {V}\) has a position \(p_v\in \mathbb {R}^3\). In a general polygonal mesh, each face is a cyclic ordering of 3 or more vertices. Each edge is an unordered pair of vertices which appear consecutively in one or more faces.

We are especially concerned with generating meshes which are not just a soup of faces, but which have coherent and consistent neighborhood connectivity. As such, we consider manifold, oriented meshes. Manifold connectivity is a topological property which does not depend on the vertex positions: edge-manifoldness means each edge has exactly two incident faces, while vertex-manifoldness means the faces incident on the vertex form a single edge-connected component homeomorphic to a disk. In an oriented mesh, all neighboring faces have a consistent outward orientation as defined by a counter-clockwise ordering of their vertices.

Halfedge Meshes. There are many possible data structures for mesh connectivity; we will leverage halfedge meshes, which by-construction encode manifold, oriented meshes with possibly polygonal faces, all using only a pair of references per element. As the name suggests, halfedge meshes are defined in terms of directed face-sides, called halfedges (see inset). Each halfedge stores two references: a \(\texttt{twin}\) halfedge, the oppositely-oriented halfedge along the same edge in a neighboring face, and a \(\texttt{next}\) halfedge, the subsequent halfedge within the same face.

The \(\texttt{twin}\) and \(\texttt{next}\) operators can be interpreted as a pair of permutations over the set of halfedges, this group-theoretic perspective is studied in combinatorics as a rotation system. A pair of permutations can be interpreted as a halfedge mesh as long as (a) neither operator maps any halfedge to itself, and (b) \(\texttt{twin}\) operator is an involution, i.e. \(\texttt{twin}(\texttt{twin}(h)) = h\). The faces of the mesh are the orbits traversed by repeatedly following the \(\texttt{next}\) operator (see inset); we further require that these orbits all have a degree of at least three, to disallow two-sided faces. Our representation will construct a valid set of \(\texttt{twin}\) and \(\texttt{next}\) operators from a continuous embedding to define mesh connectivity.

To begin, consider modeling a mesh simply as a graph \(\mathcal {G}= (\mathcal {V}, \mathcal {E})\), later we will extend this model to capture manifold mesh structure via halfedge connectivity (Section 3.3). The vertex set \(\mathcal {V}\) can be viewed as a particular kind of point cloud, and point cloud generation is a well-studied problem ([Nichol et al. 2022; Zeng et al. 2022]). Likewise, continuous representations for generating undirected graph edges is a classic topic in graph representation learning [Law and Stam 2020; Nickel and Kiela 2017]. A basic approach is to associate an adjacency embedding \(x_v\in \mathbb {R}^k\) with each vertex, then define an edge between two vertices i, j if they are sufficiently close w.r.t. some distance function \(\mathsf {d}\):for some learned threshold \(\tau \in \mathbb {R}\). Representing the vertices and edges of a mesh then amounts to two vectors for each vertex v: a 3D position \(p_v\in \mathbb {R}^3\) and an adjacency embedding \(x_v\in \mathbb {R}^k\).

Spacetime Distance. We find that taking the adjacency features x as Euclidean vectors under pairwise Euclidean distance \(\mathsf {d}^\textrm {eu}(x_i, x_j) = ||x_i - x_j||_2\) is ineffective, with poor convergence in optimization and learning. There are many other possible choices of distance function for this embedding, but we find the recently proposed spacetime distance [Law and Lucas 2023] to be simple and highly effective. This distance function has deep interpretations in special relativity, defining pseudo-Riemannian structures. In our setting the spacetime distance \(\mathsf {d}^\textrm {st}\) is computationally straightforward, splitting the components of x into a subvector \(x^\textrm {s}\in \mathbb {R}^{k^\textrm {s}}\) of space coordinates, and a subvector \(x^\textrm {t}\in \mathbb {R}^{k^\textrm {t}}\) of time coordinates:where [ ·, ·] denotes vector concatenation. Note that \(\mathsf {d}^\textrm {st}\) is not a distance metric, and may be negative; this is of no concern, as we simply need to threshold it by some \(\tau \in \mathbb {R}\) to recover edges, treating τ as an additional optimized parameter. In Figure 4 we show that this significantly accelerates convergence, see Section 4 for details.

Loss Function. At training time, we fit the adjacency embedding by supervising the distances under a cross entropy loss:where σ is the logistic function (i.e.  a sigmoid), \(\mathcal {E}_\textrm {gt}\) denotes the set of edges in the ground truth mesh, and λ > 0 is a regularization parameter balancing positive and negative matches.

To recover faces and manifold connectivity from a graph \(\mathcal {G}= (\mathcal {V}, \mathcal {E})\), we further propose to parameterize halfedge connectivity for the mesh (Section 3.1). Given \(\mathcal {V}\) and \(\mathcal {E}\), we construct the halfedge set by splitting each edge e_ij between vertices i, j into two oppositely-directed halfedges h_ij, h_ji. This pairing trivially implies the \(\texttt{twin}\) relationships as \(\texttt{twin}(h_{ij}) = h_{ji}\); we then only need to specify the \(\texttt{next}\) relationships to complete the halfedge mesh and define the face set.

Neighborhood Orderings. The \(\texttt{next}\) operator defines a cyclic permutation with a single orbit on the halfedges outgoing from each vertex. Thus the task of assigning the \(\texttt{next}\) operator (and implicitly, the potentially-polygonal faces of the mesh) comes down to learning this permutation for each vertex.

Representing Neighborhood Orderings. For each vertex, we define a triplet of continuous permutation features: \(y^{\textrm {root}}, y^{\textrm {prev}}, y^{\textrm {next}}\in \mathbb {R}^{k^{\textrm {p}}}\). These are used to determine the local cyclic ordering of incident edges. Precisely, in the local neighborhood of each vertex \(i \in \mathcal {V}\) with degree D, for each pair of edges e_ij, e_ik, we combine the features of vertices i, j and k via a scalar-valued function \(F(y^{\textrm {root}}_i, y^{\textrm {prev}}_j, y^{\textrm {next}}_k)\) (see Section 4.3). Gathering these pairwise entries yields a nonnegative matrix in the local neighborhood of each vertex:where each row corresponds to an incident edge. We then use Sinkhorn normalization [Sinkhorn 1964] to recover a doubly-stochastic matrix, \(\bar{\Phi }^i\), representing a softened permutation matrix [Adams and Zemel 2011].

Loss Function. At training or optimization time, we simply supervise the matrices \(\bar{\Phi }\) directly with the ground truth permutation matrices using binary cross-entropy loss:where \(\mathcal {N}_\textrm {gt}\) is the set of all \(\texttt{next}\) relationships in ground truth mesh such that \(\texttt{next}(h_{ij}) = h_{jk}\). Note that we do not need to supervise the remaining entries of \(\bar{\Phi }^i\), which is already Sinkhorn-normalized.

Extracting Meshes. At inference time to actually extract a mesh, for each vertex neighborhood we seek the lowest-cost matching under the pairwise cost matrix \(-\bar{\Phi }^i\), among only those matchings which form a single orbit. To compute this matching, we first compute the optimal unconstrained lowest-cost matching [Jonker and Volgenant 1988]; often this matching already forms a single orbit, but when it does not we fall back on a greedy algorithm which starts at an arbitrary entry and repeatedly takes the next lowest-cost entry without violating the single-orbit constraint. These neighborhood matchings then imply halfedge connectivity as

This completes the halfedge mesh representation. Faces, potentially of any polygonal degree, can then be extracted as orbits of the \(\texttt{next}\) operator.

The most basic task for a mesh representation is to directly fit it to encode a particular mesh. Though straightforward in principle, this optimization could fail if a representation is unable to represent all possible meshes, or if local minima and slow convergence make fitting ineffective in practice. We consider three different challenging meshes with thin parts, anisotropic faces, and varying geometric details. For each single shape, we optimize to encode its connectivity with our per-vertex embeddings \((x_i,y^{\textrm {root}}_i, y^{\textrm {prev}}_i, y^{\textrm {next}}_i)\) using the loss functions from  Equation 3 and  5. In  Figure 2 we show the result of this optimization with our approach, as well as with the recent DMesh [Son et al. 2024], which proposes a Delaunay-based mesh representation. Our method not only converges much faster to the correct connectivity, but also is applicable to polygonal meshes, making it more suitable for general mesh generation tasks. Further experimental details are provided in the Supplement.

As a next basic test of the ability of our method to encode collections of shapes in a learning setting, we train a simple auto-decoder architecture on a subset of 200 shapes from the Thingi10k dataset, a challenging set of real-world models originally for 3D printing [Zhou and Jacobson 2016]. To be clear, we do not aim to demonstrate downstream learning tasks with this experiment, we simply validate that our representation can simultaneously represent a variety of complex shapes, even when the embeddings are parameterized by a neural network, see Section 5 for large-scale learning and applications. In particular, here we allocate a latent code for each mesh, and optimize those latent codes as well as the parameters of a simple transformer model [Vaswani et al. 2017] that decodes each latent code into the mesh, in the form of per-vertex positions and connectivity embeddings of our representation. See the Supplement for further experimental details. As shown in Figure 3, our model faithfully overfits the shape collection. Quantitatively, the encoded meshes achieve a mean L2 loss of 0.00062, an F1 score of 0.99 for adjacency prediction, and an accuracy of 0.98 for permutation predictions. This is positive evidence that the representation is able to simultaneously represent many complex shapes, even with significant geometric complexity and the nonconvexity of the neural parameterization.

Spacetime Distance. We find spacetime distance to be a dramatically more effective representation than Euclidean or other metrics to define adjacency embeddings (Section 3.2), in the sense that it can be optimized much more easily. To demonstrate this, we fit the edges of the bridge mesh appearing on the bottom right of  Figure 4 using each of three formulations for \(\mathsf {d}(x_i, x_j)\): (1) the spacetime distance introduced in Section 3.2, (2) the squared Euclidean distance \(\Vert x_i - x_j \Vert _2^2\), and (3) the negative dot product \(- x_i^{\top } x_j\). Figure 4 shows the speed of convergence—spacetime distance converges much faster compared to other distance formulations, which we observed consistently across all experiments.

Permutation Feature Reduction. We also investigate several choices for the permutation feature reduction function F (Equation 7), including elementwise maximum, addition, or concatenation. Figure 5 shows the results. We find elementwise multiplication followed by summation of all elements to be most effective. Precisely, we usewhere diag denotes constructing a diagonal matrix from a vector.

Our model architecture (Figure 6), consists of three modules: a point cloud encoding network for processing geometry information, a vertex diffusion model to generate 3D locations for vertices, and a connectivity prediction network to predict per-vertex embeddings.

Point Cloud Encoder. We encode the point cloud using PVCNN [Liu et al. 2019] to generate the feature volumes at multiple spatial resolutions. These feature volumes, as geometry context, guide the subsequent mesh generation. Note that this input point cloud is not the resulting mesh vertex set, it is conditioning information indicating the geometry that we are trying to generate a mesh of.

Vertex Position Generation Network. We re-purpose Point-E [Nichol et al. 2022], a diffusion transformer network that was originally designed for point cloud generation, to generate sparse mesh vertices conditioned on the geometry context from the encoder. Specifically, we first initialize the vertex position by sampling from a Gaussian distribution, and iteratively denoise the vertex location through the diffusion transformer. At each denoising step, we feed the input to the transformer by concatenating the vertices’ positions with features that are tri-linearly interpolated with the multi-resolution feature volumes from the encoder to capture the geometry information. If needed, we handle varying vertex counts by padding to a predefined maximum size, and additionally diffusing a binary mask at each vertex to indicate which vertices are artificial padding.

Vertex Connectivity Prediction Network. We leverage a transformer architecture [Vaswani et al. 2017] to predict the per-vertex connectivity embeddings given vertex positions. Similar to the vertex position generation network, we concatenate vertex position with the interpolated feature from the encoder for each vertex, and predict the adjacency embeddings x and permutation embeddings y^root, y^prev, y^next. We remove the positional embedding from the original transformer and predict the embeddings for all the vertices simultaneously by using the self-attention across the vertices.

Training Details. We train all the neural networks together. To train the vertex position generation network, we adopt the ϵ -prediction from the diffusion model [Ho et al. 2020; Nichol et al. 2022]. To train the connectivity generation model, we combine the losses Equation 3 and 5, supervising on meshes from the dataset. Further details are provided in the Supplement.

Our model learns to fit distributions of meshes; the tessellation pattern and element shapes of generated meshes will mimic the training population. We first demonstrate this behavior with a simple synthetic dataset, constructed by generating shapes as a union of randomly arranged cubes, tetrahedra, and spheres. For each shape, we extract a 3D iso-surface using Dual Marching Cubes [Nielson 2003], and mesh it according to several strategies: (1) isotropic remeshing [Hoppe et al. 1993] with Meshlab [Cignoni et al. 2008] (2) planar decimation from Blender [Community 2018] to create N-gon mesh. (3) QEM for surface simplification [Garland and Heckbert 1997] from Meshlab, and (4) InstantMesh [Jakob et al. 2015] to create a quad-dominant mesh with the official implementation

In  Figure 7, we show how training on each of these datasets causes our model to generate different styles of meshes as outputs. The four models, when each given the same point cloud as input specifying the desired geometry, produce respectively (1) isotropic triangle meshes, (2) minimal planar-decimated meshes, (3) QEM-simplified meshes, and (4) quad-dominant meshes.

To evaluate learning at scale on a realistic dataset, train our model on ABC dataset [Koch et al. 2019a], which consists of watertight triangle meshes of CAD shapes with isotropic triangle distribution. The meshes in the ABC dataset exhibit considerable diversity, featuring both sharp and smooth curved geometric features. We employed a benchmark [Koch et al. 2019b] subset of 10,000 shapes, all with 512 vertices, randomly split into 80% for training and 20% for testing. To obtain the input conditioning point cloud, we uniformly sampled 2048 points from the mesh surface.

Baselines. We compare our model against both classic and learning-based point cloud reconstruction methods. As a representative classic approach, we compare to Poisson Surface Reconstruction (PSR) [Kazhdan et al. 2006] as implemented in Open3D [Zhou et al. 2018], with meshes extracted via marching cubes [Lorensen and Cline 1998]. We also consider isotropic remeshing [Hoppe et al. 1993] on the output of Poisson reconstruction to obtain a more compact mesh tessellation, which is denoted PSR^*. For representative learning-based approaches, we choose Pixel2Mesh [Wang et al. 2018], which deforms a template sphere to generate a mesh, and OccNet [Mescheder et al. 2019], which predicts an implicit field and extracts the mesh using Marching Cubes [Lorensen and Cline 1998] afterwards. For a fair comparison among deep learning based methods, we adopt the same point cloud encoder as our approach.

Metrics. Our primary goal is to evaluate the ability to capture the desired distribution of surface discretization, as measured by intrinsic mesh statistics such as edge lengths and corner angles for each polygon. Furthermore, although our method is not directly designed to minimize reconstruction error, we additionally evaluate our method against baselines on how well the generated meshes align with ground truth geometry. To this end, we follow the methodology from NDC [Chen et al. 2022] and compute Chamfer Distance (CD), F-Score (F1), Edge Chamfer Distance (ECD), Edge F-Score (EF1), and the percentage of Inaccurate Normals (IN> 10°) with respect to the ground truth mesh. A detailed description of these metrics is provided in the Supplement.

Results. As shown in Figure 9 and Table 1, both qualitative and quantitative results demonstrate that our method outperforms baselines under the target metrics, particularly in recovering sharp features. The vertices and edges align accurately with sharp features, highlighting the advantage of directly generating meshes as the output representation. As shown in Figure 8, the distribution of element shapes from our generated meshes aligns much better with the ground truth than the baselines, demonstrating the ability of our model to predict connectivity which aligns with the target training population. Note that although our representation guarantees manifold connectivity, there may still be geometric self-intersections between faces. We report the fraction of faces in each mesh with self-intersections in Figure 8, and provide further discussion in Section 6.

Following recent work on mesh generation [Alliegro et al. 2023; Gao et al. 2022; Nash et al. 2020; Siddiqui et al. 2023], we further evaluate our model on ShapeNet dataset [Chang et al. 2015].

Dataset Details. As in prior work [Nash et al. 2020; Siddiqui et al. 2023], we note that the raw meshes from ShapeNet consist largely of non-manifold meshes with duplicated faces and T-junctions at intersections, and thus we preprocess all shapes by removing duplicated faces and applying planar decimation with varying thresholds to simplify them into minimal polygonal meshes. After this preprocessing, the majority of the shape are still non-manifold, making them unsuitable for our goal of generating manifold meshes with clean connectivity. We thus remove all non-manifold shapes, resulting in a total of 20,255 shapes. We adhere to an 80-20 train-test split and randomly sample 2,048 surface points as geometry conditioning input. Additionally, we apply random scaling augmentation during training. Unlike previous autoregressive methods, our approach does not require quantization of vertices.

Baselines. Many relevant baselines  [Alliegro et al. 2023; Nash et al. 2020; Siddiqui et al. 2023] do not have either training or inference code available, and regardless there are many differences in experimental protocols and target task. As such, we instead focus on qualitative comparisons to give intuition about the differences between these methods, primarily in regard to mesh quality.

Results. Figure 15 shows a variety of results generated by our method, as well as a sampling of published results from baselines. Our method generates sharp and compact polygonal meshes that match with the input condition and are guaranteed to be manifold. We also note a promising diversity in our outputs on this dataset: because our model uses a probabilistic diffusion model to generate vertices, we are able to produce distinct meshes conditioned on the same point cloud input by repeatedly sampling the model (Figure 10).

Lastly, we demonstrate the application of our model to the downstream geometry processing task of mesh repair. As illustrated in Figure 11, we envision a workflow where a user identifies a region of a mesh with poor tessellation such as self-intersections, skinny triangles, or non-manifold structures, and wishes to re-triangulate that region in a way that seamlessly blends with the surrounding mesh. We show that we can repurpose our model for this task without retraining, by viewing it as mesh inpainting, in the same sense that image models are used to inpaint undesired regions of images according to some conditioning while matching the surrounding context. We inpaint the mesh by sampling a point cloud from the desired geometry and applying our generative model, projecting during diffusion to ensure the fixed region of the input mesh is retained—see the Supplement for an in-depth explanation. Note that MeshGPT [Siddiqui et al. 2023] also demonstrated completion of a partial mesh; however, it was limited to bottom-up completion due to auto-regressive inference with sorted vertices.

Results. We visualize the results in Figure 12. Our approach generates high-quality patches to fill the removed regions in the partial meshes while preserving the geometry and connectivity of the input. For comparison, we also include the most similar results of which we are aware: a classic mesh repair framework, MeshFix [Attene 2010], and a recent learning-based method, SeMIGCN [Hattori et al. 2024]. However, note that this is not exactly an apples-to-apples comparison, our method additionally takes the surface point cloud of the complete shape as input, with a focus on re-generating surface discretization while preserving geometry. MeshFix is designed only for hole filling and cannot generate a repaired mesh conditioned on the geometry. In contrast, SeMIGCN re-meshes the shape for running GCN, resulting in an overly dense mesh that might not be desirable. We compare quantitatively with 100 randomly sampled examples from the ABC dataset validation shapes. SpaceMesh achieved a Chamfer Distance (CD) of 0.77 (10^{− 3}) and a 0.76 F1 score. The baselines, SeMIGCN and MeshFix, achieve a CD of 39.50 (10^{− 3}) and 31.59 (10^{− 3}), and an F1 score of 0.57 and 0.72, respectively.