Author Topic: Collision detection tests  (Read 13966 times)

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Collision detection tests
« Reply #30 on: December 28, 2013, 08:09:59 PM »
Just to add more detail:

You'll want to get Annulus building.  I think all the tests should build.  You'll need Visual Studio 2010 still.

if you look in Modules\Annulus\Annulus.UnitTests\SweptCollisionDetection\PolygonvsPolygonTests.cs, there's a bunch of tests for solid hits for edge-vs-edge, edge-vs-vertex and vertex-vs-vertex.  But I don't really have any tests for two polygons sliding against each other or just touching and then leaving each other.

Offline Peter

  • Bot God
  • *****
  • Posts: 1177
    • View Profile
Re: Collision detection tests
« Reply #31 on: December 29, 2013, 06:40:42 PM »
Managed to get a compatibility warning when installing VS2010 on windows 8.1. :huh:

Getting some failed tests. Nothing that seems troubling, but I had some issues on installation and initial running the project :glare: so I'll post them just in case.

Error   1   "Element
  • : Expected "GlancingNoMotion 0 <0 : 0>" but was "Entering 0 <5 : 0>"" in "Annulus.UnitTests.SweptCollisionDetection::CirclevsCircleTests.NoMotionTests::NoMotion_Intersecting_Incident"   J:\SVN\darwinbots\source\Trunk\Modules\Annulus\Annulus.UnitTests\SweptCollisionDetection\CirclevsCircleTests.cs   106   Annulus.UnitTests

Error   2   "Element
  • : Expected "GlancingNoMotion 0 <0 : 0>" but was "Entering 0 <1 : 0>"" in "Annulus.UnitTests.SweptCollisionDetection::CirclevsCircleTests.LinearMotionTests::CoMovement_JustIntersecting"   J:\SVN\darwinbots\source\Trunk\Modules\Annulus\Annulus.UnitTests\SweptCollisionDetection\CirclevsCircleTests.cs   219   Annulus.UnitTests

Warning   3   "The triangulator needs to be able to handle non parallel edges." in "Annulus.UnitTests.CSG::TriangulationTests.FindSharedEdgesTests::Parallel"   J:\SVN\darwinbots\source\Trunk\Modules\Annulus\Annulus.UnitTests\CSG\TriangulationTests.cs   1208   Annulus.UnitTests
Warning   4   "CutEdgesWithNearbyVertices tests." in "Annulus.UnitTests.CSG::TriangulationTests.CutEdgesWithNearbyVerticesTests::Todo"   J:\SVN\darwinbots\source\Trunk\Modules\Annulus\Annulus.UnitTests\CSG\TriangulationTests.cs   1216   Annulus.UnitTests
Error   5   The command ""J:\SVN\darwinbots\source\Trunk\Junk\Annulus.UnitTests\Debug\Annulus.UnitTests.exe"" exited with code 2.   Annulus.UnitTests

What are the different glancing transitionstates? Is it possible to generate images of certain steps?(it would help checking my own math)
Oh my god, who the hell cares.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Collision detection tests
« Reply #32 on: December 29, 2013, 08:20:00 PM »
I literally just did the CirclevsCircle stuff this week, so it's possible I haven't flushed through a change I need to to make it work.  I wouldn't worry about it for now.

The warnings are not failures as much as a running TODO list.

Upgrading to VS 2013 is on my todo list, but I haven't tackled it yet.  I imagine it will make this stuff much easier.

...

Basically:

Entering/Exiting - A forcefull collision, with the collider entering or exiting the collidee.
GlancingParallel - Two features (ie: vertex or edge) are rubbing against each other in such a way that they are neither entering nor exiting each other.  Imagine one box sliding on top of another, for instance.
GlancingInside/Outside - Imagine throwing a ball up to the ceiling so that it *just* touches the ceiling and then falls back down.  Here, *just* means it has 0 velocity when it touches.  Inside/Outside indicates whether you're inside the polygon glancing against the boundary from the inside or outside the polygon glancing against the boundary from the outside.
Stationary - Means the two features are intersecting but not moving relative to each other.  Basically if you had a GlancingParallel collision and froze the motion, it would be Stationary.
GlancingParallelEntering/Exiting - I don't think this will get returned by anything; it's mostly used internally.
FeaturesAligning - Usually means two polygons are really deeply penetrating.  Basically the interior side of one feature is colliding against the exterior side of another feature, and continuing on.

