Learning to Tessellate: Point Cloud Generation via Recursive Spectral Partitioning

Conference: ECCV 2026
Paper: ECCV Official
Code: https://huggingface.co/Mo-nan/PointRSP
Area: Model Compression
Keywords: point cloud generation, autoregressive model, recursive spectral partitioning, topology-preserving tessellation, dual-stream cascaded generator

TL;DR

PointRSP reformulates 3D point cloud generation as a topology-preserving spatial tessellation process via recursive spectral partitioning, building a non-balanced binary tree geometric blueprint and a dual-stream cascaded generator that significantly eliminates fragmentation artifacts and sets new SOTA generation benchmarks.

Background & Motivation

Point clouds serve as a foundational representation of 3D geometric manifolds across applications such as embodied perception, autonomous navigation, and shape reconstruction. Nevertheless, their unstructured, permutation-invariant nature presents fundamental challenges for generative modeling. While denoising diffusion probabilistic models (such as PVD, LION, and TIGER) have emerged as the prevailing standard capable of producing visually coherent global silhouettes, their reliance on continuous-space global denoising trajectories entails substantial computational cost. Moreover, holistic denoising often fails to respect fine-grained topological constraints, producing isolated floating outliers, surface perforations, and boundary blurring along delicate thin structures.

Discrete autoregressive (AR) models offer an efficient alternative by learning sequential geometric dependencies via next-token prediction. However, unlike 2D pixel grids that possess natural raster orderings, unordered 3D point sets lack a canonical sequence. Existing autoregressive architectures typically resort to heuristic linearizations, such as coordinate sorting, space-filling curves, or stochastic downsampling (e.g., PointNSP). These artificial orderings fundamentally disrupt local manifold continuity, causing structural fragmentation across synthesized parts. Furthermore, hierarchical discrete quantizers (such as NVG) enforce rigid, uniform binary splitting via kNN clustering, producing exactly \(2^t\) subsets at level \(t\). This balanced assumption directly contradicts the intrinsic, highly non-uniform geometric complexity of real-world 3D objects.

To overcome these structural limitations, this paper reformulates point cloud generation as an adaptive, topology-preserving tessellation process. Core idea: PointRSP decomposes unstructured point sets into an adaptive non-balanced binary tree blueprint via hybrid recursive spectral partitioning, and utilizes a dual-stream cascaded generator paired with geometry-calibrated positional encoding to resolve early cold-start instability and synthesize topologically faithful 3D shapes.

Method

Overall Architecture

The PointRSP architecture comprises two cooperative components: the Topology-Aware Partitioning Autoencoder (TPA) and the Dual-Stream Autoregressive Generator. The TPA uses a sparse convolutional backbone to extract continuous point features, progressively executes bottom-up greedy merging to retain fine-grained details, and performs top-down graph Laplacian spectral bipartitioning to construct an adaptive non-balanced binary tree blueprint. Driven by this blueprint, multi-scale vector quantization builds a compact discrete latent space. During autoregressive synthesis, the dual-stream generator iteratively alternates between structural tree branching prediction and residual feature synthesis. Crucially, a geometry-calibrated positional encoding dynamically smooths early unstable coordinates using multi-scale geometric centroids, yielding robust and stable point cloud synthesis decoded via an MLP decoder.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["Unordered Input Point Cloud X in R^(L×3)"] --> Enc["Sparse Convolutional Feature Extractor F0 in R^(L×D)"]
    Enc --> TPA["Topology-Aware Partitioning Autoencoder<br/>Bottom-Up Greedy Merging + Top-Down Spectral Splitting"]
    TPA --> Tree["Non-Balanced Binary Tree Blueprint S^(2)"]
    Tree --> Quant["Non-Balanced Tessellated Vector Quantization<br/>Subset Pooling -> Codebook Mapping -> Broadcast"]
    Quant --> Gen["Dual-Stream Cascaded Generator<br/>Feature Predictor Stream + Structural Predictor Stream"]
    Pos["Geometry-Calibrated Positional Encoding<br/>Multi-Scale Structural Centroid Anchoring"] --> Gen
    Gen --> Dec["Multilayer Perceptron Decoder D"]
    Dec --> Out["Topology-Preserved Reconstructed/Generated Point Cloud X_hat"]

