lyon_algorithms/
raycast.rs

1//! Find the first collision between a ray and a path.
2
3use crate::geom::{CubicBezierSegment, Line, LineSegment, QuadraticBezierSegment};
4use crate::math::{point, vector, Point, Vector};
5use crate::path::PathEvent;
6
7pub struct Ray {
8    pub origin: Point,
9    pub direction: Vector,
10}
11
12// Position and normal at the point of contact between a ray and a shape.
13pub struct Hit {
14    pub position: Point,
15    pub normal: Vector,
16}
17
18// TODO: early out in the bézier/arc cases using bounding rect or circle
19// to speed things up.
20
21/// Find the closest collision between a ray and the path.
22pub fn raycast_path<Iter>(ray: &Ray, path: Iter, tolerance: f32) -> Option<Hit>
23where
24    Iter: IntoIterator<Item = PathEvent>,
25{
26    let ray_len = ray.direction.square_length();
27    if ray_len == 0.0 || ray_len.is_nan() {
28        return None;
29    }
30
31    let mut state = RayCastInner {
32        ray: Line {
33            point: ray.origin,
34            vector: ray.direction,
35        },
36        min_dot: f32::MAX,
37        result: point(0.0, 0.0),
38        normal: vector(0.0, 0.0),
39    };
40
41    for evt in path {
42        match evt {
43            PathEvent::Begin { .. } => {}
44            PathEvent::Line { from, to } => {
45                test_segment(&mut state, &LineSegment { from, to });
46            }
47            PathEvent::End { last, first, .. } => {
48                test_segment(
49                    &mut state,
50                    &LineSegment {
51                        from: last,
52                        to: first,
53                    },
54                );
55            }
56            PathEvent::Quadratic { from, ctrl, to } => {
57                QuadraticBezierSegment { from, ctrl, to }.for_each_flattened(
58                    tolerance,
59                    &mut |line| {
60                        test_segment(&mut state, line);
61                    },
62                );
63            }
64            PathEvent::Cubic {
65                from,
66                ctrl1,
67                ctrl2,
68                to,
69            } => {
70                CubicBezierSegment {
71                    from,
72                    ctrl1,
73                    ctrl2,
74                    to,
75                }
76                .for_each_flattened(tolerance, &mut |line| {
77                    test_segment(&mut state, line);
78                });
79            }
80        }
81    }
82
83    if state.min_dot == f32::MAX {
84        return None;
85    }
86
87    if state.normal.dot(ray.direction) > 0.0 {
88        state.normal = -state.normal;
89    }
90
91    Some(Hit {
92        position: state.result,
93        normal: state.normal.normalize(),
94    })
95}
96
97struct RayCastInner {
98    ray: Line<f32>,
99    min_dot: f32,
100    result: Point,
101    normal: Vector,
102}
103
104fn test_segment(state: &mut RayCastInner, segment: &LineSegment<f32>) {
105    if let Some(pos) = segment.line_intersection(&state.ray) {
106        let dot = (pos - state.ray.point).dot(state.ray.vector);
107        if dot >= 0.0 && dot < state.min_dot {
108            state.min_dot = dot;
109            state.result = pos;
110            let v = segment.to_vector();
111            state.normal = vector(-v.y, v.x);
112        }
113    }
114}
115
116#[test]
117fn test_raycast() {
118    use crate::geom::euclid::approxeq::ApproxEq;
119    use crate::path::Path;
120
121    let mut builder = Path::builder();
122    builder.begin(point(0.0, 0.0));
123    builder.line_to(point(1.0, 0.0));
124    builder.line_to(point(1.0, 1.0));
125    builder.line_to(point(0.0, 1.0));
126    builder.end(true);
127    let path = builder.build();
128
129    assert!(raycast_path(
130        &Ray {
131            origin: point(-1.0, 2.0),
132            direction: vector(1.0, 0.0)
133        },
134        path.iter(),
135        0.1
136    )
137    .is_none());
138
139    let hit = raycast_path(
140        &Ray {
141            origin: point(-1.0, 0.5),
142            direction: vector(1.0, 0.0),
143        },
144        path.iter(),
145        0.1,
146    )
147    .unwrap();
148    assert!(hit.position.approx_eq(&point(0.0, 0.5)));
149    assert!(hit.normal.approx_eq(&vector(-1.0, 0.0)));
150
151    let hit = raycast_path(
152        &Ray {
153            origin: point(-1.0, 0.0),
154            direction: vector(1.0, 0.0),
155        },
156        path.iter(),
157        0.1,
158    )
159    .unwrap();
160    assert!(hit.position.approx_eq(&point(0.0, 0.0)));
161
162    let hit = raycast_path(
163        &Ray {
164            origin: point(0.5, 0.5),
165            direction: vector(1.0, 0.0),
166        },
167        path.iter(),
168        0.1,
169    )
170    .unwrap();
171    assert!(hit.position.approx_eq(&point(1.0, 0.5)));
172    assert!(hit.normal.approx_eq(&vector(-1.0, 0.0)));
173
174    let hit = raycast_path(
175        &Ray {
176            origin: point(0.0, -1.0),
177            direction: vector(1.0, 1.0),
178        },
179        path.iter(),
180        0.1,
181    )
182    .unwrap();
183    assert!(hit.position.approx_eq(&point(1.0, 0.0)));
184}
lyon_algorithms/raycast.rs

lyon_algorithms/
raycast.rs
