100 lines
3.6 KiB
Markdown
100 lines
3.6 KiB
Markdown
# vtk-0001: CWE-407 — O(C×npts²) linear dedup scan in vtkStaticCleanPolyData
|
||
# vtk-0002: CWE-407 — O(numPts×numLabels) linear label-set scan in vtkGeneralizedSurfaceNets3D
|
||
|
||
---
|
||
|
||
## vtk-0001
|
||
|
||
### Severity
|
||
HIGH
|
||
|
||
### File
|
||
`Filters/Core/vtkStaticCleanPolyData.cxx:257,293,343,403`
|
||
|
||
### Description
|
||
`vtkStaticCleanPolyData::RequestData()` deduplicates point IDs within each
|
||
cell using a `std::vector<vtkIdType> cellIds` maintained per cell. For each
|
||
point in the cell the code calls `std::find(cellIds.begin(), cellIds.end(),
|
||
ptId)` before appending to the vector. The pattern appears four times for
|
||
the four cell types: verts, lines, polys, and triangle strips.
|
||
|
||
The outer loop iterates over all C cells in the mesh. For each cell the
|
||
inner loop iterates npts times and each iteration does an O(k) linear scan
|
||
(where k grows from 0 to npts−1). Total cost per cell: O(npts²). Total
|
||
cost: O(C × npts²).
|
||
|
||
For a triangulated surface with C = 10 000 000 triangles this is
|
||
O(C × 9) ≈ 90 M ops — manageable. But for strip-based or high-valence mesh
|
||
data (npts up to 64–256) the cost becomes O(C × npts²) = O(C × 65536) ops,
|
||
a 7 000× regression over the expected O(C × npts) cost.
|
||
|
||
The source comment even notes: "Just use a vector to keep track of unique
|
||
ids — it's a small set so find() will execute relatively fast." This is
|
||
only true when npts is always small, but VTK processes arbitrary meshes.
|
||
|
||
### Root Cause
|
||
`cellIds` is a `std::vector<vtkIdType>`. Deduplication via linear scan is
|
||
O(k) per point. Replacing with `std::unordered_set<vtkIdType>` reduces the
|
||
membership test to O(1) amortized, cutting deduplication from O(npts²) to
|
||
O(npts) per cell.
|
||
|
||
### Fix
|
||
Replace `std::vector<vtkIdType> cellIds` with `std::unordered_set<vtkIdType>
|
||
seenIds` for the dedup check; accumulate the insertion-ordered result in a
|
||
separate `std::vector` only when building the output cell.
|
||
|
||
### Speedup
|
||
At npts = 64 (strip with 64 points): 64²/64 = 64× per cell.
|
||
At npts = 256: 256× per cell.
|
||
Asymptotic: O(C × npts²) → O(C × npts).
|
||
|
||
### Affected Operations
|
||
- `vtkStaticCleanPolyData::RequestData()` — used as a preprocessing step
|
||
before virtually every VTK geometry pipeline (surface nets, voronoi,
|
||
ghost-cell generation, smoothing, etc.)
|
||
|
||
---
|
||
|
||
## vtk-0002
|
||
|
||
### Severity
|
||
HIGH
|
||
|
||
### File
|
||
`Filters/Meshing/vtkGeneralizedSurfaceNets3D.cxx:1150`
|
||
|
||
### Description
|
||
When no explicit labels are provided, `RequestData()` collects the unique
|
||
set of region IDs by iterating all numPts point scalars and calling
|
||
`std::find(autoLabels.begin(), autoLabels.end(), regionId)` before
|
||
appending to `autoLabels`:
|
||
|
||
```cpp
|
||
for (vtkIdType i = 0; i < numPts; ++i) {
|
||
double regionId = static_cast<double>(regions->GetValue(i));
|
||
if (regionId >= 0 &&
|
||
std::find(autoLabels.begin(), autoLabels.end(), regionId) == autoLabels.end())
|
||
{
|
||
autoLabels.push_back(regionId);
|
||
}
|
||
}
|
||
```
|
||
|
||
Cost: O(numPts × numLabels). For a 50 M-point segmentation volume with
|
||
200 tissue classes: 50M × 200 = 10^10 comparisons where O(numPts) suffices.
|
||
|
||
### Root Cause
|
||
`autoLabels` is a `std::vector<double>`. The uniqueness check is a linear
|
||
scan. An `std::unordered_set<double>` provides O(1) membership.
|
||
|
||
### Fix
|
||
Use `std::unordered_set<double>` for the existence check during collection,
|
||
then move the sorted result into a vector if ordering is needed.
|
||
|
||
### Speedup
|
||
At numPts = 50 000 000, numLabels = 200: 200× speedup.
|
||
Asymptotic: O(numPts × numLabels) → O(numPts).
|
||
|
||
### Affected Operations
|
||
- `vtkGeneralizedSurfaceNets3D::RequestData()` — called when processing
|
||
multi-label segmentation volumes (medical imaging, simulation data)
|