I need to play with it all some more.  I might collapse some of the states, or rename them, or combine them, or add more.  I don't have a good intuitive sense of what the different states really are for two colliding polygons.  I originally thought I could get away with just entering/exiting states but I need more data than that when I process the results of the collision detection algorithm to feed it in to a useful format.

...

In terms of visualizing, there isn't anything super convenient right now.  If you were feeling adventurous you could see about generating animated SVGs from the test description.  The SimplePolygon class already has something for spitting out SVG descriptions of the polygons, for instance, and there's a javascript library I'm using to allow the mouse to zoom and pan the image in the browser.  See for instance Modules\Annulus\Annulus.UnitTests\CSG\StraightSkeletonBuilderTests.cs, around line 1160, where I set up a full SVG for a test.  I haven't played with it at all but I think SVG animation is possible.  The advantage of SVG animation is that you can literally specify the angular velocity, position, linear velocity, etc. and update the elements' transforms from those, so it would be the easiest way to visualize what the input data is doing.  Of course, it involves very webby programming, which I'm not all that knowledgeable about so I don't know how much help I could give.  It's almost certainly worth the effort if you could do it.

There's also Annulus.Testbed, but whether you can get it to run or not is questionable.  You'd have to manually copy the test input data to Modules\Annulus\Annulus.Testbed\Main.cs to get it to work.  And I haven't done much proofing of the graphics stuff so I'm not sure what you'd have to have installed in terms of DirectX SDKs, etc., to make sure it would work.


Offline Peter

  • Bot God
  • *****
  • Posts: 1177
    • View Profile
Re: Collision detection tests
« Reply #33 on: December 30, 2013, 05:54:23 PM »
Patch attached, the last test has a weird end result or at least I don't get it.

Also for VS2010 the main issue wasn't the compatibility. But some protection program in the background messing around where it shouldn't. Just found it messed up I got that message, it's not old enough to expect it and the program itself is even written by microsoft.
Oh my god, who the hell cares.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Collision detection tests
« Reply #34 on: December 31, 2013, 02:10:47 AM »
Thanks!  I modified some of the expected results a bit and submitted them.  Two of them are currently failing.  The way I decide how to interpret a transition is currently really mucky and these new tests show I need to either add some new cases or more likely bite the bullet and really figure out how the transitions are supposed to work.  The current system is really ad hoc which is never a good sign. :/

Anyway, good start.  Keep them coming :)

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 #35 on: January 01, 2014, 10:27:15 AM »
Question: Why circle vs circle? I though we are working with four point polys...

I actually played with VS2012 and really hated it:

1.) I hate metro
2.) Stuff will not run on XP

The only real advantage I have seen is an attempt to support multi touch.

Question: Why 2013?

Thx.

Offline Peter

  • Bot God
  • *****
  • Posts: 1177
    • View Profile
Re: Collision detection tests
« Reply #36 on: January 01, 2014, 12:48:02 PM »
1) I ran VS2012 without anything metro like, did you run the metro version?(is there a metro version?)
2) Do you still run XP?

The CAPPED menu options was all that bothered me somewhat with VS2012. And likewise that's something that can be changed.

2013 is newest, newest is best. That would be my reasoning though, at some point you would have to move on to a newer version. I didn't actually try VS2013 yet, can't say much about it.
Oh my god, who the hell cares.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Collision detection tests
« Reply #37 on: January 01, 2014, 02:05:47 PM »
The poly-vs-poly method I'm currently using is clever and sophisticated, if I do say so myself.  It's also relatively novel.  I don't think anyone is trying to do collision detection like this.  I might try even writing a paper on it. But it's also incredibly slow at present.  It's O(n^2) for the number of features in the polygons, since I do each vertex of each polygon against each edge of the other polygon.  For each feature pair, I then need to do an O(k^3) algorithm (where k is related to how fast the two bodies are rotating) to find the times of intersection of the pair.  Also, I need to accurately determine the distance between the vertex of one polygon and the line segment of another at some given time value, and it turns out that simply doing the rotation and translation the obvious way results in too much numerical noise to really be useful, so on top of everything else I have a really expensive constant in front of that O(n^2) and O(k^3).

So how slow is slow, you might ask?  Currently I can run a 6 body sim at about 5 FPS or so.  Not unusably slow, but the method isn't going to supplant the normal techniques anytime soon.

I'm currently working out how to cache some of the work that's getting done, which should improve performance by quite a bit, but it's always going to be a source of performance problems.  What's needed here is a "midphase" check.  Basically don't check two polygons or features against each other if we don't have to, because they're far enough apart.

