dymokomi/luce-cad
Source of release 0.9.3
0.9.3 / src / sketch / freedom.lucb
## A solved sketch's freedom: how many degrees of freedom are left, which
## entities are fully constrained (none of their parameters can move
## without breaking a constraint), and which constraints are redundant
## (dependent on others but holding) or conflicting (dependent and not
## holding). One QR with column pivoting of the transposed Jacobian Jᵀ at
## the solution answers all three: its rank is the independent rows; the
## null space of J, the last columns of Q, says which unknowns can still
## move (an unknown is fixed when its row of that block is zero); and the
## columns of Jᵀ the pivoting left behind are the dependent rows. For the
## editor after a change, not every drag frame.
pub struct Freedom:
## The degrees of freedom left.
pub var degrees: i64
## Per entity: whether it is fully constrained.
pub var fixed: Growing[bool]
## Constraints that repeat others (and hold), and that conflict.
pub var redundant: Growing[i64]
pub var conflicting: Growing[i64]
pub func close():
self.fixed.close()
self.redundant.close()
self.conflicting.close()
## The freedom of `sketch` as it is (solve it first).
pub func freedom_of(sketch: const Sketch*) -> Freedom!:
var none_pinned: i64[1] = [0]
var classes = try classes_of(sketch, none_pinned[..<0])
defer classes.close()
var rows = Growing[Row]()
defer rows.close()
try rows_of(sketch, &rows)
let scale = size_of(sketch)
let n = classes.source.count
var values = Growing[f64]()
defer values.close()
for u in 0..<n: try values.push(sketch.params.items[(usize)classes.source.items[u]])
var result = Freedom(0, Growing[bool](), Growing[i64](), Growing[i64]())
errdefer result.close()
# Substitutions that met two different constants conflict outright.
for at in 0..<classes.conflicts.count:
let k = classes.conflicts.items[at]
if k >= 0: try add_once(&result.conflicting, k)
# Jᵀ: a column per row that reads an unknown.
var used = Growing[usize]()
defer used.close()
var context = Reading(&classes, values.view())
var partials = Growing[f64]()
defer partials.close()
var residuals = Growing[f64]()
defer residuals.close()
for at in 0..<rows.count:
let r = &rows.items[at]
let e = evaluate(r, read_value, (void*)&context, scale)
var reads = false
for i in 0..<(usize)8:
if r.at[i] >= 0 and classes.variable.items[(usize)r.at[i]] >= 0: reads = true
if not reads:
if math.abs(e.residual) > 1e-7 * scale and r.constraint >= 0: try add_once(&result.conflicting, r.constraint)
continue
try used.push(at)
try residuals.push(e.residual)
for i in 0..<(usize)8: try partials.push(e.partial[i])
let m = used.count
var movable = Growing[bool]()
defer movable.close()
try movable.fill(n, true)
if n > 0 and m > 0:
var t = Growing[f64]()
defer t.close()
try t.fill(n * m, 0.0)
for c in 0..<m:
let r = &rows.items[used.items[c]]
for i in 0..<(usize)8:
if r.at[i] < 0: continue
let u = classes.variable.items[(usize)r.at[i]]
if u >= 0: t.items[(usize)u * m + c] += partials.items[c * 8 + i]
var q = Growing[f64]()
defer q.close()
try q.fill(n * n, 0.0)
var order = Growing[i64]()
defer order.close()
try order.fill(m, 0)
let rank = pivoted_qr(t.items[..<(n * m)], n, m, q.items[..<(n * n)], order.items[..<m], 1e-9)
result.degrees = (i64)(n - rank)
# An unknown is fixed when the null space does not reach it.
for u in 0..<n:
var reach = 0.0
for k in rank..<n: reach += q.items[u * n + k] * q.items[u * n + k]
movable.items[u] = reach > 1e-18
# The rows pivoting left behind depend on the others: redundant
# when they hold, conflicting when they do not.
for k in rank..<m:
let c = (usize)order.items[k]
let constraint = rows.items[used.items[c]].constraint
if constraint < 0: continue
if math.abs(residuals.items[c]) <= 1e-7 * scale: try add_once(&result.redundant, constraint)
else: try add_once(&result.conflicting, constraint)
else:
result.degrees = (i64)n
for e in sketch.entities.view():
try result.fixed.push(try entity_fixed(sketch, &classes, movable.view(), e))
return result
## The constraints a sketch's over-constraint runs through, onto `out`:
## each one that, let go, leaves fewer constraints redundant or
## conflicting (Fusion lights these when a new one would over-constrain).
## Each is tried as driven in a copy, so this is for the moment a conflict
## is found, not for every frame.
pub func dependent_constraints(sketch: const Sketch*, out: Growing[i64]*) -> !:
out.clear()
var all = try freedom_of(sketch)
let count = all.redundant.count + all.conflicting.count
all.close()
if count == 0: return
for j in 0..<sketch.constraints.count:
if sketch.constraints.items[j].driven: continue
var trial = try sketch.copy()
trial.constraints.items[j].driven = true
var f = freedom_of(&trial) catch failure:
trial.close()
error(failure.code, failure.message)
trial.close()
let left = f.redundant.count + f.conflicting.count
f.close()
if left < count: try out.push((i64)j)
## Whether every parameter of `e` (and its points) is a constant or an
## unknown that cannot move.
func entity_fixed(sketch: const Sketch*, classes: const Classes*, movable: const bool[], e: SketchEntity) -> bool!:
if e.kind == EntityKind.point:
return param_fixed(classes, movable, e.first) and param_fixed(classes, movable, e.first + 1)
let scalar = sketch.scalar_of(e)
if scalar >= 0 and not param_fixed(classes, movable, scalar): return false
var points = Growing[i64]()
defer points.close()
try sketch.points_of(e, &points)
for p in points.view():
if not param_fixed(classes, movable, sketch.entity(p).first) or not param_fixed(classes, movable, sketch.entity(p).first + 1): return false
return true
func param_fixed(classes: const Classes*, movable: const bool[], param: i64) -> bool:
let u = classes.variable.items[(usize)param]
return u < 0 or not movable[(usize)u]