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.
Reimplementing constraint solver
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
Be nice to others! Respect the FreeCAD code of conduct!
Re: Reimplementing constraint solver
I took a look to the code. Looks good.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 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
Re: Reimplementing constraint solver
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/
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.
- DeepSOIC
- Veteran
- Posts: 7896
- Joined: Fri Aug 29, 2014 12:45 am
- Location: used to be Saint-Petersburg, Russia
Re: Reimplementing constraint solver
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...