Plug-In Request: Make Model BSP Compatible.

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.

Convexify Model by Anton_S.gif

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)

Convexify Heuristic on edge.gif

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:

Nasty Face for cloning.png

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.