Ability to cut models?

[eyal0]

This seems like a feature that users might want: The ability to cut large models into smaller pieces in case a model doesn't fit on the platform. It's also useful when a model has a lot of details and doesn't have a nice surface for printing. Users can slice the model in half and print each half, then glue it together.

I've already started thinking about how to implement cutting a model. I think that I could get it to work. Would you want to add that feature?

[kennethjiang]

Appreciated your actively improving Slicer plugin @eyal0

My biggest question is how users can interact with the plugin to cut the model. Are we going to show them a virtual plane that they can drag around to rotate/position it? Also do we need to implement an 'undo' if the cut doesn't turn out what they want?

[eyal0]

Maybe we only cut on x=0? That would keep it simple. I don't think that an undo button is necessary because users can always just remove the pieces and add the model again.

We should definitely aim to keep it simple. Perhaps we could look at how other slicers do it and copy ideas? Slic3r, cura, m33 fio?

On Oct 2, 2017 16:37, "Kenneth Jiang" notifications@github.com wrote:

Appreciated your actively improving Slicer plugin @eyal0 https://github.com/eyal0

My biggest question is how users can interact with the plugin to cut the model. Are we going to show them a virtual plane that they can drag around to rotate/position it? Also do we need to implement an 'undo' if the cut doesn't turn out what they want?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/kennethjiang/OctoPrint-Slicer/issues/135#issuecomment-333536616, or mute the thread https://github.com/notifications/unsubscribe-auth/AAGs8aURB5owU5mCP__jt0NQV4kqzy8Sks5soOcygaJpZM4Pp8Ad .

[kennethjiang]

Agreed that we should use other slicers as references to optimized user experience, and strive to make it even easier (because IMO most slicers are too difficult to use).

I will play with Cura/Slic3r when I get a chance today to see how they implement cutting models.

[donovan6000]

M33 Fio does it by allowing the user to position a stencil shape (cube or sphere) in the place where they want the cut to be performed, like this. It's simple, but it can be kinda frustrating when trying to position the cut perfectly since it doesn't have a way to undo it.

[eyal0]

