Plug-In Request: Make Model BSP Compatible.

[thomthom]

@anton_s said:

I implemented V-HACD 2.2 by Khaled Mamou, but don't find results as accurate as expected. The following image was generated with resolution of 100,000 - not accurate.

So glad I saw this thread - I wanted to see this tool in action within SketchUp!

[fredo6]

Interesting thread, but I don't quite catch the rationale.

Is this about cutting a solid into true convex solid, so a kind of spatial triangulation, which means that you have to figure out how to join faces to other faces?

I think it is possible to geometrically split the given geometry into blocks, but each individual block needs then to be closed to become a true solid.

For instance, on the picture below, the faces of the initial solid are split among 4 blocks. But each block is not a solid. That would require new geometry to make them solid.

Alternatively, one can think of spliiting the solid into base tetrahedrons, and then see if some terathedrons can be merged to still garantee convexity. But the result can be ugly (as any triangulation), because a natural decomposition may be nicer by creating new vertices on edges than to only rely on original vertices.

or maybe I missed something!!

Fredo

[Anton_S]

@thomothom
Yep! It was quite interesting for me to see this thing up an running too.

@fredo
Yes, this is about taking any solid and dividing it into convex groups. By saying dividing, I also mean adding faces at split locations to close the groups.

There is one thing that I think is required for convex decomposition process. It is required to divide each face into triangles. This can be easily done via SU Sketchup::Face.#mesh function, which returns a triangular mesh of the face. mesh.points and mesh.polygons from all faces is all the data the user will need to calculate the convex decomposition.

Then, having everything as triangles, one can develop an algorithm that splits this triangles into covex shapes. I already developed a 2D algorithm, but 3D one seems a quite more complex.

I will post a 2D exact convex decomposition plug once I get home.

[fredo6]

@Anton_S
Unfortunately, the Face.mesh method does not good visually nice result. I guess it is fast, but the result can be 'ugly'. I have on my roadmap to find a way to generate a nicer triangulation of faces. From there, it is relatively easy to split a face into convex portions, as below:

@ziiar
For the original problem of this thread, I have found a brute-force algorithm that does the job of cutting a solid into convex solids. The result may not be nice visually, even with some heuristics. Anyway, there is NO unique solution most of the time.

Here is a short video to illustrate

Fredo

[Anton_S]

Yes, face.mesh doesn't make a good mesh, but it does the job.
Here is my 2D algorithm demonstration:


Place in Plugins folder...

Your 3D convex hull decomposition is awesome! Unique results isn't a problem at all. What matters is that it works and I assume it generates very fast!

Once it is fully developed, you can share it to various physics engines, like Newton and Bullet, and they will implement it into their engine. I bet they are looking for an algorithm like that. All one will have to do is convert it to C++. And of course with your permission it could be added to my MSPhysics project, a free physics simulation that uses Newton Dynamics Physics SDK by Juleo Jerez.

[Anton_S]

Fredo, it would be nice to see how your 3D convex decomposition performs on these shapes:

convex decomposition.skp
Thanks

[fredo6]

Anton,

The algorithm works on your models. They were extremely useful because they helped me to detect a very nasty problem which I had to fight against for a few hours.

Actually the principle of the algorithm is quite simple (but the implementation is less straightforward)

Step 0: Split the selection into connected solids. This form the initial working list of solids

For each solid in the list

Step 1: Determine the concave edges (if none, then the solid is convex and go to next solid)

Step 2: Select one concave edge and take a cut plane (normally its bissector plane)

Step 3: Split the solid along this cut plane, giving 2 or more subsolids

Step 4: Put the sub-solids into the list of solids to treat

end

The heuristic is mainly about the selection of the concave edge for each solid and the best cut plane. For instance:

a) you would take first concave edges connected to other concave edges, and use the plane of these concave edges

b) then, if you find a guiding edge connected to the concave edge whose bissector plane is not too far from the bissector plane of the concave edge, then use this edge as a guide

c) for concave edges with an open angle (say > 140 degrees), the best is to take its bissector plane.

Here is an illustration of heuristic b). Obviously, with a proper triangulation and convexification of faces, these guiding edges can be computed automatically. I have done some work on it, but the 'nice' triangulation does not always work due to limitations of my algorithm (I used Delaunay triangulation and I have to implement a 'constrained' Delaunay triangulation)

I don't know too much why this convex decomposition is important in Physics engines. Are there limitation with some concave solids?

By the way, the nasty issue I was mentioning deals with copying faces when you have special cases like the one below:

