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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

//! Various math tools that are mostly usefull for the tessellators.

use fixed;
use geom::math::*;
use path_fill::Edge;
use geom::euclid;
use std::f64;

pub type FixedPoint32 = fixed::Fp32<fixed::_16>;
pub type FixedPoint64 = fixed::Fp64<fixed::_16>;
pub type TessVector = euclid::Vector2D<FixedPoint32>;
pub type TessPoint = euclid::Point2D<FixedPoint32>;
pub type TessPoint64 = euclid::Point2D<FixedPoint64>;
#[inline]
pub fn fixed(val: f32) -> FixedPoint32 { FixedPoint32::from_f32(val) }

#[inline]
fn x_aabb_test(a1: FixedPoint32, b1: FixedPoint32, a2: FixedPoint32, b2: FixedPoint32) -> bool {
    let (min1, max1) = a1.min_max(b1);
    let (min2, max2) = a2.min_max(b2);
    min1 <= max2 && max1 >= min2
}

// TODO[optim]: This function shows up pretty high in the profiles.
pub(crate) fn segment_intersection(
    e1: &Edge, // The new edge.
    e2: &Edge, // An already inserted edge.
) -> Option<TessPoint> {

    // This early-out test gives a noticeable performance improvement.
    if !x_aabb_test(e1.upper.x, e1.lower.x, e2.upper.x, e2.lower.x) {
        return None;
    }

    if e1.upper == e2.lower || e1.upper == e2.upper || e1.lower == e2.upper || e1.lower == e2.lower {
        return None;
    }

    fn tess_point(x: f64, y: f64) -> TessPoint {
        TessPoint::new(FixedPoint32::from_f64(x), FixedPoint32::from_f64(y))
    }

    let a1 = F64Point::new(e1.upper.x.to_f64(), e1.upper.y.to_f64());
    let b1 = F64Point::new(e1.lower.x.to_f64(), e1.lower.y.to_f64());
    let a2 = F64Point::new(e2.upper.x.to_f64(), e2.upper.y.to_f64());
    let b2 = F64Point::new(e2.lower.x.to_f64(), e2.lower.y.to_f64());

    let v1 = b1 - a1;
    let v2 = b2 - a2;

    debug_assert!(v2.x != 0.0 || v2.y != 0.0, "zero-length edge");

    let v1_cross_v2 = v1.cross(v2);
    let a2_a1_cross_v1 = (a2 - a1).cross(v1);

    if v1_cross_v2 == 0.0 {
        return None;
    }

    let sign_v1_cross_v2 = v1_cross_v2.signum();
    let abs_v1_cross_v2 = f64::abs(v1_cross_v2);

    // t and u should be divided by v1_cross_v2, but we postpone that to not lose precision.
    // We have to respect the sign of v1_cross_v2 (and therefore t and u) so we apply it now and
    // will use the absolute value of v1_cross_v2 afterwards.
    let t = (a2 - a1).cross(v2) * sign_v1_cross_v2;
    let u = a2_a1_cross_v1 * sign_v1_cross_v2;
    if t >= 0.0 && t <= abs_v1_cross_v2 && u > 0.0 && u <= abs_v1_cross_v2 {

        // Snap intersections to the edge if it is very close.
        // This helps with preventing small floating points errors from
        // accumulating when many edges intersect at the same position.
        let threshold = 0.000_001;
        if 1.0 - t / abs_v1_cross_v2 < threshold {
            return Some(e1.lower);
        }
        if 1.0 - u / abs_v1_cross_v2 < threshold {
            return Some(e2.lower);
        }

        let res = a1 + (v1 * t) / abs_v1_cross_v2;

        let res = tess_point(res.x, res.y);
        // It would be great if the assertion below held, but it happens
        // to fail due to precision issues.
        // debug_assert!(res.y <= e1.lower.y && res.y <= e2.lower.y);
        if res != e1.upper && res != e2.upper
            && res.y <= e1.lower.y && res.y <= e2.lower.y {
            return Some(res);
        }
    }

    None
}

/// Compute a normal vector at a point P such that ```x ---e1----> P ---e2---> x```
///
/// The resulting vector is not normalized. The length is such that extruding the shape
/// would yield parallel segments exactly 1 unit away from their original. (useful
/// for generating strokes and vertex-aa).
/// The normal points towards the left side of e1.
///
/// v1 and v2 are expected to be normalized.
pub fn compute_normal(v1: Vector, v2: Vector) -> Vector {
    //debug_assert!((v1.length() - 1.0).abs() < 0.001, "v1 should be normalized ({})", v1.length());
    //debug_assert!((v2.length() - 1.0).abs() < 0.001, "v2 should be normalized ({})", v2.length());

    let epsilon = 1e-4;

    let n1 = vector(-v1.y, v1.x);

    let v12 = v1 + v2;

    if v12.square_length() < epsilon {
        return n1;
    }

    let tangent = v12.normalize();
    let n = vector(-tangent.y, tangent.x);

    let inv_len = n.dot(n1);

    if inv_len.abs() < epsilon {
        return n1;
    }

    n / inv_len
}

#[test]
fn test_compute_normal() {
    fn assert_almost_eq(a: Vector, b: Vector) {
        if (a - b).square_length() > 0.00001 {
            panic!("assert almost equal: {:?} != {:?}", a, b);
        }
    }

    assert_almost_eq(compute_normal(vector(1.0, 0.0), vector(0.0, 1.0)), vector(-1.0, 1.0));
    assert_almost_eq(compute_normal(vector(1.0, 0.0), vector(1.0, 0.0)), vector(0.0, 1.0));
}