Convex Decomposition

[carli2]

Hi,

We have various complex meshes, for instance the cabin of the elevator. (if you ask for a pic, I can make one)
The problem is: they player should go into that object, so a convex shape is not enough - we need convex decomposition.

Is NewtonMeshApproximateConvexDecomposition doing such things I need? The output of that function is a NewtonMesh, but what I need is a array of pointclouds whose convex hulls in a compound collision become the object's shape.
Does Newton3 already provide this kind of convex decomposition or should I use a third party library for that task? (convex decomposition should be preprocessed for each model)

[Julio Jerez]

There are few funtion you can try

The first step is to make a NetwonMesh out of your cabin

for that you cna look at demo UsingNewtonMeshTool.cpp,
you cn amake newton mesh by passing faces, or vertex lis index list of faces.

The afte you have teh mesh you can call
NewtonMesh* NewtonMeshApproximateConvexDecomposition (const NewtonMesh* const mesh, dFloat maxConcavity, dFloat backFaceDistanceFactor, int maxCount, int maxVertexPerHull, NewtonReportProgress reportPrograssCallback)

which make a new convex mesh, in wich each mesh sgsment is a convex hull.

then you cal call

NewtonCollision* const compound = NewtonCreateCompoundCollisionFromMesh (world, convexApproximation, 0.001f, 0, 0);

which make a compound collision from a mesh, bascially i read teh vertices if each sub mesh on the imput mesh and create a convex hull.
the you can simple use tah compound collsion and destroy the auxiliay meshes.
check demo ConvexApproximation.cpp

The convex decomposition in Newton is the most advance, most acurate and fastest algorith out there.
3d studio max uses the the Newton Version in their tool set, there are also some comercial physic and Game engines that are using as replacement for some of the public version out there.

[Julio Jerez]

Oh, I just remember that I Commented out , part fio teh code when I was working of teh boolan funtions.

Bascially teh code was using a collsion tree for utility bu that was casing some problemstne becauise collsion tree are designed for high performance queries, and teh do no allow for removeing and adding faces.
I added that funtionality to teh NewtonMesh but I fortget to uncomment the code, and refactor it so that is uses ther new queries assesor.
I can go, over it tonight and re enables it. It is a very minor update.

if you sinc I enable the decompostion of a L shape mesh, that one is simple enough that it passes wouth errors, but enough for you to see how it works.
I will fix the rest tonight.

[carli2]

The format for loading the physics shapes into newton is either

a) a convex hull with a list of vertices, or
b) a array of (a)

So a decomposed shape is then (b).
What exactly do you mean by "segments" of a mesh? I want to create a tool that loads a model into a newton mesh, then decomposes and outputs (b). So how do I access the "segments" of the mesh?

[Julio Jerez]

please look at demo ConvexApproximation.cpp
it does what you say.
I convert a NewtonMesh int a compound collision.

If you wnat the vertex for each individual convex you can get them foprm teh mesh directly or form each indididual convex hull

this is teh funtion that make a compound collsion form a NetwonMesh

Code: Select all

NewtonCollision* NewtonCreateCompoundCollisionFromMesh (const NewtonWorld* const newtonWorld, const NewtonMesh* const convexAproximation, dFloat hullTolerance, int shapeID, int subShapeID)
{
   TRACE_FUNCTION(__FUNCTION__);
   NewtonCollision* const compound = NewtonCreateCompoundCollision(newtonWorld, shapeID);
   NewtonCompoundCollisionBeginAddRemove(compound);

   NewtonMesh* nextSegment = NULL;
   for (NewtonMesh* segment = NewtonMeshCreateFirstSingleSegment (convexAproximation); segment; segment = nextSegment) {
      nextSegment = NewtonMeshCreateNextSingleSegment (convexAproximation, segment);

      NewtonCollision* const convexHull = NewtonCreateConvexHullFromMesh (newtonWorld, segment, 0.01f, subShapeID);
      if (convexHull) {
         NewtonCompoundCollisionAddSubCollision (compound, convexHull);
         NewtonDestroyCollision(convexHull);
      }
      NewtonMeshDestroy(segment);
   }

   NewtonCompoundCollisionEndAddRemove(compound);

   return compound;
}

it simple iterate ove teh numbe of sub menesh creation a Mewsh for each sub mesh and then making a conve hull out of it.
you can ge teh verte array instead.
This is very simple, teh NewtonMesh is very usful for that kind of stuff

[Julio Jerez]

Ok I made the change, now the convex decomposition is wroking again using the version of collision tree of core 300.
Please sink to SVN, check it out and see if it work for you.

give it a try you will see in not as fificult as you think, in fact NewtonMesh is quite useful.

if you give me one or the model that you wan to decompose, I can add to the demo so you can see the quality of the decompsosition.

