solver.js 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338
  1. /*
  2. 3D Modeler - sketch constraint solver
  3. Wraps planegcs (FreeCAD's 2D geometric constraint solver, lib/planegcs).
  4. The solver is small and answers in milliseconds, so it runs on the main
  5. thread where the sketcher can call it on every pointer move of a drag.
  6. model.js turns a sketch into the solver's primitive list; this file runs
  7. the solve and reports what the sketcher shows: the degrees of freedom left
  8. and the constraints that conflict or are redundant.
  9. */
  10. import { init_planegcs_module, GcsWrapper } from '../../lib/planegcs/index.js';
  11. import { toPrimitives, applySolution, dimensionSides, measure, find, ORIGIN } from './model.js';
  12. // A point that ends up closer than this to where it was has not moved (mm)
  13. const STILL = 1e-6;
  14. let modulePromise = null;
  15. export function loadSolver() {
  16. if (!modulePromise) {
  17. modulePromise = init_planegcs_module();
  18. }
  19. return modulePromise;
  20. }
  21. function baseIds(list) {
  22. const out = [];
  23. list.forEach(function (id) {
  24. const base = String(id).split(':')[0];
  25. if (base.charAt(0) !== '$' && out.indexOf(base) < 0) {
  26. out.push(base);
  27. }
  28. });
  29. return out;
  30. }
  31. // A constraint made of several equations (Collinear: both ends of the second
  32. // line on the first; Fix: x and y) can have a part that the rest of the sketch
  33. // already implies. Two vertical lines made collinear only need one end on the
  34. // other line: the vertical constraints carry the second end along. The solver
  35. // calls that part redundant, which would refuse the whole constraint. Those
  36. // parts are returned here so they can be left out, as long as the constraint
  37. // keeps at least one equation. A redundant equation is one the solution of the
  38. // others satisfies anyway, so leaving it out does not change the answer.
  39. export function spareParts(sketch, primitives, redundant) {
  40. const constraints = new Set(sketch.constraints.map(function (c) {
  41. return c.id;
  42. }));
  43. const flagged = new Set(redundant.map(String));
  44. const parts = new Map(); // constraint id -> ids of its equations
  45. primitives.forEach(function (p) {
  46. const base = String(p.id).split(':')[0];
  47. if (constraints.has(base)) {
  48. if (!parts.has(base)) {
  49. parts.set(base, []);
  50. }
  51. parts.get(base).push(String(p.id));
  52. }
  53. });
  54. const out = [];
  55. parts.forEach(function (ids) {
  56. const extra = ids.filter(function (id) {
  57. return flagged.has(id);
  58. });
  59. if (extra.length && extra.length < ids.length) {
  60. Array.prototype.push.apply(out, extra);
  61. }
  62. });
  63. return out;
  64. }
  65. // createSolver().then(solver => solver.solve(sketch, drag))
  66. // solve() moves the geometry of `sketch` in place when it succeeds and returns
  67. // { ok, dof, conflicting: [constraint id], redundant: [constraint id] }
  68. // ok is false when the constraints cannot all be met; the sketch is then
  69. // left untouched.
  70. export async function createSolver() {
  71. const mod = await loadSolver();
  72. const wrapper = new GcsWrapper(new mod.GcsSystem());
  73. wrapper.debug_mode = 0; // DebugMode.NoDebug: keep the solver out of the console
  74. // Push the sketch and the `extra` primitives, minus the equations in
  75. // `skip`, and solve it
  76. function attempt(sketch, drag, skip, extra) {
  77. wrapper.clear_data();
  78. const primitives = toPrimitives(sketch, drag).concat(extra || []).filter(function (p) {
  79. return !skip.has(String(p.id));
  80. });
  81. wrapper.push_primitives_and_params(primitives);
  82. const status = wrapper.solve();
  83. return {
  84. primitives: primitives,
  85. status: status,
  86. conflicting: wrapper.get_gcs_conflicting_constraints(),
  87. redundant: wrapper.get_gcs_redundant_constraints()
  88. };
  89. }
  90. // Each pass leaves out the parts of constraints found to be implied by
  91. // the rest (see spareParts); one pass is the usual case. Throws when the
  92. // solver does.
  93. function passes(sketch, drag, extra) {
  94. const skip = new Set();
  95. let run = null;
  96. for (let pass = 0; pass < 4; pass++) {
  97. run = attempt(sketch, drag, skip, extra);
  98. const spare = run.conflicting.length ? [] : spareParts(sketch, run.primitives, run.redundant);
  99. if (!spare.length) {
  100. break;
  101. }
  102. spare.forEach(function (id) {
  103. skip.add(id);
  104. });
  105. }
  106. return run;
  107. }
  108. function solve(sketch, drag) {
  109. let run = null;
  110. try {
  111. run = passes(sketch, drag);
  112. } catch (err) {
  113. return { ok: false, dof: -1, conflicting: [], redundant: [], error: String(err && err.message ? err.message : err) };
  114. }
  115. const conflicting = baseIds(run.conflicting);
  116. const redundant = baseIds(run.redundant);
  117. // 0 = solved, 1 = converged to the nearest answer; anything else failed
  118. const ok = (run.status === 0 || run.status === 1) && !conflicting.length;
  119. if (ok) {
  120. wrapper.apply_solution();
  121. applySolution(sketch, wrapper.sketch_index.get_primitives());
  122. }
  123. return { ok: ok, dof: wrapper.gcs.dof(), conflicting: conflicting, redundant: redundant };
  124. }
  125. /* ---------- changing a dimension ---------- */
  126. // Holds for a change: each free point (not the origin, not projected
  127. // from the model) gets a pair of coordinate equations keeping it where
  128. // it is. Those of the points in `keep` are hard; the others are soft
  129. // (planegcs temporary constraints, which the solver meets as closely as
  130. // the real constraints allow, the way a dragged point follows the
  131. // cursor). Circles keep their size softly as well.
  132. function holds(sketch, keep) {
  133. const out = [];
  134. sketch.geometry.forEach(function (g, i) {
  135. if (g.ref) {
  136. return;
  137. }
  138. if (g.type === 'point') {
  139. const soft = !keep.has(g.id);
  140. out.push({ id: '$hx' + i, type: 'coordinate_x', p_id: g.id, x: g.x, temporary: soft });
  141. out.push({ id: '$hy' + i, type: 'coordinate_y', p_id: g.id, y: g.y, temporary: soft });
  142. } else if (g.type === 'circle') {
  143. out.push({ id: '$hr' + i, type: 'circle_radius', c_id: g.id, radius: g.r, temporary: true });
  144. }
  145. });
  146. return out;
  147. }
  148. // Solve `sketch` with the points in `keep` held and the rest held
  149. // softly, then once more without the holds to make sure every constraint
  150. // is met. True when both work; the sketch has then moved.
  151. function holding(sketch, keep) {
  152. let run = null;
  153. try {
  154. run = passes(sketch, null, holds(sketch, keep));
  155. } catch (err) {
  156. return false;
  157. }
  158. if ((run.status !== 0 && run.status !== 1) || run.conflicting.length) {
  159. return false;
  160. }
  161. wrapper.apply_solution();
  162. applySolution(sketch, wrapper.sketch_index.get_primitives());
  163. return solve(sketch).ok;
  164. }
  165. // How many points (and circle sizes) differ between two copies
  166. function moved(before, after) {
  167. let count = 0;
  168. after.geometry.forEach(function (g, i) {
  169. const b = before.geometry[i];
  170. const d = g.type === 'point' ? Math.hypot(g.x - b.x, g.y - b.y) : g.type === 'circle' ? Math.abs(g.r - b.r) : 0;
  171. if (d > STILL) {
  172. count++;
  173. }
  174. });
  175. return count;
  176. }
  177. // How early an end of a dimension was drawn: the place of its first
  178. // point in the geometry list; the origin and model edges come first
  179. function age(sketch, side) {
  180. let first = Infinity;
  181. side.forEach(function (id) {
  182. const g = id === ORIGIN ? null : find(sketch, id);
  183. const at = !g || g.ref ? -1 : sketch.geometry.indexOf(g);
  184. first = Math.min(first, at);
  185. });
  186. return first;
  187. }
  188. function copyPlaces(from, to) {
  189. to.geometry.forEach(function (g, i) {
  190. const s = from.geometry[i];
  191. if (g.type === 'point') {
  192. g.x = s.x;
  193. g.y = s.y;
  194. } else if (g.type === 'circle') {
  195. g.r = s.r;
  196. }
  197. });
  198. }
  199. // Meet the new value of dimension `dim` moving as little as possible:
  200. // hold each of its ends in turn, everything else held softly, and keep
  201. // the answer that moves the fewest points. On a tie the end drawn first
  202. // stays. When no end can be held, everything is held softly. False if
  203. // nothing worked; the sketch is then untouched.
  204. function settle(sketch, dim) {
  205. const text = JSON.stringify({ geometry: sketch.geometry, constraints: sketch.constraints });
  206. let best = null;
  207. const tryKeeping = function (side) {
  208. const copy = JSON.parse(text);
  209. const keep = new Set(side.filter(function (id) {
  210. const g = id === ORIGIN ? null : find(copy, id);
  211. return g && !g.ref; // the origin and model edges never move anyway
  212. }));
  213. if (!holding(copy, keep)) {
  214. return;
  215. }
  216. const score = [moved(sketch, copy), age(sketch, side)];
  217. if (!best || score[0] < best.score[0] || (score[0] === best.score[0] && score[1] < best.score[1])) {
  218. best = { copy: copy, score: score };
  219. }
  220. };
  221. dimensionSides(sketch, dim).forEach(tryKeeping);
  222. if (!best) {
  223. tryKeeping([]);
  224. }
  225. if (best) {
  226. copyPlaces(best.copy, sketch);
  227. }
  228. return !!best;
  229. }
  230. // solveChange(sketch, ids): solve after the value of the dimensions
  231. // `ids` was edited. A plain solve shares a change out over the whole
  232. // sketch: shortening a rectangle moved the edge it shares with the
  233. // shapes beside it, dragging them along, or turned shapes over. Here the
  234. // edited dimension moves only what it must, and an edge that is joined
  235. // to others stays. Several dimensions are settled one at a time, each
  236. // from the sizes the sketch has now; if that fails, all at once with
  237. // everything held softly. Same result as solve().
  238. function solveChange(sketch, ids) {
  239. const wanted = new Set([].concat(ids || []));
  240. const dims = sketch.constraints.filter(function (c) {
  241. return wanted.has(c.id) && !c.driven;
  242. });
  243. if (!dims.length) {
  244. return solve(sketch);
  245. }
  246. const start = JSON.stringify(sketch.geometry);
  247. const values = dims.map(function (d) {
  248. return d.value;
  249. });
  250. // The others wait at what they measure now, so each step changes one
  251. dims.forEach(function (d) {
  252. const now = measure(sketch, d);
  253. if (isFinite(now)) {
  254. d.value = now;
  255. }
  256. });
  257. let ok = true;
  258. dims.forEach(function (d, i) {
  259. d.value = values[i];
  260. ok = ok && settle(sketch, d);
  261. });
  262. dims.forEach(function (d, i) {
  263. d.value = values[i];
  264. });
  265. if (!ok) {
  266. copyPlaces({ geometry: JSON.parse(start) }, sketch);
  267. if (dims.length > 1) {
  268. ok = settle(sketch, { type: 'none' });
  269. }
  270. if (!ok) {
  271. // Nothing held: the plain solve below decides on its own
  272. copyPlaces({ geometry: JSON.parse(start) }, sketch);
  273. }
  274. }
  275. return solve(sketch);
  276. }
  277. return {
  278. solve: solve,
  279. solveChange: solveChange,
  280. destroy: function () {
  281. wrapper.destroy_gcs_module();
  282. }
  283. };
  284. }
  285. // Solve a sloppy quadrilateral into a fully constrained 60 x 40 rectangle.
  286. // Returns { ok, dof, ms }; used at start-up to confirm the solver works here.
  287. export async function selfTest() {
  288. const solver = await createSolver();
  289. const started = performance.now();
  290. const sketch = {
  291. geometry: [
  292. { id: 'p1', type: 'point', x: 1, y: -2 },
  293. { id: 'p2', type: 'point', x: 52, y: 3 },
  294. { id: 'p3', type: 'point', x: 55, y: 31 },
  295. { id: 'p4', type: 'point', x: -3, y: 35 },
  296. { id: 'l1', type: 'line', p1: 'p1', p2: 'p2' },
  297. { id: 'l2', type: 'line', p1: 'p2', p2: 'p3' },
  298. { id: 'l3', type: 'line', p1: 'p3', p2: 'p4' },
  299. { id: 'l4', type: 'line', p1: 'p4', p2: 'p1' }
  300. ],
  301. constraints: [
  302. { id: 'c0', type: 'coincident', a: 'p1', b: '$o' },
  303. { id: 'c1', type: 'horizontal', line: 'l1' },
  304. { id: 'c2', type: 'vertical', line: 'l2' },
  305. { id: 'c3', type: 'horizontal', line: 'l3' },
  306. { id: 'c4', type: 'vertical', line: 'l4' },
  307. { id: 'd1', type: 'distance', a: 'p1', b: 'p2', value: 60 },
  308. { id: 'd2', type: 'distance', a: 'p2', b: 'p3', value: 40 }
  309. ]
  310. };
  311. const result = solver.solve(sketch);
  312. const corner = sketch.geometry[2];
  313. const ok = result.ok && Math.abs(corner.x - 60) < 1e-6 && Math.abs(corner.y - 40) < 1e-6;
  314. const ms = performance.now() - started;
  315. solver.destroy();
  316. return { ok: ok, dof: result.dof, ms: ms };
  317. }