I've been having trouble with collision detection/response in my spring system, but I think I finally found a solution. James Lohr previously suggested that I use a method to find a reference point in each object made of springs, so that any point attached to the same object would know which side of a line segment (ground, something like that) to rest on.

It occured to me that no spring should ever penetrate another in my system, and so I can find the appropriate resting side of a point by simply checking for a point it's attached to. In my head, this should work with any closed shape built of springs, and with any rope, as long as at least one point on the rope is fixed in the environment. (If a rope were lying on a resting surface, all of the connected points could pass through the ground at the same moment.)

The way I implemented this was to - first of all - change my collision testing function to accept springs (rather than points), so as to test pairs of connected points. Then, after my old collision checking, I find the direction of both points from the line segment (before and after velocity). If I find that point 1 (after velocity) has moved to a side of the line opposite point 2 (before velocity), I move point 1 to the point of collision between the line segment that is testing for collision, and the line segment formed between the two points I'm testing. The same is reversed for the case of point 2 moving over the line.

And uhm... It doesn't work. Doesn't really make a difference at all.

I'm soooo close to having this thing working, and I've been wracking my brain on this - with no results.
My (awkwardly-hacked-together-during-sudden-bursts-of-thought) implementation:

(And I attached the rest of that file (which has become a grotesque monster), just in case...)

So...can anyone help me out?

I'm having myself my share of problems with springs right now. I don't think I can help you, but I'll be waiting for a demo of your spring system.

Oh, everything was going really well...the springs are fantastically elegant (in my opinion) for representing...pretty much anything... Even the collision detection/response was going fine until... Gravity...

Totally wrecked the thing. It doesn't play well with my infinitely small points and lines. 80% of the time I've spent working on this system, I've just been attempting to deal with the monkey wrench that gravity threw at me.

Gravity shouldn't be too bad , just add the acceleration of gravity to all the particles in your system , find out how much force it causes according to their mass , calculate resultant counter-forces from fixed points and tension in connected objects , sum all the forces on each object , calculate their accelerations and then you can find their new positions. Geez , it's so simple , cmon. (Just kidding)

What are you using the tiny points and lines for? Also , how are you simulating ropes? Are they a collection of connected springs to propagate tension along the points of the rope?

Oh, the problem isn't with the gravity itself, it's just that the gravity causes undesirable reactions all over the place. (like, for instance, my points falling through lines that they should be resting on)

I want the points and springs to be used to make objects, so...I want them to be as non-object-like as possible? Like atoms connected by some mysterious cosmic force.

Yeah, just like that little rope demo I posted here. I wouldn't really be implementing it... But...when the user's building, either they make closed shapes or 'ropes', right?

