Simple and Efficient Approximate Convex Decomposition

Please don't post Bullet support questions here, use the above forums instead.
RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Simple and Efficient Approximate Convex Decomposition

Post by RBD »

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.
Attachments
ForkP_off.zip
(48.91 KiB) Downloaded 1007 times
khaled
Posts: 22
Joined: Mon May 02, 2011 3:26 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post by khaled »

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-hac ... onvex.html
http://kmamou.blogspot.ca/2012/11/v-hac ... ained.html

I am still working on finalizing the algorithm and cleaning/optimizing the code.
Flix
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post by Flix »

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:
fork1_vHACD.JPG
fork1_vHACD.JPG (39.85 KiB) Viewed 37712 times
This one was made with these params:

Code: Select all

				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:
fork_simpler_vHACD.JPG
fork_simpler_vHACD.JPG (41.99 KiB) Viewed 37712 times
was made with these params:

Code: Select all

		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)				
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Simple and Efficient Approximate Convex Decomposition

Post by Erwin Coumans »

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
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post by Flix »

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
Posts: 22
Joined: Mon May 02, 2011 3:26 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post by khaled »

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
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Simple and Efficient Approximate Convex Decomposition

Post by RBD »

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.
khaled
Posts: 22
Joined: Mon May 02, 2011 3:26 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post by khaled »

V-HACD V2.0 is here and it kicks ass. Check it out!
http://kmamou.blogspot.ca/2014/11/v-hac ... -here.html
RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Simple and Efficient Approximate Convex Decomposition

Post by RBD »

Thank you Khaled for the advanced V-HACD v2.0 and for the simple to understand (and use) Using the V-HACD library in your project post this morning!
(btw, little typo in main.cpp Usage: text: there is an extra parameter (resolution maxNumVoxels), thanks)

I understand the significant usefulness of non-overlapping convex pieces and the critical role V-HACD plays here, but would you still recommend HACD over V-HACD (2.0) when that is not a specific issue, or do you see V-HACD superseding HACD?

Perhaps I do not fully understand the V-HACD parameters still.
For example, a mesh with a main body and protrusions, like this simple gear (mesh attached below):
Image
HACD:
testHACD.exe gear.off 2 50 0 0 1 30 2000
gives very good results, in about 1 second:
Image
V-HACD v2.0 (low):
testVHACD.exe gear.off 1000000 20 0.001 4 4 0.05 0.05 0.0001 0 0 256 gears_CHs.wrl log.txt
gives, in about 25 seconds:
Image
To conform more it appears I mostly need to raise the voxel count, which also significantly increases the time required to process, or is there a better way?
V-HACD v2.0 (high):
testVHACD.exe gear.off 8000000 20 0.001 4 4 0.05 0.05 0.0001 0 0 256 gears_CHs_high.wrl log.txt
gives, in about 3 and a half minutes (and 19 convex-hulls):
Image
Thanks again for your time.

EDIT: BTW, nice results posted in that video at Newton Dynamics forum.
Attachments
gear_off.zip
Simple gear mesh example
(4.05 KiB) Downloaded 850 times
khaled
Posts: 22
Joined: Mon May 02, 2011 3:26 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post by khaled »

