Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.5

0.9.5 / src / sketch / substitution.lucb

## Substitution: the constraints that only say parameters are equal or
## fixed (coincident, horizontal and vertical, concentric, equal radii, fix,
## radius and diameter) are not solved for. Their parameters merge into
## classes (union-find), each class one unknown of the solver or a
## constant; two different constants meeting in one class is a conflict,
## named at once by the constraints that met. A merge keeps the larger
## class's value (a level line's ends stay put when a free end joins them),
## the second entity's (what the first is constrained to) between equals,
## and a pinned (dragged) parameter's class keeps the pinned value.

pub struct Classes:
    ## Per parameter: its class's root while merging.
    var parent: Growing[i64]
    ## Per root: whether the class is a constant, its value, and the
    ## constraint that made it one (-1: the value it had).
    var fixed: Growing[bool]
    var fixed_value: Growing[f64]
    var fixer: Growing[i64]
    var pinned: Growing[bool]
    ## Per root: how many parameters its class holds.
    var size: Growing[i64]
    ## Per parameter: its solver unknown, or -1 for a constant.
    pub var variable: Growing[i64]
    ## Per unknown: a parameter of its class (its value is the start).
    pub var source: Growing[i64]
    ## Pairs of constraints whose substitutions conflict.
    pub var conflicts: Growing[i64]

    pub func close():
        self.parent.close()
        self.fixed.close()
        self.fixed_value.close()
        self.fixer.close()
        self.pinned.close()
        self.size.close()
        self.variable.close()
        self.source.close()
        self.conflicts.close()

    ## Parameter `param`'s value: its constant, or unknown `values`'.
    pub func value(param: i64, values: const f64[]) -> f64:
        let unknown = self.variable.items[(usize)param]
        if unknown >= 0: return values[(usize)unknown]
        return self.fixed_value.items[(usize)self.find(param)]

    func find(param: i64) -> i64:
        var at = param
        while self.parent.items[(usize)at] != at:
            at = self.parent.items[(usize)at]
        return at

    ## Merge `moved`'s class into `kept`'s for constraint `constraint`.
    func merge(moved: i64, kept: i64, constraint: i64) -> !:
        var a = self.find(moved)
        var b = self.find(kept)
        if a == b: return
        let fa = self.fixed.items[(usize)a]
        let fb = self.fixed.items[(usize)b]
        if fa and fb and math.abs(self.fixed_value.items[(usize)a] - self.fixed_value.items[(usize)b]) > 1e-9:
            try self.conflict(constraint, self.fixer.items[(usize)a])
            try self.conflict(constraint, self.fixer.items[(usize)b])
            return
        # The root keeps what wins: a constant, else a pin, else the larger
        # class, else `kept`.
        let pa = self.pinned.items[(usize)a]
        let pb = self.pinned.items[(usize)b]
        let larger = self.size.items[(usize)a] > self.size.items[(usize)b]
        if fa or (not fb and ((pa and not pb) or (pa == pb and larger))):
            let swap = a
            a = b
            b = swap
        self.parent.items[(usize)a] = b
        self.pinned.items[(usize)b] = self.pinned.items[(usize)b] or self.pinned.items[(usize)a]
        self.size.items[(usize)b] += self.size.items[(usize)a]

    ## Make `param`'s class the constant `value` for constraint `constraint`.
    func fix(param: i64, value: f64, constraint: i64) -> !:
        let root = self.find(param)
        if self.fixed.items[(usize)root]:
            if math.abs(self.fixed_value.items[(usize)root] - value) > 1e-9:
                try self.conflict(constraint, self.fixer.items[(usize)root])
            return
        self.fixed.items[(usize)root] = true
        self.fixed_value.items[(usize)root] = value
        self.fixer.items[(usize)root] = constraint

    func conflict(a: i64, b: i64) -> !:
        try self.conflicts.push(a)
        try self.conflicts.push(b)

