Author Topic: Collision detection tests  (Read 13978 times)

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Collision detection tests
« on: July 26, 2013, 04:52:56 PM »
I'm working on collision detection for physics right now.  I've redone the basic underlying algorithm, and as a result a lot of the old tests I have, while still useful, aren't fully testing what I need them to test.

If anyone has any time and interest in helping out, I basically need a whole suite of tests updated, and maybe some new ones written.  You can see the current tests here.  The old tests are only testing for the first intersection after some time, but the new algorithm finds all the intersections in an interval of time simultaneously, and I need to update the tests to reflect that.

I need tests that test each different part of a motion (linear velocity, linear acceleration, angular velocity, angular acceleration, that sort of thing), and there's a certain amount of combinatorial complexity that makes writing all the tests kinda a pain.

I can walk through it in more detail if anyone is interested.  I'll probably do it myself sometime in the next two weeks if no one volunteers, but I'm sort of dreading it.

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
Re: Collision detection tests
« Reply #1 on: July 29, 2013, 09:19:05 AM »
I kinda still want to work on DB2. I am still waiting on getting good hardware and most of this stuff is over my head anyway.

Offline Peter

  • Bot God
  • *****
  • Posts: 1177
    • View Profile
Re: Collision detection tests
« Reply #2 on: July 29, 2013, 04:11:10 PM »
Willing to help, but afraid it'll go over my head. Especially if you say it'll be a pain.
Oh my god, who the hell cares.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Collision detection tests
« Reply #3 on: July 29, 2013, 05:09:06 PM »
If you've completed an entry level physics course in University you should be good.  It's stuff like: if a box is falling at 10 m/s/s, how long does it take to impact another box rotating at Pi/2 radians/s.  Only the starting conditions don't matter; only the impact time.  So I've just been starting at the impact time with an arbitrary configuration and working backwards 2 or 3 seconds.

As a first step, can you try syncing to the DB3 SVN and grabbing the code?  Try building Azimuth.sln and Annulus.sln locally, and let me know if you have any issues.  There's going to be some unit test failures in both of those solutions, but it should compile at least.

Offline Peter

  • Bot God
  • *****
  • Posts: 1177
    • View Profile
Re: Collision detection tests
« Reply #4 on: July 29, 2013, 06:06:45 PM »
When compiling Azimuth.

Error list
Error   193   The command "call L:\darwinbots3\source\Modules\Azimuth\..\..\3rdParty\mcpp\bin\release\mcpp L:\darwinbots3\source\Modules\Azimuth\Azimuth\DenseLinearAlgebra\DenseVectorPre.cs L:\darwinbots3\source\Modules\Azimuth\Azimuth\DenseLinearAlgebra\DenseVector.cs
call L:\darwinbots3\source\Modules\Azimuth\..\..\bin\release\Reformatter L:\darwinbots3\source\Modules\Azimuth\Azimuth\DenseLinearAlgebra\DenseVector.cs" exited with code 1.   Azimuth

Output
1>------ Build started: Project: Azimuth, Configuration: Debug x86 ------
1>  The system cannot find the path specified.
1>  'L:\darwinbots3\source\Modules\Azimuth\..\..\bin\release\Reformatter' is not recognized as an internal or external command,
1>  operable program or batch file.
1>c:\Windows\Microsoft.NET\Framework\v4.0.30319\Microsoft.Common.targets(1063,5): error MSB3073: The command "call L:\darwinbots3\source\Modules\Azimuth\..\..\3rdParty\mcpp\bin\release\mcpp L:\darwinbots3\source\Modules\Azimuth\Azimuth\DenseLinearAlgebra\DenseVectorPre.cs L:\darwinbots3\source\Modules\Azimuth\Azimuth\DenseLinearAlgebra\DenseVector.cs
1>c:\Windows\Microsoft.NET\Framework\v4.0.30319\Microsoft.Common.targets(1063,5): error MSB3073: call L:\darwinbots3\source\Modules\Azimuth\..\..\bin\release\Reformatter L:\darwinbots3\source\Modules\Azimuth\Azimuth\DenseLinearAlgebra\DenseVector.cs" exited with code 1.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

:dry:
Oh my god, who the hell cares.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Collision detection tests
« Reply #5 on: July 29, 2013, 06:49:42 PM »
Hmm...

Can you verify that you have these files synced over?

3rdParty/mcpp/bin/Release/mcpp.exe
Bin/Release/Reformatter.exe

Then, if you call:

L:\darwinbots3\source\Modules\Azimuth\..\..\bin\release\Reformatter L:\darwinbots3\source\Modules\Azimuth\Azimuth\DenseLinearAlgebra\DenseVector.cs

from the command line, what happens?

Offline Peter

  • Bot God
  • *****
  • Posts: 1177
    • View Profile
Re: Collision detection tests
« Reply #6 on: July 30, 2013, 03:30:14 AM »
Hmm...

Can you verify that you have these files synced over?

3rdParty/mcpp/bin/Release/mcpp.exe
Bin/Release/Reformatter.exe
Seems they didn't. They do now!

Then, if you call:

L:\darwinbots3\source\Modules\Azimuth\..\..\bin\release\Reformatter L:\darwinbots3\source\Modules\Azimuth\Azimuth\DenseLinearAlgebra\DenseVector.cs

