Collision with non-contiguous static meshes

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
jlongstreet
Posts: 8
Joined: Mon Jul 04, 2011 8:00 pm

Collision with non-contiguous static meshes

Post by jlongstreet »

We're porting a game to XNA on Windows Phone 7, and running into some issues with collision with level geometry. It's a 2.5D platformer, and the level geometry is specified as a list of vertices/indices, which we read and create a static mesh for at runtime. The level isn't one solid body, though.

The first issue occurs in our test level, which looks like this:
Untitled.png
Untitled.png (8.98 KiB) Viewed 5398 times
The red and blue boxes are kinematic collision boxes attached to the player for doing ground checks. If the box is at the position of the red box in the above image, BEPU finds a collision between the box and the level geometry, several units down in Y from where the box actually is. However, if the box is at the position of the blue box, there's no collision. Since the blue box is outside of the entire level geometry static mesh, while the red box is inside it, my guess is that BEPU doesn't handle this case well. Is that an accurate assumption?

As a workaround, we've thought of splitting the collision into individual pieces (in this case, one for the top platform, and one for the bottom/right side). Would this be effective?

The second issue is performance based. When we load the geometry for a real level, Space.Update() takes over 100ms. The only difference is the complexity of the level geometry, so our working theory is that it's doing triangle-* collision tests for every triangle in the mesh with every other collidable, since everything is a broadphase hit with the mesh. We think the same workaround will probably help here as well. Does that make sense? Any other suggestions?

I apologize that I can't post actual screenshots for confidentiality purposes.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Collision with non-contiguous static meshes

Post by Norbo »

The red and blue boxes are kinematic collision boxes attached to the player for doing ground checks. If the box is at the position of the red box in the above image, BEPU finds a collision between the box and the level geometry, several units down in Y from where the box actually is. However, if the box is at the position of the blue box, there's no collision. Since the blue box is outside of the entire level geometry static mesh, while the red box is inside it
I'm not sure I follow completely. What I'd expect to see in that situation is that the red box will have a pair handler with the mesh, created whenever two collidables have overlapping axis aligned bounding boxes. The blue box, being outside of the mesh's AABB, does not have a pair. But based on the image, neither object should find any contact points. If there are contacts in that configuration, then the graphics are likely offset or incorrect in some way relative to the actual collision mesh.
my guess is that BEPU doesn't handle this case well. Is that an accurate assumption?

As a workaround, we've thought of splitting the collision into individual pieces (in this case, one for the top platform, and one for the bottom/right side). Would this be effective?
The problem shouldn't be happening/isn't expected in the first place, so the workaround may do nothing; fixing the core problem will likely be necessary.
The only difference is the complexity of the level geometry, so our working theory is that it's doing triangle-* collision tests for every triangle in the mesh with every other collidable, since everything is a broadphase hit with the mesh.
A convex-mesh collision pair performs deeper tests against the mesh's own hierarchy, decomposing the problem into triangle-convex tests only for triangles which have AABBs which intersect the convex's AABB. For example, the playground model in the BEPUphysicsDemos is 20,000 triangles, and it runs quite quickly even on the phone because it's only actually testing a handful of triangles at any time.
We think the same workaround will probably help here as well. Does that make sense? Any other suggestions?
In a normal situation, splitting meshes up a bunch will have either no benefit, or possibly lower performance a tiny amount. It amounts to shifting the hierarchy traversal load from specialized mesh trees to the overarching broad phase acceleration system, which, while fast, does not have all the guarantees that the mesh hierarchy has.

