rusting_engine 2.7.0

//! Front-to-back order for opaque draws.
//!
//! Opaque objects drawn nearest first let the depth test reject the
//! fragments they hide before shading them. Without an order, overdraw
//! depends on the order objects were created in, which can change from run
//! to run (for example meshes built on worker threads).

use std::collections::HashMap;
use std::hash::Hash;

/// Buckets per doubling of distance. Buckets grow with distance, so near
/// objects, which hide the most, sort finely, and far ones keep their mesh
/// order: meshes made one after another often share a vertex page and draw
/// in one call.
const BUCKETS_PER_DOUBLING: f32 = 2.0;
/// How far, in metres, the camera moves before the opaque order is sorted
/// again. Turning never needs a new sort: the order is by distance.
pub(crate) const RESORT_DISTANCE: f32 = 8.0;

/// Whether an order sorted from `sorted_at` still holds with the camera at
/// `eye`.
pub(crate) fn order_holds(sorted_at: [f32; 3], eye: [f32; 3]) -> bool {
    let squared: f32 = (0..3)
        .map(|axis| (eye[axis] - sorted_at[axis]).powi(2))
        .sum();
    squared < RESORT_DISTANCE * RESORT_DISTANCE
}

/// Distance bucket of each item, for a sort that draws batches front to
/// back. `items` holds each opaque object's batch key (objects with equal
/// keys draw as one instanced batch) and its distance from the camera. A
/// batch takes the bucket of its nearest member, so its members stay
/// together and the batch still draws once.
pub(crate) fn distance_buckets<K: Eq + Hash + Copy>(
    items: &[(K, f32)],
) -> Vec<u32> {
    let mut nearest = HashMap::<K, f32>::new();
    for &(key, distance) in items {
        let entry = nearest.entry(key).or_insert(distance);
        *entry = entry.min(distance);
    }
    items
        .iter()
        .map(|(key, _)| {
            (nearest[key].max(1.0).log2() * BUCKETS_PER_DOUBLING) as u32
        })
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn batches_sort_by_their_nearest_member_and_stay_together() {
        // Mesh 7 has a near and a far copy; mesh 3 sits in between.
        let items = [(7, 40.0), (3, 12.5), (7, 2.2), (9, f32::NAN)];
        let buckets = distance_buckets(&items);
        assert_eq!(buckets, [2, 7, 2, 0]);
        let mut order = [0, 1, 2, 3];
        order.sort_by_key(|&index| (buckets[index], items[index].0));
        assert_eq!(order, [3, 0, 2, 1]);
    }
}