Approximate Convex Decomposition

[pHySiQuE]

I tried implementing VHACD in my editor. I have found that artists are VERY resistant to modeling physics geometry, and being able to auto-calculate it would be a huge advantage for us.

• VHACD is extremely slow. A model around 1000 polys takes several minutes to process.
• The user callback isn't called often enough, and makes the program go into "not responding" mode.
• The resulting shapes are too high-res. I'd like to get something a lot simpler and blockier.
• There are a lot of different parameters available, but I have no idea what they do. Is there an explanation somewhere? These are the parameters I am using:
  

  Code: Select all

        std::vector<Surface*> Build(Surface* surface, int usercallback(float)=NULL, int resolution = 1000000, int depth = 20, float concavity = 0.0001, int planeDownsampling = 4, int convexhullDownsampling = 4, float alpha = 0.05, float beta = 0.05, float gamma = 0.0001, int pca = 0, int mode = 0, int maxNumVerticesPerCH = 256);

This would be a huge advantage for us, if it can be made really useful, but there are some challenges to overcome.

Image1.jpg (48.77 KiB) Viewed 8011 times

[Bird]

std::vector<Surface*> Build(Surface* surface, int usercallback(float)=NULL, int resolution = 1000000, int depth = 20, float concavity = 0.0001, int planeDownsampling = 4, int convexhullDownsampling = 4, float alpha = 0.05, float beta = 0.05, float gamma = 0.0001, int pca = 0, int mode = 0, int maxNumVerticesPerCH = 256);

I think you did the same thing I did at first and copied the example settings that have default voxel count(resolution) at one million.

Try one hundred thousand instead. I think that's what Khaled intended to write.

-Bird

[khaled]

Thanks pHySiQuE for the feedback.

pHySiQuE, please, why don't you compute the convex decompositions offline (run overnight)? I mean, allow a better quality (e.g. resolution = 8,000,000) at the cost of a higher computation time?

As Bird suggested, to reduce the execution time just set the resolution parameter to 100,000 (i.e., the lower the resolution, the lower the execution time).

To generate less parts increase both the concavity and gamma parameter (e.g., concavity=0.0025 and gamma=0.00125).

To reduce the number of triangles per convex-hull, reduce maxNumVerticesPerCH parameter (e.g., maxNumVerticesPerCH = 64).

A detailed description of the V-HACD parameters please, check this link
http://kmamou.blogspot.ca/2014/12/v-hac ... ption.html

An example of Blender Add-on for V-HACD was made available by Alain Ducharme
http://kmamou.blogspot.ca/2014/12/v-hac ... harme.html

[pHySiQuE]

I'm actually getting very good results now with the following parameters:

resolution: 1000
depth: 10
max verts per hull: 24

It only takes a few seconds and the results are far better than any algorithm I've seen in the past.

[khaled]

Glad to hear that!

[pHySiQuE]

I've already got it implemented in our beta build. You can read about it in detail here:
http://www.leadwerks.com/werkspace/blog ... de-useful/

Thank you.

[khaled]

@pHySiQuE An updated version of the library is available. The main changes:
- Increase update frequency
- Add parameter to adaptively sub-sample the generated convex-hulls http://kmamou.blogspot.ca/2014/12/v-hac ... pling.html

[pHySiQuE]

The new setting is integrated in the build going up tonight. You need to opt in to the beta branch to get it:
http://www.leadwerks.com/werkspace/topi ... -in-steam/

[AntonSynytsia]

I don't know if this thread is active anymore, but I need help implementing V-HACD2.

I got it into my project, but still don't understand how the points and triangles parameters should be organized.

Current Status:
I have a mesh. Each mesh is an array of triangles. I iterate through all triangles. Then, I iterate through points of each triangle, and push point x,y,z values into the points queue. This is like flattening the whole mesh.

What I don't get is what is the 'triangles' parameter for in the Compute function?

This is my first time implementing V-HACD.

Nevermind, I figured it out. The triangles represent the order in which the points are connected. In my case, it would be an array of accending numbers from 0 to the number of points.

[khaled]

A new/faster version of V-HACD is available. Check the following link for details http://kmamou.blogspot.ca/2015/01/openc ... -hacd.html

@AntonSynytsia sorry I missed your message.

[AntonSynytsia]

Thank you for the new update Sir Khaled!

[AntonSynytsia]

I just figured that the actual generated convexhulls have a thickness of ~0.25 units. Is it possible to customize the thickness as that parameter?

[khaled]

@AntonSynytsia Please, how you define thickness?

[AntonSynytsia]

The convex decomposition for my 30x30x30 cube has the final results as 30.664x30.664x30.664. I might be doing something wrong there.

Here are the points and triangles I pass:
[[30.0, 30.0, 0.0],
[0.0, 0.0, 0.0],
[0.0, 30.0, 0.0],
[30.0, 0.0, 0.0],
[30.0, 0.0, 30.0],
[0.0, 0.0, 30.0],
[30.0, 30.0, 30.0],
[0.0, 30.0, 30.0]]

[[0, 1, 2],
[1, 0, 3],
[4, 1, 3],
[1, 4, 5],
[0, 4, 3],
[4, 0, 6],
[7, 0, 2],
[0, 7, 6],
[7, 1, 5],
[1, 7, 2],
[4, 7, 5],
[7, 4, 6]]

Here are final faces I get:
[
[[30.333335876464844, 30.33333396911621, -0.33333396911621094],
[30.333335876464844, -0.33333396911621094, 30.33333396911621],
[30.333335876464844, -0.33333396911621094, -0.33333396911621094]],

[[30.333335876464844, 30.33333396911621, 30.33333396911621],
[-0.33104991912841797, 30.33333396911621, 30.33333396911621],
[30.333335876464844, -0.33333396911621094, 30.33333396911621]],

[[-0.33104991912841797, 30.33333396911621, 30.33333396911621],
[30.333335876464844, 30.33333396911621, 30.33333396911621],
[30.333335876464844, 30.33333396911621, -0.33333396911621094]],

[[30.333335876464844, 30.33333396911621, 30.33333396911621],
[30.333335876464844, -0.33333396911621094, 30.33333396911621],
[30.333335876464844, 30.33333396911621, -0.33333396911621094]],

[[-0.33104991912841797, -0.33333396911621094, -0.33333396911621094],
[-0.33104991912841797, 30.33333396911621, 30.33333396911621],
[-0.33104991912841797, 30.33333396911621, -0.33333396911621094]],

[[30.333335876464844, 30.33333396911621, -0.33333396911621094],
[-0.33104991912841797, -0.33333396911621094, -0.33333396911621094],
[-0.33104991912841797, 30.33333396911621, -0.33333396911621094]],

[[-0.33104991912841797, 30.33333396911621, 30.33333396911621],
[30.333335876464844, 30.33333396911621, -0.33333396911621094],
[-0.33104991912841797, 30.33333396911621, -0.33333396911621094]],

[[-0.33104991912841797, 30.33333396911621, 30.33333396911621],
[-0.33104991912841797, -0.33333396911621094, -0.33333396911621094],
[-0.33104991912841797, -0.33333396911621094, 30.33333396911621]],

[[30.333335876464844, -0.33333396911621094, 30.33333396911621],
[-0.33104991912841797, 30.33333396911621, 30.33333396911621],
[-0.33104991912841797, -0.33333396911621094, 30.33333396911621]],

[[-0.33104991912841797, -0.33333396911621094, -0.33333396911621094],
[30.333335876464844, -0.33333396911621094, 30.33333396911621],
[-0.33104991912841797, -0.33333396911621094, 30.33333396911621]],

[[30.333335876464844, -0.33333396911621094, 30.33333396911621],
[-0.33104991912841797, -0.33333396911621094, -0.33333396911621094],
[30.333335876464844, -0.33333396911621094, -0.33333396911621094]],

[[-0.33104991912841797, -0.33333396911621094, -0.33333396911621094],
[30.333335876464844, 30.33333396911621, -0.33333396911621094],
[30.333335876464844, -0.33333396911621094, -0.33333396911621094]]
]

Here are generation params:
resolution: 100000
depth: 20
concavity: 0.001
plane_down_sampling: 4
convex_hull_down_sampling: 4
alpha: 0.05
beta: 0.05
gamma: 0.005
pca: 1
mode: 0
max_num_vertices_per_ch: 64
min_volume_per_ch: 0.0001

Maybe its caused by some float precision thingy, but I don't think so.

[AntonSynytsia]

Oh, increasing resolution to 8000000 makes it more accurate. I guess I answered my own question.