Key Designs

1. Hybrid Recursive Spectral Partitioning: Decoupling Local Feature Aggregation and Global Manifold Splitting

Performing token-level recursive spectral graph clustering across an entire dense point cloud is computationally prohibitive and prone to misaligned boundary sequences. To address this complexity bottleneck, TPA introduces a two-stage hybrid partitioning pipeline spanning \(T\) scale levels, split into \(T_l\) bottom-up greedy merging steps and \(T_k\) top-down spectral splitting steps such that \(T_l + T_k = T\). In the merge stage, the model starts from point features \(F_0 \in \mathbb{R}^{L \times D}\) and iteratively merges the most similar token pairs based on local Euclidean feature distances, reducing the sequence length from \(L\) to \(K\) (satisfying \(\log_2 L - \log_2 K = T_l\)). This captures high-frequency local details while consolidating points into computationally manageable super-nodes \(F_k\).

In the spectral split stage, a \(k\)-nearest-neighbor graph Laplacian is constructed over the \(K\) merged super-nodes, performing recursive bipartitioning for scales \(t \in [0, T_k - 1]\). Let \(v(k, t)\) denote the Fiedler vector (the eigenvector associated with the second smallest eigenvalue of the graph Laplacian), which provides the optimal continuous relaxation for graph min-cut partitioning. Structural split decisions are deterministically assigned based on the sign of the Fiedler vector: $$ s^{\text{split}}(k, t) = \begin{cases} 0, & v(k, t) \le 0, \quad t < l_k \ 1, & v(k, t) > 0, \quad t < l_k \ \text{pad}, & \text{otherwise} \end{cases} $$ Because distinct geometric regions feature varying structural complexity, individual branches reach terminal leaf states at different depths \(l_k\), naturally yielding a non-balanced binary tree. Finally, an alignment operator \(\text{map}(\cdot)\) traces each original point through the merge hierarchy back to its spectral split super-node, constructing an unbroken, topology-preserving binary structural blueprint \(S^{(2)} \in \{0, 1\}^{L \times T}\).

2. Non-Balanced Tessellated Vector Quantization: Geometry-Adaptive Hierarchical Latent Discretization

Prior hierarchical visual quantizers (such as NVG) enforce rigid balanced bisections, producing exactly \(2^t\) clusters at level \(t\). This forces flat, simple regions to be unnecessarily over-partitioned while compelling thin, intricate parts to merge with unrelated neighboring regions. PointRSP leverages its non-balanced tree blueprint to convert binary split strings into decimal indices \(c = \text{Dec}(s^{(2)}(i, :t)) = \sum_{j=0}^t s^{(2)}(i, j) 2^{t-j}\), grouping tokens at scale \(t\) into \(C_t\) disjoint, topologically continuous subsets \(F_t^c\). Within each subset, features are pooled into an atomic structural representation: $$ \bar{F}t^c = \frac{1}{|F_t^c|} \sum f $$ Each pooled representation \(\bar{F}_t^c\) is mapped via nearest-neighbor lookup to discrete entries in a learnable codebook \(\mathcal{Z}\), and the resulting discrete code is broadcast back to all tokens sharing label \(c\), yielding quantized sequence \(Q_t \in \mathbb{R}^{L \times D}\). Residual features are progressively forwarded to subsequent scales, concentrating codebook capacity on complex topological contours and preventing boundary blurring.

3. Dual-Stream Cascaded Generator: Explicit Structural Blueprint Dictating Residual Feature Synthesis

Conventional 3D autoregressive models rely on implicit attention masking to capture geometric context, lacking explicit topological control. PointRSP designs a dual-stream cascaded generation framework comprising two explicit, dedicated modules: a Structural Predictor and a Feature Predictor, both built on Transformer self-attention blocks with Rotary Position Embeddings (RoPE). At scale \(t\), the Feature Predictor predicts residual continuous feature embeddings \(\widetilde{F}_t\) conditioned on historical accumulated features \(\widetilde{F}_{:t-1}\), which are subsequently quantized under the guidance of prior structure \(\widetilde{S}_{t-1}\) to update the representation to \(\widetilde{F}_{:t}\).

