Ranking Neighborhood Sizes Instead of Guessing Them

Estimating a surface normal at a point in a 3D scan means fitting a plane or small polynomial to the point's neighbors, and the answer depends heavily on how many neighbors you take. Too few, and sensor noise dominates. Too many, and the fit bends over edges or picks up points from a nearby parallel surface. The right size changes from point to point. We propose to treat the per-point choice of size as a small ranking problem. For each point, a lightweight network looks at a dense ladder of candidate radii and predicts, for each one, how wrong the normal fitted at that radius will be, in degrees. It is trained with two terms. A regression term keeps the predicted errors in real units. A ranking term, which ignores near-ties, makes the network order the radii correctly where the ordering actually matters.

Put simply, if you only regress errors, the network spends its effort on the huge errors of obviously bad radii. If you only rank, its scores float free of any unit and cannot be compared across points. Combining the two, a recipe borrowed from search ranking and drug-activity prediction, should give both a good per-point choice of radius and a usable per-point estimate of how much to trust that normal.

Core Claim

Neighborhood size selection for local geometric estimation has the same structure as a listwise ranking problem with a calibration requirement. The candidates are radii, the "relevance" is the negative fitting error at each radius, and the downstream needs both the argmin and its value. We claim that a hybrid loss combining log-error regression with a tie-aware listwise ranking term over radii will do three things. It will lower the gap between the chosen radius and the oracle-best radius compared with regressing errors alone or classifying the best radius. It will yield per-point error predictions whose rank correlation with true error is high enough for selective prediction. And it will do this with one shared network over a dense set of radii, rather than one expert sub-network per scale.

Relation to Prior Work

Several learned normal estimators already try to cope with scale. They differ from this proposal in what they supervise.

PCPNet feeds three nested radii into a modified PointNet and lets the normal loss sort out the mixing. CMG-Net does the same with attention over several neighbor counts and a Chamfer-based normal loss. In both, any notion of which scale is reliable is implicit and never supervised.

Nesti-Net is the closest ancestor and supplies our motivation. Its scale manager explicitly picks one scale per point and sends the point to a dedicated expert. It shows that this kind of specialization beats averaging under high noise, with RMS angle error 22.28 against PCPNet's 22.8. Nesti-Net trains a hard classifier over a few bins with duplicated experts. We instead score a dense ladder of radii with a single network, supervise the full ordering rather than only the winner, and keep calibrated error values.

DeepFit and AdaFit convert scale choice into learned per-neighbor weights inside a differentiable weighted least-squares fit, and AdaFit adds coordinate offsets and cross-scale aggregation. Both still depend on a fixed initial candidate patch, which is the limitation our approach targets. In our design these methods are interchangeable base estimators that can be run at each radius, not competitors to be replaced.

PFF-Net shrinks the patch progressively by Euclidean distance. STAR-Edge documents why large neighborhoods fail on thin walls and edges. Together these two papers constrain the design: the candidate ladder must include radii small enough to stay on one sheet.

LEGO avoids local scale selection for tangent estimation by taking gradients of global Laplacian eigenvectors. That is a different trade: it needs a global eigendecomposition and spectral hyperparameters.

The loss itself comes from the ranking literature.

None of these works treats spatial neighborhood sizes as the items being ranked. CliffRank's "neighborhoods" are fixed matched molecular pairs, and its $\delta$ is hand-tuned. We take its tie-aware hybrid loss and replace the hand-tuned threshold with one derived from the measured variability of the geometric fit.

Research Program

The pipeline has three parts: building per-radius error targets, training a scorer on them, and producing a final normal.

Building targets. For each training point we fix a ladder of $S$ radii, for example 16 values spaced geometrically between a few and a few hundred neighbors. We run a base estimator at every radius. The cheap default is plane fitting by principal component analysis (PCA) plus a second-order jet. The strong variant is a pretrained DeepFit evaluated on each radius' patch. Comparing each fitted normal to the ground-truth normal gives a true angular error $e_s$ for every radius. This costs one pass over the training set and requires no new labels.

The scorer. A small PointNet-style network looks at the largest patch, with the radius given to it as an input, and outputs a predicted error $\hat e_s$ for every radius in one shot.

The training loss. The loss is

$$ \mathcal{L} = \sum_{s}\big(\log \hat e_s - \log e_s\big)^2 \;+\; \lambda \sum_{(s,t):\,|e_s - e_t| > \delta_{st}} \log\big(1 + \exp(\hat e_s - \hat e_t)\big)\,\mathbb{1}[e_s < e_t], $$

where the first sum anchors predictions in log-degrees and the second penalizes misordered radius pairs whose true errors differ by more than $\delta_{st}$.

The threshold is not hand-set. We define $\delta_{st} = c\sqrt{v_s + v_t}$, where $v_s$ is the variance of the error at radius $s$ under bootstrap resampling of the patch. Two radii are then treated as tied exactly when their difference is within fitting noise, which leaves one scalar $c$ in place of CliffRank's free margin.

Two details of the design matter. We use the log of the error because errors are heavy-tailed across radii, and plain squared error would be dominated by over-smoothed fits at edges. The pairwise term involves at most $S^2 = 256$ pairs per point, so the quadratic pair count that worries ranking practitioners is negligible here.

