ConvexHull feature request

[Bird]

I use HACD to decompose a concave mesh into convex parts and assemble them into a single collision shape using NewtonCreateCompoundCollision. It works very well in most cases but when the concave mesh contains some flat surfaces, HACD will sometimes generate a hull that is 2 dimensional only. And so the call to NewtonCreateConvexHull returns NULL because the passed in points have no volume and collision detection at that point will fail during the simulation. My project supports Bullet and PhysX too and they both manage to handle the 2D case, so I'm hoping the Newton can handle it too if possible.

-Bird

[Sweenie]

Well, couldn't you extrude the flat surface(2D case) a bit to give it some volume?

[Bird]

Well, couldn't you extrude the flat surface(2D case) a bit to give it some volume?

You could if you knew that "a bit" wouldn't put collision geometry into a place where it shouldn't be.... but how can you know that without a lot of extra work?

-Bird

[JernejL]

What you ask for is purely a pre-processing step you should be doing in your tools pipeline.

[Julio Jerez]

Bird is right, the engine probably need to plane collision.
I will add it for core 300.

The reason I never put that in is that Newton collision system in not like the engine that use pure GJK algorithm or simple discreet collision par function as the bases of the collision system, Or like the ex employee engines that simple plagiarize older version of commercial engines and re write as open source.
Newton use his own proprietary steppes descend algorithm descend algorithm to find the closet distance in a Minkosky sum of two convex, the algorism is simple, faster and more robust that GJK, and it does not suffer from the singularity that you get when eth shape are at zero distance.

Newton also uses the GJK as a fallback solution when the numerical error of the steppes plane decend fail des to numerical precision.

the algorithm is this function here

Code: Select all

dgContactSolver::dgMinkReturnCode dgContactSolver::UpdateSeparatingPlane(dgMinkFace*& plane, const dgVector& origin)
{
   dgVector diff[4];
   dgVector aveg[4];

   plane = NULL;
   dgMinkFace* face = &m_simplex[0];
   dgMinkFace* lastDescendFace = NULL;
   dgMinkReturnCode code = dgMinkIntersecting;

   // this loop can calculate the closest point to the origin usually in 4 to 5 passes,
   dgInt32 j = 0;
   dgInt32 ciclingCount = -1;
   dgFloat32 minDist = dgFloat32 (1.0e20f);
   for (; face && (j < DG_UPDATE_SEPARATING_PLANE_MAX_ITERATION); j ++) {
      face = NULL;
      dgVector normal;
      // initialize distance to zero (very important)
      dgFloat32 maxDist = dgFloat32 (0.0f);
      for (dgInt32 i = 0; i < 4; i ++) {
         dgInt32 i0 = m_faceIndex[i][0];
         dgInt32 i1 = m_faceIndex[i][1];
         dgInt32 i2 = m_faceIndex[i][2];

         _ASSERTE (i0 == m_simplex[i].m_vertex[0]);
         _ASSERTE (i1 == m_simplex[i].m_vertex[1]);
         _ASSERTE (i2 == m_simplex[i].m_vertex[2]);

         const dgVector& p0 = m_hullVertex[i0];
         const dgVector& p1 = m_hullVertex[i1];
         const dgVector& p2 = m_hullVertex[i2];
         dgVector e0 (p1 - p0);
         dgVector e1 (p2 - p0);
         dgVector n (e0 * e1);

         dgFloat32 dist = n % n;
         if (dist > DG_DISTANCE_TOLERANCE_ZERO) {
            n = n.Scale (dgRsqrt (dist));
            dist = n % (origin - p0);

            // find the plane farther away from the origin
            if (dist > maxDist) {
               maxDist = dist;
               normal = n;
               face = &m_simplex[i];
            }
         }
      }


      // if we do not have a face at this point it means that the mink shape of the tow convexity face have a very
      // skew ratios on floating point accuracy is not enough to guarantee convexity of the shape
      if (face) {
         dgInt32 index = face->m_vertex[0];
         CalcSupportVertex (normal, 4);
         dgFloat32 dist = normal % (m_hullVertex[4] - m_hullVertex[index]);

         // if we are doing too many passes it means that it is a skew shape with big and small floats 
         // significant bits may be lost in dist calculation, increasing the tolerance help to resolve the problem
         if(dist < DG_UPDATE_SEPARATING_PLANE_DISTANCE_TOLERANCE1) {
            plane = face;
            code = dgMinkDisjoint;
            break;
         }


         if (dist < DG_DISTANCE_TOLERANCE) {
            dgInt32 i = 0;
            for (; i < 4; i ++ ) {
               dgVector error (m_hullVertex[i] - m_hullVertex[4]);
               if ((error % error) < (DG_DISTANCE_TOLERANCE * DG_DISTANCE_TOLERANCE)) {
                  plane = face;
                  //code = dgMinkDisjoint;
                  code = UpdateSeparatingPlaneFallbackSolution (plane, origin);
                  _ASSERTE ((code == dgMinkDisjoint) || ((code == dgMinkIntersecting) && (m_vertexIndex == 4)));
                  break;
               }
            }
            if (i < 4) {
               break;
            }
         }

         dgInt32 i0 = face->m_vertex[0];
         dgInt32 i1 = face->m_vertex[1];
         dgInt32 i2 = m_faceIndex[face - m_simplex][3];
         _ASSERTE (i2 != face->m_vertex[0]);
         _ASSERTE (i2 != face->m_vertex[1]);
         _ASSERTE (i2 != face->m_vertex[2]);
         Swap (m_hullVertex[i0], m_hullVertex[i1]);
         Swap (m_averVertex[i0], m_averVertex[i1]);
         m_hullVertex[i2] = m_hullVertex[4];
         m_averVertex[i2] = m_averVertex[4];
         if (!CheckTetrahedronVolume ()) {
            Swap (m_hullVertex[1], m_hullVertex[2]);
            Swap (m_averVertex[1], m_averVertex[2]);
            _ASSERTE (CheckTetrahedronVolume ());
         }
      }
   }

   if (j >= DG_UPDATE_SEPARATING_PLANE_MAX_ITERATION) {
      _ASSERTE (CheckTetrahedronVolume());
      code = UpdateSeparatingPlaneFallbackSolution (plane, origin);
   }
   return code;
}