The other difficulty of the algorithm is to intersect the solid and assign properly the faces which are located along the plane to the right side (this is where your models helped).

Fredo

[Anton_S]

These are some nice results!

I'm more of a visual person, and I don't quite understand these steps, especially step0. An animation would make things more clear for me, but it seems like it is a recursive concept; repeatedly dividing solids at special locations until they are convex.

In physics engines there is a simple way to calculate whether two convex solids intersect, i.e detect collision. When it comes to concave solids, things get more complex. Concave solids can only be static (tree or scene) collisions or be divided into convex solids and be a dynamic collision formed as compound - an array of convex solids glued together. Developers usually divide their solids into various convex shapes (manually or using VHACD) and then form them as compounds. Your algorithm would be very useful to divide solids into convex hulls automatically, just like VHACD, but with complete accuracy and good results.

I'm glad the models helped you improve your algorithm. I'll be glad to test it in various other cases once you release it.

Also, does it work with non-solids? And it does matter which side the face normal is point at, right?

[fredo6]

Anton,

Here is a short animation to illustrate the algorithm.

Also, I understand now the relation with Physics engines. The algorithm uses #intersect_with, so it has to create some geometry. However, it is easy to

• create the convex solids on a specific layer, so that you can easily associate each original solid to its convex decomposition
• Transform the convex decomposition in whatever data form suitable to the physics engine to manage collisions and delete the convex solids.

The algorithm should work on 'pseudo-solids' that is solids where all edges are bordered with 1 or 2 faces (but not more than 2)

The orientation of normals is important to detect concavity of edges. Here too, it is possible to give some flexibility based on solid topology.

Fredo

[Anton_S]

Very nice animation, Fredo!

For ziiars purpose, creating geometry is what he needs, but when implementing this to my physics engine, I would avoid creating any geometry and try computing all intersections in a function.
` # Get all convex hulls from mesh.

@param [Sketchup::Group] group

@return [Array<ArrayGeom::Point3d>] An array of convex hulls.

Each convex hull represents an array of points.

def get_convex_hulls(group)
#...
end`

Then, each of these convex hulls (an array of points) could be passed to a function in physics SDK to create convex collisions from them, as Newton Dynamics Physics SDK only asks for an array of points to create a convex hull.

Although, I'm not asking you to make it the way I requested. What I'll need is the peace of code that subdivides solid into convex hull. Then I could replace the intersect_with function with a custom function to avoid creating any geometry.

Good to know that it works with 'pseudo solids'. Will be useful.

Also, you could add 'max concavity angle' parameter to your algorithm to avoid sub-diving if angle between concave edges is greater than the 'max concavity angle'. I.E control generated 'resolution'.

[fredo6]

Anton,

I am afraid my implemnetation is fully based on Sketchup, not just for intersection, but for the topological relationships between edges, faces, etc....
I can adapt an API that can deliver the output as a hierachical matrix of points for groups and faces, leaving the model intact (either doing an abort_operation, or deleting all intermediary groups created).

But, if you plan to build it in C++, the best is to write a native version from the algorithm. As I said, it is fairly simple, and since you do not care with the esthetics of the decomposition, it can even be simpler. I can send you the details of algorithm, so that based on your C++ environment to describe the toplogy, you see how to adapt it to integrate with the Physics engine.

Fredo

[fredo6]

By the way, the algorithm happens to work on 'open solids', that is solids where edges are connected to 2 or 1 faces.

However, I am not sure the result is useful, as it gives potentially open solids too.

Fredo

[Anton_S]

Good! You can PM the code and I'll do my best in implementing it to C++.

[ziiar]

Hi, this all looks fantastic! Fredo, could you send me the plug-in or are you still working on it?

Thanks!

[fredo6]

@ziiar: I will publish in a few days. Actually, it needed some time to make the algorithm more robust.

Here is the Convexification of a complex model by Pilou. Not a lot of faces (672 faces), but a lot of concave edges (320) and not a true solid (there are some inner faces).

It took 20 seconds to compute, 40 seconds to Commit!

Here is the model
Convexify - Model by Pilou.skp

Fredo

[greenskp]

I am looking for that. Make a BSP file sometimes is a pain.
Anton and Fredo, keep doing a excellent work.

+1 for this awesome plugin.

[faust07]

So, I agree 100%. The implementation in Physics would be a big step. As a plugin to prepare concave models for physics it would be very useful.

[greenskp]

Sorry for this question but is there some news? Some progress? I am so excited about this plugin.