Some collision handling fun

I am looking for the most elegant solution to a specific problem that I am having.

Before saying anything else: I am using OpenGL with SDL.

Let me first explain how I am currently handling collision detection in my game project:

The game map is a 3-dimensional map composed of cells. Each cell is literally a block that is 1x1x1 in its dimensions - making it quite easy to handle. Each face of a cell can be defined as having a wall or not having a wall. If a specific face has a wall, then it is assigned a texture and rendered. Otherwise it is not.

Now, let's say the camera is sitting in cell X. We already know that we only have to check for collisions for other objects also in cell X or the walls defined in cell X (the faces of the cell).
For now we will assume that there are no objects at all in cell X, and so we are only checking collisions on the walls in cell X.

Please take a look at exhibit A.

Attachment 8039

Exhibit A shows us the camera facing the wall about to collide into it. The blue lines represent where I have set the "clipping planes" for collision detection. Instead of detecting collision right at the point of the wall, I detect collision just a little bit in front of the wall. This helps to avoid some unwanted artifacts of actually hitting the wall (and thus the camera seeing through the wall).

Now, to do the actual collision detection, I simplified the problem into a clipping algorithm (hence why I used the term clipping planes above). In essence that is all collision detection is. Please observe exhibit B.

Attachment 8040

In exhibit B we see a starting point and an ending point after a movement has been made. The collision detection algorithm forms a line and calls the Sutherland-Hodgman polygon clipping algorithm in order to clip the endpoint of the movement into an allowed movement space. Therefore the player is able to move to the wall without ever going beyond the wall.

So far all is well and good. What I have explained so far works...and it works well. Now we arrive at the problem. I want to implement gravity into the engine. Please observe exhibit C.

Attachment 8041

Part of the problem with implementing gravity is that I must more concretely define where the player is in terms of the y-axis. Up until this point the location of the player has been the location of the camera. This causes no problems.

Now when I implement gravity, gravity wants to push the player down onto the ground...so technically the player position should be on the ground. However, if the position of the player actually is on the ground (i.e. sitting on the collision detecting plane), then a collision is constantly occurring, and therefore the algorithm will always throw out any move that the player tries to make, and the player will not be able to move.

See the problem?

So basically...if player movement gets clipped because the entire movement vector is sitting right on a "clipping" plane, I still want the player to be able to move on axes other than the one that that clipping plane is defining. Get the drift?

Based on what I have explained here, can anyone suggest an elegant solution?

Is "down" a valid movement in the game? Do you need to check y-collisions?

And maybe I'm misunderstanding the algorithm: but isn't the clipping just keeping you from going through the wall? It should still let you glide along it? (IOW: If the motion dotted with the clipping plane is zero, then you're sliding along the wall and that's ok.)

This is exactly what I want it to do - i.e. let you glide along it. Right now it's not.

Let's say you just hit the wall at angle, and you try to move again, so it looks like this:

Attachment 8042

The clipping algorithm will clip the entire movement, but we actually want sliding action to happen. This is a case of clipped motion between the x and z axes.

Movement along the floor with gravity acting as a downward force is essentially the same case but on the x and y axes.

[edit]
and yes downward movement is allowed. The player could be on a ledge and then jump onto the floor below.
[/edit]

What if I clipped only the coordinate that corresponds with the plane that I am clipping against?

So if I am doing collision detection against the "west" plane, then i only clip any movement along the "x" axis, but I leave the y and z coordinates of the movement completely alone.

ah well I guess I answered my own question there. :)

I decided to do what I said in my last post and it works wonderfully.

Simple little 3d newb question:

Will this still work if a wall is say, angled so that the direction isn't any one axis. Or is the "world" translated so that you are always "moving forward on the z-axis" if you are moving the direction you are facing.

The plane of collision has a normal. To change the direction such that you 'slide' along the walls you subtract the component of the velocity vector which is in the same direction as the collision plane's normal.

Velocity -= Normal * (Normal dot Velocity)



Where velocity and normal are vectors, Normal dot Velocity is a scalar.
This is inelastic in which energy is lost.

To exactly mirror the collision such that the incoming angle is equal to the reflected angle the equation becomes:

Velocity -= 2 * Normal * (Normal dot Velocity)
This is a 100% elastic collision in which energy is conserved (e.g. light reflections are done this way).

