Luce packages
LuceLuce BaseLuciaOS

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]