feat(patterns): closed-form solvers for common mate patterns #27

New Issue

forbes · 2026-02-20T22:26:25Z

forbes commented

2026-02-20 22:26:25 +00:00

Summary

Implement the patterns/ module — analytical solvers for common constraint combinations that have closed-form geometric solutions, avoiding Newton-Raphson entirely for trivial subproblems.

Context

Most real assemblies are dominated by a small set of recurring mate patterns (shaft-in-hole, planar contact, fixed lock). These patterns have exact analytical solutions computable in microseconds. By recognizing and solving them during decomposition, the numerical solver only handles genuinely complex subproblems. D-Cubed (Siemens) uses this same strategy — algebraic solutions where possible, variational methods only for simultaneous systems.

Depends on: #26 (decomposer — provides biconnected components to match against)

Design

Pattern matching interface

class Pattern(ABC):
    @abstractmethod
    def name(self) -> str: ...

    @abstractmethod
    def match(self, part_ids: set[str], constraints: list[Constraint]) -> bool:
        """Return True if this pattern matches the given subproblem."""

    @abstractmethod
    def solve(self, parts: list[Part], constraints: list[Constraint]) -> list[SolveResult.PartResult]:
        """Return analytical placements for matched parts."""

class PatternMatcher:
    def __init__(self, patterns: list[Pattern] | None = None): ...
    def try_match(self, subproblem: Subproblem, ctx: SolveContext) -> tuple[str, list[PartResult]] | None:
        """Try each pattern in priority order. Return (pattern_name, placements) or None."""

Initial patterns

1. fixed_joint.py — Lock constraint

Match: exactly 1 constraint of type Fixed between 2 parts
Solve: locked part placement = grounded part placement * marker_i.inverse() * marker_j
DOF removed: 6 (fully determined)

2. shaft_in_hole.py — Coincident + Concentric

Match: 2 constraints between same 2 parts, one Coincident + one Concentric (or single Cylindrical)
Solve: align axes (from concentric markers), then translate to coincident point
DOF removed: 5 (1 rotational DOF remains around shared axis)
Returns placement that satisfies both constraints analytically

3. planar_contact.py — Planar + Parallel (or single Planar)

Match: Planar constraint (face-on-face), optionally with Parallel
Solve: align face normals, translate to contact distance (offset from params[0])
DOF removed: 3 (2 translational + 1 rotational DOF remain in-plane)

4. point_lock.py — Coincident (point-on-point)

Match: single Coincident constraint between 2 parts
Solve: translate part_j so marker_j coincides with marker_i
DOF removed: 3 (3 rotational DOF remain)

Transform math utilities

All patterns need quaternion/transform operations:

transform_compose(a, b) — apply transform b in frame a
transform_inverse(t) — inverse transform
quat_multiply(q1, q2) — quaternion multiplication (w,x,y,z convention)
quat_conjugate(q) — quaternion conjugate
axis_alignment_quat(from_axis, to_axis) — rotation aligning one axis to another

These should live in a shared math_utils.py within the decomposition package.

Tasks

Define Pattern ABC and PatternMatcher class
Implement fixed_joint.py pattern
Implement shaft_in_hole.py pattern
Implement planar_contact.py pattern
Implement point_lock.py pattern
Implement math_utils.py with transform/quaternion operations
Unit tests in tests/decomposition/test_patterns.py:
- Fixed joint: locked part ends up at correct placement
- Shaft-in-hole: axes aligned, coincident point satisfied
- Planar contact: normals aligned, offset respected
- Point lock: markers coincide after solve
- Pattern matcher returns None for non-matching subproblems
- Transform math: compose/inverse round-trip, axis alignment correctness

Acceptance criteria

Each pattern produces placements that satisfy its constraints to within 1e-9 tolerance
Pattern matcher correctly identifies applicable patterns and returns None for non-matches
All transform math operations are numerically stable and round-trip correctly

