Subtracting a shape/path from a triangle mesh

[alexisnaveros]

I realize it might be slightly out of scope for Clipper2, but I wonder, how would you subtract a shape/path64 from a mesh of triangles? Let's assume the triangle mesh has inner vertices and edges that must be preserved, so this is not just a matter of converting the triangle mesh into a bunch of contours (which would be kind-of trivial using a hash table of edges).

Awful way # 1 : One could subtract the shape/path64 from each triangle, build a hash table to look up a vertex index for any given resulting XY point, then rebuild a triangle mesh with shared vertices.

Awful way # 2 : Or, one could merge the triangle mesh as a bunch of contours (using a hash table of edges), and subtract from that shape. And then... one would do a boolean AND (intersection) between the result and each triangle, to see what part of each triangle (if any) survived the subtraction?

Instead, would it be possible with Clipper2 to clip all triangles in one pass, without having the library merging them as one big shape? Could each triangle be a "subject" path, and we subtract a "clip" path from all of them? And, in the results, getting the contour of each piece of (surviving) input triangle as an independent path?

Thanks. If there's no nice way to do that with Clipper2, other ideas are also very welcome to solve that efficiently.

[AngusJohnson]

If your shape is rectangular then use RectClip.
Otherwise, you're probably best using a Sutherland–Hodgman implementation.

[alexisnaveros]

Right. That would be similar to the "Awful way # 1" above, except using an efficient algorithm suited to convex shapes (triangles).

So one would, for every single triangle, cut the "clip shape" down by the triangle's edges, then build a hash table of all final vertices by XY, and rebuild a connected mesh... I admit that solution did sound pretty awful yesterday, but now I realize it's highly parallelizable (SIMD, threads, GPU shaders, whatever) as you repeat exactly the same steps for every triangle. I think that works pretty well, thanks!

The context is to draw separately the inside/outside regions of arbitrary shapes, for 3D terrain visualization (hence why preserving the inner vertices/edges is important). If you think 3D triangle mesh top-down clipping might not be out-of-scope for Clipper2, I'll share my code in case you want to get something out of it.

[AngusJohnson]

If your shape is simple (no possibility of self intersections) then clipping with triangles should be a very simple algorithm, especially if they all have the same orientation.

Re 3D clipping, thanks for the offer of sharing code but i don't have the resources for that.

[alexisnaveros]

Right. The code is looking pretty simple and SIMD-friendly; the big drawback is having to call my shape->triangle tesselation code whenever a triangle is cut as a non-convex shape, and that's a huge dependency.

So it would only be appropriate to possibly include triangle mesh clipping in Clipper2 if you were to also include generic triangle tesselation code (I think you mentioned somewhere that's being considered).