dymokomi/luce-cad
Source of release 0.9.3
0.9.3 / src / modeling / face_moves.lucb
## Direct modeling's local face operations, built without booleans as
## Parasolid's local operations are: chosen faces take new surfaces (moved,
## turned, offset, or another face's) and the body keeps its topology.
## Every vertex on a chosen face is found again where the surfaces of its
## faces now meet (Newton on their signed distances, the least move from
## where it was), and every edge on a chosen face again where its two
## faces' surfaces meet (intersect.lucb; between two planes, the line
## through its new ends). Neighbors so extend or shrink to the moved faces.
##
## The topology must hold: an edge that would vanish or turn round, a
## corner whose faces no longer meet in a point, a face that would turn
## inside out, or a curved neighbor tangent to a moved face (which no
## longer meets it) is an error saying so, never a broken solid.
## How a face's surface changes (FaceMove.kind).
pub let move_translate: i64 = 0
pub let move_rotate: i64 = 1
pub let move_offset: i64 = 2
pub let move_replace: i64 = 3
## A change of surface for the chosen faces: translate by `vector`;
## rotate by `angle` about the line through `origin` along unit `axis`;
## offset by `distance` along each face's outward normal; or replace by
## another surface (substitute's `targets`).
pub struct FaceMove:
pub var kind: i64
pub var vector: Vector3
pub var origin: Vector3
pub var axis: Vector3
pub var angle: f64
pub var distance: f64
## Point `p` as the move takes it (a rigid move; an offset or a
## replacement leaves points).
func point(p: Vector3) -> Vector3:
if self.kind == move_translate: return p.add(self.vector)
if self.kind == move_rotate: return self.origin.add(p.subtract(self.origin).rotated_about(self.axis, self.angle))
return p
## Direction `d` as the move takes it.
func direction(d: Vector3) -> Vector3:
if self.kind == move_rotate: return d.rotated_about(self.axis, self.angle)
return d
## Face `f`'s surface as `m` moves it: a rigid move of its frame (and net),
## or its offset `distance` along the face's outward normal (a plane
## moved, a cylinder's, cone's, sphere's or torus's radius changed).
func moved_surface(w: const Shape*, f: usize, m: const FaceMove*, distance: f64) -> Surface!:
let face = w.faces.items[f]
let s = &w.surfaces.items[(usize)face.surface]
if m.kind == move_offset:
# Outward is the surface's normal when the face runs with it.
let d = distance if face.sense else -distance
if s.kind == surface_spline: return try offset_spline(s, d, w.tolerance)
if s.kind == surface_plane:
return try Surface(s.kind, s.origin.add(s.z.multiply_scalar(d)), s.x, s.z, s.radius, s.angle, s.points, s.weights, s.ku, s.kv, s.nu, s.nv, s.du, s.dv)
if s.kind == surface_torus:
if s.angle + d <= w.tolerance: error(invalid, "the offset is larger than the torus's tube")
return try Surface(s.kind, s.origin, s.x, s.z, s.radius, s.angle + d, s.points, s.weights, s.ku, s.kv, s.nu, s.nv, s.du, s.dv)
# A cone's radius at its origin moves by d / cos(angle).
let grown = s.radius + (d / math.cos(s.angle) if s.kind == surface_cone else d)
if grown <= w.tolerance: error(invalid, "the offset is larger than the face's radius")
return try Surface(s.kind, s.origin, s.x, s.z, grown, s.angle, s.points, s.weights, s.ku, s.kv, s.nu, s.nv, s.du, s.dv)
var net = Growing[Vector3]()
defer net.close()
for p in s.points: try net.push(m.point(p))
return try Surface(s.kind, m.point(s.origin), m.direction(s.x), m.direction(s.z), s.radius, s.angle, net.view(), s.weights, s.ku, s.kv, s.nu, s.nv, s.du, s.dv)
## A surface record of its own with `s`'s geometry.
func surface_copy(s: const Surface*) -> Surface!:
return 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)
## The parameters of B-spline `s`'s point nearest `p`: inverted when `p`
## lies on it, else searched for.
func nearest_uv(s: const Surface*, p: Vector3, tol: f64) -> Vector3!:
let on = project(*s, p, Vector3(0.5, 0.5, 0.0), tol) catch failure:
_ = failure
return try nearest_parameters(*s, p, Vector3(0.5, 0.5, 0.0), true)
return on
## `p`'s signed distance from `s` (along its normal) and that normal. `p`
## may lie well off a B-spline surface (a face's middle, a vertex moving):
## its nearest point is searched for (a lattice of starts, then Newton),
## not inverted as a point on it, which refuses points off the surface.
func signed_gap(s: const Surface*, p: Vector3, tol: f64) -> (f64, Vector3)!:
if s.kind == surface_spline:
let uv = try nearest_uv(s, p, tol)
let q = try evaluate(*s, uv)
let n = try normal_at(s, q, tol)
return (p.subtract(q).dot(n), n)
let d = p.subtract(s.origin)
let n = try normal_at(s, p, tol)
if s.kind == surface_plane: return (d.dot(s.z), s.z)
if s.kind == surface_sphere: return (d.length() - s.radius, n)
let h = d.dot(s.z)
let radial = math.sqrt(math.max(0.0, d.dot(d) - h * h))
if s.kind == surface_cylinder: return (radial - s.radius, n)
if s.kind == surface_cone: return ((radial - (s.radius + h * math.tan(s.angle))) * math.cos(s.angle), n)
let ring = radial - s.radius
return (math.sqrt(ring * ring + h * h) - s.angle, n)
## `signed_gap` along a run of nearby points: a B-spline's nearest point
## searched from `seed` (the last one's parameters, updated) first.
func gap_along(s: const Surface*, p: Vector3, tol: f64, seed: Vector3*) -> (f64, Vector3)!:
if s.kind != surface_spline: return try signed_gap(s, p, tol)
var uv = try nearest_parameters(*s, p, *seed, false)
var q = try evaluate(*s, uv)
var n = try normal_at(s, q, tol)
# Not a foot point (the start slid to a domain edge, a fold): the
# whole search.
let off = p.subtract(q)
if off.subtract(n.multiply_scalar(off.dot(n))).length() > tol * 10.0:
uv = try nearest_uv(s, p, tol)
q = try evaluate(*s, uv)
n = try normal_at(s, q, tol)
*seed = uv
return (p.subtract(q).dot(n), n)
## The start of gap_along's run at `p`: a B-spline's nearest parameters
## (searched whole), anything for another surface.
func seed_of(s: const Surface*, p: Vector3, tol: f64) -> Vector3!:
return (try nearest_uv(s, p, tol)) if s.kind == surface_spline else Vector3()
## Where the surfaces `surfaces` of `w` meet nearest `seed`: Gauss-Newton
## on their signed distances, each step the least move that zeroes them to
## first order (so with two surfaces the point slides along their curve),
## from the seed projected onto them in turn first (projected_seed).
## An error when they no longer meet there.
func corner_point(w: const Shape*, surfaces: const i64[], seed: Vector3) -> Vector3!:
let count = surfaces.length
var x = try projected_seed(w, surfaces, seed)
var rows: f64[24]
var residual: f64[8]
for _ in 0..<60:
var worst = 0.0
for at in 0..<count:
let (gap, n) = try signed_gap(&w.surfaces.items[(usize)surfaces[at]], x, w.tolerance)
residual[at] = gap
rows[at * 3] = n.x
rows[at * 3 + 1] = n.y
rows[at * 3 + 2] = n.z
worst = math.max(worst, math.abs(gap))
if worst <= w.tolerance * 0.01: return x
# (J Jᵀ + μI) z = r, step -Jᵀ z.
var a: f64[64]
for i in 0..<count:
for j in 0..<count:
a[i * count + j] = rows[i * 3] * rows[j * 3] + rows[i * 3 + 1] * rows[j * 3 + 1] + rows[i * 3 + 2] * rows[j * 3 + 2] + (1e-12 if i == j else 0.0)
var z: f64[8]
for i in 0..<count: z[i] = residual[i]
if not solve_small(a[..<count * count], z[..<count], count): break
var step = Vector3()
for i in 0..<count: step = step.add(Vector3(rows[i * 3], rows[i * 3 + 1], rows[i * 3 + 2]).multiply_scalar(z[i]))
x = x.subtract(step)
var worst = 0.0
for at in 0..<count:
let (gap, _) = try signed_gap(&w.surfaces.items[(usize)surfaces[at]], x, w.tolerance)
worst = math.max(worst, math.abs(gap))
if worst > w.tolerance * 10.0: error(invalid, "the faces at a corner no longer meet in one point: the move changes the body's shape too much")
return x
## Whether edge `e` of `w` is a seam: its one face uses it both ways.
func seam_edge(w: const Shape*, e: usize) -> bool!:
let f = w.sides.items[e * 2] if w.sides.items[e * 2] >= 0 else w.sides.items[e * 2 + 1]
if f < 0: return false
var uses = 0
for use in w.face_uses((usize)f):
if edge_index(use) == e: uses += 1
return uses > 1
## How far point `x` lies from the farthest of the surfaces `surfaces`.
func corner_gap(w: const Shape*, surfaces: const i64[], x: Vector3) -> f64!:
var worst = 0.0
for s in surfaces:
let (gap, _) = try signed_gap(&w.surfaces.items[(usize)s], x, w.tolerance)
worst = math.max(worst, math.abs(gap))
return worst
## `seed` projected onto the surfaces `surfaces` of `w` one after another,
## round after round, until they nearly all pass through it: surfaces that
## meet tangentially there (a top moved with its fillet) leave Gauss-Newton
## a near-singular system far from the corner, where its steps can land
## anywhere (on a cylinder's axis); projections close in on it steadily.
## Where a surface has no nearest point (on an axis), the seed as it is.
func projected_seed(w: const Shape*, surfaces: const i64[], seed: Vector3) -> Vector3!:
var x = seed
for _ in 0..<40:
var worst = 0.0
for s in surfaces:
let (gap, n) = signed_gap(&w.surfaces.items[(usize)s], x, w.tolerance) catch failure:
_ = failure
return x
x = x.subtract(n.multiply_scalar(gap))
worst = math.max(worst, math.abs(gap))
if worst <= w.tolerance: return x
return x
## Solve the `n` x `n` system `a` z = `z` in place (Gaussian elimination
## with partial pivoting); false when it is singular.
func solve_small(a: f64[], z: f64[], n: usize) -> bool:
for col in 0..<n:
var pivot = col
for row in col + 1..<n:
if math.abs(a[row * n + col]) > math.abs(a[pivot * n + col]): pivot = row
if math.abs(a[pivot * n + col]) < 1e-14: return false
if pivot != col:
for k in 0..<n:
let swap = a[col * n + k]
a[col * n + k] = a[pivot * n + k]
a[pivot * n + k] = swap
let swap = z[col]
z[col] = z[pivot]
z[pivot] = swap
for row in col + 1..<n:
let f = a[row * n + col] / a[col * n + col]
for k in col..<n: a[row * n + k] -= f * a[col * n + k]
z[row] -= f * z[col]
var row = n
while row > 0:
row -= 1
var sum = z[row]
for k in row + 1..<n: sum -= a[row * n + k] * z[k]
z[row] = sum / a[row * n + row]
return true
## `w` with faces `faces` moved by `m`: their surfaces replaced (by
## `targets`, one per face, for move_replace, with `senses`; an offset by
## `distances`, one per face, or `m.distance` when it is empty), every
## vertex and edge on them found again, checked, as a new model.
func substitute(w: Shape*, faces: const usize[], m: const FaceMove*, targets: const Surface[], senses: const bool[], distances: const f64[], open: bool = false) -> interop.Reference[CadModel]!:
let moved_count = faces.length
if moved_count == 0: error(invalid, "pick the faces to move")
var moved = Growing[bool]()
defer moved.close()
try moved.fill(w.faces.count, false)
for f in faces: moved.items[f] = true
# Curved neighbors tangent to a moved face no longer meet it.
try refuse_tangent_neighbors(w, moved.view())
# Where each vertex was, to judge each edge's way after.
var old_points = try copied_points(w)
defer old_points.close()
# B-spline neighbors carried on past their ends, so a moved face going
# past one still meets it (and its corners are found on it).
try extend_neighbors(w, moved.view(), m, distances)
for at in 0..<moved_count:
let f = faces[at]
let distance = distances[at] if distances.length > 0 else m.distance
let surface = (try surface_copy(&targets[at])) if m.kind == move_replace else (try moved_surface(w, f, m, distance))
try w.surfaces.push(surface)
w.faces.items[f].surface = (i64)w.surfaces.count - 1
if m.kind == move_replace: w.faces.items[f].sense = senses[at]
# Each vertex's surfaces, from the faces of its edges.
var around = Growing[i64]()
defer around.close()
try around.fill(w.points.count * 8, -1)
for e in 0..<w.edges.count:
let edge = w.edges.items[e]
for side in 0..<(usize)2:
let f = w.sides.items[e * 2 + side]
if f < 0: continue
for v in [edge.start, edge.end]: try note_face(w, &around, v, f)
var surfaces = Growing[i64]()
defer surfaces.close()
for v in 0..<w.points.count:
surfaces.clear()
var touched = false
for k in 0..<(usize)8:
let f = around.items[v * 8 + k]
if f < 0: break
if moved.items[(usize)f]: touched = true
let s = w.faces.items[(usize)f].surface
if not (try same_surface_listed(w, surfaces.view(), s)): try surfaces.push(s)
if not touched: continue
if m.kind == move_translate or m.kind == move_rotate:
# Every face rigidly moved: the vertex moves with them.
if all_moved(w, &around, v, moved.view()):
w.points.items[v] = m.point(w.points.items[v])
continue
w.points.items[v] = try corner_point(w, surfaces.view(), w.points.items[v])
# A corner where offsets fitted to the tolerance meet nearly
# tangentially (a G2 corner patch and its strips) is found within
# ten tolerances: it keeps how far it strays, as a tolerant vertex.
let strays = try corner_gap(w, surfaces.view(), w.points.items[v])
if strays > w.tolerance:
while w.point_slack.count <= v: try w.point_slack.push(0.0)
w.point_slack.items[v] = math.max(w.point_slack.items[v], strays * 1.5)
# Edges on moved faces: carriers again; the rest: their intervals.
for e in 0..<w.edges.count:
let edge = w.edges.items[e]
# An edge no face uses any more (joined into another) stays out.
if w.sides.items[e * 2] < 0 and w.sides.items[e * 2 + 1] < 0: continue
try refit_edge(w, e, moved.view(), m, old_points.items[(usize)edge.start], old_points.items[(usize)edge.end])
try check_loops(w)
try check_reach(w)
try orient(w, w.faces.count, open)
let solid = try used_brep(w)
defer solid.release()
return try CadModel.of_brep(solid)
## Each B-spline face of `w` beside a moved face (not moved itself) on a
## surface extended naturally (surface_extend.lucb) every way by twice as
## far as the move takes any moved face's vertex (an offset's distance, a
## replacement's tenth of the model), as a share of the surface's middle
## isoparms' lengths. Over its old domain the surface is the same.
func extend_neighbors(w: Shape*, moved: const bool[], m: const FaceMove*, distances: const f64[]) -> !:
var reach = math.abs(m.distance)
for d in distances: reach = math.max(reach, math.abs(d))
var low = Vector3(1.0e300, 1.0e300, 1.0e300)
var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
for e in 0..<w.edges.count:
let fa = w.sides.items[e * 2]
let fb = w.sides.items[e * 2 + 1]
let on_moved = (fa >= 0 and moved[(usize)fa]) or (fb >= 0 and moved[(usize)fb])
for v in [w.edges.items[e].start, w.edges.items[e].end]:
let p = w.points.items[(usize)v]
low = lower(low, p)
high = upper(high, p)
if on_moved: reach = math.max(reach, m.point(p).subtract(p).length())
if m.kind == move_replace: reach = math.max(reach, high.subtract(low).length() * 0.1)
if not (reach > 0.0): return
var done = Growing[i64]()
defer done.close()
for e in 0..<w.edges.count:
let fa = w.sides.items[e * 2]
let fb = w.sides.items[e * 2 + 1]
if fa < 0 or fb < 0 or moved[(usize)fa] == moved[(usize)fb]: continue
let neighbor = (usize)(fb if moved[(usize)fa] else fa)
let index = w.faces.items[neighbor].surface
if w.surfaces.items[(usize)index].kind != surface_spline: continue
var seen = false
for k in done.view(): seen = seen or k == index
if seen: continue
try done.push(index)
let s = &w.surfaces.items[(usize)index]
let along_u = try isoparm_length(s, true)
let along_v = try isoparm_length(s, false)
let share_u = math.min(2.0, 2.0 * reach / math.max(along_u, 1e-300))
let share_v = math.min(2.0, 2.0 * reach / math.max(along_v, 1e-300))
let amounts = [share_u, share_u, share_v, share_v]
let longer = try extended_spline(s, amounts[..<4])
w.surfaces.items[(usize)index].close()
w.surfaces.items[(usize)index] = longer
## The length of B-spline `s`'s middle isoparm along u (`along_u`) or v,
## by 32 chords.
func isoparm_length(s: const Surface*, along_u: bool) -> f64!:
var run = 0.0
var before = try evaluate(*s, Vector3(0.0, 0.5, 0.0) if along_u else Vector3(0.5, 0.0, 0.0))
for k in 1..<33:
let t = (f64)k / 32.0
let p = try evaluate(*s, Vector3(t, 0.5, 0.0) if along_u else Vector3(0.5, t, 0.0))
run += p.subtract(before).length()
before = p
return run
## An error when a B-spline face's edge runs off its surface (past an end
## extend_neighbors could not carry it to): five points of each within a
## hundred tolerances of the surface, found over the whole surface.
func check_reach(w: const Shape*) -> !:
for f in 0..<w.faces.count:
let s = &w.surfaces.items[(usize)w.faces.items[f].surface]
if s.kind != surface_spline: continue
for use in w.face_uses(f):
for k in 0..<5:
let p = try w.edge_at(edge_index(use), ((f64)k + 0.5) / 5.0)
let q = try evaluate(*s, try nearest_parameters(*s, p, Vector3(0.5, 0.5, 0.0), true))
if q.subtract(p).length() > w.tolerance * 100.0: error(invalid, "a B-spline face cannot reach where its edge has moved: the move takes it past where its surface can be carried on")
## A shape of its own with everything `w` has.
func shape_copy(w: const Shape*) -> Shape!:
var s = empty_shape(w.tolerance)
errdefer s.close()
try s.points.assign(w.points.view())
try s.carriers.assign(w.carriers.view())
try s.edges.assign(w.edges.view())
for surface in w.surfaces.view(): try s.surfaces.push(try surface_copy(&surface))
try s.faces.assign(w.faces.view())
try s.uses.assign(w.uses.view())
try s.sizes.assign(w.sizes.view())
try s.splines.assign(w.splines.view())
try s.spline_points.assign(w.spline_points.view())
try s.spline_weights.assign(w.spline_weights.view())
try s.spline_knots.assign(w.spline_knots.view())
try s.name_bytes.assign(w.name_bytes.view())
try s.name_offsets.assign(w.name_offsets.view())
try s.sides.assign(w.sides.view())
return s
## A copy of `w`'s points (where each vertex was).
func copied_points(w: const Shape*) -> Growing[Vector3]!:
var out = Growing[Vector3]()
errdefer out.close()
try out.assign(w.points.view())
return out
## Note face `f` at vertex `v` (8 slots a vertex), once.
func note_face(w: const Shape*, table: Growing[i64]*, v: i64, f: i64) -> !:
let base = (usize)v * 8
for k in 0..<(usize)8:
let at = table.items[base + k]
if at == f: return
if at < 0:
table.items[base + k] = f
return
error(invalid, "a vertex meets more than eight faces: too many to move")
## Whether every face at vertex `v` moves.
func all_moved(w: const Shape*, table: const Growing[i64]*, v: usize, moved: const bool[]) -> bool:
for k in 0..<(usize)8:
let f = table.items[v * 8 + k]
if f < 0: break
if not moved[(usize)f]: return false
return true
## Whether surface `s` of `w` is one of `listed` (the same record, or the
## same plane: two pieces of one face).
func same_surface_listed(w: const Shape*, listed: const i64[], s: i64) -> bool!:
let a = &w.surfaces.items[(usize)s]
for other in listed:
if other == s: return true
let b = &w.surfaces.items[(usize)other]
if a.kind == surface_plane and b.kind == surface_plane and math.abs(a.z.dot(b.z)) > 1.0 - 1e-12 and math.abs(b.origin.subtract(a.origin).dot(a.z)) <= w.tolerance: return true
return false
## An error when a moved face meets a face along an edge where their
## normals agree (tangent: a fillet's strip, a cylinder's flat) and only
## one of them moves: they would no longer meet.
func refuse_tangent_neighbors(w: const Shape*, moved: const bool[]) -> !:
for e in 0..<w.edges.count:
let fa = w.sides.items[e * 2]
let fb = w.sides.items[e * 2 + 1]
if fa < 0 or fb < 0 or moved[(usize)fa] == moved[(usize)fb]: continue
if try tangent_edge(w, e): error(invalid, "a face tangent to a moved face must move with it: pick the tangent faces too (Tangent chain)")
## Whether edge `e`'s two faces meet tangentially (their outward normals
## agree at its middle).
pub func tangent_edge(w: const Shape*, e: usize) -> bool!:
let fa = w.sides.items[e * 2]
let fb = w.sides.items[e * 2 + 1]
if fa < 0 or fb < 0: return false
let middle = try w.edge_at(e, 0.5)
let na = try w.face_normal((usize)fa, middle)
let nb = try w.face_normal((usize)fb, middle)
return na.dot(nb) > 1.0 - 1e-6
## Edge `e` of `w` again on its faces' surfaces now: a new carrier when a
## moved face holds it, else its own; its interval from its ends' new
## places, the way it ran before (from `old_start` to `old_end`).
func refit_edge(w: Shape*, e: usize, moved: const bool[], m: const FaceMove*, old_start: Vector3, old_end: Vector3) -> !:
let edge = w.edges.items[e]
let fa = w.sides.items[e * 2]
let fb = w.sides.items[e * 2 + 1]
let on_moved = (fa >= 0 and moved[(usize)fa]) or (fb >= 0 and moved[(usize)fb])
let start = w.points.items[(usize)edge.start]
let end = w.points.items[(usize)edge.end]
if not on_moved and start.subtract(old_start).length() <= w.tolerance * 0.01 and end.subtract(old_end).length() <= w.tolerance * 0.01: return
let old = w.carriers.items[(usize)edge.carrier]
# The way it left its start, as the move turns it.
let old_way = m.direction((try w.tangent(edge.carrier, edge.t0)).multiply_scalar(1.0 if edge.t1 > edge.t0 else -1.0))
var carrier = edge.carrier
if on_moved:
let both = fa >= 0 and fb >= 0 and moved[(usize)fa] and moved[(usize)fb]
if both and (m.kind == move_translate or m.kind == move_rotate):
# Moved with both its faces: the carrier moves alike.
carrier = try w.add_carrier(rigid_carrier(&old, m))
elif (fb < 0 or fa < 0) and m.kind == move_replace and not try seam_edge(w, e):
# An open body's boundary on a face replaced by its own surface
# (Stitch's joins rebuilt): it keeps its curve.
carrier = edge.carrier
elif fb < 0 or fa < 0:
# A seam (one face both ways): a line through its ends, or its
# circle about its center, grown with the face.
carrier = try w.add_carrier(try seam_carrier(w, &old, start, end, m))
else:
let middle = try w.edge_at(e, 0.5)
# Faces meeting tangentially (a fillet's rim on a torus corner,
# a G2 strip and its corner patch) offset alike stay tangent, so
# they touch rather than cross: the edge is the old one moved
# along their shared normal (not traced: tracing touching
# surfaces finds nothing, slowly).
if try tangent_there(w, (usize)fa, (usize)fb, middle):
carrier = try w.add_carrier(try tangent_carrier(w, (usize)fa, (usize)fb, &old, e, start, end, middle, "a moved face no longer meets its tangent neighbor along a curve this can follow"))
else:
let met = meeting_carrier(w, (usize)fa, (usize)fb, start, end, middle) catch failure:
recover try tangent_carrier(w, (usize)fa, (usize)fb, &old, e, start, end, middle, failure.message)
carrier = try w.add_carrier(met)
let c = w.carriers.items[(usize)carrier]
var t0 = 0.0
var t1 = 0.0
if c.kind == curve_line:
t0 = start.subtract(c.origin).dot(c.x)
t1 = end.subtract(c.origin).dot(c.x)
let was = old_end.subtract(old_start)
let now = end.subtract(start)
if now.length() <= w.tolerance * 10.0: error(invalid, "an edge would shrink to nothing: the move changes the body's shape too much")
if m.kind != move_rotate and now.dot(was) <= 0.0: error(invalid, "an edge would turn round: the move changes the body's shape too much")
elif c.kind == curve_circle or c.kind == curve_ellipse:
let (a0, a1) = (angle_on(&c, start), angle_on(&c, end))
# Round the circle the way the edge ran (a new carrier's frame may
# turn the other way).
let forward = (try w.tangent(carrier, a0)).dot(old_way) > 0.0
let was = math.abs(edge.t1 - edge.t0)
t0 = a0
var span = a1 - a0
if not forward: span = -span
while span <= 1e-9: span += 2.0 * math.pi
while span > 2.0 * math.pi + 1e-9: span -= 2.0 * math.pi
# A whole circle stays whole.
if edge.start == edge.end: span = 2.0 * math.pi
if was < 2.0 * math.pi - 1e-6 and math.abs(span - was) > math.pi: error(invalid, "an arc would turn round: the move changes the body's shape too much")
t1 = t0 + (span if forward else -span)
else:
let (_, _, knots, degree) = w.spline_net(c.spline)
let low = knots[(usize)degree]
let high = knots[knots.length - 1 - (usize)degree]
t0 = try nearest_on(w, carrier, start, low, high)
t1 = try nearest_on(w, carrier, end, low, high)
if (try w.at(carrier, t0)).subtract(start).length() > w.tolerance * 100.0 or (try w.at(carrier, t1)).subtract(end).length() > w.tolerance * 100.0:
error(invalid, "a B-spline edge cannot reach its moved corner: the move changes the body's shape too much")
# A curve traced between faces fitted to the tolerance (offsets
# meeting nearly tangentially) keeps how far it strays from them.
if on_moved and fa >= 0 and fb >= 0: try note_strays(w, e, carrier, t0, t1, (usize)fa, (usize)fb)
w.edges.items[e] = ShapeEdge(carrier, t0, t1, edge.start, edge.end)
## Edge `e`'s precision (its slack) from how far carrier `carrier` strays
## from faces `fa` and `fb` between `t0` and `t1`, when over half the
## tolerance: half again over it, as a tolerant edge.
func note_strays(w: Shape*, e: usize, carrier: i64, t0: f64, t1: f64, fa: usize, fb: usize) -> !:
var strays = 0.0
let first = try w.at(carrier, t0)
var seeds: Vector3[2] = [try seed_of(&w.surfaces.items[(usize)w.faces.items[fa].surface], first, w.tolerance), try seed_of(&w.surfaces.items[(usize)w.faces.items[fb].surface], first, w.tolerance)]
for k in 0..<129:
let q = try w.at(carrier, t0 + (t1 - t0) * (f64)k / 128.0)
for side in 0..<(usize)2:
let f = fa if side == 0 else fb
let (off, _) = try gap_along(&w.surfaces.items[(usize)w.faces.items[f].surface], q, w.tolerance, &seeds[side])
strays = math.max(strays, math.abs(off))
if strays <= w.tolerance * 0.5: return
while w.edge_slack.count <= e: try w.edge_slack.push(0.0)
w.edge_slack.items[e] = math.max(w.edge_slack.items[e], strays * 1.5)
## The carrier of a tangent edge between faces `fa` and `fb` of `w`, both
## offset alike: the old carrier `old` (of old edge `edge`) moved onto
## them, a line through the new ends, the circle through them and the old
## middle `middle` moved onto the new surface along its normal, or a
## B-spline through edge `e`'s old points so moved (a G2 corner patch's
## edge with its strip). Faces not meeting tangentially fail with `reason`.
func tangent_carrier(w: Shape*, fa: usize, fb: usize, old: const Carrier*, e: usize, start: Vector3, end: Vector3, middle: Vector3, reason: str) -> Carrier!:
let na = try w.face_normal(fa, start)
let nb = try w.face_normal(fb, start)
if na.dot(nb) < 1.0 - 1e-6: error(invalid, reason)
let (gap, n) = try signed_gap(&w.surfaces.items[(usize)w.faces.items[fa].surface], middle, w.tolerance)
let moved = middle.subtract(n.multiply_scalar(gap))
if old.kind == curve_line:
let d = end.subtract(start)
if d.length() <= w.tolerance * 10.0: error(invalid, reason)
return Carrier(curve_line, start, try d.normalized(), Vector3(), 0.0, 0.0, -1)
if old.kind == curve_spline: return try moved_spline_carrier(w, fa, fb, e, start, end, reason)
if old.kind != curve_circle: error(invalid, reason)
# The circle through start, the moved middle and end.
let a = start.subtract(moved)
let b = end.subtract(moved)
let axis = a.cross(b)
if axis.length() <= w.tolerance * w.tolerance:
# A closed circle (start and end one point): about the old axis.
let z = old.x.cross(old.y)
let h = moved.subtract(old.origin).dot(z)
let center = old.origin.add(z.multiply_scalar(h))
let radius = moved.subtract(center).length()
if radius <= w.tolerance: error(invalid, reason)
return Carrier(curve_circle, center, old.x, old.y, radius, radius, -1)
let center = moved.add(b.cross(axis).multiply_scalar(a.dot(a)).add(axis.cross(a).multiply_scalar(b.dot(b))).multiply_scalar(0.5 / axis.dot(axis)))
let radius = start.subtract(center).length()
# The old frame turned to the new plane, keeping the turning sense.
var z = try axis.normalized()
if z.dot(old.x.cross(old.y)) < 0.0: z = z.multiply_scalar(-1.0)
let x = try start.subtract(center).normalized()
return Carrier(curve_circle, center, x, z.cross(x), radius, radius, -1)
## Whether faces `fa` and `fb` of `w` are tangent at `p` (their normals
## parallel to a millionth).
func tangent_there(w: const Shape*, fa: usize, fb: usize, p: Vector3) -> bool!:
# (Their surfaces moved off `p`: the normals at its nearest points.)
let (_, na) = try signed_gap(&w.surfaces.items[(usize)w.faces.items[fa].surface], p, w.tolerance)
let (_, nb) = try signed_gap(&w.surfaces.items[(usize)w.faces.items[fb].surface], p, w.tolerance)
return math.abs(na.dot(nb)) >= 1.0 - 1e-6
## A B-spline carrier through edge `e`'s old points (33 along it) each
## moved onto face `fa`'s surface along its normal, from `start` to `end`:
## faces offset alike and tangent along the edge share the moved points.
## It must lie on both faces' surfaces to within ten tolerances at the
## points between, else `reason`; the edge keeps how far it strays (the
## faces' offsets are each fitted to the tolerance).
func moved_spline_carrier(w: Shape*, fa: usize, fb: usize, e: usize, start: Vector3, end: Vector3, reason: str) -> Carrier!:
let edge = w.edges.items[e]
var points = Growing[Vector3]()
defer points.close()
let count = 32
var seed = try seed_of(&w.surfaces.items[(usize)w.faces.items[fa].surface], start, w.tolerance)
for k in 0..<count + 1:
if k == 0: try points.push(start)
elif k == count: try points.push(end)
else:
let p = try w.at(edge.carrier, edge.t0 + (edge.t1 - edge.t0) * (f64)k / (f64)count)
let (gap, n) = try gap_along(&w.surfaces.items[(usize)w.faces.items[fa].surface], p, w.tolerance, &seed)
try points.push(p.subtract(n.multiply_scalar(gap)))
var net = Growing[Vector3]()
defer net.close()
var knots = Growing[f64]()
defer knots.close()
try interpolate_cubic(points.view(), &net, &knots)
var weights = Growing[f64]()
defer weights.close()
for _ in net.view(): try weights.push(1.0)
let spline = try w.store_spline(net.view(), weights.view(), knots.view(), 3, Matrix4())
let carrier = Carrier(curve_spline, Vector3(), Vector3(), Vector3(), 0.0, 0.0, spline)
let index = try w.add_carrier(carrier)
# How far it strays, sampled four times between the points it passes
# through: the charts later find its points on both faces within it.
var strays = 0.0
var seeds: Vector3[2] = [try seed_of(&w.surfaces.items[(usize)w.faces.items[fa].surface], start, w.tolerance), try seed_of(&w.surfaces.items[(usize)w.faces.items[fb].surface], start, w.tolerance)]
for k in 0..<count * 4 + 1:
let q = try w.at(index, (f64)k / (f64)(count * 4))
for side in 0..<(usize)2:
let f = fa if side == 0 else fb
let (off, _) = try gap_along(&w.surfaces.items[(usize)w.faces.items[f].surface], q, w.tolerance, &seeds[side])
strays = math.max(strays, math.abs(off))
if strays > w.tolerance * 10.0: error(invalid, reason)
while w.edge_slack.count <= e: try w.edge_slack.push(0.0)
if strays > w.tolerance * 0.5: w.edge_slack.items[e] = math.max(w.edge_slack.items[e], strays * 1.5)
return carrier
## Circle or ellipse `c`'s parameter at `p` (on it).
func angle_on(c: const Carrier*, p: Vector3) -> f64:
let d = p.subtract(c.origin)
return math.atan2(d.dot(c.y) / (c.b if c.kind == curve_ellipse else c.a), d.dot(c.x) / c.a)
## Carrier `c` moved rigidly by `m`.
func rigid_carrier(c: const Carrier*, m: const FaceMove*) -> Carrier:
return Carrier(c.kind, m.point(c.origin), m.direction(c.x), m.direction(c.y), c.a, c.b, c.spline)
## A seam's carrier on its moved face: a line through its new ends, or its
## circle about its center (a sphere's or torus's meridian) through them.
func seam_carrier(w: const Shape*, c: const Carrier*, start: Vector3, end: Vector3, m: const FaceMove*) -> Carrier!:
if c.kind == curve_line:
if start.subtract(end).length() <= w.tolerance: error(invalid, "a seam would shrink to nothing")
return Carrier(curve_line, start, try end.subtract(start).normalized(), Vector3(), 0.0, 0.0, -1)
if c.kind == curve_circle:
if m.kind == move_translate or m.kind == move_rotate: return rigid_carrier(c, m)
return Carrier(curve_circle, c.origin, c.x, c.y, start.subtract(c.origin).length(), start.subtract(c.origin).length(), -1)
error(invalid, "a B-spline seam cannot follow its moved face")
## Where faces `fa` and `fb` of `w` meet from `start` to `end`: between
## two planes the line through them; else the curve of their surfaces'
## meeting through both, nearest `hint` (where the edge ran: a closed
## edge's ends are one point).
func meeting_carrier(w: Shape*, fa: usize, fb: usize, start: Vector3, end: Vector3, hint: Vector3) -> Carrier!:
let sa = &w.surfaces.items[(usize)w.faces.items[fa].surface]
let sb = &w.surfaces.items[(usize)w.faces.items[fb].surface]
if sa.kind == surface_plane and sb.kind == surface_plane:
let d = end.subtract(start)
if d.length() <= w.tolerance * 10.0: error(invalid, "an edge would shrink to nothing: the move changes the body's shape too much")
return Carrier(curve_line, start, try d.normalized(), Vector3(), 0.0, 0.0, -1)
var curves = Growing[Carrier]()
defer curves.close()
if sa.kind == surface_spline or sb.kind == surface_spline:
# A B-spline face: where it meets the other, in closed form where
# the booleans have one (a plane across a profile swept straight),
# else traced round the edge.
if not try spline_meet(w, fa, fb, w.tolerance, &curves):
let (la, ha) = try face_box(w, fa)
let (lb, hb) = try face_box(w, fb)
let size = upper(ha, hb).subtract(lower(la, lb)).length()
let reach = Vector3(1.0, 1.0, 1.0).multiply_scalar(end.subtract(start).length() * 0.5 + size * 0.02)
try marched(w, fa, fb, lower(lower(start, end), hint).subtract(reach), upper(upper(start, end), hint).add(reach), size, w.tolerance, &curves)
return try nearest_spline_carrier(w, curves.view(), start, end, hint)
let met = try meet(sa, sb, w.tolerance, &curves)
if met != meet_curves: error(invalid, "a moved face no longer meets its neighbor along a curve this can follow")
# The curve through both ends, nearest the hint.
var best = -1
var best_distance = 1.0e300
for at in 0..<curves.count:
let c = curves.items[at]
let gap = math.max(carrier_gap(&c, start), carrier_gap(&c, end))
if gap > w.tolerance * 100.0: continue
let away = carrier_gap(&c, hint)
if away < best_distance:
best_distance = away
best = (i64)at
if best < 0: error(invalid, "a moved face no longer meets its neighbor where the edge runs")
return curves.items[(usize)best]
## Of `curves` (any kind, B-splines' nets in `w`), the one passing through
## `start` and `end`, nearest `hint`.
func nearest_spline_carrier(w: Shape*, curves: const Carrier[], start: Vector3, end: Vector3, hint: Vector3) -> Carrier!:
var best: i64 = -1
var best_distance = 1.0e300
for at in 0..<curves.length:
let c = curves[at]
let index = try w.add_carrier(c)
let low = 0.0
let high = 1.0 if c.kind == curve_spline else 2.0 * math.pi
if c.kind == curve_line:
if math.max(carrier_gap(&c, start), carrier_gap(&c, end)) > w.tolerance * 100.0: continue
let away = carrier_gap(&c, hint)
if away < best_distance:
best_distance = away
best = (i64)at
continue
let gap_start = (try w.at(index, try nearest_on(w, index, start, low, high))).subtract(start).length()
let gap_end = (try w.at(index, try nearest_on(w, index, end, low, high))).subtract(end).length()
if math.max(gap_start, gap_end) > w.tolerance * 100.0: continue
let away = (try w.at(index, try nearest_on(w, index, hint, low, high))).subtract(hint).length()
if away < best_distance:
best_distance = away
best = (i64)at
if best < 0: error(invalid, "a moved face no longer meets its B-spline neighbor where the edge runs")
return curves[(usize)best]
## How far `p` is from carrier `c` (a line, circle or ellipse).
func carrier_gap(c: const Carrier*, p: Vector3) -> f64:
let d = p.subtract(c.origin)
if c.kind == curve_line: return d.subtract(c.x.multiply_scalar(d.dot(c.x))).length()
let normal = c.x.cross(c.y)
let h = d.dot(normal)
let a = d.dot(c.x)
let b = d.dot(c.y)
if c.kind == curve_circle: return math.sqrt(h * h + (math.hypot(a, b) - c.a) * (math.hypot(a, b) - c.a))
# An ellipse: from the point at the same angle (near enough to pick).
let t = math.atan2(b / c.b, a / c.a)
let q = c.x.multiply_scalar(c.a * math.cos(t)).add(c.y.multiply_scalar(c.b * math.sin(t)))
return d.subtract(q).length()
## Every loop of a flat face must still turn the way
## it did about the face's normal (the outer loop counterclockwise, holes
## clockwise): else the face turned inside out.
func check_loops(w: const Shape*) -> !:
var points = Growing[Vector3]()
defer points.close()
for f in 0..<w.faces.count:
let face = w.faces.items[f]
let s = &w.surfaces.items[(usize)face.surface]
if s.kind != surface_plane: continue
let n = s.z if face.sense else s.z.multiply_scalar(-1.0)
let uses = w.face_uses(f)
var at: usize = 0
var first = true
for size in w.face_sizes(f):
points.clear()
for use in uses[at..<at + (usize)size]:
let e = edge_index(use)
for k in 0..<8:
let fraction = (f64)k / 8.0
try points.push(try w.edge_at(e, fraction if use > 0 else 1.0 - fraction))
at += (usize)size
var area = Vector3()
for k in 0..<points.count:
area = area.add(points.items[k].cross(points.items[(k + 1) % points.count]))
let turn = area.dot(n)
if (turn > 0.0) != first: error(invalid, "a face would turn inside out: the move changes the body's shape too much")
first = false