RenderVisibleEntitiesClass::entity_pair_is_visible binary-searches with the wrong sort key

[wlgys8]

Bevy version

Bevy 0.19.0 and current main.

This is a regression from 0.18.1. The affected retained-visibility / pending-queue path was introduced during the 0.19 development cycle by #22966.

What went wrong

RenderVisibleEntitiesClass::entity_pair_is_visible can return false for an entity pair that is present in entities_cpu_culling.

The CPU-visible entity list is sorted by MainEntity:

render_view_entities
    .entities
    .sort_unstable_by_key(|(_, main_entity)| *main_entity);

However, entity_pair_is_visible performs a binary search using the full (Entity, MainEntity) tuple:

self.entities_cpu_culling
    .binary_search(&(entity, main_entity))
    .is_ok()

Tuple ordering compares Entity first, so this binary search requires the list to be sorted by (Entity, MainEntity). That invariant does not hold: the list is sorted only by MainEntity. As a result, the lookup depends on the unrelated render-entity ID ordering and can produce false negatives.

Minimal regression test

The following test constructs a list that is correctly sorted by MainEntity, but deliberately has the opposite Entity ordering:

#[test]
fn cpu_visible_entity_pair_lookup_uses_main_entity_sort_order() {
    use bevy_ecs::world::World;

    let mut world = World::new();

    let main_a = MainEntity::from(world.spawn_empty().id());
    let main_b = MainEntity::from(world.spawn_empty().id());

    let render_low = world.spawn_empty().id();
    let render_high = world.spawn_empty().id();

    // This is the ordering guaranteed by the visibility system: MainEntity order.
    // It is intentionally not sorted by the full (Entity, MainEntity) tuple.
    let pairs = [(render_high, main_a), (render_low, main_b)];

    let mut visible = RenderVisibleEntitiesClass::default();
    visible.update_cpu_culled_entities(&pairs);

    assert!(visible.entity_pair_is_visible(render_high, main_a));
    assert!(visible.entity_pair_is_visible(render_low, main_b));
}

At least one assertion fails with 0.19.0 and current main, even though both pairs are present.

Impact

DirtySpecializations::iter_to_specialize uses entity_pair_is_visible to retain entries from the previous frame's pending specialization queue. A false negative drops a still-visible pending entity. If that entity is no longer newly visible or otherwise dirty on a later frame, it is not retried after its mesh or material becomes ready, so it can remain absent from the specialized pipeline cache until an unrelated dirty event occurs.

This makes asynchronously prepared meshes or materials susceptible to intermittent missing draws based on entity ID allocation order.

Suggested fix

Search entities_cpu_culling by MainEntity, matching the key used to sort it, and then verify that the render Entity at the matched entry is the expected one. Sorting by the full tuple instead would conflict with the MainEntity-ordered diff logic.

For example, conceptually:

self.entities_cpu_culling
    .binary_search_by_key(&main_entity, |(_, main_entity)| *main_entity)
    .is_ok_and(|index| self.entities_cpu_culling[index].0 == entity)

A regression test should cover mismatched render-entity and main-entity ordering.

Related

#24984 removed a related pending-queue visibility filter from iter_to_queue, but iter_to_specialize still calls entity_pair_is_visible, and the inconsistent binary search remains in RenderVisibleEntitiesClass itself.