TL;DR Mesh slicing... Anyone try to venture that way?

So I'm aware of this thread: 

But since it's from 2004, I wanted to ask.. are there any games since (or ever) that actually have real dynamic mesh slicing?

The only one that I know of that kind of does this is Metal Gear Rising Revenge..?

Anyone know / can guess, how they did this? Is this mesh slicing in real time? It doesn't seem precomputed at least..

I tried myself at programming a mesh slicing algorithm, the other day, but for my routine, at about 200 Vertices it gets too slow for real time.

Using this paper here:

http://www.dainf.ct.utfpr.edu.br/~murilo/public/CAD-slicing.pdf

(Obviously some bugs, face orientation messes up, and I have to say it was completely on the CPU, and didn't spend much effort optimizing anything)

Look at this: 

really a good game as well.

Slicing definitively realtime, remember software rendered games which did this for every polygon intersecting a frustum plane.

Maybe look for polygon clipping.

Here is a routine that i use in a preprocessing tool, but you need to build and triangulate the large poly where the volume intersects the plane alongside:

Edit: Thinking of it, you should use only convex polyhedra, so slicing always results in only convex polygons.

Complex shapes can be made by multiple convex shapes (like we do for physics collision detection).

And if you have poly adjacency information at edges, you can slice in order so the volume poly emits in correct order as well and no searching is necessary to connect unordered split edges. This way you also quickly reject polys that do not intersect the splitting plane.

	inline int32_t ClipTexmapPolygon (const TexmapPolygon *pin, const vec &plane, TexmapPolygon *pout, const int32_t space)
	{
		if (pout->numAvailableVertices < pin->numVertices + 1)
			pout->Resize (pin->numVertices + 1);

		int32_t i, curin, nextin;
		float curdot, nextdot, scale;
		TexmapPolygon::Vertex *pinvert, *poutvert, *nextvert;

		pinvert = pin->vertices;
		poutvert = pout->vertices;
		curdot = pinvert->puv[space].Dot (plane);
		curin = (curdot >= plane[3]);
	
		int32_t ret = -1; // assume inside

		for (i=0; i<pin->numVertices; i++)
		{
			nextvert = &pin->vertices[(i+1) % pin->numVertices];
			// keep if inside	
			if (curin) 
			{
				*poutvert++ = *pinvert;
			}
		
			nextdot = nextvert->puv[space].Dot (plane);
			nextin = (nextdot >= plane[3]);
			
			if (curin!=nextin) // add clipped vertex if plane splits edge
			{
				assert (fabs(nextdot - curdot) > FP_EPSILON);
				ret = 1; // clipped or outside
				scale = (plane[3] - curdot) / (nextdot - curdot);

				for (int32_t c=0; c<3; c++)
					poutvert->puv[c] = pinvert->puv[c] + (nextvert->puv[c] - pinvert->puv[c]) * scale; // position and 2 uc channels

				poutvert++;
			}

			curdot = nextdot;
			curin = nextin;
			pinvert++;
		}

		pout->numVertices = int32_t(poutvert - pout->vertices);
		if (pout->numVertices < 3) return 0; // outside
	
		return ret;
	}

12 hours ago, JoeJ said:

And if you have poly adjacency information at edges

something like a winged edge structure, right?

12 hours ago, JoeJ said:

This way you also quickly reject polys that do not intersect the splitting plane.

I think I get the idea of how the triangle adjacency information allows you to disregard the majority of triangles. Correct me if I'm wrong.. 

(1)Make an empty Set L of triangles (edges) T that intersect the plane.

(2) Pick any triangle (or edge) T that intersects the plane. (I have questions about this step actually*..)

(3) Add T to L. 

(4) Regard each adjacent triangle (edge) of T and check if it is intersecting the plane. If it isn't, you can disregard all its adjacent triangles (edges) (herein lies the major part of the optimisation for this algorithm). If one of them does intersect the plane, you take it as your current T and repeat the step.

*How do you find the very first T, that intersects, without looking up every triangle in the mesh until you hit one that intersects the plane? So the worst case is you check them all, the average case is somewhere around 1/2'N checks? Or is there a much better way that I'm missing here?

Regarding 

ClipTexmapPolygon (const TexmapPolygon *pin, const vec &plane, TexmapPolygon *pout, const int32_t space)

This routine constructs the intersection polygon of mesh and plane, right? Its a 2d polygon.

Viewing the parameter list, why is one vec enough to define the plane? Shouldn't there be a distance and a normal? Or a Point-on-plane and a normal?

59 minutes ago, teutoburger said:

something like a winged edge structure, right?

Not sure what that is, but i mean for each edge have indices to left / right triangle. Further The whole mesh needs consistent winding order (each triangle has clockwise vertices. The mesh needs to be closed... the typical requirements).

59 minutes ago, teutoburger said:

I think I get the idea of how the triangle adjacency information allows you to disregard the majority of triangles. Correct me if I'm wrong.. 

Find a edge that intersects the plane, split it and go to the left trianlge, find the other edge of that triangle that intersects the plane and continue with the other triangle from that edge until you get back to the starting edge. During that add each split point to the volume / plane intersection polygon. 

No Set required. Processing any edge just once. Works only for convex meshes (otherwise need to find all starting edges, not just any single one).

It's like cutting a mesh made of paper with a scissor, so just in order vs. poking individual cuts into random triangles like traditional frustum clipping would do. 

(I've just implemented tracing a crossfield on mesh surface, which is pretty similar and i used this simple algorithm without issues.)

59 minutes ago, teutoburger said:

*How do you find the very first T, that intersects, without looking up every triangle in the mesh until you hit one that intersects the plane? So the worst case is you check them all, the average case is somewhere around 1/2'N checks? Or is there a much better way that I'm missing here?

Yeah you are right - the need to find a single intersecting edge kinda destroys the advantage we do not walk to triangles not touching the plane while cutting.

But you could speed this up when everything else works as well: 

Pick a random vertex and select the edge closest to the plane, continue until you find an intersecting edge.

Again this works only for the convex case (and you may need more adjacency information like vertex knowing all its edges - pretty annoying to maintain

22 minutes ago, teutoburger said:

This routine constructs the intersection polygon of mesh and plane, right? Its a 2d polygon.

Viewing the parameter list, why is one vec enough to define the plane? Shouldn't there be a distance and a normal? Or a Point-on-plane and a normal?

All 3D. The routine processes a polygon with an array of 3 3D vectors, 'puv'. (I store 3D position and uv channels there)

My vec has storage for 4 numbers, so in this case i use plane[3] to store the plane distance to the origin. (confusing, but seems i was too lazy to create a plane class.) 

The original code came along Michael Abrashs Graphics Programming Black Book.

11 minutes ago, JoeJ said:

Works only for concave meshes

just to remove any ambiguity here, convex(?), you probably meant to say convex here, right? 

30 minutes ago, JoeJ said:

Works only for concave meshes

wait.... I think it would work for all convex meshes and also for those concave meshes without inner holes.

17 minutes ago, teutoburger said:

30 minutes ago, JoeJ said:

Works only for concave meshes

just to remove any ambiguity here, convex(?), you probably meant to say convex here, right? 

Ooops, i did it again. Convex is right, yes - fixed.

Just now, teutoburger said:

wait.... I think it would work for all convex meshes and also for those concave meshes without inner holes.

Yes, but you need to find multiple starting edges.

But the mentioned optimization to find a start edge would fail: I could get stuck in a sink. (I'm not sure at what complexity this optimization would be a win anyways, due to the need to maintain more adjacency).

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.)