## The classes of `sketch`'s parameters under its substitutions; `pins`
## (parameters) keep their values, as a drag's do.
pub func classes_of(sketch: const Sketch*, pins: const i64[]) -> Classes!:
    var c = Classes(Growing[i64](), Growing[bool](), Growing[f64](), Growing[i64](), Growing[bool](), Growing[i64](), Growing[i64](), Growing[i64](), Growing[i64]())
    errdefer c.close()
    let count = sketch.params.count
    for at in 0..<count:
        try c.parent.push((i64)at)
        try c.fixed.push(false)
        try c.fixed_value.push(sketch.params.items[at])
        try c.fixer.push(-1)
        try c.pinned.push(false)
        try c.size.push(1)
    for pin in pins: c.pinned.items[(usize)pin] = true
    for index in 0..<sketch.constraints.count:
        let k = sketch.constraints.items[index]
        if k.driven: continue
        try substitute(sketch, &c, k, (i64)index)
    # One unknown per class that is not a constant, its value the root's.
    for at in 0..<count:
        try c.variable.push(-1)
    for at in 0..<count:
        let root = c.find((i64)at)
        if c.fixed.items[(usize)root]: continue
        if c.variable.items[(usize)root] < 0:
            c.variable.items[(usize)root] = (i64)c.source.count
            try c.source.push(root)
        c.variable.items[at] = c.variable.items[(usize)root]
    return c

## Constraint `k` (index `index`) as merges and constants, if it is one.
func substitute(sketch: const Sketch*, c: Classes*, k: SketchConstraint, index: i64) -> !:
    if k.kind == ConstraintKind.coincident:
        try c.merge(x_of(sketch, k.first), x_of(sketch, k.second), index)
        try c.merge(x_of(sketch, k.first) + 1, x_of(sketch, k.second) + 1, index)
    elif k.kind == ConstraintKind.horizontal or k.kind == ConstraintKind.vertical:
        let axis = 1 if k.kind == ConstraintKind.horizontal else 0
        let (a, b) = ends(sketch, k)
        try c.merge(x_of(sketch, a) + axis, x_of(sketch, b) + axis, index)
    elif k.kind == ConstraintKind.concentric:
        let a = sketch.entity(k.first).first
        let b = sketch.entity(k.second).first
        try c.merge(x_of(sketch, a), x_of(sketch, b), index)
        try c.merge(x_of(sketch, a) + 1, x_of(sketch, b) + 1, index)
    elif k.kind == ConstraintKind.equal and sketch.entity(k.first).kind != EntityKind.line:
        try c.merge(sketch.entity(k.first).second, sketch.entity(k.second).second, index)
    elif k.kind == ConstraintKind.fix:
        try fix_entity(sketch, c, k.first, index)
    elif k.kind == ConstraintKind.radius or k.kind == ConstraintKind.diameter:
        try c.fix(sketch.entity(k.first).second, k.value * (0.5 if k.kind == ConstraintKind.diameter else 1.0), index)

## Every parameter of entity `at` (with its points) a constant.
func fix_entity(sketch: const Sketch*, c: Classes*, at: i64, index: i64) -> !:
    let e = sketch.entity(at)
    if e.kind == EntityKind.point:
        try c.fix(e.first, sketch.params.items[(usize)e.first], index)
        try c.fix(e.first + 1, sketch.params.items[(usize)e.first + 1], index)
        return
    var points = Growing[i64]()
    defer points.close()
    try sketch.points_of(e, &points)
    for p in points.view(): try fix_entity(sketch, c, p, index)
    let scalar = sketch.scalar_of(e)
    if scalar >= 0: try c.fix(scalar, sketch.params.items[(usize)scalar], index)

## The two points a horizontal or vertical constraint levels: a line's
## ends, or two points.
func ends(sketch: const Sketch*, k: SketchConstraint) -> (i64, i64):
    let e = sketch.entity(k.first)
    if e.kind == EntityKind.line: return (e.first, e.second)
    return (k.first, k.second)

## Point `point`'s x parameter.
func x_of(sketch: const Sketch*, point: i64) -> i64:
    return sketch.entity(point).first