From my experience, handling bodies during collision detection as a set of points and lines is really a pain in the butt.
I'm guessing you're just doing line intersection checks?
If your collision detection handling is static, you'll obviously miss a lot of collisions.
If it's dynamic, you'll probably be able to detect collisions, but how to resolve them is not always obvious, with special cases to consider.
I would recommend you to handle anything you can as polygons.
Try implementing SAT (Separating Axis Theorem), for example.
It would be more simple and efficient for polygonal objects, and if you extend it for dynamic collision detection, (which isn't really that hard), you'll be able to correctly handle separate lines and points as well.

[EDIT]

Consider these cases:

In the top case, the collision would just be missed.
You could pretend that it's the horizontal line that's moving with '-v' towards the vertical and handle the case, but you'd have to detect that.

In the bottom illustration, you see plenty of intersection points but it's not so obvious what to move where.

Is this a typo in your code?

        // And after velocity
  float dir1b = (a*b)-(b*c);

Isn't that supposed to be the dot product of the two vectors like the previous one (the assignment of dir1a)?

Also , you could simplify those direction checks a little :

  float dir1a = (a*d >= b*c) ? 1 : -1;
// instead of
  float dir1a = (a*d)-(b*c);
  if (dir1a >= 0) dir1a = 1;
  else dir1a = -1;

It only gets rid of the subtraction , but it does the same thing anyway.

Well...it'd catch the collision, but nothing would happen...but that's just because I still haven't gotten around to having the point impart force on springs they collide with. Soon as that's handled (which is something I need to do anyway...any two moving objects smacking into each other will behave awkwardly in my system at the moment), it'll work.

Yeah, that'd work just fine. Each point would get properly deflected, and the springs would do the rest.

Yeah! I'd have been mad as hell if that was the problem... But strangely, it didn't seem to make a difference, really...hmm...

Well...that's handy! It seems like I've seen something like that somewhere... It tests (a*d >= b*c) for true or false, and gives the first or second value based on the result, right?

[edit] Actually... I don't think it'd catch that top collision... I should change the checks to make them use relative velocity, rather than absolute velocity. That'd fix it, I think.

Yes , the a?b:c operator returns b if a is true and c if a is false. Although I wonder what the > operator actually does for floats.

Won't that let the other end pass over the line as much as the length of the distance between the points though?

    /___
   /

I seem to get the impression that you're not checking all moving points for collisions but only one part of each object?

You may look at some 2D and 3D engines. Since they deal with most of the stuff the programmers on a.cc deal with, especially with your kind of math and spring collisions, they may be worth a look.

The idea is that...when the two points are just hanging out, not colliding, they both have the same direction from the line. If one of them crosses, it can check itself against at least one of the points it's attached to to find which side of the line it should actually be on. If point1 (after adding velocity) is on the opposite side of the line, compared to point2 (before velocity), then point1 crossed the line during the last update, and needs to be placed back on the line. (in the case of a totally unattached rope, the entire thing may cross the line at the same time, ruining my idea...)

I'm actually checking each point several times. I'm checking every spring, and in any closed shape the endpoint of one spring will be the start-point of another, so on and so on. Especially in my cube, with it's cross-struts. (This is why I used that spring->p2->checked = true; bit.)

I thought those were both rigid-body engines...? I was considering seeing if I could ask this person some questions. It looks like they made just what I want to make.

[edit] Woooah, Bullet's got cloth and soft-body stuff! I'm sure it's still polygon-based, though...

Well, you see, relative velocity is great, but it basically means that you have to treat one object as static, and the other object as moving with the relative velocity.
The problem is that you have to chose which object would be the moving one correctly, or you'll get nonsensical collision information.
As for the first example I gave (with the polygon), sure, your system would handle it, but it would look more ridiculous the more rigid the body is.

[EDIT]

Some more bad cases:
http://img502.imageshack.us/img502/5980/evil2cy7.png
Sure, you could work around it, but it wouldn't be very fast, nor very elegant.
Been there, done that, it's just not worth the burden.

Let's say spring1 is the spring that is checking for collision (as in 'Hey, what's colliding with me?') and it accepts spring2 as the springs it's checking for a collision with. (as in 'Hmm...is spring2 going to run into me?') I figured it would work fine if I always treat spring1 as the static object, and spring2 as the dynamic one. I'd check every single spring's relationship with every other spring, (as in spring1 vs. spring2 and spring2 vs. spring1) but when it comes to collision response, I'd just use the absolute velocities for both.

With the relative velocities, both those cases would be handled just fine...I think. I don't see why they wouldn't. It might not be terribly fast, but it'd be just as elegant as what I've got going now.

If you haven't looked at the code, it might be important for me to mention that the 'line-line collision' check I use is actually between the line segment checking for collision and every single point. (the second line is between the point's position before and after velocity)

Doing silly redundant tests would solve one problem, but introduce a new one:
In some cases, you'd get conflicting results and you'll have to chose which one to use.
Just look at the picture above and imagine doing the check the other way around like you suggest.
Anyway, I'm getting sort of tired of showing you why your system is flawed.
Have fun killing the FPS of your program while still getting incorrect collision data.

[EDIT]