You can tweak this for various materials with a value called the coefficient of restitution. Basically, this is a coefficient which you can plug into the equations above. It's value is between 0 and 1 and describes how elastic the collision is. The general form is:

Velocity -= (1+e) * Normal * (Normal dot velocity)

where e is the coefficient of restitution.

Vicious:

yes this techique does work for walls that are not aligned on an axis. The ease, however, depends on your implementation. It is easiest to always translate stuff so that it becomes aligned for the purpose of the collision detection algorithm, but if you don't want to do that it could be implemented such that you don't have to do that.

To all:

I am now presented with a different problem. Check out exhibit E:

Attachment 8043

In this picture solid lines represent walls, and dashed lines represent only divisions between cells (with no wall actually present).

In this case the player is moving from a cell to the northeast, where he should bump into a corner. The collision detection fails, however, because I only check collisions against objects within the same cell as the player. The walls that the player should bump into are actually in different cells. Therefore the player is allowed to pass through the wall in this case, which is of course not good.

So I am trying to think of good solution to this. One solution is that I could do collision checking against the current cell and the cell in which the movement vector ends. I think that would work. In this specific case I would have to actually create a cell and define some walls (because the movement vector ends in a place where no cell actually exists in this specific case).

What do you think about that solution to the problem, or can you suggest a different solution?

This is probably what Bob said but the projection of one vector onto another is what you would use for sliding along a wall. You would project the velocity vector of the player at a time T along the vector created by the wall's endpoints.

As long as you are constrained to a grid and keep attempting to do collision detection this way you will run into issues. Since collision detection formulas and plane collision formulas work for a plane of any orientation it would make sense to me to ditch the whole grid/wall idea. You essentially have a set of planes in a sector that the player is in. Since the player can only intersect planes near him or in his sector you would check these for collision. Further reduction could be done via simple squared distance. There is no need to check grid row,col or anything along these lines. If you render via a BSP tree you can also perform your collisions based on this BSP tree.

Also since the vectors that make up a plane stretch to infinity I fail to see how your above example would have any problems. The arrow clearly would be on the positive half spaces of the planes created by the intersection.


So if you have your plane and you have your player's position:

result = (plane.a * player.x) + (plane.b * player.y) + (plane.c * player.z) + plane.d;

This of course is from the plane equation ax + by + cz + d = 0. You may use a different form of this equation since this one effectively flips the sign of d. Keep in mind I work with Direct3D which uses different handed matrices which also means Z increases into the screen and decreases out of the screen. However the formulas work regardless of all that.

The result will tell you which side of the plane the player is on regardless of the orientation of the plane with respect the the player.

Quote:

---

So I am trying to think of good solution to this. One solution is that I could do collision checking against the current cell and the cell in which the movement vector ends. I think that would work. In this specific case I would have to actually create a cell and define some walls (because the movement vector ends in a place where no cell actually exists in this specific case).

---

DavidP:
You really must check every cell that the movement vector crosses, not just the cell that the end point resides in.

Here's some BSP code that finds the 'cells' that a movement vector passes through. While your implementation will be slightly different, due to the fact that you have real cells all of the same dimensions, this should give you the right idea.

Code:

---

void        MoveTouchNode(BSP*pBSP,int node, Vector3 *Start,Vector3 *End,float Radius, std::vector<int> &TouchedLeafs)
{
        if(node < 0)
        {
                TouchedLeafs.push_back(~node);
                return;
        }

        //Find starting point distance to plane

        tBSPNode        *pNode  = &pBSP->mpNodes[node];
        tBSPPlane        *pPlane = &pBSP->mpPlanes[        pNode->plane        ];
        Vector3                *pNormal= &pPlane->vNormal;

       
        float        StartD = DotProduct(Start,pNormal) - pPlane->d;
        float        EndD  = DotProduct(End,pNormal)        - pPlane->d;
       
        if(StartD >= Radius && EndD >= Radius)        //should be 0, not 10, enlarged for tolerances
        {
                MoveTouchNode(pBSP,pNode->front,Start,End,Radius,TouchedLeafs);
                return;
        }

        if(StartD < -Radius && EndD < -Radius)
        {
                MoveTouchNode(pBSP,pNode->back,Start,End,Radius,TouchedLeafs);
                return;
        }
       

        MoveTouchNode(pBSP,pNode->front,Start,End,Radius,TouchedLeafs);
        MoveTouchNode(pBSP,pNode->back,Start,End,Radius,TouchedLeafs);
}

---