Moving sphere against triangle collision

593

Author

November 17, 2004 01:32 AM

Okay, let me just say it one more time. I am not finding the closest point on an edge to any points. I am not finding the closest point on an edge to any rays.

I am finding the point where the ray becomes [radius distance] to the edge. There is a huge difference. Although finding the closest point on the edge to the ray will always detect collisions, if there is one, it will not give very good results when you want the point of contact.

For example, if the ray is moving into a triangle area 6 inches this frame and collides, the closest point on line to line method will report a collision, say at 3 inches. So the contact point is 3 inches after the start point. So now we change that 6 inches of movement this frame to 16 inches of movement this frame, but the exact same direction and starting point. The method will now report that contact was made after 4-5 inches of movement. So it will always report the correct yes/no answer, but the distance is off.

In a game, the point of contact is pretty important. The code you see at the top of this is 2-3 days old (err, I think). The pushed plane idea is all that remains of it in my current code. The new code finds the point where the ray end distance from the edge becomes radius.

Actually, I have learned something from this. If the ray starts inside of the pushed plane, two edges need to be checked. My assumption that another triangle would take care of it was incorrect. But the idea is very simple. When the starting point of the ray starts inside of the pushed plane, check the edges which are facing the opposite direction that the ray is moving. This could be a maximum of 2 edge checks, but sometimes could only be 1. Basically, look at the direction of the third vertex (the vertex that the edge is not connected to) from the center of the edge. If the ray is moving towards that direction to some degree, then it needs checked.

I'm holding on to my idea that the pushed plane intersection holds the first point of contact. I'm also still saying that only one edge needs checked when the ray intersects the pushed plane (starts outside of it). I have been testing this algo for 2 days straight. Mainly because I had a little trouble projecting a fixed path after collision. But the point is that out of all of the angles I've tried, this routine has never failed.

By the way, any suggestions on how to prevent several collisions in one frame and still allow "sliding"? I think I'm going to trap the sphere inside of every sliding plane that it creates. For example, if a sphere hits the ground, and slides into a wall, the wall will not only force the point back onto it's sliding plane, but the floor's as well. So on, so on. I haven't tested this out fully.

Thanks for all of the advice

edit:

Quote:
develops to :
Pos*N - N*A - r*N*N

I'm not really sure I know what vector * vector means at all. Is this a cross product? Dot product? I've seen it on math sites quite often, but I have no idea what operations are being performed.

[Edited by - Jiia on November 17, 2004 1:32:04 AM]

TempusElf

186

November 17, 2004 10:05 AM

Quote:Original post by Jiia
By the way, any suggestions on how to prevent several collisions in one frame and still allow "sliding"? I think I'm going to trap the sphere inside of every sliding plane that it creates. For example, if a sphere hits the ground, and slides into a wall, the wall will not only force the point back onto it's sliding plane, but the floor's as well. So on, so on. I haven't tested this out fully.

I think what you want is recursion... if your collision response moves the object, that movement needs to be tested for collision and so on...

is that what you were looking for or did you already know that?

Jiia

593

Author

November 17, 2004 10:47 AM

Quote:Original post by TempusElf
I think what you want is recursion... if your collision response moves the object, that movement needs to be tested for collision and so on...

is that what you were looking for or did you already know that?

Right, but I'm having trouble puting the object back on track in the second, third, fourth, etc recursive hits. For example, if I hit a ground triangle (1st), and that slides me into a wall triangle (2nd), sometimes the wall triangle slide will put me back into the ground triangle, depending on it's angle.

In some complex corners, I was getting up to 8 recursive fixes!

I want to at least allow 4 recursive slides before it stops the sphere completely. But I don't want to waste any of them on the same triangles twice. My routine seems to be doing it a lot. It may be because my world mesh is a bit messy. It is pretty hacked together. It's hard to tell what angles the polys are on.

Still, I don't want to limit my world meshes to perfect 90 degree corners anyways. I'm just not sure how to avoid hitting the same general planes more than once. I especially seem to have trouble on the ground triangles.

Dmytry

1,151

November 17, 2004 11:03 AM