This is how I see it:
{"name":"evil3ol4.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/d\/0df48a657431dd33797dc8459cd3bbe1.png","w":442,"h":252,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/d\/0df48a657431dd33797dc8459cd3bbe1"}
Two different results...
Perhaps I'm just stupid and I'm misunderstanding your idea?
Could you illustrate?

Definitely. But all I've got to go on is what I can come up with, because the only alternative I've heard - or been able to find - is to model everything as rectangles and spheres. (which seems like a real big leap from 'Simpleville' to 'Complicated-land') Would doing polygon vs. sphere collision really be that much faster than doing my line tests twice? (and besides, since I pass my collision function the whole spring object, I can just test for collisions between 'spring1's points against 'spring2' right in the same check...so I don't really need the two collision passes for everything)

The only 'collision data' I really get is just whether or not the two things collided. Everything else I figure from the current variables of the points involved. (still need to find a way for points to impart force to springs, though...I don't know what complications that'll bring into focus)

[edit]Oh, oh, oh...here...
http://www.allegro.cc/files/attachment/595503

Time steps have been taken into account.
The picture shows the line in the current frame and the arrow tips show where it's gonna be in the next frame.
Think it's improbable that an object would move that much during one frame?
They do it all the time.
Plus, this problem comes in many variations... The velocity needed to wreck havoc on your program would depend on things like object size and line angle.

P.S.:
Yes, using SAT would be much, much faster, and more reliable.
You don't treat each point or line as a sphere or rectangle or what ever.
Your points ,and lines make polygons so you do polygon vs. polygon tests.
And if you have some lines that stand alone (like rope segments), SAT can handle them just fine the same way it handles polygons.
And it's really not a complicated concept, nor is it complicated to implement.
SAT should be faster than what you're currently doing even in the worst-case scenario, but since objects are more likely not to collide than to collide, a separating axis could very quickly be found and you'd know right away that the objects don't collide.
The idea is basically that if you find an axis, project the objects on it and their projections don't overlap, this axis separates the objects and they can't collide.
There could be infinitely many such axes, but you only need to check a handful:
To be precise, the normal of each side of each polygon is a potential separating axis.
Doing the projection merely requires a dot product, and the overlap test is a small 'if' statement.
In the worst case, you'd have to check every potential axis and if none of them separate the objects, they're colliding, but if the objects don't collide, you quickly find a separating axis and terminate the test.
With your algorithm, you'd have to check every line against every line no matter what.

Indeed, that appears to be a better plan!

Would I be able to do all is my individual segments like this? I don't want to have to separate all my potential objects into polygons.

If you really don't want to treat every object as a whole, I guess you could treat them as sets of line segments and still use SAT, but you'd lose some of its important advantages, plus, you'd have to tweak it a bit and make the collision detection dynamic.
In fact, I had a soft body demo somewhere around where I used thin rectangles instead of line segments to make the soft body, because I was too lazy to code a dynamic SAT.
Rectangles have some area so they're less likely to just pass through each other between frames, so static checks worked fine, but if I had my jelly object to move at high speed, it would pass through other jelly objects. (But not through the map geometry, which is thick.)
I guess it all boils down to this:
If your system works fine for you in normal situations, and you don't need something fool-proof, don't bother... What you're doing should work for small time steps, medium velocities and for bodies that aren't too rigid.
Dynamic SAT would be fool-proof and not TOO hard to implement, plus, if you ever decide to use polygons in another project, you'd have something convenient and efficient ready for use. (It would surely be useful for the conventional types of games that use polygons to represent the world and bounding areas of entities, like a side-scroller...)

In what sense is it not dynamic? And what advantages would I be losing?

Your algorithm is dynamic. But the simple, straight-forward implementation of SAT is not dynamic in the sense that it doesn't take velocities into account, just handles overlaps. Static tests work just fine for polygons at reasonable velocities, they'd work fine for line-vs-polygon, too, but not for line-vs-line cases.
If you use dynamic SAT and treat your objects as a set of segments, you can't use that nice early-out option of finding one separating axis that separates the two objects, but you'd have to treat each segment as an object and check every segment against every other segment, which is kinda what you're doing now... But at least it would be fool-proof. (And probably still somewhat faster.)

[EDIT]

Found that soft body demo.
I'll attach it.
In case you're wondering, it doesn't use any springs at all. I use a more stable technique.

Will circle(point, given some size) vs. line not be workable in the same way as line vs. polygon? The only things I ever actually test for are collisions with points hitting lines.

[edit]I've seen that before! Huh...wonder where... No springs?

No, it would work perfectly fine...
It's just that when you check a whole object against another whole object, you can find one separating axis and quit checking those objects.
If you divide your objects into parts like line segments and points, you'd have to treat each line segment and point as a separate object, that is, you'd have to find a separating axis between every two segments before you know the objects aren't colliding.
It would be like doing polygon-vs-polygon in the worst-case scenario.

[EDIT]

Maybe you've seen it at the Depot?
I posted it there a while back.
And no, no springs. Just soft stick constraints for surface tension and real pressure calculations for inner pressure. (That is, I use infinitely-stiff "springs", and every time the length of the springs is illegal, I just change the positions of the points to change it back, then work out the velocities from the changes in position. I can make the springs appear "soft" and springy by not putting the points in the correct positions right away, but dragging them a bit in that direction.)

[EDIT 2]

There's no much point discussing SAT... If you want to, read about it a bit, to understand the principle, then decide if you need it or not.

In your opinion, would it be worth the effort of finding a method of dynamically recognizing complex convex or concave polygons full of cross-struts (which really don't need to be checked for collision) to avoid the inefficiency of that method? (the system runs very fast as it is, but I haven't gotten to the point where I can check on the demand of complex polygons interacting)

Oh, damn, I forgot...
SAT works only for nice, convex shapes.
And you probably want something that works with any arbitrary shapes.
I'm an idiot.
You can still just do your line\segment tests using dynamic SAT, because it would be fool-proof and somewhat faster.
To be honest, I now realize my points were somewhat moot... If your objects won't be moving too fast and you just want to get things done quick, I guess you better stick to what you have now.

What I have now really doesn't work any better than it did before I turned it into a huge monster, so if SAT is faster and cleaner than what I have now, I'll try it.

I have a ready static implementation of SAT.
It's neat and clean and is just about 70 lines of code.
I can give it to you if you need it. It handles polygons, lines and points.
You'll have to figure out how to make it dynamic by yourself, though.
(I mean, not completely by yourself, there's plenty of info. and I can help out here and there, but I'm not gonna write it for you. xD)

Could I bother you for a few comments? like...
interval.x = interval.y = VECTOR_DOT_PRODUCT(axis, poly[0]);
Doesn't really make much sense to me. I mean, I know what it does, but not why it does it. (some of the naming isn't too obvious, not that it needs to be, but...)

Umm... You know how projection works, right? What I do there is to basically smash a polygon against an axis. I project every point using the dot product, and the result of the dot product is some value... Now, I find the minimum and maximum and that's the interval of the polygon on an axis. (The 'x' there is the minimum, the 'y' is the maximum. That's stupid, I know. )
And what the hell do we need the intervals for?
Well, we project both objects on the same axis, check if the intervals overlap. If they do, we go on and check the next axis. If they don't, the objects can't possibly intersect.
The axes we need to check are actually the normals of the objects.
For the sake of illustration, I chose a random axis in the picture.
You can see on the right that the intervals overlap on that axis, but they don't intersect, so there must be another axis on which they don't overlap.

