Random plane cut

[sabotage3d]

Hello ,

Is it currently possible to do random plane cut using only the meshCut function and randomly generated planes ? Do I have to run recursively the meshCut function to get this effect ?

[joesfer]

Yes - if you check how the resulting mesh cells are generated, the process is nothing but cutting the source mesh with a plane matching one of the cell walls and then feed the result of that to the same cutter with the next plane. this is am iterative rather than recursive process. Mind you this works because the voronoi cells we extract the planes from are guaranteed to be convex. But you can indeed feed any arbitrary plane to meshCut. On 13 Dec 2014 16:29, "sabotage3d" notifications@github.com wrote:

Hello ,

Is it currently possible to do random plane cut using only the meshCut function and randomly generated planes ? Do I have to run recursively the meshCut function to get this effect ?

[image: screen shot 2014-12-13 at 16 23 52] https://cloud.githubusercontent.com/assets/4654347/5424390/fddba04c-82e4-11e4-87ef-a3e530024003.png [image: screen shot 2014-12-13 at 16 23 58] https://cloud.githubusercontent.com/assets/4654347/5424391/02f611c0-82e5-11e4-9715-b85c32cb473f.png

— Reply to this email directly or view it on GitHub https://github.com/joesfer/Voronoi-Shattering/issues/4.

[sabotage3d]

I am a bit confused as the code is quite complex. I am trying a simpler case like this. But I am getting is different pieces cut only by one plane. Do you happen to have simpler example it could be pseudo code to understand the concept ? This is what I have so far :

Plane plane1,plane2,plane3,plane4;
LIST(Plane) planes;
plane1.setPlane(0, -0.054, 0.998, -0.270);
plane2.setPlane(0.10, 8.742, -0.994, -0.334);
plane3.setPlane(0, -0.999, -0.0174, -0.2999);
plane4.setPlane(0.1391, 0.990, -4.3711, -0.2970);
planes.append(plane1);
planes.append(plane2);
planes.append(plane3);
planes.append(plane4);

struct MyVertex
{
    float x, y, z, w;
};

MyVertex myvertices[8] = {
    {-0.5, -0.5,  0.5, 1 },
    { 0.5, -0.5,  0.5, 1 },
    {-0.5,  0.5,  0.5, 1 },
    { 0.5,  0.5,  0.5, 1 },
    {-0.5,  0.5, -0.5, 1 },
    { 0.5,  0.5, -0.5, 1 },
    {-0.5, -0.5, -0.5, 1 },
    { 0.5, -0.5, -0.5, 1 }
};

LIST(Point3f) vertices;
LIST(int) triangleVertices;

float triangleVerticesArray[] = {0, 1, 2, 2, 1, 3, 2, 3, 4, 4, 3, 5, 4, 5, 6, 6, 5, 7, 6, 7, 0, 0, 7, 1, 1, 7, 3, 3, 7, 5, 6, 0, 4, 4, 0, 2};

int triangleVerticesArraySize = sizeof(triangleVerticesArray)/sizeof(triangleVerticesArray[0]);

for (int i = 0; i < triangleVerticesArraySize; i++ )
{
    triangleVertices.append(triangleVerticesArray[i]);
}

LIST( bool ) triangleIsInterior;
triangleIsInterior.resize( triangleVertices.size() / 3 );
triangleIsInterior.setGranularity( triangleIsInterior.size() );
memset( &triangleIsInterior[ 0 ], false, triangleIsInterior.size() * sizeof( bool ) );

for (int i = 0; i < 8 ;i++)
{
    Point3f tempPoint(myvertices[i].x,myvertices[i].y,myvertices[i].z);
    vertices.append(tempPoint);
}

for (int i = 0; i < planes.size(); i++)
{

    meshCut( vertices, triangleVertices, triangleIsInterior, planes[i], MESHCUT_DISCARD_FRONT);

}

[joesfer]

the code seems to cut the same mesh over and over again with different planes, but you're missing the part where the resulting mesh is pieced together after a cut -- that is, meshCut will return the cut triangles, but only flag those which are on the chosen side of the cutting plane (according to the supplied flag). Next on the original code is the purging of the vertices/indices corresponding to those discarded triangles before the resulting mesh is fed again to meshCut.

[sabotage3d]

I can't fully understand it can you point me to parts from the original code ?

[joesfer]

Yes, I had to read the code a bit more carefully to remember all of this: actually it all happens within the meshCut call and not as a separate process as I recalled it. The steps in meshCut.cpp are first the triangle splitting (meshCut.cpp, line 776), cleanup of resulting geometry to deal with degenerate cases, then we fill the hole left by the cut (so that the resulting volume remains closed), line 1026, and finally add the resulting triangles from the hole filling into the 'interior triangles' list (1048) -- This is not the best name, and should be clarified, the 'interior triangle list' contains those triangles which are inside of the original mesh after cutting it. Note this list is an input/output list which needs to be passed everywhere because further cuts may split interior triangles even more and we need to propagate their 'interiorness' to the resulting triangles. We finally purge the triangles according to the desired plane flag (1052) and finish up with some more geometry cleanup.

