I see.. so you split up a mesh into its convex sub-meshes (with all triangles clockwise), and you have a winged-edge-equivalent structure (that's exactly what you mean by the adjacency information for each vertex, edge and face).

Yes so, the problem remains with finding the first intersecting edge. If you randomize the picking of the first vertex, then you have the best average case performance, but it can still happen that it's the worst case.

The algorithm I used so far, needs a preordered mesh as input mesh.

For each Triangle you note its zMin and zMax. That's simply the smallest (largest) z component of the triangles vertices.
Then you order the triangles by their zMin. (You could also save the mesh to file in that face order)

Then you can intersect the mesh with any plane in distance D parallel to the xy-plane (meaning the plane containing the x and y-axis), pretty optimally, by disregarding all triangles that either have zMax < D or zMin > D.

1 hour ago, JoeJ said:

There is however a algorithm to calculate a cut graph for a mesh that cuts it to a topological disc. (Using spanning tree and it's dual, i'd need to look it up...) Eventually you could precompute that cut graph, and then only check those edges to find intersecting edges. But i need to think about this for some time - not sure if it works yet... (Also unsure if you'd need to recalculate this graph for sliced pieces so you can slice tham again - that would be much worse than just checking all edges.)

Thought about it. It would work with minor modifications for something like a torus, but it would fail for a bumpy torus with sinks on the surface, so useless.  

55 minutes ago, teutoburger said:

The algorithm I used so far, needs a preordered mesh as input mesh.

Thought about presorting as well, but i end up preferring either a tree or sorting in 3 axis to lift the 1D restriction. And rebuilding / adapting that stuff for both split pieces? Only worth if you have really high resolution meshes. Checking all vertices against the plane has perfect caching so brute force will be hard to beat i guess.

Note that if you restrict yourself to convex meshes the 'walk from random start towards the plane' approach will be best, similar runtime than hopping in a presorted list or walk a tree but no additional data structure required.

Edit: Presorting does not require to rebuild or adapt anything after the slice, right? And using 3 axis and selecting the best fit should work as well? You would need to create a bounding box of the plane intersetion with the objects bounding box, and then check all edges within that i guess, (so still a lot in worst case).

1 hour ago, JoeJ said:

but no additional data structure required.

Yup, none but the adjacency structure, which can be built offline, so who cares.

1 hour ago, JoeJ said:

Edit: Presorting does not require to rebuild or adapt anything after the slice, right?

Not for the original mesh. But you now have two new split meshes, each one having an open section, where the plane cut through. That will have to be closed up still. This means, clockwise-ordering the segments, that make up the 2d polygon (which is a convex one, if you had a convex mesh to begin with) and then triangulizing the 2d-polygon (splitting it into clockwise triangles). And lastly adding the new triangles to each of the new split meshes to close the open section.

Edit: Actually its a 3d polygon, in terms of data (made up of 3d vertices) but it "lives" in the slicing plane.

2 hours ago, JoeJ said:

And using 3 axis and selecting the best fit should work as well?

That gets my brain into a knot. You'd have to order the triangles by projected-distance on the vector going from origin to plane. So for each triangle, you project each vertex on to the vector going from origin to plane.

This gives you a Vmin, and Vmax for each triangle. Corresponding to the zMin and zMax of the 1D approach outlined above. The preordering here is more costly. There's the projection (actually not sure how that is accomplished exactly, something with dot product maybe?) and the length involves a square root, which maybe you can avoid by using the squared length? 

Edit: or perhaps I'm missing completely out on what you meant by the best fit 3 axis approach... 

59 minutes ago, teutoburger said:

Not for the original mesh. But you now have two new split meshes, each one having an open section, where the plane cut through. That will have to be closed up still. This means, clockwise-ordering the segments, that make up the 2d polygon (which is a convex one, if you had a convex mesh to begin with) and then triangulizing the 2d-polygon (splitting it into clockwise triangles). And lastly adding the new triangles to each of the new split meshes to close the open section.

Ah yeah, i ignored you need to add new stuff no matter if you sort tris / edges or verts. So resorting (at least insert) unavoidable, which means you run over the entire sorted list to copy and resort it. Further, if you use 3 axis, you can't sort primitives but just indirection indices, so jumping around in memory a lot until you find first and last element in range, making a win over brute force again unlikely.

9 minutes ago, teutoburger said:

or perhaps I'm missing completely out on what you meant by the best fit 3 axis approach... 

I meant 3 independent sorted lists of indirect indices to triangles (or edges), and you pick the one best fitting the plane normal. The worse the fit, the larger becomes the volume containing potential intersecting edges.

However, you spend a lot effort maintaining a data structure that you need only one times. Likely this has the same cost as brute force search while throwing other data out of cache. Convex decomposition to avoid all this seems much more attractive, which is necessary anyways if you want to do collision detection for the pieces.

You could order the primitives themselves by morton code in memory, which improves caching in any case.

You may be interested in the following GDC 2015 presentation: "Mesh Cutting in Farming Simulator 15", http://www.dtecta.com/files/GDC15_VanDenBergen_Gino_FS15.pdf

Looking at the convex decomposition image from that presentation it becomes clear to me that this is not really a option for detailed visual meshes.

I think creating clusters of triangles with a bounding box might be better than sorting: Checking all boxes with brute force is fast, then checking all edges per cluster remembering split edges and eventually intersections. During the scissor walk results could be reused.