{"name":"satgb8.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/f\/4f0defde056eec6feb1c754cf233dea3.png","w":706,"h":269,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/f\/4f0defde056eec6feb1c754cf233dea3"}

[EDIT]

As for how dynamic SAT works...
Imagine a moving line checked against another line... You can draw lines between the old and new points of the line, and you get a quad, right?
If that quad intersects the other line, we have a collision forward in time!
So basically, it's just the same old, but with one extra axis to check: The velocity.

{"name":"dynfs9.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/2\/92000938028336e60ab953d375cf379a.png","w":273,"h":249,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/2\/92000938028336e60ab953d375cf379a"}

So why only one extra axis if we have a whole quad now to check?
Because every normal of every side of a polygon is an axis, but the normals of parallel sides are the same, so we have 3 new sides formed, but the 'v' segments are parallel so there's actually just one new axis to check for, and the other side is parallel to the original line.

I gotta go now. I'll be back later.
Good luck!

Alright, I have to go for the night (1:22 here, and I have to be up in the morning), but I'll try and work through this, or write my own. I generally have a big problem working out how other peoples' code works. (that'd be why I didn't look into other engines when I started working on this)

Thanks for the help.

I'll try to make things clearer...
Note that in the following, every time I say "polygon", I mean a convex polygon, a line, or a point. The code I present here is simpler than what I have in my previous post, because this code only tells you whether there is an overlap, but gives no information about how to resolve it.
If you can figure this out, I'll write another short tutorial explaining how to get a the minimal translation vector that would separate the two objects after the overlap.

Let's suppose that we're dealing with overlaps in one dimension.
We have a single axis, and the "objects" are represented by intervals on this axis.
Each interval has a minimum and a maximum value.

Checking whether two intervals overlap is very straight-forward:
Two intervals overlap, unless one of the interval's minimum is bigger than the other's maximum.

int intervals_intersect(INTERVAL int0, INTERVAL int1)
{
 if(int0.min > int1.max || int1.min > int0.max)
  return 0;
 return 1;
}

Now, let's move on to two dimensions.
It's an obvious fact that if you can draw a line between two convex polygons, such that each polygon would end up on a different side of the line,
the line separates the two polygons and they can't possibly be overlapping.
If no such line exists, then the polygons are overlapping.

http://img520.imageshack.us/img520/9764/slgj7.png

So we can state our problem this way: Check every potential separating line: if the line checked separates the polygons, terminate the
test and declare the polygons as non-overlapping. If none of the potential separating lines actually separate the polygons, they overlap.
Obviously, there's an infinite amount of lines we could test, so the trick is chosing a finite set that would give us conclusive results.
We'll get back to that later.
So how do we actually check if a line separates two convex polygons?
There are plenty of ways to do that, but the one I will present will prove to be very useful later on:
We find the normal of the line we're testing, we normalize it and project both polygons on it.
To project an polygon on the normal, we take the dot product of that normal and every vertex of the polygon.
The result of the dot product would be a scalar value, and if we imagine the normal to be a 1D axis, then this value would represent each point's
location on this axis.
For each polygon, we find the minimum and maximum of the dot product results.
The extrema give us the polygon's interval on the axis.

.
If the two intervals of the projected polygons don't overlap, the line separates the polygons.

{"name":"seplinerj5.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/4\/84cdd11457f968e7f7146198b6e7ecfb.png","w":245,"h":229,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/4\/84cdd11457f968e7f7146198b6e7ecfb"}

It can be proven that while there's an infinite number of such lines we could test, we only need to test a handful:
We only need to take each side of each polygon as a potential separating line.
If we find one that separates the polygons, we terminate the test and declare the polygons as non-overlapping.
If none of the them separate the polygons, they overlap.

Wow, Stas B., I don't think even Wikipedia was able to explain it to me that clearly. Bookmarked! (And good use of simple-but-efficient graphics!)

Damn. You didn't have to go through that much trouble, though I think you've just written a good SAT resource.

And did a good job, too! Yeah, all of those snippets make perfect sense now. Hang on, I'm going to go look at the rest...

I think the only stuff that I don't get at this point is involved with the projection, but I never got around to looking into how that stuff works.

I knew I should have written something about projection.
It's quite simple:

The red point is the point we are projecting.
The bold black line is the vector B that we project the point onto, and the black point is its origin.
The green point is the projected point.
We form a right triangle between the three points.
What we're searching for is the distance between the black and green point.
Basic trigonometry tells us that it's |A|*cos(a), but we don't really know 'a'.
Luckily for us, |A|*cos(a) is exactly what A dot B is defined to be.
So how does that help? Another definition of A dot B would be Ax * Bx + Ay * By.
So the projection of point A on vector B would be Ax * Bx + Ay * By.

P.S.:
Thanks for the good comments.
People ask about collision detection often, so I figured I should write something about it. The first time I implemented SAT was after reading tons of info from many different web-pages, and even then I was not entirely sure what I was doing. I figured out how exactly it works since then, so I did my best to make a clear, short tutorial, so people won't have to go through much trouble.
Perhaps I should move this to somewhere where it can be more easily found?
Any suggestions?

Wikify it!

Oh, sorry...I should have been more clear. By 'projection', I meant the process of projecting the objects out of collision. (But that bit you just posted is actually exactly what I'm doing in my Geometry class right now...kinda funny...)

I have a feeling this is going to be a lot less clear...

To resolve an overlap between two polygons, what we need to do is to turn one of the potential separating lines we discussed earlier into a real separating line. To do so, we need to make sure that the intervals of the polygons on the normal of that line stop overlapping.
This can be done by translating one of the polygons a certain amount in the direction (or the opposite direction) of the normal.
We compute a translation vector: Its direction is the direction of the normal (or opposite to it), its length is the amount of interval overlap (the area the intervals share).

{"name":"resoverip8.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/a\/3a352044bcb17bfa86fd0ea827deaa78.png","w":553,"h":208,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/a\/3a352044bcb17bfa86fd0ea827deaa78"}

Note that in the picture, the blue rectangle is penetrating the red one from the right, so we would push it in the direction of the normal, to the right.
If it was penetrating from the left, we could still push it all the way to the right, but the reasonable thing to do would be to push it in the opposite direction, to the left.
First thing, we need to update our 'intervals_intersect' function to return the amount of overlap:

int intervals_intersect(INTERVAL int0, INTERVAL int1, double *depth)
{
 double d0, d1;

 if(int0.min > int1.max || int1.min > int0.max)
  return 0;

 d0 = int0.max - int1.min;
 d1 = int1.max - int0.min;

 *depth = (d0 < d1) ? -d0 : d1;
 return 1;
}

Note that 'depth' could be either positive or be negative, with plus meaning "in the direction of the normal" and minus meaning "in the opposite direction".
We could chose any side of the any of the polygons to separate the two, but for each line, the amount of translation needed to separate the objects would be different. The reasonable choice would be the line with the shortest translation vector, or in other words, with the smallest amount of interval overlap.
(Note that since we're doing a static test (i.e., not taking velocities into account), sometimes it might not be the most correct solution,
but it should be satisfactory in most cases.)
Here, for example, we would translate the polygon horizontally, since the amount of overlap is smaller:
{"name":"resover2cb8.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/b\/3b4dc9dfbf4b045ca087b8f599477056.png","w":279,"h":205,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/b\/3b4dc9dfbf4b045ca087b8f599477056"}

So here's an updated version of the 'poly_intersection_test', which would not only tell us if the objects overlap, but also how much and in
what direction to push them so they stop overlapping.
This code finds the normal with the smallest interval overlap and the actual smallest amount of overlap, then creates a minimal translation vector by scaling the (normalized) normal by the overlap amount.

Note that you can apply the resulting translation vector is several ways.
You could make one polygon immovable (world geometry, for example) and apply all the translation to one of the polygons, or you could
push each polygon in an opposite direction with half of the translation distance.
You could use the mass ratio to figure how much translation to apply to which polygon.

Awesome! That makes things much clearer. I'm probably going to rewrite this stuff myself (just because I'm awkward), but I'm thinking the background of the demo (if I ever release this thing) is going to be filled with "80% of this system thanks to: Stas B. and James Lohr" in huge glowing letters...or something...

Thanks again!

You're welcome.

P.S.:
I've just finished coding the dynamic version of the algorithm.
Works like a charm for lines and polygons at any velocity and just a bit more complicated than the static test.
I'm a bit too lazy to explain how it works right now, but here's the code:

Usefull code, indeed. Thanks Stas B !

Sorry, Anomie, but it turns out to be totally not worth it.
Working out the contact points is a real pain in the butt and I'm pretty sure it's gonna be as slow as your original algorithm eventually.
Also, dynamic SAT wouldn't work right for you, because it assumes that all points of a given object are moving at the same velocity, but in your case, a line segment might rotate, so each point would move with a different velocity. (A work-around might be to just chose the greater velocity for the test, but I'm not sure how it would turn out.)

[EDIT]

Now that I think of it, your algorithm would suffer from the "points with different velocities" problem too.
And if you do only lines vs. lines, figuring out the contact points would be a matter of another line intersection test after the collision has been resolved...
Damn, there's just no good way to deal with this problem!
No wonder even the most complex modern computer games use spheres and boxes for collisions.

Meh...that doesn't really bother me too much.

But the way I was thinking of doing it, I would only check points (totally separate from eachother and anything else) against lines (totally separate from eachother and everything else). The only 'objects' I would have would be singles lines, and single points. Would that still be a problem? (or would it work at all? (or would it really just fix everything if I used polygons/circles for my points/lines? (and could I model my lines as having sub-pixel width?)))

In any case, you've written a good new resource here! Not a total waste of time, even if it can't be used in my little thingy.

You guys draw nice colorful pictures. I love this thread.

Points and lines bring us back to the problems we were trying to avoid.
There's really no point in using SAT if that's your plan, because you're essentially just using it for the line intersection tests you could do with 5th grade math.
It brings us back to these problems:
{"name":"05cb8cbdb1af89c2578439bf1773e7c8.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/a\/9a2cd2c8bef78347bfe9661e68280bbb.png","w":265,"h":368,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/a\/9a2cd2c8bef78347bfe9661e68280bbb"}
Which you wanted to resolve by doubling the number of needed tests and using relative velocities... But you have to use one relative velocity while each point could be moving with a different one - the same problem with SAT.
The problem with your algorithm is that while it's perfectly fine for separate points, it can't handle well an object as a whole. That's why I suggested SAT: It's great at handling whole objects... But I almost forgot that the objects have to be convex for it to work. So I suggested breaking the objects into lines (each side of each polygon would be a line, so only lines vs. lines, no points), but that introduces new problems... Well, in fact, it introduces only one new problem because the "two different velicities" problem is present in both cases. The problem is finding the contact points. (Which could be done, but I think that by the time you're done with it, it would be a mess.)

Damn... It sounds like the dynamic SAT won't work if things can rotate, and even if I used full polygons, the standard static SAT can't be trusted unless I make my lines out of really thick rectangles... I know people have done this before me! Argh! I need to think more.

SAT does perfectly well for objects that rotate, unless they rotate really really fast. But if they rotate that fast, you can treat them like circles. So that's really not a concern.
And the thing is, people haven't done it before you... they just stick to convex shapes. I've never seen a reasonable solution for collision detection between concave shapes.

[EDIT]

Okay, this might sound like a crazy idea, but... well... you COULD break your objects into lots of lots of little circles and test those for collision.
Since you're working in 2D, AND you could use a bounding circle hierarchy, it won't be too slow. You can use fast distance approximation for the tests.
I'm pretty sure more complex operations are done in real-time per-pixel nowadays than you'll have to do for each circle.
It's a simple solution and it would mimic the way the real world works.

The 'two different velocities' thing? Unless it's a perfect square, I guess...but I know that people have made systems where everything is made of point-masses/springs. I guess the solution may really be to find a way to separate everything into convex polygons dynamically...but gawd. It seems so ridiculous that the whole thing was made so much more complicated by gravity. It looks like 95% of the code in this system is going to be for the collision stuff.

[edit] As in...having even my lines made of tiny circles? Huh... I guess, if I really wanted to, I could move things at a fifth their normal speed, and do five times as many ticks per second, to try and avoid missing collisions due to high speeds... Could that really work?

[edit2] Wait, how would that be different from a simple distance-to-line check?

You don't have the "different velocities" problem (nor any other problem we've discussed) if you use convex polygons and separate rotational velocity from translational velocity. I have a rigid body dynamics demo that works that way, and it handles rotations very well, thank you. (And probably looks more realistic than a mass\spring system.)
But the hell with that.
You don't need to break your objects into convex polygons, you can break them into circles.
If would be really simple to both break them and check them.
The more I think of it, the better this solution seems.

[EDIT]

You won't have missed collision problems if you FILL the areas of your objects with circles.
It isn't really THAT crazy if you use a boudning circle hierarchy.

[EDIT 2]

You'll need to think of a smart way to fill in your circles, so you can cover the whole area of the object with as small number of circles as possible.

[EDIT 3]
In fact, you can make only your lines out of circles but do DYNAMIC circle/circle tests, so no collisions would be missed.

Oooooooh, I see! That makes more sense. So then... It still seems like I'd have to identify the shapes with enough accuracy to separate them into polygons...the hard part would be finding the center of a connected shape, with respect to the possibility of something like a box and a pole, attached by a rope of springs...which would each need to be registered separately for the circles, right?

[edit] I must just be real slow with my posting. If I do make my lines out of circles and test those, how's that different from the distance-to-line check?

The difference is that you won't encounter any of those old problems that way.
Come on, just take a sheet of paper and do some drawing.
My computer got... ummm.... confiscated, so I can't really post much, but I'll try to post something if I figure out a good solution.