[carli2]

okay, I'll give it a try. I will tell you as soon as I built it (maybe this weekend)

[carli2]

I implemented it as proposed and get the following crash:

Code: Select all

Program received signal SIGSEGV, Segmentation fault.
CollapseClusters (maxClustesCount=<optimized out>, maxConcavity___=<optimized out>, mesh=..., this=<optimized out>)
    at ../../source/meshUtil/dgMeshEffect3.cpp:1360
1360         tree->ReduceByCount (maxClustesCount, approximation);
(gdb) backtrace
#0  CollapseClusters (maxClustesCount=<optimized out>, maxConcavity___=<optimized out>, mesh=..., this=<optimized out>)
    at ../../source/meshUtil/dgMeshEffect3.cpp:1360
#1  dgMeshEffect::CreateConvexApproximation (this=<optimized out>, maxConcavity=<optimized out>, backFaceDistanceFactor=0.200000003,
    maxHullsCount=<optimized out>, maxVertexPerHull=100, reportProgressCallback=<optimized out>) at ../../source/meshUtil/dgMeshEffect3.cpp:1444
#2  0x0000000000557487 in DECOMPOSE (this=0x1170d00) at convexdecomposition.pas:235
#3  0x000000000114d800 in ?? ()
#4  0x0000000000000000 in ?? ()


The code is the following:

Code: Select all

procedure TDecompositor.Decompose;
type TdVec3 = array[0..2] of double;
     PdVec3 = ^TdVec3;
var hmesh: PNewtonMesh;
    segment, nextsegment: PNewtonMesh;
    v: TdVec3;
    i, p: integer;
begin
  NewtonMeshEndFace(newtonmesh);
  hmesh:=NewtonMeshApproximateConvexDecomposition(newtonmesh, 0.01, 0.2, 32, 100, nil);
  NewtonMeshBeginFace(newtonmesh);

  // hmesh in hulls übernehmen
  SetLength(hulls, 0);
  segment:=NewtonMeshCreateFirstSingleSegment(hmesh);
  while segment<>nil do begin
    nextsegment:=NewtonMeshCreateNextSingleSegment(hmesh, segment);
    // Hülle aus segment extrahieren
    SetLength(hulls, length(hulls)+1);
    for i:=NewtonMeshGetVertexCount(segment)-1 downto 0 do begin
      v:=PdVec3(NewtonMeshGetVertexArray(segment)+i*NewtonMeshGetVertexStrideInByte(segment))^;
      p:=getpoint(SetVector(v[0], v[1], v[2]));
      SetLength(hulls[high(hulls)], length(hulls[high(hulls)])+1);
      hulls[high(hulls)][high(hulls[high(hulls)])]:=p;
    end;
    NewtonMeshDestroy(segment);
    segment:=nextsegment;
  end;
end;


This also occurs when I do not have any faces added to the mesh, so the problem does not seem to be in my application.

[Julio Jerez]

can I have a test for debugging?

[carli2]

I wrote a minimal test example

Code: Select all

#include "Newton.h"

int main(int argc, char **argv) {
   NewtonWorld *world = NewtonCreate();
   NewtonMesh *mesh = NewtonMeshCreate(world);
   NewtonMesh *dec = NewtonMeshApproximateConvexDecomposition(mesh, 0.01, 0.2, 32, 100, 0);
   return 0;
}

[Julio Jerez]

That was the crash? Are you making conve of meshe with zero faces?

bascially that will try to make a mesh with no faces at all, trhe teh mesh toll handel that by the conve decompsition fition had a bug that assume ther will be at least one face.
I fixed and sodul no crash anymore.

however i think the error most be somethong different than that.
please Try again the empty mesh, most importat try a non trivial mesh and see how it works.

[carli2]

Okay, the empty mesh works now.

I inserted a more complex mesh and got the following: (this mesh had a volume)

Code: Select all

Program received signal SIGSEGV, Segmentation fault.
dgAABBTree::BuildTree (this=<optimized out>, root=0x117244c,
    boxArray=0x1171c40, boxCopy=0x120c4c0, vertexArrayOut=0x11d6a80,
    treeVCount=@0x7fffffffa328: 1089)
    at ../../source/core/dgAABBPolygonSoup.cpp:174
174            if (node->m_boxIndex != -1) {
(gdb) backtrace
#0  dgAABBTree::BuildTree (this=<optimized out>, root=0x117244c,
    boxArray=0x1171c40, boxCopy=0x120c4c0, vertexArrayOut=0x11d6a80,
    treeVCount=@0x7fffffffa328: 1089)
    at ../../source/core/dgAABBPolygonSoup.cpp:174
