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%. =)

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"?

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.

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.

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.

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.

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).

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)?

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

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! )

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.