Need another algorithm!

And this time, I'm sure of it. :-)

I need a way to calculate the collision normal between two sprites.

In other words, I need to be able to take a sprite with a square mask, and calculate the normal of the edge that has been collided with.

I can cheat, but it needs to be fairly accurate. More accurate than just using a vector from the center of one sprite to the other.

Now here's the kicker. I want to do it without accessing either sprite's mask. I also do not want to build a table for each sprite.

I have an idea how to make it work, but the math is eluding me for the moment.

Let's say I have two sprites.

Let's say I take the distance between their centers, and it is the same as Min(Sprite1.Width, Sprite1.Height) + Min(Sprite2.Width, Sprite2.Height). If both sprites are perfect circles, this will always be true. As the result of this comparison deviates more and more from equality, I can assume at least one of the sprites is elongated, or at least, deviates from a perfect circle.

In other words, I am trying to find a way to perturb the normal that points from one sprite's center to the other, by using the difference between the distance to the collision point from what it should be if they were circles.

So for example, if my vector to the collision point is pointing at a 45 degree angle, but the width of my sprite is 1, and the length of the vector is Sqr(1+1) = 1.4 then I know that point is at the corner of a square.

I will give a free copy of one of my systems (your choice) or my texture generator to anyone who comes up with a solution I like and use!

(I will entertain the idea of a method that accesses a sprite's mask, or uses some other mechanism, but I really don't think it would be such a good idea to do so.)

This appears to be a rhetorical question then since you appear to be thinking out aloud, (and haven't used a single question mark) :)

I didn't need a question mark. I didn't say I have a question. I said I need an algorithm, and I satsted what algorithm I needed "I need a way to calculate the collision normal between two sprites."

Silly ENAY.

{edited}

Any chance you can post some pics/mock-ups of what you mean? I tried reading your explanation but my eyes just glazed over. :)

I know:
The position of the center of each sprite.
The distance between the centers of each sprite.
The radius of the largest circle which can fit the inside (min(width, height)/2) or outside (max(width, height)/2) of each sprite.
The collision normal.

I do not know:
The point at which they are colliding.
The collision normal.

I want to know:
The collision normal.


Currently, I compute a vector that points from the center of A to the center of B, then I normalize that, and use that as my collision normal.

This is correct if the sprites are spheres.

This works well for oddly shaped sprites if the sprites can't interpenetrate.

But it does not work well with oddly shaped sprites when the method I'm using to keep the sprites from interpenetrating is to move one sprite back from another in the direction of the collision normal, just enough to keep them from penetrating.

EDIT ... posted at same time as above.

To get the normal for collisions between rectangular shapes you'd need to use intersection techniques. Have you considered using axis aligned ellipsiod collisions ... much easier to implement and faster?

Obviously they wouldn't be completely accurate but I use similar for collisions in my verlet vehicle demonstration and they work well.

I can show you an example if you want?

I can't use ellipsoids, the normal has to be fairly close to correct, and that is much too approximate.

Well I found a way to solve the problem without the correct collision normal, but the correct collision normal would still be helpful in smoothing out the collision stuff that last bit. The offer still stands!

Erm, wouldn't the normal be the difference in x values / length of the distance vector by the difference in y values divided by the distance vector?

But isn't the real problem that it still isn't the 'correct' collision vector, as you're not taking the arbitrary shape of the sprite it collides with into question?

Flame:
That is precisely what I am doing, and precisely the problem.

I'm trying to find a way to take the aribtrary shape of the sprite into account in some way. I suppose I could, at the very least, find a way to calculate a normal assuming the sprites are ellipses rather than circles. I think that would produce different normals which would be closer to the actual shape of the sprites, though still far from perfect.

The ellipses would have to be rotatable though.

Isn't this why people create a polygon hull?

Creating a polygon hull is one way of doing it, which I considered, but there's a lot of work involved in doing that, if I wanted it to be automated, which it would be crazy not to do since the whole point is for the system to be easy to use, plug and play. Requiring a polygon editor for something so simple would suck.

