geop_core_topology/edit/split_edge_at_vertex.rs
1use crate::{Coedge, CoedgeGeometry, Edge, EdgeId, Model, Sense, VertexId};
2use geop_core_geometry::{contains::curve::curve_could_contain, search::PROJECT_ITERATIONS};
3use geop_core_math::{
4 geop_error::{GeopError, GeopResult, WithContext},
5 scalars::Scalar,
6 vector::Vector2,
7};
8
9impl Model {
10 /// Splits `edge_id` at `edge_t` into two edges joined at the pre-existing
11 /// `vertex_id` (which must already coincide with `edge.curve.evaluate(edge_t)`),
12 /// and splits every coedge tracing `edge_id` to match. `edge_id` itself
13 /// keeps the first (start -> vertex) segment; the new edge holding the
14 /// second (vertex -> end) segment, in the same direction, is returned.
15 ///
16 /// `max_nodes`/`min_subdivision_size` bound the BFS search used to locate
17 /// each coedge's own pcurve parameter for the split (see
18 /// `curve_could_contain`).
19 pub fn split_edge_at_vertex(
20 &mut self,
21 edge_id: EdgeId,
22 edge_t: Scalar,
23 vertex_id: VertexId,
24 max_nodes: usize,
25 min_subdivision_size: Scalar,
26 ) -> GeopResult<EdgeId> {
27 let ctx = |e: GeopError| {
28 e.with_context(format!(
29 "Model::split_edge_at_vertex(edge_id={edge_id}, edge_t={edge_t}, vertex_id={vertex_id}, max_nodes={max_nodes}, min_subdivision_size={min_subdivision_size})"
30 ))
31 };
32
33 let edge = self.get_edge(edge_id).with_context(&ctx)?.clone();
34 let vertex_point = self.get_vertex(vertex_id).with_context(&ctx)?.point;
35
36 // Checked for the 3-D curve *and* every coedge's pcurve before any
37 // mutation — splitting the edge and only then finding a pcurve that
38 // cannot be split would leave the model half-updated.
39 //
40 // Each parameter is Newton-refined against the point it is meant to
41 // name, and the curve is cut at the sharp middle of that: where in
42 // the refined enclosure is a free choice, and cutting at all of it
43 // made every later piece of the edge wider than the last (see
44 // `NurbCurve::split_parameter_at_point`, which also checks that the
45 // curve reaches the vertex at the parameter chosen). A parameter
46 // that could be the curve's end is refused there: the vertex is
47 // then already an endpoint, which the caller rules out before
48 // asking (see `find_piercing_crossing`), so reaching here with one
49 // is a caller bug, reported rather than quietly ignored.
50 let edge_t = edge
51 .curve
52 .split_parameter_at_point(edge_t, &vertex_point, &vertex_point)
53 .with_context(&ctx)?;
54 // Where the pieces will meet: a point within the vertex, and the one
55 // every pcurve is cut at too. Cut each at a point of the vertex of
56 // its own and the pieces of the edge and of its pcurves end apart,
57 // by as much as the vertex is wide — `1.4e-13` where a cubic crosses
58 // a plane at its inflection, and the pcurve's end then maps off the
59 // edge's.
60 let split_point = edge.curve.evaluate(edge_t).with_context(&ctx)?;
61 let mut pcurve_splits = Vec::new();
62 for coedge_id in self.coedges_of_edge(edge_id) {
63 let coedge = self.get_coedge(coedge_id).with_context(&ctx)?.clone();
64 let coedge_ctx = |e: GeopError| {
65 let (t0, t1) = coedge.pcurve.domain();
66 e.with_context(format!(
67 "coedge_id={coedge_id}, face={}, sense={:?}, pcurve_domain=({t0}, {t1})",
68 coedge.face, coedge.sense,
69 ))
70 };
71 let surface = &self.get_face(coedge.face).with_context(&ctx)?.surface;
72 // The pcurve's own parameter range doesn't share the edge curve's
73 // `t` values, so the split point is relocated geometrically:
74 // locate the split point in the face's `(u, v)` space, then project
75 // that `(u, v)` back onto the coedge's own pcurve.
76 // Located, not merely isolated: the containment search alone
77 // pins `(u, v)` only to its own subdivision tolerance, far too
78 // wide to serve as the *target* of the pcurve refinement below
79 // (a wide target makes a wide residual, a wide step, and a
80 // pcurve parameter no narrower than it started).
81 let (u, v) = surface
82 .locate(&split_point, max_nodes, min_subdivision_size)
83 .with_context(&ctx)
84 .with_context(&coedge_ctx)?
85 .ok_or_else(|| {
86 ctx(coedge_ctx(GeopError::new(format!(
87 "could not locate the split point {split_point:?} of vertex {vertex_id} (at {vertex_point:?}) on face {}'s surface",
88 coedge.face
89 ))))
90 })?;
91 let uv = Vector2::from_array([u, v]);
92 let uv_ctx = |e: GeopError| e.with_context(format!("found uv=({u}, {v})"));
93 let pcurve_t =
94 curve_could_contain(&coedge.pcurve, &uv, max_nodes, min_subdivision_size)
95 .with_context(&ctx)
96 .with_context(&coedge_ctx)
97 .with_context(&uv_ctx)?
98 .ok_or_else(|| {
99 ctx(coedge_ctx(uv_ctx(GeopError::new(format!(
100 "could not locate vertex {vertex_id} on coedge {coedge_id}'s pcurve"
101 )))))
102 })?;
103 // The vertex there: the pcurve is cut at the split point, and has
104 // only to end within the vertex.
105 let (vertex_u, vertex_v) = surface
106 .project(vertex_point, u.sharpen(), v.sharpen(), PROJECT_ITERATIONS)
107 .with_context(&ctx)
108 .with_context(&coedge_ctx)?;
109 let within = Vector2::from_array([u.union(vertex_u), v.union(vertex_v)]);
110 let pcurve_t = coedge
111 .pcurve
112 .split_parameter_at_point(pcurve_t, &uv, &within)
113 .with_context(&ctx)
114 .with_context(&coedge_ctx)
115 .with_context(&uv_ctx)?;
116 pcurve_splits.push((coedge_id, pcurve_t));
117 }
118
119 let (new_curve_1, new_curve_2) = edge.curve.split(edge_t).with_context(&ctx)?;
120 // Reuse `edge_id` for the first (start -> vertex) segment, shortened
121 // in place, and only allocate a new edge for the second segment.
122 let existing_edge = self.get_edge_mut(edge_id).with_context(&ctx)?;
123 existing_edge.curve = new_curve_1;
124 existing_edge.end_vertex = vertex_id;
125 let edge_1 = edge_id;
126 let edge_2 = self.insert_edge(Edge {
127 curve: new_curve_2,
128 start_vertex: vertex_id,
129 end_vertex: edge.end_vertex,
130 });
131
132 for (coedge_id, pcurve_t) in pcurve_splits {
133 let coedge = self.get_coedge(coedge_id).with_context(&ctx)?.clone();
134
135 let coedge_ctx = |e: GeopError| {
136 let (t0, t1) = coedge.pcurve.domain();
137 e.with_context(format!(
138 "coedge_id={coedge_id}, face={}, sense={:?}, pcurve_domain=({t0}, {t1})",
139 coedge.face, coedge.sense,
140 ))
141 };
142
143 let (pcurve_left, pcurve_right) = coedge
144 .pcurve
145 .split(pcurve_t)
146 .with_context(&ctx)
147 .with_context(&coedge_ctx)?;
148 // `pcurve_left`/`pcurve_right` are in the coedge's own traversal
149 // order (its domain's low end is its own start), which for a
150 // `Reversed` coedge runs from `edge_2` back to `edge_1`.
151 let (first_edge, first_pcurve, second_edge, second_pcurve) = match coedge.sense {
152 Sense::Forward => (edge_1, pcurve_left, edge_2, pcurve_right),
153 Sense::Reversed => (edge_2, pcurve_left, edge_1, pcurve_right),
154 };
155
156 let new_coedge_id = self.insert_coedge(Coedge {
157 geometry: CoedgeGeometry::Edge(second_edge),
158 sense: coedge.sense,
159 pcurve: second_pcurve,
160 next: coedge.next,
161 prev: coedge_id,
162 face: coedge.face,
163 });
164
165 let existing = self.get_coedge_mut(coedge_id).with_context(&ctx)?;
166 existing.geometry = CoedgeGeometry::Edge(first_edge);
167 existing.pcurve = first_pcurve;
168 existing.next = new_coedge_id;
169
170 self.get_coedge_mut(coedge.next).with_context(&ctx)?.prev = new_coedge_id;
171 }
172
173 Ok(edge_2)
174 }
175}