@donovan6000 I see that you're using the ThreeCSG library. I read the code and the open issues. It seems that it isn't maintained. :-(

Some of the issues complain that it makes non-manifold STL. Slicers might still work with non-manifold STL by repairing it but it would be nicer if it made legal STL in the first place!

ThreeCSG does more than what most users need: it will let you subtract any shape from an object. For most users, I think that simply cutting along a plane would be enough. I think that I could do that without making non-manifold surface.

@kennethjiang I like the floating cut surface idea that is semi-transparent, like M33-Fio. You could limit it to planes where X, Y, or Z equals a constant. So cuts would always be parallel to one of the 3 planes. Let the user move a dot around in 3D and which ever dimension (X, Y, or Z) is farthest from the origin, that's the normal to the cutting plane. That would let a user choose the cut by moving just 1 dot around. Probably not many users want to cut along a diagonal.

I'm not sure about how to provide a nice UI for undo. Maybe the right thing to do is provide a preview? Rather than show a plane for the cut, show the result after the cut is done and let the user move it around until happy. Then the user clicks "apply". I think that this is similar to how Slic3r does it.

[John-Mc]

@eyal0 - If a user really wanted to cut along a diagonal, could they accomplish that by rotating the object instead of rotating the cutting plane? Object rotation is already part of this plug in.

[kennethjiang]

After looking at how other slicers handle 'cut', I'd propose:

• This feature should be kept very simple and straightforward. Anything more than that should be handled in 3D modeling (TinkerCAD) or mesh fixing tools.
• A menu item 'cut' is added inside menu '...' . When it is selected, a simple dialog pops up to ask user 'the z-height (mm) of the cut'.
• User enters the z-height, we cut all the models on the build plate along the plane z=z-height.
• All parts are then re-arranged so that none of them are in mid-air or stack on each other.

Like what @John-Mc said, users can rotate the model itself when they want a cut a different angle than a z-plane.

Comments?

[eyal0]

@John-Mc Yes, the user could rotate before cutting. That's why we can keep it simple. Users that require more complicated cuts can rotate the object first themselves.

@kennethjiang I agree with all that except that I'm not sure about the z-axis. I see a couple reasons why cutting at X=0 might make more sense:

• With X, you can have a reasonable default: X=0. With Z, you can't have a reasonable default of Z=0 because all shapes are at Z>0. You could have default z=height/2 but that's not a constant and so it might be confusing.
• X=0 makes sense for a lot of shapes. Imagine that you wanted to cut a dinosaur in half. Or a skull. Or a pokemon. You would probably do it at X=0 because most natural shapes (people, animals, vehicles, homes) have side-to-side symmetry. When cutting is activated, X=0 is shown as default and the user adjusts it.

I agree without doubts about the rest:

• Just simple cuts, let the user go to fancy tools for anything else.
• Inside the ... menu, it doesn't need to be a top-level button.
• After cutting, arrange the shape again, just like when shapes are separated.

Whether it's Z or X, will the user type in the offset or will there be a plane to move around, like with M33 Fio? Moving a plane around is more complicated to implement but probably more user-friendly because they can see what is happening. Perhaps have a plane and a number, just like how rotation lets you use mouse or keyboard.

One final thing that I thought about: the icon. M33 Fio uses scissors, which were confusing for me for two reasons:

• Scissors cut thin things like paper, not 3d objects.
• Scissors already mean cut in "cut-and-paste". This confused me.

I think that the icon should be a saw. A saw seems like a natural way to cut a shape. Something like this but in a style that matches the current icons:

[kennethjiang]

@eyal0 I agreed with most of what you said. However, I still feel cutting along Z is a slightly more straightforward concept to most users because:

• We will also accomplish a feature that users have asked: z-offset. Actually more users have asked for z-offset than for the cutting model.
• Z-axis is special in 3D printing. Therefore most users are probably more used to processing a model along z-axis than along x or y.
• There is no guarantee that a symmetric model is symmetric with x=0. It could be y=0, or (x=1,y=1). Users probably won't help but asking "why can't I do that on y=0? did I miss something?"

To make it simple, I'd suggest we don't even draw a cutting plane. Just use a dialog popup to let user enter z-height. This way we don't have to make much changes to slicer.js or ViewPort.js, which are already complicated and bug-prone.

Using a saw icon is a great suggestion!

[eyal0]

I've made some progress on this. You can see the results below where I chopped a complex dinosaur shape in two.

The code to do it is on this branch of 3tk. There's a new class called ConnectedSTL that has a few functions including chop. Using chop looks like this:

let connectedSTL = new ConnectedSTL().fromBufferGeometry(geometry);
let newConnectedSTLs = connectedSTL.chop(new THREE.Plane(
    new THREE.Vector3(0,0,1), -10));
newConnectedSTLs[0].bufferGeometry();  // Returns the bottom 10mm of the object.
newConnectedSTLs[1].bufferGeometry();  // Returns the top of the object.

I'm still working on improving performance. I'll also make some drawings and write up how it works.

If you want to try it, check out the branch and run:

env INCLUDE_LARGE_TESTS=1 WRITE_TEST_OUTPUTS=1 npm test

It will fill the current directory with a few output STL files that you can view.

[eyal0]

I'll try to explain here how it works. First, I'll explain splitFaces. splitFaces(plane) takes all the faces in an STL and subdivides them as needed so that all the faces are either entirely on one side of the plane or the other. For example, if we start with the black triangle and the red plane:

We can split on the top edge into two faces, the blue and the green:

That's just the split of the top edge. We can see that the bottom right edge still needs splitting. We process each edge of each face, splitting when needed.

In an STL file, though, each edge is connected to exactly one other edge. When we split one face, we have the split the other face, too, or else the shape is no longer legal. So we split them both:

The bottom triangle become the blue and green and the top triangle became the purple and orange.

To find the split point, we just find if the edge crosses the plane and then where it crosses. That's easy. The problem is that, due to rounding, after we find that point, it might not be exactly in the plane. For example, we might find that the plane crosses the edge at X=5 but when we calculate the intersection, we get 4.99999993, due to floating point issues. To solve this problem, we keep a list of all XYZ coordinates that are considered to be "in the plane". So if a coordinate is in the list, the distance from the plane to that coordinate is considered to be exactly 0, even if it isn't exactly 0.

Every time that we do a split, we get two triangles that don't need more splitting (purple and blue) and two that do (green and yellow). To save on computation time, we modify the existing face so that the current face might need more splitting and the face that doesn't need more splitting gets added to the end. That way when we're looping over all faces, we don't need to loop over any of the new faces added to the end.

When we're all done, we return the list of XYZ coordinates that are considered to be in the plane. We use that list for the next steps...

[eyal0]

To chop(plane), we first splitFaces(plane). That gives a Set of points that are in the plane. Next, we disconnectAtSplit, which creates two new ConnectedSTLs, one for each side of the split. The new ConnectedSTLs will not be manifold because there will be a hole where the shape was disconnected. The object on the left is what it looks like. The goal is then to seal that hole, so that it looks like the object on the right:

This is the hardest part of it. Here's how it's done:

Imagine that we just a simple cube:

Where the cube is chopped there are 4 edges on the plane. Each edge has a direction and the end of each is connected to the start of the next because the original object was manifold. To seal this hole, we need to "clip ears". That is, we find two connected edges and make a face using those and a third connecting the ends:

Now the hole is just the bottom left triangle. We can continue steps like that to finish the job. This only works for shapes that are convex and have no holes. What if there is a concavity? Imagine that chop an L-shape:

The edges look like this:

We again "clip ears" but we need to be careful to choose only convex ears. If we pick incorrectly, we might get this:

That face would be outside the shape and also facing in the wrong direction. So to prevent this, we make sure that the center point of the face that we make is convex. We know that the point with minimum x and minimum y must be in the convex hull, so we just always use the minimum points.

There's also another problem: We can't get lines cross. For example, if we make a face for the bottom left point:

The green face crosses the boundary of the shape into an area outside the shape. To prevent this, we search all the edges for any endpoints that are inside the triangle. If we find one, we use that point to make a face instead of the third point. So in the example above, the top left point is not used and the center point is used instead:

Every time that we make a new face, we add the edges of that face to our list of unconnected edges. Then we go through that list and look for edges that match (head to tail, head to tail). So after the triangle above, the remaining unconnected edges are:

We can repeat the algorithm:

1. Find a convex "ear".
2. Look for points inside the face. If found, use that instead of the third point.
3. Make the face using those points.
4. Connect the matching edges (head to tail, head to tail) and remove matched edges from the unconnected list.

We continue this until there are none left. When it's done, the shape is sealed.

There are still a few things that we need to do to fix up the shape after that...

[eyal0]

There are some functions that we can use to clean up the shape before and after we do anything. One of them is to remove all faces that have a normal of 0. There are two ways that it can happen:

1. Two of the vertices are the same.
2. All the points are coplanar.

(Imagine that the purple triangle has the bottom two points in the same location and that all the green triangle's points are on the same line.)

There are some cures for this. For the first case, we can simply remove the triangle and connect the faces. The example on the left becomes the example on the right:

The purple triangle is deleted.

For triangles that are 180 degrees, we can do a "flip". We change the edge so that it divides that four sides with a different angle:

In that example, we changed it so that the line dividing those four sides goes from left to right instead of top to bottom. That eliminates the green triangle with a 180 degree angle.

By repeated apply these operations on faces with normal=0, we can get rid of all of them until all the faces have a non-zero area.

[eyal0]

After we have the above procedure to remove faces with no area (normal = 0), we can make a routine to merge faces. Merge faces allows us to remove extra faces.

Every side of an object has 3 or more edges. The number of triangle faces to make the side should be 2 less than the number of edges. For example:

Both triangulations make the same hexagon but the one on the left uses just 4 triangles, which is optimal. The one on the right uses 6, which is non-optimal. The one on the left will make for smaller files.

We can convert non-optimal sides on shapes to optimal sides by moving a vertex and then remove degenerates. For example:

If we slide the purple vertex in the direction of the red arrow, we can make two of the triangles degenerate (bottom left triangles). Then we can delete those using the procedure above and we are left with just 4 triangles, which is optimal.

We can't always slide a vertex. For example, if we move the vertex at the corner of a cube, the cube's corner will disappear. We can only move a vertex if the shape of the object will be unchanged. To test for that, we check that the normal of every face affected by the move is unchanged. And to test that normals are unchanged, all normals must be valid, so we need to remove degenerate triangles. So the procedure is this:

1. Remove all degenerates (as above).
2. For each edge:
   1. Try to collapse the edge to length 0 and see if the normal of any of the faces that use that vertex is changed.
   2. If there all normals are unchanged or 0 (because the collapsed edge will become 0), do the collapse and then remove all degenerates from affected faces.

The compare function for normals needs to be smart because floating point errors can sometimes have a normal change from 1 to 0.999999993 so mergeFaces takes as input a compare function. The compare function gets two normal vectors and determines if they are "the same". For example, if the difference angle between them is less than 0.0001.

Here's a before and after where the number of faces went from 44 to 20:

mergeFaces can also be used to intentionally decrease the detail in a shape to save size. For example:

Here we have run mergeFaces using a compare function that returns true if two angles are within 2 degrees of each other. We can see on the left the original, using 205610 faces. The shape on the right uses just 89806 faces, so 43.6% of the original size. We can see that the number of faces is decreased where the shape is mostly flat.

[kennethjiang]

Thank you so much @eyal0 for this awesome work and detailed explanations. I ran the tests and they seem reasonably fast.

Are you ready to send a PR for your work?