sphere is very good for collision - collision of sphere with any mesh(including single triangle) it's intersection of ray with thing that have sphere at each vertice, cylinder at each edge, and each face displaced along it's normal by radius. (i mean ray of sphere center movement and point of intersection with "thing" gives sphere center at time of contact)
It's in fact simple to see... that thing is a volume that iff sphere center is inside that volume, sphere intersects triangle.

Charles B

863

November 17, 2004 11:14 AM

Quote:Original post by Jiia
Okay, let me just say it one more time. I am not finding the closest point on an edge to any points. I am not finding the closest point on an edge to any rays.

Damn, we all know what finding a contact point means. You did not catch what this nearest points stuff means in the algorithm, it's related to the Voronoi partition around the triangle that allows you to know against which d-facet (vert, edge or face) the contact will occur first.

THE THEOREMS CONCERNING NEAREST POINTS ARE ELEMENTS OF THE THEORY. NOT OF THE COMPUTATIONS THAT USE THE THEORY.. The theory is implicit in the computations. That's math ! And that's why they are powerful.

I never told you to compute the nearest point of the triangle to your capsule. This would most probably be after the first contact, and none seeks this info. Of course, the problem is to find when the sphere hits the triangle first. And then at this time, the contact point is obviously the nearest point between the sphere and the triangle. A capsule is simply a moving sphere, that's the correct way to see things clearly and not miss the first time of contact.

I told you, try static sphere/triangle first. Test it toroughly. Frankly do it. Step by step. Then, once you understand it totally, you'll be able to have a flawless time based collision prediction. That's what a capsule test means : collision prediction, it's harder and more subtle than collision detection.

Quote:
The pushed plane idea is all that remains of it in my current code. The new code finds the point where the ray end distance from the edge becomes radius.

Naturally. It is the first test to make it removes more than 50% of the cases. I think I already mentionned this. But in the end, correcting your code you will just see that all I said about the Voronoi partition is your GetTriangleEdgeThatPointIsOutsideOf() part corrected. In the end you will just rediscover the canonical algorithm.

I think your main false assumptions came from that you tried to reap some conclusions from the situation at the time the sphere hits the support plane of the triangle (cf the pushed plane stuff). This gives no information about where the contact will occur next except in the easy face/sphere case. It's only useful for early rejection or early face/sphere contact conclusion. The rest depends on the movement direction, and which Voronoi cells are crossed afterwards.

Quote:
Actually, I have learned something from this. ...
check the edges which are facing the opposite direction that the ray is moving.

See, it's still too intuitive, and mathematically undefined. You need to elaborate more. How can you tell that an edge is facing something ? I has no surface, it's a segment of line, no normal. Tip : you necesarilly have to speak of planes and positive/negative half spaces. Well again this is the Voroin stuff. It's the Voronoi edge cell that you are talking about.

Beginners often do similar mistakes concerning front facing culling. They think intuitively : "Compare angles between the camera front direction and the face normal, dot product em". But this only works in isometric projections. Intuition is often misleading. The correct way is to think half space, that is volumes instead of angles. It's "Is the camera in front of the face ?" Not : "Is the face in front of the camera" ?. A punctual-projection has no true front direction. Then what about Z or the homogenous coordinate. No, that's something else. If the fov is 360, any direction is frontal ! This depends on which object you focus on. A face has a unique front direction (if oriented ccw or cw). Front-face culling is done through plane equations. You must now realize that plane equations are everywhere. When you transform a vertex in affine space in fact you compute three plane point distances.

Quote:
By the way, any suggestions on how to prevent several collisions in one frame and still allow "sliding" ?

That's a very complex thing to do, I mean in a global game code context, not just in a demo. Collision prediction and time continuous physics are just used partially. I and others try to explore this way. No 3D engine uses this as far as I know. The issue is to keep tracks of constraints and detect the events when they appear and disappear.

Quote:
Quote:
develops to :
Pos*N - N*A - r*N*N

I'm not really sure I know what vector * vector means at all.

the answer was :

= N*(Pos-A) - r

since N*N = 1

scaling : *, dot product : *, cross product : ^, it should be so in my opinion. But it's not well standardized. Still in your context it was rather clear. In fact I realized that you computed a distance in the ray direction, the fast and meaningful way to do is compute in the normal direction, what I showed you. Talking of distance between a plane and a point (or a sphere), it's the distance in the normal direction.

