Bumpy triangle meshes

sparkprime
Posts: 508
Joined: Fri May 30, 2008 2:51 am
Location: Ossining, New York
Contact:

Re: Bumpy triangle meshes

Post by sparkprime » Tue Feb 10, 2009 1:41 am

It might be useful to automatically detect these triangles when you add the mesh in the first place. Set up a map (a hashmap initialised to roughly the right size is probably the best bet) from edge to int (an edge is a std::pair<int,int> where the first index is less than the second index, to avoid duplicates). Now iterate through all the faces in the mesh, incrementing the 3 edges associated with each face. After this, any edge that has only one triangle is an external edge, and any face with 1 or more external edges is an external face.

If you want to do more work you can probably do better than this too.

pico
Posts: 229
Joined: Sun Sep 30, 2007 7:58 am

Re: Bumpy triangle meshes

Post by pico » Tue Feb 10, 2009 10:07 am

Hi Erwin and Sparkprime,

adding such edges by hand is no option i guess. Our 3d people would go nuts :)

Maybe such edges could be determined within the callback by inspecting the normals of the two triangles that use these edge? If the angle between the two normals exceeds a certain low degree then an edge normal is used. If not then the current callback is used.

The question is how to get the normals from the two triangles? Erwin, do you have a hint?

By the way, other physic engines must have the same problem. How does Physx or Havok deal with this problem?

User avatar
Erwin Coumans
Site Admin
Posts: 4193
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Bumpy triangle meshes

Post by Erwin Coumans » Tue Feb 10, 2009 5:39 pm

pico wrote:Maybe such edges could be determined within the callback by inspecting the normals of the two triangles that use these edge? If the angle between the two normals exceeds a certain low degree then an edge normal is used. If not then the current callback is used.
The question is how to get the normals from the two triangles? Erwin, do you have a hint?
Indeed, using this angle between connected triangles to determine 'internal edges' is a popular method. Connectivity is not available at run-time inside Bullet, so it is best to add some preprocessing step, as sparkprime mentioned, and make this information available for the callback. You could use a similar method to the btMultimaterialTriangleMeshShape, to store per-triangle information that can be access during the callback. See Bullet/Demos/MultiMaterialDemo for an example.

Another method is to perform a convex decomposition of the concave triangle mesh, and merging co-planar triangles into convex hulls.
Hope this helps,
Erwin

pico
Posts: 229
Joined: Sun Sep 30, 2007 7:58 am

Re: Bumpy triangle meshes

Post by pico » Wed Feb 11, 2009 12:55 pm

Hi Erwin,

thanks for verifying that this idea is actually used in other engines.

I guess it would be better to include the edge connection info into the standard mesh class. So other mesh classes like multimaterial would work with it too.
The edge info generation could be disabled by default and so users could decide if they want to generate the extra edge info or not.

The convex hull approach doesn't work as not only coplanar triangles are affected but also those with small normal changes.

Novas
Posts: 2
Joined: Mon Jan 05, 2009 2:13 pm

Re: Bumpy triangle meshes

Post by Novas » Sun Mar 15, 2009 2:03 pm

Hi everybody.

I'm currently using a GameEngine which has Bullet 2.73 and i get an error like that:

sometimes my objects behave as if there was a wall in the middle of my table. of course this happens exactly at those edges.

can you tell me whether 2.74 has a solution for this?

i didn't work a lot with bullet so i somehow can't really use the code above but of course i'd be happy to get rid of this behaviour. trying to upgrade seems like a rather easy solution :D

but does it work?

hope for your replies

thanks

User avatar
Erwin Coumans
Site Admin
Posts: 4193
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Bumpy triangle meshes

Post by Erwin Coumans » Sun Mar 15, 2009 7:40 pm

Can you please upgrade to Bullet 2.74, and
  • For the object that needs to slide smoothly , use capsule->setContactProcessingThreshold(0.);
    Avoid doing this for all objects, because it degrades resting contact a bit though, it might jitter a bit more.
  • Use the contact_added_callback to filter out the normals, as described here: http://code.google.com/p/bullet/issues/detail?id=27
Let us know if one (or both) helps,
Erwin

WiW
Posts: 1
Joined: Sat May 23, 2009 10:30 pm

Re: Bumpy triangle meshes

Post by WiW » Sun May 24, 2009 2:40 pm

I have encountered the same problem and have created the proposed workaround that does per-edge angle calculations.

Then I process contacts as follows:

Code: Select all

void bulletContactAddedCallbackObj(btManifoldPoint &cp, const btCollisionObject *colObj, const btCollisionObject *colObjOther, int partId, int index)
{
  const btCollisionShape *shape = colObj->getCollisionShape();

  if (shape->getShapeType() != TRIANGLE_SHAPE_PROXYTYPE)
    return;
  
  const btTriangleShape *tshape = static_cast<const btTriangleShape*>(colObj->getCollisionShape());
  const btCollisionShape *parent = colObj->getRootCollisionShape();
  
  if (parent == NULL || parent->getShapeType() != MULTIMATERIAL_TRIANGLE_MESH_PROXYTYPE)
    return;
  
  // Acquire edge angle information as we are going to check if edges are internal based on angles
  btMultimaterialTriangleMeshShape *pshape = (btMultimaterialTriangleMeshShape*) parent;
  const GeometryMetadata::FaceInfo *props = static_cast<const GeometryMetadata::FaceInfo*>(pshape->getMaterialProperties(partId, index));
  
  btTransform orient = colObj->getWorldTransform();
  orient.setOrigin(btVector3(0.0f, 0.0f, 0.0f));

  btVector3 v1 = tshape->m_vertices1[0];
  btVector3 v2 = tshape->m_vertices1[1];
  btVector3 v3 = tshape->m_vertices1[2];
  
  // Check first edge
  if (isPointOnLine(cp.m_localPointB, v1, v2) && props->edgeAngles[0] > INTERNAL_ANGLE_THRESHOLD)
    return;
  
  // Check second edge
  if (isPointOnLine(cp.m_localPointB, v2, v3) && props->edgeAngles[1] > INTERNAL_ANGLE_THRESHOLD)
    return;
  
  // Check third edge
  if (isPointOnLine(cp.m_localPointB, v3, v1) && props->edgeAngles[2] > INTERNAL_ANGLE_THRESHOLD)
    return;
  
  btVector3 normal = (v2-v1).cross(v3-v1);

  normal = orient * normal;
  normal.normalize();

  btScalar dot = normal.dot(cp.m_normalWorldOnB);
  btScalar magnitude = cp.m_normalWorldOnB.length();
  normal *= dot > 0 ? magnitude : -magnitude;

  cp.m_normalWorldOnB = normal;
}
The code that does the actual preprocessing is:
http://transwarp.unimatrix-one.org/geometrymeta_h.html
http://transwarp.unimatrix-one.org/geom ... a_cpp.html

