dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / surfacing / extend.lucb
## Extend (surfacing Stage 5: Alias's Object Edit › Extend, Parasolid's
## PK_BODY_extend, Rhino's ExtendSrf; §4.3 of luced-3d's
## docs/research/SURFACING-ALIAS-PLASTICITY.md): a surface's natural edge
## or a curve's end carried on by a distance or a percentage.
##
## A surface is extended column by column: each curve of its net running
## across the edge is extended alike (one parameter length for all), so
## the columns stay one net. At the end a column has its derivatives D1,
## D2, D3 by its parameter; the extension over parameter length h is a
## polynomial in s (0 to 1), as a Bezier joined at the end with full
## multiplicity, the knot then removed as far as the curve stays (to the
## continuity it was built with):
## Linear (Alias's; Parasolid's default): E + h s D1, straight on: G1,
## a curvature break;
## Natural (Alias's Extrapolate): the last span's own polynomial carried
## past the end (de Casteljau beyond 1, in homogeneous form, so an arc
## stays on its circle and a cylinder's side on the cylinder): the same
## surface, as smooth as it is;
## Soft (Parasolid's): C2 at the edge, the second derivative dying away
## to straight: E + h s D1 + h² D2 g(s) / 2, g'' = 2 (1 - s)²;
## Reflective (Parasolid's): C2, the curvature's change mirrored about
## the edge: E + h s D1 + (h s)² D2 / 2 - (h s)³ D3 / 6.
## The distance is along the middle isoparm across the edge (its chord for
## Natural), or a percentage of its length. Merged, the face is the extended net; not
## merged, the extension is a face of its own beside it.
## Extend: the knot at a joined piece's joint is removed when the curve
## moves by less than `joint_removal` of its size plus `joint_removal_floor`
## (so a curve of size zero still removes it); a curve made polynomial for
## the non-natural kinds keeps within `plain_share` of its size.
let joint_removal: f64 = 1e-9
let joint_removal_floor: f64 = 1e-15
let plain_share: f64 = 1e-9
pub let extend_linear: i64 = 0
pub let extend_natural: i64 = 1
pub let extend_soft: i64 = 2
pub let extend_reflective: i64 = 3
## The degree `kind`'s extension of a degree `p` curve needs: Soft's is
## quartic, Reflective's cubic.
func kind_degree(kind: i64, p: i64) -> i64:
if kind == extend_soft: return (i64)math.max((f64)p, 4.0)
if kind == extend_reflective: return (i64)math.max((f64)p, 3.0)
return p
## The Bezier of degree `d` with s^k coefficients `a` (power basis), its
## points onto `out`: b_i = Σ_{k ≤ i} C(i, k) / C(d, k) a_k.
func power_to_bezier(a: const Weighted[], d: usize, out: Growing[Weighted]*) -> !:
out.clear()
for i in 0..<d + 1:
var sum = Weighted(0.0, 0.0, 0.0, 0.0)
for k in 0..<i + 1: sum = sum.plus(a[k].times(choose(i, k) / choose(d, k)))
try out.push(sum)
## The extension of `c` (a polynomial curve) past its high end by
## parameter length `h` the way `kind` says, as a Bezier over high..high
## + h, raised to `c`'s degree.
func extension_piece(c: const Spline*, kind: i64, h: f64) -> Spline!:
let p = (usize)c.degree
let high = c.high()
var piece = empty_spline(c.degree)
errdefer piece.close()
if kind == extend_natural:
# The last span's Bezier, carried on by de Casteljau past its end.
var span_start = c.low()
for k in c.knots.view():
if k < high and k > span_start: span_start = k
var last = try extract(c, span_start, high)
defer last.close()
let s = (high + h - span_start) / (high - span_start)
# The modeling kernel's continuation (surface_extend.lucb), on the
# homogeneous points.
let flat = try new f64[(p + 1) * 4] --- in memory.heap
defer free(flat) in memory.heap
for i in 0..<p + 1:
let q = last.points.items[i]
flat[i * 4] = q.x
flat[i * 4 + 1] = q.y
flat[i * 4 + 2] = q.z
flat[i * 4 + 3] = q.w
try continued_bezier(flat, p, 4, s)
var left = Growing[Weighted]()
defer left.close()
for i in 0..<p + 1: try left.push(Weighted(flat[i * 4], flat[i * 4 + 1], flat[i * 4 + 2], flat[i * 4 + 3]))
for q in left.view():
if not (q.w > 0.0): error(invalid, "Extend Natural: this rational edge cannot be carried that far (its weights would vanish); extend less, or Linear")
# left is the Bezier over span_start..high + h; its part past high.
var whole = empty_spline(c.degree)
defer whole.close()
try whole.points.assign(left.view())
for _ in 0..<p + 1: try whole.knots.push(span_start)
for _ in 0..<p + 1: try whole.knots.push(high + h)
piece.close()
piece = try extract(&whole, high, high + h)
return piece
let j = try field_jet(c, high, 3, true)
var a: Weighted[5]
for k in 0..<(usize)5: a[k] = Weighted(0.0, 0.0, 0.0, 0.0)
var d: usize = 1
a[0] = Weighted(j.d[0].x, j.d[0].y, j.d[0].z, 1.0)
let d1 = j.d[1].multiply_scalar(h)
a[1] = Weighted(d1.x, d1.y, d1.z, 0.0)
if kind == extend_soft:
# g(s) = (1 - s)⁴ / 6 + 2 s / 3 - 1 / 6 = s² - 2 s³ / 3 + s⁴ / 6.
let d2 = j.d[2].multiply_scalar(h * h * 0.5)
a[2] = Weighted(d2.x, d2.y, d2.z, 0.0)
a[3] = Weighted(d2.x, d2.y, d2.z, 0.0).times(-2.0 / 3.0)
a[4] = Weighted(d2.x, d2.y, d2.z, 0.0).times(1.0 / 6.0)
d = 4
elif kind == extend_reflective:
let d2 = j.d[2].multiply_scalar(h * h * 0.5)
let d3 = j.d[3].multiply_scalar(-h * h * h / 6.0)
a[2] = Weighted(d2.x, d2.y, d2.z, 0.0)
a[3] = Weighted(d3.x, d3.y, d3.z, 0.0)
d = 3
var points = Growing[Weighted]()
defer points.close()
try power_to_bezier(a[..<d + 1], d, &points)
try piece.points.assign(points.view())
piece.degree = (i64)d
for _ in 0..<d + 1: try piece.knots.push(high)
for _ in 0..<d + 1: try piece.knots.push(high + h)
if (usize)d < p: try elevate(&piece, p - d)
return piece
## `c` with `piece` (from its high end on, of its degree) joined: the
## joint's knot at full multiplicity, then removed as far as the curve
## stays within a billionth of its size (back to the continuity built).
func joined_piece(c: const Spline*, piece: const Spline*) -> Spline!:
let p = (usize)c.degree
var made = empty_spline(c.degree)
errdefer made.close()
try made.points.assign(c.points.view())
for k in 1..<piece.points.count: try made.points.push(piece.points.items[k])
for k in 0..<c.knots.count - p - 1: try made.knots.push(c.knots.items[k])
for _ in 0..<p: try made.knots.push(c.high())
for _ in 0..<p + 1: try made.knots.push(piece.high())
_ = try remove_knot(&made, c.high(), p, size_of(c) * joint_removal + joint_removal_floor)
return made
## The parameter length that carries `c` on by `distance` the way `kind`
## does: along its end tangent; Natural, by its chord past the end.
func extension_length(c: const Spline*, kind: i64, distance: f64) -> f64!:
let j = try field_jet(c, c.high(), 1, true)
let speed = j.d[1].length()
if not (speed > 0.0): error(invalid, "Extend: the edge stops there (its tangent vanishes)")
var h = distance / speed
if kind != extend_natural: return h
for _ in 0..<8:
var piece = try extension_piece(c, kind, h)
defer piece.close()
let reach = piece.point_at(piece.high()).subtract(c.point_at(c.high())).length()
if not (reach > 0.0): break
h *= distance / reach
return h
## The length of `c` (64 chords a span).
func chord_length(c: const Spline*) -> f64:
let count = 64 * (span_count(c) + 1)
var run = 0.0
var before = c.point_at(c.low())
for k in 1..<count + 1:
let p = c.point_at(c.low() + (c.high() - c.low()) * (f64)k / (f64)count)
run += p.subtract(before).length()
before = p
return run
## `set` with the face or curve `input` ("face <name> x y z": the face's
## side nearest the point; "curve <name> x y z": the end nearest it)
## extended by `kind`, `distance` (or that percentage of its length with
## `percent`); `merge` false keeps a surface's extension a face of its own
## (a body after the others, named `<face>/extend`).
func extended_set(set: interop.Reference[GeometrySet], input: str, kind: i64, distance: f64, percent: bool, merge: bool) -> interop.Reference[GeometrySet]!:
if kind < extend_linear or kind > extend_reflective: error(invalid, "Extend is Linear, Natural, Soft or Reflective")
if not (distance > 0.0): error(invalid, "Extend: the distance must be more than zero")
let what = try input_of(input)
if what.curve:
let index = try CadCurves.find(set, what.name)
if index < 0: error(invalid, "Extend: the curve is no longer in the model: pick it again")
let on = try CadCurves.face(set, index)
defer on.release()
if on.value.length > 0: error(invalid, "Extend carries a curve off its face: duplicate it as a free curve first")
let held = try CadCurves.curve(set, index)
defer held.release()
# Natural carries the curve's own (rational) form on: an arc of a
# circle stays on the circle; the others work on its polynomial.
let own = spline_in(held.value())
var c = try own.copy() if kind == extend_natural else try plain_curve(own, size_of(own) * plain_share)
defer c.close()
let at_start = c.point_at(c.low()).subtract(what.near).length() < c.point_at(c.high()).subtract(what.near).length()
if at_start:
let turned_round = try reversed_spline(&c)
c.close()
c = turned_round
if kind_degree(kind, c.degree) > c.degree: try elevate(&c, (usize)(kind_degree(kind, c.degree) - c.degree))
let reach = distance * chord_length(&c) / 100.0 if percent else distance
let h = try extension_length(&c, kind, reach)
var piece = try extension_piece(&c, kind, h)
defer piece.close()
var longer = try joined_piece(&c, &piece)
defer longer.close()
if at_start:
let restored = try reversed_spline(&longer)
longer.close()
longer = restored
let made = try held_spline(try longer.copy())
defer made.release()
return try CadCurves.with_curve(set, what.name, made)
var w = empty_shape(CadTolerances(), 0.0)
defer w.close()
let (body, f) = try face_place(set, what.name, &w)
let tolerance = align_tolerance(&w)
var net = try surface_net(&w, (usize)w.faces.items[f].surface) if kind == extend_natural else try plain_net(&w, f, tolerance)
defer net.close()
if not try natural(&w, f, &net): error(invalid, "Extend carries a natural edge on; this face is trimmed (Untrim it, or Trim Convert it first)")
let side = nearest_side(&net, what.near)
# Turned so the edge is the net's u = high end.
var low_side = try turned(&net, side, false)
defer low_side.close()
var work = try u_reversed(&low_side)
defer work.close()
if kind_degree(kind, work.du) > work.du: try net_elevate(&work, 0, (usize)(kind_degree(kind, work.du) - work.du))
var columns = Growing[Spline]()
defer close_splines_of(&columns)
try curves_along(&work, 0, &columns)
# The distance along the surface's middle isoparm across the edge (on
# 0..1: its parameter length back on the net's).
var middle = try isoparm_spline(&work, 1, 0.5)
defer middle.close()
let reach = distance * chord_length(&middle) / 100.0 if percent else distance
let h = (try extension_length(&middle, kind, reach)) * (work.u_high() - work.u_low())
var longer = Growing[Spline]()
defer close_splines_of(&longer)
var pieces = Growing[Spline]()
defer close_splines_of(&pieces)
for c in columns.view():
var piece = try extension_piece(&c, kind, h)
errdefer piece.close()
if merge: try longer.push(try joined_piece(&c, &piece))
try pieces.push(piece)
# The columns' knots after the removal may differ by a knot one could
# lose and another not: kept at the fewest any took out.
if merge: try unify_columns(&longer, &columns, &pieces)
var extended = try net_from(longer.view() if merge else pieces.view(), 0, &work)
defer extended.close()
var back_low = try u_reversed(&extended)
defer back_low.close()
var back = try turned(&back_low, side, true)
defer back.close()
let models = set_models(try set.get())
if merge:
let made = try with_net(models[body].value(), &w, f, &back, &net)
defer made.release()
let one: interop.Reference[CadModel][1] = [made]
return try with_body(set, (i64)body, one[..<1])
var buffer: u8[256]
let piece_name = try strings.format(buffer, f"{what.name}/extend")
let sheet = try net_body(w.tolerances, &back, piece_name, w.faces.items[f].sense)
defer sheet.release()
return try with_body_added(set, sheet)
## Merged columns alike: when the joint's knot came out at different
## multiplicities (one column's shape let more go than another's), every
## column joined again keeping the most any kept.
func unify_columns(longer: Growing[Spline]*, columns: Growing[Spline]*, pieces: Growing[Spline]*) -> !:
var most: usize = 0
for c in longer.view(): most = c.knots.count if c.knots.count > most else most
var alike = true
for c in longer.view():
if c.knots.count != most: alike = false
if alike:
for at in 1..<longer.count: try longer.items[at].knots.assign(longer.items[0].knots.view())
return
# Rejoin each keeping the joint at the multiplicity the longest has.
var keep_at: usize = 0
for at in 0..<longer.count:
if longer.items[at].knots.count == most: keep_at = at
let joint = columns.items[0].high()
let want = multiplicity(longer.items[keep_at].knots.view(), joint, knot_same)
for at in 0..<longer.count:
if longer.items[at].knots.count == most: continue
var again = empty_spline(columns.items[at].degree)
let p = (usize)columns.items[at].degree
let c = &columns.items[at]
try again.points.assign(c.points.view())
for k in 1..<pieces.items[at].points.count: try again.points.push(pieces.items[at].points.items[k])
for k in 0..<c.knots.count - p - 1: try again.knots.push(c.knots.items[k])
for _ in 0..<p: try again.knots.push(c.high())
for _ in 0..<p + 1: try again.knots.push(pieces.items[at].high())
_ = try remove_knot(&again, c.high(), p - want, 1.0e300)
longer.items[at].close()
longer.items[at] = again
for at in 1..<longer.count: try longer.items[at].knots.assign(longer.items[0].knots.view())