Skip to content

Preserve float weight ordering in maximum spanning trees - #4928

Merged
sarlinpe merged 2 commits into
colmap:mainfrom
aswanth-07:fix/max-spanning-weight-order
Oct 31, 2026
Merged

sarlinpe merged 2 commits into
colmap:mainfrom
aswanth-07:fix/max-spanning-weight-order

Conversation

@aswanth-07

Copy link
Copy Markdown
Contributor

ComputeMaximumSpanningTree subtracts each float weight from the maximum before running Kruskal's algorithm. That subtraction can round distinct weights to the same value, so the result depends on edge insertion order and can select the lower-weight tree. For example, a triangle with weights 1.0f, 0.1f and the next float above 0.1f loses the ordering between its two smaller edges.

Negate the weights instead, as the interface already describes. Negation preserves finite float ordering without an offset or precision loss. The minimum-spanning-tree path, roots and disconnected-component handling stay unchanged, and the maximum-weight scan is removed.

The new native regression checks all six edge permutations. It fails in three permutations on pristine main and passes with the fix. All four native spanning-tree cases pass. An independent native oracle passes 216 weight/permutation/root combinations; 5,400 ordinary min/max tree controls match pristine output exactly. Clang-format, Clang-Tidy and whitespace checks pass.

I did not run full reconstruction datasets, GPU builds or other operating systems locally.

AI assistance disclosure: AI-assisted development tools were used during investigation and implementation. The reported tests were run against the final diff.

@aswanth-07
aswanth-07 marked this pull request as ready for review October 30, 2026 22:22
@sarlinpe sarlinpe added the full-ci Run Windows and remaining pycolmap CI label Oct 31, 2026

@sarlinpe sarlinpe left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thank you!

@sarlinpe
sarlinpe enabled auto-merge (squash) October 31, 2026 14:26
@sarlinpe
sarlinpe merged commit 8007d1a into colmap:main Oct 31, 2026
16 checks passed
fringehush-gif added a commit to fringehush-gif/colmap that referenced this pull request Nov 3, 2026
Integrate thirteen official upstream commits after the private GPU cleanup
checkpoint. Preserve blocking host-sync selection and its CUDA 12.0/12.1
flag boundary while adopting upstream's generalized compute-capability
helper and LoMa/FlexGlue callers. Keep both capability and policy tests;
remove the duplicate colmap_util_cuda link from automatic composition.

Includes upstream rig-frame covisibility, thin bitmap thumbnails, visibility
coordinate conversion, row-wise warp dispatch, benchmark fixes, FlexGlue,
review guidance, and the Windows non-GUI SIFT-test build fix.

Validation at this private checkpoint: merge conflicts resolved in cuda.cc,
cuda.h, cuda_test.cc; source search found no remaining old BF16-helper call;
git diff --check passed. Native merged-source qualification and independent
exact-diff review remain pending. Prior GPU tests qualify their pinned source,
not this entire merged product. No reconstruction or performance claim.

AI-assisted integration. Existing published history is preserved.

## Upstream commits

- `e52aa8ee12ef58eb1cd16ada2be9316fa1c02cd3` Move pycolmap macOS CI from macos-14 to macos-15 runner (colmap#4933)
- `8007d1a51ae0c0af87fff3ebd204cf4698df7565` Preserve float weight ordering in maximum spanning trees (colmap#4928)
- `dd84102ef5e75fc17e20da281d2fc2fee5aca6a9` Bump pypa/gh-action-pypi-publish from 1.14.2 to 1.14.3 in /.github/workflows (colmap#4942)
- `721e185ddb6205b85fddc39ccf0774567f6be6ed` Add FlexGlue feature matcher (colmap#4908)
- `d0a411f2a9af139b5ea8118d64e5da5b70c6a890` FlexGlue: cache the dense features on the GPU (colmap#4915)
- `105817b6299cf22144fbbf39f95689681352476d` Hoist camera model dispatch per row in image warps (colmap#4935)
- `27ffad4388ce5647df3ea9e547bf8e1ea155fbcd` Make benchmark translation-angle errors invariant to reconstruction scale (colmap#4932)
- `e8f3522b936882cbceae074a19fca58fe378d323` Resolve benchmark paths before changing subprocess directories (colmap#4931)
- `f664d5d219230c1f1ebf9c2c7ecdcafc451b95ce` Clamp visibility coordinates before unsigned conversion (colmap#4943)
- `138119b7640d46f1f51fe329694a9ddae3ae0908` Keep thin bitmap thumbnails nonempty (colmap#4927)
- `b16ed5f97fa405ff2462745f9509386a9ebe6ece` Count rig frame covisibility once per 3D point (colmap#4893)
- `93dbbcb7f3019da30bd4a2c72753421e6cb85b45` Add colmap-review agent skill for code review (colmap#4934)
- `2a6f6955ed73a3d15b2a75edede5750e7c7b3304` Fix sift_test build on MSVC without the GUI (colmap#4955)
fringehush-gif added a commit to fringehush-gif/colmap that referenced this pull request Nov 4, 2026
Integrate thirteen official upstream commits after the private GPU cleanup
checkpoint. Preserve blocking host-sync selection and its CUDA 12.0/12.1
flag boundary while adopting upstream's generalized compute-capability
helper and LoMa/FlexGlue callers. Keep both capability and policy tests;
remove the duplicate colmap_util_cuda link from automatic composition.

Includes upstream rig-frame covisibility, thin bitmap thumbnails, visibility
coordinate conversion, row-wise warp dispatch, benchmark fixes, FlexGlue,
review guidance, and the Windows non-GUI SIFT-test build fix.

Validation at this private checkpoint: merge conflicts resolved in cuda.cc,
cuda.h, cuda_test.cc; source search found no remaining old BF16-helper call;
git diff --check passed. Native merged-source qualification and independent
exact-diff review remain pending. Prior GPU tests qualify their pinned source,
not this entire merged product. No reconstruction or performance claim.

AI-assisted integration. Existing published history is preserved.

## Upstream commits

- `e52aa8ee12ef58eb1cd16ada2be9316fa1c02cd3` Move pycolmap macOS CI from macos-14 to macos-15 runner (colmap#4933)
- `8007d1a51ae0c0af87fff3ebd204cf4698df7565` Preserve float weight ordering in maximum spanning trees (colmap#4928)
- `dd84102ef5e75fc17e20da281d2fc2fee5aca6a9` Bump pypa/gh-action-pypi-publish from 1.14.2 to 1.14.3 in /.github/workflows (colmap#4942)
- `721e185ddb6205b85fddc39ccf0774567f6be6ed` Add FlexGlue feature matcher (colmap#4908)
- `d0a411f2a9af139b5ea8118d64e5da5b70c6a890` FlexGlue: cache the dense features on the GPU (colmap#4915)
- `105817b6299cf22144fbbf39f95689681352476d` Hoist camera model dispatch per row in image warps (colmap#4935)
- `27ffad4388ce5647df3ea9e547bf8e1ea155fbcd` Make benchmark translation-angle errors invariant to reconstruction scale (colmap#4932)
- `e8f3522b936882cbceae074a19fca58fe378d323` Resolve benchmark paths before changing subprocess directories (colmap#4931)
- `f664d5d219230c1f1ebf9c2c7ecdcafc451b95ce` Clamp visibility coordinates before unsigned conversion (colmap#4943)
- `138119b7640d46f1f51fe329694a9ddae3ae0908` Keep thin bitmap thumbnails nonempty (colmap#4927)
- `b16ed5f97fa405ff2462745f9509386a9ebe6ece` Count rig frame covisibility once per 3D point (colmap#4893)
- `93dbbcb7f3019da30bd4a2c72753421e6cb85b45` Add colmap-review agent skill for code review (colmap#4934)
- `2a6f6955ed73a3d15b2a75edede5750e7c7b3304` Fix sift_test build on MSVC without the GUI (colmap#4955)
fringehush-gif added a commit to fringehush-gif/colmap that referenced this pull request Nov 7, 2026
Refresh the experimental alternative with fork main while retaining its previous head as a parent. The resulting tree is exactly main plus the isolated shared-current-cost-cache deletion: one CUDA file, +1/-25.

## Change

Read the existing cost map directly during the ordered sampled-cost fold. Preserve current plane propagation, source packing, scheduling and fallback mathematics. The cache originates in custom a37c1c3, MVS: Reuse sampled current costs (GPU perf). The earlier alternative is retained through 8481f89; its original experiment was 8b1412f.

Historical Fountain11 photo+geometry at 3072 recorded 76.85 -> 78.82 seconds, one observation per arm, on the older revision. Retain this inconclusive/adverse observation with its earlier revision; current performance has not been measured. No performance experiment was reopened.

## Validation

- Exact candidate CUDA owner compiled with CUDA 13.2 for compute_86/sm_86. In a bounded retained-support context on RTX 3060, both matched targets passed all 13 selected cases: propagation, ordered source folding, checkpoint-HMM and paired-sweep preservation.
- Four complete inputs and four outputs matched across executables: 8,492,128 bytes per arm. Maps were finite with positive depth and checked ordered graph IDs. Complete witnesses use checkpoint_hmm=false; separate checkpoint tests cover both settings without full cross-executable true-mode witnesses.
- Direct owners, link maps and actual loaded providers were checked; managed jobs ended and released their bookings. Later host resize/warp changes have separate owner qualification. This is not a whole-branch build, reconstruction-quality, portability or current-performance result.

## Upstream commits carried forward

- e52aa8e Move pycolmap macOS CI from macos-14 to macos-15 runner (colmap#4933)
- 8007d1a Preserve float weight ordering in maximum spanning trees (colmap#4928)
- dd84102 Bump pypa/gh-action-pypi-publish from 1.14.2 to 1.14.3 in /.github/workflows (colmap#4942)
- 721e185 Add FlexGlue feature matcher (colmap#4908)
- d0a411f FlexGlue: cache the dense features on the GPU (colmap#4915)
- 105817b Hoist camera model dispatch per row in image warps (colmap#4935)
- 27ffad4 Make benchmark translation-angle errors invariant to reconstruction scale (colmap#4932)
- e8f3522 Resolve benchmark paths before changing subprocess directories (colmap#4931)
- f664d5d Clamp visibility coordinates before unsigned conversion (colmap#4943)
- 138119b Keep thin bitmap thumbnails nonempty (colmap#4927)
- b16ed5f Count rig frame covisibility once per 3D point (colmap#4893)
- 93dbbcb Add colmap-review agent skill for code review (colmap#4934)
- 2a6f695 Fix sift_test build on MSVC without the GUI (colmap#4955)
- 78cc729 Fix default prior_position_loss_scale to sqrt(chi2_95_3dof) (colmap#4936)
- 8653c6b Estimate two-view relative rotation covariance (colmap#4950)
- e1317dd FlexGlue: match keypoints in the resized descriptor input frame (colmap#4949)
- 3db6eb0 Extract ConvertPosePriorsToENU and skip pose priors without position (colmap#4937)
- 77cbe48 Store and estimate rotation covariances on PoseGraph (colmap#4951)
- 30a1a81 Support covariance whitening in CeresRotationAverager (colmap#4952)
- e6644e7 Fix -Wunused-result warning in ThreadPool::AddTask (colmap#4958)
- 5b6da88 Clear descriptor-index results for empty queries (colmap#4960)
- d1d92d9 Add COVARIANCE reweighting for Ceres rotation averaging (colmap#4953)
- 761d90d Enable covariance-weighted rotation averaging in global pipelines (colmap#4823)
- fdee2e1 Reuse the pose graph of GlobalPipeline in the component mappers (colmap#4912)

AI disclosure: Totally vibe coded
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

full-ci Run Windows and remaining pycolmap CI

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants