Appendix: Convergence of the Next-Best-View Stopping Criterion

This appendix analyzes the criterion by which the next-best-view (NBV) inspection loop decides that a target has been sufficiently reconstructed and halts. The treatment is grounded in the implementation (the nbv_cpp scorer and the sample_nbv_behaviors behaviors SetViews, GetBestView, GetBestViewWithCost, and CheckScoreSaturation); each claim is scoped to what that implementation guarantees rather than to an idealized model. Code references are given as file:line.

---

Notation

---

1. The Information-Gain Score

For each candidate view $j$, the server ray-casts the view frustum into the TSDF and counts voxels (next_best_view.cpp:374):

$$\mathrm{IG}_j = \bigl|\{\text{unique ROI voxels reached by view } j\text{'s rays that are unknown or rear-side}\}\bigr|.$$

Each ray is walked (Amanatides-Woo) until the first surface crossing (next_best_view.cpp:456); a voxel is counted if and only if it lies inside the ROI and (next_best_view.cpp:470) is either

• unknown (weight_ == 0, never integrated), or
• rear-side (tsdf_ < 0, behind a surface or interior).

Voxels are de-duplicated across rays, so $\mathrm{IG}_j$ measures distinct still-uninformed volume the view can see rather than a ray count. It is a visibility-coverage proxy: how much unseen or interior volume the view can reach before being occluded.

The blackboard score is the fraction, normalized by the constant total grid size $V=\texttt{getNumVoxels()}$ (nbv_server.cpp:451):

$$s_{k,j} = \frac{\mathrm{IG}_j}{V}\in[0,1].$$

Since $V$ is fixed for a given target, this normalization is a pure rescaling and affects no monotonicity argument. After each executed view, SetViews re-scores all surviving candidates against the updated TSDF.

---

2. Monotonicity: An Idealization, Not a Guarantee

The clean contraction picture requires $\mathrm{IG}$ to be a monotone submodular set function. This holds only in an idealized model, namely coverage of a fixed unknown volume under known visibility, in which a survivor's score never rises between cycles:

$$s_{k+1,j}\le s_{k,j}\qquad(\text{idealized submodular regime}).$$

The implemented scorer satisfies this only approximately. Decomposing the count:

• The unknown term (weight_ == 0) is monotone: an observed voxel never reverts to unknown, and the per-view de-duplication (§1) prevents one voxel from inflating the count across rays (the multi-counting that classically breaks submodularity).
• The surface-termination term is not provably monotone. The truncating zero-crossing is a running weighted average, so in principle an early phantom surface can erode under later measurements, allowing a survivor's rays to penetrate farther and re-count, i.e. $s_{k+1,j} > s_{k,j}$. This requires a transient mis-estimate to reverse, so it is unlikely to materially move $m_k$ in practice, but it cannot be excluded.

Consequently $\mathrm{IG}$ (hence $s_{k,j}$ and the per-cycle maximum $m_k$) is dominantly, and almost always in practice, monotone, but not provably so. The clean contraction is an idealization on which the system does not rely.

The implemented criterion reflects this. The convergence node uses a running maximum (peak_ = std::max(peak_, curr_max), check_score_saturation.cpp:50) and a patience debounce (check_score_saturation.cpp:60-66). Were $m_k$ guaranteed monotone, peak_ would always equal $m_0$ (making the running maximum redundant) and a single dip below $\varepsilon$ would be permanent (making patience unnecessary). Both mechanisms exist precisely because $m_k$ can be exceeded by a later value.

---

3. The Score Vector and Its Norms

At cycle $k$ the $N_k$ surviving candidates form the vector $\mathbf{s}_k=(s_{k,1},\dots,s_{k,N_k})$. Two candidate stopping functionals arise:

• Sum ($\ell_1$): $\|\mathbf{s}_k\|_1=\sum_j s_{k,j}$
• Max ($\ell_\infty$): $\|\mathbf{s}_k\|_\infty=\max_j s_{k,j}=:m_k$

By norm equivalence, $\|\mathbf{s}_k\|_\infty \le \|\mathbf{s}_k\|_1 \le N_k\,\|\mathbf{s}_k\|_\infty$, where the relating constant is the candidate count $N_k$. Oversampling the viewpoint manifold (for example a dense helix or cone) inflates $N_k$, so the sum grows with discretization density while the maximum is invariant to it. The $\ell_\infty$ functional is therefore the scale- and density-invariant progress measure; the $\ell_1$ functional is not.

---

4. Greedy Selection Realizes the Infinity Norm

In pure NBV, GetBestView (get_best_view.cpp:39) selects and executes the IG-maximizing candidate:

$$j^\star_k=\arg\max_j s_{k,j},\qquad m_k = s_{k,j^\star_k}=\|\mathbf{s}_k\|_\infty.$$

Evaluating the greedy step is thus identical to evaluating the $\ell_\infty$ norm: the objective and the stopping functional are the same quantity, so monitoring $m_k$ tracks exactly the value the policy captures each cycle. This self-consistency is a property of pure greedy selection, and is precisely what the cost-informed variant breaks (§7).

---

5. The Convergence Metric

The loop monitors the peak remaining gain $m_k$, normalized by the running peak $P_k=\max_{i\le k}m_i$ (rather than by the initial value $m_0$):

$$\rho_k=\frac{m_k}{P_k}\in[0,1],\qquad \text{halt when } \rho_k<\varepsilon \text{ on } p \text{ consecutive cycles (patience, §5.1).}$$

Here $\varepsilon$ is a relative tolerance, interpreted as a fraction of peak informativeness, and $p$ is the patience parameter.

Why the peak gain decays. Each cycle applies two operations to the score vector, on different footing:

• Prune (unconditional). The executed view $j^\star_k$ is removed, and removing an element cannot raise a maximum (the maximum over a subset is at most the maximum over the superset), for any removed index. This step is always monotone.
• Re-score (reliable but not provable). The survivors are re-scored against the enlarged observed set. Under submodularity (diminishing returns) no view's marginal gain rises, so $s_{k+1,j}\le s_{k,j}$. The TSDF recompute can in principle violate this (§2, surface revision), but only through a transient mis-estimate, so in practice it almost never raises a survivor.

Combining the two,

$$m_{k+1}=\max_{j\ne j^\star_k}s_{k+1,j}\;\le\;\max_{j\ne j^\star_k}s_{k,j}\;\le\; m_k,$$

so $\rho_k$ decays. The prune half is guaranteed; the re-score half holds in all but pathological TSDF transients. The running peak $P_k$ and the patience window (§5.1) absorb those rare excursions, and pool exhaustion (§5.2) supplies the one guarantee that needs no assumption at all.

Analytical character. The metric is a debounced approximate non-expansion rather than a Banach contraction. The per-step factor $\gamma_k=m_k/m_{k-1}$ is geometry-dependent, not a uniform modulus below 1. The telescoping identity $\rho_k=\prod_i\gamma_i$ holds only while $m_k$ is non-increasing; a rare re-score excursion can drive $\gamma_k>1$, which $P_k$ absorbs ($\rho_k$ resets to 1 at a new peak), so $\rho_k\in[0,1]$ throughout but is not itself monotone.

5.1 Patience

Saturation requires $\rho_k<\varepsilon$ on $p$ consecutive cycles, the crossing cycle included (check_score_saturation.cpp:60-66; the patience port, default 2; lowercase $p$, distinct from the running peak $P_k$). Let $c$ be the first cycle with $\rho_c<\varepsilon$. Because below_count_ is incremented on cycle $c$ itself, the crossing is confirmation 1, and the stop occurs at

$$k^\star = c + (p-1).$$

The $p-1$ cycles beyond the crossing are the debounce overhead; setting $p=1$ recovers the eager rule that stops at $c$. This count assumes $\rho_k$ remains below $\varepsilon$ throughout the window. Under the non-strictly-monotone signal of §2, an upward excursion resets below_count_ to 0 (check_score_saturation.cpp:62-63) and the count restarts, so $p-1$ is the minimum overhead and the patience window performs genuine noise rejection.

5.2 The Assumption-Free Guarantee: Pool Exhaustion

Each cycle removes exactly one candidate ($N_{k+1}=N_k-1$), so the loop halts within $N_0$ cycles irrespective of monotonicity, and no sequence of patience resets (§5.1) can prevent termination. Saturation is therefore an early-stop layered on this hard bound, never a prerequisite for halting. The practical payoff of the normalization is portability: $\varepsilon$ expresses a fraction of peak informativeness that carries the same meaning across targets and pool sizes.

---

6. The Infinity-Norm Rule Stops No Later Than the Sum Rule

This section assumes pure greedy selection and the submodular regime of §2.

Marginal progress of each rule. Let $\Delta_k := S_k - S_{k+1}$ be the decrement of the sum produced by cycle $k$'s observation, with $S_k=\|\mathbf{s}_k\|_1$. It splits into the removed view plus the re-scoring of the survivors:

$$\Delta_k \;=\; \underbrace{s_{k,j^\star_k}}_{\text{removed view}} \;+\; \underbrace{\sum_{j\ne j^\star_k}\bigl(s_{k,j}-s_{k+1,j}\bigr)}_{\text{drift}_k \,\ge\, 0}.$$

For pure greedy, $j^\star_k=\arg\max_j s_{k,j}$, so the removed view is the maximum, $s_{k,j^\star_k}=m_k$, giving $\Delta_k = m_k + \text{drift}_k \ge m_k$.

Two stopping rules at a common tolerance. Normalizing both marginal-progress measures by the running peak $P_k$ (the §5 normalizer) lets $\varepsilon$ serve as a single relative tolerance. Each rule fires at the first cycle its peak-normalized measure drops below $\varepsilon$:

$$k^\star_\infty = \min\{k : \rho_k < \varepsilon\}, \qquad k^\star_1 = \min\{k : \Delta_k/P_k < \varepsilon\}, \qquad \rho_k=\tfrac{m_k}{P_k}.$$

The $\ell_\infty$ rule is exactly the convergence test of §5.

Ordering by set inclusion. Since $\text{drift}_k\ge0$, dividing $\Delta_k=m_k+\text{drift}_k$ by $P_k$ gives $\Delta_k/P_k\ge\rho_k$, hence $\Delta_k/P_k<\varepsilon \Rightarrow \rho_k<\varepsilon$. The $\ell_1$ stop-set is therefore contained in the $\ell_\infty$ stop-set, and the minimum over a subset is no smaller than the minimum over its superset:

$$\{k:\Delta_k/P_k<\varepsilon\}\subseteq\{k:\rho_k<\varepsilon\} \quad\Longrightarrow\quad \boxed{\,k^\star_\infty \le k^\star_1\,}$$

The difference is a wasted tail: cycles spent waiting for $\text{drift}_k\sim O(N_k\delta)$ to bleed off after the best remaining view has already collapsed. The sum rule is worst in over-sampled scenes, where this drift is largest, while the max rule incurs no such penalty.

The result carries the usual caveats: the bound is weak ($\le$); strictness requires $\text{drift}>0$; both rules require submodularity, which a rare re-score excursion can locally violate (§2); and the identity $s_{k,j^\star_k}=m_k$ holds only for pure greedy, since under CI-NBV the removed view is sub-maximal (§7).

---

7. The Cost-Informed Case (CI-NBV)

GetBestViewWithCost (get_best_view_with_cost.cpp:64-99) replaces the IG-maximizing selection with a utility maximization over the feasible set $F_k=\{j:c_{k,j}<\infty\}$ (the views with finite Dubins cost from the live pose), with each objective min-max normalized over $F_k$:

$$u_{k,j}=(1-\alpha)\,\widetilde{\mathrm{IG}}_j-\alpha\,\tilde c_j,\qquad j^\star_k=\arg\max_{j\in F_k}u_{k,j},$$

falling back to $\arg\max_j s_{k,j}$ when $F_k=\varnothing$.

7.1 The $\ell_\infty$ self-consistency is lost. For $\alpha>0$, $j^\star_k$ is the utility maximizer, in general not the IG maximizer, so the identity of §4 degrades to

$$m_k=\|\mathbf{s}_k\|_\infty \;\ge\; s_{k,j^\star_k}.$$

The executed view's gain is no longer the monitored quantity: the objective (utility) and the stopping functional (maximum IG) are now distinct functionals on the same vector.

7.2 The metric is policy-agnostic; the full-set maximum stays monotone. Selection is upstream: $j^\star_k=\arg\max_{j\in F_k}u_{k,j}$ is fixed first, after which the survivor set $F_k\setminus\{j^\star_k\}$ is re-scored. Monotonicity then follows in two stages:

$$m_{k+1}=\max_{j\ne j^\star_k}s_{k+1,j}\;\underbrace{\le}_{\text{re-score}}\;\max_{j\ne j^\star_k}s_{k,j}\;\underbrace{\le}_{\text{prune}}\;\max_j s_{k,j}=m_k.$$

The prune inequality is where care is needed; the survivor maximum relates to $m_k$ by two cases:

• Case A (utility pick $\ne$ IG-max, the general case): the highest-IG view remains in the survivor set, so $\max_{j\ne j^\star_k}s_{k,j}=m_k$ (equality).
• Case B (utility pick $=$ IG-max, the coincidence): the peak entry is the one removed, so $\max_{j\ne j^\star_k}s_{k,j}<m_k$ (strict).

Writing $=m_k$ would silently assume Case A, i.e. that the cost-aware policy never selects the IG-max, which CI-NBV does not guarantee; the inequality covers both. The re-score inequality is the submodular drift of §5 (survivors fall, barring the rare transient of §2).

Monotonicity therefore arises from a shrinking set together with submodular re-scoring, not from the policy removing the maximum, and holds identically for NBV and CI-NBV. The convergence metric of §5 transfers to CI-NBV unchanged.

7.3 What changes is the rate, not the validity. Pure greedy removes the top component each step (an active contraction). CI-NBV removes a sub-maximal view, so $m_k$ decays only through passive submodular drift until the expensive view eventually becomes utility-best, or until $F_k$ empties and the fallback fires. Convergence reaches the same place and remains monotone, but generically takes more cycles; the "stops no later" advantage of §6 is a property of the $\alpha=0$ case.

7.4 No repair is needed, and reachability is rejected as a metric. Termination remains a pure-information question over the full candidate set; cost enters only the selection. A reachable-set variant $m_k^{\mathrm{reach}}=\max_{j\in F_k}s_{k,j}$ is rejected because feasibility is pose-dependent and re-evaluated every cycle, so $F_k$ changes continually. Such a variant would (i) destroy monotonicity, since a high-IG view re-entering $F_k$ raises the maximum over a changing index set, and (ii) couple termination to transient kinematics, risking false convergence when informative views are momentarily unreachable. Convergence is a statement about the information state, which is pose-independent; reachability and cost govern routing, never sufficiency.

7.5 The lingering-view effect is correct conservatism, not a defect. An expensive or unreachable high-IG view keeps $m_k$ high and defers the early stop, which is appropriate: if substantial information remains anywhere, the target has not converged. The effect is bounded ($\le N_0$) and self-resolving, since such a view's gain usually decays through incidental observation, and once $F_k$ empties the fallback selects it and DubinsClient (ForceSuccess-wrapped) drives through. The only residual cost is a drift toward exhaustive coverage on pathological targets.

---

8. Summary

The information gain is a visibility-coverage proxy that is dominantly, but not provably, monotone. The convergence metric is correspondingly a running-peak-normalized, patience-debounced approximate non-expansion, with pool exhaustion as its only assumption-free guarantee. Under pure greedy selection the maximum-based rule is self-consistent with the policy and stops no later than a sum-based rule. The cost-informed variant leaves the metric valid and monotone but no longer policy-driven: cost reshapes which view is visited, never whether the target is complete.