Bumpy triangle meshes

[sparkprime]

Kester, reprojecting the position seems to have helped a lot. I still get some weird behaviour on the edges but this is to be expected I think as it's intersecting with two triangles which have completely different normals, and thus it's going to be pulled off to the side a bit.

[Erwin Coumans]

Kester, reprojecting the position seems to have helped a lot. I still get some weird behaviour on the edges but this is to be expected I think as it's intersecting with two triangles which have completely different normals, and thus it's going to be pulled off to the side a bit.

I'll make sure to include this option in a future Bullet version.

One solution to your 'edge problem' is to 'instrument' the triangle mesh, so you can determine valid normals for 'edge' and 'vertex' contacts.

An edge contact is a contact along an edge shared by two triangles. You can pre-compute the range of valid normal directions in advance, and only perform the correction when the normal is 'out of range'. Another physics developer reported this fix and he had good success with it. I haven't implemented this myself yet.

Cheers,
Erwin

[sparkprime]

Is that better or worse than just storing a flag per triangle saying whether or not the normal should be corrected? This flag could be generated per triangle by using the sharpness of the edge with every neighbouring triangle.

[Dirk Gregorius]

How does this handle situations where the level is composed out of several meshes (e.g. a racing track with several ramps)? Since you now have different meshes and no connectivity information between them. Also all these methods basically consider the case where you are "above" the triangle mesh. If you use welding you can get wrong normals if you are "aside" of the mesh. A typical problem is that the normal is corrected to point upwards (though it should point to the side) and you get support in the character controller which allows the player to climb areas which he shouldn't. Snapping the normal into the range between adjancent face normals is only correct if you are supported by this triangle. It is simple to construct cases where this is wrong and sadly these cases are not unusual.

My personal opinion is that we try to fix a problem which results from the overall design how to detect contacts. E.g. clipping solves many problems you have with distance based approaches with margins. It does not solve the problem with many different meshes though :\. My suggestion would be to maybe discuss alternative approaches than the current "hacks" to solve this problem. I am not saying that you cannot make everyting work with these fixes. Many games have been shipped using the mentioned ideas. I just argue it is plenty of work and very cumbersome to get it work correctly.


Cheers,
-Dirk

[sparkprime]

Dirk:

The inverted normal problem you mention, I solved by snapping to the direction of the face normal but preserving the direction of the original normal. There is some nastiness at 90 degree edges though -- if a body is on top of a cube and you slide towards the edge, it ends up 'hitting' the vertical wall, presumably because there is a small amount of penetration down into the top face, and this is enough to prevent the body from falling off. Of course if the normal was forced outwards it would have the opposite effect -- propelling the body off the cube as it approached the edge. So no win situation there.

I actually (ab)used this phenomenon (making triangles only 'push' in a single direction) with my gimpact vehicle meshes. I know I ought to use hulls but trimeshes are easier to work with until I have proper modeller support. Anyway, sometimes clutter can end up rattling around inside the vehicle, so I have a contact added hack that 'corrects' the normal so that it always points out of the vehicle (the vertex winding is consistent throughout the mesh). This means that other bodies do not end up 'stuck' inside the vehicle as firstly it's twice as hard to penetrate the skin, and secondly they receive no resistance on their exit journey. It seems to work OK so far.

Generally I don't like any of the methods here but I have sort of come to accept that without major changes to the way triangle meshes are implemented, they are the most robust solutions available.

If there is a solution that works perfectly within a mesh, but not between meshes, then this at least presents an obvious work-around to the modeller -- just fuse the two meshes

The collection of contact added hacks I've accumulated is between lines 89 and 280 of http://gritengine.svn.sourceforge.net/v ... iew=markup

[Erwin Coumans]

It is simple to construct cases where this is wrong and sadly these cases are not unusual. [...] discuss alternative approaches than the current "hacks" to solve this problem [...]

If it is simple, please construct a reproduction case in any of the Bullet demos. Rather than discrediting other peoples work as "hack" or discussing better alternatives, please provide your own superior implementation. I'm looking forward to see it

Is that better or worse than just storing a flag per triangle saying whether or not the normal should be corrected? This flag could be generated per triangle by using the sharpness of the edge with every neighbouring triangle.

