Sign in to follow this  
Kurt-olsson

Help me solve the last 5% in my collision response

Recommended Posts

Hi. I have a small demo in Javascript that i am having some trouble with.

The problem is when my lines are obtuse angled.

 

There is some small jittering when sliding on them in the point between the lines.

 

What is wrong here? My recursive method? My sorting on the Lines in the loop? Or the fact that i need to check against the vertex points before?

 

Short Pseudo code:

 

Give player a velocity

Send Position + velocity into method

Check against all lines, are player free?

If not, correct against all the lines NORMAL pushout vector compared with SPHERE diff of penetration

If we have made corrections, run the method again to see if our new position is also free 

Correct the velocity with the "slide" factor.

If no hits return position / or when method is finished.

 

Download my demo and i would be very happy if someone can point me in the right direction.

 

Help me solve my last 5%. =)

Edited by KurtO

Share this post


Link to post
Share on other sites

Good job. I tested the example, but I can't really tell what the problem is... Aside from the fact that collision is only enforced when the player circle is on the same side of the line as the normal, I don't see any collision-response problems. Can you please give more details?

 

And the is "Has collisions:" line always supposed to show "false"?

Edited by tonemgub

Share this post


Link to post
Share on other sites

thanks for your kind words.

 

The problem is when sliding slow with really big velocity in the obtuse angles, then the circles starts to jitter a bit.

Also in the Problem area nr 2, (the big V) the circle dont stops at the closest place on the line when entering with big velocity.

 

going in the "V" shape with full speed, the circle stops sometimes 2-3mm from the line and then one-two jerky movements to get out of there.

 

The HasCollission function has a bug, i was missing its input parameters, but that function isnt used in the collission code.

 

 

Next test:

 

I will try to do test after the pushout has been done. get the length again for the closest line (only two) and then push the circle at the closest point if that is not the case.

This will be second test after the pushout.

The new sliding-velocity works only perfect if the circle is superclose to the line, otherwise jittering will appear.

Edited by KurtO

Share this post


Link to post
Share on other sites

Ok, I think I get it now. When you detect a collision with a line, you are pushing the new position (px and py) back along the line's normal. But if the result of the push happens to intersect with a second line, then your recursive call is going to push the position back against the second line's normal, and this position will again be in collision with the first line. It's like the lines are playing pong with your player, pushing them back and forth. smile.png

 

One way of solving this is to not push the player more than it's needed.

 

I think the problem is also partially caused by the fact that you are currently changing the direction of the velocity vector into the "slide" direction, which is allowing the player to slide backwards toward the original position. Instead of this, you should keep the old velocity direction, and just reduce it's length.

 

Theoretically, a slide should only take place along the first collided line in the same recursion. The slide along that first line should not produce a second slide along a second line. I think the collision response for that second line should be to simply stop the player at the closest collision point along the original velocity vector, and not let him slide further.

 

Instead of moving the position back against the normals every time, you should keep a variable (let's call it "velocityAmount"), which will take values from 0.0 to 1.0. Initially, this variable will be 1.0, meaning that there's no collision along the velocity vector. As you check for collisions with each line, if any colision is detected that is closer than the last, you compute the new velocityAmount (which will be smaller than the last). After you've checked all lines, you just move the original player position by (velocity * velocityAmount).

Only then, to get the sliding effect, you compute the sliding direction, and repeat the process, but this time, you should not generate a new "slide" in case of collisions.

Edited by tonemgub

Share this post


Link to post
Share on other sites

Wow. There are so many tips/correction in your post. And i think you really nailed the problems, because i recognize the ping-pong effect.

 

Now, when i think of it of course i should only calculate the sliding velocity once, and then cut the length when the next collision occurs! =) 

Its like you say, if the next collission then is up against a big wall, i would just simply stop instead of calulatin the new direction and velocity.

 

I am in a rush right now, but i will work on my demo tonight and update.

 

Thank you so much for your answer.

Share this post


Link to post
Share on other sites

You're welcome.

 

Because I've been curious about this for a long time (I never actually implemented my "theory"), I changed your code to do proper "stop at collision" response using my tips above. If I'm curious enough, I'll add sliding too, a bit later.

 

Sorry, I don't know how to attach files here. Here's just the modified ResolveCollissions function:

var ResolveCollissions = function(px,py,velx,vely,iteration,slide) {
/*        if (iteration > 100) {
            this.x = pos_x_old;
            this.y = pos_y_old;
            return;
        }*/
        var velocityAmount = 1.0;
        
        var pushx = 0.0;
        var pushy = 0.0;

        //i think i need to sort the lines for the first impaced line first etc instead of looping it in normal sort order!?!?!?
        //lines.sort(compare);
        for (var i = 0; i < lines.length; i++) {
            var closestpoint = new ClosetPointOnLine(lines[i].x, lines[i].y, lines[i].x2, lines[i].y2, px, py);
            var ln = new lineNormal(lines[i].x, lines[i].y, lines[i].x2, lines[i].y2);

            var VdotN = velx * ln.dx + vely * ln.dy;
            
            var lclosest = lineLength(px, py, closestpoint.x, closestpoint.y);
            var ltotal = Math.abs(VdotN);
            var newamount = Math.max(0.0, (lclosest - SPHERE_RADIUS) / ltotal);
        
            if (newamount < velocityAmount)
            {
                velocityAmount = newamount;
                pushx = (px - closestpoint.x) / lclosest;
                pushy = (py - closestpoint.y) / lclosest;
            }
        }
        
        px += velx * velocityAmount + pushx * 0.5;
        py += vely * velocityAmount + pushy * 0.5;
        
        if (slide)
        {
            // slideVelocity = dot_product(normalized_collided_line, velocity * (1.0 - velocityAmount)
            // call ResolveCollissions again with px, py, slideVelocity and slide = false
        }
        
        //Return the calculated position.
        this.x = px;
        this.y = py;
}

First time you call it, you have to call it with the extra "slide" parameter set to true, although that doesn't do anything right now.

 

Notice that even now there's still a bit of sliding, because the player position is still being pushed away from the collided line by a small amount (currently 0.5, but it can be much, much smaller; Quake 3 - where I got my inspiration from - calls it "EPSILON", and defiens it as 0.03125f, or 1/32). This is to avoid the player going "through" the collided line due to floating point precision errors. This means that there will still be a bit of jittering at the corners, but it will hardly be noticeable, because this time you're only pushing the player back by a very small amount, not the whole radius. Also, instead of pushing back along the normal (which may cause "skipping" - even though it's hardly noticeable), it would probably be better to project (dot product) the EPSILON-length normal onto the original velocity vector, and push back by that amount (along the velocity vector, not the normal).

Edited by tonemgub

Share this post


Link to post
Share on other sites

Ok Update.

 

Now i fully understand the code. It takes a percentage of the velocity to cut it before the player overpasses the lines.

This way i don+t need to push out that much.

 

This makes first part ultra-correct.

 

A Fint the closest intersection

B Cut the velocity so the remaining velocity reaches the intersection point

C Calculate the sliding vector

D Check recursive the new velocity AND if something is hit, DONT calculate a new sliding velocity, simply just CUT the speed.

 

I was up last night coding, and i did exactly like this, put i didnt finish with taking off percentage of the velocity, and i think that that is what makes it really good when fining intersection point.

 

It is still some jitter, and i dont understand the 0.5, shouldent it be like 1.001 (the pushout and then some extra just to be safe)?

Edited by KurtO

Share this post


Link to post
Share on other sites

It kind of feels like you might be having a problem with the intersection of two adjoining planes being off a bit if pushed out by a radius.  The sphere can actually be a little off from a radius-pushed-out plane.

 

See the potential inaccuracy and beveling section of this old article:  http://www.gamasutra.com/view/feature/3099/bsp_collision_detection_as_used_in_.php?print=1

Share this post


Link to post
Share on other sites

Hey,

 

Here's another version of my approach. I added sliding along the first line only, and separated line-collisions from line-endpoints collisions, but the endpoints case is not being handled properly currently (the proper way would be to slide the player's position along the tangent of the circle centered at the endpoint with radius SPHERE_RADIUS, but this was too complicated for me to implement). I think your problem is also because you're not handling the endpoints separately. However, it does seem that your V2 Clipping version handles convex endpoints (it only fails at concave ones) better than my current version, whereas my version handles the concave endpoints properly, so maybe you could mix the two methods together to get better results...

 