#1  0x00007ffff4df382c in BuildTopDown (optimizedBuild=true,
    treeVCount=@0x7fffffffa328: 1089, vertexArrayOut=0x1228840,
    boxArray=0x1171c40, boxCount=<optimized out>, allocator=0x114be80,
    this=0x1171c40) at ../../source/core/dgAABBPolygonSoup.cpp:597
#2  dgAABBPolygonSoup::Create (this=0x7fffffffb888, builder=...,
    optimizedBuild=<optimized out>)
    at ../../source/core/dgAABBPolygonSoup.cpp:1646
#3  0x00007ffff4efa1e7 in dgHACDClusterGraph::dgHACDClusterGraph (
    this=0x7fffffffb860, mesh=..., backFaceDistanceFactor=0.200000003,
    reportProgressCallback=<optimized out>)
    at ../../source/meshUtil/dgMeshEffect3.cpp:738
#4  0x00007ffff4ef2395 in dgMeshEffect::CreateConvexApproximation (
    this=0x1159200, maxConcavity=<optimized out>,
    backFaceDistanceFactor=0.200000003, maxHullsCount=<optimized out>,
    maxVertexPerHull=100, reportProgressCallback=0)
    at ../../source/meshUtil/dgMeshEffect3.cpp:1437
#5  0x0000000000557433 in DECOMPOSE (this=0x7ffff7e040c0)
    at ../convexdecomposition.pas:235

With an other model, it did not crash, but got lots of zero-vectors [0, 0, 0]. (the model was flat, I extract the vertices with NewtonMeshGetVertexArray iterating through the mesh segments)
Calling NewtonRemoveUnusedVertices(hmesh, nil); does not help. There are also some +Inf values in there. (but I think that's caused by the flat shape)

[Julio Jerez]

was do you expect from of a flat mesh? I do not know what should be the result of that.

The engine does not handle flat plane as convex hull, if a point cloud happens to form a flat plane, the convex hull returns NULL.

can you try a conventional mesh first, before you go to the complex ones?

[carli2]

was do you expect from of a flat mesh? I do not know what should be the result of that.

No mesh. 0 vertices.

The engine does not handle flat plane as convex hull, if a point cloud happens to form a flat plane, the convex hull returns NULL.

can you try a conventional mesh first, before you go to the complex ones?

That's what I tried first, but I got the following crash:

Code: Select all

    Program received signal SIGSEGV, Segmentation fault.
    dgAABBTree::BuildTree (this=<optimized out>, root=0x117244c,
        boxArray=0x1171c40, boxCopy=0x120c4c0, vertexArrayOut=0x11d6a80,
        treeVCount=@0x7fffffffa328: 1089)
        at ../../source/core/dgAABBPolygonSoup.cpp:174
    174            if (node->m_boxIndex != -1) {
    (gdb) backtrace
    #0  dgAABBTree::BuildTree (this=<optimized out>, root=0x117244c,
        boxArray=0x1171c40, boxCopy=0x120c4c0, vertexArrayOut=0x11d6a80,
        treeVCount=@0x7fffffffa328: 1089)
        at ../../source/core/dgAABBPolygonSoup.cpp:174
    #1  0x00007ffff4df382c in BuildTopDown (optimizedBuild=true,
        treeVCount=@0x7fffffffa328: 1089, vertexArrayOut=0x1228840,
        boxArray=0x1171c40, boxCount=<optimized out>, allocator=0x114be80,
        this=0x1171c40) at ../../source/core/dgAABBPolygonSoup.cpp:597
    #2  dgAABBPolygonSoup::Create (this=0x7fffffffb888, builder=...,
        optimizedBuild=<optimized out>)
        at ../../source/core/dgAABBPolygonSoup.cpp:1646
    #3  0x00007ffff4efa1e7 in dgHACDClusterGraph::dgHACDClusterGraph (
        this=0x7fffffffb860, mesh=..., backFaceDistanceFactor=0.200000003,
        reportProgressCallback=<optimized out>)
        at ../../source/meshUtil/dgMeshEffect3.cpp:738
    #4  0x00007ffff4ef2395 in dgMeshEffect::CreateConvexApproximation (
        this=0x1159200, maxConcavity=<optimized out>,
        backFaceDistanceFactor=0.200000003, maxHullsCount=<optimized out>,
        maxVertexPerHull=100, reportProgressCallback=0)
        at ../../source/meshUtil/dgMeshEffect3.cpp:1437
    #5  0x0000000000557433 in DECOMPOSE (this=0x7ffff7e040c0)
        at ../convexdecomposition.pas:235

[Julio Jerez]

make the making teh test tah reproduce that bug, It is hard for me to see from a listing.

the plece I see teh grack indicate that the imput data is no correct, because it is rare that collision tree crashe with correct data.

list the vertex and faces as you past the to the mesh so that I can reproduce it.