Given the very low performance and seemingly incorrect contact points, my first guess may be an old bug in the XNA framework. An overload of the VertexBuffer.GetData method that is usually used for runtime mesh vertex extraction does not work properly on the phone hardware. This may have been fixed by now (I haven't tested the problem directly since before NoDo), and the problem never occurred on the phone emulator or PC/Xbox360 versions.

If I misunderstood and the contacts are being generated in expected locations, and the performance is just very low, then it might be something else. How many triangles would each object collide with generally, and how many objects are in play at any time? The BEPUphysicsPhoneDemo may be a useful baseline to compare expectations against.
jlongstreet
Posts: 8
Joined: Mon Jul 04, 2011 8:00 pm

Re: Collision with non-contiguous static meshes

Post by jlongstreet »

Norbo wrote: I'm not sure I follow completely. What I'd expect to see in that situation is that the red box will have a pair handler with the mesh, created whenever two collidables have overlapping axis aligned bounding boxes. The blue box, being outside of the mesh's AABB, does not have a pair. But based on the image, neither object should find any contact points. If there are contacts in that configuration, then the graphics are likely offset or incorrect in some way.
That's what I'd expect as well, but the pair between the red box and the mesh will find contact points, inside the mesh, not on the top of it. The box shape has the correct position when we call Space.Update(), but the pair finds contacts with the mesh that are significantly outside the box shape. Using a ModelDrawer on the box, I can clearly see that the box is in the right place.

One potential issue is that these boxes are attached to the player character, and as such we set their position directly every frame based on the position of the player. The boxes are NoSolver, so I could see how it would be possible for BEPU to be putting them through the floor from gravity, only to have us overwrite their position. However, we set the position before calling Scene.Update(), so I'd assume that BEPU uses the position we set. Is there perhaps a better way to keep a collision shape attached to its parent with an offset?
In a normal situation, splitting meshes up a bunch will have either no benefit, or possibly lower performance a tiny amount. It amounts to shifting the hierarchy traversal load from specialized mesh trees to the overarching broad phase acceleration system, which, while fast, does not have all the guarantees that the mesh hierarchy has.

Given the very low performance and seemingly incorrect contact points, my first guess may be an old bug in the XNA framework. An overload of the VertexBuffer.GetData method that is usually used for runtime mesh loading does not work properly on the phone hardware. This may have been fixed by now (I haven't tested the problem directly since before NoDo), and the problem never occurred on the phone emulator or PC/Xbox360 versions.
That's certainly good to know. I'll try to dig deeper and figure out what's taking the time. I'm pretty sure we don't have a VertexBuffer.GetData problem, because this occurs on the emulator and PC version as well.
jlongstreet
Posts: 8
Joined: Mon Jul 04, 2011 8:00 pm

Re: Collision with non-contiguous static meshes

Post by jlongstreet »

For reference:

The box collidable's bounding box is:

Code: Select all

boundingBox	{Min:{X:5.999344 Y:-3.357386 Z:-0.435012} Max:{X:6.999356 Y:-2.357386 Z:0.564999}}	Microsoft.Xna.Framework.BoundingBox
The two contacts are:

Code: Select all

{Position: {X:6.505825 Y:-4.145864 Z:0.04420946} Normal: {X:0 Y:1 Z:0} Depth: 3.09532}	BEPUphysics.CollisionTests.Contact
and

Code: Select all

{Position: {X:6.520134 Y:-4.117976 Z:0.07146838} Normal: {X:0 Y:1 Z:0} Depth: 3.127281}	BEPUphysics.CollisionTests.Contact
All of these numbers are coming from BEPU. The penetration depth is also incredibly high.

As a sanity check, I also set IsAffectedByGravity to false on the entity. That doesn't change anything.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Collision with non-contiguous static meshes

Post by Norbo »

One potential issue is that these boxes are attached to the player character, and as such we set their position directly every frame based on the position of the player. The boxes are NoSolver, so I could see how it would be possible for BEPU to be putting them through the floor from gravity, only to have us overwrite their position. However, we set the position before calling Scene.Update(), so I'd assume that BEPU uses the position we set.
The engine will indeed use the most recent position for all the calculations. Position integration is the last step. If the object is affected by gravity, then it could build up velocity such that it ends up in the ground after the position update, but the contacts for that frame will be at its prior position (if any).

Resetting the linear/angular velocity of an entity to that of its 'parent' will tend to help keep things in order, but none of that will likely actually fix anything.
Is there perhaps a better way to keep a collision shape attached to its parent with an offset?
The most robust method is to make it a compound shape. A compound collidable's children can have different collision rules, so the bottom detector's collision rules can be set to NoSolver. The EntityConstructionDemo in the BEPUphysicsDemos projects shows a variety of related setups.

If you don't care about the contact points but rather just want to know if something is in the AABB of the detector, then a simpler option may be to expand the AABB of the player's body and then just check the body.CollisionInformation.OverlappedCollidables for a subset which overlap the detector's AABB. This is similar to what the in-development character controller does, and requires the current development version (http://bepuphysics.codeplex.com/SourceC ... evelopment) to work since it includes the settable BroadPhaseEntry.BoundingBox property.
The penetration depth is also incredibly high.
That's interesting. Given that the position of the contact is completely outside of the bounding box, something weird is definitely occurring. I don't know of anything off the top of my head that should behave like that.

If an object goes through a triangle mesh without any horizontal movement, and a contact's generating triangle still has an overlapping AABB with the convex, the contact can stick around by design- but there are many limitations on it to prevent goofy situations. I don't know what configuration would lead to that consistently happening.

A reproduction case would be very helpful in diagnosing the problem.

Also, what version is this in?
jlongstreet
Posts: 8
Joined: Mon Jul 04, 2011 8:00 pm

Re: Collision with non-contiguous static meshes

Post by jlongstreet »

Norbo wrote: The most robust method is to make it a compound shape. A compound collidable's children can have different collision rules, so the bottom detector's collision rules can be set to NoSolver. The EntityConstructionDemo in the BEPUphysicsDemos projects shows a variety of related setups.
I've thought about that, but with the way this game is structured it would be complicated. The detector is its own game actor, with its own physical component, which owns the entity/collidable. That actor is a subactor of the PC. We're trying to stay as true to the original codebase as possible, so if there's a way to make this work without making a compound shape, I'd rather not.
That's interesting. Given that the position of the contact is completely outside of the bounding box, something weird is definitely occurring. I don't know of anything off the top of my head that should behave like that.

If an object goes through a triangle mesh without any horizontal movement, and a contact's generating triangle still has an overlapping AABB with the convex, the contact can stick around by design- but there are many limitations on it to prevent goofy situations. I don't know what configuration would lead to that consistently happening.
That could have something to do with it. The repro case is the character starting on the mesh and jumping. Clearly, the detector will be contacting the floor to begin with. But I can't imagine it stays in the AABB of the triangle from the ground for the entirety of the jump.
Also, what version is this in?
I'm currently running latest development, but I've also reproduced it in 0.16.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Collision with non-contiguous static meshes

Post by Norbo »

if there's a way to make this work without making a compound shape, I'd rather not.
In that case, the separate entity with controlled velocity/position will be fine. The SimpleCharacterController and CharacterController (now CharacterControllerOld in the development version) both use detector entities in a similar way.
That could have something to do with it. The repro case is the character starting on the mesh and jumping. Clearly, the detector will be contacting the floor to begin with. But I can't imagine it stays in the AABB of the triangle from the ground for the entirety of the jump.
If the detector's center starts below the supporting triangle's plane and it only happens when there is no horizontal motion, it may be related (though the lack of AABB overlap is a confounding factor). If it's not already, you could try setting the mesh's sidedness to one-sided (Clockwise or Counterclockwise, depending on its winding).

If the detector's center was below the triangle plane, note that it will no longer generate contacts with the one-sided ground until a normal can be created that doesn't face away from the solid side's normal. One sided meshes will only create contacts with normals which do not face away from the 'solid' side.

A stripped-down sample which shows the problem and which I can run and debug will probably be necessary to diagnose the problem if the above isn't it.
Post Reply