Code center > Darwinbots3

Helping

<< < (3/9) > >>

Numsgil:

--- Quote ---It's starting to look like I'll need to be familiar with Azimuth to a large degree as well to make sense of Annulus anyway, so that'll help with any physics or collision detection that I attempt to contribute to in the future.

--- End quote ---

Yeah, that's very true.  Azimuth provides the foundation of a lot of other code.


--- Quote ---I'll keep poking around in the code to learn more, but I think that starting off with Azimuth.DenseLinearAlgebra might be a good idea. If you have any of the resources that you mentioned, please send them my way.

--- End quote ---

Numerical Recipes in C (ebook), chapter 2, is a whole thing on Linear Algrebra.  Section 2.5 is on iteartive improvement to a solution.  It's a fairly simplistic treatment, but it's a good starting place, and it should be possible to adapt the ideas in it at least for simple LU and QR decompositions.

Note that you might need to use Azimuth.RobustAccumulator to get the high precision on the calculation of the "right hand side" it talks about, because of all the cancellation issues.

For more advanced treatments, there's a whole chapter in Numerical Linear Algebra on iterative refinement, but I haven't read it.  I'm also not sure if there's a free version available online, but it's a really common book so you might be able to find it in university libraries or find a cheap used copy.

There's also Gauss Seidel and Jacobi, which have the advantage that the matrix doesn't need to be decomposed first.  Jacobi parallelizes very well, from what I understand, so it's probably worth implementing a version of it to play with for that reason alone.

Be sure you get comfortable with DenseVector, since the basic operations it provides are going to be a lot faster than trying to manually iterate through loops, which is how most Linear Algebra algorithms are presented.

...

At the heart of Azimuth.DenseLinearAlgebra is LinearLeastSquares.SolveSystemWithConstraints, (it's the core solver I'm going to use for rigid body physics and fluid dynamics).  At the core of that is a Linear Complementarity Problem (LCP) solver based on "Algorithm 4.2.11 "Datnzig; van de Panne and Whinston"" in The Linear Complementarity Problem.  LCPs are this whole other beast from normal Linear Algebra math, but there's a chapter in that book about iterative methods and it's possible that there's a way to build an iterative solver for LCPs that would make things run much faster.  A lot of that book is available as sample pages online, but some key pages are missing, and it's a far less common book.  Also LCPs are a pain to understand (there's a lot of really opaque vocab and math involved).  So it might not be practical for you to dig too deep, but I'm not all that likely to explore anything in this direction for a while myself.

Numsgil:
Also, there's a whole thing called "conjugate gradient methods" that I haven't looked in to at all, but it sounds like they'd be fantastic to use, especially since I expect a lot of the problems we'll encounter in practice to be sparse (I started a sparse linear algebra package in Azimuth, but haven't gotten very far with it yet).

rwill128:
Wow. This is a great way to jump into math that I never thought I'd be involved with again.

Anyway, I'll just start off reading about the Gauss-Seidel and Jacobi methods and then read Numerical Recipes in C.

SlyStalker:
The article (Fluid Simulation for Video Games) seems complicated, but I guess if you just wanted to model the resistance caused by the fulid, it would be easier.

Numsgil:

--- Quote from: SlyStalker on April 16, 2013, 03:50:13 AM ---The article (Fluid Simulation for Video Games) seems complicated, but I guess if you just wanted to model the resistance caused by the fulid, it would be easier.

--- End quote ---

It is complicated :)

But yeah, I'm willing to cut corners because I'm mostly interested in how the fluid interacts with the bots, and not how the fluid interacts with itself, and with that a lot of the math doesn't matter.  I'll post a demo of what I have once I've fixed a few outstanding issues.

Navigation

[0] Message Index

[#] Next page

[*] Previous page