Darwinbots Forum
Code center => Darwinbots3 => Topic started by: Numsgil 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 (http://svn.darwinbots.com/Darwinbots3/Trunk/Modules/Annulus/Annulus.UnitTests/SweptCollisionDetection/RotatingPointvsRotatingLineTests.cs). 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.
-
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.
-
Willing to help, but afraid it'll go over my head. Especially if you say it'll be a pain.
-
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.
-
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:
-
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?
-
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?
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... 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 (http://www.microsoft.com/visualstudio/eng/downloads#d-2010-express).
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.
-
I got VS2012, going to grab VS2010.
-
In VS2010 I can compile Annulus and Azimuth, but I get an compatibility wizard with the onlinecalculator that's in Azimuth.
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
-
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)
-
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.
-
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.
-
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 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.
-
Hey Peter, are you still interested in helping? I'll need some tests in the next few days. If you decided it's too difficult or time intensive to help, no worries :) I just need to know if I should start speccing it out or if you have this under control and I should just be patient.
-
I am! :)
It's not that's it's too difficult or time intensive. Just that I haven't spend much time on it. I hope you weren't waiting for me. :x
I'll do my best to create a patch today. Although don't expect there to be a lot of tests in there. If you then could take a look and confirm they work properly. (and with that likely take more of your time then if you would've written then yourselves :wacko:)
-
In SafeStepForward and SafeStepBackward, what is currRoot and nextRoot?
-
I hope you weren't waiting for me.
Nope; I've been working on fleshing out all the code to look approximately like I want. I have dozens of tests that are failing right now, so I haven't exhausted my to do list just yet. But I hope to get things working in the next few days, and then I'll need some new tests to push the code with.
I'll do my best to create a patch today. Although don't expect there to be a lot of tests in there. If you then could take a look and confirm they work properly. (and with that likely take more of your time then if you would've written then yourselves :wacko:)
Yeah, I'll definitely look it over. To be honest it's not even an issue of the time it takes. It's just exhausting thinking through the setups. Especially the more complex ones involving both bodies rotating and moving.
In SafeStepForward and SafeStepBackward, what is currRoot and nextRoot?
I'm probably going to remove both of those functions, so I wouldn't worry about writing tests for it. They aren't necessary for the new collision algorithm.
But to answer your question, the idea is that there's an intersection at some given time (the currRoot), and we want to step forward some amount of time until the derivative is non 0, and we haven't passed the next intersection (nextRoot).
-
Added 2 tests. Gotta start somewhere. ;)
In polygon vs. polygon. Does the test EdgeEdgeSolidHit work as it should?
I see CheckEqual(4, output.TOI); From the code behind it I assume it's the same as timeOfImpact. I also assume the polygon position is based on the center of the polygon. That makes from the distance of 10 at the center a effective distance of 8. That would mean the actual time of impact would be ~3.6 instead of 4. If not how does it define the start location of the polygon?
-
Added 2 tests. Gotta start somewhere. ;)
Great! I've added it to my working copy. I'm still neck deep in changes or I'd check it in right now.
In polygon vs. polygon. Does the test EdgeEdgeSolidHit work as it should?
I see CheckEqual(4, output.TOI); From the code behind it I assume it's the same as timeOfImpact. I also assume the polygon position is based on the center of the polygon. That makes from the distance of 10 at the center a effective distance of 8. That would mean the actual time of impact would be ~3.6 instead of 4. If not how does it define the start location of the polygon?
It's 8, yeah. Hmm... check my math?
1/2 * (-1 ) * t^2 = -8
t = 4
I stopped working on the tests in poly vs poly as it became obvious that I needed to return more than a single hit. That's what I'm working out right now. I should have some proper tests for you to use as a template in the next few days. But if you'd like to think up some tests cases in the mean time, all the better. This is the struct for a hit I'm using currently:
public class Hit
{
public Scalar TOI;
public Polygon.Edge Edge;
public Scalar HitFraction;
public Polygon.Vertex Vertex;
public bool IsEntering;
}
In the case of vertex-vertex collisions, the hit fraction is 0 and only one hit is recorded. Hopefully that's enough to go on for now. Once I lock down the API a bit more I'll start checking things in.
-
Ah, that math does work out, never mind.
Where would I find the Hit objects. An array in RotatingSimplePolygonvsRotatingSimplePolygon.output or something?
-
It'll be a List<Hit> most likely, sorted by TOIs.
-
Just here to say that I would like to help with these tests. :) If you would me to, Peter?
-
Sure, if you can think of some complicated ways that polygons collide or just miss. If you know how to make the test cases even better. :)
All I did so far were just some hit and miss tests with squares. Waiting to turn that in till the API locks in so checks can be properly modified.
-
When I have time, I will try to, but it certainly seems more difficult than I can handle. If I get one done anyway, I'm sure that'll be a little help. If you can think of anything else that will need to be done, then I will try it. :)
-
It's mostly a matter of doing physics word problems in reverse. Which is hard but should be manageable.
-
I'm back from my hiatus. I've fixed a bunch of issues that were lingering and checked in the code I was working on last summer. Also fixed a few issues that might have been hitting on other peoples' machines after a fresh checkout. Everything compiles and LinevsPoint tests are passing, but everything else is a bit of a mess. I'm still working through it to clean up everything.
There's some legacy interface stuff I want to ditch, which I'll probably start concentrating on with the LinevsPoint tests first.
Anyone still around interested in helping?
-
Sure
-
Cool :) I still need to write a lot of the glancing hit tests. Do you want to sync to the latest on the repository and see if that looks like something you can do?
-
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.
-
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)
-
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 (http://msdn.microsoft.com/en-us/library/ie/gg193979(v=vs.85).aspx) 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.
-
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.
-
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 :)
-
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.
-
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.
-
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 (http://store.steampowered.com/hwsurvey). Literally 50% of people are running windows 7 64 bit.
-
The circle check seems like premature optimization to me!
-
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.
-
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.
-
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
-
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. :)
-
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.
Life should be marginally easier for people looking to help.
How?
I get to use all sorts of new toys in the framework
What toys?
(sorry, just being Curious)
-
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).
I get to use all sorts of new toys in the framework
What toys?
(sorry, just being Curious)
Right away I used MemberwiseCopy (http://msdn.microsoft.com/en-us/library/system.object.memberwiseclone%28v=vs.110%29.aspx), 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.
-
I am surprised you where able to even find bugs in c#.
Never found (any) use for the clone method and this sounds like it works somewhat the same. Guess I am not that advanced yet.