Verlet collision by particle path ray.

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
Kundelstein
Posts: 8
Joined: Wed Nov 05, 2014 8:34 am

Verlet collision by particle path ray.

Post by Kundelstein »

Hi guys,
I'm new here so please go easy on me.

I'm using Verlet integration.
Trying to resolve collision with static bodies.
My plan is to do for every particle (or body verticle):
1. Check if NewPos is inside the StaticBody.
2. If 1 == true, Make a ray from OldPos and NewPos and check intersection with any edge of StaticBody.
3. If 2 == true, Set NewPos (and Old) to IntersectionPos.

I have tried to use the variant, where I don't use OldPos but other value VeryOldPos which is taken before integration step.

My problem is that it just doesn't work, even for easy tests like Verlet Box vs Static Box.

Did anyone succeed with this method?


PS. I'm not interested in methods some people use:
1. Putting some circles or spheres where particles are.
2. Using SAT and treating my bodies as rigid ones.
3. Using Sat for every edge vs edge.
Kundelstein
Posts: 8
Joined: Wed Nov 05, 2014 8:34 am

Re: Verlet collision by particle path ray.

Post by Kundelstein »

Hi,

Since there was not even one reply I have to assume that either no one really did this or everyone think it is trivial.

After some initial tests I managed to make it running. Some thoughts:

1. Actually we do not need to check if new position for moving vertex is inside the static body. I added it 'just to make sure' we go in the right direction. It can be avoided by using one sided raycast.

2. We do not need any additional checks - edge vs vertex is enough. We just need to go both ways (body1edge vs body2vertex and body1vertex vs body2 edge).

3. For dynamic objects we use relative velocity. We also need to move the edge in a bit (I think edge vs point idea was covered even in Jakobsen's article).

4. The issue that was making my simulation to go wrong was because if the moving vertex once gets close to static edge, in next iteration (or collision step) it starts its raycast from edge, which means it can give no-hit. Temporary I fix it by moving starting point of the raycast by some epsilon i direction of the edge normal, so we are sure to hit it. I wish I knew some better solution for this.

5. We have 'perfect friction'. This means that if the vertex hits the static edge, it does not slide. In opposition: 100% slide (no friction) is moving the point outside by edge normal. So FrictionCoef would get some % of both. As I didn't do that yet, I'm not sure if that is the right approach.


Honestly speaking it all looks a bit scary for me.
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Re: Verlet collision by particle path ray.

Post by raigan2 »

Do your particles have a radius/thickness? This would probably help make things behave a bit better.

One thing I've done in the past to make particle collision a bit less fussy is to raycast using a thick ray (which has a radius smaller than the full size of the particle), and stop at the moment of intersection, then let the static distance test (which uses the full size of the particle) handle it from there.

I guess this counts as "Putting some circles or spheres where particles are" but IMO there is no easy way to make infinitely thin rays totally robust (for one thing you get the "infinite friction" problem you mentioned); admittedly I'm not an expert on numerical precision or robust geometric predicates, but I think just inflating things a bit (even a tiny amount that won't be visible) really helps make it easier to avoid problems.
Kundelstein
Posts: 8
Joined: Wed Nov 05, 2014 8:34 am

Re: Verlet collision by particle path ray.

Post by Kundelstein »

Thank you for answer raigan2. I saw your examples some years ago.

I have to wrap around my mind those thick rays. It sounds like some way of dealing with it, though my experience tells me there will be complications.

Meanwhile I have checked the collision system in JellyPhysics (used Jelly Car game). The author uses simple penetration depth from distance to the edge. Unfortunately there is some unpleasant tweaking involved like checking the edge orientation and penetration threshold. My instincts tell me that it is used because of using absolute distance and it can be solved using signed distance.

I'm also thinking about how it was resolved in Gish game. As I remember the author used raycasts (of some limited length) from new position towards the edge (in normal direction). Funny thing because it is quite close to this distance checking from JellyPhysics.

In perfect world the above methods (with minor changes) would guarantee that even if by some miracle some point appeared inside some body, it would be pushed outside. It feels safer as the raycast derived from points' path would do nothing, so some other, additional way would have to be included (or maybe its actually better to handle it as separate case).

The only other example of dealing with collision on vertex basis I stumbled upon is NooNoo Physics. It actually uses SAT by projecting bodies to resolve collision on per-edge basis, then it pushes body 'outside' from the geometric centre of the body. Watching the simulation reminds me circus shows with act of juggling knives,chainsaw and some dynamite - should blow up any time.
Kundelstein
Posts: 8
Joined: Wed Nov 05, 2014 8:34 am

Re: Verlet collision by particle path ray.

Post by Kundelstein »

Small update regarding raycast:

1. As for the problem with raycast from old position to new position: I missed collision because raycast starting point is already on the edge.

My old solution was to move the starting point along checked edge normal a bit. Even more robust solution would be to move the point along its path in GENERAL direction of the normal (lengthen a bit the path).

However I think the best way to handle it would be to check the raycast in OPPOSITE direction - from new position to old position. This way we are 100% sure we will eventually hit the edge. Of course mathematical robustness (well, lack of it) CAN give different results for different checks, so IsPointInsidePolygon can be only treated as an early out, not the 100% answer if the point is inside the polygon. For example: Point on edge can give IsPointInsidePolygon true, but PointPathRaycast can return false, however when point moves a bit more inside polygon, both checks should return true and collision can be handled accordingly.