[Edited by - Charles B on November 17, 2004 11:14:38 AM]

"Coding math tricks in asm is more fun than Java"

Jiia

593

Author

November 17, 2004 01:59 PM

You're picking on my math lingo. That is definitely my weak point. I know a lot of the calculations, the relationships, and the situations. But I don't know the names or symbols of them. This is from self-learning, and not learning from a book or in a class room.

Another thing that I have to point out is that your decisions are too heavily defined by math rules. Math rules are not always the best choice for a game world. For example, rotating a character's head to look around. If you take the logical way, you end up with robotic, stiff necked characters. I'm not saying this is the case with sphere collision checking, but sometimes a flaw is okay, if it suits the game. This is not true in math [smile]

I already have a fully functional static sphere check. It's pretty simple stuff, compared to this. But I have characters armed with about 16 spheres attached to their different skeleton bones as they animate, and it's very difficult to prevent a sphere from moving too fast under this condition. The animation controls the spheres, so it's also that much harder to provide collision response, even with moving sphere checks. For example, what happens if the character walks into a narrow hallway and pushes both arms outward (with spheres in the hands)? Just have to provide the best response possible and try live with it. This is why it's good to ignore collisions once the starting point of the ray is inside of the triangle. Otherwise your character gets squirted to the outer boundries of endless space somewhere [lol]

So a flaw is fixing the game. The only other way I could fix it is to do some kind of crazy dynamic animation fix. Which would end up looking worse than letting the hands go through the wall.

Hmm, I don't really know how else I can prove that the routine works. Maybe if you could explain to me the angle where it will fail, I will test it out. You can either explain the situation, or give me the exact coordinates of the index buffer of triangle(s) and the beginning and end sphere locations. I'll follow it to the decimal and print out a picture of the collision point and reaction.

If the function fails, that's great. I have the chance to fix a potential problem. If it succeeds, that's one less problem I have to consider.

I have to get my flawed ass back to work now [grin]

Zakwayda

2,389

November 17, 2004 06:52 PM

Well, I won't add anything on Voronoi regions, etc. 'cause it looks that's been covered pretty thoroughly :)

But re: sliding, implementing sliding in terms of contact points and impulses is v tricky, but it can certainly be hacked effectively - see Quake and every game derived from it for proof of that.

The basic approach is recursive, as has been mentioned. Move the sphere to just short of the contact point, adjust the velocity so that it is parallel with the contact plane, and recurse to find any new collisions that may occur.

The details can be a little tricky. Even if you get it working, a naive implemention can leave you 'jiggling' in some corners and getting stuck in others. Very annoying.

A solution is to keep track of all the planes you've collided with, and handle things differently when you've hit more than one plane, or you have hit the same plane more than once (which can happen in acute corners).

The Kasper Fauerby paper doesn't deal with this, but it is (obviously) addressed in the Quake 2 source code. It's a little hard to dig up the relevant portions, but it's there.

Jiia

593

Author

November 18, 2004 03:23 AM

Exactly. But when I tried to keep the sphere inside of all sliding planes that it reached before it, it showed really funky results when testing with extremely long movement paths. I know it's dumb to worry about such things, but I hate knowing something bad can happen [smile]

I'm still sticking with this idea, though. So far, I'm testing 100 flying spheres against 1024 triangles, getting about 140 fps. I haven't performed a real test yet. This test included everything that happens in a game loop, including rendering. Plus there are no collision optimizations yet. But matching that against the 200 fps I get without any collision checking is not bad.

What do you guys think about creating a bounding volume for triangles? Since my triangles are in memory for the sole purpose of collision checking, I can give them any data I want. What would be the most efficient bounding volume to test against a ray? A sphere would be nice, but the triangles are, well, kind of massive. A sphere surrounding one tri could be as big as the entire map. I'm thinking axis aligned bounding boxes would better fit the triangles in most cases. But then I don't want to do ray-AABB either. Maybe I'll turn the ray into a AABB too [grin]

Jiia

593

Author

November 18, 2004 04:57 AM

Check out these results. These are from a much better test. I'm testing by bouncing 100 spheres on 1024 triangles, moving them around 999 iterations. The test runs in a tight loop, with no drawing or other updates.