Subsequently, the Structural Predictor takes the concatenation of updated accumulated features \(\widetilde{F}_{:t}\) and the projected prior binary structural labels \(\varphi(\text{Bin}(\widetilde{S}_{t-1}))\) to predict the branching probabilities for the current scale: $$ \widetilde{S}t^{(2)} = \sigma\left(\text{Attn}^s\left([\widetilde{F}))]\right)\right) $$ By explicitly feeding structural blueprints to constrain feature quantization while using synthesized features to guide structural evolution, the two streams mutually reinforce each other, resulting in topologically faithful and interpretable 3D shape generation.}, \varphi(\text{Bin}(\widetilde{S}_{t-1

4. Geometry-Calibrated Positional Encoding: Stabilizing Early Cold-Start via Multi-Scale Structural Centroids

During the initial coarse scales of cascaded generation, intermediate coordinates \(\widetilde{X}_{t-1} = \mathcal{D}(\widetilde{F}_{:t-1})\) inverted from rough features contain severe noise. Directly utilizing these fluctuating coordinates for positional encoding leads to severe "cold-start" error propagation. To stabilize this phase, PointRSP introduces Geometry-Calibrated Positional Encoding (GCPE), decomposing positional embeddings into discrete structural tokens \(E_s^t\) and geometry-calibrated coordinate tokens \(E_{\text{pos}}^t\).

For scales \(t < T_k\), the mechanism partitions tokens into \(M_t\) structural groups based on \(\widetilde{S}_t\) and computes their 3D centroids \(P \in \mathbb{R}^{M_t \times 3}\). Individual token coordinates are dynamically calibrated via an exponentially weighted sum of historical structural centroids: $$ e(i, t) = \alpha \cdot x(i, t) + (1 - \alpha) \sum_{j=0}^{t-1} w_j \cdot P(\text{map}(i, \widetilde{S}t), j), \quad (w w_j = 1) $$ As generation reaches finer scales (} = 2 w_j, \sum_{j=0}^{t-1\(t \ge T_k\)), intermediate coordinates become geometrically stable, and the encoding smoothly transitions to raw coordinates \(x(i, t)\). This dynamic anchoring prevents early trajectory divergence.

Loss & Training

The framework is optimized in two sequential training stages: 1. Autoencoder Training: The autoencoder is trained end-to-end using a weighted combination of three objective terms: $$ \mathcal{L}{\text{total}} = \lambda}} \mathcal{L{\text{L1}}^{\text{smooth}}(X, \hat{X}) + \lambda}} \mathcal{L{\text{cmf}}(X, \hat{X}) + \lambda}} \mathcal{L{\text{vq}}(F_0, \hat{F}_T) $$ Smooth-L1 loss \(\mathcal{L}_{\text{L1}}^{\text{smooth}}\) and Chamfer loss \(\mathcal{L}_{\text{cmf}}\) enforce surface alignment and global fidelity, while improved vector quantization loss \(\mathcal{L}_{\text{vq}}\) maximizes codebook utilization. 2. Generator Training: The feature predictor and structural predictor are jointly supervised using mean squared error (MSE): $$ \mathcal{L}}} = \frac{1}{T}\sum_{t=1}^T \mathcal{L{\text{mse}}(\hat{F}_t, \widetilde{F}) $$ Crucially, structural supervision is restricted to the spectral split horizon (}) + \frac{1}{T_k}\sum_{t=1}^{T_k} \mathcal{L}_{\text{mse}}(S_t^{(2)}, \widetilde{S}_t^{(2)\(t \le T_k\)), preventing the structural branch from overfitting to high-frequency local noise.

Key Experimental Results

Main Results

Quantitative evaluations are conducted on ShapeNetV2 across three structurally diverse benchmark categories: Airplane, Chair, and Car, using the 1-nearest neighbor accuracy (1-NNA, %; closer to 50% denotes higher quality and diversity) under both Chamfer Distance (CD) and Earth Mover's Distance (EMD). PointRSP is compared against leading diffusion models (PVD, LION, TIGER) and discrete autoregressive frameworks (PointGrow, CanonicalVAE, PointGPT, PointNSP).

Model Family	Model	Airplane CD↓ (%)	Airplane EMD↓ (%)	Chair CD↓ (%)	Chair EMD↓ (%)	Car CD↓ (%)	Car EMD↓ (%)	Mean CD↓ (%)	Mean EMD↓ (%)
GAN	1-GAN (Achlioptas et al.)	87.30	93.95	68.58	83.84	66.49	88.78	74.12	88.86
Normalizing Flow	PointFlow (Yang et al.)	75.68	70.74	62.84	60.57	58.10	56.25	65.54	62.52
Diffusion	DPM (Luo & Hu)	76.42	86.91	60.05	74.77	68.89	79.97	68.45	80.55
Diffusion	PVD (Zhou et al.)	73.82	64.81	56.26	53.32	54.55	53.83	61.54	57.32
Diffusion	LION (Vahdat et al.)	72.99	64.21	55.67	53.82	53.47	53.21	61.75	57.59
Diffusion	TIGER (Ren et al.)	73.02	64.10	55.15	53.18	53.21	53.95	60.46	57.08
Autoregressive	PointGrow (Sun et al.)	82.20	78.54	63.14	61.87	67.56	65.89	70.96	68.77
Autoregressive	CanonicalVAE (Cheng et al.)	80.15	76.27	62.78	61.05	63.23	61.56	68.72	66.29
Autoregressive	PointGPT (Chen et al.)	74.85	65.61	57.24	55.01	55.91	54.24	63.44	62.24
Autoregressive	PointNSP (Meng et al.)	73.39	64.58	55.60	54.17	53.66	54.26	60.88	57.67
Autoregressive	PointRSP (Ours)	70.68	63.94	53.88	53.96	51.47	52.68	58.67	56.86

In multi-class class-conditional generation across all 55 ShapeNet categories and 2× point cloud upsampling (1,024 to 2,048 points), PointRSP demonstrates strong generalization across diverse shape distributions:

Task	Category	LION CD / EMD (%)	TIGER CD / EMD (%)	PointGPT CD / EMD (%)	PointNSP CD / EMD (%)	PointRSP (Ours) CD / EMD (%)
Multi-Class Generation	Airplane	86.30 / 77.04	83.54 / 81.55	94.94 / 91.73	78.95 / 68.84	76.52 / 68.79
Multi-Class Generation	Chair	66.50 / 63.83	57.34 / 61.45	71.83 / 79.00	58.79 / 55.10	57.11 / 56.07
Multi-Class Generation	Car	64.52 / 54.21	65.79 / 57.24	89.35 / 87.22	69.97 / 52.89	58.39 / 53.51
2× Point Upsampling	Airplane	70.41 / 59.65	71.65 / 59.94	72.11 / 60.12	69.86 / 59.68	67.29 / 59.09
2× Point Upsampling	Chair	53.98 / 54.33	52.80 / 52.98	53.75 / 53.21	53.79 / 53.84	52.05 / 52.63
2× Point Upsampling	Car	57.14 / 47.56	57.90 / 48.01	57.26 / 47.85	56.69 / 46.93	54.95 / 48.63

Ablation Study

The ablation study on the ShapeNetV2 Car category isolates the individual contribution of each architectural component, reporting 1-NNA alongside the batch-wise standard deviation of MMD to evaluate distribution alignment and stability:

Model Variant	Cascaded (Cas.)	Structure Prior (Struc.)	Spectral Partitioning (TPA)	Calibrated PE (GCPE)	1-NNA CD↓ (%)	MMD CD Std.↓	1-NNA EMD↓ (%)	MMD EMD Std.↓	Note
Base	-	-	-	-	53.66	\(0.357 \times 10^{-3}\)	54.26	\(1.027 \times 10^{-3}\)	PointNSP-style VAE + global self-attention generator
V1	✓	-	-	-	53.02	\(0.343 \times 10^{-3}\)	53.84	\(0.923 \times 10^{-3}\)	Cascaded multi-scale generation baseline
V2	✓	✓	-	-	52.75	\(0.318 \times 10^{-3}\)	53.65	\(0.713 \times 10^{-3}\)	Incorporating NVG-style balanced kNN binary tree prior
V3	✓	✓	✓	-	51.89	\(0.304 \times 10^{-3}\)	53.01	\(0.636 \times 10^{-3}\)	Upgrading to non-balanced recursive spectral autoencoder
Full	✓	✓	✓	✓	51.47	\(\mathbf{0.294 \times 10^{-3}}\)	52.68	\(\mathbf{0.506 \times 10^{-3}}\)	Full PointRSP with geometry-calibrated positional encoding

Key Findings

• Superiority of Non-Balanced Spectral Splitting: Upgrading from balanced kNN bisection (V2) to non-balanced recursive spectral partitioning (V3) reduces 1-NNA CD from 52.75% to 51.89% and 1-NNA EMD from 53.65% to 53.01%. This confirms that adapting to non-uniform geometric complexity prevents artificial boundary tearing.
• GCPE Tames Cold-Start Instability: Introducing GCPE in the Full model reduces the batch-wise MMD EMD standard deviation from \(0.636 \times 10^{-3}\) (V3) to \(0.506 \times 10^{-3}\), a variance drop of over 20%. Anchoring coarse features with multi-scale geometric centroids stabilizes early generation trajectories.
• Outperforming Leading Diffusion Baselines: In overall mean 1-NNA, PointRSP achieves 58.67% (CD) and 56.86% (EMD), outperforming state-of-the-art diffusion models such as TIGER (60.46% / 57.08%) and LION (61.75% / 57.59%), proving that topology-aware autoregressive generation can match and exceed continuous diffusion fidelity.

Highlights & Insights

• Graph Laplacian Fiedler Vector for Point Sequence Planning: Using the continuous relaxation of the min-cut problem to guide discrete point serialization establishes a manifold-preserving topological order, resolving the fragmentation caused by 1D heuristic orderings.
• Hybrid Greedy Merging and Top-Down Spectral Splitting: Decoupling fine-grained bottom-up token grouping from macro-scale top-down spectral bipartitioning solves the computational bottleneck of graph spectral decomposition while preserving multi-scale detail.
• Centroid-to-Coordinate Smooth Anchoring Transition: Anchoring early tokens via exponentially weighted structural centroids before transitioning to local coordinates resolves cold-start instability, an insight broadly applicable to hierarchical 3D generators.

Limitations & Future Work

• Object-Centric Scale: The framework has been validated on single object point clouds (2,048 points) and upsampling tasks, but its scalability to scene-level point clouds containing multiple interacting entities remains unverified.
• Non-Differentiable Tree Construction: While autoencoding and generation are supervised with continuous loss terms, the recursive spectral tree construction remains a discrete graph algorithm not amenable to end-to-end backpropagation.
• Multimodal Extension: Future work should explore conditioning the dual-stream generator on text or images, enabling controllable, topologically faithful text-to-3D autoregressive generation.

Related Work & Insights

• vs PointNSP (Meng et al., CVPR 2026): PointNSP pioneers next-scale autoregressive point cloud prediction but relies on stochastic subset downsampling without deterministic topological correspondence; PointRSP establishes deterministic topological blueprints via recursive spectral bisection, outperforming PointNSP across all single- and multi-class benchmarks.
• vs NVG (Wang et al., ICLR 2026): NVG constructs balanced hierarchical trees for image generation, forcing \(2^t\) clusters per scale; PointRSP accommodates non-balanced 3D geometric distributions, preventing over-segmentation of flat surfaces and boundary distortion on delicate parts.
• vs 3D Diffusion Models (LION / TIGER): Diffusion models require hundreds of iterative denoising steps and often suffer from isolated floating artifacts; PointRSP requires only a few cascaded autoregressive steps, producing cleaner boundaries with significantly lower sampling latency.

Rating

• Novelty: ⭐⭐⭐⭐⭐ Formulates point cloud generation as recursive spectral tessellation, introducing non-balanced tree blueprints to 3D autoregressive generation.
• Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive benchmarking across single-class, 55-class multi-category, and 2× upsampling settings with stability-focused ablations.
• Writing Quality: ⭐⭐⭐⭐⭐ Rigorous mathematical formulation, clear architectural illustrations, and cohesive motivation-to-design alignment.
• Value: ⭐⭐⭐⭐⭐ Provides an effective paradigm shift for autoregressive 3D generation, showing that graph-spectral priors can bridge discrete tokenization and continuous manifold topology.