Storing information how and when to clip normals per edge and vertex should solve the problems mentioned, better so than a boolean flag per triangle. Also, you can preprocess multiple meshes and instrument features between separate but touching meshes.
Cheers,
Erwin

[Dirk Gregorius]

I had no intention discrediting anybodys work. It is a tough problem (much tougher than in appears on the first look in my opion). My intention was maybe to spawn a new thread from this discussion and discuss this problem from a broader perspective or share some of my experience. If there is no interest in discussing this topic, please excuse hijacking this post.

[Erwin Coumans]

Please provide a reproduction case, and possibly a better implementation.

Thanks,
Erwin

[Dirk Gregorius]

I will see what I can do. I worked on this problem for Havok so I must be carefull not to violate my NDA.

[Erwin Coumans]

There are still some issue with this implementation:

Code: Select all

/// Changes a btManifoldPoint collision normal to the normal from the mesh.
void FixMeshNormal(btManifoldPoint& cp, const btCollisionObject* colObj0)//, int /*partId0*/, int /*index0*/)
{
   const btTriangleShape* tri_shape = static_cast<const btTriangleShape*>(colObj0->getCollisionShape());
   btVector3 tri_normal;
   tri_shape->calcNormal(tri_normal);
   btScalar dot = tri_normal.dot(cp.m_normalWorldOnB);
   if (dot<0.f)
   {
   	   tri_normal *= -1.f;
   }

   cp.m_normalWorldOnB = colObj0->getWorldTransform().getBasis() * tri_normal;

   // Reproject collision point along normal.
   cp.m_positionWorldOnB = cp.m_positionWorldOnA - cp.m_normalWorldOnB * cp.m_distance1;
   cp.m_localPointB = colObj0->getWorldTransform().invXform(cp.m_positionWorldOnB);
}

As I mentioned before, we need to instrument the triangles for concave edges and vertices:

Storing information how and when to clip normals per edge and vertex should solve the problems mentioned, better so than a boolean flag per triangle. Also, you can preprocess multiple meshes and instrument features between separate but touching meshes.

I hope I can find the time soon to provide a basic implementation that can use triangle instrumentation, and it is up to the developer to provide this instrumentation (either compute it automatically or integrate it into the art pipeline and give artists control over it). Instrumenting triangles based on disconnected but touching meshes/shapes is possible but more work: there might be several different triangles/shapes along a very long edge, each with its own limits.

Another remaining issue is that the distance/penetration depth is not correct for the newly clamped normal. A better solution would be to modify the collision detector so it only searches in the allowed direction, based on the triangle instrumentation. For the minkowski penetration depth solver this would be trivial, because it searches along a fixed set of directions distributed over a unit sphere, so we can ignore directions outside of the valid edge/vertex clamping range.

For the EPA penetration depth solver it will be a lot harder to clamp the results into a certain region, but we could try out to use MPR instead.
Cheers,
Erwin

[kester]

All my world meshes are one-sided, so I always use the triangle normal (even if collision_normal.dot(tri_normal) < 0.0)

I think instrumenting the edges is probably the way to go though, but I couldn't afford the memory or time to investigate it.

[fishboy82]

I had no intention discrediting anybodys work. It is a tough problem (much tougher than in appears on the first look in my opion). My intention was maybe to spawn a new thread from this discussion and discuss this problem from a broader perspective or share some of my experience. If there is no interest in discussing this topic, please excuse hijacking this post

I think it's a good idea to spawn a new thread for this topic, I am also intersted in this ,and willing to learn some experience from yours because I am currently write my own mesh-convex collision algo and meet the same problem ,my solution is like Dirk and Peter said previously that construct the voronoi region for the triangle vertex/edge . I use Peter's method that I didn't construct the Voronoi region as a preprocessor, I construct them in the run time .Also I don't construct them explictlly. I just "computing the voronoi regions by keeping a list of "voided" edges and vertices for each collision pair / detector＂,
But the algo is in processing I don't know whether it works good. Aslo this method can not solve the mult-level mesh problem,(May be a little change like peter said "hash code based on coordinates" but will be a little time consume).