2. Friction can be treated in similar matter as Paul Nettle solved sliding along the walls in his sweep sphere (ellipsoid) example. Just project the rest of the path on the edge and multiply it by some FrictionCoef. Just lets not start with 'So maybe we will do some step loop like Nettle did' - this would require single step time division by all the hits, and by definition the simulation considered here has them quite a lot (besides it's long and hard topic, although in case of particle based simulations it is not such a bizarre way of handling things).

3. Unfortunately there is one more thing to reconsider. If we are using verlet we can really badly mess up during collisions of the single point with multiply edges (in the single frame). Every time we correct the position we also have to take care of the old position so our ray is correct. I will have to do some tests, but my guts tell me that I won't get away without some kind of 'single frame old position' value.
Kundelstein
Posts: 8
Joined: Wed Nov 05, 2014 8:34 am

Re: Verlet collision by particle path ray.

Post by Kundelstein »

Hi guys.

As you probably noticed, I focused my research on purely particle based bodies and dynamics. Mainly using verlets (though probably I can switch to some other integration).

I have tested out the system when particles path is checked. Works fine either with time rewinding scheme or with purely static world.

I have also tested penalty based methods, those used in Gish and JelloCar. This is obviously easier to handle as even if there are some problems with robustness with a few iterations those are solved pretty nicely.

The checks I used so far are vertex vs edge both ways. So if we are supposed to check collision of body A and B, we first check all vertices of body A against all edges of body B, then all vertices of body B against all edges of body A.

Now I have found another problem, which happens in my simulation and also in JelloCar.
If we are checking collision between 2 triangles and if they overlap when turned with edges to each other, we will miss a collision, since nether vertex overlaps, just edge.

(The extreme case can be also when we check two identical rectangles - we have no corner-to-edge collisions there (in this case mostly due to lack of robustness). this is however very rare and probably can be tweaked a bit.)

Did anyone have any example or know how to deal with those things?
RandyGaul
Posts: 43
Joined: Mon May 20, 2013 8:01 am
Location: Redmond, WA

Re: Verlet collision by particle path ray.

Post by RandyGaul »

You're just trying to detect collision here right? If so I can perhaps help, but I think a rough sketch or diagram to point out the exact cases would be really helpful.
Kundelstein
Posts: 8
Joined: Wed Nov 05, 2014 8:34 am

Re: Verlet collision by particle path ray.

Post by Kundelstein »

Image
Behold my Photoshop skills, 3 years of art studies definitely paid off!

Thank you for your interest Randy.
At the top we have triangle case, at the bottom rectangle case.

To the left we have easy-pie case - we just check if the corner is inside the body and if so we push it to the closest edge (so it goes along normal).

To the right - my problematic case - I have some ideas how to do this, but I'm pretty sure there is already nice way of handling those things which I just do not know.

Each contact is treated separately one after another, so multiply contacts case is divided into plenty of single ones. As we have soft bodies (used with any kind of PDB) collision itself is resolved after pushing out the vertex - of course it means that contact edge will be pushed a bit in opposite direction.
RandyGaul
Posts: 43
Joined: Mon May 20, 2013 8:01 am
Location: Redmond, WA

Re: Verlet collision by particle path ray.

Post by RandyGaul »

I cannot speak of techniques for *resolving collisions* for PBD (it seems you're comfortable with just pushing bodies to non-separation along a given contact normal) due to lack of experience. However I can talk a little bit about detecting collision and gathering useful information to pass onto your resolution code. Please excuse me if you're already familiar with this algorithm:

For all 4 of your cases you drew you can use a single algorithm to detect collision. The way I implemented this was to find a transformation matrix to rotate both polygons into the (x, y) plane. From here the problem of collision detection is treated as 2 dimensional. Of course, this only works if your two polygons can be considered parallel.

Each polygon is stored as an oriented vertex loop in CCW order. From here we can apply an algorithm that makes use of the Separating Axis Theorem as detailed by Dirk Gregorius in his 2013 GDC lecture: https://box2d.googlecode.com/files/DGre ... DC2013.zip

I also mimic'd Dirk's slides a while ago and wrote down the 2D-specific version here: http://www.randygaul.net/wp-content/upl ... Points.pdf

This collision detection scheme can give you multiple points of contact (either one or two points of contact) and a collision normal, along with penetration depth of each point of contact. The collision normal defines the axis of minimum separation, which would be similar to the axis you used to press shapes apart for PBD.
Kundelstein
Posts: 8
Joined: Wed Nov 05, 2014 8:34 am

Re: Verlet collision by particle path ray.

Post by Kundelstein »

Thank you for your help. SAT would really help me if I had just normal rigid bodies.
It is my fault that I drew primitives to illustrate problems. However with soft bodies not all polygons have to be convex (a must have for SAT and many other tests).

So far I have found out 2 described methods:
1. Triangulation (or any other convex set generation) of the body before each collision test:
http://dpt-info.u-strasbg.fr/~tjund/recherche.html
2. Vertex to Edge and Edge to Edge + Special case:
Ericson - Real-Time Collision Detection (book)

Besides after detecting the collision I need to create contact manifold and eventually contact points.
Post Reply