_____Concave Objects with strange sheer force______

[Flix]

Just to say that I'm working on btHACDCompoundShape.h to update it and fix the striding issue dphil found.
I'll post it when it's ready and well tested.

As far as duplicated vertices are concerned, I found that HACD is robust enough, but a "clean mesh" results in less convex hulls (using the same params, approximately 1/10 less hulls in a very big "beetle car mesh" I found somewhere on the web long time ago). However I haven't tried the new version of the library (that apparently can merge closed submeshes and reduce the number of hulls, if my understanding is correct), so I don't know if this small "performance issue" still persists (BTW: I was coding a mesh decimator to be able to further reduce the number of clusters, I'm happy it's useless now...).

No matter, I will add an option to remove duplicated vertices and degenerate triangles directly in btHACDCompoundShape.h, if I manage to do it. But I will post it in a week or so, so be patient...

As far as decomposition speed is concerned, unluckily with big meshes, the decomposition is slower (as expected...). It took nearly 30 seconds on my system with that big car mesh. Hope that in Bullet it's possible to serialize/deserialize a single btCollisionShape to/from a single file (I still haven't tried it).


P.S. Hope ozmik solved his problem, it was not my intention to slightly hijack its thread.

[dphil]

By "striding issue" do you mean duplicated vertices? I got around the problem by just using the "removeDuplicateVertices" bool option (which automatically removes duplicates for me) in btTriangleMesh::addTriangle() when constructing it, and then I just pass that to btHACDCompoundShape. I'm not sure how efficiently it does it, but it seems more or less instantaneous, even for some large meshes I've tried - the real slowdown being the decomposition, of course (for example, a very convoluted 20,410 mesh I have takes about 1-2 minutes to decompose with average settings on a 2.66GHz quad core system). This combined with the connection distance param in the new HACD does well for the reduction in number of hulls.

I don't know if you want to build that into btHACDCompoundShape or not. Perhaps it is just up to the user to process their mesh if they want. If you do add it, maybe a bool option would be good so the user can specify if they want duplicates removed or not (no need for extra work if they already cleaned the mesh themselves). For the updated HACD library, I simply added:

Code: Select all

double connectDist;

to btHACDCompoundShape::Params, and

Code: Select all

myHACD.SetConnectDist(params.connectDist);

to its constructor.

On a side note, I also played around with turning off HACD's own convex hull generation and just grabbing the cluster points to use directly in btConvexHullShapes. This results in slightly faster decomposition, but a lot more convex hull points (so, probably slower collision processing). I also tried using the btShapeHull utility to reduce the hull supporting vertex count, but HACD still did a better reduction on average, so I scrapped all that and just went back to your original code.

And yes, not to hijack the thread from ozmik. However, decomposition into simple convex blocks could possibly resolve his issue.

[Flix]

By "striding issue" do you mean duplicated vertices?

No,no, the code I used to get vertices/triangles from the btStridingMeshInterface did not take the stride argument into account, and so it worked only with no "additional space" between adiacent vertices (a btVector3 array has a gap of 1 btScalar and so it needs to be fixed). That's why you needed to change the stride in the ctr of your btTriangleMesh class.

I got around the problem by just using the "removeDuplicateVertices" bool option (which automatically removes duplicates for me) in btTriangleMesh::addTriangle() when constructing it, and then I just pass that to btHACDCompoundShape. I'm not sure how efficiently it does it, but it seems more or less instantaneous, even for some large meshes I've tried

Well, I'm not too familiar with the btTriangleMesh class, I will check into it (currently I've got my own home-made code to get rid of duplicated vertices/degnerate triangles, that can be used to perform a very simple mesh decimation too, that can help to speed up the decomposition when I want very few convex hulls).

Usually I use the btTriangleIndexVertexArray directly on my "mesh class": this way I can use my "mesh class" to render the object (in all its rendering beauty, ), and the btTriangleIndexVertexArray for the physic part. The btTriangleMesh is probably more sutable for the Bullet Demos (it takes only vertices and indices,isn't it?).

Anyway removing duplicated vertices does improve the decomposition result in some cases, so I believe it should always be done (in one way or another).

...I don't know if you want to build that into btHACDCompoundShape or not...

Well, in my WIP version I have already nearly doubled the params... I'm adding everything I can (this will make testing more difficult), including the possibility to process only selected submeshes (the btStridingInterface supports more than one mesh), or to keep submeshes separate (to have different friction/restitution based on the original submesh index). All the extra stuff I'm adding can be excluded with extra params; so no problem for that, and in addition the ctr will take a const btStridingMeshInterface*, so that it's clear that I don't want to touch things that belongs to others.

On a side note, I also played around with turning off HACD's own convex hull generation and just grabbing the cluster points to use directly in btConvexHullShapes. This results in slightly faster decomposition, but a lot more convex hull points (so, probably slower collision processing). I also tried using the btShapeHull utility to reduce the hull supporting vertex count, but HACD still did a better reduction on average, so I scrapped all that and just went back to your original code.

Well, I must admit that I haven't completely understood what you mean here (where do you get the points of each cluster from without a decomposition algorithm?), but your conclusion is enough for me

Other things I would like to know:

1) At the moment of writing, we have 3 versions of HACD: the SVN repository made by Khaled (it uses STL), the one in the Bullet SVN (currently it's the same, just not updated... just a question of time I guess), the one modified by John Ratcliff (I still need to check it, but it does not use STL and it's problably "mixed" with some additional features, like mesh loaders and other interesting experiments...). Which version will be "supported" by the Bullet library? The fact that John's library doesn't use STL could make Bullet switch to it in the future... I'm interested in it, because btHACDCompoundShape.h should be in sync with the Bullet version of HACD.

2) Can the connectDist be set to, let's say, 100000, so that I can control the number of hulls using the concavity parameter only ? Will decomposition take longer? Is this value absolute of relative to the input mesh (Aabb) ?

3) I've seen there's a scale factor param in the library (it's a scalar, not a vector). What's it for ?

4) Does HACD preserve the original center of the input mesh or not ?

I need points 3 and 4 because I may want to add an optional bool param to center the mesh and maybe a vector to scale it in the future.

Happy coding to everybody And very sorry for this long post !

[khaled]

Hi Flex,
Here some answers to your questions:
1) No idea
2) You can do that but it will come with an extra overhead. What will be done is that every triangle in every connected component (CC) will have an edge connecting it to any other triangle in a different CC.
3) and 4) For scale factor have a look at this http://bulletphysics.org/Bullet/phpBB3/ ... hilit=hacd
The final result is however returned with respect to the original mesh position and sclae. The algorithm works as follows:
NormalizeData(); // center and scale the coordinates
// Compute decomposition
CreateGraph();
InitializeDualGraph();
InitializePriorityQueue();
Simplify();
//------------------------
DenormalizeData(); // inverse scale and shift to original position
ComputeFinalConvexHulls()

[Flix]

Thanks Khaled for your clarifications.

BTW: I found that it was my inner method: btHACDCompoundShape::GetStridingInterfaceContent(...) that created A LOT OF duplicated vertices! No wonder that I needed a method to remove them! (and still HACD worked well without removing them: only 1/10 of convex hulls were added!).
The bug was that that method didn't consider that in most cases (almost always) different subparts of the mesh reference the same vertex array (so a mesh with N shared vertices and 10 subparts resulted in 10xN duplicated vertices!). I will try to fix that too.

[Flix]

I've finally updated the file btHACDCompoundShape.h (in page 1), and made a demo showing its usage, here:http://bulletphysics.org/Bullet/phpBB3/ ... =17&t=7159.

[stephen.austin]

Hi, thanks for everyone's hard work on this.

I've been working on an integration with the btHACDCompoundShape, but before I make any changes, I want to understand why I'm getting the odd results (as shown in the attachment). I've tried changing several settings without any luck. Is this potentially an issue because of the nature of the mesh itself?

The attached image shows 2 concave objects, the one in the foreground depicts the btTriangleMesh that was passed to the btHACDCompoundShape constructor. The far object shows the HACD compound result (white wireframe indicates the physical mesh). As you can see, its not accurate at all.

Any ideas on where I might be going wrong?

Thanks,
Steve

[Flix]

Any ideas on where I might be going wrong?

No idea, your mesh seems very simple indeed (the test meshes I used in appHACDDemo are more complicated and they work!).

I would try the following:
1) Make sure the btStridingMeshInterface (i.e. the btTriangleMesh) you used is correct (you can try creating a btGImpactMeshShape or a btBvhTriangleMeshShape and see if it's OK).
2) By default the settings of btHACDCompoundShape are very conservative (i.e. low number of clusters for simple shapes). This is because with more complex meshes usually the main problem is to reduce the number of clusters, and not to increase it.
So I would try doing everything to maximize the number of clusters instead (this is just an example):

Code: Select all

params.nClusters = 12;
params.addExtraDistPoints = true;
params.addNeighboursDistPoints = true;
params.addFacesPoints = true;
params.concavity = 50.0;	

If these works, you can tune them better to optimize the resulting number of submeshes.

It's very strange... I thought params.nClusters = 3 was enough... but every mesh is different.
... maybe the dimensions of your mesh are not "standard"...

Just guessing.

[khaled]

Hi Stephan,
Please, could you share the input mesh in obj format ?

--Khaled

[stephen.austin]

Sorry for the incredibly long delay-
Using the latest update of the appHACDDemo, (instead of my own code) I attempted to decompose this object using default settings and got an interesting result. I'm not really sure why it is decomposing this way, but I've included a screenshot from appHACDDemo as well as a zip containing the original .obj.

Thanks for your help and hard work on this!
Steve