Hi RBD,
Thanks for sharing the snapshots/mesh and reporting the typo (I'v just fixed it).

I shared more decomposition results comparing V-HACD 2.0 to HACD here http://kmamou.blogspot.ca/2014/12/v-hac ... -hacd.html

Please, check it out and let me know what you think.
RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Simple and Efficient Approximate Convex Decomposition

Post by RBD »

Thanks for the nice visual results.

There are some meshes where HACD just doesn't work well and V-HACD can obviously handle quite well. So, with some meshes, V-HACD works where HACD doesn't, great work with that.
But for others... Correct me I'm wrong, but I get the feeling that V-HACD is very well suited when non-overlapping is important, or slow but more accurate with higher convex hull count is ok, or when more approximate, encapsulating convex decompositions are desired. Based on "Bird's" video over at Newton forums, it appears V-HACD can provide low convex hull count and ok performance using lower voxel counts at the cost of less form fitting hulls. But it seems that if more form fitting is required and keeping the convex hull count low is important, then perhaps HACD may be better suited (with certain meshes, of course) than V-HACD? It appears to me in your latest post that the convex hull count is often much greater with V-HACD, for example, when comparing meshes like hand_vhacd.png with hand_hacd.png, or bunny_vhacd.png with bunny_hacd.png.

To clarify what I'm focusing on: for real-time physics simulations, convex hull count and convex hull point count need to both be the lowest possible for maximum performance; and with Bullet 2.x physics engine, we also need to factor a collision margin; if we get convex hulls that are already larger than the original mesh, and add a collision margin, we are looking at large gaps between mesh collisions.

Having said all that, nice work on V-HACD. Merci Khaled.
khaled
Posts: 22
Joined: Mon May 02, 2011 3:26 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post by khaled »

Hi RBD,
Thanks for your feedback. It would be great if we could test both decompositions in real physics simulations and report the impact on performance. In the meanwhile, I have updated some of the results on http://kmamou.blogspot.ca/2014/12/v-hac ... -hacd.html to include the number of convex-hulls generated by both HACD and V-HACD (when I'll have more time I'll update the rest of the models). I have changed the V-HACD parameters to generate comparable number of convex-hulls with HACD.

I think that:
- V-HACD provides more consistent results, which is great if you have a large set of models you would like to decompose overnight.
- For some models, V-HACD provides significantly better results than HACD (e.g., army man)
- For the majority of the models, I think that V-HACD is competitive with HACD.
- For some models, HACD provides more accurate decompositions for the same number of convex-hulls (e.g., bunny)
RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Simple and Efficient Approximate Convex Decomposition

Post by RBD »

Good points and analysis, thanks Khaled.
Yes indeed, proper testing would be needed to determine the actual impact on physics simulation performance; my instincts may be that the physics engine generally works better with rounder rather than long(er) thin(er) convex hulls, but I can't be sure of this, especially in a compound context.
Flix
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post by Flix »

@khaled
Just three quick questions:
1) Are you going to explain the meaning of the V-HACD2 params in your blog ?
2) I might be wrong, but in my early tests on the old V-HACD library, it seemed to me that it returned concave shards (i.e. verts and inds of concave solids: even if of course I could simply pass the vertices to a btConvexHullShape to obtain the convex shape).
Now it seems that the vertices/indices returned by the new V-HACD2 are those of a convex shape.
Am I correct (or I was dreaming when I did my old tests) ?
3) About the new V-HACD2: it seems that the new algorithm has some kind of concept of "symmetry": the shards are more "ordered" and seem to follow some kind of symmetric pattern.
I was wondering if rotating the input shape in some way, processing it with V-HACD2 and re-rotating the output shards back can give different results. That would give us more options in the decomposition process (I personally would prefer less clusters on the horizontal plane whenever possible).

P.S. IMO the new library is the best decomposition library I've ever seen so far (thank you for making and sharing it :D!). The only problem is that HACD is still better on a performance/time basis, at least on my 4 cores CPU (I can use HACD at init time with low polygon meshes with no problem). So for me HACD will always be useful: V-HACD2 is something that would be more useful embedded in some kind of 3D editor.
khaled
Posts: 22
Joined: Mon May 02, 2011 3:26 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post by khaled »

Hi Flix,
Thanks for your feedback. Please, find below the answers to you questions/suggestions

1) This post describes the V-HACD 2.0 parameters http://kmamou.blogspot.ca/2014/12/v-hac ... ption.html
2) Yes. V-HACD provides only the convex-hulls.
3) Yes. In fact, one of the parameters (i.e., alpha) controls how much you should bias the decomposition cost to favor symmetric decompositions. A second parameter (i.e., beta) controls how much you should bias the decomposition cost to favor cutting along revolution axes.
4) If the PCA flag is turned off (which is the case by default), rotating the object may lead different decomposition results.
5) To reduce execution time, try reducing the resolution parameter from 1000000 to 100000 or even 10000 to get faster but less accurate decompositions. In general, I think that the convex decomposition stage should be done offline (if possible) and the result stored/loaded during run time.
6) I agree. it would be great if someone creates some plugins for V-HACD for easy integration with popular editors (i.e., Max, Maya...)
Last edited by khaled on Sat Dec 13, 2014 10:44 pm, edited 2 times in total.
Post Reply