Fudging intersection with multiple bodies

Here's the place to get help and discuss features. The focus is on the C++ version, but generic questions are welcome.
ElectroDruid
Posts: 91
Joined: Thu Apr 24, 2008 2:09 pm

Fudging intersection with multiple bodies

Postby ElectroDruid » Sun Mar 01, 2009 6:53 pm

This sort of follows on from the fluid simulation thread, here: viewtopic.php?f=3&t=574
I didn't know whether to just carry on posting there or start a new thread, but I thought a new thread would be best since it's a more general problem...

To cut a long story short, the fluid simulation I'm working on does the actual fluid simulation part almost entirely seperately from Box2D - it's just quicker for performance and memory to handle fluid particles myself. However, they still need to interact with Box2D, and one of the problems I have is getting fluid particles to interact properly with static level geometry.

My fluid particles are circles, with a centre position and a radius. They're integrated using a Verlet (rather than Euler) system, so if they intersect with something, all I have to do is to find a suitable place to reposition the particle, and the integration pretty much handles the velocities for me. My collision system basically looks for shapes in the same part of the world as the particle (I have a grid system and use an AABB query for this), and for each shape tests to see if the particle circle is inside the shape. If it is, we calculate the nearest point on the outside of the shape to move the particle to, and move it there.

This works well when the particles are only colliding with one static b2Shape at a time (such as walls or the ground), but it struggles with corners where two (or more) b2Shapes line up against each other, or intersect. Pushing the particle to the nearest position out of one shape it's intersecting may put it straight inside another shape, so my particles have a tendency to "leak" through gaps:

Image

What should I do about this? How does the Box2D engine internals deal with these situations? (I've tried finding the code that deals with this, but the inner workings of Box2D are pretty impenetrable to me). I've tried doing another AABB test when pushing a particle out of a body, to make sure it's not going to be put inside another body, but (a) that's a lot of expensive AABB tests, and (b) even if the code does discover that there's a problem, at that point there's no sensible way to work out where the particle *should* go. I can set it back to its position from the previous frame, but its hardly an ideal solution.

ewjordan
Posts: 803
Joined: Sun Sep 23, 2007 2:35 pm

Re: Fudging intersection with multiple bodies

Postby ewjordan » Sun Mar 01, 2009 11:01 pm

The problem here is that the overlap against (for instance) the big wall on the right is showing up as being against the bottom edge of it, whereas you really only want things projected out to the left or right. Eventually marking of interior edges like this may become part of Box2d, but for now, it's not.

You might try working around this problem by not placing static shapes flush against each other, but instead having some overlap where they meet. Box2d doesn't do anything particularly clever about these things, and similar situations can and do arise when you have small objects (we discussed this a bit in the convex decomposition thread, because that stuff tends to expose these issues as well). TOI calculations and CCD can help, but even there, things should overlap a bit in order to prevent penetration, since the shapes used for TOI are actually somewhat shrunken.

You could try doing TOI calculations yourself, too, if creating overlapping shapes doesn't work (or if it's not feasible) - for circle vs. static object, it's not too difficult, and using Verlet integration for the particles means that you have the old positions stored away anyhow, so you just need to test for the time that the circle first touches the shape using a sweep test and move the circle to the corresponding location. You may _also_ still need your usual penetration check, as TOI calculations can be insufficient to prevent slip-through (if something is just barely moving, you get precision problems in the calculations).

It's a tough problem, though, I'll admit - issues like this are what ultimately made me give up work on a Verlet particle based physics engine a while back. I could never quite get all of the tunneling issues figured out right, esp. with tiny objects in play.

jdindia
Posts: 45
Joined: Fri Nov 14, 2008 6:22 am

Re: Fudging intersection with multiple bodies

Postby jdindia » Mon Mar 02, 2009 1:37 am

I had this kind of a problem a few years ago in my own simple physics simulation and I spent *forever* trying to solve it (and did in a limited way). Basically, I don't think the simple 'just project it out' works. You have to do more than that. You can make the shapes overlap. You can try marking interior edges so they project differently (like maybe through their neighbor's normal). You can try to get fancy and generate a list of shapes that are in question and project out of the union of the shapes. Also, it's worth mentioning that normally you project out from the static wall's normal, but if you can identify that the object contains a vertex of the static shape, then you can switch and project along a normal from the object's point of view [for circles, along the vector (center of circle - vertex)]. Your circles are kind of small so that's probably not going to work very well for you, but it did wonders in my case. If you could somehow be slightly more flexible in identifying the 'near a corner' case, it might work.

There are lots of things to try. It's just most of them won't work too well or are hard. =)

ElectroDruid
Posts: 91
Joined: Thu Apr 24, 2008 2:09 pm

Re: Fudging intersection with multiple bodies

Postby ElectroDruid » Mon Mar 02, 2009 6:40 pm

Having the static shapes overlap helps a bit, but not in all cases. It's still possible for an overlapping shape to push a particle inside another shape. I guess I'll look at TOI/CCD, but I tried it before and the performance hit was crippling. Perhaps I was using it in a sub-optimal way though, so it bears further inspection. What would be the most optimal way to do this in the engine? Obviously I'd only need to perform tests for particles which are in a grid cell which contains Box2D geometry, but even then doing a full raycast from the old position to the (proposed) new position seems a bit heavy-handed. Unless I'm mistaken, all I'd really need to know is "how far along this line can the particle get before it hits something?", without needing to generate a full list of all of the shapes which intersect with the line. I just need the lambda, don't I? What's the cheapest way to get that?

Erin Catto
Site Admin
Posts: 2948
Joined: Thu Sep 06, 2007 12:34 am

Re: Fudging intersection with multiple bodies

