Simple and Efficient Approximate Convex Decomposition

RBD · **Joined:** Tue Sep 16, 2008 11:31 am **Posts:** 118

Hi Khaled, HACD is working great, but I'm not sure I understand how to best deal with certain meshes. For example, for the attached fork mesh (I created, free to use), I can't seem to choose the right parameters so that the convex hulls conform to all of the fork's teeth all the time, even with low concavity (5 to 10); it seems I always get one hull that sticks out a little too much. It's not that serious an issue, it doesn't stick out that much, but I'd like to know what params I should have used to get them all to conform as close as possible (with the least number of hulls/faces, of course)?

ah… and you can ignore the LetterP, I was having issues with HACD always filling the hole; it appeared to get worse with the most recent source code, however it turns out it works perfect now when I do not use any extra/face points… (with earlier versions they were required for this mesh). So in this case I hadn't realized how things had changed. It's good now.

BTW, if you're interested, some simple Bullet Physics test animations where I used HACD:
Jars of jelly beans and concrete wall voronoi fracture test: Glass jars and Phymec letters were HACDed.
Noodle physics simulation test: Fork, bowl and glass were all HACDed.
Thanks.

khaled · **Joined:** Mon May 02, 2011 3:26 pm **Posts:** 14

Hi RBD

Please, could you try out the new V-HACD library http://code.google.com/p/v-hacd/

More details could be found here
http://kmamou.blogspot.ca/2012/11/v-hacd-hierarchical-approximate-convex.html
http://kmamou.blogspot.ca/2012/11/v-hacd-replacing-triangle-s-constrained.html

I am still working on finalizing the algorithm and cleaning/optimizing the code.

Flix · **Joined:** Tue Dec 25, 2007 1:06 pm **Posts:** 316

Nice work, Khaled!

I've just made a pair of experiments (on the "Bullet bunny" mesh) and the results look good.

I guess that vHACD could be used mainly when we want to separate parts of the original shape (maybe together with RBD's convex shatter algorithm to produce a bigger number of debris).

Or do you think that for generic convex decomposition it's better than the "original" HACD?

PS. in "hacdHACD.h" and "vhacdHACD.h":
#include <functional> is needed in VC++2012 for std::greater (VC++2010 was OK without it).

PS2. I'm almost sure that some time ago I managed to get a good decomposition of RBD's fork mesh with (a version of) the original HACD. However I didn't save it (or its decomposition parameters). RBD's post was written in April, but if he still needs it, I can try and see if I can do it again...
[Edit] Just tried the new vHACD with the fork mesh:

Attachment:

fork1_vHACD.JPG [ 39.85 KiB | Viewed 655 times ]

This one was made with these params:

Code:

            depth(10),                  //depth: maximum number of decomposition stages (type: integer, default: 10)
            maxConcavity(0.01f),      //maxConcavity: maximum allowed concavity (type: float, default 0.01)
            invertInputFaces(false),   //indicates whether mesh normals should be inverted or not (type: boolean, default 0)
            posSampling(10),         //posSampling: clipping plane position sampling resolution for coarse search (type: int, default 10)
            angleSampling(10),         //angleSampling: clipping plane orientation sampling resolution for coarse search (type: int, default 10) 
            posRefine(5),            //posRefine: clipping plane position sampling resolution for refined search (type: int, default 5) 
            angleRefine(5),            //angleRefine: clipping plane orientation sampling resolution for refined search (type: int, default 5)
            alpha(0.01),            //alpha: parameter controlling the compromise between concavity and balance between convex-hulls. (type: float, default: 0.01)
            targetNTrianglesDecimatedMesh(      0)

A simpler version (10 clusters) here:

Attachment:

fork_simpler_vHACD.JPG [ 41.99 KiB | Viewed 655 times ]

was made with these params:

Code:

      targetNTrianglesDecimatedMesh = 500;
      depth = 5;               //depth: maximum number of decomposition stages (type: integer, default: 10)
      maxConcavity =0.04f;      //maxConcavity: maximum allowed concavity (type: float, default 0.01)
      invertInputFaces = false;   //indicates whether mesh normals should be inverted or not (type: boolean, default 0)
      posSampling = 5;         //posSampling: clipping plane position sampling resolution for coarse search (type: int, default 10)
      angleSampling = 5;         //angleSampling: clipping plane orientation sampling resolution for coarse search (type: int, default 10) 
      posRefine = 3;            //posRefine: clipping plane position sampling resolution for refined search (type: int, default 5) 
      angleRefine = 3;         //angleRefine: clipping plane orientation sampling resolution for refined search (type: int, default 5)
      alpha = 0.04;            //alpha: parameter controlling the compromise between concavity and balance between convex-hulls. (type: float, default: 0.01)            

Erwin Coumans · **Posted:** Fri Nov 16, 2012 5:36 pm

Hi Flix, so does the fork mesh work fine with the new V-HACD?

Do you mind sharing the fork .obj file or .bullet file as zipped attachment to his issue?

Flix · **Joined:** Tue Dec 25, 2007 1:06 pm **Posts:** 316

Erwin Coumans wrote:

Hi Flix, so does the fork mesh work fine with the new V-HACD?
Do you mind sharing the fork .obj file or .bullet file as zipped attachment to his issue?

No problem about the fork mesh for me (it was posted as attachment two posts above by RBD, who was not satisfied with his HACD decomposition of this mesh). Khaled suggested him to try the new V-HACD, and I ... did it myself! (was curious about the new decomposition method).
So no problem on my side, V-HACD looks very promising, although I still have to understand if it produces better quality decomposition (i.e. less clusters) than HACD, so I can always replace HACD when the input mesh is manifold closed. Sorry for the misunderstanding...

khaled · **Joined:** Mon May 02, 2011 3:26 pm **Posts:** 14

Hi Flix
the V-HACD library is still under development. I think it is still too early to replace HACD. For now, I am trying to collect some feedback to understand the limitations of the algorithm.

--Khaled

RBD · **Joined:** Tue Sep 16, 2008 11:31 am **Posts:** 118

khaled wrote:

try out the new V-HACD library http://code.google.com/p/v-hacd/

Wow, nice, looks really promising! I can see the non-overlapping could have many more uses for it... fun stuff.
(I'll definitely play with it at some point, but I'm slow {just a hobby at home}.)

Thanks Flix for the test and sharing parameters.

Physics Simulation Forum

Simple and Efficient Approximate Convex Decomposition

Who is online