1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

use num::{PrimInt, Float, NumCast};
#[cfg(any(test, feature = "arbitrary"))]
use quickcheck::{Arbitrary, Gen};
use nalgebra::{Vector2, BaseFloat};
use partition::{Partition, Subdivide};


/// A partition of the unit quad [0, 1) × [0, 1)
#[derive(Copy, Clone, Debug, PartialEq, Hash, Eq)]
pub struct UnitQuad {
    scale: u8,
    offset: (u32, u32),
}

impl UnitQuad {
    /// Create a new `UnitQuad`
    ///
    /// This asserts that the offset is valid given the scale level.
    pub fn new(scale: u8, offset: (u32, u32)) -> UnitQuad {
        assert!(scale < 32); // Otherwise exponentiation will overflow
        let max_offset = 2.pow(scale as u32);
        assert!(offset.0 < max_offset && offset.1 < max_offset);
        UnitQuad { scale: scale, offset: offset }
    }

    /// Integer scale
    pub fn scale(&self) -> u8 { self.scale }

    /// Integer offset
    pub fn offset(&self) -> (u32, u32) { self.offset }

    /// Get coordinate within the partition from (u, v) coordinates
    pub fn coordinate<T: BaseFloat + NumCast + Float>(&self, coord: (T, T)) -> Vector2<T> {
        let (u, v) = coord;
        let width: T = self.width();
        Vector2::new(
            width * (<T as NumCast>::from(self.offset.0).unwrap() + u),
            width * (<T as NumCast>::from(self.offset.1).unwrap() + v),
        )
    }

    /// Center of the partitioned region
    pub fn center<T: BaseFloat + NumCast + Float>(&self) -> Vector2<T> {
        let half = NumCast::from(0.5).unwrap();
        self.coordinate((half, half))
    }

    /// Width of the partitioned region
    pub fn width<T: BaseFloat + NumCast + Float>(&self) -> T {
        Float::powi(<T as NumCast>::from(0.5).unwrap(), self.scale as i32)
    }
}

impl Subdivide for UnitQuad {
    fn subdivide(&self) -> Vec<UnitQuad> {
        [(0, 0), (0, 1), (1, 0), (1, 1)]
            .iter()
            .map(|&(di, dj)| {
                let (i, j) = self.offset;
                UnitQuad::new(self.scale + 1, (i * 2 + di, j * 2 + dj))
            })
            .collect()
    }
}

impl<T: BaseFloat + NumCast + Float> Partition<Vector2<T>> for UnitQuad
{
    fn contains(&self, elem: &Vector2<T>) -> bool {
        let width: T = self.width();
        let offset = Vector2::new(
            width * NumCast::from(self.offset.0).unwrap(),
            width * NumCast::from(self.offset.1).unwrap(),
        );
        (offset.x < elem.x) && (elem.x < offset.x + width) &&
        (offset.y < elem.y) && (elem.y < offset.y + width)
    }
}

#[cfg(any(test, feature = "arbitrary"))]
impl Arbitrary for UnitQuad {
    fn arbitrary<G: Gen>(g: &mut G) -> UnitQuad {
        use std::cmp;
        // FIXME: somehow this explicit usage of the `Rng` trait is required for
        // the `.gen_range` calls, even though `Rng: Gen`. The compiler
        // complains that the "source trait is private". Curiously, adding this
        // import here fixes the same situation in the `cubemap` module as well.
        use rand::Rng;
        let scale: u8 = {
            // scale >= 32 is invalid (overflow)
            // At scale >= 31 subdivision fails
            let max_scale = cmp::min(31, g.size()) as u8;
            g.gen_range(0, max_scale)
        };
        let max_offset = 2.pow(scale as u32);
        UnitQuad::new(scale, (
            g.gen_range(0, max_offset),
            g.gen_range(0, max_offset),
        ))
    }
}


#[cfg(test)]
mod test {
    pub use nalgebra::Vector2;
    pub use super::*;
    use quickcheck::{quickcheck, TestResult};
    use partition::Partition;

    partition_quickcheck!(unitquad_vec2_f32, UnitQuad, Vector2<f32>);
    partition_quickcheck!(unitquad_vec2_f64, UnitQuad, Vector2<f64>);

    #[test]
    fn unitquad_base_contains_region() {
        fn check(v: Vector2<f64>) -> TestResult {
            if v.x < 0.0 || v.x >= 1.0 || v.y < 0.0 || v.y >= 1.0 {
                TestResult::discard()
            } else {
                TestResult::from_bool(UnitQuad::new(0, (0, 0)).contains(&v))
            }
        }
        quickcheck(check as fn(Vector2<f64>) -> TestResult);
    }
}