So, first, I'd have to access the image of every sprite the user creates. I might step down from the top center of the image, pixel by pixel, until I hit one which was opaque. Then I'd have to step around the edge of the sprite until I got back to the start.

Once I'd done this I'd now have a polygon with hundreds of sides, and half the sides would be horitontal or vertical, and half would be at a 45 degree angle, since I'd be using the offsets of the pixels.

So, then I'd have to make a smoothing function to take all the points of this polygon and smooth them out. This would make the polygon shape a little less accurate, but it's an absolutely neccessary step to actually get collision normals out of it which would be useful.

Then I'd have to write a polygons Simplification function which could step around the polygon and delete vertices. I could go for something sophisticated that would remove vertcies in areas that don't curve much, or I could just delete every other vertex and repeat the process to simplify more.

Finally, I'd have to write a collision function that can handle colliding polygon objects, which would requring the speerating axes theorem, which I have never implemented, but know invlolves testing every edge and vertex combination to try to find a plane (or in this case a line) that seperates the two shapes.

Somehow I just cannot convince myself that this is a worthwhile endeavor for a sprite system. :-)


Anyway, I think I figured out how I can calculate colliding ellipses. I think I need to transform my collision normal calculated as if the sprites are circles into the sprite's space, and then transform it from ellipse space into circle space by scaling it so that the ratio of height to width is 1:1. Then I transform that normal back into global space, and it should be squashed in the direction of the ellipse's long axis.

[edit]
Well, I implemented object-aligned ellipsoid collision. Might be a little more accurate. Hardly enough to make a difference though.
[/edit]

Just spent 15 mins typing out an idea, then lost it to a droppped net connection (I usually copy any long posts before submitting for that very reasdon)

.... had to do with a BSP approach to collisions. Let me know if you see any milage and I will type it up again.

BlackJunper:
I don't really see how one could implement a BSP based solution without creating polygon hulls, which I really don't want to do.

Hm...

If you moved the sprites back to the point where they are just touching but not overlapping, you could move the sprite about a few ways to determine which directions cause collisions and which don't, and from that perhaps you could determine the collision angle. I think you'd have to move it at least eight ways though. That would give you the equivalent of an eight sided polygon. Or maybe... you'd have to move it just three ways, since you'd know that moving it away from the other sprite wouldn't result in a collision. So you could move it on one axis towards the other sprite, on the other axis towards the other sprite, and then on both towards it, and the result would give you one of three collision angles. That's probably not accurate enough though and even if more tests could whittle the results down it would be too expensive to do so many overlap tests.

Here's my take on this,... I've skimmed the previous posts, so I may have missed some things already said.

Although you say you don't want to create an underlying polygon system, I think that's the absolute best way to get acurate normal collisions. You may be able to simplify things quite a bit though, by creating a few presets that may work just fine. For example, a bounding box, circle, triangle or diamond shape might be the presets. you could test the image of the sprite to find the upper/lower limits of these and automatically scale them to fit the bounds.

You could also create a simplified poly shape by projecting N number of lines inward until they touch a pixel, and then connect those points. This method would miss some peaks and valleys, but in a few mock-ups I did the results were not horrible. I don't know if I explained this well enough, I can illustrate more later if you need.

What a great idea .. I wonder who suggested that ;)

I use exactly the same method.

Stevie

StevieG:
It was a nice suggestion. But I had already considered it myself. :-)

Unfortunately, it didn't really work any better than the circle method, and I was afraid it would screwed up the 1D collision physics of sprites on paths. So I decided not to implement it after all. If it made any kind of noticeable difference I would have kept it, but it really didn't.


Pongo:
An interesting idea. The current method is working pretty well though. Objects for the most part, no longer interpenetrate, and I'm not sure that even if I had correct collision normals that it would fix those few extreme cases where they do.