dymokomi/luce-cad
Source of release 0.9.4
0.9.4 / src / modeling / boolean.lucb
## Booleans of two closed solids, OpenCASCADE's General Fuse structure in
## a lean form (docs/research/CAD-MODELING-STUDY.md ยง3.1):
##
## 1. Both solids in one shape; vertices closer than the tolerance merged.
## 2. For each pair of faces whose boxes meet, where their surfaces meet
## (intersect.lucb), each curve clipped to both faces: its crossings with
## either face's boundary split it and the boundary edges (clip.lucb);
## the stretches inside both faces become new edges across both. Faces on
## one surface (coplanar ones above all: a sketch on a face extruded onto
## it) imprint each other's boundaries instead.
## 3. Every edge cut at its split points; pieces with the same ends and the
## same middle are one edge, so faces meeting along new edges share them.
## 4. Every face split along its new edges (split.lucb).
## 5. Each piece classified at a point well inside it: on the other solid's
## coincident face (facing the same way or not), else inside or outside
## the other solid by counting crossings of rays through its mesh.
## 6. The pieces the operation keeps: union, the outside ones; subtract,
## the first's outside and the second's inside, turned; intersect, the
## inside ones. Of coincident pieces one is kept or none.
## 7. Written as a new B-rep; an edge not used exactly twice, once each
## way, means the result is not closed: an error, never a broken solid.
## Boolean operations (combine's `op`).
pub let op_union: i64 = 0
pub let op_subtract: i64 = 1
pub let op_intersect: i64 = 2
## Piece classes.
let class_out: i64 = 0
let class_in: i64 = 1
let class_same: i64 = 2
let class_opposite: i64 = 3
## Where an original edge is cut, by parameter; `slack`, how far the cut
## may lie from where it is (it came from a tolerant edge or vertex), so its
## vertex merges that far.
struct Cut:
var edge: usize
var t: f64
var slack: f64 = 0.0
## A new edge: an interval of a carrier between merged vertices, lying
## across faces fa and fb (fb -1 for one face); `precision`, how far a
## traced carrier strays from the faces there (0: exact).
struct Section:
var edge: ShapeEdge
var fa: i64
var fb: i64
var precision: f64 = 0.0
## Original edge `edge`'s pieces lie across face `face` where inside it.
struct Imprint:
var face: usize
var edge: usize
## Faces of the two solids touching along a curve (tangent there, as a
## cylinder lying on a face); `same` when their outward normals agree (one
## body inside the other there), else they touch from outside.
struct Tangency:
var fa: usize
var fb: usize
var same: bool
## Two faces on one surface; `same` when their normals agree.
struct Coincident:
var fa: usize
var fb: usize
var same: bool
## The working state of one boolean.
struct Work:
var w: Shape
var faces_a: usize
var size: f64
var tol: f64
## Merged vertices, and each shape point's merged vertex.
var vertices: Growing[Vector3]
var point_vertex: Growing[i64]
var cuts: Growing[Cut]
var sections: Growing[Section]
var imprints: Growing[Imprint]
var coincident: Growing[Coincident]
## Final edges (vertices merged), and each original edge's pieces:
## piece_ids[piece_starts[e]..<piece_starts[e + 1]], from its start.
var finals: Growing[ShapeEdge]
var piece_ids: Growing[i64]
var piece_starts: Growing[usize]
var section_ids: Growing[i64]
## The first solid's faces the second meets (Split Face's chosen
## faces); empty: all of them.
var chosen: Growing[bool]
## Faces touching along sections (note_tangency).
var tangencies: Growing[Tangency] = Growing[Tangency]()
## B-spline faces touching another along a line no section follows
## (contact.lucb); `same` unused.
var contacts: Growing[Tangency] = Growing[Tangency]()
## Each merged vertex's zone: how far from it a point is still it
## (the work's own tolerance, or a tolerant entity's precision).
var zones: Growing[f64] = Growing[f64]()
## Each merged vertex's canonical point: of the points merged into it,
## one that was exact (the least slack) and of those the first,
## lexicographically: where the result puts it, one place whichever
## operand came first, and never a tolerant point where an exact one
## is there (the merging itself goes by the vertex as found).
var canonical: Growing[Vector3] = Growing[Vector3]()
var canonical_slack: Growing[f64] = Growing[f64]()
## Whether the operands are peers (a user's union, subtraction or
## intersection: the result the same either way round), or the first is
## a body a tool works on (its geometry kept where they meet).
var symmetric: bool = false
## Each final edge's slack: how far it may lie from the edges it stands
## for (a tolerant edge's precision, or a section's).
var final_slack: Growing[f64] = Growing[f64]()
func close():
self.w.close()
self.vertices.close()
self.point_vertex.close()
self.cuts.close()
self.sections.close()
self.imprints.close()
self.coincident.close()
self.tangencies.close()
self.contacts.close()
self.zones.close()
self.final_slack.close()
self.canonical.close()
self.canonical_slack.close()
self.finals.close()
self.piece_ids.close()
self.piece_starts.close()
self.section_ids.close()
self.chosen.close()
## The merged vertex at `p`.
func vertex(p: Vector3) -> i64!:
return try self.vertex_within(p, 0.0)
## The merged vertex at `p`, merging within `slack` too (a tolerant
## edge's or vertex's precision: Parasolid's tolerant modeling).
## Two points are one vertex when they are nearer than their zones
## together: each zone five tolerances, or a tolerant entity's
## precision; the vertex's zone grows to the larger. Of the vertices in
## reach the nearest is the one (the first of equals), not the first
## found.
func vertex_within(p: Vector3, slack: f64) -> i64!:
let zone = math.max(self.tol * 5.0, slack)
var best: i64 = -1
var best_distance = 0.0
for at in 0..<self.vertices.count:
let d = self.vertices.items[at].subtract(p).length()
if d <= zone + self.zones.items[at] and (best < 0 or d < best_distance):
best = (i64)at
best_distance = d
if best >= 0:
self.zones.items[(usize)best] = math.max(self.zones.items[(usize)best], zone)
# Between peers every merge goes to the canonical point; under a
# tool only a tolerant one (points further apart than the fine
# zone), so the body keeps its own points to the bit.
if (usize)best < self.canonical.count and (self.symmetric or p.subtract(self.canonical.items[(usize)best]).length() > self.tol * 10.0):
let held = self.canonical_slack.items[(usize)best]
if slack < held or (slack == held and lexicographic_before(p, self.canonical.items[(usize)best])):
self.canonical.items[(usize)best] = p
self.canonical_slack.items[(usize)best] = slack
return best
# Vertices pushed elsewhere (Stitch's) have no canonical point:
# theirs is where they are.
while self.canonical.count < self.vertices.count:
try self.canonical.push(self.vertices.items[self.canonical.count])
try self.canonical_slack.push(0.0)
try self.vertices.push(p)
try self.canonical.push(p)
try self.canonical_slack.push(slack)
try self.zones.push(zone)
return (i64)self.vertices.count - 1
## The merged vertex for a new edge's end at `p` across faces `fa` and
## `fb`: on a tolerant edge of either it merges within the edge's
## precision, so the sections either face makes there (each crossing
## it where its own surface does) meet at one vertex; and within the
## section's own precision (`own`, a traced curve's measured distance
## from the faces).
func section_end(p: Vector3, fa: usize, fb: usize, own: f64) -> i64!:
var slack = own
for f in [fa, fb]:
for use in self.w.face_uses(f):
let e = edge_index(use)
let precision = self.w.edge_slack_of(e)
if precision <= 0.0: continue
let edge = self.w.edges.items[e]
let t = try nearest_on(&self.w, edge.carrier, p, edge.t0, edge.t1)
if (try self.w.at(edge.carrier, t)).subtract(p).length() <= precision: slack = math.max(slack, precision)
return try self.vertex_within(p, slack)
## The tolerance to meet edge `e` by: the work's, or its precision
## when it is tolerant (crossings and boundary tests compare within ten
## of it).
func edge_tol(e: usize) -> f64:
return math.max(self.tol, self.w.edge_slack_of(e) * 0.1)
## The final edge for `edge` (vertices merged; `slack` how far it may lie
## from where it is, a tolerant edge's precision): an existing one with
## the same ends and middle, or a new one; and whether `edge` runs its
## way.
func final_edge(edge: ShapeEdge, slack: f64) -> (i64, bool)!:
let middle = try self.w.at(edge.carrier, (edge.t0 + edge.t1) * 0.5)
for at in 0..<self.finals.count:
let other = self.finals.items[at]
let same_ends = (other.start == edge.start and other.end == edge.end) or (other.start == edge.end and other.end == edge.start)
if not same_ends: continue
let reach = math.max(self.tol * 100.0, math.max(slack, self.final_slack.items[at]))
if (try self.w.at(other.carrier, (other.t0 + other.t1) * 0.5)).subtract(middle).length() > reach: continue
var forward = other.start == edge.start
if edge.start == edge.end:
# A closed edge: its way by the tangent in its middle.
let mine = (try self.w.tangent(edge.carrier, (edge.t0 + edge.t1) * 0.5)).multiply_scalar(1.0 if edge.t1 > edge.t0 else -1.0)
let theirs = (try self.w.tangent(other.carrier, (other.t0 + other.t1) * 0.5)).multiply_scalar(1.0 if other.t1 > other.t0 else -1.0)
forward = mine.dot(theirs) > 0.0
self.final_slack.items[at] = math.max(self.final_slack.items[at], slack)
return ((i64)at, forward)
try self.finals.push(edge)
try self.final_slack.push(slack)
return ((i64)self.finals.count - 1, true)
## Where merged vertex `v` goes in the result (its canonical point).
func placed(v: i64) -> Vector3:
if not self.symmetric: return self.vertices.items[(usize)v]
return self.canonical.items[(usize)v] if (usize)v < self.canonical.count else self.vertices.items[(usize)v]
func is_a(f: usize) -> bool:
return f < self.faces_a
## Whether point `a` comes before `b`: by x, then y, then z.
func lexicographic_before(a: Vector3, b: Vector3) -> bool:
if a.x != b.x: return a.x < b.x
if a.y != b.y: return a.y < b.y
return a.z < b.z
## A box holding face `f` of `w`, never short of it (a pair of faces whose
## boxes miss is never met). A plane's face lies within its boundary's box;
## a curved face can bulge past its boundary, so it takes its surface's
## extent there: a cylinder's or cone's band between the boundary's
## heights, a sphere's ball, a torus whole, a B-spline's control net.
func face_box(w: const Shape*, f: usize) -> (Vector3, Vector3)!:
var low = Vector3(1.0e300, 1.0e300, 1.0e300)
var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
for use in w.face_uses(f):
let (l, h) = try edge_box(w, edge_index(use))
low = lower(low, l)
high = upper(high, h)
let s = &w.surfaces.items[(usize)w.faces.items[f].surface]
if s.kind == surface_plane: return (low, high)
if s.kind == surface_spline:
low = Vector3(1.0e300, 1.0e300, 1.0e300)
high = Vector3(-1.0e300, -1.0e300, -1.0e300)
for p in s.points:
low = lower(low, p)
high = upper(high, p)
return (low, high)
if s.kind == surface_sphere:
let r = Vector3(s.radius, s.radius, s.radius)
return (s.origin.subtract(r), s.origin.add(r))
if s.kind == surface_torus:
# The ring's circle, widened by the tube.
let (l, h) = circle_box(s.origin, s.z, s.radius)
let tube = Vector3(s.angle, s.angle, s.angle)
return (l.subtract(tube), h.add(tube))
# A cylinder or cone between the boundary's lowest and highest heights
# (from its box's corners): the circles there hold the band between
# (a cone's points are blends of theirs).
var bottom = 1.0e300
var top = -1.0e300
for corner in 0..<8:
let p = Vector3(high.x if corner % 2 == 1 else low.x, high.y if (corner // 2) % 2 == 1 else low.y, high.z if corner >= 4 else low.z)
let height = p.subtract(s.origin).dot(s.z)
bottom = math.min(bottom, height)
top = math.max(top, height)
let slope = math.tan(s.angle) if s.kind == surface_cone else 0.0
let r0 = math.abs(s.radius + bottom * slope)
let r1 = math.abs(s.radius + top * slope)
let (l0, h0) = circle_box(s.origin.add(s.z.multiply_scalar(bottom)), s.z, r0)
let (l1, h1) = circle_box(s.origin.add(s.z.multiply_scalar(top)), s.z, r1)
return (lower(l0, l1), upper(h0, h1))
## A box holding edge `e` of `w`: a line's ends, an arc's whole circle or
## ellipse, a B-spline's control points (it lies in their hull).
func edge_box(w: const Shape*, e: usize) -> (Vector3, Vector3)!:
let edge = w.edges.items[e]
let c = w.carriers.items[(usize)edge.carrier]
if c.kind == curve_line:
let a = try w.at(edge.carrier, edge.t0)
let b = try w.at(edge.carrier, edge.t1)
return (lower(a, b), upper(a, b))
if c.kind == curve_circle or c.kind == curve_ellipse:
# Along each axis, origin +- |(a x_i, b y_i)|.
let reach = Vector3(math.sqrt(c.a * c.x.x * c.a * c.x.x + c.b * c.y.x * c.b * c.y.x),
math.sqrt(c.a * c.x.y * c.a * c.x.y + c.b * c.y.y * c.b * c.y.y),
math.sqrt(c.a * c.x.z * c.a * c.x.z + c.b * c.y.z * c.b * c.y.z))
return (c.origin.subtract(reach), c.origin.add(reach))
let (points, _, _, _) = w.spline_net(c.spline)
var low = Vector3(1.0e300, 1.0e300, 1.0e300)
var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
for p in points:
low = lower(low, p)
high = upper(high, p)
return (low, high)
## The box of the circle of `radius` about unit `axis` through `center`:
## along each axis e, center +- radius sqrt(1 - (axis . e)^2).
func circle_box(center: Vector3, axis: Vector3, radius: f64) -> (Vector3, Vector3):
let reach = Vector3(radius * math.sqrt(math.max(0.0, 1.0 - axis.x * axis.x)), radius * math.sqrt(math.max(0.0, 1.0 - axis.y * axis.y)),
radius * math.sqrt(math.max(0.0, 1.0 - axis.z * axis.z)))
return (center.subtract(reach), center.add(reach))
func lower(a: Vector3, b: Vector3) -> Vector3:
return Vector3(math.min(a.x, b.x), math.min(a.y, b.y), math.min(a.z, b.z))
func upper(a: Vector3, b: Vector3) -> Vector3:
return Vector3(math.max(a.x, b.x), math.max(a.y, b.y), math.max(a.z, b.z))
func boxes_meet(a: (Vector3, Vector3), b: (Vector3, Vector3), pad: f64) -> bool:
let (al, ah) = a
let (bl, bh) = b
return al.x <= bh.x + pad and bl.x <= ah.x + pad and al.y <= bh.y + pad and bl.y <= ah.y + pad and al.z <= bh.z + pad and bl.z <= ah.z + pad
## `source` appended to `into`: indices moved past what `into` has.
func append_shape(into: Shape*, source: const Shape*) -> !:
let points = (i64)into.points.count
let carriers = (i64)into.carriers.count
let edges = (i64)into.edges.count
let surfaces = (i64)into.surfaces.count
let splines = (i64)into.splines.count
let spline_points = into.spline_points.count
let spline_knots = into.spline_knots.count
for p in source.points.view(): try into.points.push(p)
for s in source.splines.view(): try into.splines.push(ShapeSpline(s.first + spline_points, s.count, s.knot_first + spline_knots, s.degree))
for p in source.spline_points.view(): try into.spline_points.push(p)
for w in source.spline_weights.view(): try into.spline_weights.push(w)
for k in source.spline_knots.view(): try into.spline_knots.push(k)
for c in source.carriers.view():
var moved = c
if moved.spline >= 0: moved.spline += splines
try into.carriers.push(moved)
for e in source.edges.view(): try into.edges.push(ShapeEdge(e.carrier + carriers, e.t0, e.t1, e.start + points, e.end + points))
# Tolerant edges and points keep their slack (none listed: exact).
while into.edge_slack.count < (usize)edges: try into.edge_slack.push(0.0)
for e in 0..<source.edges.count: try into.edge_slack.push(source.edge_slack_of(e))
while into.point_slack.count < (usize)points: try into.point_slack.push(0.0)
for p in 0..<source.points.count: try into.point_slack.push(source.point_slack_of(p))
for s in source.surfaces.view():
try into.surfaces.push(try Surface(s.kind, s.origin, s.x, s.z, s.radius, s.angle, s.points, s.weights, s.ku, s.kv, s.nu, s.nv, s.du, s.dv))
var uses = Growing[i64]()
defer uses.close()
for f in 0..<source.faces.count:
uses.clear()
for use in source.face_uses(f): try uses.push(use + edges if use > 0 else use - edges)
try into.add_face(source.faces.items[f].surface + surfaces, source.faces.items[f].sense, uses.view(), source.face_sizes(f), try into.add_name(source.face_name(f)))
## `a` combined with `b` by `op` (op_union, op_subtract, op_intersect);
## `symmetric` for peers (Work.symmetric), else `a` is the body a tool `b`
## works on.
pub func combine(a: const CadModel*, b: const CadModel*, op: i64, symmetric: bool = false) -> interop.Reference[CadModel]!:
var first = try shape_of(a)
let faces_a = first.faces.count
var second = try shape_of(b)
defer second.close()
try append_shape(&first, &second)
var work = Work(first, faces_a, 1.0, 1e-9, Growing[Vector3](), Growing[i64](), Growing[Cut](), Growing[Section](), Growing[Imprint](),
Growing[Coincident](), Growing[ShapeEdge](), Growing[i64](), Growing[usize](), Growing[i64](), Growing[bool]())
defer work.close()
work.symmetric = symmetric
var low = Vector3(1.0e300, 1.0e300, 1.0e300)
var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
for f in 0..<work.w.faces.count:
let (l, h) = try face_box(&work.w, f)
low = Vector3(math.min(low.x, l.x), math.min(low.y, l.y), math.min(low.z, l.z))
high = Vector3(math.max(high.x, h.x), math.max(high.y, h.y), math.max(high.z, h.z))
work.size = math.max(1e-6, high.subtract(low).length())
# Relative to the model's size, not the inputs' tolerances.
work.tol = work_tolerance(&work.w)
try coincide(&work)
for at in 0..<work.w.points.count: try work.point_vertex.push(try work.vertex_within(work.w.points.items[at], work.w.point_slack_of(at)))
try intersect_faces(&work)
try vertex_cuts(&work)
try cut_edges(&work)
var others = try new_others(&work)
defer others.close()
return try assemble(&work, op, &others)
## Steps 2: new edges where faces of the two solids meet.
func intersect_faces(work: Work*) -> !:
let w = &work.w
var lows = Growing[Vector3]()
defer lows.close()
var highs = Growing[Vector3]()
defer highs.close()
# Each face's widest edge slack: a tolerant face (put on another's
# surface by coincide.lucb) is met as far off as it may lie.
var slacks = Growing[f64]()
defer slacks.close()
for f in 0..<w.faces.count:
let (l, h) = try face_box(w, f)
try lows.push(l)
try highs.push(h)
var most = 0.0
for use in w.face_uses(f): most = math.max(most, w.edge_slack_of(edge_index(use)))
try slacks.push(most)
var curves = Growing[Carrier]()
defer curves.close()
var hits = Growing[Hit]()
defer hits.close()
var ts = Growing[f64]()
defer ts.close()
# Faces and edges stay as they are until the cuts are made.
var lookup = try new_lookup(w)
defer lookup.close()
for fa in 0..<work.faces_a:
if work.chosen.count > 0 and not work.chosen.items[fa]: continue
for fb in work.faces_a..<w.faces.count:
if not boxes_meet((lows.items[fa], highs.items[fa]), (lows.items[fb], highs.items[fb]), math.max(work.tol * 10.0, math.max(slacks.items[fa], slacks.items[fb]))): continue
let sa = w.faces.items[fa]
let sb = w.faces.items[fb]
curves.clear()
var met = meet_curves
if w.surfaces.items[(usize)sa.surface].kind == surface_spline or w.surfaces.items[(usize)sb.surface].kind == surface_spline:
met = try spline_coincidence(w, fa, fb, work.tol)
if met == meet_curves and not try spline_meet(w, fa, fb, work.tol, &curves): met = meet_march
else:
# Between peers the surfaces are met in an order of their
# own, so the curves come out the same either way round.
let first_surface = &w.surfaces.items[(usize)sa.surface]
let second_surface = &w.surfaces.items[(usize)sb.surface]
if work.symmetric and surface_before(second_surface, first_surface): met = try meet(second_surface, first_surface, work.tol, &curves)
else: met = try meet(first_surface, second_surface, work.tol, &curves)
if met == meet_march:
# Where both faces are, a little more.
let pad = Vector3(work.size * 0.01, work.size * 0.01, work.size * 0.01)
let la = lows.items[fa]
let lb = lows.items[fb]
let ha = highs.items[fa]
let hb = highs.items[fb]
let box_low = Vector3(math.max(la.x, lb.x), math.max(la.y, lb.y), math.max(la.z, lb.z)).subtract(pad)
let box_high = Vector3(math.min(ha.x, hb.x), math.min(ha.y, hb.y), math.min(ha.z, hb.z)).add(pad)
if work.symmetric and surface_before(&w.surfaces.items[(usize)sb.surface], &w.surfaces.items[(usize)sa.surface]): try marched(w, fb, fa, box_low, box_high, work.size, work.tol, &curves)
else: try marched(w, fa, fb, box_low, box_high, work.size, work.tol, &curves)
met = meet_curves
if met != meet_curves:
let same = (met == meet_same) == (sa.sense == sb.sense)
try work.coincident.push(Coincident(fa, fb, same))
try imprint(work, fa, fb)
try imprint(work, fb, fa)
continue
if curves.count == 0:
# No curve where a B-spline face meets the other: they may
# still touch (contact.lucb).
let spline_pair = w.surfaces.items[(usize)sa.surface].kind == surface_spline or w.surfaces.items[(usize)sb.surface].kind == surface_spline
if spline_pair and (try spline_contact(work, &lookup, fa, fb)) == contact_line: try work.contacts.push(Tangency(fa, fb, false))
continue
# Where curves of this pair cross each other (two ellipses where
# equal pipes cross, at the points the pipes touch): one vertex
# each, which both curves are cut at.
let first_carrier = w.carriers.count
for carrier in curves.view(): _ = try w.add_carrier(carrier)
var crossing_points = Growing[Vector3]()
defer crossing_points.close()
try mutual_crossings(work, (i64)first_carrier, curves.count, &crossing_points)
for index in 0..<curves.count:
let carrier = curves.items[index]
let c = (i64)(first_carrier + index)
var lowest = 0.0
var highest = 2.0 * math.pi
var closed = carrier.kind != curve_line
if carrier.kind == curve_spline:
# A traced curve: its knots' range; closed when it ends
# where it starts.
highest = 1.0
closed = (try w.at(c, 0.0)).subtract(try w.at(c, 1.0)).length() <= work.tol * 10.0
if carrier.kind == curve_line:
# The line across the two faces' boxes, and a margin.
lowest = 1.0e300
highest = -1.0e300
let al = lows.items[fa]
let ah = highs.items[fa]
for corner in 0..<8:
let p = Vector3(ah.x if corner % 2 == 1 else al.x, ah.y if (corner // 2) % 2 == 1 else al.y, ah.z if corner >= 4 else al.z)
let t = p.subtract(carrier.origin).dot(carrier.x)
lowest = math.min(lowest, t)
highest = math.max(highest, t)
lowest -= work.size * 0.1
highest += work.size * 0.1
hits.clear()
ts.clear()
# The curve's box, to pass over edges far from it (a plate's
# other holes) without sampling them.
var curve_low = Vector3(1e300, 1e300, 1e300)
var curve_high = Vector3(-1e300, -1e300, -1e300)
for at in 0..<129:
let q = try w.at(c, lowest + (highest - lowest) * (f64)at / 128.0)
curve_low = lower(curve_low, q)
curve_high = upper(curve_high, q)
let curve_pad = curve_high.subtract(curve_low).length() / 64.0 + work.size * 1e-6
let cuts_before = work.cuts.count
let sections_before = work.sections.count
let imprints_before = work.imprints.count
for side in 0..<2:
let f = fa if side == 0 else fb
let other = fb if side == 0 else fa
for use in w.face_uses(f):
let e = edge_index(use)
if not boxes_meet((curve_low, curve_high), (lookup.edge_low.items[e], lookup.edge_high.items[e]), curve_pad + work.edge_tol(e) * 10.0): continue
let before = hits.count
try crossings(w, c, lowest, highest, e, work.size, work.edge_tol(e), &hits)
# A crossing cuts the boundary edge only where the
# other face is: elsewhere no section ends there,
# and the cut would leave a stray vertex on the edge.
for at in before..<hits.count:
if try lookup_contains(&lookup, w, other, try w.at(c, hits.items[at].t), work.tol) != outside: try work.cuts.push(Cut(e, hits.items[at].s, w.edge_slack_of(e)))
for hit in hits.view(): try ts.push(hit.t)
for p in crossing_points.view():
let t = try nearest_on(w, c, p, lowest, highest)
if (try w.at(c, t)).subtract(p).length() <= work.tol * 10.0: try ts.push(t)
sort.sort(ts.items[..<ts.count])
try add_sections(work, &lookup, c, closed, lowest, highest, ts.view(), fa, fb)
# A curve that leaves no section (it grazes a face's
# boundary, a plane touching a rounded face's edge at its
# extreme) leaves no cut either: its crossings would split
# the edge into a sliver no section closes.
if work.sections.count == sections_before and work.imprints.count == imprints_before: work.cuts.count = cuts_before
## The points where the `count` curves from carrier `first` on cross one
## another, onto `out`: each curve sampled, the other's nearest point found,
## and the sample stretches where that distance falls to a minimum narrowed
## by golden section. Lines are left out (their crossings are boundary
## crossings already).
func mutual_crossings(work: Work*, first: i64, count: usize, out: Growing[Vector3]*) -> !:
let w = &work.w
if count < 2: return
let samples = 128
for i in 0..<count:
let a = first + (i64)i
let ka = w.carriers.items[(usize)a].kind
if ka == curve_line: continue
let high_a = 1.0 if ka == curve_spline else 2.0 * math.pi
for j in i + 1..<count:
let b = first + (i64)j
let kb = w.carriers.items[(usize)b].kind
if kb == curve_line: continue
let high_b = 1.0 if kb == curve_spline else 2.0 * math.pi
var previous = 1e300
var before = 1e300
for k in 0..<samples + 2:
let t = high_a * (f64)k / (f64)samples
let p = try w.at(a, math.min(t, high_a))
let d = (try w.at(b, try nearest_on(w, b, p, 0.0, high_b))).subtract(p).length()
# A minimum at the previous sample: narrow its stretch.
if k >= 2 and previous <= before and previous <= d and previous < work.size * 0.05:
let found = try narrowed(w, a, b, high_a * (f64)(k - 2) / (f64)samples, math.min(t, high_a), high_b)
if found.y <= work.tol * 10.0:
var known = false
for q in out.view(): known = known or q.subtract(found_point(w, a, found.x)).length() <= work.tol * 10.0
if not known: try out.push(try w.at(a, found.x))
before = previous
previous = d
func found_point(w: const Shape*, c: i64, t: f64) -> Vector3:
return w.at(c, t) catch failure: recover Vector3(1e300, 1e300, 1e300)
## The parameter of curve `a` in [low, high] nearest curve `b` (x) and that
## distance (y), by golden section.
func narrowed(w: const Shape*, a: i64, b: i64, low: f64, high: f64, high_b: f64) -> Vector3!:
var l = low
var h = high
let ratio = 0.6180339887498949
for _ in 0..<80:
let m1 = h - (h - l) * ratio
let m2 = l + (h - l) * ratio
let p1 = try w.at(a, m1)
let p2 = try w.at(a, m2)
let d1 = (try w.at(b, try nearest_on(w, b, p1, 0.0, high_b))).subtract(p1).length()
let d2 = (try w.at(b, try nearest_on(w, b, p2, 0.0, high_b))).subtract(p2).length()
if d1 < d2: h = m2
else: l = m1
let t = (l + h) * 0.5
let p = try w.at(a, t)
return Vector3(t, (try w.at(b, try nearest_on(w, b, p, 0.0, high_b))).subtract(p).length(), 0.0)
## The stretches of carrier `c` between consecutive crossings `ts` that lie
## inside both faces, as sections.
func add_sections(work: Work*, lookup: Lookup*, c: i64, closed: bool, low: f64, high: f64, ts: const f64[], fa: usize, fb: usize) -> !:
let w = &work.w
var bounds = Growing[f64]()
defer bounds.close()
for t in ts:
if bounds.count > 0 and (try w.at(c, t)).subtract(try w.at(c, bounds.items[bounds.count - 1])).length() <= work.tol * 10.0: continue
try bounds.push(t)
if closed:
if bounds.count > 1 and (try w.at(c, bounds.items[0])).subtract(try w.at(c, bounds.items[bounds.count - 1])).length() <= work.tol * 10.0:
bounds.count -= 1
if bounds.count == 0: try bounds.push(low if w.carriers.items[(usize)c].kind == curve_spline else try seam_parameter(work, c, fa, fb))
try bounds.push(bounds.items[0] + (high - low))
let count = bounds.count
if count < 2: return
for at in 0..<count - 1:
let t0 = bounds.items[at]
let t1 = bounds.items[at + 1]
var halfway = (t0 + t1) * 0.5
if halfway > high and w.carriers.items[(usize)c].kind == curve_spline: halfway -= high - low
let middle = try w.at(c, halfway)
let ia = try lookup_contains(lookup, w, fa, middle, work.tol)
let ib = try lookup_contains(lookup, w, fb, middle, work.tol)
if ia == outside or ib == outside or (ia == on_boundary and ib == on_boundary): continue
# A closed traced curve's stretch may run past its end: wrap it.
if t1 > high and w.carriers.items[(usize)c].kind == curve_spline:
try add_wrapped(work, c, t0, t1, low, high, fa, fb, try traced_deviation(work, c, fa, fb, t0, t1, low, high))
continue
# Along a boundary edge of one face: that edge, cut at the stretch's
# ends, lies across the other face (no second edge on the same line).
if ia == on_boundary or ib == on_boundary:
let owner = fa if ia == on_boundary else fb
let other = fb if ia == on_boundary else fa
var found = false
for use in w.face_uses(owner):
let e = edge_index(use)
let edge = w.edges.items[e]
if not try same_curve(w, c, e, work.edge_tol(e)): continue
let s_mid = try nearest_on(w, edge.carrier, middle, edge.t0, edge.t1)
if (try w.at(edge.carrier, s_mid)).subtract(middle).length() > work.edge_tol(e) * 10.0: continue
try work.cuts.push(Cut(e, try nearest_on(w, edge.carrier, try w.at(c, t0), edge.t0, edge.t1)))
try work.cuts.push(Cut(e, try nearest_on(w, edge.carrier, try w.at(c, t1), edge.t0, edge.t1)))
try work.imprints.push(Imprint(other, e))
try note_tangency(work, fa, fb, c, t0, t1)
found = true
break
if found: continue
# Not along an edge but within the tolerance of one all the way:
# the faces graze there (a plane at a rounded face's extreme).
if try hugs_boundary(work, lookup, c, t0, t1, owner): continue
let precision = try traced_deviation(work, c, fa, fb, t0, t1, low, high)
let start = try work.section_end(try w.at(c, t0), fa, fb, precision)
let end = try work.section_end(try w.at(c, t1), fa, fb, precision)
# Ends merged into one vertex: nothing between them (a closed curve
# once around is its own loop).
if start == end and not (closed and count == 2): continue
try work.sections.push(Section(ShapeEdge(c, t0, t1, start, end), (i64)fa, (i64)fb, precision))
try note_tangency(work, fa, fb, c, t0, t1)
## How far traced curve `c` (a B-spline fitted to where faces `fa` and
## `fb` meet) strays from their surfaces over t0..t1 (past `high`, from
## `low` again: a closed curve's stretch through its end): the largest
## distance at 17 points along it. An exact curve's is 0. It is the
## section's precision: its ends merge within it, and its edge keeps it.
func traced_deviation(work: Work*, c: i64, fa: usize, fb: usize, t0: f64, t1: f64, low: f64, high: f64) -> f64!:
let w = &work.w
if w.carriers.items[(usize)c].kind != curve_spline: return 0.0
var deviation = 0.0
var seeds = [Vector3(0.5, 0.5, 0.0), Vector3(0.5, 0.5, 0.0)]
for k in 0..<17:
var t = t0 + (t1 - t0) * (f64)k / 16.0
if t > high: t -= high - low
let p = try w.at(c, t)
for side in 0..<(usize)2: deviation = math.max(deviation, try surface_gap(w, fa if side == 0 else fb, p, &seeds[side], k == 0))
return deviation
## Whether stretch t0..t1 of curve `c` lies on face `f`'s boundary within
## ten tolerances at nine points along it.
func hugs_boundary(work: Work*, lookup: Lookup*, c: i64, t0: f64, t1: f64, f: usize) -> bool!:
for k in 1..<10:
let p = try work.w.at(c, t0 + (t1 - t0) * (f64)k / 10.0)
if try lookup_contains(lookup, &work.w, f, p, work.tol * 10.0) != on_boundary: return false
return true
## Whether faces `fa` and `fb` touch along section `c` (t0..t1) rather
## than cross it, noted as a tangency. At a quarter, half and three quarters
## along, their normals must be parallel (to a thousandth of a radian, as a
## traced B-spline's are), and the faces must part to one side: stepping off
## the section across face `fa` both ways, a little and further, its points
## stay on one side of `fb`'s surface. That is the Dupin indicatrix test,
## made by measuring: faces tangent along a curve have no relative curvature
## along it and a definite one across it, while faces crossing at a shallow
## angle (normals nearly parallel too) fall on either side.
func note_tangency(work: Work*, fa: usize, fb: usize, c: i64, t0: f64, t1: f64) -> !:
let w = &work.w
# Two planes meet along a line only by crossing: lying together within
# P they were made one before (coincide.lucb), so a shallow angle
# between them is a crossing, whatever their normals say.
if w.surfaces.items[(usize)w.faces.items[fa].surface].kind == surface_plane and w.surfaces.items[(usize)w.faces.items[fb].surface].kind == surface_plane: return
var agree: f64 = 0.0
for fraction in [0.25, 0.5, 0.75]:
let t = t0 + (t1 - t0) * fraction
let p = try w.at(c, t)
let na = try w.face_normal(fa, p)
let nb = try w.face_normal(fb, p)
let dot = na.dot(nb)
if math.abs(dot) < 1.0 - 5e-7: return
agree = dot
let along = w.tangent(c, t) catch failure: recover Vector3()
let sideways = na.cross(along).normalized() catch failure: recover Vector3()
if sideways.length() == 0.0: continue
for reach in [work.size * 1e-3, work.size * 1e-2]:
var sides: f64[2] = [0.0, 0.0]
for k in 0..<(usize)2:
let q = try nearest_on_surface(w, fa, p.add(sideways.multiply_scalar(reach if k == 0 else -reach)))
sides[k] = q.subtract(try nearest_on_surface(w, fb, q)).dot(nb)
if sides[0] * sides[1] < 0.0 and math.min(math.abs(sides[0]), math.abs(sides[1])) > work.tol * 10.0: return
try work.tangencies.push(Tangency(fa, fb, agree > 0.0))
## A stretch of closed traced curve `c` (parameters low..high) from t0
## past its end to t1: two sections meeting at its ends' vertex.
func add_wrapped(work: Work*, c: i64, t0: f64, t1: f64, low: f64, high: f64, fa: usize, fb: usize, precision: f64) -> !:
let w = &work.w
let start = try work.section_end(try w.at(c, t0), fa, fb, precision)
let seam = try work.section_end(try w.at(c, high), fa, fb, precision)
let end = try work.section_end(try w.at(c, t1 - (high - low)), fa, fb, precision)
if start != seam: try work.sections.push(Section(ShapeEdge(c, t0, high, start, seam), (i64)fa, (i64)fb, precision))
if seam != end: try work.sections.push(Section(ShapeEdge(c, low, t1 - (high - low), seam, end), (i64)fa, (i64)fb, precision))
## Face `onto` and coincident face `source`: where `source`'s boundary
## crosses `onto`'s, both cut; `source`'s boundary inside `onto` imprints it.
func imprint(work: Work*, onto: usize, source: usize) -> !:
let w = &work.w
var hits = Growing[Hit]()
defer hits.close()
for use in w.face_uses(source):
let e = edge_index(use)
let edge = w.edges.items[e]
for other in w.face_uses(onto):
let o = edge_index(other)
hits.clear()
try crossings(w, edge.carrier, edge.t0, edge.t1, o, work.size, math.max(work.edge_tol(e), work.edge_tol(o)), &hits)
for hit in hits.view():
let slack = math.max(w.edge_slack_of(e), w.edge_slack_of(o))
try work.cuts.push(Cut(e, hit.t, slack))
try work.cuts.push(Cut(o, hit.s, slack))
try work.imprints.push(Imprint(onto, e))
## A vertex lying inside an edge cuts it there, so faces meeting along it
## share the vertex (OpenCASCADE's vertex/edge interference): a new edge's
## end on an edge it does not cross, one solid's vertex on an edge of the
## other, or where an edge is cut, on edges lying along it.
func vertex_cuts(work: Work*) -> !:
let w = &work.w
var lows = Growing[Vector3]()
defer lows.close()
var highs = Growing[Vector3]()
defer highs.close()
let pad = work.tol * 10.0
var widest_zone = 0.0
for zone in work.zones.view(): widest_zone = math.max(widest_zone, zone)
for e in 0..<w.edges.count:
var low = Vector3(1.0e300, 1.0e300, 1.0e300)
var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
for step in 0..<17:
let p = try w.edge_at(e, (f64)step / 16.0)
low = Vector3(math.min(low.x, p.x), math.min(low.y, p.y), math.min(low.z, p.z))
high = Vector3(math.max(high.x, p.x), math.max(high.y, p.y), math.max(high.z, p.z))
# Arcs bulge between samples: a sixteenth of their reach more; and a
# tolerant vertex reaches as far as its zone.
let bulge = high.subtract(low).length() * 0.02 + math.max(math.max(pad, work.edge_tol(e) * 10.0), widest_zone)
try lows.push(low.subtract(Vector3(bulge, bulge, bulge)))
try highs.push(high.add(Vector3(bulge, bulge, bulge)))
# The ends of new edges, and every vertex of both solids (one solid's
# vertex on the other's edge: edges lying along each other).
var done = Growing[bool]()
defer done.close()
for _ in work.vertices.view(): try done.push(false)
var candidates = Growing[i64]()
defer candidates.close()
for section in work.sections.view():
try candidates.push(section.edge.start)
try candidates.push(section.edge.end)
for v in work.point_vertex.view(): try candidates.push(v)
# Where edges are cut too: an edge lying along a cut one is cut alike.
for at in 0..<work.cuts.count:
let cut = work.cuts.items[at]
try candidates.push(try work.vertex_within(try w.at(w.edges.items[cut.edge].carrier, cut.t), cut.slack))
try done.push(false)
for v in candidates.view():
if done.items[(usize)v]: continue
done.items[(usize)v] = true
let p = work.vertices.items[(usize)v]
for e in 0..<w.edges.count:
let l = lows.items[e]
let h = highs.items[e]
if p.x < l.x or p.y < l.y or p.z < l.z or p.x > h.x or p.y > h.y or p.z > h.z: continue
let edge = w.edges.items[e]
# An edge's own ends cut nothing.
if work.point_vertex.items[(usize)edge.start] == v or work.point_vertex.items[(usize)edge.end] == v: continue
let t = try nearest_on(w, edge.carrier, p, edge.t0, edge.t1)
# Within the edge's reach, or the vertex's own (a tolerant one).
if (try w.at(edge.carrier, t)).subtract(p).length() > math.max(math.max(pad, work.edge_tol(e) * 10.0), work.zones.items[(usize)v]): continue
try work.cuts.push(Cut(e, t, work.zones.items[(usize)v]))
## Step 3: every original edge cut where it was crossed, into final edges.
func cut_edges(work: Work*) -> !:
let w = &work.w
var ts = Growing[f64]()
defer ts.close()
var slacks = Growing[f64]()
defer slacks.close()
try work.piece_starts.push(0)
for e in 0..<w.edges.count:
let edge = w.edges.items[e]
ts.clear()
slacks.clear()
let span = edge.t1 - edge.t0
for cut in work.cuts.view():
if cut.edge != e: continue
let f = (cut.t - edge.t0) / span
if not (f > 1e-9 and f < 1.0 - 1e-9): continue
# In order along the edge, ties the widest slack first (one
# order, whatever order the cuts came in; the tolerant cut makes
# the vertex the others then merge into).
var at = ts.count
try ts.push(f)
try slacks.push(cut.slack)
while at > 0 and (ts.items[at - 1] > f or (ts.items[at - 1] == f and slacks.items[at - 1] < cut.slack)):
ts.items[at] = ts.items[at - 1]
slacks.items[at] = slacks.items[at - 1]
at -= 1
ts.items[at] = f
slacks.items[at] = cut.slack
var previous_fraction = 0.0
var previous_vertex = work.point_vertex.items[(usize)edge.start]
let last_vertex = work.point_vertex.items[(usize)edge.end]
for at in 0..<ts.count + 1:
let fraction = ts.items[at] if at < ts.count else 1.0
let vertex = (try work.vertex_within(try w.edge_at(e, fraction), math.max(w.edge_slack_of(e), slacks.items[at]))) if at < ts.count else last_vertex
# Cuts that merge into a vertex already there cut nothing.
if at < ts.count and (vertex == previous_vertex or vertex == last_vertex): continue
if vertex == previous_vertex and fraction - previous_fraction < 1e-9: continue
let piece = ShapeEdge(edge.carrier, edge.t0 + span * previous_fraction, edge.t0 + span * fraction, previous_vertex, vertex)
let (id, forward) = try work.final_edge(piece, w.edge_slack_of(e))
try work.piece_ids.push((id + 1) * (1 if forward else -1))
previous_fraction = fraction
previous_vertex = vertex
try work.piece_starts.push(work.piece_ids.count)
for section in work.sections.view():
let (id, forward) = try work.final_edge(section.edge, section.precision)
try work.section_ids.push((id + 1) * (1 if forward else -1))