## Summary Implement the `patterns/` module — analytical solvers for common constraint combinations that have closed-form geometric solutions, avoiding Newton-Raphson entirely for trivial subproblems. ## Context Most real assemblies are dominated by a small set of recurring mate patterns (shaft-in-hole, planar contact, fixed lock). These patterns have exact analytical solutions computable in microseconds. By recognizing and solving them during decomposition, the numerical solver only handles genuinely complex subproblems. D-Cubed (Siemens) uses this same strategy — algebraic solutions where possible, variational methods only for simultaneous systems. Depends on: #26 (decomposer — provides biconnected components to match against) ## Design ### Pattern matching interface ```python class Pattern(ABC): @abstractmethod def name(self) -> str: ... @abstractmethod def match(self, part_ids: set[str], constraints: list[Constraint]) -> bool: """Return True if this pattern matches the given subproblem.""" @abstractmethod def solve(self, parts: list[Part], constraints: list[Constraint]) -> list[SolveResult.PartResult]: """Return analytical placements for matched parts.""" class PatternMatcher: def __init__(self, patterns: list[Pattern] | None = None): ... def try_match(self, subproblem: Subproblem, ctx: SolveContext) -> tuple[str, list[PartResult]] | None: """Try each pattern in priority order. Return (pattern_name, placements) or None.""" ``` ### Initial patterns **1. `fixed_joint.py` — Lock constraint** - Match: exactly 1 constraint of type `Fixed` between 2 parts - Solve: locked part placement = grounded part placement * marker_i.inverse() * marker_j - DOF removed: 6 (fully determined) **2. `shaft_in_hole.py` — Coincident + Concentric** - Match: 2 constraints between same 2 parts, one `Coincident` + one `Concentric` (or single `Cylindrical`) - Solve: align axes (from concentric markers), then translate to coincident point - DOF removed: 5 (1 rotational DOF remains around shared axis) - Returns placement that satisfies both constraints analytically **3. `planar_contact.py` — Planar + Parallel (or single Planar)** - Match: `Planar` constraint (face-on-face), optionally with `Parallel` - Solve: align face normals, translate to contact distance (offset from params[0]) - DOF removed: 3 (2 translational + 1 rotational DOF remain in-plane) **4. `point_lock.py` — Coincident (point-on-point)** - Match: single `Coincident` constraint between 2 parts - Solve: translate part_j so marker_j coincides with marker_i - DOF removed: 3 (3 rotational DOF remain) ### Transform math utilities All patterns need quaternion/transform operations: - `transform_compose(a, b)` — apply transform b in frame a - `transform_inverse(t)` — inverse transform - `quat_multiply(q1, q2)` — quaternion multiplication (w,x,y,z convention) - `quat_conjugate(q)` — quaternion conjugate - `axis_alignment_quat(from_axis, to_axis)` — rotation aligning one axis to another These should live in a shared `math_utils.py` within the decomposition package. ## Tasks - [ ] Define `Pattern` ABC and `PatternMatcher` class - [ ] Implement `fixed_joint.py` pattern - [ ] Implement `shaft_in_hole.py` pattern - [ ] Implement `planar_contact.py` pattern - [ ] Implement `point_lock.py` pattern - [ ] Implement `math_utils.py` with transform/quaternion operations - [ ] Unit tests in `tests/decomposition/test_patterns.py`: - Fixed joint: locked part ends up at correct placement - Shaft-in-hole: axes aligned, coincident point satisfied - Planar contact: normals aligned, offset respected - Point lock: markers coincide after solve - Pattern matcher returns None for non-matching subproblems - Transform math: compose/inverse round-trip, axis alignment correctness ## Acceptance criteria - Each pattern produces placements that satisfy its constraints to within 1e-9 tolerance - Pattern matcher correctly identifies applicable patterns and returns None for non-matches - All transform math operations are numerically stable and round-trip correctly

forbes referenced this issue

2026-02-20 22:26:57 +00:00

feat(dispatch): subproblem dispatcher to backend solvers #28

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: kindred/solver#27