It turns out that for circle-vs-circle, angular velocity doesn't matter.  That's because a circle rotated around its center is still the same circle.  Which means you can determine the time of collision of two circles undergoing ballistic motion in constant time using a quartic polynomial.  Solving a quartic is still a tiny bit slow, but way faster than the polygon-vs-polygon check.

So my plan is to wrap a circle around each polygon, centered at its center of mass, and use that to form "windows" where it's possible for two polygons to intersect.  If the circles don't intersect, the polygons don't intersect.  If the circles intersect, we just switch over to the more sophisticated polygon-vs-polygon collision detection.

...

VS 2008 is still my preferred version, actually.  The leap to 2010 broke a bunch of stuff I use a lot on C projects.

However, unlike for C++ programming, the version actually matters a lot for C# programming.  They keep building new releases of the .NET framework and C# language, and you need the latest IDE to actually use the language features.  There's also bug fixes to the framework, and I do rarely hit some of them.

Also, assuming you're stuck in 2010 or more recent, the later IDEs improve responsiveness and stability immensely.

The stuff that most people don't like, like the color scheme and all caps menu, can be changed with various add ons and registry hacks in VS 2012 at least.  Hopefully for 2013 it's similar.

...

You're still running XP?  I can understand not wanting to run Vista or 8, but 7 has been kind of the de facto OS for a while now.  Check out the steam hardware survey.  Literally 50% of people are running windows 7 64 bit.

Offline Peter

  • Bot God
  • *****
  • Posts: 1177
    • View Profile
Re: Collision detection tests
« Reply #38 on: January 01, 2014, 02:43:11 PM »
The circle check seems like premature optimization to me!
Oh my god, who the hell cares.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Collision detection tests
« Reply #39 on: January 01, 2014, 03:28:57 PM »
Not at all; I've got a simple physics engine working under the Lodestone module based on the current collision detection and response stuff I've got working right now.  It's crashy but I can measure the performance of it, at least, and trace back to where all that time is going.  On top of that, I have experience with physics engines, so I know what sort of optimizations get made, what sort of performance to expect, etc.

That said, the circle stuff isn't actually used anywhere yet.  But it will be.  I'm leaving it out for now to make it easier to see performance impacts of changes to the collision detection stuff, and to make it easier to find bugs in 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 #40 on: January 02, 2014, 10:10:40 AM »
That collision things are very smart, good job.



Interesting, So I can hack visual2012 to make look ok? I have to mess with that some day.



I do have 7 on my laptop.

But I did buy my tower when the latest they had was crappy vista.
So I figured I install XP and Vista on my tower.
I am considering a new tower based on your specs and put XP (I want to save my XP image because of a software called "IPhotoPlus") and windows 8.1

However, I got a chance to play with 2012 when I was working. They also have some older soft that does not like anything later then XP. So, half of there comps are running XP.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Collision detection tests
« Reply #41 on: January 06, 2014, 04:19:27 PM »
Okay, I've upgraded everything to VS 2013.  Life should be marginally easier for people looking to help, and I get to use all sorts of new toys in the framework :D

Offline Peter

  • Bot God
  • *****
  • Posts: 1177
    • View Profile
Re: Collision detection tests
« Reply #42 on: January 08, 2014, 01:55:14 PM »
Windows 8 got hyper-v(do all versions of win8 have this?), you could try to make a image of XP and run it in a virtual machine when you need the program.

Time to download VS2013. :)
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 #43 on: January 09, 2014, 06:03:36 PM »
Yea I know I can make a new virtual image, but I want to save my current image, 1 reason being I am too lazy to dig trough my cd collection to find the software to reinstall the second reason being I like how everything is organized in that image (and I also have a 'left' copy of visio that I will not be able to reinstall).

However, I planning to get a Nokia Lumina 2520  with 8.1RT and download 2013
Also, I think 2013 will run on my windows7 laptop.

Quote
Life should be marginally easier for people looking to help.

How?

Quote
I get to use all sorts of new toys in the framework

What toys?

(sorry, just being Curious)


Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Re: Collision detection tests
« Reply #44 on: January 09, 2014, 10:09:20 PM »
Quote
Life should be marginally easier for people looking to help.

How?

Visual Studio 2013 is slightly easier to get (you don't have to dig to find it).

Quote
Quote
I get to use all sorts of new toys in the framework

What toys?

(sorry, just being Curious)

Right away I used MemberwiseCopy, which is much faster than traditional ways to shallow copy.  Plus some mostly minor stuff, and a few bug fixes here and there that are nice not to have to work around.  Nothing too amazing, though.