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: Point2D) = segment.line_intersection(&state.ray) {
106 let dot: f32 = (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: Vector2D = segment.to_vector();
111 state.normal = vector(-v.y, 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}
185