Author Topic: Helping  (Read 14919 times)

Offline rwill128

  • Bot Builder
  • **
  • Posts: 67
    • View Profile
Helping
« on: September 07, 2012, 02:18:52 PM »
I have a background in C++, working 3d graphics libraries, and a college education in math up to various levels of calculus. It's all super rusty (5+ years old), but I'm willing to relearn and then learn some more.

I'd love to get involved helping with DB3. The program's really caught my attention this summer, and having just finished an English degree, I'm thinking about getting back into computer science. This would be a great project to keep me coming back and learning more.

I'm familiarizing myself with the wiki, getting the C# compiler working, downloading the libraries, etc. Once I've laid out the basics, how can I start helping. (Or learning more about the system/code, so I can eventually help.)

Thanks,

Rick

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Helping
« Reply #1 on: November 12, 2012, 02:57:16 AM »
Sorry, I missed this message somehow.  Are you still around?

Offline rwill128

  • Bot Builder
  • **
  • Posts: 67
    • View Profile
Re: Helping
« Reply #2 on: April 12, 2013, 01:59:33 AM »
Hey Numsgil,

Sorry I've been off the map for a long while. But I'm back in the programming game now, and yeah, I'd like to help.

I'm learning still, but it will be good to have something to cut my teeth on -- a specific goal or project.

So please, let me know what I can do or start learning to do if you're still around.

Thanks,

Ricky

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Helping
« Reply #3 on: April 12, 2013, 02:42:55 PM »
Good to see you again.

An interesting task you could do to get your feet wet is build something for the graphics engine to save out screenshots as SVG. I have some code already in Annulus for visualizing unit tests that produces SVG. It would just be a matter of taking that code and expanding it to handle more shape types and that sort of thing. It might also be possible to include animation data in JavaScript or something like that, but I don know how to do that. But it would let us save out basically movies from a sim and post them online in the forums.

If that doesn't sound interesting I have some other ideas, too.  Let me know how much vector calculus, linear algebra, programming data structures, etc you think you can handle.  I have tasks that involve GPGPU, fluid physics, rigid body physics, graphics shader programming, code refactoring/beautification, and optimizing code for speed and memory.

Offline rwill128

  • Bot Builder
  • **
  • Posts: 67
    • View Profile
Re: Helping
« Reply #4 on: April 12, 2013, 11:58:36 PM »
I'll take a look at Annulus tonight and see what's going on in the code. I'm definitely behind the curve, so we'll see how things go.

Should I request a password for changing code at this point (or at least adding comments), or should I just browse through it?

The fluid physics and rigid body physics sound really interesting, as do the graphics shader programming, code beautification, and code optimization. I think I'd be most capable of working on the physics-based problems to start off with.

As for my experience, I don't use math much in my day-to-day life anymore, but linear algebra is kind of like riding a bike.

As for vector calculus and advanced data structures... I did a bit of vector math and matrix math for the 3d graphics programming that I fuddled around with in high school. That was many moons ago, but with enough hours I think I can google my way into those subjects again.


Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Helping
« Reply #5 on: April 13, 2013, 02:13:36 AM »
In the short term just submit SVN patches.  I'll look them over and check them in if they look good.  After I get sick of doing that much work, I'll set you up with proper credentials to check in changes yourself :) 

...

If you're feeling adventurous here's some meatier problems.  They involve a lot of math and reading, but it sounds like you don't mind giving it a go:

...

I'm working on fluid physics right now.  I wouldn't mind some help, but there's a lot of weird ideas and vocab you need to get familiar with for any of it to make sense.  Here's some papers/links:

Basically I'm working on an incompressible "inviscid" "discrete vortex element"/"panel method" fluid sim.  Only I'm mostly interested in fluid/boundary interactions, so I'm strongly considering ignoring vortices entirely and only using a "potential flow".  Which represents a weird sort of fluid that has properties of both inviscid and really really viscous fluids at the same time.  But it's pretty fast to calculate.

...