Also, I now have a better idea about how to implement sliding - I was wrong before - sliding should be done not only along the first collided line, but along subsequent lines as well. The problem is stopping the slide at the closest point (from the destination point) on whichever line is collided with last. To do this, it is probably better if your recursive function can just be modified to take the destination point as parameters directly, rather than just the source point and velocity. Then, at every recursion step, you calculate the new velocity from the source and destination points, but I didn't have time to make these changes...

 

[attachment=23670:collision.html]

 

(Yay, I found out how to attach files! smile.png )

Edited by tonemgub

Share this post


Link to post
Share on other sites

I think your approach with cutting the velocity before the circle hits is the best one.

This makes the circle always stop at the intersection point of the first line.

 

Now i will have to fix the last part.

 

Check vertex of the lines (points)

Give new slide vector after player got hit forst time.

So i my recursive method i will have something like (playersVelocityCut = true)

then give him a slide vector again etc.

 

the problem now is my slide vector is so small after cutting the velocity. So i need to have some sort of where player wants to go slide vector.

i will base the sliding based on where the player wants to go.

Share this post


Link to post
Share on other sites

i will base the sliding based on where the player wants to go.

Yes, this is exactly what I tried to explain before: it would be better if your function took the destination point as input instead of the velocity. Also, when generating the slide-to position, you should use your existing function ClosestPointOnLine, instead of the new ProjectPointOnLine I used, so that the sphere stops sliding at the end of the line. Otherwise, if the projection of the destination point is outside of the line segment, the player sphere will slide too far, possibly missing other collisions.

 

Also in my example, during the slide-response, you should call ResolveCollissions repeatedly, each time using the returned x and y values as the new source position (set them as the new px and py values which will be passed to the next ResolveCollissions call), and calculating a new slide-to position based on the existing destination position. You stop calling ResolveCollissions when the position it returns is "almost" identical to the last (px, py) position. By "identical" I mean: when the distance from the currently returned x and y position to the last returned position (which you saved in (px, py)) is smaller than 1.0 (one pixel) for example. I think this will also solve the problem of sliding against the convex corners, but it would probably still be better if you could handle that case by using your algorithm - in the example I attached, this is handled by just pushing the player away from the corner point by 20.0 pixels - I don't like that. This should be used instead of the "slide" boolean parameter I added before.

 

Also, I think it would be best if you separate the collision response from the collision detection, like you did with the GetClosestCollision function, except GetClosestCollision should always re-calculate and return the closest line & point instead of returning the closest line based on the cached "line[i].overlap" values. GetClosestCollision should also differentiate between lines and line-endpoints (like in my example), and it should return the closest point on the line, pushed-out along the normal of the line in case of a line collision, or pushed-away along the radius from the line-endpoint in case of a line-endpoint collision. Then, in the collision-response code (which remains in the ResolveCollissions function), you just call GetClosestCollision (the collision-detection code), initially with the source and destination points passed to ResolveCollissions, and then repeatedly with the destination position returned by GetClosestCollision, until GetClosestCollision returns a position that is "almost" identical to the last position like I explained above. Also, GetClosestCollision should return the destination point directly in case there's no collision (it currently returns 0, meaning there was a collision with the line at position 0?).

Edited by tonemgub

Share this post


Link to post
Share on other sites

Update!

 

i have followed this document a little bit and also tried to implement the things you pointed on, seperate detection and response.

I now have a function that returns data that we need when solving response.

http://www.peroxide.dk/papers/collision/collision.pdf

 

I think the key to the good routine my first version compared to my latest is to not just "push-out". Instead, calculate time of impact from a velocity.

Then get new velocity and run checks again.

 

And my pseudo code works like this now:.

 

Before movement, see if the player is free: 1.0 = free < 1.0 = we hit something and return the time t of impact.

If we dont hit anything, just move player

If we hit we check:
If player is not very very close, move the player close to the impact line - a little value
Now take the new velocity and run the function again recursivly.

 

This works now brilliant on edges corners, but have some problems in the vertex edges.

 

My next update will be to add checks for "edges" first and handle them seperatly.

 

I have uploaded a new document Version 4.

Edited by KurtO

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this