from the command line, what happens?

Quote
Unhandled Exception: System.ArgumentNullException: Value cannot be null.
Parameter name: type
   at System.Activator.CreateInstance(Type type, Boolean nonPublic)
   at System.Activator.CreateInstance(Type type)
   at Reformatter.Program.FormatFile(String file)
   at Reformatter.Program.Main(String[] args)

Same result after a update and a clean checkout.
Oh my god, who the hell cares.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Collision detection tests
« Reply #7 on: July 30, 2013, 12:59:49 PM »
Oh... which version of Visual Studio do you have installed?  I think it's set up for VS2010 right now.  If you have VS2012, that would explain the problem.

Sorry, I know it's a huge pain, but I think you can still grab 2010 from Microsoft: clicky.

If you do have VS2010 installed it means I probably set it up to work with the pro version and extra steps are necessary to get it working for the express version.

Offline Peter

  • Bot God
  • *****
  • Posts: 1177
    • View Profile
Re: Collision detection tests
« Reply #8 on: July 30, 2013, 01:37:03 PM »
I got VS2012, going to grab VS2010.
Oh my god, who the hell cares.

Offline Peter

  • Bot God
  • *****
  • Posts: 1177
    • View Profile
Re: Collision detection tests
« Reply #9 on: July 31, 2013, 05:42:00 AM »
In VS2010 I can compile Annulus and Azimuth, but I get an compatibility wizard with the onlinecalculator that's in Azimuth.

Quote
The solution or project you are opening must be converted. It was either created in a previous version of Visual Studio, or it relies on an older version of a program that you have installed on your computer. ... When converted it may not run in earlier versions

After I go through the wizard it can't find System.Web, System.web.extensions, System.Web.Mobile.

Version I'm using.
Microsoft Visual Studio 2010
Version 10.0.30319.1 RTMRel
Microsoft .NET Framework
Version 4.5.50709 RTMRel
Oh my god, who the hell cares.

Offline Botsareus

  • Society makes it all backwards - there is a good reason for that
  • Bot God
  • *****
  • Posts: 4483
    • View Profile
Re: Collision detection tests
« Reply #10 on: July 31, 2013, 11:35:30 AM »
Peter, what is your level of knowledge Math/Physics wise?

(I flunked calculus believe it or not :P One of this days I will have to buy some self study kits)

Offline Peter

  • Bot God
  • *****
  • Posts: 1177
    • View Profile
Re: Collision detection tests
« Reply #11 on: July 31, 2013, 12:39:39 PM »
Quite rusty, learned it at some point, but don't have to use it much. Might need to read in a bit on differential equations or geometry.

Possibly you'll learn better completely on your own then with a teacher. Sadly some teachers manage to make it more complicated then it actually is.
Oh my god, who the hell cares.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Collision detection tests
« Reply #12 on: July 31, 2013, 01:09:49 PM »
In VS2010 I can compile Annulus and Azimuth, but I get an compatibility wizard with the onlinecalculator that's in Azimuth.

Ignore that.  I think it's unloaded from the solution by default?  It was going to be a way to do some math via a web interface to help me spec out some stuff, but it never went anywhere and the window of usefulness sort of passed on it.

Anyway, now that things are building can you take a look at Modules/Annulus/Annulus.UnitTests/SweptCollisionDetection/RotatingPointvsRotatingLineTests.cs and see if it sort of makes sense to you?

Basically, for the collision of a box vs another box, I've decomposed it in to vertices (points in space) vs line segments.  And to do point vs. line segment, I first do point vs. infinite line, and then clip it to the segment's range.

SimpleLinearMotion_Velocity should hopefully make sense to you, for instance.  It might help to draw some of the tests out on graph paper to get an idea of what they're doing.  There should be ample comments in the actual source code for all the different parameters on the input struct.

I basically need to test a variety of combinations of linear and angular motion to be sure that the code is actually working.  The point vs line tests are mostly done, but point vs. segment I think are missing some tests still, and polygon vs polygon are pretty much missing entirely.

For point vs. segment tests, in addition to just hitting the line segment squarely in the center other good tests are to hit it exactly on its end, to be sure that the code that clips the points to the segments is working correctly.

If you start looking at what tests are there, it will hopefully inspire you about what other tests could be done.

Most new tests you write will probably fail, just because the backend code isn't done, so don't worry about that.

Offline Peter

  • Bot God
  • *****
  • Posts: 1177
    • View Profile
Re: Collision detection tests
« Reply #13 on: July 31, 2013, 02:55:53 PM »
I think I understand enough of it to make some tests. I think I'll make some tomorrow.

What's the DOUBLE_ROOT in the ending states, 2 intersections?
Oh my god, who the hell cares.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Collision detection tests
« Reply #14 on: July 31, 2013, 04:38:06 PM »
I think I understand enough of it to make some tests. I think I'll make some tomorrow.

What's the DOUBLE_ROOT in the ending states, 2 intersections?

I redid a lot of the backend and won't need it anymore, but basically it represented a parabola that didn't quite hit the X axis.  Imagine y = x^2 + 1e-10, for instance.  It was the way the root solver flagged that the first derivative had hit 0, but it hadn't managed to actually find the root.  But it would only occur for things that were almost roots.  Usually issues with floating point accuracy.