Test 1:

1) Loop through triangles
2) Only check if DOT( MoveDir, Triangle.Normal ) <= 0.0f
3) Collision test

Results: 59000+ ms. I only checked this one once [grin]

Test 2:

1) Create AABB for moving sphere (triangles AABB already created)
2) Loop through triangles
3) Only check if DOT( MoveDir, Triangle.Normal ) <= 0.0f
4) Only check if sphere AABB intersects triangle AABB
5) Collision test

Results: 10170 to 10249 ms. Not bad!

Test 3 is exactly like test 2, except I made the AABBs use integers instead of floats. The positions were rounded off and 1 point was added to each side.

Results: 9818 to 9873 ms. Not much better.

Test 4 is exactly like test 3, except I swapped the 3rd and 4th steps (see test 2). I couldn't believe this one.

Results: 6880 to 6895 ms. Wow! Dot products suck!

I am running in debug mode, so it's hard to tell what the PC is doing around each of these corners. I suppose I need to do a release build to really test this. Any other suggestions on ways to improve this?

Thanks [smile]

edit: I forgot to mention that each iteration adds 0.02 milliseconds to the amount of time the spheres have to move. This makes the time-per-frame range from 0.02 to 19.98. So pretty close to what would be seen in a game.

Charles B

863

November 18, 2004 07:32 AM

Quote:Original post by Jiia
You're picking on my math lingo.

No, I could translate. It's not about language, the superficy, it's about the content, in depth.

Quote:
Another thing that I have to point out is that your decisions are too heavily defined by math rules...

No geometry is math and this is 100% geometry. AI rules are something else, they can be fuzzy. Wrong geometry algos lead to bugs. Specially nasty when they happen rarely.

Quote:
I already have a fully functional static sphere check.

Yes I'd be happy to see the code. It will be easy to detect a flaw if one exists.

Quote:
This is why it's good to ignore collisions once the starting point of the ray is inside of the triangle.

Inside the triangle should never happen. The contact should have been checked before it happens.

But inside the negative half space of the support plane, that is behind the triangle plane has to be treated. Imagine this simple case :

Up view. wall 1| /wall 2       |/room 1 *                  /radius     x           room 2  hit         _ (vertical        start pos  edge or  |  x  |   vertex)     _

Collision happens slightly behind the support plane of wall 2. It happens on a common vertical edge or a common vertex. But it's more on the side of wall 1. Normally the contact point should be intercepted by the test on wall 1.

Quote:
Hmm, I don't really know how else I can prove that the routine works.

It's never possible to fully assert a routine works unless a math theory and demonstration fully asserted backs it and the code actually translates the math correctly. However it's possible and easier to show that a routine is flawed, by a counter example if it's flawed. I need your modified code to tell if such a counter example can be exhibited.

But firstly, you can probably tell me if your routine reacts correctly in this situation. Would it detect the collision ? And then would it be the exact first contact point ? Note you can view this example in a 2D (orthographic) projection. It's only one of the many cases where your routine could fail from what I have read in the thread.

Else if you want I can take your algo back and show how I would correct it in a both solid and efficient (optimal way). But show me your current code first.

I would start with this :

Early rejection volume.

          .         /|\          / | \       S1            /  |  \     .      /  / \  \       .            /         \         .   S0    /  /  C  \  \           .   /             \     /  /  /   \  \  \  /_________________\   | /  A--  --B   \ | |                 | | - - - - - - - - | |_________________|

2 dot products reject more than 50% of the cases. That was "your" pushed plane idea.

Now extend this idea to the planes on the edges that are perp to the tri normal and maybe 99% of the cases will be rejected by 6 more dot products. That's very fast.

If the case is not rejected, that is if the ray possibly hits this extended volume, then it's more subtle (than the early rejection and than what you did in your first version at least). But I know how to make the last steps very efficient. One idea is use 2D, in the triangle plane, saying AB is in the x direction, to save computations later. This can be made very efficient with 3DNow for instance.

[Edited by - Charles B on November 18, 2004 8:32:18 AM]

"Coding math tricks in asm is more fun than Java"

Moving sphere against triangle collision

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Moving sphere against triangle collision

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines