Approximate Convex Decomposition

A place to discuss everything related to Newton Dynamics.

Moderators: Sascha Willems, walaber

Re: Approximate Convex Decomposition

Postby Julio Jerez » Mon Nov 24, 2014 11:12 am

This
NewtonMeshApproximateConvexDecomposition (mesh, 0.01f, 0.2f, 256, 100, nullptr, nullptr);

set a limited to 256 convex shapes, after that the algorithm try to reduced the hierarchy until is formn the number of specified faces.

if you pass a large convex count say 512 or higher, then it will generate a better approximation for the same concavity.
The give a way is when you see same shape that closely approximate the feces they cover and some other with a large concavity errors.
Untitled.png
Untitled.png (253.11 KiB) Viewed 7387 times


try passing
NewtonMeshApproximateConvexDecomposition (mesh, 0.01f, 0.2f, 500, 100, nullptr, nullptr);

Maybe is will be good to add a function what their the result is the hierarchy, and the another function that will give to the number of faces,

This will let the user to make a slider what you can move up or down to the desired decomposition for the given concavity. do you think that will be useful?

all in all as you can see the quality are very similar, with newton's being a little faster, but Khaled generation a more elegant decomposition because of the splitting.

One good effect of Khale is that the solution has fewer seem to have fewer overlapping, and perhaps even fewer shapes because of the cutting, and that could be very useful.

I could add a preprocessing precutting stage base on the few first partitions. but in any case Khaled can be very useful.
Julio Jerez
Moderator
Moderator
 
Posts: 12426
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Approximate Convex Decomposition

Postby khaled » Mon Nov 24, 2014 3:41 pm

Thanks Bird for running the tests and sharing these comparative results!
Thanks Julio for the parameters recommendation.
Bird, I can see that you turned on PCA, which means that you played with the parameters . Did you get better results with PCA enabled?
Please, could you try running with the parameters suggested by Julio? Is it possible to report the number of convex hulls generated (ideally you would like to compare the decompositions generated with the same number of convex-hulls)?
For the army man, I suspect an issue with the input. Please, could you share the OBJ version of the file? You can also file an issue https://code.google.com/p/v-hacd/issues/list
Regarding V-HACD execution time, the code need be optimized once the algorithm is finalized. If you or Julio are interested, you are more than welcome to join the project and help me improve both the algorithm and the code.
khaled
 
Posts: 19
Joined: Sat May 07, 2011 8:57 am

Re: Approximate Convex Decomposition

Postby Julio Jerez » Mon Nov 24, 2014 4:14 pm

is PCA Principal Component Analysis?
is that what you are using to select a cutting plane?
The problem I have with cutting plane is that the are not local.
for example the first plane will slice the mesh in half. even If there are places that will turn into
disconnect section.
In the end if you do too many cuts, you will have to run a Regeneration phase.

That's the problem with Radcliff method, although he does not do PCA (if this is what you are doing)
instead he simply does a Variance minimization ignoring the Covariance.

But yes when using a cut plane, I think the result have fewer convexes, just because of the fact that a cut plane define a surface flat surface, therefore some part is already convex .

I still think that the best way to do this is but rung in two passes.

-First pass does a fine granularity convey decomposition.
-second pass rebuild a mesh by clipping the mesh again the convex array
-Now you have a solid representation of the mesh,

-the last pass run the Algerian by this time only a true monotone concave matrix
can be used because each cluster that you combine will have a smaller area that the sum of the part.

This is no the case when using perimeter the prime of two convened cluster can be larger that the parts, and make the metric unpredictable.

The matrix is like a stack market share plot, some of them have a trend but the trend is hard to predict.
Julio Jerez
Moderator
Moderator
 
Posts: 12426
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Approximate Convex Decomposition

Postby Julio Jerez » Mon Nov 24, 2014 4:22 pm

Bill, I think the army man model show the same problem I had with a Cessna model.

Basically the mesh is ill formed with few face that fold to themselves, it took my a long debugging section to determine that problem.

I bet you that if you render that model you will be some artifact preciselythy around the are where both algorithm are failing.
I even tried to make a mesh reconstruction, but that is no an easy thing to do oprecrurally.
Julio Jerez
Moderator
Moderator
 
Posts: 12426
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Approximate Convex Decomposition

Postby khaled » Mon Nov 24, 2014 7:05 pm

Hi Julio,
Yes, PCA is Principal Component Analysis. It is not used to select cutting planes. It is used only to align the mesh with its principal axes (i.e., make the results independent of the initial pose).

I agree with the fact that using clipping planes may results in unwanted cuts. A potential improvement my consist in trying to stitch back the unwanted cuts after every plane clip (see feature request I added https://code.google.com/p/v-hacd/issues/list). You can see that we reached to the same conclusion ;)

I still do not understand what is the problem if the cost function is not strictly monotone. Please, could you clarify?
khaled
 
Posts: 19
Joined: Sat May 07, 2011 8:57 am

Re: Approximate Convex Decomposition

Postby Bird » Tue Nov 25, 2014 11:28 am

Bird, I can see that you turned on PCA, which means that you played with the parameters . Did you get better results with PCA enabled?
Please, could you try running with the parameters suggested by Julio? Is it possible to report the number of convex hulls generated (ideally you would like to compare the decompositions generated with the same number of convex-hulls)?
For the army man, I suspect an issue with the input. Please, could you share the OBJ version of the file? You can also file an issue https://code.google.com/p/v-hacd/issues/list


Hi Khaled,

I don't have much time to experiment at the moment unfortunately. I took the settings from your test/main.cpp file. But I didn't use the ones in the "Usage:Recommended parameters" .... instead I inadvertently used the ones in the comments below and as result started trying HACD with 1,000,000 voxels instead of 1000,000 and thought the new version was really slow. :)

Anyway I experimented a little now with pca on/off and didn't see much difference in quality or number of parts generated or the time it took to generate them.

The models in the video HACD generated around 23-33 parts. Newton would mostly generate whatever the maxCount setting was so it was making 256 parts and then 512 later when I upped the maxCount parameter in NewtonMeshApproximateConvexDecomposition like Julio suggested

I took a look at the army man mesh in LightWave and could not find anything obviously wrong. LW's merge points tool did find some coplanar vertices though. If I export the model to OBJ format and re-load in LW both HACD and Newton have no problem with the mesh. I'm including it here in LWO format in case you want to take a look
Bird
 
Posts: 636
Joined: Tue Nov 22, 2011 1:27 am

Re: Approximate Convex Decomposition

Postby Bird » Tue Nov 25, 2014 11:49 am

NewtonMeshApproximateConvexDecomposition (mesh, 0.01f, 0.2f, 256, 100, nullptr, nullptr);
set a limited to 256 convex shapes, after that the algorithm try to reduced the hierarchy until is formn the number of specified faces.
if you pass a large convex count say 512 or higher, then it will generate a better approximation for the same concavity.
The give a way is when you see same shape that closely approximate the feces they cover and some other with a large concavity errors.


Hi Julio,

I added some gui so I can change the number of convex shapes but I didn't see any changes in the test I did. I tried to get Newton to make a better fit around the dragon's head/shoulder area.
http://hurleyworks.com/media/flash/MaxHulls/MaxHulls.html

The right cow used 256, the middle used 512 and the left used 2500 but the results are pretty much all the same

Maybe is will be good to add a function what their the result is the hierarchy, and the another function that will give to the number of faces,
This will let the user to make a slider what you can move up or down to the desired decomposition for the given concavity. do you think that will be useful?


Definitely useful but in my experience most users would never use it. They just want a "don't make me think" tool and would prefer general default settings that work well in most cases like I have now. :)

Bill, I think the army man model show the same problem I had with a Cessna model.
Basically the mesh is ill formed with few face that fold to themselves, it took my a long debugging section to determine that problem
.

Yes,I think you're right. I ran the MergePoints tool in LW and now it works fine in Newton and HACD

I have a model that sets off the dgPolyhedra::IsOkToCollapse assert. Do you know what would cause that?

-Bird
Bird
 
Posts: 636
Joined: Tue Nov 22, 2011 1:27 am

Re: Approximate Convex Decomposition

Postby Julio Jerez » Tue Nov 25, 2014 2:40 pm

Bird wrote:
Bill, I think the army man model show the same problem I had with a Cessna model.
Basically the mesh is ill formed with few face that fold to themselves, it took my a long debugging section to determine that problem
.

Yes,I think you're right. I ran the MergePoints tool in LW and now it works fine in Newton and HACD

I have a model that sets off the dgPolyhedra::IsOkToCollapse assert. Do you know what would cause that?
-Bird


Yes I was almost 85% sure that was the problem. but It surprised me that you did not fin render artifact and now I think I know why, my guess that the model have double faces.

By this I mean a face facing to the front and a face facing back. I have also found some public model that haves that problem. This does not imposes a problem for rendering because the face can only be seem from on side, however this create a big problem for any wing edge data structure.

This is a long weekend I will fix that because to me this is a problem with tool and I find unacceptable.

of the dragon model, all decomposition are unacceptable to me can I have the model for try this weekend. Maybe is time to revamp the decomposition tool.

this dgPolyhedra::IsOkToCollapse mean it found a face that if collapsed will generate a no manifold
maybe there are some bug that need to be fixed.
was that model loaded for OBJ formal? can you save as a OFF and see If the problem happens, and if so provide to me for testing. I do no have OBJ loader.
Julio Jerez
Moderator
Moderator
 
Posts: 12426
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Approximate Convex Decomposition

Postby khaled » Wed Nov 26, 2014 2:24 am

Thanks Bird for the results you shared.

Julio, as we discussed, I have added a merge stage to avoid over-segmentation. An updated version is available here http://code.google.com/p/v-hacd/

Enjoy the long weekend!
khaled
 
Posts: 19
Joined: Sat May 07, 2011 8:57 am

Re: Approximate Convex Decomposition

Postby Bird » Wed Nov 26, 2014 11:24 am

Thanks Bird for the results you shared.

No problem. Thanks for all your greate work on HACD!

One big advantage of Khaled's version is that the simulation runs much faster when the decomp mesh has fewer parts. In this sim the HACD version has only 13 pieces and Newton's version has 512.
http://hurleyworks.com/media/flash/DecompTest/DecompTest.html

all decomposition are unacceptable to me can I have the model for try this weekend


Great!, thanks for looking into it.

Here's a few models in OFF format including the dragon, army man, and the spider which was causing the dgPolyhedra::IsOkToCollapse assert. The bmw model was causing a hard crash in LW when using Newton's algorithm but HACD had no problems with it. I didn't have time to track down where the crash came from
http://hurleyworks.com/downloads/OFF_Meshes.zip

-Bird
Bird
 
Posts: 636
Joined: Tue Nov 22, 2011 1:27 am

Re: Approximate Convex Decomposition

Postby Julio Jerez » Wed Nov 26, 2014 12:27 pm

wow, that is a convincing demonstration that Khaled way of clipping plane yield a more useful result.

I still do no like the idea of clipping and regeneration, I believe there got to be a better way, I will try this weekend wit an idea I have base of voroiniid map as first decomposition.

that can be use to turn the algorithm into a top down concavity splitting rather than a bottom up method of combining clusters. I suspect that in the end it will have to be a combination of both.

But any way yes that Khaled method look pretty good, specially when I yield to fastest simulation which is the final goal.

If I do not come up with any decent solution them I will leave the way it is a m people can use Khaled.


Bill is the model that casuse the crash in the zip file? I like to see what is causing it first.


that simulation of all those head falling on the box was awesome, at first I thought what are all this boxes an them I see that the renderer could not keep up and display obbs.
Julio Jerez
Moderator
Moderator
 
Posts: 12426
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: Approximate Convex Decomposition

Postby Bird » Wed Nov 26, 2014 12:46 pm

Bill is the model that casuse the crash in the zip file? I like to see what is causing it first.


Yes, its the bmw model.

that simulation of all those head falling on the box was awesome, at first I thought what are all this boxes an them I see that the renderer could not keep up and display obbs.


Yeah, LW's renderer is amazingly fast these days but it still can't do real time global illumination on a gazillion triangles being animated. :)

-Bird
Bird
 
Posts: 636
Joined: Tue Nov 22, 2011 1:27 am

Re: Approximate Convex Decomposition

Postby Bird » Wed Nov 26, 2014 1:04 pm

Bill is the model that casuse the crash in the zip file? I like to see what is causing it first.


I just took a closer look and it was crashing because it hit the dgPolyhedra::IsOkToCollapse assert too.

Bird
Bird
 
Posts: 636
Joined: Tue Nov 22, 2011 1:27 am

Re: Approximate Convex Decomposition

Postby khaled » Thu Nov 27, 2014 10:48 am

Hi Bird,
Do you think adding a parameter to control the maximum number of vertices per convex-hull is a desired/important feature?
khaled
 
Posts: 19
Joined: Sat May 07, 2011 8:57 am

Re: Approximate Convex Decomposition

Postby Bird » Sat Dec 06, 2014 9:35 am

khaled wrote:Hi Bird,
Do you think adding a parameter to control the maximum number of vertices per convex-hull is a desired/important feature?


Hi Khaled,

Sorry I somehow missed this post. It might be nice to have but I don't think it's too critical since the defaults in HACD seem to work fine in all the meshes I've tried. I would say yes if the number of vertices has a big effect on hull generation time and the fidelity of resulting hull.

-Bird
Bird
 
Posts: 636
Joined: Tue Nov 22, 2011 1:27 am

PreviousNext

Return to General Discussion

Who is online

Users browsing this forum: No registered users and 1 guest