I am then using it like:

Code: Select all

m_staticGeometry = new btTriangleIndexVertexMaterialArray();
m_scene->getRootNode()->batchStaticGeometry(m_staticGeometry);
m_staticGeometryMeta = new GeometryMetadata(m_staticGeometry);
m_staticShape = new btMultimaterialTriangleMeshShape(m_staticGeometry, true, aabbMin, aabbMax);
This seems to work quite well:) If anyone sees things that can be improved/fixed (I'm sure there are a few, since I am new to this thing), I would be glad to hear them. Also anyone can reuse this code for any purpuse if one so whishes.

pico
Posts: 229
Joined: Sun Sep 30, 2007 7:58 am

Re: Bumpy triangle meshes

Post by pico » Fri Jun 12, 2009 9:37 am

Hi WiW,

thanks for your effort. I will try that out. If it works it would take Bullet to a whole new quality level for games.

Erwin, wouldn't it make sense to make that preprocessing part of Bullet?
Maybe this could even be done on the fly only for the triangles that that the current contact point in question?
So the preprocessing could be skipped and that extra processing would only be needed for player controllers.

pico
Posts: 229
Joined: Sun Sep 30, 2007 7:58 am

Re: Bumpy triangle meshes

Post by pico » Fri Jun 12, 2009 11:25 am

Oops, after taking a look at the sources i saw they are not using bullet functions but BOOST and STD. This is no option.

Maybe it would be better to let Bullet do the hard work in realtime. Around the collision point an AABB should gather all triangles. Then a fuzzy algorithm could get connectivity between those few triangles. With this algorithm even unconnected (but forming an edge together) shapes would be taken into the edge considerations.

jthrush
Posts: 2
Joined: Fri Sep 11, 2009 11:45 pm

Re: Bumpy triangle meshes

Post by jthrush » Fri Sep 11, 2009 11:51 pm

So we've been seeing this same problem (a sliding capsule catching on internal static triangle mesh edges and bouncing up). After reading this thread, we tried the simple thing first: just calling setContactProcessingThreshold(0) for the capsule rigid body, and this seems to completely solve the problem.

I'm curious why people are pursuing the more complicated methods involving callbacks? Are we going to run into other problems if we call setContactProcessingThreshold(0), which I imagine is turning off all contact processing?

I would definitely just try adding that call first if you are experiencing this problem. I would also suggest adding it to the docs somewhere prominent, as this is a problem that I would imagine every game comes across.

IronSquare
Posts: 1
Joined: Tue Sep 15, 2009 3:29 pm

Re: Bumpy triangle meshes

Post by IronSquare » Tue Sep 15, 2009 3:35 pm

I've added the complex solution to my code, and it fixed it for the most part, but it still catches on vertices. I've tried setContactProcessingThreshold(0), and that doesnt seem to have done anything.. maybe its because im using it with Triangle Meshes...

So i'm still searching for a solution.

sparkprime
Posts: 508
Joined: Fri May 30, 2008 2:51 am
Location: Ossining, New York
Contact:

Re: Bumpy triangle meshes

Post by sparkprime » Thu Sep 17, 2009 11:45 pm

Yes that's basically my experience -- it helps a bit but there are still serious problems. Thinking of trying ODE but don't have time at the moment.

jthrush
Posts: 2
Joined: Fri Sep 11, 2009 11:45 pm

Re: Bumpy triangle meshes

Post by jthrush » Thu Sep 17, 2009 11:53 pm

That's odd because setContactProcessingThreshold(0) seems to have completely solved the problem for us.

User avatar
Erwin Coumans
Site Admin
Posts: 4193
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Bumpy triangle meshes

Post by Erwin Coumans » Fri Sep 18, 2009 12:03 am

IronSquare, sparkprime,

So you are hitting internal triangle edges between btCapsuleShape versus btBvhTriangleMeshShape? Or is is another shape? If so, please check if the btCapsuleShape works fine, sliding over the mesh when using setContactProcessingThreshold(0). I assume the collision margins are kept to a reasonable value (0.04 default), and not zero, right?

Can you check it with the updated Bullet 2.75 release, revision 1776?
Thanks,
Erwin

sparkprime
Posts: 508
Joined: Fri May 30, 2008 2:51 am
Location: Ossining, New York
Contact:

Re: Bumpy triangle meshes

Post by sparkprime » Sat Sep 19, 2009 7:19 am

For me I'm mostly worried about gimpact triangle meshes, convex hulls, and boxes. I seem to have no problem with spheres, haven't tried a capsule. I'll update bullet and try it when i get time. thanks

Post Reply