use super::*;
fn face_normal(face: &FaceRecord, u: f64, v: f64) -> Result<Vec3, String> {
let normal = match face.surface.normal(u, v) {
Ok(normal) => normal,
Err(error) => {
if !error.contains("zero-length")
|| std::env::var("BREP_POLE_NORMAL_RESCUE").as_deref() == Ok("0")
{
return Err(error);
}
let [u0, u1] = face.surface.domain_u()?;
let [v0, v1] = face.surface.domain_v()?;
let step_u = (u1 - u0) * 1e-4;
let step_v = (v1 - v0) * 1e-4;
let inner_u = u.clamp(u0 + step_u, u1 - step_u);
let inner_v = v.clamp(v0 + step_v, v1 - step_v);
let mut recovered = None;
for (cu, cv) in [(u, inner_v), (inner_u, v), (inner_u, inner_v)] {
if let Ok(normal) = face.surface.normal(cu, cv) {
recovered = Some(normal);
break;
}
}
match recovered {
Some(normal) => normal,
None => return Err(error),
}
}
};
Ok(if face.same_sense {
normal
} else {
normal.scale(-1.0)
})
}
fn face_uv_tolerance(face: &FaceRecord, u: f64, v: f64, spatial: f64) -> f64 {
surface_uv_band(&face.surface, u, v, spatial)
}
pub(crate) fn surface_uv_band(surface: &crate::NurbsSurface, u: f64, v: f64, spatial: f64) -> f64 {
let Ok(derivatives) = surface.derivatives(u, v, 1) else {
return spatial;
};
let band = crate::tolerance::surface_uv_tolerance(
spatial,
derivatives[1][0].length(),
derivatives[0][1].length(),
);
let cap = match (surface.domain_u(), surface.domain_v()) {
(Ok([u0, u1]), Ok([v0, v1])) => ((u1 - u0).min(v1 - v0) * 0.05).max(1e-12),
_ => f64::INFINITY,
};
band.min(cap)
}
#[derive(Clone, Copy, Debug, PartialEq, Serialize)]
#[serde(rename_all = "lowercase")]
pub enum PointClass {
In,
Out,
On,
}
#[derive(Clone, Copy, Debug, Serialize)]
pub struct PointClassification {
pub class: PointClass,
#[serde(skip_serializing_if = "Option::is_none")]
pub on_normal: Option<Vec3>,
}
#[derive(Default, Clone, Copy)]
pub(crate) struct ClassifyProfile {
pub enabled: bool,
pub classify_calls: u64,
pub band_candidates: u64,
pub band_project_ms: f64,
pub band_trim_tests: u64,
pub band_trim_ms: f64,
pub rays: u64,
pub ray_faces: u64,
pub ray_csi_ms: f64,
pub ray_exact_faces: u64,
pub ray_fallback_faces: u64,
pub ray_trim_tests: u64,
pub ray_trim_ms: f64,
pub coincident_calls: u64,
pub coincident_ms: f64,
pub classifier_builds: u64,
pub classifier_build_ms: f64,
}
thread_local! {
static CLASSIFY_PROFILE: std::cell::Cell<ClassifyProfile> =
const { std::cell::Cell::new(ClassifyProfile {
enabled: false, classify_calls: 0, band_candidates: 0, band_project_ms: 0.0,
band_trim_tests: 0, band_trim_ms: 0.0, rays: 0, ray_faces: 0, ray_csi_ms: 0.0,
ray_exact_faces: 0, ray_fallback_faces: 0, ray_trim_tests: 0, ray_trim_ms: 0.0, coincident_calls: 0, coincident_ms: 0.0,
classifier_builds: 0, classifier_build_ms: 0.0,
}) };
}
impl crate::profile::Counters for ClassifyProfile {
fn armed(&self) -> bool {
self.enabled
}
}
fn classify_profile(update: impl FnOnce(&mut ClassifyProfile)) {
crate::profile::update(&CLASSIFY_PROFILE, update)
}
fn classify_profile_started() -> Option<web_time::Instant> {
crate::profile::started(&CLASSIFY_PROFILE)
}
use crate::profile::elapsed_ms as classify_elapsed_ms;
pub(crate) fn classify_profile_begin() {
let enabled = crate::profile::profile_enabled();
CLASSIFY_PROFILE.with(|cell| {
cell.set(ClassifyProfile {
enabled,
..ClassifyProfile::default()
})
});
}
pub(crate) fn classify_profile_report(label: &str) {
let p = CLASSIFY_PROFILE.with(|cell| cell.get());
if !p.enabled {
return;
}
profile_line!(
"classify.profile {label} calls={} builds={} build_ms={:.2} band: candidates={} project_ms={:.2} trim_tests={} trim_ms={:.2} rays={} ray_faces={} csi_ms={:.2} exact_faces={} fallback_faces={} ray_trim_tests={} ray_trim_ms={:.2} coincident: calls={} ms={:.2}",
p.classify_calls, p.classifier_builds, p.classifier_build_ms, p.band_candidates,
p.band_project_ms, p.band_trim_tests, p.band_trim_ms, p.rays, p.ray_faces,
p.ray_csi_ms, p.ray_exact_faces, p.ray_fallback_faces, p.ray_trim_tests, p.ray_trim_ms, p.coincident_calls, p.coincident_ms,
);
CLASSIFY_PROFILE.with(|cell| cell.set(ClassifyProfile::default()));
}
fn exact_ray_enabled() -> bool {
switch!("BREP_CLASSIFY_EXACT_RAY", true)
}
fn ray_face_intersections(
sub_ray: &NurbsCurve,
surface: &crate::NurbsSurface,
tolerance: f64,
) -> Result<Vec<crate::CurveSurfaceIntersection>, String> {
if exact_ray_enabled() {
if let Some(seeds) = crate::exact_line_surface::exact_line_surface_seeds(sub_ray, surface, tolerance) {
classify_profile(|p| p.ray_exact_faces += 1);
return crate::curve_surface_intersection::intersect_curve_surface_from_seeds(sub_ray, surface, tolerance, seeds);
}
classify_profile(|p| p.ray_fallback_faces += 1);
}
intersect_curve_surface(sub_ray, surface, tolerance)
}
pub struct SolidClassifier<'a> {
faces: Vec<&'a FaceRecord>,
face_boxes: Vec<Aabb>,
bounds: Aabb,
bvh: Bvh,
tolerance: f64,
coincident_caps: Vec<(Aabb, f64)>,
}
fn clip_segment_to_aabb(
start: Vec3,
direction: Vec3,
length: f64,
bounds: &Aabb,
) -> Option<[f64; 2]> {
let mut s0 = 0.0f64;
let mut s1 = length;
for axis in 0..3 {
let (origin, delta, minimum, maximum) = match axis {
0 => (start.x, direction.x, bounds.minimum.x, bounds.maximum.x),
1 => (start.y, direction.y, bounds.minimum.y, bounds.maximum.y),
_ => (start.z, direction.z, bounds.minimum.z, bounds.maximum.z),
};
if delta.abs() <= 1e-15 {
if origin < minimum || origin > maximum {
return None;
}
continue;
}
let mut near = (minimum - origin) / delta;
let mut far = (maximum - origin) / delta;
if near > far {
std::mem::swap(&mut near, &mut far);
}
s0 = s0.max(near);
s1 = s1.min(far);
if s0 > s1 {
return None;
}
}
Some([s0, s1])
}
impl<'a> SolidClassifier<'a> {
pub fn new(solid: &'a BrepSolid, tolerance: f64) -> Result<Self, String> {
let build_started = classify_profile_started();
let faces: Vec<&FaceRecord> = solid.shells.iter().flat_map(|shell| &shell.faces).collect();
let face_boxes = faces
.iter()
.map(|face| Aabb::from_surface_controls(&face.surface))
.collect::<Result<Vec<_>, _>>()?;
let mut bounds = Aabb::empty();
for face_box in &face_boxes {
bounds.include(*face_box);
}
let bvh = Bvh::build(&face_boxes);
classify_profile(|p| {
p.classifier_builds += 1;
p.classifier_build_ms += classify_elapsed_ms(build_started);
});
Ok(Self {
faces,
face_boxes,
bounds,
bvh,
tolerance,
coincident_caps: Vec::new(),
})
}
pub fn near_surface(&self, point: Vec3) -> Result<bool, String> {
let on_tolerance = self.tolerance * 10.0;
if !self.bounds.expanded(on_tolerance).contains(point) {
return Ok(false);
}
let mut candidates = Vec::new();
self.bvh
.containing_point(point, on_tolerance, &mut candidates);
for &index in &candidates {
let projection = project_point_to_surface(&self.faces[index].surface, point)?;
if projection.distance <= on_tolerance {
return Ok(true);
}
}
Ok(false)
}
pub fn within_band(&self, point: Vec3, band: f64) -> Result<bool, String> {
if !self.bounds.expanded(band).contains(point) {
return Ok(false);
}
let mut candidates = Vec::new();
self.bvh.containing_point(point, band, &mut candidates);
for &index in &candidates {
let projection = project_point_to_surface(&self.faces[index].surface, point)?;
if projection.distance <= band {
return Ok(true);
}
}
Ok(false)
}
pub fn classify(&self, point: Vec3) -> Result<PointClassification, String> {
let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::CLASSIFY);
classify_profile(|p| p.classify_calls += 1);
let tolerance = self.tolerance;
if !self.bounds.expanded(tolerance).contains(point) {
return Ok(PointClassification {
class: PointClass::Out,
on_normal: None,
});
}
let on_tolerance = self.capped_band(point, tolerance * 10.0);
if !self.coincident_caps.is_empty() && env_read!("BREP_DEBUG_FEATURE_SCALE").is_some() {
eprintln!("feature_scale: classify at {point:?} on band {on_tolerance:.3e} (uncapped {:.3e}, {} caps)", tolerance * 10.0, self.coincident_caps.len());
}
let mut candidates = Vec::new();
self.bvh
.containing_point(point, on_tolerance, &mut candidates);
candidates.sort_unstable();
let mut interior_normals: Vec<Vec3> = Vec::new();
let mut boundary_normals: Vec<Vec3> = Vec::new();
for &index in &candidates {
let face = self.faces[index];
let project_started = classify_profile_started();
let projection = project_point_to_surface(&face.surface, point)?;
classify_profile(|p| {
p.band_candidates += 1;
p.band_project_ms += classify_elapsed_ms(project_started);
});
if projection.distance > on_tolerance {
continue;
}
let uv_tolerance = face_uv_tolerance(face, projection.u, projection.v, on_tolerance);
let trim_started = classify_profile_started();
let trim = parameter_point_in_face(
face,
Vec2 {
x: projection.u,
y: projection.v,
},
uv_tolerance,
)?;
classify_profile(|p| {
p.band_trim_tests += 1;
p.band_trim_ms += classify_elapsed_ms(trim_started);
});
match trim {
PolygonClass::Inside => {
interior_normals.push(face_normal(face, projection.u, projection.v)?)
}
PolygonClass::Boundary => {
boundary_normals.push(face_normal(face, projection.u, projection.v)?)
}
PolygonClass::Outside => {}
}
}
let pool = if interior_normals.is_empty() {
&boundary_normals
} else {
&interior_normals
};
if !pool.is_empty() {
let mut sum = Vec3::default();
for normal in pool {
sum = sum.add(*normal);
}
if sum.length() > 1e-3 {
return Ok(PointClassification {
class: PointClass::On,
on_normal: Some(sum.normalized()?),
});
}
}
let directions = [
Vec3::new(0.577215, 0.618034, 0.532088),
Vec3::new(-0.707107, 0.267949, 0.654321),
Vec3::new(0.316228, -0.741657, 0.585786),
Vec3::new(-0.414214, -0.552786, -0.723607),
Vec3::new(0.9482, 0.11893, -0.29456),
Vec3::new(-0.13947, 0.90271, -0.40718),
Vec3::new(0.62361, -0.33912, -0.70414),
Vec3::new(0.20912, 0.51293, 0.83261),
];
let ray_length = self.bounds.diagonal() * 3.0 + 1.0;
let require_agreement = std::env::var("BREP_CLASSIFY_RAY_AGREE").as_deref() != Ok("0");
let mut verdicts: Vec<PointClass> = Vec::new();
'directions: for direction in directions {
classify_profile(|p| p.rays += 1);
let direction = direction.normalized()?;
let ray_end = point.add(direction.scale(ray_length));
candidates.clear();
self.bvh
.intersecting_segment(point, ray_end, on_tolerance, &mut candidates);
candidates.sort_unstable();
let mut crossings = 0;
for &index in &candidates {
let face = self.faces[index];
let margin = on_tolerance.max(self.face_boxes[index].diagonal() * 1e-3);
let Some([span_start, span_end]) = clip_segment_to_aabb(
point,
direction,
ray_length,
&self.face_boxes[index].expanded(margin),
) else {
continue;
};
let span_start = (span_start - margin).max(0.0);
let span_end = (span_end + margin).min(ray_length);
if span_end - span_start <= 1e-12 {
continue;
}
let sub_ray = make_line(
point.add(direction.scale(span_start)),
point.add(direction.scale(span_end)),
)?;
let csi_started = classify_profile_started();
let intersections = ray_face_intersections(&sub_ray, &face.surface, tolerance)?;
classify_profile(|p| {
p.ray_faces += 1;
p.ray_csi_ms += classify_elapsed_ms(csi_started);
});
for intersection in intersections {
if intersection.point.sub(point).length() <= on_tolerance {
let trim_started = classify_profile_started();
let trim = parameter_point_in_face(
face,
Vec2 {
x: intersection.u,
y: intersection.v,
},
face_uv_tolerance(face, intersection.u, intersection.v, on_tolerance),
)?;
classify_profile(|p| {
p.ray_trim_tests += 1;
p.ray_trim_ms += classify_elapsed_ms(trim_started);
});
if trim != PolygonClass::Outside {
return Ok(PointClassification {
class: PointClass::On,
on_normal: Some(face_normal(face, intersection.u, intersection.v)?),
});
}
continue;
}
if intersection.tangential {
continue 'directions;
}
let trim_started = classify_profile_started();
let trim_class = parameter_point_in_face(
face,
Vec2 {
x: intersection.u,
y: intersection.v,
},
face_uv_tolerance(face, intersection.u, intersection.v, on_tolerance),
)?;
classify_profile(|p| {
p.ray_trim_tests += 1;
p.ray_trim_ms += classify_elapsed_ms(trim_started);
});
if std::env::var("BREP_DEBUG_CLASSIFY").is_ok() {
eprintln!(
"classify ray dir=({:.3},{:.3},{:.3}) face={} hit=({:.4},{:.4},{:.4}) t3d={:.4} uv=({:.6},{:.6}) trim={:?}",
direction.x, direction.y, direction.z,
face.id,
intersection.point.x, intersection.point.y, intersection.point.z,
intersection.point.sub(point).length(),
intersection.u, intersection.v,
trim_class
);
}
match trim_class {
PolygonClass::Boundary => continue 'directions,
PolygonClass::Inside => crossings += 1,
PolygonClass::Outside => {}
}
}
}
let verdict = if crossings % 2 == 1 {
PointClass::In
} else {
PointClass::Out
};
if std::env::var("BREP_DEBUG_CLASSIFY").is_ok() {
eprintln!(
"classify verdict dir=({:.3},{:.3},{:.3}) crossings={crossings} -> {verdict:?}",
direction.x, direction.y, direction.z
);
}
if !require_agreement || verdicts.contains(&verdict) {
return Ok(PointClassification {
class: verdict,
on_normal: None,
});
}
verdicts.push(verdict);
}
if let Some(&verdict) = verdicts.last() {
return Ok(PointClassification {
class: verdict,
on_normal: None,
});
}
Err("classifyPointVsSolid: no clean ray direction found".into())
}
pub fn with_coincident_caps(mut self, caps: Vec<(Aabb, f64)>) -> Self {
self.coincident_caps = caps;
self
}
fn capped_band(&self, point: Vec3, band: f64) -> f64 {
self.coincident_caps
.iter()
.filter(|(region, _)| region.expanded(band).contains(point))
.fold(band, |band, &(_, cap)| band.min(cap * (1.0 - 1e-9)))
}
pub fn coincident_on_normal(&self, point: Vec3) -> Result<Option<Vec3>, String> {
let started = classify_profile_started();
let result = self.coincident_on_normal_inner(point);
classify_profile(|p| {
p.coincident_calls += 1;
p.coincident_ms += classify_elapsed_ms(started);
});
result
}
fn coincident_on_normal_inner(&self, point: Vec3) -> Result<Option<Vec3>, String> {
let band = (self.tolerance * 10.0).max(self.bounds.diagonal() * 1e-7);
let band = self.capped_band(point, band);
if !self.bounds.expanded(band).contains(point) {
return Ok(None);
}
let mut candidates = Vec::new();
self.bvh.containing_point(point, band, &mut candidates);
let mut interior_normals: Vec<Vec3> = Vec::new();
for &index in &candidates {
let face = self.faces[index];
let projection = project_point_to_surface(&face.surface, point)?;
if projection.distance > band {
continue;
}
let uv_tolerance = face_uv_tolerance(face, projection.u, projection.v, band);
if let PolygonClass::Inside = parameter_point_in_face(
face,
Vec2 {
x: projection.u,
y: projection.v,
},
uv_tolerance,
)? {
interior_normals.push(face_normal(face, projection.u, projection.v)?);
}
}
if interior_normals.is_empty() {
return Ok(None);
}
let mut sum = Vec3::default();
for normal in &interior_normals {
sum = sum.add(*normal);
}
if sum.length() <= 1e-3 {
return Ok(None);
}
Ok(Some(sum.normalized()?))
}
}
pub fn classify_point(
point: Vec3,
solid: &BrepSolid,
tolerance: f64,
) -> Result<PointClassification, String> {
let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::CLASSIFY);
classify_profile_begin();
let result = SolidClassifier::new(solid, tolerance)?.classify(point);
classify_profile_report("classify_point");
result
}