Postby Erin Catto » Mon Mar 02, 2009 7:06 pm

Ray-casts would be much faster than TOI/CCD. I would expand the AABB around a moving particle and cast a ray against the non-particle pairs. Most particles would have only particle pairs.

jdindia
Posts: 45
Joined: Fri Nov 14, 2008 6:22 am

Re: Fudging intersection with multiple bodies

Postby jdindia » Mon Mar 02, 2009 7:11 pm

Your particles are in the fluid simulation and therefore not visible. If they're a little off, it shouldn't matter too much. Have you tried simply resetting the position back to the prior position? x = x_old. Perhaps reflecting the velocity as well. It's not perfect, but you might not need perfect.

ElectroDruid
Posts: 91
Joined: Thu Apr 24, 2008 2:09 pm

Re: Fudging intersection with multiple bodies

Postby ElectroDruid » Wed Mar 04, 2009 2:05 pm

So, I've got it "nearly" working, but there are (predictably) some problems... You can't use TestPoint to see if a particle intersects with a b2Shape, because even though the particles are quite small (radius of 0.05f), the radius is significant enough that you can't treat particles simply as points. Fortunately I already had a function which can tell if a particle with a radius intersects with a b2Shape, so I've just tried using that. But I've replaced the collision response code (which previously just moved the particle to the nearest outside point, which was causing the problems) with something that does a RaycastOne instead, and moves the particle centre to the point of impact according to lambda, and then moves it along the normal the length of the radius to actually get it out of the b2Shape.

Code: Select all

// Detect an intersection between a particle and a b2Shape, and also try to suggest the nearest
// point on the shape to move the particle to, and the shape normal at that point
bool FluidTest::ParticleSolidCollision(b2Shape* pShape, int particleIdx,
                              b2Vec2& nearestPos, b2Vec2& impactNormal)
{
   b2Vec2 particlePos = liquid[particleIdx].mPosition;

   if (pShape->GetType() == e_circleShape)
   {
      b2CircleShape* pCircleShape = static_cast<b2CircleShape*>(pShape);
      float radius = pCircleShape->GetRadius() + liquid[particleIdx].mRadius;
      b2Vec2 circlePos = pCircleShape->GetBody()->GetPosition() + pCircleShape->GetLocalPosition();
      b2Vec2 delta = particlePos - circlePos;
      if (delta.LengthSquared() > radius * radius)
      {
         return false;
      }

      delta.Normalize();
      delta *= radius;
      nearestPos = delta + circlePos;
      impactNormal = (nearestPos - circlePos);
      impactNormal.Normalize();

      return true;
      
   }
   else if (pShape->GetType() == e_polygonShape)
   {
      b2PolygonShape* pPolyShape = static_cast<b2PolygonShape*>(pShape);
      const b2XForm& xf = pPolyShape->GetBody()->GetXForm();
      int numVerts = pPolyShape->GetVertexCount();

      b2Vec2 vertices[b2_maxPolygonVertices];
      b2Vec2 normals[b2_maxPolygonVertices];


      for (int32 i = 0; i < numVerts; ++i)
      {
         vertices[i] = b2Mul(xf, pPolyShape->GetVertices()[i]);
         normals[i] = b2Mul(xf.R, pPolyShape->GetNormals()[i]);
      }

      float shortestDistance = 99999.0f;
      float radius = liquid[particleIdx].mRadius;

      for (int i = 0; i < numVerts ; ++i)
      {
         float distance = b2Dot(normals[i], b2Vec2(vertices[i] - particlePos));

         if (distance < -radius)
         {
            return false;
         }

         if (distance < shortestDistance)
         {
            shortestDistance = distance;
            
            nearestPos = b2Vec2(
               normals[i].x * (distance + radius) + particlePos.x,
               normals[i].y * (distance + radius) + particlePos.y);

            impactNormal = normals[i];
         }
      }

      return true;
   }
   else
   {
      // Unrecognised shape type
      assert(false);
      return false;
   }
}

// For particles which we already know have an mPosition which means they intersect with a b2Shape.
// Do a raycast from the old position to the proposed new position, and find the point inbetween where
// the particle should actually go
void FluidTest::DoNewCollision(int particleIdx)
{
   b2Segment segment;
   segment.p1 = liquid[particleIdx].mOldPosition;
   segment.p2 = liquid[particleIdx].mPosition;

   float32 lambda=1;
   b2Vec2 normal;
   b2Shape* shape = m_world->RaycastOne(segment, &lambda, &normal, true, NULL);
   
   if (lambda != 1)
   {
      b2Vec2 delta = liquid[particleIdx].mPosition - liquid[particleIdx].mOldPosition;
      delta *= lambda;

      normal *= liquid[particleIdx].mRadius;

      liquid[particleIdx].mPosition = liquid[particleIdx].mOldPosition + delta + normal;
   }               
}


The particles don't leak through gaps now, but they do behave a bit erratically when they come into contact with the geometry, kind of bouncing around quite strangely. I think partly this is because my raycast test is obviously wrong - Although it tries to take the particle radius into account, it's moving the particle along the normal rather than back along the direction of the ray. Is there some way to adjust the raycast to instead represent a swept circle? My collision maths is a bit shaky in this field.

What could also be part of the problem is that, compared to the "move to the nearest outside point" method, the raycast method sort of cuts the particle's motion short for that frame. Using the nearest point method (with no other special collision response except to move the particle to the nearest point), a particle intersecting at an angle to the side/top of a polygon would sort of slide along it, whereas with the raycast method that sliding motion is basically removed. Any ideas about that?


Return to “General Discussion”



Who is online

Users browsing this forum: No registered users and 4 guests