The final normal. At test time we compute the fits at all radii, which is cheap for PCA, and output either the normal at the argmin radius or a blend weighted by $\exp(-\hat e_s/\tau)$. Because $\hat e$ is calibrated, its minimum value serves as a per-point confidence. We will test whether this confidence predicts true error across points, which a pure ranker cannot provide.

Analyses. Beyond accuracy, we will analyze where the chosen radius changes. We expect small radii near edges and thin walls, large radii in flat noisy regions, and smooth variation in between. We will also check whether the ranking term mainly helps on edge points, the geometric analogue of CliffRank's activity cliffs.

Baselines

Fixed single radius. The naive reference is PCA and jet fitting at one global radius, tuned on validation data per noise level. Every method must beat this.

Oracle radius. The upper reference picks, per point, the radius with the lowest true error from the same ladder. It bounds what any selector over this base estimator can achieve. The key metric is how much of the gap between fixed-radius and oracle each method closes.

Strongest existing methods. These are PFF-Net, CMG-Net and AdaFit, run from their released configurations on the same PCPNet split. PFF-Net reports 9.38 average normal-angle RMSE on PCPNet and 16.95 on FamousShape. AdaFit reports 5.19 on noise-free PCPNet. CMG-Net reports average Chamfer normal distance 8.87 on SceneNN and 16.23 under 1.2% noise. These are the numbers to meet or beat.

A selector over cheap PCA fits may well not beat PFF-Net in absolute RMSE. The fair head-to-head is therefore our selector run over a DeepFit base estimator, compared with DeepFit at its default patch, AdaFit and PFF-Net under equal training data and an equal hyperparameter-search budget. Beating PFF-Net's 9.38 average would be a clear win. Closing more than half of the oracle gap over the base estimator's default patch, with fewer parameters than PFF-Net's 2.03M, would be the minimum result worth reporting.

Nesti-Net-style classifier. This is the scale-classification baseline. The same scorer architecture is trained with cross-entropy on the index of the oracle-best radius over the same ladder. It isolates "supervise the winner" from "supervise the ordering."

Ablations. These isolate the two ingredients of the loss on an identical architecture and budget:

  • regression term only ($\lambda = 0$);
  • ranking term only (no anchor);
  • hybrid loss with a fixed hand-tuned $\delta$ in place of the bootstrap threshold.

Why not just…?

Why not just let attention over scales learn end to end, as CMG-Net does? This is the most serious threat. End-to-end training optimizes the final normal directly, which our two-stage target construction does not. The evidence against it is indirect. Nesti-Net found explicit specialization better than mixing under high noise, and implicit attention yields no per-point confidence. We settle the question by giving the end-to-end attention baseline the same radius ladder and base fits and comparing RMSE, especially on edge and high-noise points. If attention matches us on accuracy, our remaining contribution is the calibrated confidence, and the paper will say so.

Why not just classify the best radius? Classification treats the second-best radius, often nearly tied with the best, as just as wrong as a terrible one, and it produces no error estimate. The Nesti-Net-style classifier baseline measures this directly through the gap to the oracle. Our tie-aware threshold should help most where neighboring radii are nearly equivalent, which a classifier handles arbitrarily.

Why not just regress the per-radius error and take the argmin? This is the $\lambda = 0$ ablation. Ranking work in recommendation and search (Heterogeneous Loss, Temporal Relational Ranking for Stock Prediction) argues that pointwise losses blur close competitors. That argument applies here precisely near the minimum of the error curve. If regression alone closes the oracle gap as well as the hybrid does, the ranking term is unnecessary, and we will report it that way.

Why not just use a global spectral method like LEGO? LEGO targets tangent spaces on manifolds through a global eigendecomposition and has its own spectral parameters. Global low-frequency eigenvectors are a poor fit for the thin-wall separations that STAR-Edge highlights. We will include LEGO on the synthetic manifold benchmarks it was designed for. No scalar result was found on Lacuna for LEGO, so we will run it ourselves at matched neighbor graphs.

Proposed Experiments

We train on the PCPNet benchmark's 8 training shapes and test on its 22 test shapes. Evaluation covers all four noise levels and both non-uniform density patterns. We then test zero-shot transfer to FamousShape and to SceneNN, using normal-angle RMSE and Chamfer normal distance as each prior paper does. The base estimators are PCA, jet and DeepFit, and NYU Depth V2 is used only for qualitative inspection.

Three checks decide the outcome.

The first is the oracle-gap ratio: the fraction of the gap between fixed-radius and oracle-radius error that each method closes. It is computed separately for edge points and flat points, with edge points identified from ground-truth normal discontinuity. The hybrid loss should close more of the gap on edge points than both the regression-only ablation and the classifier.

The second is calibration. We measure the Spearman correlation across test points between predicted minimum error and true error, and the area under the risk–coverage curve when points are discarded in order of predicted error. The hybrid loss should clearly beat the ranking-only model here, since a pure ranker's scores mean nothing across points.

The third is robustness of the tie threshold. Bootstrap-derived $\delta$ should be insensitive to $c$ over an order of magnitude, while a fixed $\delta$ degrades across noise levels. If this fails, the claim that geometry removes CliffRank's margin heuristic fails with it.

A negative outcome on the first check, together with a positive outcome on the second, would narrow the contribution to calibrated confidence for local geometry. That result is still useful, and it is reportable as such.