For rigid body physics, right now, in Annulus, there's some code to do moving polygon vs moving polygon collision detection, and it's only partially finished.  In order to handle rotations and translations, I've been decomposing the polygons in to vertices and edges, and using numerical root finding techniques to find roots.  I think there's some edge cases (quite literally :) ) I haven't solved yet.  It's not conceptually too difficult, though you need a certain foundation in numerical root finding and a basic understanding of equations of motion.  And there's a lot of code to handle (it's very verbose for some reason.  Something I was going to refactor at some point. )

...

Also in Annulus the straight skeleton code I mentioned earlier is technically correct for all the toy problems I've thrown at it (and that involved way more work than I'd care to admit), but I've noticed that for larger polygons it can get confused and break for numerical reasons.  Even writing the unit tests for more complex cases would be helpful, as it takes a lot of work to transcribe the vertices for the polygons and find a straight skeleton solver somewhere online to give the "correct" answer.  Fixing the code up would be fantastic :)

...

There's a lot of linear algebra code in Azimuth.DenseLinearAlgebra.  Right now it's all direct methods (QR decompositions, Cholesky decompositions, etc.).  But some iterative methods would be useful, too.  Especially because I've noticed that decomposing even medium sized matrices (with about ~40 ros/cols) starts to introduce some numerical error.  Being able to "polish" answers with an iteration or two of some iterative solver would be really nice.  I don't know a whole lot about iterative solvers, though.  But it shouldn't be too hard.  If that sounds interesting you could work on that.  I can probably dig up some references to get you started.

...

This very week I've been working on optimizing the x86 assembly that the very low level linear algebra code is getting compiled to by the C# JITter.  However I'd like to be able to use AVX/SSE as well.  But there's no way in C# to indicate that those instructions should be used by the JITter.  So I need someone to explore various ways to force their use.  One possibility is slimgen.  Another possibility is having a C++/CLI version of the DenseVector code, but that adds a whole lot of complexity to the build process (since now it needs a C++ compiler, and separate DLLs for x86 and x64 builds).  And I'd like to the program to autodetect which instruction set is supported and automatically load the appropriate version, which means someone needs to much around with the internals of the JITter.  And I'd still like to test all the different versions against the unit tests, so there's that.

...

Those are all really meaty and hard to just jump in and start working on, but they're also IMO the most interesting problems.  Feel free to poke around the code base in the mean time and get a feel for things at least.

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
Re: Helping
« Reply #6 on: April 13, 2013, 02:14:14 PM »
cool stuff. I have to say it was a brave move to use 4 point polygons instead of circles. I don't know even where to begin to figure out fluid dynamics OR collision detection on these.  :) (Not that we had any proper fluid physics in DB2 anyway, even still)



Quote
n the short term just submit SVN patches.  I'll look them over and check them in if they look good.  After I get sick of doing that much work, I'll set you up with proper credentials to check in changes yourself

So you are saying that the SVN patches I submit do not make changes to the vb6 version? Or, is there like a virtual copy of the stuff I am working on?
« Last Edit: April 13, 2013, 02:40:03 PM by Botsareus »

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Helping
« Reply #7 on: April 13, 2013, 04:41:16 PM »
You've been committing changes, which are different from patches.  Patching produces files that have the diffs in them, and then someone else can use those to get your changes.

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
Re: Helping
« Reply #8 on: April 13, 2013, 05:21:29 PM »
oh cool

Offline rwill128

  • Bot Builder
  • **
  • Posts: 67
    • View Profile
Re: Helping
« Reply #9 on: April 13, 2013, 11:19:38 PM »
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.

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. Thoughts?
« Last Edit: April 13, 2013, 11:21:57 PM by rwill128 »

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Helping
« Reply #10 on: April 14, 2013, 12:59:47 AM »
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.

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.

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.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Helping
« Reply #11 on: April 14, 2013, 01:05:04 AM »
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).

Offline rwill128

  • Bot Builder
  • **
  • Posts: 67
    • View Profile
Re: Helping
« Reply #12 on: April 14, 2013, 12:29:44 PM »
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.

Offline SlyStalker

  • Bot Destroyer
  • ***
  • Posts: 132
  • nomnomnomnom
    • View Profile
Re: Helping
« Reply #13 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.
Knowledge is knowing that a tomato is a fruit; Wisdom is not putting it in a fruit salad.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Helping
« Reply #14 on: April 16, 2013, 04:07:33 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.

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.