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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
//! Where a ray crosses a solid's faces, from the exact geometry.
//!
//! [`Rays`] meshes the arena once. A ray's candidate faces are those with a mesh triangle within
//! twice the mesh deflection of it: a face's exact surface lies within the deflection of its mesh,
//! so no crossing is missed. On each, over the stretches of the ray that pass those triangles, the
//! line is intersected with the face's surface exactly, in closed form on a plane, cylinder, cone,
//! sphere and torus. A crossing counts where it lies inside the face and its `t` in the ray's
//! range. One crossing on an edge between two faces counts once, as does a ray that touches a
//! surface without crossing it.
use std::collections::BTreeMap;
use crate::{
boolean::{
classify::DIRECTIONS,
csi::curve_surface,
domain::{Domain, Where},
face_domain,
},
error::{Error, Result},
geom::{Curve, Line},
math::{Aabb, Point3, Vec3},
mesh::{
self, MeshOptions,
bvh::{Bvh, segment_triangle},
},
tol,
topo::{Brep, FaceId},
};
/// Where a ray crosses a face: `t` along its unit direction, the point, the face and the face's
/// outward normal there. `on_edge` where the point lies on the face's boundary: the ray passes
/// through an edge there, and the face next to it has a crossing at the same point.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Hit {
pub t: f64,
pub point: Point3,
pub face: FaceId,
pub normal: Vec3,
pub on_edge: bool,
}
/// The meshes tried, finest first: the mesher gives up on a very fine chord over a large part.
const MESHES: [MeshOptions; 3] = [
MeshOptions {
linear: 0.01,
angular: 0.2,
},
MeshOptions {
linear: 0.05,
angular: 0.5,
},
MeshOptions {
linear: 0.2,
angular: 0.8,
},
];
/// How far past the ends of its range a crossing may lie and still count, and how near the
/// surface a ray stays over a stretch it only grazes.
const ON: f64 = 0.01 * tol::LINEAR;
/// Where a point lies against an arena's solids.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Side {
Inside,
/// On the boundary, within the linear tolerance.
On,
Outside,
}
/// An arena prepared for casting rays at its faces: its mesh, a box tree over it, and each face's
/// trimmed domain on its surface.
pub struct Rays<'a> {
b: &'a Brep,
tris: Vec<(FaceId, [Point3; 3])>,
tree: Bvh,
deflection: f64,
domains: Vec<Domain>,
/// The mesh's box: the arena lies within the deflection of it.
reach: Aabb,
}
impl<'a> Rays<'a> {
pub fn new(b: &'a Brep) -> Result<Rays<'a>> {
let mut err = None;
let mut found = None;
for opt in MESHES.iter().map(|o| mesh::seeding(o, b)) {
match mesh::tessellate(b, &opt) {
Ok(m) => {
found = Some((m, opt));
break;
}
Err(e) => err = Some(e),
}
}
let Some((m, opt)) = found else {
return Err(err.expect("a mesh was tried"));
};
let tree = Bvh::new(&m);
let mut face_of = vec![None; m.triangles.len()];
for (f, range) in &m.faces {
for k in range.clone() {
face_of[k] = Some(*f);
}
}
let tris = m
.triangles
.iter()
.zip(face_of)
// The tree names triangles by index, so each keeps its place.
.map(|(t, f)| {
let f = f.expect("every mesh triangle lies in its face's range");
(f, t.map(|i| m.positions[i as usize]))
})
.collect();
let mut reach = Aabb::EMPTY;
for &q in &m.positions {
reach.add(q);
}
Ok(Rays {
b,
tris,
tree,
deflection: opt.linear,
domains: b.face_ids().map(|f| face_domain(b, f)).collect(),
reach,
})
}
/// Whether a solid of the arena holds `p`, by the parity of a ray's crossings of its faces: a
/// point in a void, or between solids, is held by none. A ray that passes through an edge,
/// grazes a face or starts on one does not say, and the next direction is tried. `None` where
/// none says: the point is on the boundary.
pub fn holds(&self, p: Point3) -> Option<bool> {
if self.tris.is_empty() {
return Some(false);
}
let far = self.reach.min.dist(p).max(self.reach.max.dist(p)) + self.reach.diagonal() + 1.0;
DIRECTIONS.iter().find_map(|d| {
let d = Vec3::from_array(*d).unit()?;
let hits = self.crossings(p, d, (0.0, far));
let unclear =
|h: &Hit| h.on_edge || h.t <= tol::LINEAR || h.normal.dot(d).abs() < tol::TANGENT;
(!hits.iter().any(unclear)).then_some(hits.len() % 2 == 1)
})
}
/// Where `p` lies against the arena's solids. A point no ray decides is one every ray leaves
/// through a face, an edge or a touch at its start: a point of the boundary.
pub fn side(&self, p: Point3) -> Side {
match self.holds(p) {
Some(true) => Side::Inside,
Some(false) => Side::Outside,
None => Side::On,
}
}
/// Every crossing of the ray `o + t·d` with the arena's faces for `t` in `[t0, t1]`, nearest
/// first, `t` measured along `d` made a unit.
pub fn cast(&self, o: Point3, d: Vec3, range: (f64, f64)) -> Result<Vec<Hit>> {
let Some(d) = d.unit() else {
return Err(Error::InvalidInput("a ray needs a direction".into()));
};
// Seeds from neighbouring triangles land on one crossing, and a crossing on an edge is on
// both its faces.
let mut hits = self.crossings(o, d, range);
hits.dedup_by(|later, kept| later.t - kept.t <= tol::LINEAR);
Ok(hits)
}
/// Every crossing of the ray, nearest first, a crossing on an edge once for each face.
///
/// The mesh says where to look, and no more: each face is searched over the stretches of the
/// ray that pass one of its triangles, and what is found there is every meeting of the line
/// with the face's exact surface, by the intersection the booleans use. A chord across a
/// curved face shallower than the mesh resolves is two crossings, as any other chord is.
fn crossings(&self, o: Point3, d: Vec3, (t0, t1): (f64, f64)) -> Vec<Hit> {
let pad = 2.0 * self.deflection;
let (s0, s1) = (t0 - pad, t1 + pad);
let mut near = Vec::new();
self.tree.along(o, d, (s0, s1), pad, &mut near);
let (a, z) = (o + d * s0, o + d * s1);
let mut stretches: BTreeMap<FaceId, Vec<(f64, f64)>> = BTreeMap::new();
for &k in &near {
let (f, tri) = &self.tris[k];
if segment_triangle(a, z, tri).0 > pad {
continue;
}
// The surface over this triangle lies within the deflection of it, so the ray can
// meet it only this far past the triangle's own reach along the ray.
let along = tri.map(|v| (v - o).dot(d));
let lo = along.iter().copied().fold(f64::INFINITY, f64::min) - pad;
let hi = along.iter().copied().fold(f64::NEG_INFINITY, f64::max) + pad;
stretches
.entry(*f)
.or_default()
.push((lo.max(s0), hi.min(s1)));
}
let line = Curve::Line(Line { origin: o, dir: d });
let mut hits: Vec<Hit> = Vec::new();
for (f, mut spans) in stretches {
spans.sort_by(|x, y| x.0.total_cmp(&y.0));
let mut merged: Vec<(f64, f64)> = Vec::new();
for (lo, hi) in spans {
match merged.last_mut() {
Some(last) if lo <= last.1 => last.1 = last.1.max(hi),
_ => merged.push((lo, hi)),
}
}
let face = self.b.face(f);
let s = &face.surface;
for span in merged {
// A ray that runs in the surface crosses it nowhere.
let found = curve_surface(&line, span, s);
for t in found.ts {
if t < t0 - ON || t > t1 + ON {
continue;
}
let q = o + d * t;
let dom = &self.domains[f.index()];
let (uv, on_edge) = match dom.locate(q) {
Where::Outside => continue,
Where::Inside(uv) => (uv, false),
Where::Boundary => (s.project(q), true),
};
hits.push(Hit {
t: t.clamp(t0, t1),
point: q,
face: f,
normal: dom.outward(uv),
on_edge,
});
}
}
}
hits.sort_by(|x, y| x.t.total_cmp(&y.t).then(x.face.cmp(&y.face)));
self.touches(hits, o, d)
}
/// `hits` with each run on one face that the ray stays on between, a ray grazing the surface,
/// as one touch. A grazing ray stays within [`ON`] of the surface over a stretch as long as
/// the square root of that over the curvature, so its seeds settle anywhere along it; the touch
/// is where the surface's normal turns square to the ray, which bisection finds exactly.
fn touches(&self, hits: Vec<Hit>, o: Point3, d: Vec3) -> Vec<Hit> {
let mut out: Vec<Hit> = Vec::with_capacity(hits.len());
let mut i = 0;
while i < hits.len() {
let h = hits[i];
let s = &self.b.face(h.face).surface;
let foot = |t: f64| {
let p = o + d * t;
let uv = s.project(p);
(uv, s.eval(uv.x, uv.y).dist(p))
};
let mut j = i;
while j + 1 < hits.len()
&& hits[j + 1].face == h.face
&& foot(0.5 * (hits[j].t + hits[j + 1].t)).1 <= ON
{
j += 1;
}
if j == i {
out.push(h);
i += 1;
continue;
}
let square = |t: f64| {
let (uv, _) = foot(t);
s.normal(uv.x, uv.y).dot(d)
};
let (mut lo, mut hi) = (hits[i].t, hits[j].t);
if square(lo).signum() != square(hi).signum() {
for _ in 0..100 {
let mid = 0.5 * (lo + hi);
if square(mid).signum() == square(lo).signum() {
lo = mid;
} else {
hi = mid;
}
}
}
let t = 0.5 * (lo + hi);
let (uv, _) = foot(t);
let n = s.normal(uv.x, uv.y);
out.push(Hit {
t,
point: o + d * t,
face: h.face,
normal: if self.b.face(h.face).reversed { -n } else { n },
on_edge: hits[i..=j].iter().any(|x| x.on_edge),
});
i = j + 1;
}
out
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{
boolean,
math::{Frame, Vec2},
profile::{NamedSegment, Profile, ProfileLoop, Segment},
sweep::extrude,
sweep::{Helix, helix},
};
use std::f64::consts::{PI, TAU};
#[test]
fn a_ray_up_a_threaded_bore_meets_its_wall() {
// A hex nut 7.6 tall, bored 4 in radius, a 60° thread ridge of pitch 1.2 joined inside it
// for three turns from z = 2: the bore's wall left between the turns is a strip that winds
// three times round, and a ray from inside the bore must cross it or a flank to leave.
let seg = |segment, name: &str| NamedSegment::new(segment, name);
let d: f64 = 6.8;
let rc = 2.0 * d / 3f64.sqrt();
let hex: Vec<Vec2> = (0..6)
.map(|i| {
let a = PI / 3.0 * i as f64;
Vec2::new(rc * a.cos(), rc * a.sin())
})
.collect();
let mut nut_profile = Profile::polygon(&hex, &["a", "b", "c", "d", "e", "f"]);
nut_profile.loops.push(ProfileLoop {
segments: vec![seg(
Segment::Circle {
center: Vec2::ZERO,
radius: 4.0,
ccw: false,
},
"bore",
)],
});
let nut = extrude(&nut_profile, &Frame::WORLD, 7.6, "nut").unwrap();
let (pitch, major) = (1.2, 4.0);
let minor = major - 0.6134 * pitch;
let root = major + 0.1 * pitch;
let half = |x: f64| (x - minor) * (PI / 6.0).tan();
let tri = [
Vec2::new(root, 2.0 - half(root)),
Vec2::new(root, 2.0 + half(root)),
Vec2::new(minor, 2.0),
];
let ridge_profile = Profile {
loops: vec![ProfileLoop {
segments: (0..3)
.map(|i| {
seg(
Segment::Line {
a: tri[i],
b: tri[(i + 1) % 3],
},
"s",
)
})
.collect(),
}],
};
let motion = Helix {
origin: Point3::ZERO,
axis: Vec3::Z,
rise: pitch / TAU,
sign: 1.0,
};
let meridian = Frame::new(Point3::ZERO, -Vec3::Y, Vec3::X).unwrap();
let ridge = helix(&ridge_profile, &meridian, &motion, 3.0 * TAU, "hel").unwrap();
let threaded = boolean::union(&nut, &ridge).unwrap();
let rays = Rays::new(&threaded).unwrap();
let a = 72.7f64.to_radians();
let p = Point3::new(2.031 * a.cos(), 2.031 * a.sin(), 4.655);
let dir = Vec3::new(0.3713, 0.5347, 0.7591);
let hits = rays.cast(p, dir, (0.0, 1e6)).unwrap();
let first = hits
.first()
.expect("the ray leaves the bore through something");
assert!(
first.normal.dot(dir) < 0.0,
"the bore's first crossing enters the nut"
);
}
}