Reimplementing constraint solver

Discussion about the development of the Assembly workbench.
User avatar
DeepSOIC
Posts: 7810
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Thu Jul 16, 2020 11:16 pm

I've set up a new branch for playing with hyperduals. https://github.com/DeepSOIC/FreeCAD-ell ... HyperDuals
The first implementation, based on recursive templates, is mostly up. It is different from cppduals, but I did look at cppduals' source code for some hints.
I have tested it by computing (x^4-x^2) at x=1, and it spitted out correct values of three derivatives. So i consider the concept proven.

The complexity of computation seems to be exponential for the number of derivatives. While it sounds bad, since I don't think we ever need derivatives higher than 3, it may not be a problem. Implementing functions is very easy.

I plan to at least try the alternative "brute-force" approach, with all derivatives stored in an array. This is going to be a lot more code, but the complexity seems to be n^3, and may even be further improved.
Then I will probably compare the two implementations to pick the faster one.
abdullah
Posts: 3534
Joined: Sun May 04, 2014 3:16 pm

Re: Reimplementing constraint solver

Postby abdullah » Sat Jul 18, 2020 5:15 am

DeepSOIC wrote:
Thu Jul 16, 2020 11:16 pm
I plan to at least try the alternative "brute-force" approach, with all derivatives stored in an array. This is going to be a lot more code, but the complexity seems to be n^3, and may even be further improved.
Then I will probably compare the two implementations to pick the faster one.
I took a look to the code. Looks good.

I would not be worried about the performance at all at this stage. Hyperduals is almost a corner case in normal sketcher usage, as DualNumbers are enough for 90% of the functionality. While testing may show otherwise, I am not expecting a latency perceivable as annoying even for that remaining 10%. Even if we landed in performance issues, it is the kind of performance optimization that can be done at the end by reimplementing some functions.

But, of course, I am not saying you should not have fun if you want to do it ;)
User avatar
saso
Posts: 1574
Joined: Fri May 16, 2014 1:14 pm
Contact:

Re: Reimplementing constraint solver

Postby saso » Tue Aug 25, 2020 8:47 am

Somewhat related to this topic, in general more about a game engine physics based animation, but with a lot of links to other related resources...

Improving Simulation and Performance with an Advanced Physics Solver
https://medium.com/roblox-tech-blog/imp ... a071a98d35

Improving an Iterative Physics Solver Using a Direct Method
https://www.youtube.com/watch?v=P-WP1yMOkc4

--- links from the article ---

Nonconvex Rigid Bodies with Stacking
https://graphics.stanford.edu/papers/ri ... bodies.pdf

Free textbook: Physics-Based Animation
https://iphys.wordpress.com/2020/01/12/ ... animation/

An Introduction to Physics-Based Animation
https://www.youtube.com/watch?v=b_WJ-HwalwU

Video Game Physics Tutorial - Part I: An Introduction to Rigid Body Dynamics
https://www.toptal.com/game/video-game- ... y-dynamics

Physics for Game Programmers: Understanding Constraints
https://www.youtube.com/watch?v=SHinxAhv1ZE

Robot Dynamics Algorithms
https://www.springer.com/gp/book/9781475764376

Analytical Methods for Dynamic Simulation of Non-penetrating Rigid Bodies
https://www.cs.cmu.edu/~baraff/papers/sig89.pdf

Impulse-based Simulation of Rigid Bodies
https://graphics.stanford.edu/courses/c ... /ibsrb.pdf

An Implicit Time-Stepping Scheme for Rigid Body Dynamics with Coulomb Friction
https://foswiki.cs.rpi.edu/foswiki/pub/ ... icra00.pdf

Fast Contact Force Computation for Nonpenetrating Rigid Bodies
https://www.cs.cmu.edu/~baraff/papers/sig94.pdf

Post-Stabilization for Rigid Body Simulation with Contact and Constraints
https://www.cs.rutgers.edu/~dpai/papers/ClinePai03.pdf

Iterative Dynamics with Temporal Coherence
https://pdfs.semanticscholar.org/f8d6/8 ... 86692e.pdf

Modeling and Solving Constraints
https://twvideo01.ubm-us.net/o1/vault/g ... ration.pdf

Linear-Time Dynamics using Lagrange Multipliers
https://www.cs.cmu.edu/~baraff/papers/sig96.pdf

--- some more links ---

Constraints
https://zalo.github.io/blog/constraints/

Inverse Kinematics
https://zalo.github.io/blog/inverse-kinematics/
Last edited by saso on Thu Oct 01, 2020 4:55 pm, edited 1 time in total.
User avatar
DeepSOIC
Posts: 7810
Joined: Fri Aug 29, 2014 12:45 am
Location: Saint-Petersburg, Russia

Re: Reimplementing constraint solver

Postby DeepSOIC » Fri Sep 11, 2020 1:18 am

Today i kinda returned, and bumped into an interesting problem: python examples I wrote no longer work, because ParaPoint is not accepted by constraints, they want a parashape. I don't quite remember where it all came to, all i really remember is that there were some perturbations around typesystem...