mod codec;
mod facts;
mod memo;
mod names;
pub(crate) mod pcurve;
pub(crate) mod radial;
mod similar;
use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::sync::Arc;
pub use facts::{Facts, OnFace};
pub(crate) use memo::{FaceMemo, FaceVolume, IntegralKey};
pub use names::FaceName;
pub use pcurve::PCurve;
pub(crate) use pcurve::project_on;
use crate::{
geom::{Curve, Surface},
math::{Point3, Transform, Vec2},
tol,
};
macro_rules! id {
($(#[$m:meta])* $name:ident) => {
$(#[$m])*
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct $name(u32);
impl $name {
pub fn index(self) -> usize {
self.0 as usize
}
fn at(i: usize) -> $name {
$name(u32::try_from(i).expect("arena index fits in u32"))
}
}
};
}
id!(VertexId);
id!(EdgeId);
id!(CoedgeId);
id!(LoopId);
id!(FaceId);
id!(ShellId);
id!(SolidId);
#[derive(Clone, Debug, PartialEq)]
pub struct Vertex {
pub point: Point3,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Edge {
pub curve: Option<Curve>,
pub range: (f64, f64),
pub start: VertexId,
pub end: VertexId,
}
impl Edge {
pub fn is_degenerate(&self) -> bool {
self.curve.is_none()
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct Coedge {
pub edge: EdgeId,
pub reversed: bool,
pub pcurve: PCurve,
pub lp: LoopId,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Loop {
pub coedges: Vec<CoedgeId>,
pub face: FaceId,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Face {
pub surface: Surface,
pub reversed: bool,
pub loops: Vec<LoopId>,
pub names: BTreeSet<FaceName>,
pub shell: Option<ShellId>,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Shell {
pub faces: Vec<FaceId>,
pub solid: Option<SolidId>,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Solid {
pub shells: Vec<ShellId>,
pub outer: usize,
}
#[derive(Clone, Debug, PartialEq)]
pub struct CoedgeSpec {
pub edge: EdgeId,
pub reversed: bool,
pub pcurve: PCurve,
}
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Brep {
vertices: Vec<Vertex>,
edges: Vec<Edge>,
coedges: Vec<Coedge>,
loops: Vec<Loop>,
faces: Vec<Face>,
shells: Vec<Shell>,
solids: Vec<Solid>,
memos: memo::Memos,
tolerances: Box<Tolerances>,
partners: BTreeMap<CoedgeId, CoedgeId>,
beside: BTreeMap<CoedgeId, CoedgeId>,
uses: Vec<Vec<CoedgeId>>,
}
pub type Tolerant = (Vec<(VertexId, f64)>, Vec<(EdgeId, f64)>);
#[derive(Clone, Debug, Default, PartialEq)]
struct Tolerances {
vertices: BTreeMap<VertexId, f64>,
edges: BTreeMap<EdgeId, f64>,
}
impl Brep {
pub fn new() -> Brep {
Brep::default()
}
pub(crate) fn add_vertex(&mut self, point: Point3) -> VertexId {
self.vertices.push(Vertex { point });
VertexId::at(self.vertices.len() - 1)
}
pub(crate) fn add_edge(
&mut self,
curve: Curve,
range: (f64, f64),
start: VertexId,
end: VertexId,
) -> EdgeId {
self.edges.push(Edge {
curve: Some(curve),
range,
start,
end,
});
self.uses.push(Vec::new());
EdgeId::at(self.edges.len() - 1)
}
pub(crate) fn add_degenerate_edge(&mut self, vertex: VertexId, range: (f64, f64)) -> EdgeId {
self.edges.push(Edge {
curve: None,
range,
start: vertex,
end: vertex,
});
self.uses.push(Vec::new());
EdgeId::at(self.edges.len() - 1)
}
pub(crate) fn add_face(
&mut self,
surface: Surface,
reversed: bool,
names: impl IntoIterator<Item = FaceName>,
) -> FaceId {
self.faces.push(Face {
surface,
reversed,
loops: Vec::new(),
names: names.into_iter().collect(),
shell: None,
});
self.memos.0.push(Arc::default());
FaceId::at(self.faces.len() - 1)
}
pub(crate) fn add_loop(&mut self, face: FaceId, coedges: Vec<CoedgeSpec>) -> LoopId {
let lp = LoopId::at(self.loops.len());
let mut ids = Vec::with_capacity(coedges.len());
for c in coedges {
let edge = c.edge;
self.coedges.push(Coedge {
edge,
reversed: c.reversed,
pcurve: c.pcurve,
lp,
});
let id = CoedgeId::at(self.coedges.len() - 1);
self.uses[edge.index()].push(id);
ids.push(id);
}
self.loops.push(Loop { coedges: ids, face });
self.faces[face.index()].loops.push(lp);
self.memos.0[face.index()] = Arc::default();
lp
}
pub(crate) fn add_shell(&mut self, faces: Vec<FaceId>) -> ShellId {
let id = ShellId::at(self.shells.len());
for &f in &faces {
self.faces[f.index()].shell = Some(id);
}
self.shells.push(Shell { faces, solid: None });
id
}
pub(crate) fn add_solid(&mut self, shells: Vec<ShellId>) -> SolidId {
self.add_solid_of(shells, 1)
}
pub(crate) fn add_solid_of(&mut self, shells: Vec<ShellId>, outer: usize) -> SolidId {
let id = SolidId::at(self.solids.len());
for &s in &shells {
self.shells[s.index()].solid = Some(id);
}
self.solids.push(Solid { shells, outer });
id
}
pub fn pair(&mut self, a: CoedgeId, b: CoedgeId) {
self.partners.insert(a, b);
self.partners.insert(b, a);
}
pub(crate) fn set_beside(&mut self, a: CoedgeId, b: CoedgeId) {
self.beside.insert(a, b);
self.beside.insert(b, a);
}
pub fn beside(&self, c: CoedgeId) -> Option<CoedgeId> {
let us = &self.uses[self.coedges[c.index()].edge.index()];
match us.len() {
2 => us.iter().copied().find(|&o| o != c),
n if n > 2 => self.beside.get(&c).copied(),
_ => None,
}
}
pub fn edge_uses(&self, e: EdgeId) -> &[CoedgeId] {
&self.uses[e.index()]
}
pub fn partner(&self, c: CoedgeId) -> Option<CoedgeId> {
let us = &self.uses[self.coedges[c.index()].edge.index()];
match us.len() {
2 => us.iter().copied().find(|&o| o != c),
n if n > 2 => self.partners.get(&c).copied(),
_ => None,
}
}
pub fn radial_edges(&self) -> impl Iterator<Item = EdgeId> + '_ {
self.edge_ids().filter(|&e| self.uses[e.index()].len() > 2)
}
pub(crate) fn pair_radial(&mut self) {
let edges: Vec<EdgeId> = self.radial_edges().collect();
for e in edges {
let us = self.uses[e.index()].clone();
if us.iter().all(|c| self.partners.contains_key(c)) {
continue;
}
let edge = &self.edges[e.index()];
let Some(curve) = &edge.curve else { continue };
let (m, d) = curve.d1(0.5 * (edge.range.0 + edge.range.1));
let Some(t) = d.unit() else { continue };
let len = crate::topo::radial::length(curve, edge.range);
let sides: Vec<radial::Side> = us
.iter()
.map(|&c| {
let face = &self.faces[self.coedge_face(c).index()];
radial::Side {
surface: &face.surface,
reversed: face.reversed,
travel: if self.coedges[c.index()].reversed {
-t
} else {
t
},
}
})
.collect();
let Some((pairs, beside)) = radial::round(m, t, len, &sides) else {
continue;
};
for (i, j) in pairs {
self.pair(us[i], us[j]);
}
for (i, j) in beside {
self.set_beside(us[i], us[j]);
}
}
}
pub(crate) fn index_uses(&mut self) {
self.uses = vec![Vec::new(); self.edges.len()];
for (i, c) in self.coedges.iter().enumerate() {
self.uses[c.edge.index()].push(CoedgeId::at(i));
}
}
pub fn vertex(&self, id: VertexId) -> &Vertex {
&self.vertices[id.index()]
}
pub fn edge(&self, id: EdgeId) -> &Edge {
&self.edges[id.index()]
}
pub fn coedge(&self, id: CoedgeId) -> &Coedge {
&self.coedges[id.index()]
}
pub fn lp(&self, id: LoopId) -> &Loop {
&self.loops[id.index()]
}
pub fn is_vertex_loop(&self, id: LoopId) -> bool {
let cs = &self.lp(id).coedges;
cs.len() == 1 && self.edge(self.coedge(cs[0]).edge).is_degenerate()
}
pub fn face(&self, id: FaceId) -> &Face {
&self.faces[id.index()]
}
pub(crate) fn face_mut(&mut self, id: FaceId) -> &mut Face {
self.memos.0[id.index()] = Arc::default();
&mut self.faces[id.index()]
}
pub fn rename_faces<I>(&mut self, mut names_for: impl FnMut(&FaceName) -> I)
where
I: IntoIterator<Item = FaceName>,
{
for face in &mut self.faces {
face.names = face.names.iter().flat_map(&mut names_for).collect();
}
}
pub(crate) fn set_face_names(&mut self, id: FaceId, names: BTreeSet<FaceName>) {
self.faces[id.index()].names = names;
}
pub(crate) fn memo(&self, id: FaceId) -> &FaceMemo {
&self.memos.0[id.index()]
}
pub(crate) fn shared_memo(&self, id: FaceId) -> Arc<FaceMemo> {
#[cfg(debug_assertions)]
self.memo(id).layout.get_or_init(|| self.layout(id));
self.memos.0[id.index()].clone()
}
pub(crate) fn share_memo(&mut self, id: FaceId, memo: Arc<FaceMemo>) {
self.memos.0[id.index()] = memo;
#[cfg(debug_assertions)]
if let Some(was) = self.memo(id).layout.get() {
debug_assert!(
*was == self.layout(id),
"face {} takes the memo of a face laid out another way",
id.index()
);
}
}
#[cfg(debug_assertions)]
fn layout(&self, id: FaceId) -> Vec<Vec<(u64, u64, bool)>> {
let of = |&c: &CoedgeId| {
let co = self.coedge(c);
let (t0, t1) = self.edge(co.edge).range;
(t0.to_bits(), t1.to_bits(), co.reversed)
};
let coedges = |&lp: &LoopId| self.lp(lp).coedges.iter().map(of).collect();
self.face(id).loops.iter().map(coedges).collect()
}
pub fn shell(&self, id: ShellId) -> &Shell {
&self.shells[id.index()]
}
pub fn solid(&self, id: SolidId) -> &Solid {
&self.solids[id.index()]
}
pub fn vertex_ids(&self) -> impl Iterator<Item = VertexId> + use<> {
(0..self.vertices.len()).map(VertexId::at)
}
pub fn edge_ids(&self) -> impl Iterator<Item = EdgeId> + use<> {
(0..self.edges.len()).map(EdgeId::at)
}
pub fn coedge_ids(&self) -> impl Iterator<Item = CoedgeId> + use<> {
(0..self.coedges.len()).map(CoedgeId::at)
}
pub fn loop_ids(&self) -> impl Iterator<Item = LoopId> + use<> {
(0..self.loops.len()).map(LoopId::at)
}
pub fn face_ids(&self) -> impl Iterator<Item = FaceId> + use<> {
(0..self.faces.len()).map(FaceId::at)
}
pub fn shell_ids(&self) -> impl Iterator<Item = ShellId> + use<> {
(0..self.shells.len()).map(ShellId::at)
}
pub fn solid_ids(&self) -> impl Iterator<Item = SolidId> + use<> {
(0..self.solids.len()).map(SolidId::at)
}
pub fn vertex_tolerance(&self, v: VertexId) -> f64 {
self.tolerances
.vertices
.get(&v)
.copied()
.unwrap_or(tol::LINEAR)
}
pub fn edge_tolerance(&self, e: EdgeId) -> f64 {
self.tolerances
.edges
.get(&e)
.copied()
.unwrap_or(tol::LINEAR)
}
pub(crate) fn set_vertex_tolerance(&mut self, v: VertexId, t: f64) {
let old = self.vertex_tolerance(v);
if t > tol::LINEAR {
self.tolerances.vertices.insert(v, t);
} else {
self.tolerances.vertices.remove(&v);
}
if self.vertex_tolerance(v) != old {
self.forget_faces_of(|b, e| b.edge(e).start == v || b.edge(e).end == v);
}
}
pub(crate) fn set_edge_tolerance(&mut self, e: EdgeId, t: f64) {
let old = self.edge_tolerance(e);
if t > tol::LINEAR {
self.tolerances.edges.insert(e, t);
} else {
self.tolerances.edges.remove(&e);
}
if self.edge_tolerance(e) != old {
self.forget_faces_of(|_, x| x == e);
}
}
fn forget_faces_of(&mut self, uses: impl Fn(&Brep, EdgeId) -> bool) {
let faces: Vec<FaceId> = self
.coedges
.iter()
.filter(|c| uses(self, c.edge))
.map(|c| self.loops[c.lp.index()].face)
.collect();
for f in faces {
self.memos.0[f.index()] = Arc::default();
}
}
pub fn tolerant(&self) -> Tolerant {
(
self.tolerances
.vertices
.iter()
.map(|(&v, &t)| (v, t))
.collect(),
self.tolerances
.edges
.iter()
.map(|(&e, &t)| (e, t))
.collect(),
)
}
pub fn has_tolerances(&self) -> bool {
!self.tolerances.vertices.is_empty() || !self.tolerances.edges.is_empty()
}
pub fn face_count(&self) -> usize {
self.faces.len()
}
pub fn solid_faces(&self, s: SolidId) -> Vec<FaceId> {
self.solid(s)
.shells
.iter()
.flat_map(|&sh| self.shell(sh).faces.iter().copied())
.collect()
}
pub fn coedge_start(&self, c: CoedgeId) -> VertexId {
let co = self.coedge(c);
let e = self.edge(co.edge);
if co.reversed { e.end } else { e.start }
}
pub fn coedge_end(&self, c: CoedgeId) -> VertexId {
let co = self.coedge(c);
let e = self.edge(co.edge);
if co.reversed { e.start } else { e.end }
}
pub fn coedge_face(&self, c: CoedgeId) -> FaceId {
self.lp(self.coedge(c).lp).face
}
pub fn coedge_uvs(&self, c: CoedgeId, ts: &[f64]) -> Vec<Vec2> {
let co = self.coedge(c);
let surface = &self.face(self.coedge_face(c)).surface;
let periodic = surface.u_period().is_some() || surface.v_period().is_some();
if !periodic || ts.len() < 2 || matches!(co.pcurve, PCurve::Affine { .. }) {
return self.coedge_uvs_at(c, ts);
}
let (Some(curve), PCurve::Projected { seed }) = (&self.edge(co.edge).curve, &co.pcurve)
else {
return self.coedge_uvs_at(c, ts);
};
let (t0, t1) = (ts[0], ts[ts.len() - 1]);
let mut length = 0.0;
let mut prev = curve.eval(t0);
for k in 1..=256 {
let p = curve.eval(t0 + (t1 - t0) * k as f64 / 256.0);
length += p.dist(prev);
prev = p;
}
let (_, su, sv) = surface.d1(seed.x, seed.y);
let around = [(surface.u_period(), su), (surface.v_period(), sv)]
.iter()
.filter_map(|&(p, d)| p.map(|p| p * d.norm()))
.filter(|&c| c > 1e-9)
.fold(f64::INFINITY, f64::min);
let steps = if around.is_finite() {
(8.0 * length / around).ceil() as usize
} else {
0
};
let steps = if steps >= ts.len() - 1 {
let n = 32;
let mut turns = 0.0;
for k in 0..n {
let (p, dp) = curve.d1(t0 + (t1 - t0) * (k as f64 + 0.5) / n as f64);
let uv = surface.project(p);
let (_, su, sv) = surface.d1(uv.x, uv.y);
let rate = [(surface.u_period(), su), (surface.v_period(), sv)]
.iter()
.filter_map(|&(per, d)| per.map(|per| (per * d.norm(), d)))
.filter(|&(c, _)| c > 1e-9)
.map(|(c, d)| dp.dot(d).abs() / (d.norm() * c))
.fold(0.0, f64::max);
turns += rate * (t1 - t0).abs() / n as f64;
}
let needed = (16.0 * turns).ceil();
if needed.is_finite() {
steps.min(needed as usize)
} else {
steps
}
} else {
steps
};
let per = (steps / (ts.len() - 1) + 1).min(4096);
if per <= 1 {
return self.coedge_uvs_at(c, ts);
}
let mut dense = Vec::with_capacity((ts.len() - 1) * per + 1);
for w in ts.windows(2) {
for k in 0..per {
dense.push(w[0] + (w[1] - w[0]) * k as f64 / per as f64);
}
}
dense.push(t1);
let uvs = self.coedge_uvs_at(c, &dense);
(0..ts.len()).map(|i| uvs[i * per]).collect()
}
fn coedge_uvs_at(&self, c: CoedgeId, ts: &[f64]) -> Vec<Vec2> {
let co = self.coedge(c);
let edge = self.edge(co.edge);
match &co.pcurve {
PCurve::Affine { origin, dir } => ts.iter().map(|&t| *origin + *dir * t).collect(),
PCurve::Projected { seed } => {
let surface = &self.face(self.coedge_face(c)).surface;
let mut hint = *seed;
let mut out = Vec::with_capacity(ts.len());
for (i, &t) in ts.iter().enumerate() {
let beside = if i == 0 { ts.get(1) } else { ts.get(i - 1) };
let inside = t > edge.range.0 && t < edge.range.1;
let uv = match (&edge.curve, beside) {
(Some(curve), Some(&b)) if inside && i > 0 => {
pcurve::follow(surface, curve, (b, t), hint)
}
(Some(curve), Some(&b)) => pcurve::project_on(surface, curve, t, b, hint),
(Some(curve), None) => surface.project_near(curve.eval(t), hint),
(None, _) => surface.project_near(self.vertex(edge.start).point, hint),
};
hint = uv;
out.push(uv);
}
out
}
}
}
pub fn name_counts(&self) -> BTreeMap<String, usize> {
let mut out = BTreeMap::new();
for f in &self.faces {
for n in &f.names {
*out.entry(n.to_string()).or_insert(0) += 1;
}
}
out
}
pub fn transform(&mut self, t: &Transform) {
for v in &mut self.vertices {
v.point = t.point(v.point);
}
for e in &mut self.edges {
if let Some(c) = &e.curve {
e.curve = Some(c.transformed(t));
}
}
for f in &mut self.faces {
f.surface = f.surface.transformed(t);
}
let slid = t.r == Transform::IDENTITY.r;
for m in &mut self.memos.0 {
let fresh = FaceMemo::default();
if let (true, Some(b)) = (slid, m.loose_box.get()) {
let _ = fresh.loose_box.set(crate::math::Aabb {
min: b.min + t.t,
max: b.max + t.t,
});
}
if let Some(v) = m.volume.get() {
let _ = fresh.volume.set(FaceVolume {
anchor: t.point(v.anchor),
volume: v.volume,
vector_area: t.vector(v.vector_area),
});
}
if m.clean.get().is_some() {
let _ = fresh.clean.set(());
}
*m = Arc::new(fresh);
}
}
pub fn append(&mut self, other: &Brep) -> Vec<SolidId> {
let (v0, e0, c0, l0, f0, sh0, so0) = (
self.vertices.len(),
self.edges.len(),
self.coedges.len(),
self.loops.len(),
self.faces.len(),
self.shells.len(),
self.solids.len(),
);
self.vertices.extend(other.vertices.iter().cloned());
self.edges.extend(other.edges.iter().map(|e| Edge {
curve: e.curve.clone(),
range: e.range,
start: VertexId::at(e.start.index() + v0),
end: VertexId::at(e.end.index() + v0),
}));
self.coedges.extend(other.coedges.iter().map(|c| Coedge {
edge: EdgeId::at(c.edge.index() + e0),
reversed: c.reversed,
pcurve: c.pcurve.clone(),
lp: LoopId::at(c.lp.index() + l0),
}));
self.loops.extend(other.loops.iter().map(|l| {
Loop {
coedges: l
.coedges
.iter()
.map(|c| CoedgeId::at(c.index() + c0))
.collect(),
face: FaceId::at(l.face.index() + f0),
}
}));
self.faces.extend(other.faces.iter().map(|f| Face {
surface: f.surface.clone(),
reversed: f.reversed,
loops: f.loops.iter().map(|l| LoopId::at(l.index() + l0)).collect(),
names: f.names.clone(),
shell: f.shell.map(|s| ShellId::at(s.index() + sh0)),
}));
self.memos.0.extend(other.memos.0.iter().cloned());
self.shells.extend(other.shells.iter().map(|s| Shell {
faces: s.faces.iter().map(|f| FaceId::at(f.index() + f0)).collect(),
solid: s.solid.map(|s| SolidId::at(s.index() + so0)),
}));
self.solids.extend(other.solids.iter().map(|s| {
Solid {
shells: s
.shells
.iter()
.map(|sh| ShellId::at(sh.index() + sh0))
.collect(),
outer: s.outer,
}
}));
for (&a, &b) in &other.partners {
self.partners
.insert(CoedgeId::at(a.index() + c0), CoedgeId::at(b.index() + c0));
}
for (&a, &b) in &other.beside {
self.beside
.insert(CoedgeId::at(a.index() + c0), CoedgeId::at(b.index() + c0));
}
self.index_uses();
for (&v, &t) in &other.tolerances.vertices {
self.tolerances
.vertices
.insert(VertexId::at(v.index() + v0), t);
}
for (&e, &t) in &other.tolerances.edges {
self.tolerances.edges.insert(EdgeId::at(e.index() + e0), t);
}
(so0..self.solids.len()).map(SolidId::at).collect()
}
}