The final mesh going back to maya is a straightforward copy from the resulting data, in DelaunayNode.cpp line 566.

Some things to note which may help understanding the process: meshCut is designed to cut a closed mesh which describes a valid volume (for instance a torus or a cube, but not a bunch of cubes overlapping together like your picture seems to imply, because this will cause the hole filling heuristics to fail. This is probably what you're seeing). Also, the process of cutting a voronoi cell by splitting the mesh in two with successive planes works because the cell walls describe a convex volume, and thus the resulting piece is mostly convex (depends on the surface of the original mesh, but in most cases it will be). This may be easier to understand if you do some drawings, but what I want to stress is that the method can't be generallised to random planes describing a non-convex volume.

[sabotage3d]

Thanks a lot for helping out. I though that cutting by four planes is guaranteed to be convex ? In my failing test the idea was to describe 4 planes and cut the mesh like this. Is there any workaround to get something similar ?

[joesfer]

Yes, that case is well defined and should work well -- I was getting confused by your previous screenshot. I can't spot anything immediately wrong from your code, so lets simplify things: can you cut the box with only one plane and attach a debugger to meshCut to gather more information of what's going on? (especially around the purgeTriangles function, you can even disable the hole filling for a single cut and simplify the code even further). Should be a simple enough case to track down. You can also copy some of the debug code on the original delaunayNode.cpp to dump the cuts and intermediate steps to debug visually.

[sabotage3d]

My current problem is that I can do one cut with meshCut. I can't understand how to do multicut. Let say we cut by one plane and ignore hole filling everything works fine. When it comes to multiple planes I am getting confused . Do you remember the name of the algorithm that you are using ? I am after this in 3d .

[joesfer]

There's nothing particularly fancy about the algorithm, things just get more tricky once you add a 3rd dimension, and start handling degenerate cases etc. But at its core it is not very different from your image.

What we do is to split a mesh one triangle at a time. For each triangle, there's a few ways of cutting it by an arbitrary plane (excluding degenerate cases which lead to no cut), but the easiest thing is to do it incrementally one edge at a time, which is what meshCut does -- if you take a triangle and split one single edge in two, you'll see that the result is always two triangles (again, no degenerate cases), then we do the same with each intersecting edge (keeping track of the growing number of triangles we're producing), and we get our final tessellation. In 3D we just have a plane-segment intersection rather than line-line, but the procedure is analogous in 2D and 3D.

Here's a sketch, hope it helps:

Note that in the grand scheme of things, most of the complexity of the algorithm is on the tetrahedralization and voronoi diagram calculation, the mesh cutting shenanigans are only necessary because Maya's built-in plane cut function (which you can invoke from MEL) was not robust enough to handle trickier cases such as cutting a torus in half.

[sabotage3d]

I see it is similar to the algorithms I found. Let say we do MESHCUT_DISCARD_NONE and cut by 4 planes at the same time is there a way to maybe to flag the pieces and loop over them so that I can get separate pieces ? Do we keep track of any adjacency at the moment ?

[joesfer]

Not sure I quite follow what you mean: there's no cutting by more than one plane at a time (precisely because cutting is a serial process where the next plane that comes along needs to process the output pieces from the previous cut). DISCARD_NONE means "keep the pieces from both sides of the plane", that is, don't discard anything. Lastly, yes, there's an adjacency cache which is used to keep track of edges/triangles/vertices, used in the method as described above, not sure if this is what you meant.

[sabotage3d]

Yeah I understand what it does I was trying to get optimal performance for multiplane cut but at the same time preserve my chunks so that I can use them with bullet. But I am trying now naive approaches which are slow. By DISCARD_NONE I meant: mesh = box for each plane in planes: meshcut(box, plane,DISCARD_NONE)

Will end up with box cut by many planes then is there a way to split those chunk again ?

[joesfer]

You'd generate a new input mesh (or simply reuse the arrays) for all of the resulting chunks, and feed these to the next plane. In the specific case of voronoi cells, we generate each cell from the original mesh and split those with every wall of a given cell. The next cell comes along and starts from the entire source mesh again (imagine an interior cell for instance, where nothing of the original mesh surface is left remaining, but just the results of the hole filling). If what you're after is more a kind of random splitting, maybe you can lay it out more efficiently by precomputing which meshes are guaranteed not to be touched by a cut plane before you feed these to the mesh cutting.

[sabotage3d]

Well If keep cutting the same arrays all over and over again with DISCARD_FRONT I will end up with one chunk. If I cut by 4 planes I would like to have all the 9 chunks but I keep getting confused on how to do that.

[sabotage3d]

Is that a naive approach it looks like it will be expensive ?