Also thi salgorithn is much simpler, faster and robust that GJK, it does no deal with degenrate convex line a plane,ther is a test that check fo rteh intermediate subshape bing generated to have a volume
if (!CheckTetrahedronVolume ()) { ...

and then the sign of teh volume is use as teh decition to what diriction to take. If you ahev tow shapes tah are very thin, of a flat face that is colliong flat wih anoteh shape the is lon and also flat then teh volume of eh contact arear is zero and the algorith never temrinate.
a distance base algorih will no solve that probme either but the go around it but having a "skinthickess" as the minimum distance that teh collsion is valid.
for this reason I decided not to use plane collision, because eventually two plane collide flat and the algorith will simple fail.
Collsion with collision tree and heigh filed is OK because one of the tow collision shape isa simpel convex with non zero volume and threfore all posible permutation of tetrahedras also have non zero volume.

That is the bad news. The good news si that the single do have a polygon to polygon collision functions,
it is use extensivally in the collision tree collider every time the contacts are calculated, There is aslso a point collionde too that is use for closest distance calculation.

basically the polygon and the point colliders are private subshapes classes on the collision tree and the world, but for core 300,
I can make those legitimate shapes and when a convex hull happen to be a flat face, I can generate a convex flat plane instead and special case the Plane-Plane collision.

That should solve the problem.


on the how to detect i fteh fase are flat, teh converhull3d class does generate flat convex I just do no let it return that shape because in my opnion it dis no mak esence to produce a
shape that I new was going to fail later. but teh conve hull produces perfect hull for any set of point, even a single point. with will give a point,
for a tow point it iwll prduce a line, for three point it will produce a triangle, and for more points eieth a flat convex polygon or a regular hull.
I simple report the special cases as NULL.

another quick solution that can be use is to fake the hull. si what Sweenie sugested. Fake teh hull by giving it the thickess.
you can actually do that in your size very eassy.


if you look at the class dgConveHull3d, teh funtion that preproces the point cloud to produce the convex hull is this

Code: Select all

void dgConvexHull3d::BuildHull (const dgFloat64* const vertexCloud, dgInt32 strideInBytes, dgInt32 count, dgFloat64 distTol, dgInt32 maxVertexCount)
{
#if (defined (_WIN_32_VER) || defined (_WIN_64_VER))
   dgUnsigned32 controlWorld = dgControlFP (0xffffffff, 0);
   dgControlFP (_PC_53, _MCW_PC);
#endif

   dgInt32 treeCount = count / (DG_VERTEX_CLUMP_SIZE_3D>>1);
   if (treeCount < 4) {
      treeCount = 4;
   }
   treeCount *= 2;

   dgStack<dgHullVertex> points (count);
   dgStack<dgAABBPointTree3dClump> treePool (treeCount + 256);
   count = InitVertexArray(&points[0], vertexCloud, strideInBytes, count, &treePool[0], treePool.GetSizeInBytes());

   if (m_count >= 4) {
      CalculateConvexHull (&treePool[0], &points[0], count, distTol, maxVertexCount);
   }

#if (defined (_WIN_32_VER) || defined (_WIN_64_VER))
   dgControlFP (controlWorld, _MCW_PC);
#endif
}
 

this is the part part that does no buil teh hull is teh point cloud does no form a hull

count = InitVertexArray(&points[0], vertexCloud, strideInBytes, count, &treePool[0], treePool.GetSizeInBytes());

if (m_count >= 4) {
CalculateConvexHull (&treePool[0], &points[0], count, distTol, maxVertexCount);
}


bascially all you have to do is that is count is less that 4the it is becaus eth epoint are a plane, take any tree point form the original point cloud and make a plane equation.

the for each point in the original point cloud add an extra point that is equal to the point translated by alone teh direction of normal,
somethon

Code: Select all

if (m_count < 4)
   plane makeplane (points[0], points[1], points[2])
   stack<dgFloat64> tmp(count * 2 * stride);
   copy original points to tmp
  for each point in vertexCloud do
   vertexCloud[i + count] =   vertexCloud[i] + normal.scale (somethikness)

dgStack<dgAABBPointTree3dClump> treePool (treeCount + 256);
count = InitVertexArray(&points[0], tmp, strideInBytes, count, &treePool[0], treePool.GetSizeInBytes());
if (m_count >= 4) {
   CalculateConvexHull (&treePool[0], &points[0], count, distTol, maxVertexCount);
}

and that will make a conve hull of a thick plane, and should work as temporary solution.

[Julio Jerez]

if you are ok with the temp solution, until I add teh plane collision to core 300, I can make the modification to dgCollision convex Hull and check in so that you can continue the work.

[Bird]

if you are ok with the temp solution, until I add teh plane collision to core 300, I can make the modification to dgCollision convex Hull and check in so that you can continue the work.

Hehe, most of the math in your reply is way over my head but I'm very happy that it's not over yours.

Temp solution is fine. Thank you for adding plane collision support to Newton!

-bired

[Julio Jerez]

Ok I will add that new shape this weekend.

basically it will be a wraprr over the convex full, that will check if the hull fail, and if it fail because the point cloud form a flat plane,
it will calculate the plane of the cloud and extrude then by a specified thickness, and will call convex hull again with this new set of point, returning a convex full.

I will also add the ConvexPolygon class, taht will do basically the same.
this is a feature people ask some time because the like double face collision on decals. so that way they can add that withoput too much hazzel.


Thanks for repoting that shor comming, it was abpout time to fix that.

[Bird]

Great. Thanks very much!

I have 1 more request if it's not too difficult to do. My project is an artist's tool and I need to display the ConvexHull shape to provide visual feedback to the user. I noticed that when calling NewtonConvexHullGetFaceIndices, that some of the faces are ngons instead of just triangles. Is it possible for you to triple the ngons faces first using dgPolydedra::Triangulate(), so that we only have to deal with triangles when creating the ConvexHull display mesh?

-Bird

[Julio Jerez]

Ok bird, if you sync to SVN, the convex hull shape will automalically make a thin convex polygon, by extruding the face.

there is also a new collsion shape name convexPolygon, I am glad fix that for soem many people hwo liek to use tow side decals.

The cool thing is that it is possible to make an entire world of single conve faces by using the scene collision.
basically all the decal can be place in a scenm collision and there the do no have teh hover head of making then a full body.
I love this


for you it should simply works by creating conveHull

[Julio Jerez]

I have 1 more request if it's not too difficult to do. My project is an artist's tool and I need to display the ConvexHull shape to provide visual feedback to the user. I noticed that when calling NewtonConvexHullGetFaceIndices, that some of the faces are ngons instead of just triangles. Is it possible for you to triple the ngons faces first using dgPolydedra::Triangulate(), so that we only have to deal with triangles when creating the ConvexHull display mesh?
-Bird

I can not do that because it defeats the porpouse of making the most posible efficient shape for physics manipulation.
however you can do that on you side with a very simple function to fan every face you get in the call back, or on the index list
here is an exsample

Code: Select all

void DebugShowGeometryCollision (void* userData, int vertexCount, const dFloat* faceVertec, int id)
{
   dVector p0 (faceVertec[0 * 3 + 0], faceVertec[0 * 3 + 1], faceVertec[0 * 3 + 2]);
   dVector p1 (faceVertec[1 * 3 + 0], faceVertec[1 * 3 + 1], faceVertec[1 * 3 + 2]);
   for (int i = 2; i < vertexCount; i ++) {
      dVector p2 (faceVertec[i * 3 + 0], faceVertec[i * 3 + 1], faceVertec[i * 3 + 2]);
      drawface (p0, p1, p2);
      p1 = p2;
   }
}

The other way you can do that is by using the newton utility that is created for that kind of stuff, that is the NewtonMesh
the conve Hull use that to manipulate the mesh, you do no even have to make the collision shape, you can craete the Hull and manipulate it, then buidl teh final hull
these are some of teh funtion you cna use

Code: Select all

   NEWTON_API NewtonMesh* NewtonMeshCreate(const NewtonWorld* const newtonWorld);
   NEWTON_API NewtonMesh* NewtonMeshCreateFromMesh(const NewtonMesh* const mesh);
   NEWTON_API NewtonMesh* NewtonMeshCreateFromCollision(const NewtonCollision* const collision);
   NEWTON_API NewtonMesh* NewtonMeshConvexHull (const NewtonWorld* const newtonWorld, int count, const dFloat* const vertexCloud, int strideInBytes, dFloat tolerance);

   NEWTON_API void NewtonMeshPolygonize (const NewtonMesh* const mesh);
   NEWTON_API void NewtonMeshTriangulate (const NewtonMesh* const mesh);

plus a whole other bunch that you can use for that.

[Julio Jerez]

you know what is funny, the concave bug in HACD library and the solution is actually part of my contribution to the library.
I was the one who showed the concave bug in HACD and workred with him the solution to Khaled Mamou,
he had a provition for that but it was still failing when the convave face did not have any conetion to teh gloval mesh,
then after the he added some chnage and fix it but I never had the time to try after he fixed.
http://www.newtondynamics.com/forum/viewtopic.php?f=9&t=4607

I was suppost to work with him on spinding the algorithm, I had an impelnetation that is actually way faster, but I never complete because o fteh Convave Bug.
But I am glad he gave me permistion to use use as it and I do not have to write anything at all.

I supplied the Bowl model and a test base for him to expose the bug, so that he can implement the solution, because it was failling on those kind of model that are typical of Game.
I am very glad he fix it, because it was stopping me form completing the demo to show the integration of the library with Newton.
He gave me permission to distribute it with the SDK, so I am going to complete the convex decomposition demo using the NewtonMesh this week end, maybe that can help you see how handy the Newton Mesh is for that kind of stuff.

[Bird]

Ok bird, if you sync to SVN, the convex hull shape will automalically make a thin convex polygon, by extruding the fac

I tried on several meshes that were failing before and now they're all working perfectly. Thanks again for the quick fix!

The other way you can do that is by using the newton utility that is created for that kind of stuff, that is the NewtonMesh
the conve Hull use that to manipulate the mesh, you do no even have to make the collision shape, you can craete the Hull and manipulate it, then buidl teh final hull
these are some of teh funtion you cna use

Thanks, I'll give that a try.

I was suppost to work with him on spinding the algorithm, I had an impelnetation that is actually way faster, but I never complete because o fteh Convave Bug.
But I am glad he gave me permistion to use use as it and I do not have to write anything at all

It would be really great if you could find a way to speed it up ... I hope you can find the time to do it.

-Bird