dymokomi/luce-cad
Source of release 0.9.2
0.9.2 / 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