java-topology/docs/tickets/panda3d-0001-camera-display-regions-linear-find.md

panda3d-0001 — Camera::remove_display_region: std::find on small_vector

Project: panda3d/panda3d File: panda/src/pgraph/camera.cxx line 252 Severity: LOW-MEDIUM Status: PATCHED CWE: CWE-407 (Algorithmic Complexity — O(n) linear membership test; called per-region removal)

Description

Camera::remove_display_region() uses std::find over _display_regions, a small_vector<DisplayRegion *> (unsorted, pointer-equality):

void Camera::
remove_display_region(DisplayRegion *display_region) {
  DisplayRegions::iterator dri =
    std::find(_display_regions.begin(), _display_regions.end(), display_region);
  if (dri != _display_regions.end()) {
    _display_regions.erase(dri);
  }
}

This is called from DisplayRegion's destructor and from set_camera() on every camera reassignment (displayRegion.cxx lines 73 and 160). In scenes with many display regions per camera (split-screen rendering, render-to-texture pipelines, VR multi-eye setups) this is O(n) per removal.

When display regions are added and removed in a loop (e.g., cycling through 64 render targets in a deferred pipeline), the cumulative cost becomes O(n²).

Camera::add_display_region (line 241) is a plain push_back — no dedup guard — so _display_regions can contain many entries.

Fix

Replace small_vector<DisplayRegion *> with an unordered_set<DisplayRegion *> (or a pset<DisplayRegion *> using Panda3D's allocator). Membership test and removal both become O(1). Iteration order does not matter for this container (it is only used for tracking which regions share this camera).

See patch panda3d-0001-camera-display-region-unordered-set.patch.

Benchmark Results (Java simulation)

See defects/panda3d/unit/Panda3DTest.java.

Scenario	Slow (320K ops)	Fast (800 ops)	Speedup
camera remove-all N=800	0ms	0ms	400x
VR reassign N=800 x K=10	4ms	5ms	400x

Theoretical ops ratio: N/2 = 400× at N=800. Confirmed by benchmark.