Code center > Darwinbots3
Collision detection tests
Botsareus:
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.
Peter:
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.
Numsgil:
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.
Peter:
The circle check seems like premature optimization to me!
Numsgil:
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.
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version